Symmetric Key

Cryptosystems
Module 2
Overview
Model of Symmetric key Cryptosystem
Cryptography
Cryptographic systems are characterized along three
independent dimensions:
1. The type of operations used for transforming
plaintext to ciphertext.(substitution / transposition)
2. Number of keys used (secret-key / public-key)
3. The way in which plaintext is processed (block
cipher / stream cipher)
Block Cipher Principles
Reversible Vs Irreversible encryption

non-singular transformation singular transformation

Ideal Block Cipher (Substitution)
● This is the most general form of block cipher and can be
used to define any reversible mapping between plaintext
and ciphertext.
● Feistel refers to this as the ideal block cipher, because it
allows for the maximum number of possible encryption
mappings from the plaintext block
● But there is a practical problem with the ideal block cipher.
If a small block size, such as n = 4, is used, then the system
is equivalent to a classical substitution cipher vulnerable to
a statistical analysis of the plaintext.
● This weakness is results from the use of a small block size.
So n should be sufficiently large.
● In general, for an n-bit ideal block cipher, the
length of the key defined in this fashion is n * 2n
bits.
○ For a 64-bit block, which is a desirable length to thwart
statistical attacks, the required key length is 64 * 264 =
270 ≈ 1021 bits.
● These problems led to the feistel cipher structure.
Data Encryption Standard
(DES)
Data Encryption Standard (DES)
● Symmetric block cipher
– 56-bit key, 64-bit input block, 64-bit output block
● One of most used encryption systems in world
– Developed in 1977 by NBS/NIST
– Designed by IBM (Lucifer) with input from NSA
– Principles used in other ciphers, e.g. 3DES, IDEA
● Simplified DES (S-DES)
– Cipher using principles of DES
– Developed for education (not real world use)
DES
Encryption
Algorithm
Permutation Tables for DES
Permutation Tables for DES
3: Expansion permutation (E )

4 : Permutation Function (P)

Single Round of DES Algorithm

16
DES Round Structure
Definition of DES S-Boxes
Definition of DES S-Boxes
DES Key Schedule Calculation

20
Table 3.2

DES
Example

Note: DES subkeys are shown as eight 6-bit values in hex format
DES Example
Avalanche Effect
● Aim: small change in key (or plaintext) produces large change in
ciphertext
● Avalanche effect is present in DES (good for security)
● Following examples show the number of bits that change in output
when two different inputs are used, differing by 1 bit
– Plaintext 1: 02468aceeca86420
– Plaintext 2: 12468aceeca86420
– Ciphertext difference: 32 bits
– Key 1: 0f1571c947d9e859
– Key 2: 1f1571c947d9e859
– Ciphertext difference: 30
Table 3.3 Avalanche Effect in DES: Change in Plaintext
Tale 3.4 Avalanche Effect in DES: Change in Key
Table 3.5
Average Time Required for Exhaustive Key Search
Key size
● Although 64 bit initial key, only 56 bits used in encryption
(other 8 for parity check)
● 256 = 7.2 x 1016
– 1977: estimated cost $US20m to build machine to break in
10 hours
– 1998: EFF built machine for $US250k to break in 3 days
– Today: 56 bits considered too short to withstand brute force
attack
● 3DES uses 128-bit keys
Attacks on DES
● Timing Attacks
– Information gained about key/plaintext by observing how long the
implementation takes to decrypt
– No known useful attacks on DES
● Differential Cryptanalysis
([Link]
– Observe how pairs of plaintext blocks evolve
– Break DES in 247 encryptions (compared to 255); but require 247 chosen
plaintexts
● Linear Cryptanalysis
([Link]
– Find linear approximations of the transformations
– Break DES using 243 known plaintexts
DES Algorithm Design
● DES was designed in private; questions about the
motivation of the design
– S-Boxes provide non-linearity: important part
of DES, generally considered to be secure
– S-Boxes provide increased confusion
– Permutation P chosen to increase diffusion
Multiple Encryption with DES
● DES is vulnerable to brute force attack
● Alternative block cipher that makes use of DES
software/equipment/knowledge: encrypt multiple
times with different keys
● Options:
– 1. Double DES: not much better than single DES
– 2. Triple DES (3DES) with 2 keys: brute force 2112
– 3. Triple DES with 3 keys: brute force 2168
Double Encryption

● For DES, 2 56-bit keys, meaning 112-bit key length

● Requires 2111 operations for brute force?
● Meet-in-the-middle attack makes it easier
Triple Encryption
● 2 keys, 112 bits
● 3 keys, 168 bits
● Why E-D-E? To be compatible with single DES:
International Data
Encryption Algorithm (IDEA)
IDEA
● IDEA is a symmetric-key block cipher introduced in 1991.
● Provides secure encryption for digital data in applications like secure
communications, financial transactions, and electronic voting
systems.
● The block size is 64 bits and key size is 128 bits.
● It uses a series of mathematical operations to transform the plaintext
into ciphertext.
● The cipher is highly secure and resistant to various types of attacks,
including differential and linear cryptanalysis.
IDEA (Contd.)
● One of the strengths of IDEA is its efficient implementation in
software and hardware.
● The algorithm is relatively fast and requires only a small amount of
memory and processing power making it a popular choice for use in
embedded systems and other applications where resources are
limited.
● It is replaced by AES in recent years but continues to be used in
legacy systems.
IDEA (Contd.)
● IDEA uses a 128-bit key and operates on 64-bit blocks.
● It encrypts a 64-bit block of plaintext into a 64-bit block of
ciphertext.
● The input plaintext block is divided into four subblocks of 16 bits
each.
● It consists of a series of eight identical transformations, where each
transformation is known as a round, as well as an output
transformation, which is known as a half-round.
● Similar to the 16-bit plaintext block, the ciphertext block is also the
exact same size.
IDEA (Contd.)
● A block cipher operates in round blocks, with part of the encryption
key, known as round key, applied to each round, followed by other
mathematical operations.
● After a certain number of rounds, the ciphertext for that block is
generated.
 Encryption in IDEA
IDEA derives most of its security from multiple interleaved mathematical
operations:
● modular addition
● modular multiplication
● bitwise exclusive-OR (XOR)
Encryption in IDEA (Contd.)
● IDEA encrypts a 64-bit block of plaintext into a 64-bit block of ciphertext
using a 128-bit key.
● The plaintext block is divided into four 16-bit subblocks for each of the eight
complete rounds, namely X1, X2, X3 and X4.
● The 128 bit key is used to produce six 16-bit key subblocks for each of the
encryption rounds, namely Z1, Z2, Z3, Z4, Z5 and Z6.
● For subsequent output transformation also another four 16-bit key subblocks
are required.
● Thus, from a 128-bit key, a total of 52 16-bit subblocks are generated.
● In each complete round, three algebraic operations are performed: bitwise
XOR, addition modulo 216 and multiplication modulo 216+1.
 Encryption in IDEA (Contd.)
A complete round has 14 steps: 8. Add the results of steps 6 and 7.
1. Multiply X1 with Z1. 9. Multiply the result of step 8 with
2. Add X2 to Z2. Z6.
3. Add X3 to Z3. 10. Add the results of steps 7 and 9.
4. Multiply X4 with Z4. 11. Bitwise XOR the results of steps 1
5. Bitwise XOR the results of steps and 9.
1 and 3. 12. Bitwise XOR the results of steps 3
6. Bitwise XOR the results of steps and 9.
2 and 4. 13. Bitwise XOR the results of steps 2
7. Multiply the result of step 5 with and 10.
Z5. 14. Bitwise XOR the results of steps 4
and 10.
Encryption in IDEA (Contd.)
● Six subkeys are used in each of the eight rounds, and the final 4
subkeys are used in the ninth half-round final transformation.
● Swapping occurs for every round until the final complete round
(round 8).
● After eight complete rounds, the final half-round transformation
occurs. The steps involved are the following:
a. Multiply X1 with the first subkey.
b. Add X2 with the second subkey.
c. Add X3 with the third subkey.
d. Multiply X4 with the fourth subkey.
● The concatenation of the four blocks is the encrypted output.
Simplified IDEA (16 bits divided into 4 bit
blocks)
 Example (Simplified IDEA) (4 rounds)
Key: 1101 1100 0110 1111 0011 1111 0101 1. (1001(9) * 1101(13))(mod 17) = 1111(15)
2. (1100(12) + 1100(12))(mod 16) = 1000(8)
1001
3. (1010(10) + 0110(6))(mod 16) = 0000(0)
Plaintext: 1001 1100 1010 1100 4. (1100(12) * 1111(15))(mod 17) = 1010(10)
Ciphertext: 1011 1011 0100 1011 5. (1111(15) ^ 0000(0)) = 1111(15)
6. (1000(8) ^ 1010(10)) = 0010(2)
7. (1111(15) * 0011(3))(mod 17) = 1011(11)
Round 1
8. (0010(2) + 1011(11))(mod 16) = 1101(13)
plaintext: X1 – 1001, X2 – 1100, X3 – 1010, 9. (1101(13) * 1111(15))(mod 17) = 1000(8)
X4 – 1100 10. (1011(11) + 1000(8))(mod 16) = 0011(3)
K1 – 1101, K2 – 1100, K3 – 0110, K4 – 11. (1000(8) ^ 1111(15)) = 0111(7)
12. (1000(8) ^ 0000(0)) = 1000(8)
1111, K5 – 0011, K6 – 1111 13. (0011(3) ^ 1000(8)) = 1011(11)
Here * is modular multiplication 24+1=17 14. (0011(3) ^ 1010(10)) = 1001(9)
+ is modular addition 24 and Round 1 Output: 0111 1011 1000 1001 (Step 12
^ is bitwise XOR and Step 13 results are interchanged)
* denotes a shift of bits
Key Schedule: 6 subkeys of 4 bits
out of the 8 subkeys are used in
each complete round, while 4 are
used in the half-round. So, 4.5
rounds require 28 subkeys. The
given key, ‘K’, directly gives the
first 8 subkeys. By rotating the
main key left by 6 bits between
each group of 8, further groups of
8 subkeys are created, implying
less than one rotation per round
for the key (3 rotations).
After last complete round, the half-round is as follows:

1. X1 * K1
2. X2 + K2
3. X3 + K3
4. X4 * K4

The final output is obtained by concatenating the blocks.

Advanced Encryption Standard
(AES)
 Galois Field / Finite Field for AES
[Link]
3JVG0gJW

Please watch this video to understand GF(28)

for AES.
 Origins of AES
■ DES problems
■ have theoretical attacks that can break it
■ have demonstrated exhaustive key search attacks
■ DES solution
■ Triple-DES – but slow with small blocks
■ US NIST issued call for ciphers in 1997
■ 15 submissions were accepted in Jun 98
■ 5 were shortlisted in Aug-99
■ Rijndael was selected as the AES in Oct-2000
■ issued as FIPS PUB 197 standard in Nov-2001
 AES Requirements
■ private key symmetric block cipher
■ 128-bit data, 128/192/256-bit keys
■ stronger & faster than Triple-DES
■ active life of 20-30 years
■ provide full specification & design details
■ both C & Java implementations
■ NIST have released all submissions & unclassified analyses
 AES Evaluation Criteria
■ initial criteria (Table 5.1):
■ security – effort for practical cryptanalysis
■ Brute-force for 128-bit key is impractical
■ cost – computational efficiency
■ algorithm & implementation characteristics
 AES Evaluation Criteria
■ final criteria:
■ general security – public security analysis for 3 years
■ software & hardware implementation ease
■ Attacks on implementations
■ Timing attacks, power analysis
■ flexibility (in en/decrypt, keying, other factors)
 AES Shortlist
■ after testing and evaluation, shortlist in Aug-99:
■ MARS (IBM) - complex, fast, high security margin
■ RC6 (USA) - v. simple, v. fast, low security margin
■ Rijndael (Belgium) - clean, fast, good security margin
■ Serpent (Euro) - slow, clean, v. high security margin
■ Twofish (USA) - complex, v. fast, high security margin
■ then subject to further analysis & comment
■ saw contrast between algorithms with
■ few complex rounds verses many simple rounds
■ which refined existing ciphers verses new proposals
 Outline
■ AES cipher
■ Overview
■ AES key expansion
■ Substitute bytes transformation
■ Shift row transformation
■ Mix column transformation
■ Add round key transformation
■ Equivalent inverse cipher
 The AES Cipher - Rijndael
■ designed by Rijmen-Daemen in Belgium
■ has 128/192/256 bit keys, 128 bit data
 Rijndael
■ an iterative rather than Feistel cipher
■ Feistel cipher: half of the data block is used to modify the
other half, then swap the halves
■ Rijndael cipher: treats data in 4 groups of 4 bytes, operates
an entire block in every round
■ designed to be:
■ resistant against known attacks
■ speed and code compactness on many CPUs
■ design simplicity
sub.
perm.
sub.
sub.

AES
 AES preview
■ has 9/11/13 full rounds:
■ byte substitution (1 S-box used on every byte)
■ shift rows (permute bytes between groups/columns)
■ mix columns (subs using matrix multipy of groups)
■ add round key (XOR state with key material)
■ initial XOR key material & incomplete last round
■ all operations can be combined into XOR and table lookups -
hence very fast & efficient
 AES data structure
128-bit data block => 16 bytes
input row state output

Round Round
1 n

a byte
A column
of 4 bytes(1 word)
 Add Round Key
■ XOR state with 128-bits of the round key
■ inverse for decryption is identical since XOR is own inverse, just
with correct round key
 Add round key (cont.)
■ processed by column (though effectively a series of byte
operations)

+ +
128-bit key

Original key Expanded key

 AES key expansion
■ takes 128-bit (16-byte) key and expands into array of 44/52/60
32-bit words
■ start by copying key into first 4 words
■ Expanded key: loop creating words that depend on values in
previous & 4 places back
■ in 3 of 4 cases just XOR these together
■ every 4th has S-box + rotate + XOR constant of previous
before XOR together
 AES key expansion (cont.)
w3 = 7F 8D 29 2F
g: 1. Rotate word -
8D 29 2F 7F
Original 2. Substitute byte (S-Box) -
128-bit 5D A5 15 D2
key 3. XOR a round constant -
5C A5 15 D2
S-Box 8D 29 2F 7F => 5D A5 15 D2
 Round constant in g
3. XOR a round constant
5D A5 15 D2 5C A5 15 D2

■ Round constant (RC) word

■ 3 rightmost bytes are 0
■ Leftmost byte follows RC[j]=2∙RC[j-1] over GF(28)
Round j 1 2 3 4 5 6 7 8 9 10
RC[j] 01 02 04 08 10 20 40 80 1B 36

∙2 ∙2
 Substitute bytes transformation
0101
One byte:
1001 0101
1001
S-Box (the only one in AES)
 Construction of S-box
1. Initialize S-box 0 1 2 3 4 5 … E F
0 00 01 02 03 04 05 … 0E 0F
2. Map each entry to its 1 10 11 12 13 14 15 … 1E 1F
multiplicative inverse …
in GF(28) F F0 F1 F2 F3 F4 F5 … FE FF
0 1 2 3 4 5 … E F
3. Apply transformation 0 00 01 …
formula 1
…
9 … 8A
…
F …
 Mathematics behind S-Box
■ Modulo 2 arithmetic

=7C
 Rationale behind S-Box
■ Low correlation between input bits and output bits (check linear
approximation table)
■ No fixed points: S-box(a)=a
■ By the added constant 01100011
■ No opposite fixed points: S-box(a)=a
■ a : the bitwise complement of a
■ S-box is not self-inverse
■ S-box(a) = Inv_S-box(a)
 S-box design criterion
■ Strict avalanche criterion (SAC)
■ Any output bit j of an S-box should change with probability ½
when any single input bit i is inverted for all i, j
■ Bit independence criterion (BIC)
■ Output bits j and k should change independently when any
single input bit i is inverted, for all i, j, k
■ Guaranteed avalanche (GA)
■ For a 1-bit input change, at least r output bits change. (r=2 to 5
provides strong diffusion)
 S-box design approaches
■ Random: use pseudo-random number generator for each entry in
the S-box
■ Suitable for large S-box
■ Random with testing: test results against various criteria
■ Human-made: ex. DES
■ Suitable for small S-box
■ Math-made: ex. AES
■ Key-dependent S-box: Blowfish
Shift Rows
Shift left 1 byte

Shift left 2 bytes

Shift left 3 bytes

 Mix column transformation

column

Input state Output state

column
 Mix Columns (cont.)
■ each column is processed separately
■ each byte is replaced by a value dependent on all 4 bytes in the
column
■ a matrix multiplication in GF(28) using prime poly m(x)
=x8+x4+x3+x+1
 8
Matrix computation in GF(2 )

Example:

Only 1, 2, 3

* Only shift, conditional XOR, and XOR

 8
Matrix computation in GF(2 )

Example:

00010101
10110010
+ 01000110
10100110

01000111
={47}
For 8-bit processor

=>

2∙x =>
can be replaced
by a table lookup
 Implementation Aspects
■ can efficiently implement on 8-bit CPU
■ byte substitution works on bytes using a table of
256 entries
■ shift rows is simple byte shifting
■ add round key works on byte XORs
■ mix columns requires matrix multiply in GF(28)
which works on byte values, can be simplified to
use a table lookup
 AES Decryption
■ AES decryption is not identical to encryption since
steps done in reverse
According to the previous figure, both operations are on
each bytes, and they are commute.

Inverse shift rows then Sub. bytes = Sub. bytes then Inverse shift
rows
 Add round key and inverse mix columns
■ The order can be exchanged
AES Implementation by table look-up and XOR
aij: element of status matrix
SubBytes bij = S[aij] AddRoundKey
ShiftRows

MixColumns
Stream Cipher - RC4
 Stream Ciphers
● Processes message bit by bit (as a stream)
● have a pseudo random keystream
● combined (XOR) with plaintext bit by bit
● randomness of stream key completely destroys
statistically properties in message
○ Ci = Mi XOR StreamKeyi
● but must never reuse stream key
○ otherwise can recover messages
Stream Cipher Structure
 Stream Cipher Properties
● some design considerations are:
○ long period with no repetitions
○ statistically random
○ depends on large enough key
○ large non-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)
● 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 a state array S of numbers: 0..255
● use key to well and truly shuffle S
● 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
● RC4 is theoretically considered as broken but practically
it is not
End of Module 2