Block ciphers, DES and AES Flashcards
What are 2 widely deployed block ciphers?
AES and DES
Wha are block ciphers?
Symmetric key
Each block of plaintext is encrypted with the same key
Each block has a fixed size, often between 64 and 256 bits.
Used in certain configurations called modes of operation.
What is the encryption technique Confusion?
Use substitution to make the relationship between the key and the ciphertext as complex as possible.
What is the encryption technique diffusion?
Involves transformations that dissipate the statistical properties of the plaintext across ciphertext.
What is a product cipher?
Cryptosystem
Encryption function is formed by applying several sub-encryption functions.
Most block ciphers are compositions of function f_i, where each f_i has a different key K_i
C = E(P, K) = f_i(…,( f2 ( f1 (P,K1), K2)…) Ki)
What are iterated ciphers?
A class of product ciphers
Encryption process divided into r similar rounds
sub-encryptions are all the same round function g
Each round-key Ki is derived from an overall master key K..
What is a round function?
The sub-encryption function used in iterate ciphers
What is a key schedule in iterate ciphers?
The process that derives sub-keys from a master key
Give an example of how a ciphertext is derived through r rounds of an iterate cipher
W0 = P
W1 = g(w0, k1)
W2 = g(w1, k2)
…
Wr = g(w_(r-1), k_r)
C = Wr
Give an example of how a ciphertext is decrypted through r rounds of an iterate cipher
Wr = C
W_(r-1) = g^-1 ( Wr, Kr)
W_(r-2) = g^-1 ( Wr-1, Kr-1)
…
W0 = g^-1 ( W1, K1)
P = W0
What does an iterate cipher need to have to be able to decrypt?
A round function g that have an inverse g^-1
with g^-1(g(W,ki), ki) = W for all Ki and blocks W
What type of block cipher is DES (Data Encryption Standard)
Feistel ciphers
What type of block cipher is AES (Advanced Encryption Standard)
Substitution-Permutation Networks (SPNs)
What is a Feistel cipher?
Iteration cipher
The round function swaps the two halves of the block and forms a new right hand half.
Why is the Feistel cipher process often called a Feistel network?
The process can be seen as a network which the two halves of the plaintext block travel through
Describe feistel encryption
Plaintext: P = Wo
Split plaintext into two halves: W0 = (L0, R0)
For each round r, perform:
Li = Ri-1
Ri = Li-1 XOR f(Rw-1, K1)
C = Wr
C = (Lr, Rr)
Describe feistel decryption
C = (Lr, Rr)
For each round r, perform:
Li-1 = Ri XOR f(Li, Ki)
Ri-1 = Li
P = (L0, R0)
Does every round function allow decryption when using Feistel cipher?
Yes, Feistel don’t use an inverse, so any function f allows decryption.
Because of this, the choice of f is critical for security
What is substitution-permutation network (SPNs)?
Iterated cipher
Block length n must allow for each block to be split into m sub-blocks of length l.
n = lm
2 permutations are defined
Permutation P_S operates on sub-blocks of size r bits
P_s: {0, 1}^r -> {0, 1}^r
The permutation P_s is normally called an S-box (substitution box)
Permutation P_p swaps the inputs from {1, …, n}. This is similar to the transposition cipher
Pp: {1, 2, …, n} -> {1, 2, …, n}
How is the SPNs round function defined?
Ki is XORed with the current state block Wi
Each sub-block gets the same substitution applied using Ps
The whole block is permuted using Pp, at bit level (transposition)
What properties does good block ciphers have?
Avalanche effects with respect to both key and plaintext
What is Plaintext avalance?
Small change in P should result in a large change in C.
Ideally, 1 bit change in P should change each bit in C with the probability 1/2.
Relates to diffusion
What is key avalanche?
Small change in key should result in a large change in the resulting C, when applied to the same plaintext.
Relates to confusion
What is differential cryptoanalysis?
Chosen plaintext attack
Idea: Difference between two input plaintexts, can be correlated to the difference between two output ciphertexts
What is linear cryptoanalysis?
Known plaintext attack
Can theoretically be used to break DES
What defines the security of DES?
It resides in the difficulty of decryption without knowledge of the key.
This is because enc and dec definitions are public property.
What is DES
16-round
Feistel cipher
Key length: 56 bits
block length: 64 bits
Define DES encryption
- 64 bits of P (input block) are permuted according to an initial fixed permutation IP
- 16 rounds of Feistel operation are applied, denoted by function f.
A different 48-bit subkey is used for each round of f. - A fixed inverse permutation, IP^-1, is applied
Output from 1-3 is ciphertext C
What is DES’s Feistel operation (function f)
- 32 bits expanded to 48
- Bitwise modulo two, add 48 bits to 48 bit subkey
- break 48 bits into 8 blocks of 6 bits
- put block i into substitution table i, resulting in a block length of 4 (now 8 blocks of 4 instead of 6)
5- Apply permutation to resulting 32 bits
What is the key schedule of DES?
Each of the 16 rounds involves 48 bits of the 56 bit key.
The key is defined by a series of permutations and shifts on the full 56 bit key
How can you do a brute force attack on a block cipher?
Testing all 2^k possible keys
Right key can be identified by using a small number of cipher blocks. Looking for low entropy in the decrypted P
What is double encryption?
K1 and K2 are two keys of the block cipher
C = E( E(P1,K1), K2)
Key length of original block is k
Brute force qould require 2^(2k-1) trials on avarage
What is a meet in the middle attack on double encryption?
We have a P and C pair which satisfy:
- For each key, store C’ = E(P, K) in memory
- Check whether D(C,K’) = C’ for any K’
- K from step 1 is K1, and K’ from step 2 is K2
- Check whether key values in step 3 work for other (P, C) pairs
This requires storage for one P for every possible key
What is required to be able to do the meet in the middle attack on DES?
Storage of one P for every key
Single enc for every key
Single dec for every key
Store:
- 2^56 64-bit blocks
- 2^56 enc operations
- 2^56 dec operations
What is triple encryption?
C = E( D( E(P, K1), K2 ), K3 )
Secure from the meet-in-the-middle attack
What are the three options for triple decryption?
Three independent keys
K1 = K3
K1 = K2 = K3, vulnerable to brute force
What is AES?
Symmetric block cipher
128-bit block
128, 192, 256 bit master key
Number of rounds (NR) is 10, 12, 14 (128, 192, 256 bit)
byte-based design
Substitution-permutation network
- initial round key addition
- NR-1 rounds
final round
How is state defined in AES?
Using a matrix of bytes.
Example: A block size of 16 bytes gives a 4x4 matrix
What 4 basic operations does AES consist of?
- ByteSyb (non-linear substitution)
- ShiftRow (permutation)
- MixColumn (diffusion)
- AddRoundKey
This creates a substitution-permutation network wit n=128 and l=8
S-box is a lookup table and mathematically defined in GF(2^8)
What is GF(2^8) in AES?
Galois Fields
These are finite fields
GF(2^8) provides a mathematical basis for byte substitution and diffusion
What is the key schedule of AES?
Master key: 128 bits (or 192, 256)
Rounds use 128-bit subkey.
Each round uses one subkey. An additional initial subkey is also required.
Meaning, for 128-bit key, 10 rounds are done, and 11 keys are required.
The schedule derives the 128-bit subkeys from the 128-bit master key
What are related key attacks?
Attacker is able to obtain C encrypted with a key related to the actual key, in a specified way.
What are some attacks that have appeared for AES?
Attacks on reduced-round versions
Related key attacks
Attacks that are able to reduce effective key size by around 2 bits
Compare DES and AES
Block size: DES-64, AES-128
Key size: DES-56, AES-128, 192, 256
Design structure:
- both are iterate
- DES has feistel structure, AES is SPN
- DES is bit-based, AES is byte-based
- AES is faster in HW and SW
Which of AES and DES is in use today?
AES, but DES is still in use in older applications
what is a key schedule?
The process of derive sub-keys for use in a round function, from a master key
What are 2 widely used general block cipher designs?
Feistel ciphers: DES
Substitution-Permutation Networks (SPNs): AES
What should modern block ciphers be designed to be immune to?
Differential and linear cryptanalysis
