DES
(Data Encryption Standard)
Stream Ciphers vs. Block Ciphers
Stream cipher encrypts digital data one bit (byte) at a time Block cipher encrypts block of plaintext at a time
Will produce a ciphertext block of the same size
DES Basics
Block cipher (64-bit block) Uses 56-bit key (out of 64 bits) 16 rounds 48-bit subkeys Feistel structure (except initial and final permutations)
DES
Overall Scheme of DES Encryption
Initial Permutation (IP) and Inverse IP
DES
Single Round of DES
DES Round function F
DES
DES Round Function
Operates on 32-bit units 32-bit 48-bit expansion/permutation (E table) XOR with 48 bit subkey S-box computation returns 32 bits Round permutation (P)
Look at the following diagram!!!
Single Round of DES cont
Expansion E and Permutation P
10
S-BOX Substitution
S-BOX: 4 x 16 entry table
Input: 6 bits 2-bits determine the table (1 s/d 4) 4-bits determine the table entry Output: 4 bits
11
S-BOX table
12
DES Key Generation
Parity bits (8, 16, , 64) are discarded (out of 64-bit key) 56-bit key is split into 28-bit L and R 16 48-bit subkeys (K1, K2, , K16) are generated by various circular left shifts of L and R Bits are permuted and selected
13
Security of DES
This secret key is 56 bits Trying out all 72,057,594,037,927,936 possible keys (a seven with 16 zeros) would be impossible because computers could not possibly ever become fast enough. In 1998 the Electronic Frontier Foundation (EFF) built a special-purpose machine that could decrypt a message by trying out all possible keys in less than three days. The machine cost less than $250,000 and searched over 88 billion keys per second.
14
Triple-DES with Two-Keys
hence must use 3 encryptions
would seem to need 3 distinct keys
but can use 2 keys with E-D-E sequence
C = EK1[DK2[EK1[P]]] NB: encrypt & decrypt equivalent in security if K1=K2 then can work with single DES
standardized in ANSI X9.17 & ISO8732 no current known practical attacks
15
Triple-DES with Three-Keys
The Triple-DES variant was developed after it became clear that DES by itself was too easy to crack. It uses three 56-bit DES keys, giving a total key length of 168 bits. Encryption using Triple-DES
encryption using DES with the first 56-bit key decryption using DES with the second 56-bit key encryption using DES with the third 56-bit key C = EK3[DK2[EK1[P]]]
Has been adopted by some Internet applications, eg PGP, S/MIME
16
DES variant
DESL was first presented at the workshop on RFID security (RFIDSec) in 2006. DESL was designed by the Communication Security Group at the Ruhr University Bochum.
Key: 56 bit Application: RFID tags (resource constrained devices in general)
DESX(x) = K2 + DESKDES(x + K1)
Key: 168 bit
DESXL(x) = K2 + DESLKDESL(x + K1)
Key: 168 bit
17
Modes of Operation
Modes of Operation
Block ciphers encrypt fixed size blocks
eg. DES encrypts 64-bit blocks, with 56-bit key
need way to use in practise, given usually have arbitrary amount of information to encrypt Four were defined for DES in ANSI standard ANSI X3.106-1983 Modes of Use subsequently now have 5 for DES and AES have block and stream modes
19
Electronic Code Book (ECB)
message is broken into independent blocks which are encrypted one at a time each block is a value which is substituted, like a codebook each block is encoded independently of the other blocks
Ci = DESK1 (Pi)
20
Electronic Codebook Book (ECB)
21
Limitations of ECB
repetitions in message may show in ciphertext
main use is sending a few blocks of data, for example, an encryption key
22
Cipher Block Chaining (CBC)
message is broken into blocks but these are linked together in the encryption operation each previous cipher blocks is chained with current plaintext block use Initial Vector (IV) to start process
Ci = DESK1(Pi XOR Ci-1) C-1 = IV
uses: bulk data encryption, authentication
23
Cipher Block Chaining (CBC)
24
Advantages and Limitations of CBC
each ciphertext block depends on all message blocks thus a change in the message affects all ciphertext blocks after the change as well as the original block need Initial Value (IV) known to sender & receiver at end of message, handle possible last short block
by padding either with known non-data value (eg nulls) or pad last block with count of pad size
eg. [ b1 b2 b3 0 0 0 0 5] <- 3 data bytes, then 5 bytes pad+count
25
Cipher FeedBack (CFB)
message is treated as a stream of bits added to the output of the block cipher result is feed back for next stage standard allows any number of bit (1,8 or 64 or whatever) to be feed back
denoted CFB-1, CFB-8, CFB-64 etc
is most efficient to use all 64 bits (CFB-64)
Ci = Pi XOR DESK1(Ci-1) C-1 = IV
uses: stream data encryption, authentication
26
Cipher FeedBack (CFB)
27
Advantages and Limitations of CFB
appropriate when data arrives in bits/bytes most common stream mode limitation is need to stall while do block encryption after every n-bits note that the block cipher is used in encryption mode at both ends
28
Output FeedBack (OFB)
message is treated as a stream of bits output of cipher is added to message output is then feed back (hence name) feedback is independent of message can be computed in advance
Ci = Pi XOR Oi Oi = DESK1(Oi-1) O-1 = IV
uses: stream encryption over noisy channels
29
Other Symmetric Block Ciphers
International Data Encryption Algorithm (IDEA) Skipjack Blowfish
30
International Data Encryption Algorithm (IDEA)
Developed by Xu Lai & James Massey (ETH Zurich, Switzerland) Characteristics:
64-bits block cipher 128-bits key length Uses three algebraic groups: XOR, + mod 216, x mod 216 + 1 17 rounds (or 8 rounds according to the description)
Speed: software 2 times faster than DES
31
32
Skipjack
is a recent algorithm that was developed in 1987 and put into service in 1993. encrypts and decrypts data in 64-bit blocks using an 80-bit key Skipjack has 32 rounds, meaning the main algorithm is repeated 32 times to produce the ciphertext.
33
Rule A and B
34
Diagram of Rule A and Rule B
35
SkipJack: Encryption & Decryption
36
Blowfish
has a 64-bit block size and a variable key length from 0 up to 448 bits 16-round Feistel cipher
37
Structure of Blowfish
38
demo blowfish
http://www.php-einfach.de/blowfish_en.php
demo AES
http://www.cs.bc.edu/~straubin/cs38105/blockciphers/rijndael_ingles2004.swf
39
