CS计算机代考程序代写 algorithm chain Symmetric Key Cryptography

Symmetric Key Cryptography
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapters 3.1–3.3)
Ryszard Janicki
Symmetric Key Cryptography 1/28

Symmetric Key Crypto
Symmetric Key Cryptography
9
 Stream cipher  generalize one-time pad
o Except that key is relatively short
o Key is stretched into a long keystream
o Keystream is used just like a one-time pad Stream Ciphers
 Block cipher  generalized codebook o Block cipher key determines a codebook
 Once upon a time, not so very long ago… sotrEeaachmkceyipyhielrds awdeirfefetrehnet kcoindgebofokcrypto
 TooEdmapyl,oynsobtoaths “pcopnfuulasirona”sanbdlo“cdkiffcuispihone”rs
 We’ll discuss two stream ciphers:
Part 1  Cryptography 3
 A5/1
o Based on shift registers
o Used in GSM mobile phone system
 RC4
o Based on a changing lookup table o Used many places
Part 1  Cryptography Ryszard Janicki
Symmetric Key Cryptogra4p1hy 2/28

A5/1: Shift Registers
A5/1 uses 3 shift registers:
X: 19 bits (x0,x1,…,x18) Y: 22 bits (y0,y1,…,x21) Z: 23 bits (z0,z1,…,x22) Note that 19 + 22 + 23 = 64
The A5/1 key K is 64 bits
The key is used as the initial values in the three registers X , Y
and Z
After these three registers are filled with the key we are ready
to generate the keystream
At each iteration we calculate ONE bit of the keystream. If a plaintext has the length of k bits, we need k iterations to create the entire keystream.
Ryszard Janicki
Symmetric Key Cryptography 3/28

A5/1: ‘majority function’
For all x,y,z ∈ {0,1}, we define maj(x,y,z) (‘majority’) as follows:
􏰻 0 if the number of 0’s in {x,y,z} is at least 2 maj(x,y,z) = 1 if the number of 1’s in {x,y,z} is at least 2
For example: maj(0, 1, 0) = 0, maj(1, 1, 0) = 1, maj(0,0,0) = 0,maj(1,1,1) = 1, etc.
Ryszard Janicki
Symmetric Key Cryptography 4/28

A5/1: Calculation of One Keystream Bit
At each iteration: m = maj(x8, y10, z10) If x8 = m then the register X steps and
t =x13 ⊕x16 ⊕x17 ⊕x18
xi = xi−1 for i = 18,17,…,1 x0 = t
If y10 = m then the register Y steps and t = y20 ⊕ y21
yi = yi−1 for i = 21,20,…,1 y0 = t
If z10 = m then the register Z steps and
t =z7 ⊕z20 ⊕z21 ⊕z22
zi = zi−1 for i = 22,21,…,1 z0 = t
Keystream bit s is s = x18 ⊕ y21 ⊕ z22
If the length of plaintext is k we have to do k iterations. The output registers X,Y and Z calculated at the k iteration are the input registers for the k + 1 iteration.
Ryszard Janicki
Symmetric Key Cryptography 5/28

A5/1
A5/1: example and Final Comment
X1 Y1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
110011001100110011000
Z
11
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1

 In this example, m = maj(x8, y10, z10) = maj(1,0,1) = 1  Register X steps, Y does not step, and Z steps
 Keystream bit is XOR of right bits of registers  Here, keystream bit will be 0  1  0 = 1
Part 1  Cryptography 45 Shift register cryptography very efficient in hardware.
Often, slow if implemented in software (due to shift by one bit).


Ryszard Janicki
Symmetric Key Cryptography 6/28

RC4
 A self-modifying lookup table
 Table always contains a permutation of the
byte values 0,1,…,255
 Initialize the permutation using key
 At each step, RC4 does the following
o Swaps elements in current lookup table
o Selects a keystream byte from table
 Each step of RC4 produces a byte
o Efficient in software
 Each step of A5/1 produces only a bit
o Efficient in hardware
Part 1  Cryptography
47
RC4
Ryszard Janicki
Symmetric Key Cryptography 7/28

RC4: Initialization
 S[] is permutation of 0,1,…,255  key[] contains N bytes of key
for i = 0 to 255
S[i] = i
K[i] = key[i (mod N)]
next i
j=0
for i = 0 to 255
j = (j + S[i] + K[i]) mod 256
swap(S[i], S[j]) next i
i=j=0
Part 1  Cryptography 48
Ryszard Janicki
Symmetric Key Cryptography 8/28
RC4 Initialization

RC4: Keystream
RC4 Keystream
 At each step, swap elements in table and select keystream byte
i = (i + 1) mod 256
j = (j + S[i]) mod 256 swap(S[i], S[j])
t = (S[i] + S[j]) mod 256 keystreamByte = S[t]
 Use keystream bytes like a one-time pad
 Note: first 256 bytes should be discarded
o Otherwise, related key attack exists
Part 1  Cryptography 49
Ryszard Janicki
Symmetric Key Cryptography 9/28

Stream Ciphers: Final Comment
Stream Ciphers
 Stream ciphers were popular in the past o Efficient in hardware
o Speed was needed to keep up with voice, etc.
o Today, processors are fast, so software-based crypto is usually more than fast enough
 Future of stream ciphers?
o Shamir declared “the death of stream ciphers” o May be greatly exaggerated…
Part 1  Cryptography 50
Ryszard Janicki
Symmetric Key Cryptography 10/28

(Iterated) Block Cipher
(Iterated) Block Cipher
Plaintext and ciphertext consist of fixed-sized blocks
Ciphertext obtained from plaintext by iterating a round function
Input to round function consists of key and output of previous round
Usually implemented in software
Part 1  Cryptography 52
Ryszard Janicki
Symmetric Key Cryptography 11/28

Feistel Cipher: Encryption
Feistel Cipher: Encryption
 Feistel cipher is a type of block cipher o Not a specific block cipher
 Split plaintext block into left and right halves: P = (L0, R0)
 For each round i = 1, 2, …, n, compute Li = Ri1
Ri = Li1  F(Ri1, Ki)
where F is round function and Ki is subkey
 Ciphertext: C = (Ln, Rn)
Part 1  Cryptography 53
Ryszard Janicki
Symmetric Key Cryptography 12/28

Feistel Cipher: Decryption
Feistel Cipher: Decryption
 Start with ciphertext C = (Ln, Rn)
 For each round i = n, n1, …, 1, compute
Ri1 = Li
Li1 = Ri  F(Ri1, Ki)
where F is round function and Ki is subkey
 Plaintext: P = (L0, R0)
 Decryption works for any function F o But only secure for certain functions F
Part 1  Cryptography
Ryszard Janicki
54
Symmetric Key Cryptography 13/28

DES Numerology
DES: Data Encryption Standard
 DES is a Feistel cipher with… o 64 bit block length
o 56 bit key length
o 16 rounds
o 48 bits of key used each round (subkey)
 Round function is simple (for block cipher)
 Security depends heavily on “S-boxes” o Each S-box maps 6 bits to 4 bits
Part 1  Cryptography
Ryszard Janicki
Symmetric Key Cryptography 14/28
56

One Round of DES
32
expand
48
Ki
48
32 32

32
28
28
shift
key
32
One Round
of DES

48
S-boxes
28
28
28 28
compress
32
L
R
P box
key
shift
L
R
Part 1  Cryptography
DES round function F can be written as:
57
F(Ri−1,Ki) = P-box(S-boxes(Expand(Ri−1) ⊕ Ki)).
Ryszard Janicki
Symmetric Key Cryptography 15/28

DES Expansion Permutation: Function Expand(R)
DES Expansion Permutation
Input 32 bits
0 1 2 3 4 5 6 7 8 9101112131415
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Output 48 bits
31 0 1 2 3 4 3 4 5 6 7 8
7 8 9101112111213141516 15 16 17 18 19 20 19 20 21 22 23 24 2324252627282728293031 0
Part 1  Cryptography
Ryszard Janicki
Symmetric Key Cryptography 16/28
58

DES S-boxes: Function S-boxes(. . .)
DES S-box
8 “substitution boxes” or S-boxes Each S-box maps 6 bits to 4 bits Here is S-box number 1
input bits (0,5)
 input bits (1,2,3,4)
| 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
———————————————————————————— 00 | 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111 01 | 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 10 | 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 11 | 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101
Part 1  Cryptography 59
Ryszard Janicki
Symmetric Key Cryptography 17/28

DES P-box: Function P-box(. . .)
DES P-box
Input 32 bits
0 1 2 3 4 5 6 7 8 9101112131415
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Output 32 bits
15 6192028112716 0142225 41730 9
1 723133126 2 8181229 52110 324
Part 1  Cryptography Ryszard Janicki
Symmetric Key Cryptography 18/28 60

DES Subkeys. Schedule for Ki
For rounds i = 1, 2, …, 16
Let LK = (LK circular shift left by ri )
Let RK = (RK circular shift left by ri ) Left half of subkey Ki is of LK bits
13 16 10 23 0 4 2 27 14 5 20 9
22 18 11 3 25 7 15 6 26 19 12 1 Right half of subkey Ki is RK bits
12 23 2 8 18 26 1 11 22 16 4 19 15 20 10 27 5 24 17 13 21 7 0 3
For rounds 1, 2, 9 and 16 the shift ri is 1, and in all other rounds ri is 2
Bits 8,17,21,24 of LK omitted each round Bits 6,9,14,25 of RK omitted each round Ki has 48 bits (LK plus RK have 56 total)
Ryszard Janicki
Symmetric Key Cryptography 19/28

DES: Final Steps and Its Security
An initial permutation before round 1
Halves are swapped after last round
A final permutation (inverse of initial perm) applied to (R16, L16)
None of this serves any security purpose
Security depends heavily on S-boxes
Everything else in DES is linear
40+ years of intense analysis has revealed no back door Attacks, essentially exhaustive key search (56 bits)
Ryszard Janicki
Symmetric Key Cryptography 20/28

Block Cipher Notation
Block Cipher Notation
 P = plaintext block
 C = ciphertext block
 Encrypt P with key K to get ciphertext C o C = E(P, K)
 Decrypt C with key K to get plaintext P o P = D(C, K)
Note: P = D(E(P, K), K) and C = E(D(C, K), K)
o But P  D(E(P, K1), K2) and C  E(D(C, K1), K2) when K1  K2
Part 1  Cryptography 66
Ryszard Janicki
Symmetric Key Cryptography 21/28

Triple DES
Today, 56 bit DES key is too small Exhaustive key search is feasible
But DES is everywhere, so what to do? Triple DES or 3DES (112 bit key)
C = E(D(E(P,K1),K2),K1)
P = D(E(D(C,K1),K2),K1)
Why Encrypt-Decrypt-Encrypt with 2 keys?
Backward compatible: E(D(E(P,K),K),K) = E(P,K)
And 112 is a lot of bits
Why not C = E(E(P,K),K) instead?
Trick question – still just 56 bit key Why not C = E(E(P,K1),K2) instead? A (semi-practical) known plaintext attack
Pre-compute table of E(P,K1) for every possible key K1 (resulting table has 256 entries)
Then for each possible K2 compute D(C,K2) until a match in table is found
When match is found, have E(P,K1) = D(C,K2)
Result gives us keys: C = E(E(P,K1),K2)
Ryszard Janicki
Symmetric Key Cryptography 22/28

AES: Advanced Encryption Standard
Replacement for DES
AES competition (late 90’s)
NSA openly involved
Transparent selection process
Many strong algorithms proposed Rijndael Algorithm ultimately selected
Iterated block cipher (like DES)
Not a Feistelcipher (unlike DES)
Block size:128 bits (others in Rijndael) Key length:128, 192 or 256 bits
10 to 14 rounds (depends on key length) Each round uses 4 functions (3 “layers”)
ByteSub (nonlinear layer) ShiftRow (linear mixing layer) MixColumn (nonlinear layer) AddRoundKey (key addition layer)
General Idea: Simulation of long random key as well as possible!
More details in the textbook.
Ryszard Janicki
Symmetric Key Cryptography 23/28

A Few Other Block Ciphers
IDEA (64-bit blocks, 128-bit key, uses mixed-mode arithmetic)
Blowfish (64-bit blocks, key is variable length, up to 448 bits, almost a Feistel cipher)
RC6 (uses data dependent rotations, so algorithm details depend on plaintext)
TEA: Tiny Encryption Algorithm (64 bit block, 128 bit key, number of rounds is a variable)
General Idea: Simulation of long random key as well as possible!
More details in the textbook.
Ryszard Janicki
Symmetric Key Cryptography 24/28

Block Cipher Modes
Using a stream cipher is easy – you generate a keystream that is the same length as the plaintext (or ciphertext) and XOR.
Using a block cipher is also easy, provided that you have exactly one block to encrypt.
But how should multiple blocks, say, P0, P1, P2, . . ., be encrypted with a block cipher?
Many modes – we discuss briefly 3 most popular.
Electronic Codebook (ECB) mode: encrypts each block independently, most obvious approach, but easiest to break.
Cipher Block Chaining (CBC) mode: chains the blocks together, more secure than ECB, virtually no extra work.
Counter Mode (CTR) : block ciphers act like a stream cipher, popular for random access.
Ryszard Janicki
Symmetric Key Cryptography 25/28

ECB Mode
Notation: C = E(P,K), given plaintext P0,P1,…,Pm,… Most obvious way to use a block cipher:
Encrypt
C0 = E(P0,K) C1 = E(P1,K) C2 = E(P2,K)…
Decrypt
P0 = D(C0,K) P1 = D(C1,K) P2 = D(C2,K)…
For fixed key K, this is “electronic” version of a codebook cipher (without additive), with a different codebook for each key.
ECB weakness:
NotethatPi =Pj ⇐⇒ Ci =Cj.
An attacker most likely will notice that Ci = Cj , so he will also know that Pi = Pj
An attacker may know Pi , this may help to find K , or parts of it, see the textbook.
Ryszard Janicki
Symmetric Key Cryptography 26/28

CBC Mode
Blocks are “chained” together
A random initialization vector, or IV , is required to initialize CBC mode
IVis random, but not secret
Encrypt
Decrypt
C0 =E(IV ⊕P0,K)
C1 =E(C0 ⊕P1,K)
C2=E(C1⊕P2,K)… P2=C1⊕D(C2,K)…
P0 =IV ⊕D(C0,K) P1 =C0 ⊕D(C1,K)
Analogous to classic codebook with additive
Identical plaintext blocks yield different ciphertext blocks – this is very good!
But what about errors in transmission?
IfC1 isgarbledto,say,GthenP1̸=C0⊕D(G,K), P2 ̸=G⊕D(C2,K),
ButP3 =C2⊕D(C3,K),P4 =C3⊕D(C4,K),… Automatically recovers from errors!
Ryszard Janicki
Symmetric Key Cryptography 27/28

Counter Mode (CTR)
CTR is popular for random access Use block cipher like a stream cipher
Encrypt
C0 =P0 ⊕E(IV,K)
C1 =P1 ⊕E(IV +1,K)
C2 =P2 ⊕E(IV +2,K)…
Decrypt
P0 =C0 ⊕E(IV,K)
P1 =C1 ⊕E(IV +1,K)
P2 =C2 ⊕E(IV +2,K)…
Ryszard Janicki
Symmetric Key Cryptography 28/28