Cryptography Questions

Pseudo-random generators, pseudo-random functions and pseudo-random permutations are computationally indistinguishable, respectively, from

Which of these assumptions is sufficient to construct a pseudo-random generator, a pseudo-random function and a pseudo-random permutation?

Assume |s1|=|s2|=n and consider the functions defined, for any s1 and s2, as:

(a) G1(s1,s2)=s1 xor s2,  (b) G2(s1,s2)=(s1, s2, s1 xor s2).

We have that:

Let us denote as "X ci Y" the fact that random variables X and Y are computationally indistinguishable.

For any random variables X,Y,Z, consider the statements:

(a) if X ci Y then Y ci X,

(b) if X ci Y and Y ci X then X = Y,

(c) if X ci Y and Y ci Z then X ci Z,

(d) if X = Y then X ci Y,

(e) if X ci Y then X = Y.

Which of them are true?

An oracle adversary is an adversary that makes queries to an oracle and obtains answers, before making a determination about the oracle. To prove that a permutation P is not a pseudo-random permutation, it suffices to show an efficient oracle adversary that can distinguish, with not negligible probability, the case in which its oracle is P from the case in which its oracle is a random permutation RP with the same input and output domains as P. To obtain an algorithm that makes this distinction, it suffices to find one or more distinguishing conditions among the adversary's query inputs and query outputs such that: (a) if the oracle is P, then the condition holds with high (e.g., 1) probability; (b) if the oracle is RP, then the condition holds with low (e.g., negligible) probability. Define the "extended FT transform" as the permutation that maps (L,M,R) to (R,f_k(R) xor M,f_k(M) xor L), where k is a random key, f is a pseudo-random function, and L,M,R are n-bit strings, for some large integer n. Which of the following conditions are distinguishing conditions for the 1-round iteration and 2-round iteration of the extended FT transform, respectively? Notation: (L',M',R') and (L'',M'',R'') denote the 1-round and 2-round outputs, respectively, of the extended FT transform on input (L,M,R); when we run the transform on different inputs, we use the notations (L0,M0,R0), (L1,M1,R1), .... for the inputs, (L0',M0',R0'), (L1',M1',R1'), .... for the 1-round outputs and (L0'',M0'',R0''), (L1'',M1'',R1''), .... for the 2-round outputs.

Rationale:

For modern symmetric encryption schemes, which among these are the differences between these two notions: indistinguishability in the presence of eavesdropping and the indistinguishability in the presence of chosen message attacks?

Which among these are the differences between the indistinguishability notion with chosen message attack and the indistinguishability notion with adaptive chosen message attack?

Let G:{0,1} n-->{0,1} 2n be a pseudo-random generator and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a message bit b, returns c = G(k) xor 1 2n if b=1 or c = G(k) if b=0 and D is naturally defined so to satisfy the decryption correctness property. Which of the following security notions is satisfied by (KG,E,D)?

Let P:{0,1}^n-->{0,1}^{n} be a pseudo-random permutation and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and an n-bit string m, returns c =P(k,m) and D is naturally defined so to satisfy the decryption correctness property.

Which of the following security notions is satisfied by (KG,E,D)?

Let F:{0,1}^n-->{0,1}^{n} be a pseudo-random function and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a string m, returns c =F(k,0) xor m and D is naturally defined so to satisfy the decryption correctness property. Which of the following security notions is satisfied by (KG,E,D)?

Rationale:

We want to design a new block cipher based on substitution/permutation networks. Which of the following sets of principles should we apply?

Which one among the following block cipher modes of operation, on an input of the type (x,y,x), returns an output of the type (z,w,z)? Here, x,y,z,w denote distinct and equal-length message blocks.

Which block cipher mode of operation does not associate two outputs of the type (y,x) and (z,x) to two inputs of the type (b,a) and (c,a), respectively? (If the mode requires an IV or a counter, use the same IV or counter for the two input pairs.)

Consider function tinyDES defined by applying the following modifications to DES (abstracted here, for simplicity, as a 16-round Feistel network): (a) 8-bit message inputs instead of 64-bit message inputs (b) 8-bit secret key k(3,1),k(3,0),k(2,1),k(2,0),k(1,1),k(1,0),k(0,1),k(0,0) inputs instead of 56-bit secret key inputs (c) for n=1,..,15, the n-th round key is computed as 4 bits k'(3),..,k'(0) selected from the 8-bit secret key, as follows: write n in binary as (n(3),n(2),n(1),n(0)), and define k'(j)=k(j,n(j)); (d) for n=1,..,15, the n-th round application of function F returns the bitwise xor between the current R input and the n-th round key k'. Assume the initial left input L is 0111, the initial right input R is 0011, and the 8-bit key is 01101011. Which of the following is the output of tinyDES?

When choosing a previously designed 128-bit block cipher for some real-life application, we want to ensure that this cipher is somewhat resistant to known attacks, including ciphertext-only, known-plaintext, known-ciphertext, chosen-ciphertext, differential and linear attacks. Which of the following is a realistic goal for such a cipher?

Rationale:

Consider function tinyMD5 defined by applying the following modifications to MD5: (a) 12 operations instead of 64 (b) each operation maps a 4-bit state (A,B,C,D) into a 4-bit state (A,B,C,D) (c) operations 1,5,9 (resp., 2,6,10) (resp., 3,7,11) (resp., 4,8,12) use function F (resp., G) (resp., H) (resp., I) (d) addition mod 32 is replaced by logical XOR (e) the left bit rotation by s bits is replaced by logical NOT (f) M(i) and K(i) are bits. Assume the initial state is 1100, the message M(1),...,M(12) is 100110111010 and the constant K(1),..,K(12) is 010010111011. Which of the following is the output of tinyMD5?

Q5 Assume students randomly choose their answers to a homework similar to this one, with only 12 questions, of 4 possible answers each. Using the appropriate result in [KL, appendix A], which among these numbers is the smallest number of students so that with probability at least 0.5 at least two students give the same answers to all 12 questions?

Let F be a pseudo-random function, and consider the following proposed constructions 

for a Tag algorithm in a MAC: 

(1) Tag(k,(m1,m2)) = (F(k;m1),F(k;m2)); and (2) Tag(k,(m1,m2)) = F(k;m1) xor F(k;m2).

Note that both constructions are forgeable under a chosen message attack (i.e., for construction 1, an attack making a query (m1,m2), can use the obtained output to forge a tag for a query (m1,m1); for construction 1, an attack making a query (m1,m2), can use the obtained output to forge a tag for a query (m2,m1)). Now, consider the following proposed constructions 

for a Tag algorithm in a MAC:

(3) Tag(k,(m1,m2)) = F(k;m2 xor F(k;m1)); (4) Tag(k,(m1,m2)) = (F(k;m1),F(k;m2 xor F(k;m1))); (5) Tag(k,(m1,m2)) =  F(k;r) xor F(k;m1) xor F(k;m2), for a random r.

Which of these constructions are unforgeable under a chosen message attack?

Consider the following symmetric encryption scheme (KG,E,D), which uses a block cipher F, and a message authentication scheme (Gen, Tg,Vrfy) with unique tags. The key generation algorithm KG returns randomly chosen keys k1, k2. On input keys k1,k2 (returned by KG) and a large message m, the encryption algorithm E  computes x=(Enc-Mode-F(k,m)) and returns ciphertext c=(x,Tg(k2;x)), where Enc-Mode-F(k,m) is an encryption of message m, using F as a block cipher and the encryption algorithm of a block cipher mode of operation, denoted as Enc-Mode. On input keys k1,k2 (returned by KG) and ciphertext c, the decryption algorithm D writes c as (c1,c2), verifies whether Vrf(k2;(c1,c2))=1; if yes, it returns the decryption m' of x computed using F as a block cipher and the decryption algorithm of a block cipher mode of operation, denoted as Dec-Mode; if not, it returns an error message. For which of the following block cipher modes of operation, does this construction satisfy security in the sense of indistinguishability in the presence of a chosen ciphertext attack?

Consider the following symmetric encryption scheme (KG,E,D), which uses a pseudo-random function F, and a message authentication scheme (Gen, Tg,Vrfy) with unique tags. The key generation algorithm KG returns randomly chosen keys k1, k2. On input keys k1,k2 (returned by KG) and message m, the encryption algorithm E randomly chooses r, computes x=(r,F(k1;r) xor m) and returns ciphertext c=(x,Tg(k2;x)). On input keys k1,k2 (returned by KG) and ciphertext c, the decryption algorithm D writes c as (c1,c2), verifies whether Vrf(k2;(c1,c2))=1; if yes, it writes x as (x1,x2) and returns message m'=F(k1;x1) xor x2, otherwise it returns an error message. Which is the strongest security notion satisfied by the scheme (KG,E,D)?

Rationale: