Block Ciphers (part 1)
Modern Private Key Ciphers (part 1)
- now want to concentrate on modern encryption systems
- these usually consider the message as a sequence of bits
- (eg as a series of ASCII characters concatenated)
- have two broad families of methods
- stream ciphers and block ciphers
Stream Ciphers and the Vernam cipher
- process the message bit by bit (as a stream)
- the most famous of these is the Vernam cipher
- (also known as the one-time pad)
- invented by Vernam, working for AT&T, in 1917
- simply add bits of message to random key bits
- need as many key bits as message, difficult in practise
- (ie distribute on a mag-tape or CDROM)
- is unconditionally secure provided key is truly random
- since difficult to distribute so much key, why not generate keystream from
a smaller (base) key
- use some pseudo-random function to do this
- although this looks very attractive, it proves to be very very difficult
in practise to find a good pseudo-random function that is cryptographically
strong
- this is still an area of much research
Block Ciphers
- in a block cipher the message is broken into blocks, each of which is then
encrypted (ie like a substitution on very big characters - 64-bits or more)
- most modern ciphers we will study are of this form
Shannons Theory of Secrecy Systems
- Claude Shannon wrote some of the pivotal papers on modern cryptology
theory in 1949:
- C E Shannon, "Communication Theory of Secrecy Systems", Bell System
Technical Journal, Vol 28, Oct 1949, pp 656-715
- C E Shannon, "Prediction and Entropy of printed English", Bell System
Technical Journal, Vol 30, Jan 1951, pp 50-64
- in these he developed the concepts of:
- entropy of a message,
- redundancy in a language,
- theories about how much information is needed to break a cipher
- defined the concepts of computationally secure vs unconditionally secure
ciphers
- he showed that the Vernam cipher is the only currently known
unconditionally secure cipher, provided the key is truly random
- also showed that if try to encrypt English text by adding to other English
text (ie a Bookcipher), this is not secure since English is 80%
redundant, giving ciphertext with 60% redundancy, enough to break
- a similar technique can also be used if the same random key stream is used
twice on different messages, the redundancy in the messages is sufficient to
break this
- as discussed earlier, exhaustive key search is the most fundamental
attack, and is directly proportional to the size of the key
- can tabulate these for reasonable assumptions about the number of
operations possible (& parallel tests):
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
- as the ultimate limit, it can be shown from energy consumption
considerations that the maximum number of possible elementary operations in
1000 years is about: 3 x 10 ^(48)
- similarly can show that if need say 10 atoms to store a bit of
information, then the greatest possible number of bits storable in a volume of
say the moon is: 10 ^(45)
- if a cipher requires more operations, or needs more storage than
this, it is pretty reasonable to say it is computationally secure
- eg to test all possible 128-bit keys in Lucifer takes about 3
x 10 ^(48) encryptions, needing 10 ^(19)
years
Substitution-Permutation Ciphers
- in his 1949 paper Shannon also introduced the idea of
substitution-permutation (S-P) networks, which now form the basis of modern
block ciphers
- an S-P network is the modern form of a substitution-transposition product
cipher
- S-P networks are based on the two primitive cryptographic operations we
have seen before
Substitution Operation
- a binary word is replaced by some other binary word
- the whole substitution function forms the key
- if use n bit words, the key is 2^(n)!bits,
grows rapidly
- can also think of this as a large lookup table, with n address lines
(hence 2^(n) addresses), each n bits wide being the
output value
- will call them S-boxes
Permutation Operation
- a binary word has its bits reordered (permuted)
- the re-ordering forms the key
- if use n bit words, the key is n!bits, which grows more
slowly, and hence is less secure than substitution
- this is equivalent to a wire-crossing in practise (though is much harder
to do in software)
- will call these P-boxes
Substitution-Permutation Network
- Shannon combined these two primitives
- he called these mixing transformations
- Shannons mixing transformations are a special form of product ciphers where
- S-Boxes
- provide confusion of input bits
- P-Boxes
- provide diffusion across S-box inputs
- in general these provide the following results, as described in:
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
- where changing one input bit results in changes of approx
half the output bits
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
- where each output bit is a complex function of all the input bits
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
- in practise we need to be able to decrypt messages, as well as to encrypt
them, hence either:
- have to define inverses for each of our S & P-boxes, but this doubles
the code/hardware needed, or
- define a structure that is easy to reverse, so can use basically the same
code or hardware for both encryption and decryption
- Horst Feistel, working at IBM Thomas J Watson Research Labs devised just
such a structure in early 70's, which we now call a feistel cipher
- the idea is to partition the input block into two halves,
L(i-1)and R(i-1), and use only R(i-1)in each round
i (part) of the cipher
- the function g incorporates one stage of the S-P network,
controlled by part of the key K(i)known as the ith
subkey
- this can be described functionally as:
L(i) = R(i-1)
R(i) = L(i-1) (+) g(K(i), R(i-1))
- this can easily be reversed as seen in the above diagram, working
backwards through the rounds
- in practise link a number of these stages together (typically 16 rounds)
to form the full cipher
Lucifer
- Lucifer is the first publically known example of a practical
substitution-permutation cipher
- it was developed by Horst Feistel at IBM labs
- the best known public reference is his paper:
- Horst Feistel, "Cryptography and Computer Privacy", Scientific American,
Vol 228(5), May 1973, pp 15-23.
- it provides an overview of his work, but actual details of Lucifer are
very sketchy, the best detailed reference:
- Arthur Sorkin, "Lucifer, A Cryptographic Algorithm", Cryptologia, Vol
8(1), Jan 1984, pp 22-41, with addenda in Vol 8(3) pp260-261
- this contains a detailed description of the algorithm, plus a Fortran
implementation
- the original descriptions are not the clearest
Sorkin Fig 1 p24
- redrawn in modern form, Lucifer has the following form:
- Lucifer uses 128-bit data blocks and 128-bit keys, and uses a Feistel
structure
- the subkeys used in each round are taken from the left part of the key,
which is then rotated left 56-bits, so all key bits are used
- the S-P function for Lucifer has the following structure:
- the substitution consists of 8 identical pairs of 4-bit S-boxes (S0 &
S1) used in alternate order (S0|S1) or (S1|S0) depending on the key
- then the subkey is added modulo 2
- and the result is permuted through a combination of small 8-bit
permutations and a large 128-bit simple permutation (convolution)
- for details see Sorkin
- from the little known discussion, Lucifer appears to be a fairly well
constructed cipher, although recently it has been theorectically broken by
differential cryptanalysis
- its main claim is that it is the predecessor the DES, developed by IBM in
the mid 70's and submitted to the NBS (& NSA) to become the standard
encryption algorithm for commercial use at the time
DES
- in May 1973, and again in Aug 1974 the NBS (now NIST) called for possible
encryption algorithms for use in unclassified government applications
- response was mostly disappointing, however IBM submitted their Lucifer
design
- following a period of redesign and comment it became the Data Encryption
Standard (DES)
- it was adopted as a (US) federal standard in Nov 76, published by NBS as a
hardware only scheme in Jan 77 and by ANSI for both hardware and software
standards in ANSI X3.92-1981 (also X3.106-1983 modes of use)
- subsequently it has been widely adopted and is now published 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
having twice reconfirmed its recommended use for 5 year periods - a further
extension is not expected however
- although the standard is public, the design criteria used are classified
and have yet to be released
- there has been considerable controversy over the design, particularly in
the choice of a 56-bit key
- 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
- the DES has also been theorectically broken using a method called
Differential Cryptanalysis, however in practise this is unlikely to be a
problem (yet)
Overview of the DES Encryption Algorithm
- 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
- in more detail the 16 rounds of f consist of:
- this can be described functionally as
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
- the subkeys used by the 16 rounds are formed by the key schedule
which consists of:
- 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 and permuting them by PC2 for use in
function f,
- rotating each half either 1 or 2 places depending on the key rotation
schedule KS
- this can be described functionally as:
K(i) = PC2(KS(PC1(K),i))
- 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 Rot 1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28
- more details on the various DES functions can be found in your textbooks
- following is a walk-through of a DES encryption calculation taken from:
H Katzan, "The Standard Data Encryption Algorithm", Petrocelli
Books, New York, 1977
DES Modes of Use
- DES encrypts 64-bit blocks of data, using a 56-bit key
- we need some way of specifying how to use it in practise, given that we
usually have an arbitrary amount of information to encrypt
- the way we use a block cipher is called its Mode of Use and four
have been defined for the DES by ANSI in the standard: ANSI X3.106-1983 Modes
of Use)
- modes are either:
- 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
- each mode has its advantages and disadvantages
- []
Limitiations of Various Modes
ECB
- repetitions in message can be reflected in ciphertext
- if aligned with message block
- particularly with data such graphics
- or with messages that change very little, which become a code-book
analysis problem
- weakness is because enciphered message blocks are independent of each other
Davies Fig 4.1 p81
CBC
- use result of one encryption to modify input of next
- hence each ciphertext block is dependent on all message blocks
before it
- thus a change in the message affects the ciphertext block after the change
as well as the original block
Davies Fig 4.5 p85
- to start need an Initial Value (IV) which must be known by both
sender and receiver
- however if IV is sent in the clear, an attacker can change bits of the
first block, and change IV to compensate
- hence either IV must be a fixed value (as in EFTPOS) or it must be sent
encrypted in ECB mode before rest of message
- also at the end of the message, have to handle a possible last short block
- either pad last block (possible with count of pad size), or use some
fiddling to double up last two blocks
- see Davies for examples
CFB
- when data is bit or byte oriented, want to operate on it at that level, so
use a stream mode
- the block cipher is use in encryption mode at both ends,
with input being a feed-back copy of the ciphertext
- can vary the number of bits feed back, trading off efficiency for ease of
use
- again errors propogate for several blocks after the error
Davies Fig 4.7 p88 & Fig 4.8 p89
OFB
- also a stream mode, but intended for use where the error feedback is a
problem, or where the encryptions want to be done before the message is
available
- is superficially similar to CFB, but the feedback is from the output of
the block cipher and is independent of the message, a variation of a Vernam
cipher
- again an IV is needed
- sender and receiver must remain in sync, and some recovery method is
needed to ensure this occurs
- although originally specified with varying m-bit feedback in the
standards, subsequent research has shown that only 64-bit OFB should
ever be used (and this is the most efficient use anyway), see
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
- with many block ciphers there are some keys that should be avoided,
because of reduced cipher complexity
- these keys are such that the same sub-key is generated in more than one
round, and they include:
Weak Keys
- he same sub-key is generated for every round
- DES has 4 weak keys
Semi-Weak Keys
- only two sub-keys are generated on alternate rounds
- DES has 12 of these (in 6 pairs)
Demi-Semi Weak Keys
- have four sub-keys generated
- none of these cause a problem since they are a tiny fraction of all
available keys
- however they MUST be avoided by any key generation program [2]
DES Design Principles
- although the standard for DES is public, the design criteria used are
classified and have yet to be released
- some information is known, and more has been deduced
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.
- will briefly overview the basic results, for more detailed analyses see
the above papers
DES S-Box Design Criteria
- each S-box may be considered as four substitution functions
- these 1-1 functions map inputs 2,3,4,5 onto output bits
- a particular function is selected by bits 1,6
- this provides an autoclave feature
DES Design Criteria
- there were 12 criterion used, resulting in about 1000
- possible S-Boxes, of which the implementers chose 8
- these criteria are CLASSIFIED SECRET
- however, some of them have become known
- The following are design criterion:
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
- The following are said to be caused by design criteria
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
- there are 5 Permutations used in DES:
- IP and IP^(-1) , P, E, PC1, PC2
- their design criteria are CLASSIFIED SECRET
- it has been noted that IP and IP^(-1) and PC1 serve
no cryptological function when DES is used in ECB or CBC modes, since searches
may be done in the space generated after they have been applied
- E, P, and PC2 combined with the S-Boxes must supply the
required dependence of the output bits on the input bits and key bits
(avalanche and completeness effects)
Ciphertext Dependence on Input and Key
- the role of P, E, and PC2 is distribute the outputs of the
S-boxes so that each output bit becomes a function of all the input bits in as
few rounds as possible
- Carl Meyer (in Meyer 1978, or Meyer & Matyas 1982) performed this
analysis on the current DES design
Ciphertext dependence on Plaintext
- define G_(i,j) a 64*64 array which shows the dependence of output
bits X(j) on input bits X(i)
- examine G_(0,j) to determine how fast complete dependence is
achieved
- to build G_(0,1) use the following
L(i) = R(i-1)
R(i) = L(i-1) (+) f( K(i), R(i-1))
- DES P reaches complete dependence after 5 rounds
- []
Ciphertext dependence on Key
- Carl Meyer also performed this analysis
- define F_(i,j) a 64*56 array which shows the dependence of output
bits X(j) on key bits U(i) (after PC1 is used)
- examine F_(0,j) to determine how fast complete dependence is
achieved
- DES PC2 reaches complete dependence after 5 rounds
Key Scheduling and PC2
- Key Schedule
- is a critical component in the design
- must provide different keys for each round otherwise security may be
compromized (see Grossman & Tuckerman 1978)
- current scheme can result in weak keys which give the same, 2 or 4 keys
over the 16 rounds
- Key Schedule and PC-2 Design
- is performed in two 28-bit independent halves
- C-side provides keys to S-boxes 1 to 4
- D-side provides keys to S-boxes 5 to 8
- the rotations are used to present different bits of the key for selection
on successive rounds
- PC-2 selects key-bits and distributes them over the S-box inputs
Possible Techniques for Improving DES
- multiple enciphering with DES
- extending DES to 128-bit data paths and 112-bit keys
- extending the Key Expansion calculation
Triple DES
- DES variant
- standardised in ANSI X9.17 & ISO 8732 and in PEM for key management
- proposed for general EFT standard by ANSI X9
- backwards compatible with many DES schemes
- uses 2 or 3 keys
C = DES_(K1) Bbc{(DES^(-1)_(K2)Bbc{(DES_(K1)(P)))
- no known practical attacks
- brute force search impossible
- meet-in-the-middle attacks need 2^(56) PC pairs per key
- popular current alternative
[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]
Lawrie.Brown@adfa.oz.au / 15-Apr-96