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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} : faster encryption, but harder data recovery
Small Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \oplus Y}	Exclusive Or
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \mid Y}	Concatenation
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K\{m\}}	Application of Encryption Alogrithm

Principles of Cipher design:

confusion: make output as complex (non-linear) as possible
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
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} rounds of encryption	subkey 1 … Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Break input block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} into left and right halves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i}
Copy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}}
Half block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i} and key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} are "scrambled" by function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
XOR result with input half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} L_{i+1} &= R_i \\ R_{i+1} &= f(R_i, k_i) \oplus L_i \end{align}}

— OR —

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \text{input} &= L_i ~\mid~ R_i \\ \text{output} &= R_i ~\mid~ (f(R_i, k_i) \oplus L_i) \end{align}}

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

Break input block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} into left and right halves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}}
Copy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} back into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i}
Use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} and key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} as input to function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
XOR result with input half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i}

Post-processing: swap outputs

Parameters:

Block size
Key Size
number of rounds
subkey generation algorithm
scrambling function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Initial permutation based on table (does not improve security, but makes this a feistel cipher)
Throw out 8 parity bits of key
Perform a circular left-shift of each part of 56-bit key, permute and discard to get 48 bit subkey
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} -function is an expansion of 32-bit half-block to 48 bits, XOR with subkey, substitution (shrink to 32 bits), and permutation
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