- currently the most widely used block cipher in the world
- developed as a result of the NBS (now NIST) called for possible encryption algorithms for use in unclassified government applications
- in May 1973, and again in Aug 1974
- response was mostly disappointing (reworked classical or machine ciphers)
- however IBM submitted Lucifer
- was redesigned to became the Data Encryption Standard (DES)
- adopted as a (US) federal standard in Nov 76
- published by NBS as a hardware only scheme in Jan 77
- by ANSI for both h/w & s/w in ANSI X3.92-1981 (& X3.106-1983 modes of use)
- subsequently widely adopted and is in many standards around the world
- cf Australian Standard AS2805.5-1985
- one of the largest users of the DES is the banking industry, particularly with EFT, and EFTPOS
- it is for this use that the DES has primarily been standardised, with ANSI reconfirming its use for 5 year periods - in future will use AES
- although the standard is public, the design criteria used are classified
- was considerable controversy over the design
- particularly in the choice of a 56-bit key, cf.
- W Diffie, M Hellman "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74-84
- M Hellman "DES will be totally insecure within ten years" IEEE Spectrum 16(7), Jul 1979, pp 31-41
- recent analysis has shown despite this that the choice was appropriate, and that DES is well designed
- rapid advances in computing speed though have rendered the 56 bit key susceptible to exhaustive key search, as predicted by Diffie & Hellman
- have demonstrated breaks:
- 1997 on a large network of computers in a few months
- 1998 on dedicated h/w (EFF) in a few days
- 1999 above combined in 22hrs!
- the DES also theoretically broken using Differential or Linear Cryptanalysis
- in practise is unlikely to be a problem yet
unless the information needs to be secured for long periods. Key issue is how much is the security worth. If only securing a funds transfer for a few seconds, it wont matter once its done if the message s subsequently broken. However is encrypting a highly sensitive spy report, may well not want it to be broken even 50 years later. Would not use DES for this.
- the basic process in enciphering a 64-bit data block using the DES
consists of:
- an initial permutation (IP)
- 16 rounds of a complex key dependent calculation f
- a final permutation, being the inverse of IP
DES is also a classic Feistel cipher, with 16 rounds, working on 64-bit blocks of data. We will examine its structure and internal workings in details, because its both a widely used and known cipher, and because it embodies many of the concepts of modern block ciphers.
- the subkeys used in each round are formed by the key schedule which has:
- an initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves
- 16 stages consisting of:
- selecting 24-bits from each half
- permuting them by PC2 for use in function f,
- rotating each half separately either 1 or 2 places depending on the key rotation schedule KS
- can be described functionally as:
SKi = PC2(KS(PC1(Key),i))
Emphasise that following PC1, the key schedule is in TWO independent halves, the rotations happen separately on each of the halves, and PC2 is effectively 2 smaller permutations taking bits strictly from C to S-boxes 1-4, and from D to S-boxes 5-8.
- PC1 is used to select 56 of 64 bits supplied as the key
- every 8th bit is discarded (assumed to be parity)
- nb. simplisitic s/w implementations which just concatenate 8 bytes, essentially only have 48-bits
- PC1 also splits the key bits into 2 halves (C and D)
- nb. in DES number bits from 1 (left, MSB) to 32/64 (right, LSB)
57, 49, 41, 33, 25, 17, 9, C Half 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, D Half 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
The 56 bit size comes from security considerations as we know now. It was big enough so that an exhaustive key search was about as hard as the best direct attack (a form of differential cryptanaysis called a T-attack, known by the IBM & NSA researchers), but no bigger. The extra 8 bits were then used as parity (error detecting) bits, which makes sense given the original design use for hardware communications links. However we hit an incompatibility with simple s/w implementations since the top bit in each byte is 0 (since ASCII only uses 7 bits), but the DES key schedule throws away the bottom bit! A good implementation needs to be cleverer!
Note that the bit numbering for DES reflects IBM mainframe practice, and is the opposite of what we now mostly use - so be careful! Read this (and the other DES permutations as follows: Bit 1 (leftmost) out of PC2 comes from bit 57 of the input. Bit 2 from bit 49. Bit 3 from bit 41 etc to bit 56 (rightmost) from bit 4.
- PC2 is used to select 48 bits (actually 2 lots of 24 bits)
- used in each round of the DES data computation
- C half provides bits to S1-S4, D half to S5-S8
14, 17, 11, 24, 1, 5, C half 3, 28, 15, 6, 21, 10, (bits 1-28) 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, D half 30, 40, 51, 45, 33, 48, (bits 29-56) 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
PC2 collects groups of bits from across each half to feed into each S-box, thus making sure the output depends in a complex way on the key. The split into 2 halves again reflects the limitations of h/w at the time. Note that 4 bits aren't used each time.
- the key rotation schedule KS is specified as:
Round 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 KS 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Total 1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28
The key rotation schedule along with PC2 ensures that on successive rounds any given key bit affects a different S-box, and if missed for one round, will be used in the next. Also, after 16 rounds each key half register is back to its starting value, which makes compting keys for decryption easier, just rotate the other way, and use the rotation amounts in the reverse order.
keyinit(5b5a5767, 6a56676e) PC1(Key) C=00ffd820, D=ffec9370 KeyRnd01 C=01ffb040, D=ffd926f0, PC2(C,D)=(38 09 1b 26 2f 3a 27 0f) KeyRnd02 C=03ff6080, D=ffb24df0, PC2(C,D)=(28 09 19 32 1d 32 1f 2f) KeyRnd03 C=0ffd8200, D=fec937f0, PC2(C,D)=(39 05 29 32 3f 2b 27 0b) KeyRnd04 C=3ff60800, D=fb24dff0, PC2(C,D)=(29 2f 0d 10 19 2f 1d 3f) KeyRnd05 C=ffd82000, D=ec937ff0, PC2(C,D)=(03 25 1d 13 1f 3b 37 2a) KeyRnd06 C=ff608030, D=b24dfff0, PC2(C,D)=(1b 35 05 19 3b 0d 35 3b) KeyRnd07 C=fd8200f0, D=c937ffe0, PC2(C,D)=(03 3c 07 09 13 3f 39 3e) KeyRnd08 C=f60803f0, D=24dfffb0, PC2(C,D)=(06 34 26 1b 3f 1d 37 38) KeyRnd09 C=ec1007f0, D=49bfff60, PC2(C,D)=(07 34 2a 09 37 3f 38 3c) KeyRnd10 C=b0401ff0, D=26fffd90, PC2(C,D)=(06 33 26 0c 3e 15 3f 38) KeyRnd11 C=c1007fe0, D=9bfff640, PC2(C,D)=(06 02 33 0d 26 1f 28 3f) KeyRnd12 C=0401ffb0, D=6fffd920, PC2(C,D)=(14 16 30 2c 3d 37 3a 34) KeyRnd13 C=1007fec0, D=bfff6490, PC2(C,D)=(30 0a 36 24 2e 12 2f 3f) KeyRnd14 C=401ffb00, D=fffd9260, PC2(C,D)=(34 0a 38 27 2d 3f 2a 17) KeyRnd15 C=007fec10, D=fff649b0, PC2(C,D)=(38 1b 18 22 1d 32 1f 37) KeyRnd16 C=00ffd820, D=ffec9370, PC2(C,D)=(38 0b 08 2e 3d 2f 0e 17)
Note that all numbers are written in hexadecimal as a "short-form"
version of the binary actually used, since 1 Hex digit = 4 Binary bits.
The digit mapping is:
0=0000 1=0001 2=0010 3=0011 4=0100 5=0101 6=0110 7=0111
8=1000 9=1001 a=1010 b=1011 c=1100 d=1101 e=1110 f=1111
- provides the actual scrambling (en/decryption) of the data
- first has an initial permutation which rearranges the input
- has 16 rounds of the complex non-linear round function f
- which has expansion E, key addition, substitution S, permutation P:
- result is XOR's with LH half of data, and the halves are swapped
- can be described functionally as:
Li = Ri-1 Ri = Li-1 XOR P(S(E(Ri-1) XOR SKi))
- finishes with the final permutation (inverse of the initial permutation)
- first step of the data computation
- IP reorders the input data bits
- even bits to LH half, odd bits to RH half
- quite regular in structure (easy in h/w)
- generally doesn't improve actual security
- just makes the cipher more complex
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
- Example:
IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)
- expands RH side data input from 32 to 48 bits
- by duplicating some bits
- specifically split input into 8 groups of 4 bits
- then duplicate bits from either side to form groups of 6 bits
- provides an autokeying effect for following S-boxes
32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1
- Example:
E(004df6fb) = 20 00 09 1b 3e 2d 1f 36E expands the data input to 48-bits, before its added to the subkey. The duplicated outside bits in each group of 6 act as a key to the following S-box, allowing the data (as well as the key) to influence the S-box operation. This is known as autokeying or autoclave.
- the expanded 48 data bits are then XORed (addition modulo 2) to the 48 subkey bits selected by PC2
- thus the key bits influence the result of the round function
- Example:
E(R): 20 00 09 1b 3e 2d 1f 36 XOR SK: 38 09 1b 26 2f 3a 27 0f = 18 09 12 3d 11 17 38 39
- there are 8 S-boxes, each of which maps 6 bits to 4 bits
- each S-box is actually 4 little 4 bit boxes
- outer bits 1 & 6 (row bits) select one of the 4 rows
- inner bits 2-5 (col bits) are substituted for 4 others
- result is 8 lots of 4 bits, or 32 bits
0 1 2 3 4 5 6 7 8 9 a b c d e f COL S[1] 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 S[2] 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 S[3] 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 S[4] 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 S[5] 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 S[6] 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 S[7] 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 S[8] 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
- Example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03Note the values in the tables above are given in decimal (as is usally shown in the specs). When working through the examples, you'll need to convert to binary or hex.
- P diffuses the S-box outputs across different S-box inputs in the next round
- numbers appear scrambled, but do have some pattern
- ensures each S-box outs affect both row and col bits
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
- Example:
P(5fd25e03) = 746fc91a
- once the result of the round function
fhas been computed - the result is XOR'd (added modulo 2) to the
Ldata half - and the halves are exchanged (except in the last round)
- Example:
f = 746fc91a, L0=ffb2194d, f ^ L0 = 8bddd057 = R1
L1 = R0 = 004df6fb
- last step after the 16 rounds
- result become the output from the DES computation
- does the inverse mapping to IP
- hence when decrypting the IP undoes this
40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25
- Example:
FP(068dddcd 1d4ccebf) = 974affbf, 86022d1f
- to decrypt a block of data must unwind all steps of data computation
- but with Feistel design, same as just doing encryption steps again
- except that must use subkeys in reverse order (SK16 first, the SK15 etc)
- note that IP undoes the final FP step of encryption
- first round with SK16 undoes 16th round of encryption
- etc till 16th round with SK1 undoes 1st encryption round
- and final FP undoes the initial encryption IP
- thus recovering the original data value
- you are expected to be able to trace through 1 round of the DES data computation
- given L & R data halves and SK, compute the new data half values
- as has been done in the examples above
-
descertis a program used to verify a DES implementation - given known correct triples of (
key plain cipher) - first encrypts plain using key and checks get cipher
- then decrypts cipher using key and checks get plain
- with debugging compiled in also display values for each round
Rnd f(R 32bit data value, SK 48 (8x6bit) subkey) = function output XOR L
note that the L data value is not given (but of course is just previous R value) - eg. when run on triple used by Katzan reference:
keyinit(5b5a5767, 6a56676e) endes[P=(675a6967, 5e5a6b5a)] IP(P) = (L0=ffb2194d, R0=004df6fb) Rnd01 f(R00=004df6fb, SK01=(38 09 1b 26 2f 3a 27 0f)) = 746fc91a ^ L00 Rnd02 f(R01=8bddd057, SK02=(28 09 19 32 1d 32 1f 2f)) = 7add38ae ^ L01 Rnd03 f(R02=7a90ce55, SK03=(39 05 29 32 3f 2b 27 0b)) = a5e3f499 ^ L02 Rnd04 f(R03=2e3e24ce, SK04=(29 2f 0d 10 19 2f 1d 3f)) = c5403e1c ^ L03 Rnd05 f(R04=bfd0f049, SK05=(03 25 1d 13 1f 3b 37 2a)) = 91a62c82 ^ L04 Rnd06 f(R05=bf98084c, SK06=(1b 35 05 19 3b 0d 35 3b)) = 6aeb6bc3 ^ L05 Rnd07 f(R06=d53b9b8a, SK07=(03 3c 07 09 13 3f 39 3e)) = 1e9f7513 ^ L06 Rnd08 f(R07=a1077d5f, SK08=(06 34 26 1b 3f 1d 37 38)) = 59d1851c ^ L07 Rnd09 f(R08=8cea1e96, SK09=(07 34 2a 09 37 3f 38 3c)) = 0fc4b474 ^ L08 Rnd10 f(R09=aec3c92b, SK10=(06 33 26 0c 3e 15 3f 38)) = 8de55e67 ^ L09 Rnd11 f(R10=010f40f1, SK11=(06 02 33 0d 26 1f 28 3f)) = dced7991 ^ L10 Rnd12 f(R11=722eb0ba, SK12=(14 16 30 2c 3d 37 3a 34)) = 898d0def ^ L11 Rnd13 f(R12=88824d1e, SK13=(30 0a 36 24 2e 12 2f 3f)) = 34cee3c3 ^ L12 Rnd14 f(R13=46e05379, SK14=(34 0a 38 27 2d 3f 2a 17)) = 6a4754b1 ^ L13 Rnd15 f(R14=e2c519af, SK15=(38 1b 18 22 1d 32 1f 37)) = 5bac9dc6 ^ L14 Rnd16 f(R15=1d4ccebf, SK16=(38 0b 08 2e 3d 2f 0e 17)) = e448c462 ^ L15 L16=068dddcd, R16=1d4ccebf endes returns C = FP(L16,R16) = (974affbf, 86022d1f) dedes[C=(974affbf, 86022d1f)] IP(C) = (L0=068dddcd, R0=1d4ccebf) Rnd01 f(R00=1d4ccebf, SK01=(38 0b 08 2e 3d 2f 0e 17)) = e448c462 ^ L00 Rnd02 f(R01=e2c519af, SK02=(38 1b 18 22 1d 32 1f 37)) = 5bac9dc6 ^ L01 Rnd03 f(R02=46e05379, SK03=(34 0a 38 27 2d 3f 2a 17)) = 6a4754b1 ^ L02 Rnd04 f(R03=88824d1e, SK04=(30 0a 36 24 2e 12 2f 3f)) = 34cee3c3 ^ L03 Rnd05 f(R04=722eb0ba, SK05=(14 16 30 2c 3d 37 3a 34)) = 898d0def ^ L04 Rnd06 f(R05=010f40f1, SK06=(06 02 33 0d 26 1f 28 3f)) = dced7991 ^ L05 Rnd07 f(R06=aec3c92b, SK07=(06 33 26 0c 3e 15 3f 38)) = 8de55e67 ^ L06 Rnd08 f(R07=8cea1e96, SK08=(07 34 2a 09 37 3f 38 3c)) = 0fc4b474 ^ L07 Rnd09 f(R08=a1077d5f, SK09=(06 34 26 1b 3f 1d 37 38)) = 59d1851c ^ L08 Rnd10 f(R09=d53b9b8a, SK10=(03 3c 07 09 13 3f 39 3e)) = 1e9f7513 ^ L09 Rnd11 f(R10=bf98084c, SK11=(1b 35 05 19 3b 0d 35 3b)) = 6aeb6bc3 ^ L10 Rnd12 f(R11=bfd0f049, SK12=(03 25 1d 13 1f 3b 37 2a)) = 91a62c82 ^ L11 Rnd13 f(R12=2e3e24ce, SK13=(29 2f 0d 10 19 2f 1d 3f)) = c5403e1c ^ L12 Rnd14 f(R13=7a90ce55, SK14=(39 05 29 32 3f 2b 27 0b)) = a5e3f499 ^ L13 Rnd15 f(R14=8bddd057, SK15=(28 09 19 32 1d 32 1f 2f)) = 7add38ae ^ L14 Rnd16 f(R15=004df6fb, SK16=(38 09 1b 26 2f 3a 27 0f)) = 746fc91a ^ L15 L16=ffb2194d, R16=004df6fb dedes returns P = FP(L16,R16) = (675a6967, 5e5a6b5a) Test 0, K: 5b5a57676a56676e P: 675a69675e5a6b5a C: 974affbf86022d1f OK descert: 0 failures in 1 tests
Discuss the interpretation of this trace of DES in operation. Given a triple comprising (Key,Plain,Cipher),
descertfirstly encrypts plain using key and checks it gets the cipher, then decrypts cipher using key and checks it gets plain. If both occur, the test succeeds. As it does each en/decryption, a trace is printed of the data values in each round: 32-bit RH data values and 48-bit SubKey value (note display as 8 x 6-bit values) going into the round functionf, and the result offwhich then must be XOR'd with the LH data value (which is not shown, as its just the previous RH value). All values are written in hexadecimal (base 16 numbers).