Introduction to Information Security

This differs from a block cipher where we operate on blocks of plaintext, not byte-by-byte in a streaming fashion.

Stream Cipher

• Stream ciphers

• Rather than divide bit stream into discrete blocks, as block ciphers do, XOR each bit of your plaintext continuous stream with a bit from a pseudo-random sequence
• At receiver, use same symmetric key, XOR again to extract plaintext

Performance: Stream vs. block ciphers

AMD Opteron, 2.2 GHz (Linux)

	Cipher	Block/key size	Throughput [MB/s]
Stream	RC4		126
	Salsa20/12		643
	Sosemanuk		727
Block	3DES	64/168	13
	AES128	128/128	109

History of DES

• 1970s: Horst Feistel designs Lucifer at IBM

key = 128 bits, block = 128 bits

• 1973: NBS asks for block cipher proposals.

IBM submits variant of Lucifer.

• 1976: NBS adopts DES as federal standard

key = 56 bits, block = 64 bits

• 1997: DES broken by exhaustive search
• 2000: NIST adopts Rijndael as AES to replace DES. AES currently widely deployed in banking, commerce and Web

DES: core idea – Feistel network

Given one-way functions

Goal: build invertible function

R1
L1
R2
L2
Rd
Ld
Rd-1
Ld-1
fd
⊕
n-bits
R0
n-bits
L0
f1
⊕
f2
⊕
• • •
input
output
In symbols:

Feistel network - inverse

Claim: Feistel function F is invertible

Proof: construct inverse

Ri+1
Li+1
Ri
Li
fi+1
⊕
inverse
Ri
Li
Ri+1
Li+1
fi+1
⊕

Decryption circuit

Ld-1
Rd-1
Ld-2
Rd-2

• Inversion is basically the same circuit, with f1, …, fd applied in reverse order
• General method for building invertible functions (block ciphers) from arbitrary functions.
• Used in many block ciphers … but not AES

Rd
Ld
fd
⊕
n-bits
n-bits
fd-1
⊕
• • •
R0
L0
L1
R1
f1
⊕

DES: 16 round Feistel network

key expansion
key k1
key k
• • •
64 bits
64 bits
IP-1
IP
R1
L1
R2
L2
R16
L16
R15
L15
f16
R0
L0
f1
⊕
f2
• • •
⊕
⊕
16 round Feistel network
56 bits
48 bits
key k2
key k16
To invert, use keys in reverse order

The function F(ki, x)

x
32 bits
Ex
x’
48 bits
ki
48 bits
⊕
48 bits
P
32 bits
y
6
4
S1
6
4
S2
6
4
S3
6
4
S4
6
4
S5
6
4
S6
6
4
S7
6
4
S8
32 bits
S-box: function {0,1}6 ⟶ {0,1}4, implemented as lookup table.

The S-boxes

e.g., 011011 ⟶ 1001

The S-boxes

"We sent the S-boxes off to Washington. They came back and were all different.“

--- Alan Konheim (one of the designers of DES)

1990: (Re-)Discovery of differential cryptanalysis

DES S-boxes resistant to differential cryptanalysis!

-> Both IBM and NSA likely knew of attacks, but they were classified

Computer Systems Security

Modern cryptographic algorithms

Modern Ciphers

• We design one relatively simple scrambling method (called a round) and repeat it many times
• Think of each round as a rotor on the Enigma
• One round may be easy to break, but when you put them all together it becomes very hard
• Almost all ciphers follow one of two structures
• SPN (Substitution Permutation Network)
• Feistel Network
• These describe the basic structure of a round

One SPN Round

Input to the round
Output from the round
First, the input is XORed with the round subkey
Second, the input is split into pieces (usually of one byte) and put through a substitution
Finally, the pieces are swapped around
And the output from this round becomes the input to the next round