Cryptanalysis and brute-force attacks

Question 1

What are the typical objectives of attacking an encryption system?

Answer 1

1. is not simply to recover the plaintext of a single ciphertext
2. but to recover the key in use (so that all future and past messages encrypted with that key are compromised).

Question 2

What is cryptanalysis?

Answer 2

1. Attacks rely on nature of the algorithm plus perhaps some knowledge of general characteristics of the plaintext or even some sample plaintext-ciphertext pairs.
2. Exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used.

Question 3

What is brute-force attack?

Answer 3

1. Attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained - assumes that plaintext is known ore recognisable.
2. On average, half of all possible keys must be tried to achieve success.
3. Its cost (heavily) depends on key size and on average, half of all possible keys must be tried to achieve success (greater key size -> more time to try out keys)

Question 4

What are cryptanalytic attacks? What are some of the assumptions?

Answer 4

1. ALWAYS ASSUME THAT THE ATTACKER KNOWS WHAT ALGORITHMS ARE BEING USED.
2. Algorithms should be published so that their security can be evaluated.
3. Contrasts with security by obscurity - extremely dangerous.

Question 5

What is the model of attack? (the attacker adversary game model)

Answer 5

1. Input: what the attacker knows from the start (input das). This could be the public key, the distribution of plaintext…
2. Oracle: provides additional information to the attacker during the attack - more info that characterises the different types of attacks.
3. Output: what the attacker is trying to obtain/ achieve, for example, the secret key/ private key, partial info about plaintext. If the attacker obtains what he wants - he wins the game

Question 6

What are the different types of attacks?

Answer 6

1. Ciphertext only
2. Known plaintext
3. Chosen plaintext
4. Chosen ciphertext
5. Chosen text

Question 7

What is the ciphertext only attack?

Answer 7

1. attacker knows: ciphertext C and the encryption algorithm E
2. Given C1,….,Cn where C1 = Ek(M1)…. Cn = Ek(Mn)
3. Deduce the messages M1,….,Mn or the algorithm/key to compute Mn+1 from Cn+1 (Decryption key) where Cn+1 = Ek(Mn+1)

Question 8

What is the known plaintext attack?

Answer 8

1. attacker knows: ciphertext, encryption algorithm and one or more plaintext-ciphertext pairs formed with the secret key.
2. Given: M1, C1 = Ek(M1),…..,Mn, Cn = Ek(Mn)
3. Deduce the inverse key/ decryption key or algorithm to compute Mn+1 from Cn+1 = Ek(Mn+1)

Question 9

What is the chosen plaintext attack?

Answer 9

1. attacker knows: ciphertext, encryption algorithm and they can choose M1,…Mn
2. The attackers tests out messages Mi from M1,…Mn and observes the ciphertext C in order to deduce the key (goal)

Question 10

What is the adaptive chosen plaintext attack?

Answer 10

1. attacker not only chooses the plaintext but can also modify it based on the encryption results.

Question 11

What is the chosen ciphertext attack?

Answer 11

1. attacker knows: ciphertext, encryption algorithm, ciphertexts can be chosen by the attacker and these can be decrypted to get access to the decrypted plaintext.
2. tries to recover key with this info

Question 12

What is the chosen text attack?

Answer 12

1. attacker knows: Encryption algorithm, ciphertext, plaintext message chosen, together with its corresponding ciphertext generated with the secret key and ciphertext chosen, together with its corresponding decrypted plaintext generated with the secret key.

Question 13

How to build a definition for security? (going back to the adversary game)

Answer 13

1. Specify an oracle (a type of attack) and the input data (what the attacker knows from the start)
2. Define what the adversary needs to do to win the game, i.e., a condition on his output.
3. The system is secure under the definition, if any efficient adversary (realistic computing power) wins the game with only negligible probability (very low).

Question 14

What is unconditional security?

Answer 14

1. System (algorithm) is secure even if attacker has unbounded computing power since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext.
2. security is measured using information theory.
3. ONE TIME PAD IS THE ONLY ENCRYPTION ALGO THAT IS UNCONDITIONALLY SECURE.

Question 15

What is the criteria for unconditional security?

Answer 15

1. Cost of breaking cipher exceeds value of encrypted information.
2. Time required to break cipher exceeds useful lifetime of information.

Algorithm is COMPUTATIONALLY SECURE if either of these two criteria are met.

Question 16

What is conditional security?

Answer 16

1. System can be broken in principle, but this requires more computing power than a realistic attacker would have.
2. Security measured using complexity theory.