Week 2
You can’t query the same IV more than once. Else you can distinguish immediately from the PRG and the truly random.
RC4
Beautiful and simple.
Byte oriented stream cipher.
A5/1
Stream cipher was used in mobile phones.
First mass market deployment of cryptography.
Very friendly for hardware because it has LFSR (Linear Feedback shift register).
Was widely deplyed, now broken.
Modern Stream ciphers
AES and 3DES in counter mode.
ChaCha (not as fast as AES but more secure against side-channel attacks)
Keystream reuse is a big security issue in stream ciphers. Since you could recover something by checking for “the”.
Block ciphers
Encrypts blocks of bits.
Typically blocksize: 64 bits (DES) or 128 bits (AES)
Typical Key size = same as block size.
Keysize is the primary security factor.
Block size is the secondary indicator of security level.
Cache timing attacks not possible if AES is implemented in the HW.
If you need a block cipher, use AES.
Security for block ciphers
All attacks try to recover the key here:
-
Known plaintext attack: He gets many plaintexts and ciphertext pairs.
Example: IPsec protocol. He know how the header looks like which gets encrypted. -
Chosen Plaintext attack: He can choose many plaintexts that will get encrypted under a Key
Javascript in the browser attack: get the victim to visit your website first while he is visiting another. Inject some javascript in it which allows you to make requests to the server the client is visiting, then you can choose what gets sent and you see the sent encrypted packets. -
Chosen ciphertext attack: He gets to choose many ciphertexts and gets the corresponding plaintexts P under the key k.
Ipsec protocol again.
For all 3 attack scenarios, a few plaintext/ciphertext pairs enable an exhaustive key search.
(If the keylength is not too large)
Design target block cipher: No attack is faster than the exhaustive key search (else we throw that block cipher away).
Exercise 2
Problem 1: Key Stream Generator
a.) Why is the attacker not allowed to repeat IVs in its queries?
Adversaries that can repeat IVs can trivially distinguish real from random.
The purpose of the IV is that the same plaintext will not be encoded into the same ciphertext. (It is similar to the state of a PRG, where for the same seed and state the same text gets encoded to the same ciphertext.)
If the same IV is sent in 2 queries then the KSG will output the same stream of data but the truly random box will still output pure random stream. So the Distinguisher could send all queries with the same IV and when a stream is identical to one that came before, then it knows that it is the KSG.
Same IV –> Same Keystream
b.)
l is the seed space.
It seems that the G’ generator can be reduced to the G generator, since even though the seedspace is bigger (l+m), it only uses the first l bits as the seed which is the same as G. Since G is secure G’ is also secure.
c.)
Is a KSG not the same as a PRG with nonces/seed-state?
KSG | PRG
–|–
Key | Seed
IV | Nonce/seed-state (optinal)
efficient, deterministic algorithm | efficient, deterministic algorithm
Input: key K and an initialisation vector IV | a short “seed”
outputs an (infinite) stream of bits KS = KS 0 ,KS 1 ,… called the keystream | outputs a pseudo-random string (usually longer than input, added length = stretch)
A PRG is secure if the Adversary can’t distinguish between truly random and pseudo random.
A KSG is secure if the Adversary can’t distinguish, even if the provides the IV. But since in the definition H(K,IV) := G(K||IV) the IV is part of the seed in the PRG, which the adversary knows.
So if we have a PRG where the key is empty, only the IV is the seed, that is still a secure PRG, but it would fail the KSG test since the adversary could use the IV as a key for a PRG itself and predict the outcomes.