Cryptography course notes - Block Ciphers

https://www.coursera.org/learn/crypto

PRP/PRF - Psuedo Random Permutations/Functions and Block Ciphers are the terms which can be used independently.

They map a block of size n to output block of size n. For 3DES, n = 64 bits and k(key size) = 168 bits. For AES, n = 128 bits, k = 128, 192, 256

Key is expanded in round keys which are in turn applied to input. It's parallel in nature.

Key expansion. Round function.

Basic building block - Feistel netwrok - take functions which map n bits to n bits and construct invertible functions which map 2n bits to 2n bits.

DES is 16 round Feistel network. Function is same in all rounds, just that key is different.

Luby Rackoff theorem - 3 round Feistel network gives a secure PRF. Argue that 2 round is not secure.

Breaking DES with exhaustive search

Given 1 m,c pair there is 99.5% probability that a certain key was used.

With 2 pairs, prob. is even higher.

56-bit DES has been broken in 3 months, 3 days, 22 hours. In 7 days with 120 off-the-shelf FPGAs.

With double-DES, it can be broken in 2^63 time (vs 2^56 for single-DES) due to man in the middle attack. For triple-DES it's 2^118. 

DES-X can be used to make DES more secure by doing k1 XOR (E (k2, m XOR k3))

Attacks on the implementation

Side channel attacks
For e.g. if a smart card has a key which is used for encryption/decryption - by observing power consumption you can guess 1) number of cycles (peaks/troughs count) 2) by zooming in on the graph even 0s and 1s can be guessed of the key. 3) Smart card companies try to mask the power but by differential power analysis it can still be broken.

Also, if one core is used for enc/dec, on another core the attack can run which can monitor cache misses since both the cores share the cache.

Fault attacks

Computing errors in the last round expose the secret key k

Linear and Differential attacks
Given many inp/oup pairs, can we recover key in time less than 2^56 (Exhaustive search).

Linear cryptoanalysis -

If you XOR subset of message bits with subset of CT resulting value should be equal to subset of original key with prob = 1/2

But if it's 1/2 + epsilon then there is some bias.

In case of DES epsilon is non-trivial which breaks DES in 2 POW 42. Turns out the 5th S-box (S5) has some linearity which results in 2 POW 42 attack.

Quantum attacks:

Generic search problem:

Given f:X->{0,1}
Goal : find x e X s.t. f(x) = 1

Classical computer will take O(|X|) time. Quantum computing can help us to solve this problem faster, in O(|X| pow 1/2). A quantum computer can break DES in 2 POW 28 as opposed to 2 POW 56. And AES in 2 POW 64. These days 2 pow 64 is considered insecure. 

Cryptography course notes

https://www.coursera.org/learn/crypto

Stream Ciphers 4 - What is a secure cipher?

PRG Security Definitions - 

Statistical tests - given an input it will tell how random it is.

Advantage - |Pr(A(PRG) = 1) - Pr(A(R) = 1)| A is statistical test which will return 1 if it thinks input is random enough. Advantage is close to 1 if A can distinguish very well between a truly random number and PRG random number else it's close to 0.

A PRG is secure if ADV_PRG[A,G] is negligible. It means it's difficult to distinguish between PRG and truly random.

Are there provably secure PRGs? We don't know. It's linked to P = NP.

Secure PRGs are unpredictable. Given first i bits if an algo can predict the i+1 bit with prob > 1/2 + epsilon where epsilon is non-neg then PRGs is predictable and Advantage > epsilon.

Theorem => if for all i in (0 to n-1) PRG G is unpredictable at position i then G is secure PRG.

If next bit predictors can't distinguish G from random then no statistical test can.

Semantic Security - if attacker can't distinguish between Exp(0) and Exp(1) - i.e. m0 and m1. Definition similar to advantage.

Quiz

<?php 

    $cipherText = '6c73d5240a948c86981bc294814d';

    $originalText = 'attack at dawn';

    $newText = 'attack at dusk';

    $otpInAscii = pack('H*',$cipherText) ^ $originalText;

    $newCipherText = bin2hex($otpInAscii ^ $newText);

    echo $newCipherText;

?>

Stream cipher with scure PRG is semantically secure - 

Coursera cryptography notes

https://www.coursera.org/learn/crypto

W1S5
1. Problems with RC4 (used in HTTPS/WEP), some bytes have higher prob
of being 0.
2. CSS(Content scrambling system) used for DVDs, Bluetooth, GSM -
implemented in hardware is badly broken. It uses LFSR. US allowed
export of crypto algorithms which weren't more than 40 bits. Hence DVD
manufacturers were constrained.

3. Modern stream ciphers - eStream - Salsa20(elegant) Sosemanuk

Coursera cryptography notes

https://www.coursera.org/learn/crypto

W1S4
1. If you use same pad to encrypt multiple messages m1,m2 - an
attacker can XOR resulting CTs C1,C2 = m1 XOR m2 from which one can
recover easily the original messages since there is plenty of
redundancy in English esp ASCII.

2. Real world failures of the 2 time pad - Project Venona (US vs
Russia - 1941-46). MS-PPTP (Windows NT) wherein both server and client
used the same key to encrypt messages. Also 802.11b WEP - IV || k is
used to encrypt a frame. Length of IV is 24 bits. So after 16M frames,
encrypting key gets recycled. So 2 diff msgs encrypted with same key.
Also if you reset router, IV gets reset to 0 - so it will get recycled
faster than normal. Also IV goes like this - 0,1,2,3 so all the keys
are closely related. The PRG used by WEP is RC4 which was demonstrated
to fail after 10^6 frames.

3. Disk encryption fail -
4. OTP is malleable. If attacker has access to CT, he can XOR it with
some pattern to modify the resulting message.

Coursera cryptography notes

https://www.coursera.org/learn/crypto

W1S1-2

1. Anything which can be done with a Trusted authority can be done without it through some secret protocol communication among all the parties.
2. If there are 2 Random variables with uniform distribution, their XOR is also a uniform distribution.
3. Birthday paradox - 1.2 * sqrt(size(U)) samples would yield 2 distinct elements with same values where size(U) is the size of the entire set. 1.2*sqrt(365) = 24 people in a room would yield 2 people with same birthday. 2^64 samples of 128 bit numbers would yield 2 same numbers. Probability of this happening is >= 0.5

W1S3

1. Definition of perfect secrecy (E,D) over (K,M,C), Pr [ E(k,m0) = c] = Pr[E(k,m1) = c] given that |m0| = |m1|. In other words, CT only attacks are not possible. So One Time Pad (OTP) as perfect secrecy. OTP is simply m XOR k = c.

2. Perfect secrecy also requires that len(k) >= len(m) . OTP satisifies this with equality. So OTP is not practical since if you can transmit the key securely, you can as well transmit the message securely as well(they are the same length).

How to make OTP more secure with stream ciphers?

1. PRG but PRG must be unpredictable. Predictable means that given first few bits of PRG output I can deduce the rest of the bits. If that's so, if the attacker knows first few bits of m and sees the CT, by XORing can get first few bits of PRG output. From those first few bits, can generate rest of the bits.

2. Weak PRGs - A. glibc random() B. LCG 

3. Negligible/non negligible epsilon corresponds to polynomial/exponential