Introduction to Information Security

Quizzes

Quiz 2 Q2 (Meet-in-the-middle)

(Meet-in-the-middle) Suppose instead of using triple DES, DES is being applied 6 times. Under known-plaintext attack, what would be the approximate key strength? (note: a single DES is 56 bit)

• 112
• 280
• 144
• 336
• 168

Answer

$2(2^{56+56+56})=2^{169}⟹\text{approx. 168}$

Quiz 2 Q3

Consider a block cipher where each block is 8 bits. The following is a 5-block ciphertext (in hexadecimal) under ECB mode:

$$\text{06 A9 F3 36 A9}$$

Which are possible plaintexts (see Question in Canvas for choices)

• $\text{00 00 00 00 00}$
• $\text{00 05 FF 00 05}$
• $\text{00 0A 0C FF 0A}$
• $\text{00 01 02 03 04}$

Answer

• $\text{00 0A 0C FF 0A}$

Quiz 2 Q4 (Padding Oracle)

(Padding Oracle) Consider padding oracle attack described in this course. Suppose the ciphertext consists of 3 blocks

$$v,c_1,c_2$$ where v is the IV. The attacker knows the last byte in the plaintext and now want to find out the 2nd last byte. To carry out the attack, the attacker would next ____.

• M1: iteratively modifies
  $v$ to get
  $v^{\prime }$, and sends
  $(v^{\prime },c_1,c_2)$ to the oracle.
• M2: iteratively modifies
  $v$ to get
  $v^{\prime }$, and sends
  $(v^{\prime },c_2)$ to the oracle.
• M3: iteratively modifies
  $c_1$ to get
  $c^{\prime }$, and sends
  $(v,c^{\prime },c_2)$ to the oracle.
• M4: iteratively modifies
  $c_1$ to get
  $c^{\prime }$, and sends
  $(c^{\prime },c_2)$ to the oracle.

Answer

• M3
• M4

Recall:

For ciphertexts with only 1 block, when decrypted, AES-CBC decrypts with the key, then XORs the result with the IV.

However, for ciphertexts with multiple blocks, only the first block is XOR-ed with the IV, with the subsequent blocks being XORed with the ciphertext of the previous block (e.g. Block 2 uses XORs the result from the decryption with the ciphertext of Block 1 to obtain the plaintext of Block 2)

Quiz 3 Q1 (Entropy)

(Entropy) Alice chooses her password in this way:

1. Randomly picks one of the 1024 pokémons, e.g. evee.
2. Keeps the first 3 characters, e.g. eve.
3. Next, flips a coin. If “head”, capitalizes the first character, e.g. Eve, and that will be the password. Otherwise, the password is the original, e,g. eve.

What is the entropy of Alice’s password?

Answer

Method 1: Count all the combinations:

$1024\times 2$. Note that every combination occurs with equal probability.

$$\text{Entropy}={\log }_2(1024\times 2)=11$$

Method 2: Note that step (1) and (3) are independent. So, we can add the entropy introduced in (1) & (3).

$$\text{Entropy}={\log }_2(1024)+{\log }_2(2)=11$$

Note: Entropy depends on the source’s randomness, not the final representation. So,

${\log }_2(2\times 26\times 26\times 26)$ is wrong!

Tutorial 2

Q1

You have intercepted two ciphertexts

$C_1$,

$C_2$ generated by a stream cipher using the same secret key. The first 4 bits of the ciphertext form the

$\text{IV}$.

$$C_1=\text{0111 11011011}$$

$$C_2=\text{0111 00101011}$$ You know that the plaintext must be among the following 4 sequences:

$$P_1=\text{00000000},P_2=\text{11111111},P_3=\text{00001111},P_4=\text{11000011}$$ What are the possible plaintexts of

$C_1$ and

$C_2$ ?

Answer

Refer lecture slides on stream cipher.

1. Let
   $m_1$ and
   $m_2$ be plaintext of
   $C_1$ and
   $C_2$ respectively. Let
   $K$ be a long sequence.
2. We know
   $C_1=m_1\oplus K$ and
   $C_2=m_2\oplus K$.
3. So,
   $C_1\oplus C_2=m_1\oplus m_2=\text{11110000}$.
4. By writing a simple program to test the combination of
   $P_1,P_2,P_3$ and
   $P_4$, only
   $P_2\oplus P_3$ produces
   $\text{11110000}$

Q2 (Meet-in-the-middle)

(Meet-in-the-middle) Instead of applying DES three times, Bob wants to apply it four times with 4 different 56-bit keys

$k_1,k_2,k_3$ and

$k_4$. By using meet-in-the-middle attack, what is the of number of cryptographic operations (including encryption and decryption) required for known-plaintext attack? Give your answer in the form of

$2^k$ and approximation is suffice. (Remark: Lecture note mentioned that there is a more efficient meet-in-the-middle attack. Here, we only consider the “simple” meet-in-the-middle given in the lecture note).

Answer

• Need to meet at Y
• From m to Y:
  $2^{56+56}$
• From c to Y:
  $2^{56+56}$
• Total:
  $2^{113}$

Q4 (Padding Oracle)

(Padding Oracle) Consider the padding oracle attack described in the lecture note. Suppose the attacker knows that the 16-byte plaintext is the sequence

$$⟨b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8,b_9,00,00,\text{FF},04,04,04,04⟩$$, where the numbers are in hexadecimal representation, and the attacker does not know the value of the

$b_i$’s. Describe how the attacker determine the value

$b_9$. In particular, describe how the value of

$v$ in the lecture note is to be computed.

Answer

1. We want to find out
   $b_9$ and want padding oracle to return TRUE
2. So need last 8 bytes to be
   $08$
3. Note:
   $00\oplus 08=08$,
   $\text{FF}\oplus 08=\text{F7}$,
   $04\oplus 08=\text{0C}$
4. So,
   $v=\text{IV}\oplus ⟨0,0,0,0,0,0,0,0,t,08,08,\text{F7},\text{0C},\text{0C},\text{0C},\text{0C}⟩$
5. When padding oracle output TRUE, we know
   $t\oplus b_9=08⟹b_9=t\oplus 08$

Q5

Lecture note assumes that the attacker knows how many bytes are being padded. Now, we consider cases where such knowledge is not available. Let us consider an attacker who has the one-block

$\text{IV}$, and a 2-block ciphertext. The attacker does not know how many bytes are being padded. Give a method to determine the number of padded bytes. Use as little calls to the oracle as possible.

Answer

1. s

Improvement: Use Binary Search

Tutorial 3

Q1

This is a paragraph from

$\text{RFC4086}$ mentioned in Lecture 2 on password strength.

Assume that user passwords change once a year and that it is desired that the probability that an adversary could guess the password for a particular account be less than one in a thousand....

To have a one-in-a-thousand chance of guessing the password in 500,000 tries implies a universe of at least 500,000,000 passwords, or about 2^29. Thus, 29 bits of randomness are needed. This can probably be achieved by using the US DoD- recommended inputs for password generation, as it has 8 inputs that probably average over 5 bits of randomness each (see section 7.1). Using a list of 1,000 words, the password could be expressed as a three-word phrase (1,000,000,000 possibilities). By using case-insensitive letters and digits, six characters would suffice ((26+10)^6 = 2,176,782,336 possibilities).

For a higher-security password,...To go to a one-in-10^9 chance, 49 bits of randomness are needed, implying a five-word phrase or a ten-letter/digit password.’’

The above mentions three methods to generate passwords. Let’s consider the second method (i.e. choosing 3 words from a dictionary of 1000 words). Suppose we want to have 50 bits of randomness and using the same 1000 word dictionary, how many words are required in a password? (assume with replacement)

Guideline on entropy required. The above

$\text{RFC}$ doesn’t explicitly state how much entropy is sufficient to prevent online dictionary attack. Implicitly, it suggests 29 bits or 49 bits for “higher-security”.

Answer

Tutorial 4

Q5 (Design of mac)

(Design of mac) It is tempting to design a mac using encryption. Given a message

$m$ and key

$k$, the mac is

${\text{ENC}}_k(H(m))$ where

$H(\cdot )$ is a collision resistant hash, and

${\text{ENC}}_k(\cdot )$ is a symmetric key stream cipher, for instance

$\text{AES CTR}$ mode.

Explain why it is not a secure mac.

Answer

1. Suppose the adversary has a valid pair of
   $m$ and
   ${\text{mac}}_k(m)$.
2. The adversary wants to pretent
   $m_{\text{fake}}$ is from valid source, so need to forge
   ${\text{mac}}_k(m_{\text{fake}})$.
3. Since
   ${\text{mac}}_k(m)=H(m)\oplus K⟹K={\text{mac}}_k(m)\oplus H(m)$.
4. So,
   ${\text{mac}}_k(m_{\text{fake}})=H(m_{\text{fake}})\oplus {\text{mac}}_k(m)\oplus H(m)$.
5. The adversary has successfully forged a mac.

Remark: For certain choice of encryption schemes, the above hash-and-encrypt can give a secure mac. What we have shown above is that, in general, an encryption scheme, which is secure w.r.t. confidentiality, does not guarantee to give a secure mac. So, confidentiality is not sufficient to give integrity.

Tutorial 5

Tutorial 6

Tutorial 7

Q3 (Hash Tree)

(Hash Tree) A storage system maintains an archive of files

$f_1$,

$f_2$,

$\dots$. The files arrive sequentially, where

$f_i$ arrives earlier than

$f_j$ for any

$i<j$. Each file could be very large, e.g. each could be an image and the whole sequence is a video. The system consists of two sub-systems:

(a) A large, fast but untrusted storage. It is untrusted in the sense that attacker might able to modify the data.

(b) A small, slow but trusted storage. It is trusted in the sense that attacker is unable to compromise its integrity. Let’s call data stored here the meta data.

Whenever a new file arrives, the system writes the file to the untrusted storage and updates the metadata. A user can submit a query

$i$ and obtain

$f_1$,

$\dots$,

$f_i$ that are retrieved from the untrusted storage, and some data (let’s call it “digest”) from the trusted storage. Since the large storage is untrusted, the files could be modified. The user can use the digest to verify integrity of

$f_1$,

$\dots$,

$f_i$.

Here is one straightforward design. The trusted storage keeps the

$\text{SHA3}$ of each file. On query

$i$, the trusted storage simply sends:

$$⟨\text{SHA3}(f_1),\text{SHA3}(f_2),\dots ,\text{SHA3}(f_i)⟩.$$

We can treat

$⟨\text{SHA3}(f_1),\text{SHA3}(f_2),\dots ,\text{SHA3}(f_i)⟩$ as a digest of the sequence of files

$⟨f_1,\dots ,f_i⟩$. Let us write it as

$$H(⟨f_1,\dots ,f_i⟩)=⟨\text{SHA3}(f_1),\text{SHA3}(f_2),\dots ,\text{SHA3}(f_i)⟩$$

The user, after received

$f_1,\dots ,f_i$ and the digests

$H(⟨f_1,\dots ,f_i⟩)$, can then verify the integrity of each file. Note the reply consists of

$i$ digests, which incurs high communication overhead. We want to lower the traffic overhead, while keeping computation overhead low. More specifically, we want it design a new hash

$\tilde{H}()$ and a data structure for the metadata such that:

R1. When a new file

$f_i$ arrives, the computation required to update the metadata is low.

R2. When given a query

$i$, the computation required to extract the digest

$\tilde{H}(⟨f_1,\dots ,f_i⟩)$ is low.

R3. When given a query

$i$, the digest

$\tilde{H}(⟨f_1,\dots ,f_i⟩)$ is short.

Of course,

$\tilde{H}()$ has to be secure, i.e. collision resistant. That is, it is difficult to find two sequences of files having the same digest under

$\tilde{H}()$.

(a) Give a method to meet the requirement. (Hint: Use a chain.)

(b) Give a method for more general queries. The query is

$i,j$, and the output is the sequence

$⟨f_i,f_{i+1},\dots ,f_j⟩$. (Hint: Use hash tree.)

Answer

(a)

• Let
  $h_i=\text{SHA3}(h_{i-1}||\text{SHA3}(f_i))$ where
  $h_0$ be the string "
  $0$" and
  $||$ is string concatenation.
• The system takes
  $h_i$ as the digest of
  $⟨f_1,f_2,\dots ,f_i⟩$. The system keeps the
  $h_i$'s as meta data.
• When a new file
  $f_i$ arrive, compute
  $h_i$ and store it in the trsuted storage. Note that this is done with only one hashing.
• For the query
  $i$, read
  $h_i$ from the storage and return it.

(b)

• Use a hash tree a.k.a Merkle Tree
• Given
  $f_1,f_2,\dots f_n$. Consider a tree with all the
  $\text{SHA3}(f_i)$'s as leaves.
• For each intermediate node, its value is
  $\text{SHA3}(h_{\text{left}}||h_{\text{right}})$ where
  $h_{\text{left}},h_{\text{right}}$ are its children.
• If the intermediate node has only one child, then the right child is taken as a special string (e.g. "
  $0$").
• When a new file
  $f_{n+1}$ arrives, the meta data can be updated using around
  ${\text{log}}_{2}n$ hash operations.
• Queries on
  $(i,j)$: consider the subtrees with the
  $f_i,\dots ,f_j$ as leaves. Output the roots of the subtrees as digest.

AY2425 S1 Midterm

Q11

Lecturer highlighted that a typical attack model would formulate the attacker's goal and the attacker's capabilities. In the case of "known plaintext attack", what is the goal and capability?

A. Goal: Not specified; Capability: Attacker has pair(s) of plaintext the corresponding ciphertext.

B. Goal: Not specified; Capability: Attacker has access to a decryption oracle.

C. Goal: Find the secret key; Capability: Attacker has pair(s) of plaintext the corresponding ciphertext.

D. Goal: Find the secret key; Capability: Attacker has access to a decryption oracle.

E. Goal: Find the secret key; Capability: Attacker has many ciphertexts.

Answer

A

Following the lecture note formulation, "Known plaintext attack" only specifies what the attackers have. For instance, in a known-plaintext attack, an attacker might have many pairs of plaintext and the corresponding ciphertext. Now, when given a new ciphertext, the attacker wants to know whether its plaintext is "YES".

(optional: this is known as KPA-IND, indistinguishability under known plaintext attack).

Q15 - Q18 (Padding Oracle Attack Calculation)

All the followings are encrypted using CBC mode and each block consists of 16 (sixteen) bytes. Numbers written in the form x00 are in hexadecimal format. E.g. x0F represents the value 15 (fifteen). A single block (x10,x10,…,x10) is considered "Correctly padded".

Suppose the attacker knew that a 16-byte plaintext was of the following form:

$$(b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8,b_9,b_{10},b_{11},b_{12},b_{13},b_{14},\text{x03,x01})$$ The attacker did not know the value of

$b_i$'s. Let

$\text{v}$ be the one-block IV and

$\text{c}$ be the one-block ciphertext of the above plaintext.

$$\text{v}=(v_1,v_2,v_3,\dots ,v_{16})$$

$$\text{c}=(c_1,c_2,c_3,\dots ,c_{16})$$ The attacker is given

$\text{v}$,

$\text{c}$ and wants to find out the value of

$b_{14}$. Following oracle attack in the lecture, what could be the next query to be sent?

A.

$\text{(v,c')}$, where

$\text{c'}=(c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10},c_{11},c_{12},c_{13},c_{14},c_{15}\oplus \text{x03},c_{16}\oplus \text{x03})$

B.

$\text{(v,c')}$, where

$\text{c'}=(c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10},c_{11},c_{12},c_{13},c_{14},c_{15}\oplus \text{x01},c_{16}\oplus \text{x03})$

C.

$\text{(v',c)}$, where

$\text{v'}=(v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10},v_{11},v_{12},v_{13},v_{14},v_{15}\oplus \text{x03},v_{16}\oplus \text{x03})$

D.

$\text{(v',c)}$, where

$\text{v'}=(v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10},v_{11},v_{12},v_{13},v_{14},v_{15}\oplus \text{x01},v_{16}\oplus \text{x03})$

E.

$\text{(v',c)}$, where

$\text{v'}=(v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10},v_{11},v_{12},v_{13},v_{14},v_{15},v_{16}\oplus \text{x02})$

Answer

E

This is a continuation of Q15. Suppose after the query was sent, the oracle replied with "Correctly padded", what was

$b_{14}$?

A. x00

B. x01

C. x02

D. x03

E. x04

Answer

D

Consider a single bock plaintext

$x$. Let the IV and it's ciphertext be

$$\text{v}=(v_1,v_2,v_3,\dots ,v_{16})$$

$$\text{c}=(c_1,c_2,c_3,\dots ,c_{16})$$

(S1): On query

$\text{(v,c)}$ the padding oracle returns "Correctly padded"

(S2): On query

$\text{(v',c)}$ the padding oracle returns "Wrongly padded", where

$\text{v'}=(v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10},v_{11},v_{12},v_{13},v_{14},\text{x07}\oplus v_{15},\text{x07}\oplus v_{16})$

We do not have other information on

$x$. From (S1) and (S2), we can eliminate some possibilities and derive the possible padding sizes of

$x$. Let

$S$ be the set of possible padding sizes. What is

$S$ ?

A. {1,2}

B. {5,6}

C. {3,4,5,6,7,8,9,10,11,12,13,14,15,16}

D. {1,2,3,4,7,8,9,10,11,12,13,14,15,16}

E. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

Answer

D

This question is same as the previous question, except that in step (S2), the padding oracle returns "Correctly padded". What is

$S$ ?

A. {1,2}

B. {5,6}

C. {1,2,5,6}

D. {1,2,3,4,7,8,9,10,11,12,13,14,15,16}

E. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

C

Q19 (Padding Oracle Attack)

An attacker has access to a padding oracle and is given

$\text{v}$ (the IV) and

$\text{c}$ (the ciphertext) of a plaintext.

$$\text{v}=(v_1,v_2,v_3,\dots ,v_{16})$$

$$\text{c}=(c_1,c_2,c_3,\dots ,c_{16})$$ No other information on the plaintext is given to the attacker. The attacker wants to determine the plaintext. Suppose on query

$\text{(v,c)}$, the padding oracle returns "Wrongly padded". Note that the oracle attack in our lecture note & tutorial only start from a given

$\text{(v,c)}$ that is correctly padded. Which of the statements is correct and most appropriate?

A. The attacker is unable to carry on because the original plaintext is not correctly padded. So it is not possible to employ the padding oracle to find the plaintext.

B. The attacker can find the plaintext. The attacker iterates on

$r$, starting from

$r=\text{x00}$, and queries the oracle with

$\text{(v',c)}$ where

$$\text{v'}=(v_1,\dots ,v_{16}\oplus r)$$

C. Same as the method in (B) except that the query sent is

$\text{(v,c')}$ where

$$\text{c'}=(c_1,\dots ,c_{16}\oplus r)$$

D. Same as the method in (B) except that the query sent is

$\text{(v',c')}$ where

$\text{v'}$,

$\text{c'}$ is respectively defined in (B) and (C).

E. The methods in (B), (C) and (D) are all correct.

Answer

B

Q20 (Decryption Oracle)

Bob made the following remark about padding oracle and decryption oracle.

"(1) With access to a padding oracle, the attacker can essentially decrypt any given ciphertext by adaptively querying the oracle."

"(2) Hence, having multiple adaptive access to a padding oracle is quivalent to having access to a decryption oralce."

What do you think?

A. Do not agree. An attacker with access to a padding oracle can get more information on the padding than from a decryption oracle.

C. Do not agree. An attacker with access to a decryption oracle will always obtain the plaintext. However, with padding oracle, there is a small probability that the attacker fails to decrypt it.

D. Do not agree. While the first statement is true, this does not imply the second statement.

E. Agree.

Answer

E

This is by elimination.

• (A, 3%). This is a wrong statement. Padding oracle is a special case of decryption oracle. Attacker cannot get strictly more info from padding oracle.
• (B, 24%) Note that padding oracle always succeed.
• (C, 23%) This is not true. Even if it is not padded correctly, we still can find the plaintext.
• (D, 27%) Q19 shows that it is always possible.

AY2021 S1 Final

Q2ii (Diffie-Hellman)

Suppose Alice and Bob perform a Diffie-Hellman Key Exchange with pre-agreed

$g=2$ and

$p$ is a prime number larger than

$2^{12}$. Alice, however, sends

$8$ to Bob; and Bob sends

$16$ to Alice. What is the key agreed by Alice and Bob?

a.

$8$

b.

$24$

c.

$128$

d.

$1024$

e.

$2^{12}$

Answer

e

Let

$k$ be the key,

$a$ and

$b$ be Alice and Bob's private value respectively.

Then,

Alice's public value = 8 =

$2^3$ =

$2^a\mathrm{mod}p$

Bob's public value = 16 =

$2^4$ =

$2^b\mathrm{mod}p$

$k=8^b\mathrm{mod}p={16}^a\mathrm{mod}p$

Note that

$p>2^{12}$. Take

$a=3$ and

$b=4$

Then,

$k=8^4={16}^3=4096=2^{12}$

Note:

$a=3$ and

$b=4$ is not the only possible values, but the smallest possible values.

AY2324 S2 Final

Q12 - Q14 (Hashing vs Encrypting a password)

A question was posted in the public forum Stack Overflow:

What is the difference between hashing a password (using SHA3 with salt) and encrypting it (using AES-CBC mode with random IV)? Which way is recommended for password file protection?

You want to post an answer. You want to support using hash. Which of the followings is a sensible and most precise reason.

a. Encryption has the disadvantage that the key must be securely stored. If the attacker happens to obtain both the password file and the key, all passwords will be revealed.

b. Encryption does not have salt, and hence vulnerable under rainbow table attack.

c. Encryption is vulnerable to Grover’s search and thus not quantum safe.

d. There are many side-channel attacks on encryption.

e. In term of security, both are equivalent since it is computationally infeasible to invert. Nonetheless, encryption/decryption is much slower than hash. Hence for efficiency consideration, use hash.

Answer

a

This is a continuation of the previous question. Instead of hash, you want to support using encryption. Which of the followings is a sensible and most precise reason?

a. Hash has the disadvantage that collision is inevitable. There is no guarantee that there is no collision among the passwords.

b. It is not possible to recover the original password using hash. On the other hand, with encryption, it is possible.

c. For weak passwords, it is still feasible for an attacker to recover the passwords from their digests, even if salted. However, without knowing the key, it is infeasible to recover the weak passwords from the ciphertext.

d. Hash is vulnerable to birthday attack, which essentially reduce the security strength by half.

e. In term of security, both are equivalent since it is computationally infeasible to invert. Nonetheless, hash is much slower than encryption/decryption. Hence for efficiency consideration, use encryption.

Answer

c

This is a continuation of the previous question. Instead of supporting either hash or encryption, you want to recommend doing both. Which of the followings is a sensible and most precise reason?

a. Following the principle of defense-in-depth, it is always not less secure to have additional layer of defense.

b. Following the principle of least privilege, it is advisable to employ a combination of multiple protections.

c. It is more secure to have the respective advantage in both previous 2 questions. For each password

$p$, one should store

$(c,s||d)$ where

$c=\text{Enc}(k,p)$ is the cyphertext (together with the IV),

$s$ is the salt,

$d$ is the salted hash, and

$k$ is the encryption key.

d. It is more secure to have the respective advantage in both previous 2 questions. For each password

$p$, one should store

$(s||c)$ where

$c=\text{Enc}(k,H(s||p))$, where

$k$ is the encryption key. In other words, encrypt the salted hash.

Answer

d

Q15 - Q16 (Birthday Attack)

An IoT device can receive remote instructions. The length of each instruction is 128 bits. Not all possible 128-bit strings are valid instructions. A total of

$2^{100}$ strings are valid instructions. After the device receives an instruction, it checks whether it is valid. If not, the device will drop the instruction. An attacker can send a total number of

$M$ instructions to the device. However, due to some technical constraint, the attacker can only send randomly chosen strings. Among the choices of

$M$ below, which is the smallest so that with high probability (more than 0.5), at least one of the strings is a valid instruction?

a.

$2^{30}$

b.

$2^{50}$

c.

$2^{64}$

d.

$2^{100}$

e.

$2^{128}$

Answer

a

This is the 2 pools variant. So use the formula

$1-{2.7}^{kM{2}^{-n}}$

$k=2^{100}$

$n=128$

So,

$1-{2.7}^{(2^{100})M{2}^{-128}}\ge 0.5$

$\cdots$

$M\ge 2^{27.4\dots }$

Smallest

$M=2^{30}$

Refer to Q15. A new version of the IoT device employs AES encryption. Each instruction is encrypted using AES CBC mode with randomly chosen IV. When the device receives the instruction, it decrypts and check whether the plaintext is a valid instruction. If not, the device will drop the instruction. Similarly, the attacker can send

$M$ random strings (each string consists of the IV and the ciphertext) to the device. Among the choices of

$M$ below, which is the smallest so that with high probability (more than 0.5), at least one of the plaintexts is a valid instruction?

a.

$2^{30}$

b.

$2^{50}$

c.

$2^{64}$

d.

$2^{100}$

e.

$2^{128}$

Answer

a

Similar to previous question.

Length of IV = Length of valid instruction = 128 bits

$k=2^{100}\times 2^{128}=2^{228}$

$n=128+128$

So,

$1-{2.7}^{(2^{228})M{2}^{-256}}\ge 0.5$

$\cdots$

$M\ge 2^{27.4\dots }$

Smallest

$M=2^{30}$

The use of AES CBC encryption mode does not change the probabilities involved.

Q27 (Secure Programming)

Consider the IP address example on "Data Representation" in Topic Secure Programming. Suppose the ip address 100.3.1.2 is blacklisted, among the following possible inputs, which would bypass the check and yet 100.3.1.2. would be connected?

The formula with problem: Suppose ip address is a.b.c.d, to combine them into a single 32 bits integer, we do

$(a\times 2^{24})+(b\times 2^{16})+(c\times 2^8)+d$.

a. 100.3.1.2

b. 2.1.3.100

c. 100.2.257.2

d. 100.31.2.0

e. 100.3.0.256

Answer

c. 100.2.257.2

The problem with the formula is that it didn't account for integer more that 255 (more than 8 bits).

So a,b,d are not answers.

For e, 256 =

$(100000000{)}_2$, right most 8 bits are all

$0$, the leading

$1$ bit will overflow to next position, so the ip generated is actually 100.3.1.0