Cryptography Summary

Cryptography
Attacks
• Types of attacks:
• brute force attack: tyring all possible decryption keys
• ciphertext only attack: given 𝑦1 = 𝑒𝑘 (𝑥1 ), … , 𝑦𝑖 = 𝑒𝑘 (𝑥𝑖 ), deduve 𝑘, an alorgithm that
outputs 𝑥𝑖+1 given 𝑦𝑖+1 = 𝑒𝑘 (𝑥𝑖+1 ), OR 𝑥1 , … , 𝑥𝑖
• known plaintext attack
• chosen plaintext attack
• adaptive chosen plaintext attack
• chosen ciphertext attack
• non cryptographic attacks: bribery, physical theft, blackmail, threats, torture etc
• Attacks on SPNs: differential cryptanalysis, linear cryptanalysis
• cost of attacks




• meet in the middle attack
• AES: secure against all known attacks
• naive attack
• birthday attack
• MAC: known-text attack, chosen-text attack, adaptive chosen-text attack
• CBC-MAC: best attack is the birthday attack
• possible attack goals: total break, partial break, distinguishability of ciphertexts
• Hastad’s broadcast attack
• Coppersmith’s short pad
• man in the middle attack
• known message existential forgery

Birthday Attack
• based on the birthday paradox
2
• cost: find a collision by brute force in around 2𝑛 operations
• is the best-known attack on CBC-MAC

Block Ciphers
• iterated block cipher: a key schedule of 𝑁𝑟 round keys (𝑘1 , 𝑘 2 , … , 𝑘 𝑁𝑟 ) and a round
function 𝑓 which takes a round key and a current state
• known attacks: differential cryptanalysis, linear cryptanalysis

Chinese Remainder Theorem
• 𝑚1 , 𝑚2 , … , 𝑚𝑟 pairwise relatively prime, 𝑎1 , 𝑎2 , … , 𝑎𝑟 , the system of 𝑟 congruences
𝑥 ≡ 𝑎𝑖 (𝑚𝑜𝑑 𝑚𝑖 ) has a unique solution modulo 𝑀 = 𝑚1 𝑚2 … 𝑚𝑟 :

, 𝑟

𝑥 ≡ ∑ 𝑎𝑖 𝑀𝑖 𝑦𝑖 (𝑚𝑜𝑑 𝑀)
𝑖=1
𝑀
where 𝑀𝑖 = 𝑚 , 𝑦𝑖 ≡ 𝑀𝑖−1 (𝑚𝑜𝑑 𝑚𝑖 )
𝑖
• used to speed up modular exponentiation 𝑥 𝑦 (𝑚𝑜𝑑 𝑛) if n is composite

DES
• Data Encryption Standard
• timeline: section 12, early 1970s - 1977
• protected against differential cryptanalysis but not linear
• Feistel Ciphers: an iterated cipher, state on round 𝑖 divided into two halves, picture 𝑝𝑔 20
• DES is a 16 round Feistel cipher where:
• m=64, 𝐿𝑖 and 𝑅 𝑖 are bitstrings of length 32
• 𝑘 56 bits long
• initial permutation 𝐿0 𝑅 0 = 𝐼 𝑃(𝑥)
• inverse permutation 𝐼𝑃 −1 (𝑅16 𝐿16 )
• 𝑓 ∶ {0,1}32 × {0,1}48 → {0,1}32
• 𝑓 consists of a sub (S-box) followed by a perm
• DES 𝑓 function:
• expand 𝑅 𝑖−1 to 48 bits and x-or with 𝑘 𝑖 : state = 𝐸(𝑅 𝑖−1 ) ⨁ 𝑘 𝑖
• apply subs to state
• permute state: 𝑠𝑡𝑎𝑡𝑒 = 𝑃(𝑠𝑡𝑎𝑡𝑒)
• diagram page 21
• security:




• DES has 4 weak keys and 6 pairs of semi-weak keys
• Theorem 2: DES is not a group

DES (Double)
• a product cipher
• 𝑘1 , 𝑘2 DES keys of length 56 bits
• double DES encryption: 𝑒(𝑘1 ,𝑘2) (𝑥) = 𝑒𝑘𝐷𝐸𝑆
2
(𝑒𝑘𝐷𝐸𝑆
1
(𝑥))
• double DES decryption: 𝑑(𝑘1,𝑘2) (𝑥) = 𝑑𝑘𝐷𝐸𝑆
1
(𝑑𝑘𝐷𝐸𝑆
2
(𝑥))
• the combined key length of (𝑘1 , 𝑘2 ) is 112 bits
• security: meet in the middle attack
• Double-DES essentially no more secure than DES itself

DES (Triple)
• variant 1: three keys
• select 3 independent keys 𝑘1 , 𝑘2 , 𝑘3
• encryption: 𝑒(𝑘1,𝑘2, 𝑘3) (𝑥) = 𝑒𝑘𝐷𝐸𝑆
3
(𝑑𝑘𝐷𝐸𝑆
2
(𝑒𝑘𝐷𝐸𝑆
1
(𝑥)))