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?
  2. [1 point] What was the key k? Explain a procedure to obtain the key
  3. [2 points] Suppose now that the encryption algorithm is modified as follows:

Please, explain the weakness of the proposed approach.

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:

Question 3

Let $G_1$ and $G_2$ be deterministic functions, each accepting inputs of length $\lamda$ and producing outputs of length $3\lambda$.

  1. Define the function $H(s_1 | s_2) = G_1(s_1) \oplus G_2(s_2)$. Prove that if either of $G_1$ or $G_2$ (or both) is a secure PRG, then so is $H$.
  2. What can you say about the simpler construction $H(s) = G_1(s) \oplus G_2(s)$, when one of $G_1$, $G_2$ is a secure PRG?
Hints

Question 4

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

Question 5

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

Show that the scheme is not a secure MAC. Descrive a distinguisher and compute its advantage.

Back to top