Thursday, December 7, 2017

Cryptography course - AES

AES is a subs-perm network not Feistel (in which half the bits remain unchanged in every round). Here all bits change in every round.
Intel Westmere and AMD Bulldozer architectures have special instructions for AES.
AES implementation will have shortest code when tables are not pre computed and vice versa.
So, to transmit AES implementation to browser, just the code is sent and browser pre computes the table.
On AES-128 best known attacks are only 4 times faster than exhaustive search - i.e. 2^126. AES-256 though can be broken in 2^99.

Can we build a PRF from a PRG? Though the ultimate goal is to build PRP.
Answer is yes. It's called GGM PRF.
If we have a PRF, we can plug it in Luby-Rackoff theorem which says that PRF + 3 round Fiestel will give us PRP.
But constructing a PRP like this is very slow in practice, so it's not used.

Any secure PRP is a secure PRF if |X| is sufficiently large. For e.g. |X| for AES is 2^128. 

How to correctly encrypt long messages with block ciphers?
If two parts of the message are same, and the block cipher is not long enough to encrypt the full message, attacker can gain information about the underlying text.
One way to solve it is to use - Deterministic Counter mode.

Sol 1
Randomized Encryption
Given the same PT, output different CT every time due to randomization. But the size of CT increases since the randomness is encoded in the message.

Sol 2
Nonce based Encryption
Message is encrypted using (k, n) and this pair never repeats. n could be public too. For e.g. for HTTP(s) packet counter can be used as n since packets arrive in order.

Cipher block chaining - with random IV
but if IV is predictable, CPA challenge will fail. In SSL/TLS this was a bug.

CBC -with nonce
Another key to encrypt nonce since nonce has to be random.

Randomized counter mode (CTR)
Parallelizable - Unlike CBC

Advantages of CTR over CBC
Requires PRF rather than PRP
Better error bounds
No Padding required

But all these encryptions don't really protect against message tampering. 

Wednesday, November 29, 2017

Cryptography course notes - Block Ciphers

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. 

Sunday, November 19, 2017

Cryptography course notes

Stream Ciphers 4 - What is a secure cipher?

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.

    $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 - 

Wednesday, November 15, 2017

Coursera cryptography notes

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

Tuesday, November 14, 2017

Coursera cryptography notes

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

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

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


Blog Archive