Dominik Farhan

Symmetric Ciphers

E and D are parameterized with a key K.

In symmetric cipher Alice and Bob share the same key (the encryption and decryption keys are the same).

Kerckhoffs's principle = “one ought to design systems under the assumption that the enemy will immediately gain full familiarity with them” —basically everything can and should be public except the key.

Some well known symmetric ciphers:

DES
AES/Rijndael
fast and nice mathematical structure
Blowfish
Twofish
- improved Blowfish
- larger key size than Blowfish
Serpent
- conservative
Caesar’s cipher

Asymmetric ciphers

Encryption and decryption keys are different.

Typical use cases:

multiple people communicating
- everyone can share encryption keys
- each person has her own private decryption key

signing
- encryption key is private
- but everyone can decrypt and verify signature

Some well-known asymmetric ciphers:

RSA
DSA
Elliptic curve cryptography
ElGamal

Hash functions

We want:

impossibility of collision
non-invertible
some kind of randomness, unpredictability

Use-cases

smaller signatures
MAC
- Message Authentication Code
- Used for Symmetric signatures
- something like $h(k|m)$ is appended to the message. because of Merkle-Damgård this particular construction is not safe with many hash functions (possible to append to the message)
HMAC two hashes involved $h(k_2|h(k_1|m))$

Generating randomness

We want something unpredictable and uninfluenceable.

hybrid ciphers, challenge-response authentication.

Attacks

known ciphertext
- most common attack
- most ciphers are well equipped against it
- attack on Two-Time pad
- frequency analysis
known plaintext
- attacker knows plaintext ciphertext pairs and the goal is to recover the key
chosen plaintext
- The attacker can choose plaintext to be encrypted
- Used in WWII before the battle of Midway
- Also used in Enigma (gardening)
chosen-ciphertext
- the attacker can force the victim to decrypt any text and send it to him
distinguishing attacks
- attack to distinguish encrypted data from a random permutation

Birthday attacks

How many tries are needed before something repeats?

P[\text{random function from [m] to [n] is injection}] = \frac{\# \text{injection}}{\# \text{all}}

= 1\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right) \cdot...\cdot \left(1-\frac{m-1}{n}\right) \approx 1 \cdot e^{-1/n}\cdot e^{-2/n}\cdot...\cdot\cdot e^{(m-1)/n} = e^{\frac{m(m-1)}{2n}}

P[\text{random function from [m] to [n] is injection}] = \frac{1}{2} \implies m \approx \sqrt{n}

often one can precompute and listen at once thus making the

m

even smaller.

Vernam cipher a.k.a One-Time Pad

Xors key and the plaintext.

Another similar structure is $E(x, k) = x+k, D(y,k) = y-k$ done in $\mathbb{Z}_2$ .

Perfectly secure. Key must not be repeated ever.

An attacker can easily change messages.

Perfect security

The probability that ciphertext decrypts to a given plaintext is the same for all plaintexts.

When the number of keys is smaller than the number of messages it must hold that for some 2 messages.

P[D(y, k) = x] > 0 ,

P[D(y, k) = x'] = 0

Thus, such cipher is not secure.