COMP5563 Chap.3 Block Cipher Design, DES and AES
Block Cipher Design, DES and AES
Match evidence to claims
A block cipher is a keyed permutation on a fixed block space. PRP security compares it with a random permutation, while PRF security compares a function with a random function.
Key length, block length, round structure and implementation evidence each support different conclusions.
Construction and attack
Feistel networks obtain invertibility even when the round function is not invertible. DES illustrates Feistel structure and a key size vulnerable to exhaustive search. Meet-in-the-middle shows why double encryption does not double the exponent.
AES uses a substitution-permutation network with a 128-bit block, while GGM demonstrates how pseudorandom functions can be constructed from generators.
Trace structure
A Feistel round copies the old right half and combines the old left half with a keyed transformation. Reversing round-key order reconstructs both halves without inverting the round function.
Writing every pair exposes cancellations that prose can hide.
Keep parameters separate
Key length controls generic exhaustive search, while block length controls collision and birthday limits. DES shows why a 56-bit key is inadequate even with a 64-bit block.
Double encryption exposes a shared midpoint that forward and backward searches can match.
Name the attacker model
Linear and differential attacks exploit abstract relations. Timing, power and fault attacks observe an implementation. Quantum search changes generic work factors. Each conclusion should state the access model, work estimate and operational boundary it actually supports.
What this chapter covers
- 01
PRF and PRP experiments
- 02
Feistel round inversion
- 03
DES rounds and S-box evidence
- 04
Exhaustive and meet-in-the-middle search
- 05
Linear, implementation and quantum attacks
- 06
AES and GGM construction
Worked example · free
Price meet-in-the-middle for a toy double cipher
- 2Store every forward midpoint.
- 2Compute every backward midpoint and match.
- 2State approximate time and memory.
Key terms
- Pseudorandom Permutation
- An invertible keyed family indistinguishable from a random permutation to efficient oracle algorithms.
- Feistel Network
- A split-block construction using swapping and XOR to create an invertible permutation.
- Meet-in-the-Middle Attack
- A search matching forward and backward intermediate values to reduce composed-cipher work.
Block Cipher Design, DES and AES FAQ
What is the practical difference between a PRF and PRP?
A PRP is invertible for every key and maps a block space onto itself, which supports decryption. A PRF need not be invertible. Their oracle games also differ because a random function may collide while a permutation cannot.
Why does double DES not provide 112-bit security?
The attacker computes all first-key forward midpoints and all second-key backward midpoints, then matches them. This requires roughly two 56-bit searches plus memory rather than a joint search over every key pair.
Does using AES guarantee a secure financial protocol?
No. AES can be a strong block-cipher primitive while the mode repeats nonces, the application omits integrity, keys leak through an implementation channel, or the authenticated domain excludes critical fields. The surrounding construction remains part of the claim.
What does the GGM construction contribute?
It shows how a length-doubling pseudorandom generator can define a much larger keyed function through a binary tree. Evaluation follows input bits through left or right generator halves. A hybrid proof replaces expansions step by step, connecting any function distinguisher to an attack on the underlying generator.
Exam move
Build an evidence ledger with one row each for key size, block size, construction shape, best structural attack, implementation exposure and traffic limits. In a second column, write the conclusion that each fact supports; in a third, write what it does not establish. Trace one Feistel round forward and backward until you can explain invertibility without assuming an inverse round function.
Reconstruct meet-in-the-middle from the shared intermediate equation rather than memorising its name. Compare DES and AES only after separating key and block parameters. For reductions, rehearse the PRP and PRF ideal objects and ask where collisions distinguish them. Finish every answer with its attacker model: abstract oracle access, known pairs, side-channel measurements or quantum search.
That boundary keeps evidence from being stretched beyond the theorem or attack it actually supports. Draw a three-bit GGM path and label each generator expansion, then describe one adjacent hybrid replacement in complete sentences. Explain how a distinguisher at that step attacks the generator. Finally, compare a theorem about oracle access with an implementation attack such as timing or power observation.
List what each adversary sees and why success in one model does not automatically prove success in the other.
Working through Block Cipher Design, DES and AES in COMP5563? Sia is AskSia’s AI Computer Science tutor — ask any COMP5563 Block Cipher Design, DES and AES question and get a clear, step-by-step explanation grounded in how COMP5563 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.