The Hong Kong Polytechnic University · FACULTY OF COMPUTER SCIENCE

COMP5563 Chap.3 Block Cipher Design, DES and AES

- one subject, every graph, every model, every mark
6 Chapters6-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 3 of 5 · COMP5563

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.

In this chapter

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

Q [6 marks]. AskSia-authored practice. A toy cipher has independent 20-bit keys and is applied twice. Estimate generic meet-in-the-middle time and storage. The marks shown are an AskSia study allocation and are not the University's marking scheme.
Meet-in-the-middle collapses the intended gain from double DES.Meet-in-the-middle collapses the intended gain from double DES. Storing forward values under first keys and matching backward values under second keys reduces work from roughly 2^112 to about 2^57 operations plus memory. Approximate key-search work on a base-two exponent scale 2⁵⁶2¹¹²about 2⁵⁷ DES searchnaive double DESmeet-in-middle work exponent
Meet-in-the-middle collapses the intended gain from double DES. Storing forward values under first keys and matching backward values under second keys reduces work from roughly 2^112 to about 2^57 operations plus memory.
  • 2Store every forward midpoint.
  • 2Compute every backward midpoint and match.
  • 2State approximate time and memory.
Store 2^20 values E(k1,m), then compute 2^20 values D(k2,c) and search for matches. Time is about 2^21 cipher operations and storage about 2^20 values, not 2^40 work. Extra known pairs verify candidates.
Sia tip — Look for an intermediate value that both sides of a composition can compute independently.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 24 of your subjects at The Hong Kong Polytechnic University, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP5563 tutor, unlimited, worked the way the exam marks it
The full 6-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works