Block Ciphers (part 1)

Modern Private Key Ciphers (part 1)

Stream Ciphers and the Vernam cipher

Block Ciphers

Shannons Theory of Secrecy Systems

Key Size (bits)         Time (1us/test)              Time (1us/106test)             
24                      8.4 sec                      8.4 usec                       
32                      35.8 mins                    2.15 msec                      
40                      6.4 days                     550 msec                       
48                      4.46 yrs                     2.35 mins                      
56                      ~2000 yrs                    10.0 hrs                       
64                      ~500000 yrs                  107 days                       

Substitution-Permutation Ciphers

Substitution Operation Permutation Operation Substitution-Permutation Network
A F Webster & S E Tavares "On the Design of S-boxes", in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp 523-534

Avalanche effect

More formally, a function f has a good avalanche effect if for each bit i,0<=i<m, if the 2^(m) plaintext vectors are divided into 2^(m-1) pairs X and X_(i) with each pair differing only in bit i; and if the 2^(m-1) exclusive-or sums, termed avalanche vectors

V_(i) = f(X) (+) f(X_(i))

are compared, then about half of these sums should be found to be 1.

Completeness effect

More formally, a function f has a good completeness effect if for each bit j,0<=j<m, in the ciphertext output vector, there is at least one pair of plaintext vectors X and X_(i) which differ only in bit i, and for which f(X) and f(X_(i)) differ in bit j

Practical Substitution-Permutation Networks

L(i) = R(i-1)

R(i) = L(i-1) (+) g(K(i), R(i-1))


Sorkin Fig 1 p24


Overview of the DES Encryption Algorithm

L(i) = R(i-1)

R(i) = L(i-1) (+) P(S( E(R(i-1))(+) K(i) ))

and forms one round in an S-P network

K(i) = PC2(KS(PC1(K),i))
   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 Rot     1    2   4    6    8    10   12   14   15   17   19   21   23   25   27   28   

H Katzan, "The Standard Data Encryption Algorithm", Petrocelli Books, New York, 1977

DES Modes of Use

Block Modes
splits messages in blocks (ECB, CBC)
Stream Modes
on bit stream messages (CFB, OFB)

Block Modes

Electronic Codebook Book (ECB)
- where the message is broken into independent 64-bit blocks which are encrypted
			C_(i) = DES_(K1) (P_(i))
Cipher Block Chaining (CBC)
- again the message is broken into 64-bit blocks, but they are linked together in the encryption operation with an IV
C_(i) = DES_(K1) (P_(i)(+)C_(i-1)) C_(-1)=IV

Stream Modes

Cipher FeedBack (CFB)
- where the message is treated as a stream of bits, added to the output of the DES, with the result being feed back for the next stage
C_(i) = P_(i)(+) DES_(K1) (C_(i-1)) C_(-1)=IV
Output FeedBack (OFB)
- where the message is treated as a stream of bits, added to the message, but with the feedback being independent of the message
C_(i) = P_(i)(+) O_(i) O_(i) = DES_(K1)(O_(i-1)) O_(-1)=IV

Limitiations of Various Modes


Davies Fig 4.1 p81


Davies Fig 4.5 p85


Davies Fig 4.7 p88 & Fig 4.8 p89


D Davies, G Parkin, "The Average Cycle Size of the Key Stream in Output Feedback Encipherment" in Advances in Cryptology - Crypto 82, Plenum Press, 1982, pp97-98
Davies Fig 4.12 p94

DES Weak Keys

Weak Keys

Semi-Weak Keys

Demi-Semi Weak Keys

DES Design Principles

L P Brown, "A Proposed Design for an Extended DES", in Computer Security in the Age of Information, W. J. Caelli (ed), North-Holland, pp 9-22, 1989

L P Brown, J R Seberry, "On the Design of Permutation Boxes in DES Type Cryptosystems", in Advances in Cryptology - Eurocrypt '89, Lecture Notes in Computer Science, vol 434, pp 696-705, J.J. Quisquater, J. Vanderwalle (eds), Springer-Verlag, Berlin, 1990.

L P Brown and J R Seberry, "Key Scheduling in DES Type Cryptosystems," in Advances in Cryptology - Auscrypt '90, Lecture Notes in Computer Science, vol 453, pp 221-228, J. Seberry, J. Pieprzyk (eds), Springer-Verlag, Berlin, 1990.

DES S-Box Design Criteria

DES Design Criteria

R1: Each row of an S-box is a permutation of 0 to 15

R2: No S-Box is a linear of affine function of the input

R3: Changing one input bit to an S-box results in changing at least two output bits

R4: S(x) and S(x+001100) must differ in at least 2 bits

R5: S(x) [[pi]] S(x+11ef 00) for any choice of e and f

R6: The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input is held constant

R7: The S-boxes chosen require significantly more minterms than a random choice would require

Meyer Tables 3-17, 3-18

DES Permutation Tables

Ciphertext Dependence on Input and Key

Ciphertext dependence on Plaintext
L(i) = R(i-1)

R(i) = L(i-1) (+) f( K(i), R(i-1))

Ciphertext dependence on Key

Key Scheduling and PC2

Possible Techniques for Improving DES

Triple DES

			C = DES_(K1) Bbc{(DES^(-1)_(K2)Bbc{(DES_(K1)(P)))

[1] follow with Modes of Use illustrations
[2] follow with Appendix A from AS2805.5 (also found in Seberry Appendix B2)
[3] follow with Meyer - Fig 3-17; Fig 3-15, 3-16, 3-19; Fig 3-18, 3-21.
[CSC Info] / 15-Apr-96