Block ciphers-DES DATA ENCRYPTION STANDARD 曹天杰 Tianjie Cao ticao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou China 中国矿业大学计算机科学与技术学院 2003.5.19
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.19 Block ciphers-DES DATA ENCRYPTION STANDARD
DES 1973, NBS solicits proposals for cryptosystems for“ unclassified” documents 1974, NBS repeats request IBM responds with modification of LUCIFER NBS asks nsa to evaluate BM holds patent for dES 1975, details of the algorithm published, public discussion begins des became a federal standard in november 76 NBS(NIST hardware standard in January 77 ANSI X3.92-1981(hardware software ANSI X3 106-1983(modes of operation Australia As2805.5-1985
2 DES • 1973, NBS solicits proposals for cryptosystems for “unclassified” documents. • 1974, NBS repeats request. IBM responds with modification of LUCIFER. NBS asks NSA to evaluate. IBM holds patent for DES. • 1975, details of the algorithm published, public discussion begins. • DES became a federal standard in November 76 – NBS (NIST) hardware standard in January 77 – ANSI X3.92-1981 (hardware + software) – ANSI X3.106-1983 (modes of operation) – Australia AS2805.5-1985
DES 1983, no problem. First publicly available algorithm certified by Nsa as secure. Certificate to be renewed every 5 years 1987, passed, but NSa says that des soon will be vulnerable to brute force attack. This is the last time Business lobbies to keep it, since so the had much invested 1993, still passed(no alternatives) 1997, call for proposals: AES
3 DES • 1983, no problem. First publicly available algorithm certified by NSA as secure. Certificate to be renewed every 5 years. • 1987, passed, but – NSA says that DES soon will be vulnerable to bruteforce attack. This is the last time. – Business lobbies to keep it, since so the had much invested. • 1993, still passed (no alternatives). • 1997, call for proposals: AES
DES Design Controversy Originally designed to be efficient in hardware. A LOT of money has been invested in hardware although dES standard is public there was considerable controversy over design in choice of 56-bit key(vs Lucifer 128-bit) and because design criteria were classified subsequent events and public analysis show in fact design was appropriate DES has become widely used, especially in financial applications
4 DES Design Controversy • Originally designed to be efficient in hardware . A LOT of money has been invested in hardware. • although DES standard is public there was considerable controversy over design – in choice of 56-bit key (vs Lucifer 128-bit) – and because design criteria were classified • subsequent events and public analysis show in fact design was appropriate • DES has become widely used, especially in financial applications
DES Standard Cipher Iterative Key generation Action Box Input: 64 bits nput: 56 bits Key: 48 bits Output: 48 bits Output: 64 bits One round (Total 16 rounds)
5 DES Standard • Cipher Iterative Action : – Input: 64 bits – Key: 48 bits – Output: 64 bits • Key Generation Box : – Input: 56 bits – Output: 48 bits One round (Total 16 rounds)
Feistel Networks f,…k:{0,1→0.1} Arbitrary functions ° Not necessarily invertible ④← R=L1f(R:1) 卫s8αx卫
6 Feistel Networks f1 , …, fk : {0,1}n → {0,1}n • Arbitrary functions • Not necessarily invertible f1 f2 fk-1 fk L0 : R0 : L1 : R1 : Lk-2 : Rk-2 : Lk-1 : Rk-1 : Lk : Rk : n bits n bits Round 1 Round 2 Round k-1 Round k … Li = Ri-1 Ri = Li-1 fi (Ri-1 )
Inverting a Feistel Network Theorem For any f1,…fk:{0,1}n→{0,1yn, a feistel network computes a permutationπ:{0,1}→{0,1}n L1=R1⊕f(L1 Inverse:
7 Inverting a Feistel Network f1 f2 fk-1 fk L0 : R0 : L1 : R1 : Lk-2 : Rk-2 : Lk-1 : Rk-1 : Lk : Rk : … Li-1 = Ri fi (Li ) Ri-1 = Li Theorem For any f1 , …, fk : {0,1}n → {0,1}n , a Feistel network computes a permutation p : {0,1}n → {0,1}n Inverse:
Feistel Cipher Design Principles ·b| ock size increasing size improves security, but slows cipher key size increasing size improves security, makes exhaustive key searching harder, but may slow cipher number of rounds increasing number improves security, but slows cipher subkey generation greater complexity can make analysis harder, but slows cipher · round function greater complexity can make analysis harder, but slows cipher fast software en/decryption ease of analysis are more recent concerns for practical use and testing 8
8 Feistel Cipher Design Principles • block size – increasing size improves security, but slows cipher • key size – increasing size improves security, makes exhaustive key searching harder, but may slow cipher • number of rounds – increasing number improves security, but slows cipher • subkey generation – greater complexity can make analysis harder, but slows cipher • round function – greater complexity can make analysis harder, but slows cipher • fast software en/decryption & ease of analysis – are more recent concerns for practical use and testing
Inside des cleartext DES is a feistel network with 16 rounds 64 bit cleartext blocks 56 bits key 16-round f,, 16 derived from key Feistel Network Initial permutation T (public) Decryption Apply f16, ,f,(in reverse order) Same chip ciphertext
9 Inside DES DES is a Feistel network with – 16 rounds – 64 bit cleartext blocks – 56 bits key – f1 , …, f16 derived from key – Initial permutation p (public) – Decryption • Apply f16, …, f1 (in reverse order) • Same chip cleartext ciphertext 16-round Feistel Network p p -1 key 64 64 64 64 56
Inside des Xo=P(m)= 07v0 16 Rounds,=1,2,,16: =L40f -1 Where f(Ri, Ki=p(s(e(rio ki), with operations E(expansion S(S-box lookup), and P some (permutation) c=|P1(L16R16) 10
10 Inside DES • x0 = IP(m) = L0R0 . • 16 Rounds, i = 1, 2, …, 16: Li := Ri-1 , Ri := Li-1 f (Ri-1 , Ki ), where f (Ri-1 , Ki ) = P(S(E(Ri-1 ) Ki )), with operations E (expansion), S (S-box lookup), and P some (permutation). • c = IP-1 (L16R16)