Skip to main content

Exercises on cryptography

More exercises aviable at overthewire.org.

2021-2022 DEMO Exam exercise 2 (5 points)

You have intercepted two ciphertexts:

  • c1 = 1111100101111001110011000001011110000110
  • c2 = 1111101001100111110111010000100110001000

You know that both are OTP ciphertexts, encrypted with the same key.

  1. [2 points] You know that either c1 is an encryption of alpha and c2 is encryption of bravo or c1 is an encryption of delta and c2 is an encryption of gamma (all converted to binary from ascii in the standard way). Which of these two possibilities is correct, and why?
Solution

We can say that for sure c1 is the encryption of alpha and c2 of bravo because the last digits of the two ciphertext are different, they would have been the same with the encryptions of gamma and delta (since both end with an a).

  1. [1 point] What was the key k? Explain a procedure to obtain the key
Solution

We can find the key as alpha ⊕\oplus c1 = bravo ⊕\oplus c2 = 1001100000010101101111000111111111100111.

  1. [2 points] Suppose now that the encryption algorithm is modified as follows: Please, explain the weakness of the proposed approach.
Solution

We recall that for every m∈{0,1}λm \in \lbrace 0, 1 \rbrace^\lambda the function EAVESDROP(m) is the uniform distribution on {0,1}λ\lbrace 0, 1 \rbrace^\lambda. Hence, for all m,m′∈{0,1}λm, m' \in \lbrace 0, 1 \rbrace^\lambda the distributions EAVESDROP(m) and EAVESDROP(m') are identical.

EAVESDROP'(m) returns also the key kk which can be used to decrypt the ciphertext in less than polynomial time.

Question 1

You are having a discussion with a friend about cryptography.

Your friend makes a series of statements. Please tell us how you would respond (True or False) and motivate your answer.

  1. The reason why the 2048bit RSA is more robust to brute forcing that a 256bit AES, is because the key is longer.
Solution

False. The size of the key cannot be used as a direct comparison criterion because RSA is asymmetric, whereas AES is symmetric.

  1. No encryption algorithm is perfect, as they are all vulnerable to brute forcing.
Solution

False. The one-time pad is invulnerable because each ciphertext decrypts to every possible plaintext.

  1. An encryption algorithm is broken when there is at least one way to derive the key from a given amount of ciphertext.
Solution

False. Generally, a cryptosystem is broken if there is any attack faster than brute force to obtain either the key or the plaintext.

Question 2

Show that the following libraries are not interchangeable. Describe an explicit distinguishing calling program, and compute its output probabilities when linked to both libraries:

Solution

The two libraries are not interchangeable because they return the key k that we can use to decrypt the ciphertext and find which message was decrypted.

Question 3

Let G1G_1 and G2G_2 be deterministic functions, each accepting inputs of length λ\lambda and producing outputs of length 3λ3\lambda.

Hints

  1. Define the function H(s1,s2)=G1(s1)⊕G2(s2)H(s_1, s_2) = G_1(s_1) \oplus G_2(s_2). Prove that if either of G1G_1 or G2G_2 (or both) is a secure PRG, then so is HH.
Solution

This is the definition of a one time pad perfect cipher. If we take a look at the definition of the VERNAM cipher we extract the key randomply (either G1G_1 or G2G_2 is PRG) and then we xor it with the message (either G1G_1 or G2G_2, the one which is not the PRG) to obtain a ciphertext, which will be a PRG.

  1. What can you say about the simpler construction H(s)=G1(s)⊕G2(s)H(s) = G_1(s) \oplus G_2(s), when one of G1G_1, G2G_2 is a secure PRG?

Question 4

Let HH be a collision-resistant hash function with output length nn. Let H∗H^* denote iterating HH in a manner similar to CBC-MAC: Show that H∗H^* is not collision-resistant. Describe a sucessful attack.

Solution

Lets imagine a string splitted only in x1x_1 and x2x_2. The xor of the chain is between a controllable variable x2x_2 and the output of the hash function on x1x_1: H∗(x1,x2)=H(x2⊕H(x1))H^*(x_1,x_2) = H(x_2 \oplus H(x_1)).

To find a collision H(x1)=H(x2)H(x_1)=H(x_2) we need to find x2x_2 s.t. x2⊕H(x1)=x1x_2 \oplus H(x_1) = x_1, then x2=x1⊕H(x1)x_2 = x_1 \oplus H(x_1).

This is feasible because x1x_1 is controllable and we can first calculate H∗(x1)=H(x1)H^*(x_1)=H(x_1) then x2=x1⊕H(x1)x_2 = x_1 \oplus H(x_1) is a collision because H∗(x1)=H∗(x2)H^*(x_1)=H^*(x_2).

For example if x1=aaaax_1=aaaa and H(x1)=ccccH(x_1)=cccc, to find a collision we must find x2x_2 s.t. x2⊕cccc=aaaax_2 \oplus cccc = aaaa which means that x2=cccc⊕aaaax_2 = cccc \oplus aaaa.

We can iterate this procedure for a sting of arbitrary length.

Question 5

Consider the following MAC scheme, where FF is a secure PRF with in=out=λin = out = \lambda:

Show that the scheme is not a secure MAC.

My solution

We can see that m∗=m1⊕m2⊕...⊕mlm^* = m_1 \oplus m_2 \oplus ... \oplus m_l because it is initialized to all zeros and then xored to all mim_i.

We can show that two different input can have the same MAC, for example MAC(k,00000000)MAC(k, 0000 0000) and MAC(k,11111111)MAC(k, 1111 1111) both will have the same MAC F(k,0000)F(k, 0000).

This is mecause for 000000000000 0000, m∗=0000⊕0000⊕0000m^* = 0000 \oplus 0000 \oplus 0000 and for 111111111111 1111, m∗=0000⊕1111⊕1111m^* = 0000 \oplus 1111 \oplus 1111.

No Comments
Back to top