CSCE 465 Lecture 12

« previous | Thursday, February 21, 2013 | next »

End Exam 1 content

Lecture Slides

AES

Encryption

128-bit (16 bytes) key 10 Rounds of encryption using 10 128-bit generated keys

Each plaintext block of 16 bytes is arranged as 4×4 square

0	4	8	12
1	5	9	13
2	6	10	14
3	7	11	15

Apply S-box function to each byte of state (i.e. 16 substitutions)

Row 0 unchanged Row 1 shifts left 1 Row 2 shifts left 2 Row 3 shifts left 3

Apply MixColumn function to each column of state (last round omits this step)

Decryption

Run cipher in reverse order

Recall AES is not a Feistel Cipher, so it cannot use the same "inverse" function

Inverse Ops:

• XOR is its own reverse
• inverse of S-box is inverse table
• Rotation in opposite direction
• Inverse of MixColumn is inverse table

Run cipher in forward direction, but use inverse operations and apply round keys in reverse order

Decryption takes more memory and cycles than encryption

• only partially reuses hardware.

Assessment

• Speed: about 16 clock cycles per byte on 32-bit CPU
• 200 MB on a PC without special hardware
• No known successful attacks on full 10–14 rounds AES (best attacks work around 7–9 rounds)
• Clean design
• Brute force takes 4e21 times more effort than DES

Attacks

Differential

reduced due to high number of rounds

Linear

S-box and MixColumns designed to frustrate this

Side Channel

attacks on implementation and not on algorithm

Timing: measure time taken to perform operation; some operation/operand combos are fast/slow; provides clues about internal data values

Power Attacks: measure power consumed to perform operations; changing 1 bit uses less power than changing many bits

Summary

Secret Key Cryptography is

1. good quality
2. faster to compute than public key
3. most widely used cryptography

DES

• DES was strong enough back in the day (i.e. outdated)
• Repeated runs Triple-DES (with 3 keys) is better

AES

• even better (stronger and faster)
• supports variable key sizes

Modes of Operation

Most ciphers work on blocks of fixed (small) size

Long messages broken into many blocks

Modes of Operation:

1. Electronic Code Book (ECB)
2. Cipher Block Chaining (CBC)
3. Output Feedback (OFB)
4. Cipher Feedback (CFB)
5. Counter (CTR)

3–5 are stream ciphers; they don't need to wait for all bytes in a block in order to encrypt it.

Only 1–3 will be covered in class.

Issues

• Information Leakage: Does block chaining mode reveal information about plaintext blocks?
• Ciphertext manipulation: Can attacker modify/rearrangeciphertext block(s) that will produce a predicted/desired change in decrypted plaintext? (Note: Assume structure of plaintext is known)
• Parallel/Sequential: Can blocks be encrypted/decrypted in parallel?
• Error Propagation: If there is an error in a block, will that error affect other blocks?

Electronic Code Book (ECD)

Most intuitive way:

1. Break message into blocks
2. use same key to encrypt each block
3. and then concatenated to form ciphertext.

Similarly, same key used to independently decrypt each block

• Information can leak: two identical blocks will have he same ciphertext
• Ciphertext can be manipulated for profit: moving blocks around
• Parallel is possible since each block is handled independently
• Errors do not propagate

Cipher Block Chaining (CBC)

One of most common modes used

1. Message broken into blocks
2. First block XOR-ed with an initialization vector of numbers
3. ciphertext output of each block is XOR-ed with successive plaintext block before being encrypted
4. Same key used for each block encryption

Note chaining dependency: each ciphertext block depends on all preceding plaintext blocks

Initialization Vector (IV)

• may not be kept secret
• if randomly generated, it may be transmitted with ciphertext
• if IV is incrementally generated, the receiver may be able to predict it
• Different IV may be used for each time message is transmitted
• Changing either key or IV will change entire ciphertext output

Decryption happens reverse:

1. ciphertext broken into blocks
2. first block is decrypted and XOR-ed with IV
3. Each block is decrypted and XOR-ed with the previous ciphertext block

• No info leakage
• Encryption cannot be parallelized
• Can be exploited: flipping a bit in the ciphertext will flip the corresponding bit in the plaintext
• Errors only propogate to two message blocks (corresponding and adjacent)

Output Feedback Mode (OFB)

Message plaintext blocks XOR-ed with a Pseudo-random number generator (One-time pad)

Pseudo-random number generator is the encryption of an IV; output used for XOR and as input to next encryption for next block's random number

to decrypt, just XOR Ciphertext with generated pad again.

No decryption function required: XOR is its own inverse. As a side-effect, IV must be different every time, otherwise a single plaintext/ciphertext pair will reveal the pad.

• No info leakage
• If pad is pre-generated, it can be parallelized
• Can still do bit-flip trick to exploit
• Errors do not propagate

Exam Review

• Multi-choice
• T/F

Handwritten "cheat-sheet"