CSCE 465 Lecture 11

« previous | Tuesday, February 19, 2013 | next »

Lecture Slides

test next week

Secret Key Cryptography

• Intro
• Feistel Cipher
• DES
• AES

Same key used for both encryption and decryption

Applications

Confidentiality

• Transmission over insecure channel
• Secure storage on insecure volumes

Integrity

• Message Integrity Codes (MIC)

Authentication

• Challenge-Response protocol: ask Alice to encrypt a known string of text, check that encrypted text is original

Block Encryption

Converts one input plaintext block of fixed size $k$ bits to an output ciphertext bolck of $k$ bits.

• Large $k$: faster encryption, but harder data recovery
• Small $k$: easier data recovery, but slower encryption

Key Sizes

• 40 bits were adequate in 70s
• 56 used by DES adequate in 80s
• 128 adequate for now

If computers increase in power by 40% per year, need roughly 5 more bits per decade to stay "sufficiently" hard to break.

Notation

Notation	Meaning
$X\oplus Y$	Exclusive Or
$X\mid Y$	Concatenation
$K\{m\}$	Application of Encryption Alogrithm

Principles of Cipher design:

1. confusion: make output as complex (non-linear) as possible
2. diffusion: spread influence of each input bit across many output bits

Use multiple, alternating permutations (diffusion) and substitutions (confusion): S → P → S → P → ...

Basic Form of modern block ciphers

Plaintext Block	Key
Preprocessing	subkey generation
$n$ rounds of encryption	subkey 1 … $n$
Postprocessing
Ciphertext block

Feistel Cipher

Very influential template for designing a block cipher

Major benefit: can do encryption and decryption with the same hardware (same function)

Examples: DES, RC5

One Round of Feistel

To encrypt:

1. Break input block $i$ into left and right halves $L_{i}$ and $R_{i}$
2. Copy $R_{i}$ to create output half-block $L_{i+1}$
3. Half block $R_{i}$ and key $K_{i}$ are "scrambled" by function $f$
4. XOR result with input half-block $L_{i}$ to create output half-block $R_{i+1}$

${\begin{aligned}L_{i+1}&=R_{i}\\R_{i+1}&=f(R_{i},k_{i})\oplus L_{i}\end{aligned}}$

— OR —

${\begin{aligned}{\text{input}}&=L_{i}~\mid ~R_{i}\\{\text{output}}&=R_{i}~\mid ~(f(R_{i},k_{i})\oplus L_{i})\end{aligned}}$

To decrypt, reverse the steps (by reversing the order of the keys)

1. Break input block $i$ into left and right halves $L_{i+1}$ and $R_{i+1}$
2. Copy $L_{i+1}$ back into $R_{i}$
3. Use $L_{i+1}$ and key $K_{i}$ as input to function $f$
4. XOR result with input half-block $R_{i+1}$ to create output half-block $L_{i}$

Post-processing: swap outputs

Parameters:

• Block size
• Key Size
• number of rounds
• subkey generation algorithm
• scrambling function $f$

DES

Standardized in 1976 by NBS

• Proposed by IBM
• A Feistel cipher

Criteria (official)

• Provide high security
• security in key, not algorithm
• not pantented
• exportable

Unofficial:

• slow to compute on software, but fast on hardware
• breakable by the NSA

64-bit block size 16 rounds of encryption 64 bit key length (actually 56, since every 8^th bit is a parity checksum bit

1. Initial permutation based on table (does not improve security, but makes this a feistel cipher)
2. Throw out 8 parity bits of key
3. Perform a circular left-shift of each part of 56-bit key, permute and discard to get 48 bit subkey
4. $f$-function is an expansion of 32-bit half-block to 48 bits, XOR with subkey, substitution (shrink to 32 bits), and permutation
5. Final permutation reverse of table (does not improve security, but makes this a feistel cipher)

Substitution is a lookup table: for 6-bit chunk b of 48-bit expanded part, b[0] | b[5] denote row, b[1] | b[2] | b[3] | b[4] denote column. output is table value o[0] | o[1] | o[2] | o[3]

Analysis

• Were the particular details well-chosen?
• Tables built by flipping coins?
• Built-in exploits by the designer?

Don't know

Number of rounds should be large enough to make advanced attacks as expensive as exhaustive search for key.

S-Box (substitution) is only non-linear part of DES

• Each row should have unique permutation of four bits

Avalanche Effect:

• Small change in either plaintext or key should produce big change in ciphertext
• Output bit should be inverted with probability 0.5 if any input bit is changed
• DES Example: 0x000000000000000 and 0x800000000000000 differ by 1 bit. key: 0x16B24621C181C32; Differ by 34 bits out of 64
• There are 4 weak keys such that K{K{m}} = m: /(0{28}|1{28})(0{28}|1{28})/ (RegExp)
• Semiweak keys such that K₁{K₂{m}} = m

Cryptanalysis

Differential cryptanalysis: Exploits differences between two different plaintext blocks; provides insight into possible key values Linear cryptanalysis: exploits similarities between two different plaintext blocks;

AES

Selected from an open competition by NSA (won by Rijndael /rhine-dall/)

Similarities to DES:

• rounds
• round keys
• alternate permutation+substitution

Differences:

• not a Feistel cipher
• Block-size = 128 bits
• Key sizes may be 128, 192, or 256 bits
• Secure, well-justified, fast