Transcript Symmetric-Key Cryptography - Sensorweb Research Laboratory

Network Security
Symmetric Encryption and Message
Confidentiality
WenZhan Song
Cryptography and Network Security
1
Some Basic Terminology
 Plaintext - original message
 Ciphertext - coded message
 Cipher - algorithm for transforming plaintext to ciphertext
 Key - info used in cipher known only to sender/receiver
 Encipher (encrypt) - converting plaintext to ciphertext
 Decipher (decrypt) - recovering ciphertext from plaintext
 Cryptography - study of encryption principles/methods
 Cryptanalysis (code breaking) - study of principles/methods of
deciphering ciphertext without knowing key
 Cryptology - field of both cryptography and cryptanalysis
Cryptography and Network Security
3
Requirements
 There are two requirements for secure use of
symmetric encryption:


A strong encryption algorithm
Sender and receiver must have obtained copies of the secret
key in a secure fashion and must keep the key secure
 The security of symmetric encryption depends
on the secrecy of the key, not the secrecy of
the algorithm



This makes it feasible for widespread use
Manufacturers can and have developed low-cost chip
implementations of data encryption algorithms
These chips are widely available and incorporated into a number of
products
Cryptography
Cryptographic
systems are
generically
classified along
three
independent
dimensions:
• The type of operations used for transforming plaintext to
ciphertext
• Substitution
• Each element in the plaintext is mapped into another
element
• Transposition
• Elements in the plaintext are rearranged
• Fundamental requirement is that no information be lost
• Product systems
• Involve multiple stages of substitutions and transpositions
• The number of keys used
• Referred to as symmetric, single-key, secret-key, or
conventional encryption if both sender and receiver use the
same key
• Referred to as asymmetric, two-key, or public-key
encryption if the sender and receiver each use a different
key
• The way in which the plaintext is processed
• Block cipher processes the input one block of elements at a
time, producing an output block for each input block
• Stream cipher processes the input elements continuously,
producing output one element at a time, as it goes along
Table 2.1
Types of Attacks on Encrypted Messages
cryptanalysis
 An encryption scheme is computationally
secure if the ciphertext generated by the
scheme meets one or both of the following
criteria:
 The
cost of breaking the cipher exceeds the value of the
encrypted information
 The time required to break the cipher exceeds the useful
lifetime of the information
Brute Force attack
 Involves trying every possible key until an
intelligible translation of the ciphertext into
plaintext is obtained
 On average, half of all possible keys must be
tried to achieve success
 Unless known plaintext is provided, the analyst
must be able to recognize plaintext as
plaintext
 To supplement the brute-force approach


Some degree of knowledge about the expected plaintext is
needed
Some means of automatically distinguishing plaintext from
garble is also needed
Two types of symmetric ciphers
 Block ciphers
 Break
plaintext message in equal-size blocks
 Encrypt each block as a unit
 Stream ciphers
 Encrypt
one bit at time
Network Security
Cryptography and Network Security
Block Ciphers
Cryptography and Network Security
10
Block Ciphers
 The message is broken into blocks,
Each of which is then encrypted
 (Like a substitution on very big characters - 64-bits or
more)

Cryptography and Network Security
11
Substitution and Permutation
 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 substitutiontransposition product cipher
 S-P networks are based on the two primitive
cryptographic operations we have seen before
Cryptography and Network Security
12
Substitution
 A binary word is replaced by some other
binary word
 The whole substitution function forms the
key
 If use n bit words,

The key space is 2n!
 Can also think of this as a large lookup
table, with n address lines (hence 2n
addresses), each n bits wide being the
output value
 Will call them s-boxesCryptography and Network Security
13
Cont.
Cryptography and Network Security
14
Permutation
 A binary word has its bits reordered
(permuted)
 The re-ordering forms the key
 If use n bit words,
 The
key space is n! (Less secure than substitution)
 This is equivalent to a wire-crossing in
practice

(Though is much harder to do in software)
 Will call these p-boxes
Cryptography and Network Security
15
Cont.
Cryptography and Network Security
16
Substitution-permutation
Network
 Shannon combined these two primitives
 He called these mixing transformations
 A special form of product ciphers where

S-boxes
 Provide confusion of input bits

P-boxes
 Provide diffusion across s-box inputs
Cryptography and Network Security
17
Confusion and Diffusion
 Confusion

A technique that seeks to make the relationship
between the statistics of the ciphertext and the value of
the encryption keys as complex as possible. Cipher uses
key and plaintext.
 Diffusion

A technique that seeks to obscure the statistical
structure of the plaintext by spreading out the influence
of each individual plaintext digit over many ciphertext
digits.
Cryptography and Network Security
18
Desired Effect
 Avalanche effect
A characteristic of an encryption algorithm in which a
small change in the plaintext gives rise to a large
change in the ciphertext
 Best: changing one input bit results in changes of
approx half the output bits

 Completeness effect

where each output bit is a complex function of all the
input bits
Cryptography and Network Security
19
Practical Substitutionpermutation Networks
 In practice 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

Cryptography and Network Security
20
Feistel Cipher
 Invented by Horst Feistel,

working at IBM Thomas J Watson research labs in
early 70's,
 The idea is to partition the input block into
two halves, l(i-1) and r(i-1),

use only r(i-1) in each round i (part) of the cipher
 The function f incorporates one stage of
the S-P network, controlled by part of the
key k(i) known as the ith subkey
Cryptography and Network Security
21
Cont.
Cryptography and Network Security
22
Cont.
 This can be described functionally as:
L(i) = R(i-1)
 R(i) = L(i-1)  f(k(i), R(i-1))

 This can easily be reversed as seen in the
above diagram, working backwards through
the rounds
 In practice link a number of these stages
together (typically 16 rounds) to form the
full cipher
Cryptography and Network Security
23
Feistel Cipher Design
Elements
• Larger block
sizes mean
greater security
but reduced
encryption/decry
ption speed
Block size
• Greater
complexity
generally means
greater resistance
to cryptanalysis
Round function
Key size
• Larger key size
means greater
security but may
decrease
encryption/decrypti
on speed
Subkey generation
algorithm
• The essence of a
symmetric block
cipher is that a
single round offers
inadequate security
but that multiple
rounds offer
increasing security
• Greater
complexity in
this algorithm
should lead to
greater difficulty
of cryptanalysis
Number of rounds
Fast software
encryption/decryp
tion
• In many cases, encryption is
embedded in applications or
utility functions in such a way
as to preclude a hardware
implementation; accordingly,
the seed of execution of the
algorithm becomes a concern
• If the algorithm can be
concisely and clearly
explained, it is easier to
analyze that algorithm
for cryptanalytic
vulnerabilities and
therefore develop a
higher level of assurance
as to its strength
Ease of analysis
Data Encryption Standard
 Adopted in 1977 by the National Bureau of
Standards, now the National Institute of
Standards and Technology
 Data are encrypted in 64-bit blocks using a
56-bit key
 The same algorithm is used for decryption.
 Subject to much controversy
Cryptography and Network Security
25
History
 IBM LUCIFER 60’s

Uses 128 bits key
 Proposal for NBS, 1973
 Adopted by NBS, 1977
 Uses
only 56 bits key
 Possible brute force attack

Design of S-boxes was classified
 Hidden weak points in in S-Boxes?

Wiener (93) claim to be able to build a machine at
$100,00 and break DES in 1.5 days
Cryptography and Network Security
26
DES
 DES encrypts 64-bit blocks of data, using
a 56-bit key
 the basic process consists of:
an initial permutation (IP)
 16 rounds of a complex key dependent calculation f
 a final permutation, being the inverse of IP
 Function f can be described as
 L(i) = R(i-1)
 R(i) = L(i-1)  P(S( E(R(i-1))  K(i) ))

Cryptography and Network Security
27
DES
Cryptography and Network Security
28
Initial and Final Permutations
 Inverse Permutations
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
Cryptography and Network Security
29
Function f
Cryptography and Network Security
30
Expansion Table
 Expands the 32 bit data to 48 bits

Result(i)=input( array(i))
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
Cryptography and Network Security
31
S-Boxes
 S-Box is a fixed 4 by 16 array
 Given 6-bits B=b1b2b3b4b5b6,
Row r=b1b6
 Column c=b2b3b4b5
 S(B)=S(r,c) written in binary of length 4

See examples at https://en.wikipedia.org/wiki/S-box
Cryptography and Network Security
32
Example
 S-Box S1
14 4
13 1
0
15 7
4
1
2
15 11
8
3
10 6
12 5
0
7
9
5
3
8
3
10 5
0
4
14 2
13 1
10 6
14 8
13 6
2
11
15 12 9
7
4
1
7
5
14 10 0
15 12 8
2
9
11
12 11
9
3
6
Cryptography and Network Security
13
33
Permutation Table
 The permutation after each round
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
Cryptography and Network Security
34
Subkey Generation
 Given a 64 bits key (with parity-check bit)
Discard the parity-check bits
 Permute the remaining bits using fixed table P1
 Let C0D0 be the result (total 56 bits)

 Let Ci =Shifti(Ci-1); Di =Shifti(Di-1) and Ki be
another permutation P2 of CiDi (total 56
bits)
Where cyclic shift one position left if i=1,2,9,16
 Else cyclic shift two positions left

Cryptography and Network Security
35
Permutation Tables
57 49 41
33 25 17
9
14
17
11
28 15
24 1
5
6
21
10
4
26 8
1
58 50 42 34 26 18
3
10
2
59 51
23 19
12
19
11
3
16
7
27 20 13
41
52 31
37 47 55
45 33 48
43 35 27
60 52 44 36
63 55 47 39 31
23 15
2
7
62 54 47 38 30 22
30 40 51
14
6
61
53 45 37 29
44 49 39 56 34 53
21
13
5
28 20 12
46 42 50 36 29 32
4
Permutation table P1
Permutation table P2
Cryptography and Network Security
36
DES in Practice
 DEC (Digital Equipment Corp. 1992) built a
chip with 50k transistors
Encrypt at the rate of 1G/second
 Clock rate 250 Mhz
 Cost about $300

 Applications

ATM transactions (encrypting PIN and so on)
Animation: http://kathrynneugent.com/animation.html
Cryptography and Network Security
37
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:
Cryptography and Network Security
38
Cont.
 Weak keys
The 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
Cryptography and Network Security
39
Cont.
 None of these causes a problem since they
are a tiny fraction of all available keys
 However they MUST be avoided by any key
generation program
Cryptography and Network Security
40
DES Attacks
1998:
The EFF's US$250,000
DES cracking machine
contained 1,536 custom chips
and could brute force a DES key in a
matter of days —
the photo shows a DES Cracker
circuit board fitted
with several Deep Crack chips.
Cryptography and Network Security
41
DES Attacks:
The COPACOBANA
machine, built for
US$10,000 by the
Universities of Bochum and
Kiel, contains 120 low-cost
FPGAs and can perform an
exhaustive key search on
DES in 9 days on average.
The photo shows the
backplane of the machine
with the FPGAs
Cryptography and Network Security
42
Attack Faster than Brute Force
 Differential cryptanalysis
 was discovered in the late 1980s by Eli Biham and Adi Shamir,
although it was known earlier to both IBM and the NSA and kept
secret. To break the full 16 rounds, differential cryptanalysis
requires 247 chosen plaintexts. DES was designed to be resistant to
DC.
 Linear cryptanalysis

was discovered by Mitsuru Matsui, and needs 243 known plaintexts
(Matsui, 1993); the method was implemented (Matsui, 1994), and
was the first experimental cryptanalysis of DES to be reported.
There is no evidence that DES was tailored to be resistant to this
type of attack.
Cryptography and Network Security
43
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
Cryptography and Network Security
44
Double DES?
 Using two encryption stages and two keys
C=Ek2(Ek1(P))
 P=Dk1(Dk2(C))

 It is proved that there is no key k3 such
that

C=Ek2(Ek1(P))=Ek3(P)
 But Meet-in-the-middle attack
Cryptography and Network Security
45
Meet-in-the-Middle Attack
 Assume C=Ek2(Ek1(P))
 Given the plaintext P and ciphertext C
 Encrypt P using all possible keys k1
 Decrypt C using all possible keys k2
Check the result with the encrypted plaintext lists
 If found match, they test the found keys again for
another plaintext and ciphertext pair
 If it turns correct, then find the keys
 Otherwise keep decrypting C

Cryptography and Network Security
46
Triple DES
 DES variant
 Standardized 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
Cryptography and Network Security
47
3DES guidelines
 FIPS 46-3 includes the following guidelines
for 3DES:
3DES is the FIPS-approved symmetric encryption
algorithm of choice
 The original DES, which uses a single 56-bit key, is
permitted under the standard for legacy systems only;
new procurements should support 3DES
 Government organizations with legacy DES systems
are encouraged to transition to 3DES
 It is anticipated that 3DES and the Advanced
Encryption Standard (AES) will coexist as FIPSapproved algorithms, allowing for a gradual transition
to AES

Cont.
 No known practical attacks
 Brute force search impossible (very hard)
 Meet-in-the-middle attacks need 256
Plaintext-Ciphertext pairs per key
 Popular current alternative
Cryptography and Network Security
50
IDEA:
 Developed by James Massey & Xuejia Lai
at ETH originally in Zurich in 1990, then
called IPES:

X Lai, J L Massey, "A Proposal for a New Block
Encryption Standard"
 in Advances in Cryptology - Eurocrypt '90, Lecture
Notes in Computer Science, vol 473, pp 389-404,

X Lai, J L Massey, S Murphy, "Markov Ciphers and
Differential Cryptanalysis"
 in Advances in Cryptology - Eurocrypt '91, Lecture
Notes in Computer Science, vol 547, pp 17-38,

name changed to IDEA in 1992
Cryptography and Network Security
51
Basic Features
 Encrypts 64-bit blocks using a 128-bit key
 Based on mixing operations from different
(incompatible) algebraic groups
XOR, + mod 2^(16) , X mod (2^(16) +1)
 On 16-bit sub-blocks, with no permutations used

 IDEA is patented in Europe & US, however
non-commercial use is freely permitted
used in the public domain PGP (with agreement)
 currently no attack against IDEA is known

 Seem secure against differential cryptanalysis, brute
force
Cryptography and Network Security
52
Operations
 Operations

XOR, Addition mod 216, multiplication mod 216 +1
 Why these special mod for addition, multiplication

They do not satisfy the distributive law and the
associative law
 http://www.mathsisfun.com/associative-commutativedistributive.html
Cryptography and Network Security
53
MA: multiplication/addition
 Multiplication/addition
Basic block to provide diffusion
 Input of MA

 Two sub-blocks derived from 4 input sub-blocks, 4
sub-keys
 Two other sub-keys

Output
 Two sub-blocks

Needs four operations
 Four operations are the minimum to provide full
diffusion
Cryptography and Network Security
54
Overview
Cryptography and Network Security
55
Cont.
 IDEA encryption works as follows:
 Use 8-rounds
 The 64-bit data is divided into: X1 , X2 , X3 , X4
 Each round
 The sub-blocks are added (2,3), multiplied (1,4) with subkeys
 The results are XORed [1,3] and [2,4] to 2 sub-blocks
 The XOR results set as input of MA structure,
 It outputs two subblocks
 Results are then XORed with 2,4 and 1,3 subblocks respectively
 The second and third sub-blocks are swapped

Finally new sub-keys are combined with the sub-blocks
Cryptography and Network Security
56
Sub-Keys
 Total need 52=6*8+4 sub-keys
First are directly from key in order
 Left shift of 25 bits, and then next 8 sub-keys
 Each sub-key is a sub-block of the original key

 Decryption
Much more complicated
 It needs the inverse of the encryption key

 For addition, multiplication
Cryptography and Network Security
57
Decryption
 The process of decryption is essentially
the same as encryption
But with different selection of sub-keys
 Basic Operations

 K1.1^(-1 ) is the multiplicative inverse mod 2^(16) +1
 -K1.2 is the additive inverse mod 2^(16)
 The original operations are:
 (+) bit-by-bit XOR
 + additional mod 2^(16) of 16-bit integers
 * multiplication mod 2^(16) +1 (where 0 means 2^(16) )
Cryptography and Network Security
58
Decryption Sub-Keys
Round
Encryption Keys
1 K1.1 K1.2 K1.3 K1.4 K1.5 K1.6
K8.5 K8.6
2 K2.1 K2.2 K2.3 K2.4 K2.5 K2.6
K7.5 K7.6
3 K3.1 K3.2 K3.3 K3.4 K3.5 K3.6
K6.5 K6.6
4 K4.1 K4.2 K4.3 K4.4 K4.5 K4.6
K5.5 K5.6
5 K5.1 K5.2 K5.3 K5.4 K5.5 K5.6
K4.5 K4.6
6 K6.1 K6.2 K6.3 K6.4 K6.5 K6.6
K3.5 K3.6
7 K7.1 K7.2 K7.3 K7.4 K7.5 K7.6
K2.5 K2.6
8 K8.1 K8.2 K8.3 K8.4 K8.5 K8.6
K1.5 K1.6 Output K9.1 K9.2 K9.3 K9.4
Decryption Keys
K9.1-1 -K9.2 -K9.3 K9.4-1
K8.1-1 -K8.3 -K8.2 K8.4-1
K7.1-1 -K7.3 -K7.2 K7.4-1
K6.1-1 -K6.3 -K6.2 K6.4-1
K5.1-1 -K5.3 -K5.2 K5.4-1
K4.1-1 -K4.3 -K4.2 K4.4-1
K3.1-1 -K3.3 -K3.2 K3.4-1
K2.1-1 -K2.3 -K2.2 K2.4-1
K1.1-1 -K1.2 -K1.3 K1.4-1
Cryptography and Network Security
59
Important Feature
 The size of the sub-block

Need 216+1 be prime number
 To compute the inverse for each possible subkey

So sub-block size 8 is also possible
 28+1=257 is prime number
Cryptography and Network Security
60
CAST-128
 By Carlisle Adams, Stafford Tavares
Defined in RFC 2144
 Use key size varying from 40 to 128 bits
 Structure of Feistel network
 16 rounds on 64-bits data block
 Four primitive operations

 Addition, subtraction (mod 232)
 Bitwise exclusive-OR
 Left-circular rotation
Cryptography and Network Security
61
Skipjack and Clipper
 Skipjack
used in Clipper escrowed encryption scheme(US govt)
 Skipjack is a block cipher, 64-bit data
 hardware only implementation
 80-bit key (escrowed in 2 halves)
 32 round
 all design details and descriptions are classified
 has been very considerable debate over its use
 attack by Matt Blaze (ATT) on the LEAF component of
the Clipper protocol for secure phone communications

Cryptography and Network Security
62
Blowfish Scheme
 Developed by Bruce Schneier
Fast, compact, simple and variably secure
 Two basic operations: addition, XOR
 Key ranges from 32 bits to 448 bits
 Similar to Feistel scheme
 The sub-key and s-boxes are complicated
 So not suitable when key changes often
 Function g is very simple, unlike DES

Cryptography and Network Security
63
RC5
 Developed by R. Rivest
Suitable for hardware or software
 Fast, simple, low memory, data-dependent rotations
 Adaptable to processors of different word length

 A family of algorithms determined by word length,
number of rounds, size of secret key

Decryption and encryption are not the same
 With little variations

Primitive operations
 Addition, XOR, left circular rotation
Cryptography and Network Security
64
Characteristics
 Key features of advanced sym block cipher
Variable key length
 Mixed operators
 Data dependent rotation
 Key dependent rotation
 Key dependent S-boxes
 Lengthy key schedule algorithm
 Variable function F
 Variable of number of rounds
 Operation on both halved data each round

Cryptography and Network Security
65
AES
 Advanced Encryption Standard (Rijndael)
 key size and the block size may be chosen to be any of 128, 192, or 256
bits (later only key, block fixed 128)
 Rijndael has a variable number of rounds. Not counting an extra round
performed at the end of encipherment with one step omitted, the
number of rounds in Rijndael is:
 9 if both the block and the key are 128 bits long.
 11 if either the block or the key is 192 bits long, and neither of
them is longer than that.
 13 if either the block or the key is 256 bits long.

Three big blocks
 first perform an Add Round Key step (XORing a subkey with the
block) by itself,
 then regular rounds noted above,
 the final round with the Mix Column step
Cryptography and Network Security
66
Advanced Encryption
Standard
Cryptography and Network Security
67
Origins
 clear a replacement for DES was needed
 have theoretical attacks that can break it
 have demonstrated exhaustive key search attacks
 can use Triple-DES – but slow, has small
blocks
 US NIST issued call for ciphers in 1997
 15 candidates accepted in Jun 98
 5 were shortlisted in Aug-99
 Rijndael was selected as the AES in Oct2000
 issued as FIPS PUB 197 standard in Nov2001
The Finalists



MARS

IBM

RSA Laboratories

Joan Daemen (Proton World International) and
Vincent Rijmen (Katholieke Universiteit Leuven)
RC6
Rijndael


Serpent




Ross Anderson (University of Cambridge),
Eli Biham (Technion), and
Lars Knudsen (University of California San Diego)
Twofish




Bruce Schneier, John Kelsey, and Niels Ferguson (Counterpane, Inc.),
Doug Whiting (Hi/fn, Inc.),
David Wagner (University of California Berkeley), and
Chris Hall (Princeton University)
Wrote the book
on crypto
Cryptography and Network Security
69
Evaluation Criteria
(in order of importance)
 Security

Resistance to cryptanalysis, soundness of math,
randomness of output, etc.
 Cost


Computational efficiency (speed)
Memory requirements
 Algorithm / Implementation Characteristics

Flexibility, hardware and software suitability, algorithm
simplicity
Cryptography and Network Security
70
Results
Cryptography and Network Security
71
Results
Cryptography and Network Security
72
The AES Cipher - Rijndael
 designed by Rijmen-Daemen in Belgium
 has 128/192/256 bit keys, 128 bit data
 an iterative rather than feistel cipher
 processes data as block of 4 columns of 4 bytes
 operates on entire data block in every round
 designed to be:
 resistant against known attacks
 speed and code compactness on many CPUs
 design simplicity
AES
Encryption
Process
AES Structure
 data block of 4 columns of 4 bytes is state
 key is expanded to array of words
 has 9/11/13 rounds in which state undergoes:





byte substitution (1 S-box used on every byte)
shift rows (permute bytes between groups/columns)
mix columns (subs using matrix multiply of groups)
add round key (XOR state with key material)
view as alternating XOR key & scramble data bytes
 initial XOR key material & incomplete last
round
 with fast XOR & table lookup implementation
Convert to State Array
Input block:
0
0
4
8
12
1
5
9
13
1 2 2 6 310 414 5
3
7
11 15
S0,0 S0,1 S0,2 S0,3
=
6
7
8
S1,0 S1,1 S1,2 S1,3
9 10 11 12 13 14 15
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
Cryptography and Network Security
76
AES
Structure
SubBytes
 Replace each byte in the state array with
its corresponding value from the S-Box
00 44 88 CC
11
55 99 DD
55
22 66 AA EE
33 77 BB FF
Cryptography and Network Security
79
ShiftRows
 Last three rows are cyclically shifted
S0,0 S0,1 S0,2 S0,3
S1,0
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2
S3,0 S3,1 S3,2 S3,3
Cryptography and Network Security
80
MixColumns
 Apply MixColumn transformation to each
column
S’0,c = ({02}  SMixColumns()
0,c)  ({03}  S1,c)  S2,c  S3,c
S0,0
S0,1
S’0,1
S S’S1,c =SS0,c  ({02}  S1,c)  ({03}  S2,c
S’ ) SS
’ 3,cS’
0,1
0,2
0,3
0,0
0,1
0,2
S’0,3
S1,0 S
S1,1
S’1,0S’
S’
1,1S’S1,2=SS
1,3  S
1,1 )S’1,2 S’1,3

({02}

S
)

({03}
S1,1
2,c
0,c
1,c
2,c
3,c
S2,0 S2,1 S2,2 S2,3
S’2,0 S’2,1 S’2,2 S’2,3
S3,0 S3,1 S3,2 S3,3
S’3,0 S’3,1 S’3,2 S’3,3
S2,1S’
3,c
S3,1
= ({03}  S0,c)  S1,c  S2,c  ({02} S’S2,13,c
S’3,1
Cryptography and Network Security
81
AddRoundKey
 XOR each byte of the round key with its
corresponding byte in the state array
XOR
S0,1
S0,0 S0,1 S0,2 S0,3
S1,0 S
S1,1
1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S2,1
S3,0 S3,1 S3,2 S3,3
S3,1
R0,1
R0,0 R0,1 R0,2 R0,3
1,1 R1,2 R1,3
R1,0 R
R1,1
R2,0 R2,1 R2,2 R2,3
R2,1
R3,0 R3,1 R3,2 R3,3
R3,1
S’0,1
S’0,0 S’0,1 S’0,2 S’0,3
S’1,0S’
S’1,1
1,1 S’1,2 S’1,3
S’2,0 S’2,1 S’2,2 S’2,3
S’2,1
S’3,0 S’3,1 S’3,2 S’3,3
S’3,1
Cryptography and Network Security
82
Table 2.2
Average Time Required for Exhaustive Key Search
Cryptography and Network Security
Stream Ciphers
Cryptography and Network Security
84
Stream ciphers
 Stream ciphers
 The most famous: Vernam cipher
 Invented by Vernam, ( AT&T, in 1917)
 Process the message bit by bit (as a stream)
 different from the one-time pad– some call same
 Simply add bits of message to random key bits
 Examples
 A well-known stream cipher is RC4;
 others include: A5/1, A5/2, Chameleon, FISH, Helix. ISAAC,
Panama, Pike, SEAL, SOBER, SOBER-128 and WAKE.
 Usage
 Stream ciphers are used in applications where plaintext comes in
quantities of unknowable length - for example, a secure wireless
connection
Cryptography and Network Security
85
Simplest Stream Cipher
Cryptography and Network Security
86
Pros and Cons
 Drawbacks
Need as many key bits as message, difficult in practice
 (ie distribute on a mag-tape or CDROM)

 Strength
 Is
unconditionally secure provided key is truly random
Cryptography and Network Security
87
Stream Cipher design
considerations
 The encryption sequence should have a large
period

The longer the period of repeat, the more difficult it will be to do
cryptanalysis
 The keystream should approximate the properties
of a true random number stream as close as
possible

The more random-appearing the keystream is, the more
randomized the ciphertext is, making cryptanalysis more difficult
 The pseudorandom number generator is
conditioned on the value of the input key


To guard against brute-force attacks, the key needs to be
sufficiently long
With current technology, a key length of at least 128 bits is
desirable
Key Generation
 Why not to 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 practice to find a good pseudo-random
function that is cryptographically strong
 This is still an area of much research
Cryptography and Network Security
89
Transposition Methods
 Permutation of plaintext
 Example

Write in a square in row, then read in column order
specified by the key
 Enhance: double or triple transposition

Can reapply the encryption on ciphertext
Cryptography and Network Security
90
Stream Cipher Structure
Stream Cipher Properties
 some design considerations are:
long period with no repetitions
 statistically random
 depends on large enough key
 large linear complexity

 properly designed, can be as secure as a
block cipher with same size key
 but usually simpler & faster
RC4
 a proprietary cipher owned by RSA DSI
 another Ron Rivest design, simple but
effective
 variable key size, byte-oriented stream
cipher
 widely used (web SSL/TLS, wireless
WEP/WPA)
 key forms random permutation of all 8-bit
values
 uses that permutation to scramble input
info processed a byte at a time
RC4 Key Schedule
 starts with an array S of numbers: 0..255
 use key to well and truly shuffle
 S forms internal state of the cipher
for i = 0 to 255 do
S[i] = i
T[i] = K[i mod keylen])
j = 0
for i = 0 to 255 do
j = (j + S[i] + T[i]) (mod 256)
swap (S[i], S[j])
RC4 Encryption
 encryption continues shuffling array values
 sum of shuffled pair selects "stream key"
value from permutation
 XOR S[t] with next byte of message to
en/decrypt
i = j = 0
for each message byte Mi
i = (i + 1) (mod 256)
j = (j + S[i]) (mod 256)
swap(S[i], S[j])
t = (S[i] + S[j]) (mod 256)
Ci = Mi XOR S[t]
RC4 Overview
RC4 Security
 claimed secure against known attacks

have some analyses, none practical
 result is very non-linear
 since RC4 is a stream cipher, must never
reuse a key
 have a concern with WEP, but due to key
handling rather than RC4 itself
Cryptography and Network Security
Ciper Block Modes of Operation
Cryptography and Network Security
98
Electronic Codebook Mode (ECB)
 Plaintext is handled b bits at a time and each block
of plaintext is encrypted using the same key
 The term “codebook” is used because, for a
given key, there is a unique ciphertext for every
b-bit block of plaintext

One can imagine a gigantic codebook in which there is an entry for
every possible b-bit plaintext pattern showing its corresponding
ciphertext
 With ECB, if the same b-bit block of plaintext
appears more than once in the message, it always
produces the same ciphertext


Because of this, for lengthy messages, the ECB mode may not be
secure
If the message is highly structured, it may be possible for a
cryptanalyst to exploit these regularities
Advantages of CTR mode
 Hardware efficiency
 Encryption/decryption can be done in parallel on multiple blocks of plaintext or ciphertext
 Throughput is only limited by the amount of parallelism that is achieved
 Software efficiency
 Because of the opportunities for parallel execution, processors that support parallel features
can be effectively utilized
 Preprocessing

The execution of the underlying encryption algorithm does not depend on input of the plaintext or
ciphertext --- when the plaintext or ciphertext input is presented, the only computation is a series of
XORs, greatly enhancing throughput
 Random access

The ith block of plaintext or ciphertext can be processed in random-access fashion

It can be shown that CTR is at least as secure as the other modes discussed in this section

Requires only the implementation of the encryption algorithm and not the decryption algorithm
 Provable security
 Simplicity
Cryptography and Network Security
Pseudo-random Number
Cryptography and Network Security
104
Random Numbers
 many uses of random numbers in
cryptography
nonces in authentication protocols to prevent replay
 session keys
 public key generation
 keystream for a one-time pad or stream ciper

 in all cases its critical that these values be
statistically random, uniform distribution, independent
 unpredictability of future values from previous values

 true random numbers provide this
 care needed with generated random numbers
Random & Pseudorandom Number
Generators
Pseudorandom Number
Generators (PRNGs)
 often use deterministic algorithmic
techniques to create “random numbers”
although are not truly random
 can pass many tests of “randomness”

 known as “pseudorandom numbers”
 created by “Pseudorandom Number
Generators (PRNGs)”
Randomness Definition
 Chaitin-Kolmogorov randomness (also called
algorithmic randomness)

a string of bits is random if and only if it is shorter than
any computer program that can produce that string
 this basically means that random strings are those
that cannot be compressed.
 Statistical Randomness
 A numeric sequence is said to be statistically random
when it contains no recognizable patterns or
regularities;
 sequences such as the results of an ideal die roll, or
the digits of Pi (as far as we can tell) exhibit
statistical randomness.
Cryptography and Network Security
108
Inherent non-randomness
 Because any PRNG run on a deterministic computer
(contrast quantum computer) is deterministic, its
output will inevitably have certain properties that
a true random sequence would not exhibit.

guaranteed periodicity—it is certain that if the generator uses only
a fixed amount of memory then, given a sufficient number of
iterations, the generator will revisit the same internal state twice,
after which it will repeat forever. A generator that isn't periodic can
be designed, but its memory requirements would grow as it ran. In
addition, a PRNG can be started from an arbitrary starting point, or
seed state, and will always produce an identical sequence from that
point on.
Cryptography and Network Security
109
cont

In practice, many PRNGs exhibit artifacts which can
cause them to fail statistically significant tests. These
include, but are certainly not limited to:
 Shorter than expected periods for some seed states
(not full period)
 Poor dimensional distribution
 Successive values are not independent
 Some bits may be 'more random' than others
 Lack of uniformity
Cryptography and Network Security
110
Pseudo-random Bit Generator
 Several applications
Key generation
 Some encryption algorithms, or one-time pad

 Let l>k be integers
f: Z2k Z2l computable in poly-time
 Then f called (k,l)-pseudo-random bit generator
 The input s0 Z2k is called the seed
 Output f(s0) is called the pseudo-random string
 Function
Cryptography and Network Security
111
Desired Properties
 Three important properties:

Unbiased (uniform distribution):
 All values of whatever sample size is collected are
equiprobable

Unpredictable (independence):
 It is impossible to predict what the next output will
be, given all the previous outputs, but not the internal
"hidden" state.

Irreproducible:
 Two of the same generators, given the same starting
conditions, will produce different outputs.
Cryptography and Network Security
112
Desired Properties
 Usually when a person says

A "good" pseudo-random number generator
 they mean it is unbiased.

A "true" PRNG
 they usually mean it's irreproducible

A "cryptographically strong" PRNG
 they mean it's unpredictable

Very rarely they mean it's all threes
Cryptography and Network Security
113
More Properties
 Long period

The generator should be of long period
 Fast computation

The generator should be reasonably fast
 Security
The generator should be secure
 What is security level of PRNG?

Cryptography and Network Security
114
Security
 A PRNG suitable for cryptographic applications is
called a cryptographically secure PRNG (CSPRNG).


Its output should not only pass all statistical tests for randomness
but satisfy some additional cryptographic requirements.
Used in many aspects of cryptography require random numbers,
for example:




Key generation
Nonces
Salts in certain signature schemes, (ECDSA, RSASSA-PSS).
One-time pads
Cryptography and Network Security
115
CSPRNG
 CSPRNG requirements fall into two groups:
 their statistical properties are good (passing tests of randomness),
 they hold up well in case of attack, even when (part of) their secrets are
revealed.
 A CSPRNG should satisfy the 'next-bit test'.
 Given the first l bits of a random sequence there is no polynomial-time
algorithm that can predict the next bit with probability of success
significantly higher than 1/2.
 It has been proven that a generator passing the next-bit test will pass all
other polynomial-time statistical tests for randomness.
 should withstand state compromise extensions.
 That is, in the unfortunate case that part or all of the state has been
revealed (or guessed correctly), it should be impossible to reconstruct
the stream of random numbers prior to the incident. Also if there is an
input of entropy, it should be infeasible to use knowledge of the state to
predict future conditions of the state.
Cryptography and Network Security
116
Example
 the CSPRNG being considered produces
output by computing some function of the
next digit of pi (ie, 3.1415...),
 it may well be random as pi appears to be a random
sequence.
 However, this does not satisfy the next-bit test, and
 thus is not cryptographically secure.
 There exists an algorithm that will predict the next bit.
Cryptography and Network Security
117
Design
 divide designs of CSPRNGs into classes:
those based on block ciphers;
 those based upon hard mathematical problems, and
 special-purpose designs.

Cryptography and Network Security
118
Designs based on cryptographic
primitives
 Designs based on cryptographic primitives
 A secure block cipher can also be converted into a CSPRNG by
running it in counter mode.
 This is done by choosing an arbitrary key and encrypting a zero, then
encrypting a 1, then encrypting a 2, etc. The counter can also be
started at an arbitrary number other than zero. Obviously, the period
will be 2n for an n-bit block cipher; equally obviously, the initial
values (i.e. key and 'plaintext') must not become known to an attacker
lest, however good this CSPRNG construction might be otherwise, all
security be lost.
 A cryptographically secure hash of a counter might
also act as a good CSPRNG in some cases.

it is necessary that the initial value of this counter is random and secret.
If the counter is a bignum, then CSPRNG could have an infinite period.
Cryptography and Network Security
119
DES Based Generator
 ANSI X9.17 PRNG (used by PGP,..)

Inputs: two pseudo-random inputs
 one is a 64-bit representation of date and time
 The other is 64-bit seed values
Keys: three 3DES encryptions using same keys
 Output:

 a 64-bit pseudorandom number and
 A 64-bit seed value for next-round use
Cryptography and Network Security
120
ANSI X9.17
K1,K2
DT
EDE
EDE
Si+1
Si
EDE
Ri
Cryptography and Network Security
121
Linear Congruential Generator
 Protocol
Let M be an integer and a, b less than M
 Let k be number of bits of M
 Integer l is between k+1 and M-1
 Let s0 be a seed less than M
 Define si=asi-1+b mod M
 Then the ith random bit is si mod 2
 It is not proved to be secure

Cryptography and Network Security
122
Parameter Setting
 Not all a, b are good and m should be large
 For example, m is a large prime number
 For fast computation, usually m=231-1

And b is set to 0 often
 For this m, there are less than 100
integers a
It generates all numbers less than m
 The generated sequences appear to be random

 One such a=7516807

Used in IBM 360 family of computers
Cryptography and Network Security
123
RSA Generator
 Protocol
Let p, q be two k/2 bits primes and define n=pq
 Integer b: gcd(b, (n))=1
 Public: n, b; Private p,q
 A seed s0 with k bits
 Sequence si+1=sib mod n
 Then the ith random bit is si mod 2
 It is proved to be secure!

Cryptography and Network Security
124
BBS Generator
 Blum-Blum-Shub Generator
 Let p, q be two k/2 bits primes and define n=pq
 Here p=q=3 mod 4
 this guarantees that each quadratic residue has one
square root which is also a quadratic residue
 gcd(φ(p-1),
φ(q-1)) should be small
 this makes the cycle length large.
Let QR(n) be all quadratic residues modulo n
 Public: n; Private p,q
 A seed s0 with k bits from QR(n)
 Sequence si+1=si2 mod n
 Then the ith random bit is si mod 2

Cryptography and Network Security
125
Cont on BBS
 Provably “secure”
When the primes are chosen appropriately,
 and O(log log n) bits of each Si are output,
 then in the limit as n grows large, distinguishing the
output bits from random will be at least as difficult as
factoring n.

 However,

it's theoretically possible that a fast algorithm for
factoring will someday be found, so BBS is not yet
guaranteed to be secure.
Cryptography and Network Security
126
Discrete Logarithm Generator
 Protocol
Let p be a k-bit prime,
 Let  be primitive element modulo p
 A seed s0 is any non-zero integer less than p
 Define si+1 =  si mod p
 Then the ith random bit is

 1 if si is larger than p/2
 0 if si is less than p/2
Cryptography and Network Security
127
Standards
 A number of designs of CSPRNGs have
been standardized. They can be found in:
FIPS 186-2
 ANSI X9.17-1985 Appendix C
 ANSI X9.31-1998 Appendix A.2.4
 ANSI X9.62-1998 Annex A.4

Cryptography and Network Security
128