Cyber and Information Security Notes | B.Sc. (Computer Science) Semester 5 | Mumbai University | munotes

Availability. FIPS 199: "Ensuring timely and reliable access to and use of information". A loss of availability is the disruption of access to or use of information or an information system.

In plain English: it works when you need it. This is the property people forget is part of security, and it is the one attacked most often in practice, because a denial of service attack needs no cleverness at all.

Two more that the standards add, and MU will expect you to know

Confidentiality, integrity and availability are the three the syllabus names, but the security literature adds two, and both appear later in this paper.

Authenticity. RFC 4949 defines authenticity as the property of being genuine and able to be verified and trusted. It is what a digital signature gives you: not only that the message was not altered, but that it came from the person it claims to have come from. It is the reason Module 1 spends five chapters on message authentication.

Accountability. The property that an entity's actions can be traced uniquely to that entity. It is what an audit log gives you, and without it there is no investigation after an incident and no non-repudiation. NIST SP 800-12 Rev. 1 treats both of these as objectives alongside the triad.

Worked example: why you cannot have all three at once

The system. A college publishes semester results on a web server. Three thousand students want them within an hour of publication. The Examination Section wants nobody to see them early and nobody to change them ever.

Step 1: strengthen confidentiality. Require every student to log in with a password, and post nothing publicly. Confidentiality improves. Availability falls, because three thousand simultaneous logins are far heavier than three thousand reads of one static page, and because several hundred students will have forgotten their password on the day.

Step 2: strengthen integrity. Require two officers of the Examination Section to approve every upload, and make the published file read only, signed, and impossible to correct without repeating the approval. Integrity improves. Availability falls again, because a genuine correction to one student's mark now takes two days.

Step 3: strengthen availability. Put the results file on a public content delivery network with no login, cached in fifty places so that no surge can slow it. Availability becomes excellent. Confidentiality is gone, because anyone with the address can read anyone's marks, and integrity is weaker, because there are now fifty copies and no single place to correct.

What the example shows. Every one of the three steps was a correct security decision, and every one made another property worse. Security is therefore not a quantity a system has more or less of; it is a set of deliberate trade-offs recorded against a stated requirement. When a question asks you to "design a secure system for X", it is asking which trade-off you chose and why, and an answer that promises all three is a weak answer.

Distinctions that carry marks

What it does not mean

Security is not the same as cryptography. Cryptography is one mechanism, and it serves confidentiality, integrity and authenticity. It does nothing at all for availability, and a great deal of this paper's Module 2 is about controls with no cryptography in them: firewalls, intrusion detection, antivirus.

"Secure" is not a property a system has. It is always relative to a threat and a cost. A lock that resists a student with a hairpin does not resist a locksmith, and the honest statement is always "secure against whom, for how long, at what cost".

Integrity does not mean the data is correct. It means the data has not been altered since it was recorded. If the clerk typed 45 when the answer book said 54, integrity is perfect and the mark is wrong. Integrity protects the record, not the truth of what was recorded.

Availability failures are usually accidents. A power cut, a full disk and a wrong configuration take down more systems than attackers do, which is why availability sits inside security rather than beside it.

Quick revision

• Security: information and systems do what their owner intended, and nothing else.
• The CIA triad: confidentiality, integrity, availability.
• Confidentiality: preserving authorised restrictions on access and disclosure. Lost by disclosure.
• Integrity: guarding against improper modification or destruction. Lost by modification.
• Availability: timely and reliable access. Lost by disruption.
• Two more from the standards: authenticity (genuine and verifiable) and accountability (actions traceable to one entity).
• The three pull against each other. Strengthening one usually weakens another, and naming the trade-off is the answer.
• Integrity is about the record being unaltered, not about the record being true.

Test yourself

1. Define information security, and name the three properties it preserves. Information security is the protection of information and information systems from unauthorised access, use, disclosure, disruption, modification or destruction. The three properties are confidentiality (only authorised people can read the data), integrity (the data has not been improperly altered or destroyed) and availability (authorised users can reach the data when they need it).

2. A college's public examination timetable is altered so that one paper shows the wrong date. Which property was lost, and which was not? Integrity was lost: the data was modified without authority. Confidentiality was not lost, because the timetable was public and there was nothing to disclose. Availability was not lost either, because the page still answered.

3. Give one control for each of the three properties. Confidentiality: encrypt the data and require a login. Integrity: store a hash or a message authentication code with the record and check it before use. Availability: keep a second server and limit how many requests one address may make.

4. Why is it wrong to call a system "secure" without qualification? Because security is always relative to a threat, a time and a cost. A control that stops a curious classmate will not stop a funded attacker, so the meaningful claim names who the system resists and for how long.

5. A results server is put behind a login, and on results day it collapses under the load. Was that a security failure? Yes. Availability is one of the three properties, so a system that cannot be reached when it is needed has failed a security objective, even though the failure came from a control that was correctly protecting confidentiality. It is the trade-off in the worked example.

6. What do authenticity and accountability add to the triad? Authenticity is the property of being genuine and verifiable, so that a message can be shown to come from the party it claims to; a digital signature provides it. Accountability is the property that an action can be traced uniquely to the entity that performed it; an audit log provides it, and non-repudiation depends on it.

7. Distinguish security from privacy. Security asks whether data is protected from unauthorised access, and is decided by the people who build the system. Privacy asks whether the data should be collected and held at all, and for what purpose, and is decided by law and by the person the data concerns. Security is necessary for privacy but does not by itself produce it.

Read the column of dates. Eight of the nine fall after 2010, and four fall after 2019. MU's prescribed textbook was printed in 2017, so a student who learns this subject only from it will state four of these nine facts wrongly, and will say "3DES is secure" and "DSA is the Digital Signature Standard" in an examination that is being sat in 2026. This book teaches what MU sets and then gives the date, in the chapter that owns each one.

What actually drives the trend

Four separate forces push in the same direction, and naming them is usually worth more in an answer than describing the curve.

1. Computing became cheap, and attacks are arithmetic. DES's 56-bit key was a defensible choice in 1977 and an indefensible one in 1998, without anybody discovering anything new about DES. The key did not weaken; the machines got faster. Every key length in this subject is therefore a statement about hardware at a date, which is why NIST publishes a transition schedule rather than a permanent answer.

2. Attacks get packaged. The first person to exploit a weakness needs to understand it. The second thousand need only run the tool the first person published. This is the single mechanism behind the whole trend: the knowledge moves out of the attacker's head and into software.

3. The attack surface grew faster than the defences. In 1980 the systems worth attacking were a few thousand mainframes reached over leased lines. Today a first-year student carries a networked computer, and a college has servers, wireless, cloud accounts and a payment gateway. Every one of those is a place where the three properties of the previous chapter can be lost.

4. Attacking became a business. When the motive was curiosity the volume was limited by the number of curious people. When the motive is money, the volume is limited only by profit, which is why ransomware and credential theft dominate the incident reports rather than clever cryptographic breaks.

Where the subject starts: Anderson, 1980

The earliest document in this book's authority base is James P. Anderson's report of 15 April 1980, Computer Security Threat Monitoring and Surveillance, which is where intrusion detection begins. It is worth knowing for two reasons.

First, it already contains the classification of intruders that Module 2 of this syllabus still uses, and it already argues that you cannot prevent every intrusion, so you must be able to detect one from the records the system keeps anyway. That argument is forty-six years old and is the reason your college's servers keep logs.

Second, it shows what has and has not changed. The threats Anderson lists are the masquerader using someone else's credentials, the legitimate user exceeding their authority, and the user hiding their tracks. Those are exactly the three classes in Module 2's chapter on intruders. The tooling changed beyond recognition; the taxonomy did not.

A worked example: one weakness, three populations

The weakness. In 2014 a flaw was published in the way SSL 3.0 pads a block cipher record, which lets a party who can sit between a browser and a server recover the plaintext one byte at a time. The mathematics is not hard but the setup is fiddly.

Population 1, the week it was published. A handful of people in the world could mount it, because it needed a researcher's understanding and custom code. The number of actual victims was approximately zero.

Population 2, three months later. The attack was in penetration testing toolkits, as a menu item. Anybody running a network scan on a campus could now find every server that still spoke SSL 3.0 and demonstrate the attack in an afternoon, with no understanding of padding at all.

Population 3, June 2015. The IETF published RFC 7568, which prohibits SSL 3.0 outright: implementations must not send or accept it. The weakness did not get harder to exploit. It was removed from the ecosystem instead, by a standards body, eight months after publication.

What the example shows. The trend is not that attackers get cleverer. It is that the distance between discovering a weakness and being able to use it collapses, so the only durable defence is retiring the weak thing. That is why this subject is full of dates, and why every chapter here ends on what the current standard says rather than on what the algorithm was designed to do.

Distinctions that carry marks

What beginners get wrong here

"Attacks are getting more sophisticated" does not mean "attackers are getting smarter." It means the tools are. The two claims are opposites, and mixing them up is the commonest error in an answer on this topic.

A retired algorithm is not a broken algorithm, and a broken algorithm is not always retired. DES was withdrawn because its key is too short, not because anybody found a flaw in its design. SHA-1 is still permitted for some non-collision uses, such as inside HMAC, long after collisions were found. The right question is always "what property failed, and for which use".

Old does not mean weak. The one-time pad is from 1917 and is unbreakable. AES is from 2001 and, with a 256-bit key, is expected to outlive everybody reading this. Age is not the variable; key length and published cryptanalysis are.

Quick revision

• The trend: attack sophistication rises while the intruder knowledge required falls, because attacks get packaged into tools.
• Proved by the retirement dates: DES 2005, MD5 and SHA-1 restricted 2011, SSL 3.0 2015, two-key 3DES disallowed 2019, TLS 1.0 and 1.1 2021, 3DES 2024, DSA for signing 2024.
• Four drivers: cheap computing, packaged tools, a bigger attack surface, and money.
• Intrusion detection begins with Anderson, 1980, and his three classes of intruder are still the ones in Module 2.
• A cryptographic claim with no date is not a claim.
• Vulnerability is a weakness; threat is who could use it; attack is the attempt; risk is the expected loss.

Test yourself

1. State the security trend in one sentence, and give the mechanism behind it. Attack sophistication has risen steadily while the technical knowledge needed by an intruder has fallen. The mechanism is packaging: once an attack is discovered it is written into an automated tool, so the understanding moves from the attacker into software and the number of people able to run the attack grows enormously.

2. Name three algorithms or protocols that have been formally retired, with their dates. DES, withdrawn 19 May 2005. SSL 3.0, deprecated by RFC 7568 in June 2015. Triple DES, which stopped being an approved block cipher on 1 January 2024 when NIST SP 800-67 Rev. 2 was withdrawn. DSA for signature generation is a fourth, withdrawn by FIPS 186-5 with effect from 3 February 2024.

3. Why was DES withdrawn, and what does that tell you about key lengths generally? Because its 56-bit key became brute-forceable as hardware improved, not because a flaw was found in the cipher. It shows that a key length is a claim about the cost of computing at a date, so every key length recommendation has an expiry and must be read with its date.

4. Distinguish a vulnerability, a threat and an attack. A vulnerability is a weakness in the system, such as an out-of-date protocol still being accepted. A threat is a party or circumstance that could exploit it. An attack is an actual attempt to exploit it. You can remove a vulnerability; you cannot remove a threat, only your exposure to it.

5. Why does this book give a date with every claim about an algorithm's strength? Because strength is relative to published cryptanalysis and to the cost of computing, and both change. A statement such as "SHA-1 is secure" was true in 2000 and false in 2017, so a claim with no date cannot be checked and cannot be correct for long.

6. What is the significance of Anderson's 1980 report? It is where intrusion detection starts. It argues that not every intrusion can be prevented, so systems must detect intrusions from the audit records they already produce, and it classifies intruders into the external masquerader, the legitimate user exceeding authority, and the user who hides their tracks, which is still the classification used in this syllabus.

7. A college server still accepts TLS 1.0. Is that a vulnerability, and what should be done? Yes. RFC 8996 of March 2021 deprecates TLS 1.0 and TLS 1.1, so accepting it is a known weakness that automated scanners will find within minutes of being pointed at the server. The fix is to configure the server to offer TLS 1.2 and TLS 1.3 only, which is exactly the "retire the weak thing" response the trend forces.

The vocabulary, defined once for the whole book

Each of these is used in every later chapter and is not redefined there.

Threat. X.800 distinguishes two kinds, and the distinction is the basis of the next chapter. A passive threat is, in the Recommendation's own words, "The threat of unauthorized disclosure of information without changing the state of the system." An active threat is "The threat of a deliberate unauthorized change to the state of the system", and X.800's note gives the examples: modification of messages, replay of messages, insertion of spurious messages, masquerading as an authorized entity, and denial of service.

Vulnerability. A weakness in a system that a threat can exploit. A threat is who or what might act; a vulnerability is the hole they would act through. A system with a vulnerability and no threat is safe by luck, and a system with a threat and no vulnerability is safe by design.

Attack. An assault on system security that derives from a threat: an actual attempt to evade security services and violate the security policy of a system. A threat is a possibility; an attack is an event.

Risk. The expectation of loss: how likely a successful attack is, multiplied by what it would cost. Risk is the quantity a manager acts on, and it is the reason perfect security is never the goal.

Security policy. The set of rules that says what is permitted and what is not. Every mechanism in this book enforces a policy, and a mechanism without a stated policy cannot be judged right or wrong.

Entity, principal, subject and object. X.800 speaks of entities communicating. An entity that can be authenticated is a principal. In access control the thing that acts is the subject and the thing acted upon is the object: a student is a subject, a mark sheet is an object.

Encipherment. X.800's word for what everybody else calls encryption, and the Recommendation is careful about it: encipherment algorithms "may be reversible or irreversible", and the reversible ones divide into symmetric, where "knowledge of the encipherment key implies knowledge of the decipherment key and vice versa", and asymmetric, where it does not. That one sentence is the whole of Module 1 in miniature.

A worked example: placing eight things in the right box

The scenario. A college runs a student portal. The Examination Section is worried about eight things. Sort them.

The step that carries the marks. Notice that rows 2 and 3 are the same concern stated twice, once as a service and once as a mechanism, and rows 5 and 6 likewise. That pairing is exactly what MU's Module 1 asks for when it lists "Security Services" and "Security Mechanisms" as separate topics, and it is the thing to practise: given a service, name the mechanisms; given a mechanism, name the services it supports.

The model X.800 gives you to hang everything on

Every protocol in this book is an instance of one picture, and it is worth fixing now because Module 2 is nothing but instances of it.

Two parties want to exchange a message across a channel they do not control. Each applies a security-related transformation to what they send, using secret information that the opponent does not have. Often a trusted third party is needed, either to distribute the secret information to both parties before they start, or to arbitrate afterwards if they disagree. The opponent sits on the channel.

Four tasks follow from that picture, and they are the four things the rest of this book does.

1. Design the transformation. Chapters on DES, AES, RSA, the hash functions.
2. Generate the secret information the transformation needs. The chapters on key generation.
3. Distribute and share the secret information. Diffie-Hellman, the key distribution centre, certificates, Kerberos.
4. Specify a protocol that uses both, so that the service is actually delivered. IPsec, SSL and TLS, PGP, S/MIME.

There is a second model for a different problem, and MU's Module 2 is built on it: network access security, where the threat is not somebody reading the channel but somebody or something getting inside. Its two answers are a gatekeeper function, which is the firewall chapters, and internal controls, which is the intrusion detection and antivirus chapters.

What beginners get wrong here

X.800 is not the OSI seven-layer model. It is a security architecture written to sit alongside that model, and its three headings are useful whether or not anybody uses OSI layering. The seven layers are not examinable here; the three headings are.

A service is not a mechanism, even when only one mechanism can provide it. Non-repudiation is a service; a digital signature is the mechanism. Writing "non-repudiation is a digital signature" loses the mark because the question is testing whether you know the two are different kinds of thing.

Encipherment is a mechanism, not a service. It is the commonest slip in this topic. Confidentiality is the service; encipherment is one mechanism that provides it, and there are others, such as routing control and traffic padding.

X.800 is a 1991 document, and some of it has dated. The taxonomy has not, which is why MU still sets it, but its examples and its layer placements are of their time. This book uses it for the vocabulary and takes the current detail from the standards that came later.

Quick revision

• The OSI Security Architecture is ITU-T Recommendation X.800, March 1991.
• Three headings: security attack, security service, security mechanism. The order matters.
• Attack: any action that compromises security. Service: a promise that counters attacks, delivered by mechanisms. Mechanism: the machinery that detects, prevents or recovers.
• Passive threat: unauthorised disclosure without changing the state of the system. Active threat: a deliberate unauthorised change to the state of the system.
• Active examples in X.800's own note: modification, replay, insertion of spurious messages, masquerade, denial of service.
• Threat is what might happen, vulnerability is the weakness it would use, attack is the attempt, risk is likelihood times loss.
• The model: two parties, a transformation, secret information, sometimes a trusted third party, an opponent on the channel. Four tasks follow.
• Encipherment is a mechanism; confidentiality is the service.

Test yourself

1. What is the OSI Security Architecture, and what are its three headings? It is ITU-T Recommendation X.800 of March 1991, a systematic way of specifying security requirements and characterising the approaches that satisfy them. Its three headings are security attacks, security services and security mechanisms.

2. Define a security service and a security mechanism, and give the relationship between them. A security service is a processing or communication service that enhances the security of a system and counters security attacks. A security mechanism is a process designed to detect, prevent or recover from a security attack. A service is a promise; it is delivered by one or more mechanisms, and one mechanism can support several services.

3. Distinguish a passive threat from an active threat, in X.800's terms. A passive threat is the threat of unauthorised disclosure of information without changing the state of the system. An active threat is the threat of a deliberate unauthorised change to the state of the system, with examples of modification of messages, replay, insertion of spurious messages, masquerading and denial of service.

4. Distinguish threat, vulnerability, attack and risk. A threat is a potential for a security violation. A vulnerability is a weakness through which a threat could act. An attack is an actual attempt to violate the security policy. Risk is the expected loss, being the likelihood of a successful attack multiplied by its cost.

5. Is encipherment a service or a mechanism? What is the service it supports? It is a mechanism. It supports data confidentiality principally, and also contributes to data integrity, authentication and non-repudiation when combined with other mechanisms.

6. Draw out the model of network security and name the four tasks it implies. Two parties exchange a message over an insecure channel, each applying a security-related transformation that uses secret information, with a trusted third party where one is needed, and an opponent on the channel. The four tasks are: design the transformation; generate the secret information; distribute and share it; and specify a protocol that uses both to deliver the service.

7. Give the two elements of the network access security model, and name the part of this syllabus that treats each. A gatekeeper function, which is the firewalls topic of Module 2; and internal controls, which are the intrusion detection and malicious software topics of Module 2.

A concrete example: the Examination Section's server normally exchanges a few small messages an hour with the printer's office. On one night in November it exchanges two hundred megabytes with them at three in the morning. Nobody has read a single mark, and everybody now knows the question papers went out that night. Or, on a personal scale: an opponent who sees encrypted traffic between a student's phone and a particular clinic's booking system learns something private without decrypting one byte.

Traffic analysis is why X.800 lists traffic flow confidentiality as a service of its own and traffic padding as a mechanism of its own. Encrypting the payload does not defeat it; only sending cover traffic does.

Active attacks: the four kinds

X.800's own note on active threats names the examples: "modification of messages, replay of messages, insertion of spurious messages, masquerading as an authorized entity and denial of service". The four standard headings are these.

Masquerade. X.800: "The pretence by an entity to be a different entity." One entity pretends to be a different one, usually by replaying captured authentication information so that the receiver believes it is talking to somebody it is not.

Example: an attacker captures a clerk's login from the wireless in the afternoon and replays it that evening, and the portal accepts an upload of marks as though the clerk had sent it. Masquerade usually comes with one of the other three: the captured credential is a replay, and the upload is an insertion.

Replay. The passive capture of a data unit and its subsequent retransmission to produce an unauthorised effect. The message is genuine, which is what makes it dangerous: every signature on it is valid, every checksum correct. It is simply being sent again, or later, or to somebody else.

Example: a student's fee payment authorisation is captured and sent to the payment gateway three more times. Nothing in the message is forged. Nothing in the message is wrong. The student has paid four times. Defeating replay needs a nonce, a sequence number or a timestamp, and that is why Module 2's chapter on authentication protocols exists.

Modification of messages. Some portion of a legitimate message is altered, or messages are delayed or reordered, to produce an unauthorised effect. Altering "Allow Ramesh Patil to read the accounts file" to "Allow Suresh Kadam to read the accounts file" is the classic instance.

Example on this campus: an internal mark of 12 is changed to 42 in transit between the department and the Examination Section. Notice that encryption does not stop this by itself. A block cipher in the wrong mode is quite happy to have its ciphertext altered, and the chapter on cipher block chaining shows exactly what an attacker gets by flipping one ciphertext bit. Integrity needs a hash or a message authentication code, not merely secrecy.

Denial of service. The prevention or inhibition of the normal use or management of communication facilities. It may have a specific target, such as suppressing all messages to a particular server, or it may be a general disruption, such as flooding a network so that nothing gets through.

Example: on the morning results are published, a few thousand requests a second arrive at the college's results page from machines all over the world, and no student can reach it for two hours. Nothing was read and nothing was altered. The only property lost was availability, and it was lost completely. Module 2's chapter on distributed denial of service works out the arithmetic of how this is done with very little bandwidth of the attacker's own.

A worked example: one interception, four outcomes

The setup. Asha, in the accounts office, sends a message to the bank: Pay 40,000 to vendor 8817. Darth sits on the network between them and captures it. What Darth chooses next decides which attack this is.

The step that carries the marks. One captured message and six different attacks. That is the answer to "classify security attacks with examples": not six unrelated stories, but one interception and the six things an opponent can do with it, with the countermeasure for each.

Distinctions that carry marks

The second table is a different cut of the same ground, by which property is attacked rather than by whether the system changed. Both are asked, so both are worth knowing; they are not two different taxonomies to be confused, they are two ways of sorting the same six attacks.

What beginners get wrong here

"Passive" does not mean harmless. It means the attacker does not change anything. Reading every mark in a university is entirely passive and is the most damaging thing on this page.

Encryption does not stop an active attack. It stops the passive ones. A ciphertext can be replayed, reordered, truncated or flipped, and a cipher on its own says nothing about whether it arrived as sent. That separation, confidentiality against integrity, is the reason message authentication has its own five chapters.

Traffic analysis is not a failure of encryption. It works precisely because the payload is encrypted and the opponent has to fall back on the metadata. It is defeated by padding and cover traffic, not by a stronger cipher.

Denial of service is a security attack. Students leave it out because nothing is stolen. Availability is one of the three properties, so a successful denial of service is a complete security failure.

Quick revision

• Passive: reads, changes nothing. Release of message contents, traffic analysis. Prevent (encryption); you cannot detect it.
• Active: changes something. Masquerade, replay, modification of messages, denial of service. Detect and recover; you cannot prevent it absolutely.
• X.800 passive threat: unauthorised disclosure without changing the state of the system.
• X.800 active threat: a deliberate unauthorised change to the state of the system.
• Masquerade, in X.800's words: the pretence by an entity to be a different entity.
• Replay uses a genuine message, so every signature on it is valid: the defence is a nonce, a sequence number or a timestamp.
• The second cut: interruption (availability), interception (confidentiality), modification (integrity), fabrication (authenticity).
• Traffic analysis survives encryption; traffic padding is the answer.

Test yourself

1. Classify security attacks and give the defining difference. Into passive and active. A passive attack learns or makes use of information from the system without affecting system resources; an active attack alters system resources or affects their operation. The difference is whether the state of the system changes.

2. Name the two passive attacks and explain why neither can be detected. Release of message contents and traffic analysis. Neither alters the message or the system, so nothing on the legitimate parties' side is different from a normal exchange and there is no evidence to detect. The defence is therefore prevention, by encryption.

3. What is traffic analysis, and why does encryption not stop it? Observing the pattern of encrypted traffic (who talks to whom, when, how often, how much) and drawing conclusions from it. Encryption hides the contents but not the existence, size, timing or endpoints of a message, so the pattern remains readable. Traffic padding and cover traffic are the countermeasures.

4. Name the four active attacks, with one example each. Masquerade: an attacker replays a clerk's captured login and uploads marks. Replay: a captured payment authorisation is sent three more times. Modification of messages: a mark of 12 is altered to 42 in transit. Denial of service: the results page is flooded on results day so no student can reach it.

5. Why can active attacks not be prevented absolutely? Because the attacker has a very large number of possible points of attack, physical and logical, across every link and device between the parties, and defending all of them completely is not feasible. The realistic goal is to detect the attack, recover from any disruption it causes, and make it expensive.

6. Why does replay work even when every message is signed? Because the replayed message is genuine. Its signature is valid and its contents are unaltered; the only thing wrong is that it is being delivered again or at the wrong time. Freshness must therefore be supplied separately, by a nonce, a sequence number or a timestamp.

7. Sort interruption, interception, modification and fabrication by the property each attacks, and say which is passive. Interruption attacks availability; interception attacks confidentiality; modification attacks integrity; fabrication attacks authenticity. Only interception is passive; the other three are active.

3. Data confidentiality

The protection of data from unauthorised disclosure. X.800 gives four sub-services, and this is the clause worth memorising because all four appear in later chapters.

Connection confidentiality (5.2.3.1): all user data on a connection is protected. This is what TLS gives a browser.

Connectionless confidentiality (5.2.3.2): the user data in a single data unit is protected. This is what an encrypted email or a single IPsec-protected datagram gives.

Selective field confidentiality (5.2.3.3): only chosen fields are protected. A form might encrypt the card number and leave the customer's name in clear, which is exactly what the dual signature in the Secure Electronic Transaction chapter does.

Traffic flow confidentiality (5.2.3.4): the protection of the information that could be derived from observing traffic flows. This is the service that answers traffic analysis, and it is the one a cipher alone does not provide.

4. Data integrity

The assurance that data is received exactly as sent, with no duplication, insertion, modification, reordering or replay. X.800 gives five sub-services, and the first two carry the distinction that is set most often.

Connection integrity with recovery (5.2.4.1): the integrity of all user data on a connection is protected, and any modification, insertion, deletion or replay is detected with recovery attempted.

Connection integrity without recovery (5.2.4.2): the same detection, but only reporting, with no attempt to recover.

Selective field connection integrity (5.2.4.3): integrity of chosen fields within the user data of a connection.

Connectionless integrity (5.2.4.4): integrity of a single data unit, which may also take a limited form of detection of modification.

Selective field connectionless integrity (5.2.4.5): integrity of chosen fields within a single data unit.

Why would anyone choose the version without recovery? Because recovery costs something, and at the wrong layer it costs too much. A protocol that must detect and repair every altered datagram carries state, buffers and retransmission logic; one that merely reports the fault and drops the connection is far simpler, and the application above it can decide what to do. Detection alone is often the right engineering answer, which is why the standard offers both.

5. Non-repudiation

Protection against one of the parties to a communication denying that they took part. X.800 gives two forms.

Non-repudiation with proof of origin (5.2.5.1): the recipient is given proof of the origin of the data, so the sender cannot later deny having sent it.

Non-repudiation with proof of delivery (5.2.5.2): the sender is given proof of delivery, so the recipient cannot later deny having received it.

This is the service that needs a public key. That claim is the whole of the worked example below, and it is the most commonly missed point in the topic.

A worked example: why a MAC cannot give non-repudiation

The setup. Asha and Bharat share one secret key, K. Asha sends Pay 40,000 to vendor 8817 with a message authentication code computed over it using K. A message authentication code, or MAC, is a short tag computed from the message and a shared secret key; anybody holding the key can recompute it and check it.

Step 1: integrity and authentication both succeed. Bharat recomputes the tag with K and it matches. He knows the message was not altered, because an attacker without K cannot produce a matching tag for a changed message. He knows it came from somebody holding K, and only he and Asha hold it. So he has data integrity and data origin authentication.

Step 2: the dispute. Asha later denies sending it. Bharat produces the message and the tag.

Step 3: why Bharat loses. Asha's answer is: "Bharat holds K too. He could have written that message himself and computed that tag himself. There is nothing in that tag that only I could have produced." And she is right. A MAC is symmetric: everybody who can verify it can also forge it. Bharat cannot prove to a third party, a court or an arbitrator, that the message came from Asha rather than from himself.

Step 4: what fixes it. Asha signs the message with her private key, which nobody else has, and Bharat verifies with her public key, which everybody has. Now the verification succeeds for anybody who cares to check, and only Asha could have produced the signature. Bharat can prove origin to a third party. That is non-repudiation with proof of origin.

The step that carries the marks. The reason is the asymmetry, not the strength. A MAC with a 256-bit key is enormously strong and still cannot give non-repudiation, because the verifier and the signer are the same role. A signature with a much smaller security margin can, because they are different roles.

In Indian law. This is not only a technical distinction. Section 3A of the Information Technology Act 2000 recognises an electronic signature, and section 5 provides that where any law requires a signature, that requirement is satisfied by an electronic signature affixed in the prescribed manner. The Act therefore builds on exactly the asymmetry above: a signature is attributable to the person whose private key made it.

Distinctions that carry marks

What beginners get wrong here

Integrity is not a weaker form of confidentiality. They are independent. A public timetable needs integrity and no confidentiality. A stored password needs confidentiality and, oddly, rather little integrity, because a corrupted password simply fails to match.

Authentication does not include authorisation. Logging in proves who you are. Whether you may see the accounts file is access control, and a system that confuses the two gives every authenticated user everything.

A MAC gives authentication but not non-repudiation. The worked example above is the whole answer, and it is set.

Availability is not one of X.800's five services. It appears as one of the three properties of the first chapter, and the Recommendation treats it through other means, but if a question asks for X.800's security services the answer is the five named here. Some texts add availability as a sixth; say which list you are giving.

Quick revision

• Five services: authentication, access control, data confidentiality, data integrity, non-repudiation.
• Authentication: peer entity (a connection, at set-up) and data origin (one data unit, no protection against duplication).
• Confidentiality: connection, connectionless, selective field, traffic flow.
• Integrity: connection with recovery, connection without recovery, selective field connection, connectionless, selective field connectionless.
• Non-repudiation: with proof of origin, with proof of delivery.
• A MAC cannot give non-repudiation, because the verifier can also forge. A digital signature can, because only the holder of the private key can sign.
• In India, sections 3A and 5 of the Information Technology Act 2000 give an electronic signature the effect of a signature.
• Integrity and confidentiality are independent; authentication and access control are different services.

Test yourself

1. List X.800's five security services and say what each one promises. Authentication (the other party is who it claims to be), access control (only permitted use of a resource), data confidentiality (no unauthorised disclosure), data integrity (the data arrived exactly as sent) and non-repudiation (neither party can later deny taking part).

2. Distinguish peer entity authentication from data origin authentication. Peer entity authentication confirms the identity of the entity at the other end of a connection, at the time the connection is established, and is used in a live session. Data origin authentication confirms the source of a single data unit and is used for store-and-forward traffic such as electronic mail; by itself it gives no protection against duplication or modification of the data unit.

3. Name X.800's four confidentiality sub-services. Connection confidentiality, connectionless confidentiality, selective field confidentiality, and traffic flow confidentiality.

4. What is the difference between connection integrity with recovery and without recovery, and why would anybody choose the weaker one? Both detect modification, insertion, deletion and replay on a connection; the first attempts to recover from what it detects and the second only reports it. The reporting form is chosen because recovery costs state, buffering and retransmission, and at the wrong layer that cost is not worth paying: the application above can decide what to do.

5. Why can a message authentication code not provide non-repudiation? Because the key is shared. Anybody who can verify the tag can also compute it, so the recipient could have produced the message and the tag themselves. There is nothing in the tag that only the sender could have made, so origin cannot be proved to a third party. A digital signature made with a private key can be verified by anybody and produced by only one party, which is what non-repudiation requires.

6. Give the two forms of non-repudiation. Non-repudiation with proof of origin, which stops the sender denying that they sent the data; and non-repudiation with proof of delivery, which stops the recipient denying that they received it.

7. Which service answers traffic analysis, and why is encryption alone not enough? Traffic flow confidentiality. Encryption conceals the contents but leaves the existence, length, frequency and endpoints of messages visible, and conclusions can be drawn from those alone. The service is provided by traffic padding and cover traffic, not by a stronger cipher.

8. Notarisation. X.800 defines it as "The registration of data with a trusted third party" that allows the later assurance of the accuracy of its characteristics such as content, origin, time and delivery. It is how a third party makes a claim about a message stick, and it is what Module 2's arbitrated digital signatures and the whole certificate hierarchy are built on.

The five pervasive mechanisms

These are not tied to a particular service or layer, and they are the ones that make the rest workable.

Trusted functionality. That which is judged to be correct with respect to some criteria. Everything else rests on it: if the code implementing your cipher is untrustworthy, the cipher is irrelevant.

Security labels. A marking bound to a resource that names its security attributes, which is how a system can enforce a policy about data rather than about users.

Event detection. Detection of security-relevant events, which is the mechanism intrusion detection is built out of.

Security audit trail. Data collected and potentially used to facilitate a security audit, which is an independent review of system records. Without it there is no accountability and no investigation.

Security recovery. Deals with requests from mechanisms such as event handling and management functions, and takes recovery actions. This is the "recover" in the definition of a mechanism, and it is the one students forget is part of security at all.

X.800's own table, service by mechanism

This is Table 1 of the Recommendation. A mark means the mechanism is considered appropriate for that service, on its own or with others; a blank means it is considered not appropriate. The Recommendation adds a note that in some instances a mechanism provides more than the service needs but could nevertheless be used.

Four things to read out of it, because these are what a question on the table is testing.

Encipherment appears against everything except the two non-repudiation rows and access control. It is the most widely useful mechanism in the standard, and that is why Module 1 is mostly about it.

A digital signature appears against no confidentiality row at all. Signing does not hide. This is the cell most often filled in wrongly, and getting it right is worth a mark on its own.

Non-repudiation is the only service for which encipherment is not appropriate. Its three mechanisms are digital signature, data integrity and notarisation, which is the previous chapter's worked example expressed as a row of a table.

Traffic flow confidentiality is the only service with three mechanisms from three different families: encipherment, traffic padding and routing control. It is the service you cannot buy with a cipher alone.

One honest note about the source. The text layer of the ITU PDF merges a cell in the "Connection confidentiality" row, printing seven marks where there should be eight. The row above and the row below are intact and identical in shape, and the connectionless row reads encipherment and routing control, so the connection row has been reconstructed the same way. That is stated here rather than presented as if it had been read cleanly.

A worked example: designing for one requirement

The requirement. The Examination Section says: "A department must be able to submit internal marks to us over the campus network. We must know which department sent them, nobody else on the network may read them, we must be certain they were not altered, and if a department later denies submitting them we must be able to prove it."

Step 1: name the services. Four sentences, four services. "Which department sent them" is data origin authentication. "Nobody else may read them" is connectionless confidentiality, connectionless because each submission is a standalone message. "Not altered" is connectionless integrity. "Prove it against a denial" is non-repudiation with proof of origin.

Step 2: read the mechanisms off the table. Data origin authentication takes encipherment or a digital signature. Connectionless confidentiality takes encipherment, or routing control. Connectionless integrity takes encipherment, a digital signature, or a data integrity mechanism. Non-repudiation of origin takes a digital signature, a data integrity mechanism, or notarisation, and not encipherment.

Step 3: choose the smallest set that covers all four. A digital signature covers three of the four rows. Encipherment covers the fourth, confidentiality, which the signature cannot. So the answer is: hash the submission, sign the hash with the department's private key, and encrypt the whole thing. Two mechanisms, four services.

Step 4: notice what the table forced. Nothing in this design was chosen by taste. The requirement named four services, the standard's table named the mechanisms that serve them, and the intersection gave the design. That is the reasoning a question asking you to "design a scheme for the following requirement" is looking for.

The two models the rest of the book fills in

The communication model. Two parties exchange a message over a channel they do not control. Each applies a security-related transformation using secret information the opponent lacks, sometimes with a trusted third party to distribute that information beforehand or to arbitrate afterwards. Module 1 designs the transformations and distributes the secrets; Module 2's first half specifies the protocols that use them, which is what PGP, S/MIME, IPsec and TLS are.

The access model. The threat is not somebody reading the channel but something getting inside: an unwanted person, or unwanted software. Two answers: a gatekeeper function at the boundary, which is the firewall chapters, and internal controls that watch what is already inside, which is the intrusion detection and malicious software chapters. Module 2's second half is nothing but this model.

Every remaining chapter of this book sits in one of those two pictures, and it is worth deciding which one a new topic belongs to before reading it.

What beginners get wrong here

A digital signature does not provide confidentiality. It is the single commonest error in this topic, and X.800's Table 1 settles it: there is no mark in any confidentiality row under the signature column. To get both you sign and then encrypt, which is exactly what PGP does.

Traffic padding is useless unless it is encrypted. If an opponent can tell the filler from the data, the filler hides nothing. X.800 says so.

Notarisation is a mechanism, not an institution. It means registering data with a trusted third party. A certification authority is one instance; a timestamping service is another.

The pervasive mechanisms are examinable. They are usually omitted from notes because they do not map to a service. Trusted functionality, security labels, event detection, security audit trail and security recovery are five easy marks in a question that asks for X.800's mechanisms in full.

Quick revision

• Mechanism: a process designed to detect, prevent or recover from an attack.
• Eight specific: encipherment, digital signature, access control, data integrity, authentication exchange, traffic padding, routing control, notarisation.
• Five pervasive: trusted functionality, security labels, event detection, security audit trail, security recovery.
• Encipherment is reversible (symmetric or asymmetric) or irreversible (a hash).
• From Table 1: encipherment serves almost everything; a signature serves no confidentiality service; non-repudiation is the one service encipherment does not serve; traffic flow confidentiality needs encipherment, padding and routing control.
• Authentication exchange techniques: timestamps and synchronised clocks, two-way and three-way handshakes.
• Traffic padding works only if the padding is enciphered.
• Two models: communication (transformation, secret, trusted third party, opponent on the channel) and access (gatekeeper plus internal controls).

Test yourself

1. Define a security mechanism, and give X.800's two categories. A process, or a device incorporating such a process, designed to detect, prevent or recover from a security attack. X.800 divides them into specific security mechanisms, which sit in a protocol layer and provide particular services, and pervasive security mechanisms, which are not specific to any service or layer.

2. Name the eight specific mechanisms. Encipherment, digital signature, access control, data integrity, authentication exchange, traffic padding, routing control and notarisation.

3. Name the five pervasive mechanisms. Trusted functionality, security labels, event detection, security audit trail and security recovery.

4. Which mechanisms provide non-repudiation, and which one notably does not? A digital signature, a data integrity mechanism and notarisation. Encipherment does not: X.800's Table 1 marks it as not appropriate for either form of non-repudiation, because a shared key lets the verifier forge.

5. Which mechanisms provide traffic flow confidentiality, and why is more than one needed? Encipherment, traffic padding and routing control. Encryption hides the contents but leaves the pattern of traffic visible, so padding is needed to conceal volume and timing and routing control to choose which physical paths carry the data.

6. Does a digital signature provide confidentiality? Justify from the standard. No. In X.800's Table 1 the digital signature column has no entry against any of the four confidentiality services. A signature proves origin and integrity and leaves the data readable; to obtain confidentiality as well you must also encipher.

7. A requirement states that a message must be readable only by the recipient, provably from the sender, unaltered, and undeniable later. Name the services and the smallest set of mechanisms. The services are connectionless confidentiality, data origin authentication, connectionless integrity and non-repudiation with proof of origin. A digital signature over a hash of the message serves the last three; encipherment serves the first. So two mechanisms suffice: sign the hash, then encrypt.

Requirement 2 is the harder of the two in practice, and it is the reason a third of this syllabus is about key management rather than about ciphers. Designing a cipher is a problem you solve once, publicly, and then everybody uses the answer. Getting a key to the other party is a problem you have again with every new party, and it is why the Diffie-Hellman chapter exists.

Kerckhoffs's principle: why the algorithm is published

A student's instinct is that a secret algorithm must be safer than a published one, because the opponent knows less. It is the opposite, and the reason is practical rather than mathematical.

A secret algorithm cannot be reviewed. The only way to gain confidence that a cipher is strong is for many skilled people to attack it and fail. A cipher nobody has seen has not been tested; it has only not been tested yet. AES was chosen after a five-year open competition in which everybody was invited to break every candidate. That is evidence. "Nobody has broken our secret cipher" is not evidence, because nobody has tried.

A secret algorithm cannot be replaced. Keys change easily and algorithms do not. If security rests on the algorithm and the algorithm leaks, everything must be rebuilt. If security rests on the key and the key leaks, you change the key. Putting the secret in the smaller, cheaper, more replaceable component is simply good engineering.

A secret algorithm cannot be standardised. Two parties who have never met cannot interoperate over a secret. Every protocol in Module 2 works because both ends can look the algorithm up in a published document.

The principle, in one line: a cryptosystem should be secure even if everything about the system, except the key, is public knowledge. That is Kerckhoffs's principle, from 1883, and it is the working assumption of this entire subject. Every algorithm on this syllabus is published: DES in FIPS 46-3, AES in FIPS 197, the hash functions in FIPS 180-4, RSA in RFC 8017. You can read all of them. They are secure anyway.

The opposite practice has a name, security through obscurity, and it is used as a criticism. It is not worthless as one layer among many, but as the foundation it fails, because obscurity is lost once and cannot be restored.

A worked example: what the key actually decides

The setup. Take the simplest possible symmetric cipher: shift every letter forward by K positions in the alphabet. Plaintext MEET ME AFTER THE TOGA PARTY.

Step 1: the algorithm is public. Everybody, including the opponent, knows that the rule is "shift by K". Requirement 1 says the cipher must be secure anyway.

Step 2: the key is secret. Suppose K is 3. The program below performs the encryption and the decryption, and prints both.

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def shift(text, k):
    out = ""
    for ch in text.upper():
        if ch in ALPHABET:
            out += ALPHABET[(ALPHABET.index(ch) + k) % 26]
        else:
            out += ch
    return out

plaintext = "MEET ME AFTER THE TOGA PARTY"
key = 3

ciphertext = shift(plaintext, key)
recovered = shift(ciphertext, -key)

print("plaintext :", plaintext)
print("key       :", key)
print("ciphertext:", ciphertext)
print("recovered :", recovered)
print("P = D(K, E(K, P)) is", recovered == plaintext)

plaintext : MEET ME AFTER THE TOGA PARTY
key       : 3
ciphertext: PHHW PH DIWHU WKH WRJD SDUWB
recovered : MEET ME AFTER THE TOGA PARTY
P = D(K, E(K, P)) is True

Step 3: read the model off the run. shift with a positive key is E; shift with a negative key is D; 3 is K. The last line is the identity from section 3, verified rather than asserted. Both parties need the number 3 and nothing else, and anybody who learns the number 3 reads everything.

Step 4: and this cipher fails requirement 1. There are only 25 useful keys, so an opponent who knows the algorithm tries all of them in a fraction of a second. That is not a criticism of the model; the model is fine. It is a statement about this particular algorithm's keyspace, and the next chapters are about making the keyspace large enough that requirement 1 is actually met.

Distinctions that carry marks

What beginners get wrong here

"Symmetric" does not mean the two algorithms are identical. It means the two keys are the same, or trivially derived from each other. In DES the decryption algorithm is the encryption algorithm with the subkeys reversed, which is not the same thing as being identical.

The key is not a password. A key is a value of a fixed length, usually 128 or 256 bits, chosen to be unpredictable. A password is something a human remembers and is far weaker; turning one into the other is a separate job, done by a key derivation function.

Knowing the algorithm is assumed, not a weakness. An answer that offers "keep the algorithm secret" as a countermeasure has misunderstood requirement 1.

Two parties, one key. The N(N - 1)/2 count in the table above is the reason symmetric cryptography alone does not scale, and it is worth being able to compute: ten parties need forty-five keys, a hundred parties need four thousand nine hundred and fifty.

Quick revision

• Five ingredients: plaintext, encryption algorithm, secret key, ciphertext, decryption algorithm.
• C = E(K, P) and P = D(K, C).
• Two requirements: a strong algorithm, against an opponent who knows the algorithm and holds ciphertext; and a securely obtained and kept key.
• X.800: symmetric means knowing the encipherment key implies knowing the decipherment key.
• Kerckhoffs's principle: secure even when everything but the key is public. Because a secret algorithm cannot be reviewed, replaced or standardised.
• Security through obscurity is the opposite practice and fails as a foundation, because obscurity is lost once.
• Symmetric needs N(N - 1)/2 keys for N parties; asymmetric needs 2N.
• Cryptography designs, cryptanalysis breaks, cryptology is both.

Test yourself

1. Name the five ingredients of a symmetric cipher. Plaintext, an encryption algorithm, a secret key, ciphertext and a decryption algorithm.

2. State the two requirements for secure use of conventional encryption. First, a strong encryption algorithm: an opponent who knows the algorithm and has access to one or more ciphertexts should be unable to decipher the ciphertext or to determine the key. Second, the sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure.

3. What does it mean to say a cipher is symmetric, in X.800's terms? That knowledge of the encipherment key implies knowledge of the decipherment key, and the other way round; in practice the two are the same key.

4. State Kerckhoffs's principle and give two reasons for it. A cryptosystem should remain secure even if everything about it except the key is public. First, a published algorithm can be attacked by many skilled people, and surviving that is the only real evidence of strength; a secret one is merely untested. Second, a key can be changed cheaply and an algorithm cannot, so the secret belongs in the replaceable part.

5. Why is requirement 2 harder in practice than requirement 1? Because a cipher is designed once and then used by everybody, whereas a key must be delivered securely to every new correspondent, again and again, over channels that may be no safer than the ones the cipher is protecting. Key distribution is therefore the recurring problem, and it is why public-key methods were invented.

6. How many keys do twenty parties need to communicate pairwise under symmetric encryption, and under public-key encryption? Symmetric: 20 times 19 divided by 2, which is 190 keys. Public-key: two per party, so 40 keys, of which only the 20 private ones are secret.

7. A vendor says their cipher is safe because nobody knows how it works. What is wrong with that? It is security through obscurity. The claim is unverifiable, because the cipher has not been reviewed by anybody able to attack it; and it is fragile, because a single disclosure or reverse engineering destroys all security at once, with no key to change. Published algorithms with secret keys fail more gracefully and can be evaluated.

4. Chosen ciphertext. The attacker can choose a ciphertext and obtain the matching decrypted plaintext, or at least learn whether decryption succeeded. Systems that report "bad padding" hand this over, and that one bit of feedback is enough to recover plaintext byte by byte. The chapter on cipher block chaining shows the mechanism.

5. Chosen text. Both 3 and 4 at once. The strongest attacker, and the model a modern cipher is expected to resist.

Two kinds of security, and the one that matters

Unconditionally secure. No amount of ciphertext, and no amount of computing, is enough to recover the plaintext, because the ciphertext simply does not contain enough information to determine it. Exactly one cipher in this syllabus is unconditionally secure, the one-time pad, and its chapter proves it.

Computationally secure. Either the cost of breaking the cipher exceeds the value of the information, or the time required to break it exceeds the useful lifetime of the information. Every other cipher in this book is in this class. Notice that both tests are about economics, not mathematics: a cipher protecting a share price for one minute needs far less than one protecting a medical record for fifty years.

This is why key length recommendations carry dates, and why NIST publishes transition schedules rather than permanent answers.

The cost of brute force, computed

The listing below takes the keyspaces of the ciphers in this syllabus and works out how long an exhaustive search takes at two speeds: one thousand million keys a second, which is roughly a single modern processor core, and one million million million keys a second, which is far beyond any machine that exists and is included to show that the large keyspaces do not care.

SECONDS_IN_YEAR = 365.25 * 24 * 60 * 60

def show(name, keyspace_bits, extra=""):
    keys = 2 ** keyspace_bits
    average = keys // 2
    for rate, label in ((10 ** 9, "1e9/s"), (10 ** 18, "1e18/s")):
        years = average / rate / SECONDS_IN_YEAR
        if years < 1 / 365.25:
            t = "%.3g seconds" % (average / rate)
        elif years < 1:
            t = "%.3g days" % (years * 365.25)
        else:
            t = "%.3g years" % years
        print("%-22s %4d bits  %-7s %s" % (name, keyspace_bits, label, t))
    if extra:
        print("%-22s %s" % ("", extra))

show("Caesar", 4.7, "25 keys in all, so the bits are only an analogy")
show("DES", 56)
show("two-key 3DES", 112)
show("AES-128", 128)
show("AES-256", 256)

Caesar                    4 bits  1e9/s   1.2e-08 seconds
Caesar                    4 bits  1e18/s  1.2e-17 seconds
                       25 keys in all, so the bits are only an analogy
DES                      56 bits  1e9/s   1.14 years
DES                      56 bits  1e18/s  0.036 seconds
two-key 3DES            112 bits  1e9/s   8.23e+16 years
two-key 3DES            112 bits  1e18/s  8.23e+07 years
AES-128                 128 bits  1e9/s   5.39e+21 years
AES-128                 128 bits  1e18/s  5.39e+12 years
AES-256                 256 bits  1e9/s   1.83e+60 years
AES-256                 256 bits  1e18/s  1.83e+51 years

Read four things out of that.

DES at one core is 1.14 years, which is why DES fell. Not because the number is large but because it is not large enough: a thousand such cores bring it to about ten hours, and at the fanciful rate in the second row it is thirty-six thousandths of a second. In 1998 a purpose-built machine did it in under three days, and the chapter on the strength of DES gives that machine's name and date.

AES-128 at a million million million keys a second is still more than five million million years. Brute force against a 128-bit key is not a matter of waiting for better hardware; the number does not come down within any span that means anything, and a machine running at a million million million keys a second does not exist.

The jump from 56 to 112 bits multiplies the time by about seventy-two thousand million million, from 1.14 years to 8.23e+16 years. Doubling a key length does not double the work, it squares the size of the keyspace, and that is the single most important intuition in this chapter.

The Caesar row is honest about being an analogy, and the printed bit count is not. The program was given 4.7 bits, which is 26 keys, and printed it with an integer format as 4; the timing beside it was computed from the 26. The timing is what matters: it is instantaneous, which is the point of the next chapter. It is also a small demonstration of why a number in a book should be produced by the program that printed it, because a bit count of 4 would be wrong and a reader would have no way to know.

A worked example: what an attacker actually does

The setup. An opponent captures ciphertext from a college portal. They do not know the cipher's key. They know, because the algorithm is published, that it is AES with a 128-bit key.

Step 1: consider brute force. From the table, out of the question.

Step 2: consider cryptanalysis of the algorithm. AES has been attacked publicly since 1998 and no attack materially better than brute force is known against the full cipher. So this route is closed too.

Step 3: attack something else. And this is the real lesson. The opponent stops attacking the cipher and attacks the key, the implementation or the person: a password that generates the key and can be guessed; a key stored in a file that is backed up to a public bucket; a timing difference in the implementation; a clerk who will read out a code over the telephone. Every successful real attack in Module 2 of this syllabus is of this kind.

The step that carries the marks. "The cipher is strong" and "the system is secure" are different claims. A question asking you to assess a system's security is not asking about AES's key length; it is asking where the weakest point is, and it is almost never the cipher.

Distinctions that carry marks

What beginners get wrong here

Brute force is not cryptanalysis. They are the two separate approaches in the definition, and a question that asks for "approaches to attacking a cipher" wants both, named and distinguished.

"On average half the keys" is part of the definition. Exhaustive search succeeds after half the keyspace on average, not after all of it, and the factor of two is worth stating because it is in the standard phrasing.

A large keyspace does not make a cipher strong. It makes brute force infeasible, which is a different claim. The monoalphabetic cipher of the next chapter but one has a keyspace of twenty-six factorial, which is far beyond brute force, and a schoolchild can break it with a pencil.

"Broken" rarely means "plaintext recovered". In cryptanalysis a cipher is considered broken when any attack does better than brute force, even if it is still far too expensive to run. That is why a cipher can be "broken" in a paper and still be safe to use for years, and why the retirement dates in the trend chapter lag the attacks.

Quick revision

• Two approaches: cryptanalysis (uses the algorithm's structure and knowledge of the plaintext) and brute force (tries every key; on average half of them).
• Five models, weakest attacker first: ciphertext only, known plaintext, chosen plaintext, chosen ciphertext, chosen text.
• Known plaintext is realistic because of fixed headers and formats. A modern cipher must resist chosen text.
• Unconditionally secure: only the one-time pad. Computationally secure: everything else, and the test is economic.
• Computed: DES 56 bits is about 1.14 years at a thousand million keys a second; AES-128 is beyond any machine.
• Doubling the key length squares the keyspace.
• A strong cipher does not make a secure system; the weak point is the key, the implementation or the person.
• "Broken" in cryptanalysis means "better than brute force", not "readable".

Test yourself

1. Name and distinguish the two general approaches to attacking a symmetric cipher. Cryptanalysis uses the nature of the algorithm together with knowledge of the general characteristics of the plaintext, or some plaintext and ciphertext pairs, to deduce a plaintext or the key. Brute force tries every possible key until an intelligible translation appears, and on average succeeds after half the keyspace. Cryptanalysis exploits design; brute force ignores it.

2. List the five attack models and what the attacker holds in each. Ciphertext only: the algorithm and ciphertext. Known plaintext: also one or more plaintext and ciphertext pairs under the same key. Chosen plaintext: also the ability to encrypt plaintext of their choice. Chosen ciphertext: also the ability to decrypt ciphertext of their choice, or to learn whether decryption succeeded. Chosen text: chosen plaintext and chosen ciphertext together.

3. Why is known plaintext a realistic model rather than a pessimistic one? Because real messages have predictable parts: standard headers, fixed salutations, file format signatures, repeated field names. An attacker who knows the message format therefore knows some plaintext before starting, without any special access.

4. Distinguish unconditionally secure from computationally secure, and name a cipher in each class. An unconditionally secure cipher cannot be broken however much ciphertext and computing power are available, because the ciphertext does not determine the plaintext; the one-time pad is the only example. A computationally secure cipher is one where the cost of breaking exceeds the value of the information or the time exceeds its useful life; DES, AES and RSA are all in this class.

5. Roughly how long does exhaustive search of a 56-bit key take at a thousand million keys a second, and what does that tell you about DES? About 1.14 years on average. It tells you DES was defensible in 1977 and indefensible once a thousand such processors, or a purpose-built machine, could be pointed at it, which is what happened in the 1990s. The cipher did not change; the cost of computing did.

6. Why does a large keyspace not by itself make a cipher strong? Because cryptanalysis does not search the keyspace. A monoalphabetic substitution has twenty-six factorial keys, which is far beyond brute force, and yet letter frequencies in the ciphertext reveal the mapping directly. Resistance to brute force and resistance to cryptanalysis are separate properties and both are required.

7. What does a cryptanalyst mean by saying a cipher is "broken"? That some attack performs better than exhaustive search, even if it remains far too expensive to carry out. It is a statement about the design rather than about present-day readability, which is why an algorithm can be broken in a paper years before it is formally withdrawn from use.

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

ENGLISH = {"E": 12.70, "T": 9.06, "A": 8.17, "O": 7.51, "I": 6.97, "N": 6.75,
           "S": 6.33, "H": 6.09, "R": 5.99, "D": 4.25, "L": 4.03, "C": 2.78,
           "U": 2.76, "M": 2.41, "W": 2.36, "F": 2.23, "G": 2.02, "Y": 1.97,
           "P": 1.93, "B": 1.29, "V": 0.98, "K": 0.77, "J": 0.15, "X": 0.15,
           "Q": 0.10, "Z": 0.07}

def shift(text, k):
    return "".join(ALPHABET[(ALPHABET.index(c) + k) % 26] if c in ALPHABET else c
                   for c in text.upper())

def fit(text):
    letters = [c for c in text if c in ALPHABET]
    n = len(letters)
    score = 0.0
    for c in ALPHABET:
        seen = letters.count(c)
        expected = ENGLISH[c] * n / 100
        score += (seen - expected) ** 2 / expected
    return score

ciphertext = "WKH TXHVWLRQ SDSHU OHDNHG IURP WKH SULQWHUV RQ WXHVGDB QLJKW"

results = sorted((fit(shift(ciphertext, -k)), k) for k in range(26))
print("the three best fits of all 26 shifts:")
for score, k in results[:3]:
    print("  k = %2d  score %7.1f  %s" % (k, score, shift(ciphertext, -k)))
print()
print("the three worst:")
for score, k in results[-3:]:
    print("  k = %2d  score %7.1f  %s" % (k, score, shift(ciphertext, -k)))

the three best fits of all 26 shifts:
  k =  3  score    29.3  THE QUESTION PAPER LEAKED FROM THE PRINTERS ON TUESDAY NIGHT
  k = 15  score    99.4  HVS EISGHWCB DODSF ZSOYSR TFCA HVS DFWBHSFG CB HISGROM BWUVH
  k = 16  score   189.3  GUR DHRFGVBA CNCRE YRNXRQ SEBZ GUR CEVAGREF BA GHRFQNL AVTUG

the three worst:
  k = 23  score  1455.7  ZNK WAKYZOUT VGVKX RKGQKJ LXUS ZNK VXOTZKXY UT ZAKYJGE TOMNZ
  k = 17  score  1750.7  FTQ CGQEFUAZ BMBQD XQMWQP RDAY FTQ BDUZFQDE AZ FGQEPMK ZUSTF
  k =  8  score  1952.9  OCZ LPZNODJI KVKZM GZVFZY AMJH OCZ KMDIOZMN JI OPZNYVT IDBCO

Read three things out of the run.

The right answer is first, and not narrowly. The correct shift scores 29.3 and the second best scores 99.4, more than three times worse. The gap is what makes the attack automatic: no human needs to read twenty-six candidates, the program can simply report the best.

A human would not have needed the score at all. The first line is English and the others are not, and that is the honest version of the attack: the scoring exists so that a machine can do what a person does at a glance.

Nothing about the cipher was used. The attack did not analyse the Caesar cipher's structure. It tried every key. That is brute force, and it is available here only because there are twenty-six keys and not because the cipher has any particular flaw.

A worked example in both directions

Encrypt ATTACK AT DAWN with a key of 11.

A is 0; 0 plus 11 is 11; 11 is L. T is 19; 19 plus 11 is 30; 30 modulo 26 is 4; 4 is E. C is 2, giving 13, which is N. K is 10, giving 21, which is V. D is 3, giving 14, which is O. W is 22; 22 plus 11 is 33; 33 modulo 26 is 7; 7 is H. N is 13, giving 24, which is Y.

So ATTACK AT DAWN becomes LEELNV LE OLHY.

Decrypt LEEL with the same key. L is 11; 11 minus 11 is 0, which is A. E is 4; 4 minus 11 is minus 7; minus 7 plus 26 is 19, which is T. So LEEL is ATTA, the opening of the plaintext, and the check works.

Note the two things that give the game away even without trying keys. The doubled EE in LEEL sits where TT sits in the plaintext, and the word lengths are preserved. A substitution cipher that keeps the spaces has handed the attacker the word structure of the message, which is a large part of the work.

Distinctions that carry marks

The affine cipher is worth knowing because it shows what enlarging a keyspace by tinkering achieves: 312 keys instead of 25 is thirteen times better and still nothing. Real improvement comes from changing the shape of the cipher, not from adding a parameter.

What beginners get wrong here

The key is not 26. A shift of 26 is a shift of 0 and leaves the message unchanged, so the useful keys are 1 to 25. Writing "26 possible keys" is the commonest slip in this topic.

Negative results must be brought back positive. Minus 2 modulo 26 is 24, not minus 2. Decryption is where this bites.

A big keyspace would not save this cipher. The affine cipher has 312 keys and is broken the same afternoon. Caesar's real problem, shared by every monoalphabetic cipher, is that it leaves the letter frequencies of the language intact, and the next chapter is about that.

Keeping the spaces is a real weakness. It is convenient for the example and helpful to the attacker, so a serious implementation removes spaces and punctuation and groups the output in fives.

Quick revision

• Caesar cipher: C = (p + k) mod 26, p = (C - k) mod 26, with k from 1 to 25.
• Keyspace 25, so brute force is instantaneous.
• Three facts that break it: the algorithm is known, there are only 25 keys, the plaintext language is recognisable.
• The program ranks candidates by a chi-squared fit to English letter frequencies; low is better. The right key scored 29.3 against 99.4 for the runner-up.
• Brute force uses nothing about the cipher's structure.
• Variants: multiplicative (p a) mod 26 with a coprime to 26, keyspace 12; affine (a p + k) mod 26, keyspace 312.
• A negative result in modular arithmetic is brought into range by adding 26.
• Preserving spaces preserves word lengths and helps the attacker.

Test yourself

1. Give the encryption and decryption rules of the Caesar cipher and the size of its keyspace. With the alphabet numbered A as 0 to Z as 25, encryption is C = (p + k) mod 26 and decryption is p = (C - k) mod 26. There are 25 useful keys, because a key of 0 or 26 leaves the message unchanged.

2. Encrypt CYBER with a key of 5. C is 2 giving 7, which is H. Y is 24; 24 plus 5 is 29; 29 modulo 26 is 3, which is D. B is 1 giving 6, which is G. E is 4 giving 9, which is J. R is 17 giving 22, which is W. The answer is HDGJW.

3. Decrypt WKLV with a key of 3. W is 22 giving 19, which is T. K is 10 giving 7, which is H. L is 11 giving 8, which is I. V is 21 giving 18, which is S. The plaintext is THIS.

4. State the three characteristics that make the Caesar cipher easy to break. The encryption and decryption algorithms are known; there are only 25 keys to try; and the language of the plaintext is known and easily recognised, so a correct decryption announces itself.

5. What is the affine cipher, how large is its keyspace, and why does that not help? It replaces p by (a * p + k) mod 26, where a must be coprime to 26 so that the mapping is reversible, giving 12 choices of a and 26 of k, so 312 keys. It does not help because 312 is still trivially small for brute force, and because the cipher remains monoalphabetic, so frequency analysis breaks it regardless of keyspace.

6. Why must the multiplier in a multiplicative cipher be coprime to 26? Because only then does multiplication by it permute the residues modulo 26, so that each plaintext letter maps to a distinct ciphertext letter and the mapping can be inverted. If the multiplier shares a factor with 26, several plaintext letters collide on one ciphertext letter and decryption is impossible.

7. Explain how the program in this chapter chooses among the 26 candidate decryptions. For each candidate it computes a chi-squared statistic: for every letter of the alphabet it takes the observed count, subtracts the count English would predict for a text of that length, squares the difference, divides by the predicted count and sums over all 26 letters. The candidate with the lowest total is the one whose letter distribution is closest to English, and in the run shown it was the correct key by a margin of more than three times.

plain  alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
cipher alphabet: EXAMINTOBCDFGHJKLPQRSUVWYZ

plaintext : THE SEAT NUMBERS FOR THE THEORY EXAMINATION WILL BE DISPLAYED ON THE NOTICE BOARD
ciphertext: ROI QIER HSGXIPQ NJP ROI ROIJPY IWEGBHERBJH VBFF XI MBQKFEYIM JH ROI HJRBAI XJEPM

the eight commonest letters of the ciphertext, with counts:
  I:10  R:7  J:6  B:5  E:5  H:5  O:4  P:4
English's own order begins: E T A O I N S H

total letters: 68

Note in passing how the keyword was reduced: EXAMINATION has repeated letters, and after dropping the repeats it contributes EXAMINTO, after which the alphabet fills in from B.

The break, step by step

Step 1: count the letters. The run above did it. I appears 10 times in 68 letters, R 7 times, J 6 times.

Step 2: match the top of the list to the top of English's list. English runs E, T, A, O, I, N, S, H. The ciphertext runs I, R, J, B and E tied, H, then O and P tied. So the first guesses are I stands for E and R stands for T, and both are correct: the cipher alphabet in the run maps E to I and T to R. Two letters of the key recovered from counting alone.

Step 3: use the structure, not only the counts. This is where the attack becomes fast, and where a machine is worse than a person.

• ROI appears three times and is the commonest three-letter group. With I as E and R as T, ROI is T?E, and the only sensible English word is THE. So O stands for H. Three letters recovered.
• XI is a two-letter word ending in E, so it is BE, ME, WE or HE. O is already H, so X stands for B, M or W.
• JH is a two-letter word whose second letter is H. Of the English two-letter words ending in a letter we have not placed, ON and IN are the candidates, so H stands for N and J for O or I. J was the third commonest letter, and English's fourth is O, so J stands for O. Five letters recovered.
• VBFF is a four-letter word with a doubled ending: WILL, WELL, FALL, TELL. I is taken by E's image, so the second letter is not E, and WILL fits. Eight letters recovered.

Step 4: read the rest off. With E, T, H, N, O, W, I and L in place, the ciphertext reads T?E SE?T N?M?E?S ?O? T?E T?EO?? E???IN?TION WILL ?E ?IS?L??E? ON T?E NOTI?E ?O???, and THE SEAT NUMBERS FOR THE THEORY EXAMINATION WILL BE DISPLAYED ON THE NOTICE BOARD is forced. The whole key follows.

The step that carries the marks. Steps 2 and 3 together. Frequency counts give you the start; digrams, trigrams, doubled letters and word lengths give you the rest. An answer that mentions only single-letter frequencies is describing a quarter of the attack.

What the attacker uses besides single letters

That table is the answer to "how is a monoalphabetic cipher broken", and it is worth more than a recital of the frequency percentages.

Distinctions that carry marks

The third table is the whole lesson. The monoalphabetic row is the one to remember, because it is the counter-example to "a long key means a strong cipher".

What beginners get wrong here

A large keyspace is not strength. Say it in the answer. This cipher has about 88 bits of key and is broken in an afternoon by hand.

Frequency analysis needs enough ciphertext. On a message of ten letters the counts mean nothing, and this is a real limitation, not a technicality: the attack needs a few hundred characters to be comfortable. A very short message under a monoalphabetic cipher may genuinely resist it.

Removing the spaces makes the attack harder, not impossible. It takes away the word lengths and the one-letter words, which is a real loss to the attacker. The digram and trigram counts survive, so the cipher still falls; it simply takes longer.

It is "monoalphabetic" because there is one cipher alphabet, not because there is one key. The word is about the number of substitution alphabets in use, which is what the polyalphabetic ciphers change.

Quick revision

• Monoalphabetic substitution: one fixed permutation of the alphabet, used throughout. Keyspace 26 factorial, which is 403,291,461,126,605,635,584,000,000, about 88 bits.
• Brute force does not break it. Frequency analysis does, because each letter keeps the plaintext language's frequency under a new name.
• The attack: count single letters, match to E T A O I N S H, then use digrams (TH, HE, IN, ER), trigrams (THE, AND, ING), doubled letters and word lengths.
• In the run: I was E at 10 of 68 letters and R was T at 7, both correct from counting alone; ROI then gave THE.
• A keyword builds a memorable permutation, at the cost of a much smaller effective keyspace.
• The lesson: resisting brute force and resisting cryptanalysis are different properties.
• Frequency analysis needs a few hundred characters; a very short message may resist it.

Test yourself

1. Define a monoalphabetic substitution cipher and state the size of its keyspace. It replaces each plaintext letter with a ciphertext letter according to a single fixed permutation of the alphabet, used for the whole message. The key is that permutation, so there are 26 factorial keys, which is 403,291,461,126,605,635,584,000,000.

2. Why is such a large keyspace no defence? Because the attack is not exhaustive search. A fixed substitution preserves the statistical structure of the plaintext: each letter of English appears in the ciphertext with the frequency it had in the plaintext, merely relabelled. Counting letters, digrams and trigrams therefore recovers the key directly, whatever the keyspace.

3. Describe the attack on a monoalphabetic cipher. Count the ciphertext letters and match the commonest to English's E, T, A, O, I, N, S, H to seed two or three guesses. Then use structure: the commonest trigram is almost always THE, the commonest digrams are TH, HE, IN and ER, a doubled ciphertext pair is one of LL, EE, SS, OO or TT, one-letter words are A or I, and common endings are ING, ED and TION. Fill letters in, read the partial plaintext, and the rest is forced.

4. Build the cipher alphabet from the keyword SECURITY. Write the keyword's distinct letters in order, S E C U R I T Y, then continue with the unused letters of the alphabet in order: A, B, D, F, G, H, J, K, L, M, N, O, P, Q, V, W, X, Z. The cipher alphabet is SECURITYABDFGHJKLMNOPQVWXZ.

5. Why does a keyword make the cipher weaker, even though the algorithm is unchanged? Because it reduces the effective keyspace from all 26 factorial permutations to the far smaller number that a memorable word can produce. An attacker can try likely keywords directly, which is a dictionary attack on the key rather than a search of the permutations.

6. What happens to the attack if the spaces are removed? The word lengths, one-letter words and common word endings are no longer visible, which removes several of the attacker's best clues and makes the work longer. Single-letter, digram and trigram frequencies are unaffected, so the cipher still falls; removing spaces raises the cost without changing the outcome.

7. Contrast monoalphabetic and polyalphabetic substitution in terms of what an attacker sees. Under a monoalphabetic cipher each plaintext letter always becomes the same ciphertext letter, so the ciphertext has the plaintext language's frequency profile with the labels changed, and frequency analysis applies immediately. Under a polyalphabetic cipher a plaintext letter becomes different ciphertext letters at different positions, which flattens the frequency profile; the attacker must first determine the key length and then apply frequency analysis to each column separately.

Preparation 2: if the plaintext has an odd number of letters, add a filler at the end.

Now the three rules. For a pair of plaintext letters:

Rule 1, same row. Replace each by the letter to its right, wrapping round from the last column to the first.

Rule 2, same column. Replace each by the letter below it, wrapping round from the bottom row to the top.

Rule 3, neither. Each letter is replaced by the letter in its own row and in the other letter's column. In other words, the two letters mark two corners of a rectangle and you take the other two corners, keeping each letter on its own row.

Rule 3 is the one that goes wrong, and it goes wrong in one specific way: students take the corners in the wrong order. The first ciphertext letter is on the first plaintext letter's row. Keeping to that removes the error entirely.

The program, which shows which rule it used

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def square(key):
    seen, out = set(), []
    for c in (key + ALPHABET).upper().replace("J", "I"):
        if c in ALPHABET and c not in seen:
            seen.add(c)
            out.append(c)
    return [out[r * 5:r * 5 + 5] for r in range(5)]

def digraphs(plain):
    t = "".join(c for c in plain.upper() if c in ALPHABET).replace("J", "I")
    pairs, i = [], 0
    while i < len(t):
        a = t[i]
        b = t[i + 1] if i + 1 < len(t) else "X"
        if a == b:
            pairs.append(a + "X")
            i += 1
        else:
            pairs.append(a + b)
            i += 2
    return pairs

def find(sq, c):
    for r in range(5):
        for k in range(5):
            if sq[r][k] == c:
                return r, k

def crypt(sq, pairs, step):
    out = []
    for a, b in pairs:
        ra, ca = find(sq, a)
        rb, cb = find(sq, b)
        if ra == rb:
            out.append(sq[ra][(ca + step) % 5] + sq[rb][(cb + step) % 5])
        elif ca == cb:
            out.append(sq[(ra + step) % 5][ca] + sq[(rb + step) % 5][cb])
        else:
            out.append(sq[ra][cb] + sq[rb][ca])
    return out

sq = square("MONARCHY")
print("the square for the keyword MONARCHY:")
for row in sq:
    print("   " + " ".join(row))
print()

plain = "BALLOON"
pairs = digraphs(plain)
print("plaintext  :", plain)
print("digraphs   :", " ".join(pairs))
enc = crypt(sq, pairs, +1)
print("ciphertext :", "".join(enc))
print()
print("rule used for each pair:")
for p, c in zip(pairs, enc):
    ra, ca = find(sq, p[0]); rb, cb = find(sq, p[1])
    if ra == rb:
        rule = "same row, move right"
    elif ca == cb:
        rule = "same column, move down"
    else:
        rule = "rectangle, swap columns"
    print("   %s -> %s   %s" % (p, c, rule))
print()
back = crypt(sq, [(c[0], c[1]) for c in enc], -1)
print("decrypted  :", "".join(back))

the square for the keyword MONARCHY:
   M O N A R
   C H Y B D
   E F G I K
   L P Q S T
   U V W X Z

plaintext  : BALLOON
digraphs   : BA LX LO ON
ciphertext : IBSUPMNA

rule used for each pair:
   BA -> IB   same column, move down
   LX -> SU   rectangle, swap columns
   LO -> PM   rectangle, swap columns
   ON -> NA   same row, move right

decrypted  : BALXLOON

Read four things out of the run.

BA is a same-column pair. B is in row 1, column 3; A is in row 0, column 3. Same column, so each moves down: B becomes I and A becomes B. This is the pair students misread, because B and A look like they should form a rectangle.

ON is a same-row pair. Both are in row 0, so each moves right: O becomes N and N becomes A. Notice that the ciphertext NA contains a letter from the plaintext, which is normal and not an error.

Two pairs used rule 3, and in both the first ciphertext letter came from the first plaintext letter's row: for LO, L is row 3 and O is column 1, giving row 3 column 1, which is P.

The decryption returns BALXLOON, not BALLOON. The filler X is still there. The receiver has to notice that LXL is not a word and remove the X. That is a genuine weakness of the scheme and a genuine examination trap: when asked to decrypt, remove the fillers and say that you did.

Decrypting

Decryption uses the same three rules with the direction reversed: same row, move left; same column, move up; rectangle, unchanged, because taking the other two corners twice returns you to where you started. That last point is worth stating in an answer, because it explains why rule 3 needs no reversal.

A second worked example, by hand

Encrypt HIDE THE GOLD with the same square.

Pairs: HI DE TH EG OL DX. The last pair needed a filler because the letter count is odd.

• HI: H is row 1 column 1, I is row 2 column 3. Rectangle. H takes row 1 column 3, which is B; I takes row 2 column 1, which is F. So BF.
• DE: D is row 1 column 4, E is row 2 column 0. Rectangle. D takes row 1 column 0, which is C; E takes row 2 column 4, which is K. So CK.
• TH: T is row 3 column 4, H is row 1 column 1. Rectangle. T takes row 3 column 1, which is P; H takes row 1 column 4, which is D. So PD.
• EG: E is row 2 column 0, G is row 2 column 2. Same row, move right: F and I. So FI.
• OL: O is row 0 column 1, L is row 3 column 0. Rectangle. O takes row 0 column 0, which is M; L takes row 3 column 1, which is P. So MP.
• DX: D is row 1 column 4, X is row 4 column 3. Rectangle. D takes row 1 column 3, which is B; X takes row 4 column 4, which is Z. So BZ.

Ciphertext: BFCKPDFIMPBZ.

What an attacker gets from the structure

Playfair leaks in ways worth knowing, because a question about its weaknesses expects more than "it is old".

A digram and its reverse give a ciphertext digram and its reverse. If AB encrypts to RS, then BA encrypts to SR. So the pairs AB and BA are visibly related in the ciphertext, and English has many such pairs (ER and RE, ON and NO, ES and SE).

No letter ever maps to itself. Every rule moves both letters, so a ciphertext letter is never in the same place as its plaintext letter. That halves the candidate space at every step.

Doubled letters cannot appear in the ciphertext. The preparation eliminated them from the plaintext, so LL never appears in the output. A ciphertext with no doubled letters at all is a signature of Playfair.

676 digrams, and about 600 keys' worth of square. Digram frequency analysis on a few hundred letters recovers enough of the square to guess the keyword, and the keyword then gives the rest.

Distinctions that carry marks

What beginners get wrong here

The order in rule 3. The first ciphertext letter stays on the first plaintext letter's row. Swapping them is the commonest error in this topic.

Forgetting to split a doubled pair. BALLOON is BA LX LO ON, not BA LL OO N. Missing the filler shifts every subsequent pair and destroys the answer.

Forgetting that I and J share a cell. A plaintext J becomes I before encryption, and on decryption an I may be either. The receiver decides from context.

Thinking Playfair is unbreakable because the frequencies look flat. They are flatter, not flat. A few hundred letters is enough.

Leaving the fillers in on decryption. The recovered text is BALXLOON, and the answer is BALLOON. Say that you removed it.

Quick revision

• Playfair: digram substitution using a 5 by 5 square from a keyword, I and J sharing a cell. Wheatstone, 1854.
• 676 digrams to disguise instead of 26 letters, so the letter frequencies are much flatter.
• Preparation: split a doubled pair with an X, and pad an odd length.
• Three rules: same row move right; same column move down; otherwise the other two corners, first ciphertext letter on the first plaintext letter's row.
• Decryption: left, up, and rule 3 unchanged.
• BALLOON under MONARCHY is IBSUPMNA, and decrypting gives BALXLOON: strip the filler.
• Leaks: a reversed digram gives a reversed ciphertext digram; no letter maps to itself; no doubled letters in the ciphertext.
• Broken by digram frequency analysis on a few hundred letters.

Test yourself

1. Construct the Playfair square for the keyword SECURITY. Row by row: S E C U R; I T Y A B; D F G H K; L M N O P; Q V W X Z. The keyword's distinct letters come first, then the remaining letters in order, with I and J sharing the I cell.

2. Encrypt MEET with the MONARCHY square. Pairs are ME and ET. M is row 0 column 0 and E is row 2 column 0, so they share a column: M becomes C and E becomes L, giving CL. E is row 2 column 0 and T is row 3 column 4, a rectangle: E takes row 2 column 4, which is K, and T takes row 3 column 0, which is L, giving KL. The ciphertext is CLKL.

3. Why is Playfair harder to break than a monoalphabetic cipher? Because it encrypts two letters at a time, so the attacker must work with 676 digrams rather than 26 letters, and digram frequencies are much flatter and need far more ciphertext to distinguish reliably. Single-letter frequency analysis, which breaks a monoalphabetic cipher at once, does not work.

4. State the three encryption rules and how each is reversed. Same row: move each letter one place right, wrapping; reversed by moving left. Same column: move each letter one place down, wrapping; reversed by moving up. Neither: take the other two corners of the rectangle, each ciphertext letter on its own plaintext letter's row; reversed by the same operation, because applying it twice returns the original.

5. What is done with a doubled letter in the plaintext, and what must the receiver do? A filler letter, conventionally X, is inserted between the two, so the pair is split. On decryption the receiver recovers the filler as part of the text and must remove it by inspection, since BALXLOON is plainly BALLOON.

6. Name three structural weaknesses of Playfair that help an attacker. A plaintext digram and its reverse encrypt to a ciphertext digram and its reverse, so related pairs are visible. No letter is ever encrypted to itself, which halves the possibilities at each step. Doubled letters never occur in the ciphertext, which both identifies the cipher and constrains the plaintext.

7. Why does rule 3 need no separate decryption rule? Because it maps the two letters to the other two corners of the same rectangle, each staying on its own row. Applying that operation to the ciphertext pair returns the original corners, so encryption and decryption are the same step.

key matrix K:
   17 17  5
   21 18 21
    2  2 19
det K mod 26 = 23 and its inverse mod 26 = 17
K inverse mod 26:
    4  9 15
   15 17  6
   24  0 17
plaintext : PAYMOREMONEY
ciphertext: LNSHDLEWMTRW
decrypted : PAYMOREMONEY

a key that cannot be used:
    6 24
    1 13
det = 2  gcd(det, 26) = 2  inverse = None
so this key encrypts and can never decrypt. Check it:
   AB encrypts to YN and so does NO

Read the second half of that run carefully, because it is the point of the chapter. The key with determinant 2 is a perfectly good-looking matrix. It encrypts happily. And AB and NO both come out as YN, so a receiver holding YN cannot know which was sent, and no amount of cleverness will help, because the information is gone. A Hill key whose determinant shares a factor with 26 is not weak; it is not a cipher at all.

Why the determinant must be coprime to 26

The inverse of a matrix modulo 26 is the modular inverse of its determinant, times the adjugate. So the inverse exists exactly when the determinant has a multiplicative inverse modulo 26, and a number has one exactly when it is coprime to 26. Since 26 is 2 times 13, the determinant must be odd and not a multiple of 13.

In the working key above the determinant is 23, which is coprime to 26, and its inverse is 17: you can check that 23 times 17 is 391, and 391 modulo 26 is 1, since 26 times 15 is 390.

A worked example on a 2 by 2, by hand

Take K as the matrix with first row 3, 3 and second row 2, 5, and encrypt HELP.

Step 1: the determinant. 3 times 5 minus 3 times 2 is 15 minus 6, which is 9. And 9 is coprime to 26, so the key can be used. The inverse of 9 modulo 26 is 3, because 9 times 3 is 27, which is 1 modulo 26.

Step 2: the first block, HE. H is 7 and E is 4.

• First ciphertext value: 3 times 7 plus 3 times 4, which is 21 plus 12, which is 33; 33 modulo 26 is 7, which is H.
• Second: 2 times 7 plus 5 times 4, which is 14 plus 20, which is 34; 34 modulo 26 is 8, which is I.

Step 3: the second block, LP. L is 11 and P is 15.

• First: 3 times 11 plus 3 times 15, which is 33 plus 45, which is 78; 78 modulo 26 is 0, which is A.
• Second: 2 times 11 plus 5 times 15, which is 22 plus 75, which is 97; 97 modulo 26 is 19, since 26 times 3 is 78 and 97 minus 78 is 19; 19 is T.

Ciphertext: HIAT.

Step 4: the inverse key. For a 2 by 2 matrix with entries a, b, c, d the adjugate has first row d, minus b and second row minus c, a. So here it is 5, minus 3 over minus 2, 3, which modulo 26 is 5, 23 over 24, 3. Multiply by 3, the inverse of the determinant: first row 15, 69 and second row 72, 9, which modulo 26 is 15, 17 over 20, 9.

Step 5: check. Decrypt HI: H is 7, I is 8. First: 15 times 7 plus 17 times 8, which is 105 plus 136, which is 241; 241 modulo 26 is 7, since 26 times 9 is 234; and 7 is H. Second: 20 times 7 plus 9 times 8, which is 140 plus 72, which is 212; 212 modulo 26 is 4, since 26 times 8 is 208; and 4 is E. So HI decrypts to HE, which is right.

The known-plaintext attack, worked

The setup. An attacker knows the cipher is Hill with m of 2, and has two plaintext and ciphertext block pairs. Say the attacker knows that HE encrypted to HI and LP encrypted to AT, which is exactly what the example above produced.

Step 1: write the pairs as matrices. Put the plaintext blocks as the columns of a matrix P and the matching ciphertext blocks as the columns of C:

• P has first column 7, 4 (for H, E) and second column 11, 15 (for L, P).
• C has first column 7, 8 (for H, I) and second column 0, 19 (for A, T).

Step 2: the relation. Since C = K P mod 26 for every column, the whole matrices satisfy the same equation. So if P is invertible modulo 26,

Step 3: invert P. Its determinant is 7 times 15 minus 11 times 4, which is 105 minus 44, which is 61; 61 modulo 26 is 9. The inverse of 9 modulo 26 is 3. The adjugate is 15, minus 11 over minus 4, 7, which is 15, 15 over 22, 7 modulo 26. Times 3: 45, 45 over 66, 21, which modulo 26 is 19, 19 over 14, 21.

Step 4: multiply. C times that inverse gives, entry by entry modulo 26: first row is 7 times 19 plus 0 times 14, which is 133, which is 3; and 7 times 19 plus 0 times 21, which is also 3. Second row: 8 times 19 plus 19 times 14, which is 152 plus 266, which is 418, and 418 modulo 26 is 2, since 26 times 16 is 416; and 8 times 19 plus 19 times 21, which is 152 plus 399, which is 551, and 551 modulo 26 is 5, since 26 times 21 is 546.

So K comes out with first row 3, 3 and second row 2, 5, which is the key. The attacker now has the whole key from four letters of known plaintext.

Step 5: what if P is not invertible? The attacker simply uses a different pair of blocks. Any two blocks whose plaintext matrix is invertible will do, and in a message of any length there are plenty.

The step that carries the marks. m squared known plaintext letters, arranged into an invertible matrix, give the whole key by one matrix inversion. Making m larger does not help, because the attacker only needs m squared letters and a longer message contains more of them. Linearity is the flaw, and no choice of key repairs it.

Distinctions that carry marks

The right-hand column of the second table is one idea in three dresses: a cipher must be a bijection, and each condition is what makes it one.

What beginners get wrong here

Forgetting to check the determinant. A matrix chosen at random has about a one in four chance of being unusable, because it needs to be both odd and not a multiple of 13. Always compute the determinant and its gcd with 26 first.

Taking the inverse over the real numbers. The inverse here is modulo 26, so the reciprocal of the determinant is its modular inverse, an integer, not a fraction. Writing one twenty-third is wrong.

Negative entries in the adjugate. Minus 3 modulo 26 is 23. Bring every entry into the range 0 to 25 before multiplying.

Claiming Hill is strong. It is strong against a ciphertext-only attacker and worthless against a known-plaintext one, and an answer must say which.

Confusing m with the key size. The key has m squared entries, so a 3 by 3 key is nine numbers, and the attacker needs nine known plaintext letters, not three.

Quick revision

• Hill cipher, Lester Hill 1929: C = K P mod 26, P = K inverse C mod 26, blocks of m letters, key an m by m matrix.
• The key must be invertible modulo 26, which means det K must be coprime to 26, so odd and not a multiple of 13.
• The inverse is (modular inverse of the determinant) times the adjugate, all modulo 26.
• Worked: K with rows 17 17 5, 21 18 21, 2 2 19 has determinant 23, inverse of determinant 17, and PAYMOREMONEY encrypts to LNSHDLEWMTRW.
• A bad key is not weak but broken: with determinant 2, AB and NO both encrypt to YN.
• Hill completely conceals single-letter frequencies for m of 3 or more.
• It falls to a known-plaintext attack: K = C P inverse, needing m squared known plaintext letters.
• The flaw is linearity, and a larger m does not fix it.

Test yourself

1. State the Hill cipher's encryption and decryption rules, and the condition on the key. C = K P mod 26 and P = K inverse C mod 26, where P and C are column vectors of m letter values and K is an m by m matrix. The key must be invertible modulo 26, which requires its determinant to be coprime to 26, that is odd and not a multiple of 13.

2. For the 2 by 2 key with rows 3, 3 and 2, 5, encrypt HELP. The determinant is 9, which is coprime to 26, so the key is usable. HE is 7, 4: the first value is 21 plus 12, which is 33, giving 7 or H; the second is 14 plus 20, which is 34, giving 8 or I. LP is 11, 15: the first is 33 plus 45, which is 78, giving 0 or A; the second is 22 plus 75, which is 97, giving 19 or T. The ciphertext is HIAT.

3. Find the inverse of that key modulo 26. The determinant is 9 and its inverse modulo 26 is 3, since 27 is 1 modulo 26. The adjugate is 5, minus 3 over minus 2, 3, which is 5, 23 over 24, 3 modulo 26. Multiplying by 3 gives 15, 69 over 72, 9, which reduces to 15, 17 over 20, 9.

4. Why must the determinant be coprime to 26, and what goes wrong if it is not? Because the matrix inverse modulo 26 requires the modular inverse of the determinant, which exists only for values coprime to 26. If it is not, the map is not one to one: distinct plaintext blocks collide on the same ciphertext block. Under the key with rows 6, 24 and 1, 13, whose determinant is 2, both AB and NO encrypt to YN, so decryption is impossible in principle.

5. Describe the known-plaintext attack on the Hill cipher. Collect m squared known plaintext letters, that is m block pairs. Arrange the plaintext blocks as the columns of a matrix P and the matching ciphertext blocks as the columns of C. Since C = K P mod 26, the key is K = C P inverse mod 26, provided P is invertible modulo 26; if it is not, choose different blocks. One matrix inversion recovers the whole key.

6. Why does increasing m not protect against that attack? Because the attacker needs m squared known plaintext letters, and any message long enough to be worth attacking contains far more than that. Increasing m strengthens the cipher only against a ciphertext-only attacker; the linear structure that makes the known-plaintext attack work is unchanged.

7. What does the Hill cipher achieve that Playfair does not? For m of 3 or more it completely conceals single-letter frequency information, because every ciphertext letter depends on three or more plaintext letters, and it conceals digram frequencies as well. Playfair flattens the single-letter frequencies but leaves digram structure that a few hundred letters of ciphertext is enough to exploit.

Breaking it: find the key length first

A polyalphabetic cipher is a set of monoalphabetic ciphers interleaved. So if you know the key length, you have already won: take every ninth letter of the ciphertext and you have a monoalphabetic cipher on that column, which the chapter on frequency analysis broke. The whole attack therefore reduces to finding the key length.

There are two classical methods.

Kasiski's method. If two identical plaintext sequences happen to line up with the same part of the key, they produce identical ciphertext sequences. So look for repeated sequences of three or more letters in the ciphertext, measure the distances between them, and the key length is likely to be a common factor of those distances. In the example above, the sequence VTW appears twice, nine letters apart, and the key is nine letters long.

The index of coincidence. This one is more reliable and is what the program below uses. The index of coincidence of a text is the probability that two letters drawn at random from it are the same letter. For English it is about 0.0667, because English is lumpy. For a text whose letters are uniformly spread it is 1 in 26, which is about 0.0385.

Now the trick. Guess a key length m. Split the ciphertext into m columns, taking every mth letter. If the guess is right, each column was enciphered with a single shift, so each column is a monoalphabetic cipher on English and its index of coincidence should be close to English's 0.0667. If the guess is wrong, the columns mix several shifts and their index will be near 0.0385.

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def letters(s):
    return "".join(c for c in s.upper() if c in ALPHABET)

def vigenere(text, key, sign=1):
    t, k = letters(text), letters(key)
    return "".join(ALPHABET[(ALPHABET.index(t[i])
                             + sign * ALPHABET.index(k[i % len(k)])) % 26]
                   for i in range(len(t)))

def ic(s):
    t = letters(s)
    n = len(t)
    if n < 2:
        return 0.0
    return sum(t.count(c) * (t.count(c) - 1) for c in set(t)) / (n * (n - 1))

plain = "wearediscoveredsaveyourself"
key = "deceptive"
cipher = vigenere(plain, key)
print("plaintext :", letters(plain))
print("key       :", (letters(key) * 4)[:len(letters(plain))])
print("ciphertext:", cipher)
print("decrypted :", vigenere(cipher, key, -1))
print()

long_plain = ("the examination section will publish the seat numbers for the theory "
              "papers on the college notice board and on the college website before "
              "the end of this month so that every student can check the hall and the "
              "date of each paper well before the examination begins")
long_cipher = vigenere(long_plain, "deceptive")
print("index of coincidence of the plaintext :", "%.4f" % ic(long_plain))
print("index of coincidence of the ciphertext:", "%.4f" % ic(long_cipher))
print("English is about 0.0667, a flat random text about 0.0385")
print()
print("average index of coincidence of the columns, for each assumed key length:")
best = []
for m in range(1, 13):
    cols = [long_cipher[i::m] for i in range(m)]
    avg = sum(ic(c) for c in cols) / m
    best.append((avg, m))
    print("   length %2d  %.4f" % (m, avg))
best.sort(reverse=True)
print()
print("the three highest:", ", ".join("%d (%.4f)" % (m, a) for a, m in best[:3]))
print("the real key length is", len("deceptive"))

plaintext : WEAREDISCOVEREDSAVEYOURSELF
key       : DECEPTIVEDECEPTIVEDECEPTIVE
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ
decrypted : WEAREDISCOVEREDSAVEYOURSELF

index of coincidence of the plaintext : 0.0736
index of coincidence of the ciphertext: 0.0409
English is about 0.0667, a flat random text about 0.0385

average index of coincidence of the columns, for each assumed key length:
   length  1  0.0409
   length  2  0.0395
   length  3  0.0473
   length  4  0.0397
   length  5  0.0401
   length  6  0.0444
   length  7  0.0393
   length  8  0.0402
   length  9  0.0717
   length 10  0.0392
   length 11  0.0419
   length 12  0.0419

the three highest: 9 (0.0717), 3 (0.0473), 6 (0.0444)
the real key length is 9

Read four things out of that run.

The cipher did its job. The plaintext's index of coincidence is 0.0736, a little above English's average because this passage repeats words like "the" and "examination". The ciphertext's is 0.0409, close to flat random. Frequency analysis on the ciphertext as a whole is dead.

Key length 9 stands out, and by a wide margin. 0.0717 against 0.0473 for the next best. This is what makes the method practical: you do not need judgement, you take the largest.

The second best is a divisor of the answer, and that is not a coincidence. Length 3 scores 0.0473 because 3 divides 9: splitting into three columns groups key positions 1, 4 and 7 together, so each column mixes three shifts rather than nine and is lumpier than random even though the guess is wrong. So a divisor of the true length scores above the ordinary run, and the rule for reading the table is to take the largest good score, not the first: if 3 were taken as the answer, 9 would be missed. Length 6 at 0.0444 is not a divisor of 9 and is simply noise, which is the honest caution: on a sample of 216 letters the low scores sit between 0.0392 and 0.0444 and a single value in that band means nothing.

0.0717 is above English's 0.0667, which looks wrong and is not. Each column is a monoalphabetic cipher on a sample of only twenty-four letters, and the index of coincidence of a small sample is noisy. The method finds the key length; it does not measure English precisely.

After the key length: recovering the key

Once the length is 9, take column 0, which is every ninth ciphertext letter starting at the first. It was produced by shifting English by one fixed amount, so run the Caesar break of the earlier chapter on it: try all 26 shifts and take the one whose letter frequencies fit English best. That gives the first letter of the keyword. Repeat for the other eight columns. The whole key falls out, and with it the message.

This is why the length of the keyword matters so much. A keyword of length 9 on the 216-letter message above gives each column 24 letters, which is thin but workable. A keyword as long as the message gives each column one letter, and then there is nothing to count, which is the one-time pad of the next chapter.

The autokey cipher: the improvement that does not work

Vigenere himself proposed a better scheme. The trouble with a repeating keyword is exactly that it repeats, so use the plaintext itself to extend the key: start with the keyword and then continue with the plaintext.

key        D E C E P T I V E W E A R E D I S C O V E R E D S A V
plaintext  W E A R E D I S C O V E R E D S A V E Y O U R S E L F
ciphertext Z I C V T W Q N G K Z E I I G A S X S T S L V V W L A

There is now no period at all, so Kasiski's method and the index of coincidence both have nothing to find. And the cipher is still broken, because the key is English. The attacker guesses a short piece of key, decrypts a few letters, and if the result is English then those plaintext letters are also key letters further along, which decrypt more, which give more key. The attack propagates through the message from any correct guess. The statistical structure of the plaintext leaked into the key, and that is fatal.

The lesson is worth an answer of its own: removing the period is not enough. The key must also be unpredictable.

Distinctions that carry marks

What beginners get wrong here

Thinking Vigenere is unbreakable. It was called le chiffre indechiffrable for three hundred years and it is broken by a schoolchild with a spreadsheet. Any answer claiming it is secure is wrong.

Forgetting to find the key length first. The attack is two stages, and the first stage is the whole difficulty. An answer that jumps to "then use frequency analysis" has skipped the part being examined.

Reading the index of coincidence backwards. A high index means lumpy, English-like text, so a high score means the guessed length is right. Low means flat and wrong.

Taking the smallest good score as the key length. A divisor of the true length scores well too, so take the largest clear winner and treat a smaller good score as a hint that its multiple is the answer.

Thinking the autokey cipher is a real improvement. It removes the period and keeps the predictability, which is the wrong half of the problem to solve.

Quick revision

• Polyalphabetic: several cipher alphabets, selected by the key. Vigenere: C = (p + k) mod 26 with k the key letter, keyword repeated.
• The keyword's length is the period, and the ciphertext's letter frequencies are flattened towards 1 in 26.
• Break in two stages: find the key length, then solve each column as a Caesar cipher.
• Kasiski: repeated three-letter sequences; the key length divides the distances between them.
• Index of coincidence: the chance two random letters are equal. English about 0.0667, flat text about 0.0385. Split into m columns and take the m with the highest average.
• In the run, the true length 9 scored 0.0717 and its divisor 3 scored 0.0473, so take the largest clear winner; the other low scores sat between 0.0392 and 0.0444 and mean nothing individually.
• Autokey: keyword then plaintext, no period, still broken, because the key is English. Removing the period is not enough: the key must be unpredictable.

Test yourself

1. Define a polyalphabetic cipher and give the Vigenere rule. A cipher that uses a set of related monoalphabetic substitution rules, with the key selecting which rule applies at each position. In Vigenere the key is a keyword repeated to the message length, and each plaintext letter is shifted by the value of the key letter above it: C = (p + k) mod 26, with decryption p = (C - k) mod 26.

2. Encrypt CIPHER with the keyword KEY. The key stream is K E Y K E Y, that is 10, 4, 24, 10, 4, 24. C is 2 giving 12, which is M. I is 8 giving 12, which is M. P is 15; 15 plus 24 is 39; 39 modulo 26 is 13, which is N. H is 7 giving 17, which is R. E is 4 giving 8, which is I. R is 17; 17 plus 24 is 41; 41 modulo 26 is 15, which is P. The ciphertext is MMNRIP.

3. Why does Vigenere defeat simple frequency analysis? Because one plaintext letter is enciphered with different shifts at different positions, so its frequency is spread over as many ciphertext letters as the key is long. The ciphertext's letter distribution flattens towards uniform, and the correspondence between a ciphertext letter's count and a plaintext letter is destroyed.

4. What is the index of coincidence, and what are its values for English and for random text? The probability that two letters drawn at random from a text are the same letter. For English it is about 0.0667; for text whose letters are uniformly distributed it is 1 in 26, about 0.0385.

5. How is the index of coincidence used to find the key length? Guess a length m, split the ciphertext into m columns by taking every mth letter, and average the index of coincidence of the columns. If m is right each column is a single-shift cipher on English and the average is high; if m is wrong the columns mix shifts and the average is near 0.0385. The best-scoring m is the key length, and its divisors also score above the rest, which confirms the answer.

6. Describe Kasiski's method. Find sequences of three or more letters that repeat in the ciphertext. Such a repetition usually arises because the same plaintext lined up with the same part of the key, so the distance between the two occurrences is a multiple of the key length. Taking the common factors of several such distances gives the key length.

7. What is the autokey cipher, and why is it still broken? The key is the keyword followed by the plaintext itself, so the key never repeats and there is no period for Kasiski or the index of coincidence to find. It is broken because the key is ordinary English and therefore predictable: a correct guess at a short stretch of key reveals plaintext, and that plaintext is itself key material further along, so a single correct guess propagates through the whole message.

plaintext : ATTACKATDAWN
pad       : XMCKLXMCKLAB
ciphertext: XFVKNHMVNLWO
decrypted : ATTACKATDAWN

the proof of perfect secrecy: one ciphertext, two plausible plaintexts
   a pad of GBCTJHTVUSSB turns XFVKNHMVNLWO into RETREATATTEN
   a pad of FBIHUHZLVYIS turns XFVKNHMVNLWO into SENDTANKSNOW

both pads are the same length and look equally random, so the ciphertext
cannot tell an attacker which one was used.

what a reused pad gives away:
   c1 = KXRKGIKXBKAL
   c2 = RSJNTMCMRSSL
   c1 - c2 = TFIXNWILKSIA which is p1 - p2 and has no key in it at all
   p1 - p2 = TFIXNWILKSIA so the two agree: True

Read the middle block of that run again, because it is the whole chapter. One ciphertext, XFVKNHMVNLWO. Three different twelve-letter military orders, all consistent with it, each with its own perfectly ordinary-looking pad. An attacker who captures the ciphertext and knows that it is a one-time pad knows the length of the message and nothing else. There is no computation that helps, because the information is not there. Contrast every other cipher in this book, where the right key produces English and the wrong keys produce rubbish: that difference is exactly what a cryptanalyst exploits, and the one-time pad does not offer it.

Why it is almost never usable

The one-time pad is unbreakable and is used for almost nothing. The three conditions are the reason.

The key must be as long as the message. To send a megabyte you must first have securely delivered a megabyte of key. But if you had a secure channel for a megabyte of key, you could have sent the message down it. The cipher does not remove the need for a secure channel, it only moves it in time, and that is useful only when a courier can carry the key in advance.

The key must be truly random. Not the output of a program, which is predictable to anybody who knows the program and its starting state, but physically random: radioactive decay, thermal noise, electronic noise. A pad generated by a random number generator is not a one-time pad, it is a stream cipher, and stream ciphers are computationally secure at best.

The key must never be used twice. The last block of the run shows what happens if it is. Subtract the two ciphertexts and the key cancels exactly, leaving the difference of the two plaintexts, which is a cipher with no key at all and falls to ordinary analysis. c1 - c2 came out TFIXNWILKSIA and so did p1 - p2: the program checked that the two are equal, and they are.

That failure is not hypothetical. Reusing key material is one of the most productive real attacks there has ever been against systems that were otherwise sound, and it is exactly the mistake that broke WEP's use of RC4, which the chapter on stream ciphers takes up.

Where it is genuinely used: a diplomatic or military link where a courier can deliver key material in advance, and the volume of traffic is small. Historically, the Moscow to Washington hot line. Nothing on a campus network qualifies.

A worked example in the bit form

Encrypt the byte 01001000, which is the letter H in ASCII, with the key byte 11010110.

Line them up and exclusive-or bit by bit. Exclusive-or gives 1 when the two bits differ and 0 when they are the same.

plaintext  0 1 0 0 1 0 0 0
key        1 1 0 1 0 1 1 0
ciphertext 1 0 0 1 1 1 1 0

Decrypt by applying the same key to the ciphertext.

ciphertext 1 0 0 1 1 1 1 0
key        1 1 0 1 0 1 1 0
plaintext  0 1 0 0 1 0 0 0

The plaintext is back, and the second table is the same operation as the first. That is what "exclusive-or is its own inverse" buys, and it is why every stream cipher in this book, and the counter and output feedback modes of block ciphers, all end in an exclusive-or with a key stream.

Distinctions that carry marks

The third table is the most useful one, because it shows that the one-time pad is not a different kind of cipher from Vigenere at all. It is Vigenere with the period pushed out to the length of the message and the key made random, and that alone takes it from breakable to unbreakable.

What beginners get wrong here

"Unbreakable" is a claim about information, not about difficulty. The one-time pad is not hard to break; it is impossible, because the ciphertext does not determine the plaintext. Saying "it would take too long" describes AES, not this.

A pad generated by software is not a one-time pad. It is a stream cipher whose key is the seed. The security then rests on the generator, which is a computational assumption.

Perfect secrecy says nothing about integrity. An attacker who cannot read a one-time pad ciphertext can still flip a bit of it, and the corresponding bit of the plaintext flips too. Worse, an attacker who knows the plaintext can change it to any other plaintext of the same length by exclusive-oring in the difference. The pad gives confidentiality alone, and this is why authenticated encryption exists.

The key distribution problem is not solved, only moved. The pad needs a secure channel for as many bits as the message. That is why public-key cryptography had to be invented.

Quick revision

• Vernam, 1917: c = p XOR k. One-time pad: Vernam with a key that is random, as long as the message, and used once.
• Shannon, 1949: the one-time pad has perfect secrecy and is unconditionally secure. It is the only such cipher here.
• Perfect secrecy means every plaintext of the same length is equally consistent with the ciphertext; the run produced the pads for two different plausible messages from one ciphertext.
• Exclusive-or is its own inverse, so encryption and decryption are the same operation.
• Reusing a pad: c1 - c2 equals p1 - p2, the key cancels, and both are gone. Proved in the run.
• Not usable in general because the key is as long as the message, must be physically random, and must never repeat.
• It gives confidentiality only. Flip a ciphertext bit and the plaintext bit flips; knowing the plaintext lets an attacker substitute any other of the same length.
• Used where a courier can deliver key in advance and traffic is small.

Test yourself

1. What are the three conditions for a one-time pad, and what do they buy? The key must be truly random, at least as long as the message, and used only once. Together they give perfect secrecy: the ciphertext carries no information about the plaintext, so the cipher is unconditionally secure and cannot be broken by any amount of computation.

2. State what perfect secrecy means, and how it can be demonstrated. That for a given ciphertext every plaintext of the same length is equally possible, so holding the ciphertext leaves the attacker exactly as informed as before. It is demonstrated by taking one ciphertext and, for any chosen plaintext of the same length, producing the key that makes the one decrypt to the other: subtract the plaintext from the ciphertext. Since every such key is as plausible as any other, the ciphertext cannot distinguish the messages.

3. Encrypt the bits 10110010 with the key 01101001 and then decrypt the result. Exclusive-or gives 11011011. Applying the same key to that gives 10110010, the original, because exclusive-or is its own inverse.

4. What happens if a one-time pad is used twice, and why? Subtracting the two ciphertexts removes the key entirely, because the same key was added to both, and leaves the difference of the two plaintexts. That difference is a cipher with no key, and can be attacked by ordinary language analysis. The run in this chapter checked it: c1 - c2 and p1 - p2 came out identically as TFIXNWILKSIA.

5. Why is the one-time pad rarely used despite being unbreakable? Because the key must be as long as the message and delivered securely in advance, so it does not remove the need for a secure channel but only shifts it in time; and because a truly random key must come from a physical source rather than from a program. It is practical only where key material can be couriered ahead and traffic volumes are small.

6. Is a stream cipher with a pseudorandom key stream a one-time pad? Justify. No. The key stream is generated from a short seed by a deterministic algorithm, so it is predictable to anybody who learns the seed and the algorithm, and the number of possible key streams is limited by the number of seeds. Security then rests on a computational assumption about the generator, which makes the cipher computationally secure at best rather than unconditionally secure.

7. Does a one-time pad protect integrity? Explain with an example. No. It gives confidentiality only. Flipping any bit of the ciphertext flips the corresponding bit of the recovered plaintext, and an attacker who knows the plaintext can exclusive-or in the difference between it and any other message of the same length, so the recipient decrypts to whatever the attacker chose. Integrity therefore needs a separate mechanism such as a message authentication code.

rail fence, depth 2
   plaintext: MEETMEAFTERTHETOGAPARTY
   row 0    : M E M A T R H T G P R Y
   row 1    : E T E F E T E O A A T
   ciphertext: MEMATRHTGPRYETEFETEOAAT

rail fence, depth 3
   row 0    : M M T H G R
   row 1    : E T E F E T E O A A T
   row 2    : E A R T P Y
   ciphertext: MMTHGRETEFETEOAATEARTPY

row transposition, key 4312567
   key  : 4 3 1 2 5 6 7
   row  : A T T A C K P
   row  : O S T P O N E
   row  : D U N T I L T
   row  : W O A M X X X
   read the columns in the order 1 2 3 4 5 6 7:
   ciphertext: TTNAAPTMTSUOAODWCOIXKNLXPETX

the same transposition applied twice: NSCXAUOPTTWLTMDNAOIEPAXTTOKX

a transposition preserves the letter counts exactly:
   plaintext : {'A': 3, 'E': 5, 'F': 1, 'G': 1, 'H': 1, 'M': 2, 'O': 1, 'P': 1, 'R': 2, 'T': 5, 'Y': 1}
   ciphertext: {'A': 3, 'E': 5, 'F': 1, 'G': 1, 'H': 1, 'M': 2, 'O': 1, 'P': 1, 'R': 2, 'T': 5, 'Y': 1}
   equal: True

Read four things out of that run.

Depth 3 does not fill the rows evenly. Row 1, the middle row, gets eleven letters while rows 0 and 2 get six each, because the zigzag passes through the middle on the way down and again on the way up. A student drawing this by hand must count the letters per row before reading them off, or the ciphertext will be wrong.

The row transposition grid needed padding. attackpostponeduntiltwoam is twenty-five letters and the key has seven columns, so three X's were added. Say so in an answer: the padding is part of the method.

The ciphertext is read column by column, in the order the key gives. The key 4312567 means the first column is labelled 4, the second 3, the third 1, and so on. So the third column is read first, because it is labelled 1. That is the step that goes wrong: the key gives each column a label, and you read in label order, not in key order.

The letter counts are equal, exactly. The two dictionaries are identical. This is the identifying signature of a transposition and the answer to "how would you recognise a transposition cipher from its ciphertext".

Row transposition, by hand

Encrypt ATTACK POSTPONED UNTIL TWO AM with the key 4312567.

Step 1: write the key across the top and the plaintext in rows beneath it, seven letters to a row.

key         4 3 1 2 5 6 7
row 1       A T T A C K P
row 2       O S T P O N E
row 3       D U N T I L T
row 4       W O A M X X X

Step 2: pad. Twenty-five letters into rows of seven leaves the last row three short, so three X's are added. The grid is now full.

Step 3: read the columns in the order of their labels. Column labelled 1 is the third column, reading down: T, T, N, A. Column 2 is the fourth: A, P, T, M. Column 3 is the second: T, S, U, O. Column 4 is the first: A, O, D, W. Column 5 is the fifth: C, O, I, X. Column 6 is the sixth: K, N, L, X. Column 7 is the seventh: P, E, T, X.

Ciphertext: TTNA APTM TSUO AODW COIX KNLX PETX, which run together is TTNAAPTMTSUOAODWCOIXKNLXPETX, exactly what the program printed.

To decrypt, do it backwards: the ciphertext length divided by the number of columns gives the number of rows, four here; cut the ciphertext into four-letter pieces; write the first piece down the column labelled 1, the second down the column labelled 2, and so on; then read the grid across.

Breaking a transposition

Step 1: recognise it. Count the letters. If the frequencies match the language's, it is a transposition and not a substitution. That single test decides which family of attacks to use, and it is why the program prints the counts.

Step 2: guess the block length. Try each possible number of columns. The correct one is usually recognisable because plausible digrams and trigrams start appearing when the columns are correctly grouped.

Step 3: rearrange. With the block length known, the problem is to find the permutation, and the tool is digram and trigram frequency: try orders of the columns and score the result by how many common English digrams it produces. For a seven-column key there are only 5,040 orders, so this is a small search.

Step 4: if it is a double transposition, the work is much greater, which is why double transposition was used seriously in both World Wars. The program applied the same key twice and got NSCXAUOPTTWLTMDNAOIEPAXTTOKX, which is not the plaintext and not the single ciphertext either: composing a permutation with itself gives another permutation, and a much less structured one. A single transposition leaves letters that were adjacent in the plaintext still fairly close together in the ciphertext; a double one does not, which is exactly the diffusion the attacker was relying on.

Distinctions that carry marks

What beginners get wrong here

Reading the columns in the wrong order. The key labels the columns; you read in label order. With key 4312567 the first column read is the third one.

Forgetting to pad, or forgetting to say you padded. An unfilled last row makes the columns unequal and the decryption ambiguous.

Miscounting the rail fence rows at depth 3 or more. The middle rows hold about twice as many letters as the top and bottom rows.

Thinking a transposition hides anything about letter frequencies. It hides nothing at all about them, which is a complete giveaway and the reason transposition alone is never used.

Assuming a double transposition with the same key undoes itself. It does not. A permutation composed with itself is a different permutation, and the run shows the result.

Quick revision

• Transposition: permute the positions, change no symbol. Letter frequencies are identical to the plaintext's, which is how you recognise one.
• Rail fence: write in a zigzag over depth rows, read off row by row. The key is the depth, so the keyspace is tiny.
• Row transposition: write in rows of n, read the columns in the order the key labels them. Pad the last row.
• With key 4312567, ATTACKPOSTPONEDUNTILTWOAM becomes TTNAAPTMTSUOAODWCOIXKNLXPETX.
• Decrypt by computing the number of rows, cutting the ciphertext into that many letters per piece, and writing each piece down its labelled column.
• Break it by recognising the frequencies, guessing the block length, then searching column orders with digram scores.
• Double transposition is much stronger and was used in both World Wars; applying the same key twice gives a new permutation, not the identity.
• Substitution gives confusion, transposition gives diffusion, and a strong cipher needs both.

Test yourself

1. Define a transposition cipher and state how a ciphertext reveals that one was used. It permutes the positions of the plaintext symbols without replacing any symbol by another. Because no symbol changes, the letter frequencies of the ciphertext are exactly those of the plaintext, so a ciphertext whose letter counts match the language's ordinary profile is the product of a transposition rather than a substitution.

2. Encrypt DEFEND THE EAST WALL with a rail fence of depth 2. The letters are DEFENDTHEEASTWALL. Row 0 takes the letters in odd positions, D, F, N, T, E, A, T, A, L, and row 1 the rest, E, E, D, H, E, S, W, L. Reading row 0 then row 1 gives DFNTEATALEEDHESWL.

3. Encrypt ATTACK AT DAWN with the row transposition key 31452. The plaintext is ATTACKATDAWN, twelve letters, and the key has five columns, so pad to fifteen with three X's: rows are ATTAC, KATDA, WNXXX. Column labelled 1 is the second: T, A, N. Label 2 is the fifth: C, A, X. Label 3 is the first: A, K, W. Label 4 is the third: T, T, X. Label 5 is the fourth: A, D, X. The ciphertext is TANCAXAKWTTXADX.

4. How is a row transposition decrypted? Divide the ciphertext length by the number of columns to get the number of rows. Cut the ciphertext into consecutive pieces of that length. Write the first piece down the column labelled 1, the second down the column labelled 2, and so on until the grid is full, then read the grid row by row and discard any padding.

5. Why is a transposition never used on its own, and what is it used for instead? Because it preserves letter frequencies completely, so it conceals nothing from a frequency analysis and only the ordering has to be recovered. It is used as one of the two elementary operations inside a product cipher, where it supplies diffusion, spreading the influence of each plaintext symbol over many ciphertext positions, while substitution supplies confusion.

6. What is a double transposition, and why is it much stronger? Applying a transposition twice, with the same or a different key. It is stronger because a single transposition leaves letters that were adjacent in the plaintext fairly close together in the ciphertext, which an attacker exploits; composing two permutations destroys that locality, so the structure the attack depends on is gone. Applying the key 4312567 twice to ATTACKPOSTPONEDUNTILTWOAM gives NSCXAUOPTTWLTMDNAOIEPAXTTOKX.

7. Distinguish confusion from diffusion and say which elementary operation provides each. Confusion makes the relationship between the key and the ciphertext as complex as possible, and is provided by substitution. Diffusion spreads the statistical structure of the plaintext over the whole ciphertext, so that a change in one plaintext symbol affects many ciphertext symbols, and is provided by transposition. A strong cipher alternates the two over many rounds.

The program below builds a 16 by 16 grey picture so that it is complete in itself, hides a twelve-character message in it, prints what changed, and reads the message back.

# A picture, and a message hidden in the last bit of each byte of it.
# The picture is made here rather than read from a file, so the program is
# complete and the numbers below are its own.

WIDTH, HEIGHT = 16, 16

def make_picture():
    """A grey gradient. Each pixel is one byte, 0 black to 255 white."""
    return bytearray(((x * 16 + y * 3) % 256) for y in range(HEIGHT)
                     for x in range(WIDTH))

def to_bits(message):
    data = message.encode("ascii") + b"\x00"
    return [(b >> (7 - i)) & 1 for b in data for i in range(8)]

def hide(picture, message):
    out = bytearray(picture)
    bits = to_bits(message)
    if len(bits) > len(out):
        raise ValueError("the picture is too small for the message")
    for i, bit in enumerate(bits):
        out[i] = (out[i] & 0xFE) | bit
    return out

def reveal(picture):
    bits, chars = [], []
    for byte in picture:
        bits.append(byte & 1)
        if len(bits) == 8:
            value = 0
            for b in bits:
                value = (value << 1) | b
            if value == 0:
                return "".join(chars)
            chars.append(chr(value))
            bits = []
    return "".join(chars)

original = make_picture()
message = "PAPER LEAKED"
carrier = hide(original, message)

print("picture size      :", WIDTH, "by", HEIGHT, "=", len(original), "bytes")
print("message           :", message)
print("bits to hide      :", len(to_bits(message)), "so", len(to_bits(message)),
      "of", len(original), "bytes are touched")
print()
print("the first twelve bytes, before and after:")
print("   before:", " ".join("%3d" % b for b in original[:12]))
print("   after :", " ".join("%3d" % b for b in carrier[:12]))
print("   change:", " ".join("%+3d" % (carrier[i] - original[i]) for i in range(12)))
print()
changed = sum(1 for i in range(len(original)) if original[i] != carrier[i])
print("bytes changed     :", changed, "of", len(original))
print("largest change    :", max(abs(carrier[i] - original[i]) for i in range(len(original))))
print("recovered message :", reveal(carrier))
print()
print("and here is why it is not encryption: anybody who suspects the trick")
print("reads it straight out, with no key at all.")

picture size      : 16 by 16 = 256 bytes
message           : PAPER LEAKED
bits to hide      : 104 so 104 of 256 bytes are touched

the first twelve bytes, before and after:
   before:   0  16  32  48  64  80  96 112 128 144 160 176
   after :   0  17  32  49  64  80  96 112 128 145 160 176
   change:  +0  +1  +0  +1  +0  +0  +0  +0  +0  +1  +0  +0

bytes changed     : 46 of 256
largest change    : 1
recovered message : PAPER LEAKED

and here is why it is not encryption: anybody who suspects the trick
reads it straight out, with no key at all.

Read four things out of that run.

104 bits were written and only 46 bytes changed. A bit is only written when it differs from the bit already there, and about half the time it does not. That is worth noticing because it is why the method is hard to see: a random message overwrites a random half of the bits it touches.

The largest change to any byte is 1. Out of a range of 256. The picture is visually identical, and that is the whole claim of least significant bit steganography, stated as a measurement rather than as an assurance.

The message came back exactly. The terminating zero byte tells the reader where to stop, which is a detail every implementation needs and most descriptions omit: without it you cannot tell the message from the picture's own last bits.

A twelve-character message needed 104 of 256 bytes. So the capacity of a cover is about one eighth of its size, and that is the arithmetic to quote: one bit per byte, so one character per eight bytes. A one-megabyte photograph hides about 128 kilobytes, which is a great deal of text, and that is why the method is used.

The weaknesses, honestly

It is not secure, in the sense this subject uses the word. There is no key. Anybody who suspects that the last bits of a picture carry a message reads it out, which is exactly what the reveal function does. The security is entirely in the opponent's ignorance of the method, and the chapter on the symmetric cipher model already dealt with that: it is security through obscurity.

Statistical detection works. The last bits of a real photograph are not random, they are correlated with the image. A hidden message makes them look random, and that difference is measurable. The field that does this is called steganalysis, and simple tests catch simple hides reliably.

The overhead is enormous. Concealing a few hundred bits of message needed a cover of several thousand bits. An answer should quote the ratio: eight cover bits carry one message bit in the method above.

Any change to the cover destroys the message. Recompressing the picture, resizing it, or saving it in a format that discards detail removes the last bits and with them the message. A file that has passed through a social media platform has almost certainly lost it.

Distinctions that carry marks

A worked example: which one does the job

The requirement. A journalist inside an organisation wants to send a document to a colleague. Two different threats.

Threat A: the network operator can read the traffic. Encryption answers this. The operator sees an encrypted file, cannot read it, and the job is done. Steganography would be pointless extra work.

Threat B: the network operator will act against anybody who sends an encrypted file. Encryption fails here, not because it can be broken but because using it is the offence. Steganography answers this: the journalist sends a photograph.

The correct design for both threats at once. Encrypt the document with a key the colleague already holds, then hide the ciphertext in the photograph. If the cover is never suspected, nothing is learned. If it is suspected and the ciphertext extracted, the cipher still stands. Two independent failures are needed instead of one, which is the principle of defence in depth and the reason the two techniques belong together.

Quick revision

• Steganography hides the existence of a message; cryptography hides its contents.
• Classical methods: character marking, invisible ink, pin punctures, typewriter correction ribbon, and the acrostic or first-letter method.
• Modern method: least significant bit substitution in an image or audio file. One bit per byte, so one character per eight bytes.
• In the run: a 12-character message in a 256-byte picture touched 104 bytes, changed 46, and the largest change to any byte was 1.
• A terminator is needed so the reader knows where the message ends.
• Weaknesses: no key, so it is security through obscurity; statistical steganalysis detects it; huge overhead; destroyed by recompressing the carrier.
• Watermarking is the related technique for proving ownership, and it must survive attack rather than merely avoid detection.
• Best practice: encrypt, then hide, so that two independent failures are needed.

Test yourself

1. Distinguish steganography from cryptography. Cryptography conceals the contents of a message, so an interceptor knows that a secret is being sent but cannot read it. Steganography conceals the existence of the message by hiding it inside an innocuous cover, so an interceptor has no reason to suspect a communication at all.

2. Name four classical steganographic techniques. Character marking, in which selected letters of printed text are overwritten in pencil; invisible ink; pin punctures over chosen letters; and the use of a typewriter correction ribbon between the lines. The first-letter or acrostic method is a fifth.

3. Explain least significant bit steganography and state its capacity. Each pixel of an image is stored as a number, and changing its lowest bit alters the brightness by one part in 256, which is invisible. The message's bits are written one per byte into those lowest bits. The capacity is therefore one bit per byte of cover, that is one character per eight bytes, so a one-megabyte image holds about 128 kilobytes of text.

4. In the chapter's run, 104 bits were hidden and only 46 bytes changed. Why? Because a bit is only altered when it differs from the bit already in that position, and for a roughly random message that is about half the time. The consequence is that a hide touches fewer bytes than it writes bits, which makes it harder to notice.

5. Give three weaknesses of steganography. It has no key in its simple form, so its security rests entirely on the method not being guessed, which is security through obscurity. Statistical analysis, called steganalysis, detects it, because the lowest bits of a real photograph are correlated with the image and a hidden message makes them look random. And the overhead is very large, with eight cover bits needed per message bit.

6. Why is a hidden message lost when a picture is uploaded to a social media platform? Because such platforms recompress and often resize the image, and both operations discard exactly the fine detail that the lowest bits carry. The cover survives visually and the message does not.

7. What is the correct way to combine the two techniques, and why? Encrypt the message first and hide the resulting ciphertext in the cover. Then an opponent must both discover the hiding method and break the cipher, so two independent defences must fail rather than one; and if the cover is never suspected, nothing at all is learned.

block of   4 bits
   table entries        : 16
   key = the whole table: 64 bits
   possible mappings    : 16 factorial, a number of about 14 digits
block of   8 bits
   table entries        : 256
   key = the whole table: 2,048 bits
   possible mappings    : 256 factorial, a number of about 507 digits
block of  64 bits
   table entries        : 18,446,744,073,709,551,616
   key = the whole table: 1,180,591,620,717,411,303,424 bits
   possible mappings    : 18,446,744,073,709,551,616 factorial, a number of about 347,382,171,305,201,303,553 digits
block of 128 bits
   table entries        : 340,282,366,920,938,463,463,374,607,431,768,211,456
   key = the whole table: 43,556,142,965,880,123,323,311,949,751,266,331,066,368 bits
   possible mappings    : 340,282,366,920,938,463,463,374,607,431,768,211,456 factorial, a number of about 12,963,922,773,915,897,742,449,490,839,078,382,338,049 digits

Read the 64-bit row. The ideal 64-bit block cipher needs a key of 1,180,591,620,717,411,303,424 bits, which is about 147 million terabytes. It is not a cipher anybody can use; it is a definition of what a cipher should behave like. The mapping count in the last column is printed by Stirling's formula rather than computed, because the number itself has more digits than could be stored: about 347 followed by eighteen further digits of them.

So a real block cipher has a short key, say 56 or 128 bits, and is built to approximate the ideal mapping. It selects one mapping out of the tiny number its key can address, and the design problem is to make that small family look, to an attacker, like a random choice from the enormous one. That problem is what the next chapter's structure solves.

Two more things follow, and both are worth stating in an answer.

A block cipher's block size matters separately from its key size. A 64-bit block is small enough that after about 2 to the power 32 blocks a repeat becomes likely, whatever the key length, and that is the weakness behind the retirement of 3DES rather than any weakness in its key. AES uses 128-bit blocks for this reason.

A short key is not a compromise on security, only on generality. A 128-bit key gives 2 to the power 128 mappings out of an unimaginably larger set, and 2 to the power 128 is already beyond brute force.

Choosing between them

The last row is the one to carry away. Each family has exactly one catastrophic mistake, and they are different mistakes: for a block cipher it is electronic codebook mode, and for a stream cipher it is key reuse. Both have their own chapter later.

A worked example: which one for which job

Job 1: encrypt a student's answer script, stored as a PDF, in a college archive.

A block cipher, in cipher block chaining or counter mode. The file is complete before encryption starts, so nothing is gained from a stream cipher; the file will be stored for years, so a 128-bit block cipher is the safe choice; and if one sector of the disk goes bad it is better to lose one block than to lose the alignment of everything after it.

Job 2: encrypt a voice call over a poor mobile connection.

A stream cipher, or a block cipher in counter mode behaving as one. Each sample must be enciphered and sent immediately, so waiting for a block is not acceptable; and a corrupted bit must corrupt one sample and not a whole block, because a click is tolerable and a burst of noise is not.

Job 3: encrypt the traffic of a college portal over the web.

A block cipher in an authenticated mode, because that is what TLS specifies and because the data is a mixture of short and long messages. Notice that the answer is not decided by the block-against-stream question alone: it is decided by the protocol, which is the subject of Module 2.

The step that carries the marks. In each case the reason names a property from the table: completeness of the message, the effect of a corrupted bit, and the lifetime of the data. An answer that says "a block cipher is more secure" has not answered, because neither family is more secure than the other.

What beginners get wrong here

"A stream cipher is weaker." It is not. The one-time pad is a stream cipher and is the only unconditionally secure cipher there is. What is true is that stream ciphers fail catastrophically when misused, and that the commonest misuse, key reuse, is easy to commit.

Confusing the block size with the key size. DES has a 64-bit block and a 56-bit key. AES has a 128-bit block and a key of 128, 192 or 256 bits. They are independent choices and both matter.

Thinking a block cipher is inherently deterministic. The cipher is, and that is why modes exist. Cipher block chaining with a fresh initialisation vector, or counter mode with a fresh counter, gives a different ciphertext every time for the same plaintext.

Believing a bigger block is always better. A larger block means more padding overhead on short messages and more state in hardware. 128 bits is the current answer because it is large enough that repeats are not a concern.

Quick revision

• Block cipher: a fixed-size block at a time, deterministic for a given key, needs padding. DES, 3DES, AES.
• Stream cipher: one bit or byte at a time, combined with a key stream. One-time pad, Vernam, RC4.
• The ideal block cipher is an arbitrary reversible mapping, and its key is the whole table: for a 64-bit block that is about 1.18 times 10 to the power 21 bits. Unusable, so real ciphers approximate it with a short key.
• Block size and key size are independent. DES: 64-bit block, 56-bit key. AES: 128-bit block, 128, 192 or 256-bit key.
• A small block is a weakness in itself: repeats become likely after about 2 to the power 32 blocks for a 64-bit block.
• One corrupted ciphertext bit: a whole block for a block cipher, one bit for a stream cipher.
• Each family has one catastrophic mistake: electronic codebook mode for block ciphers, key stream reuse for stream ciphers.
• The practical answer: a block cipher in a mode that behaves like a stream cipher.

Test yourself

1. Define a block cipher and a stream cipher, and give two examples of each from this syllabus. A block cipher processes the input one fixed-size block at a time and produces one output block for each input block; DES and AES are examples. A stream cipher encrypts a data stream one bit or byte at a time by combining it with a key stream; the one-time pad and RC4 are examples.

2. What is the ideal block cipher, and why can it not be used? It is an arbitrary reversible mapping from every possible input block to a distinct output block, which is the strongest block cipher of that size. It cannot be used because the key must specify the whole mapping: for a 64-bit block that is over 18 million million million entries and a key of about 1.18 times 10 to the power 21 bits. A practical cipher therefore uses a short key and approximates the ideal.

3. Distinguish block size from key size, with DES and AES as examples. The block size is how much plaintext is transformed at once; the key size is how many bits of secret select the transformation. DES has a 64-bit block and a 56-bit key; AES has a 128-bit block and a key of 128, 192 or 256 bits. A cipher can be weak in one and strong in the other.

4. Why is a 64-bit block a weakness independent of the key length? Because the number of distinct blocks is limited, so in a long enough message a repeated ciphertext block becomes likely after about 2 to the power 32 blocks, and a repeat leaks information about the plaintext whatever the key. This is the reason a 64-bit block cipher is unsuitable for large volumes of data even with a long key.

5. A corrupted bit arrives in the ciphertext. Compare the damage under a block cipher and a stream cipher. Under a stream cipher only the corresponding plaintext bit is wrong, because each bit is combined with its own key stream bit independently. Under a block cipher the entire block containing that bit decrypts to rubbish, and in a chaining mode the following block is also affected.

6. Which family would you choose for a live voice call, and why? A stream cipher, or a block cipher in counter mode behaving as one. Each sample must be enciphered and transmitted immediately rather than waiting for a full block, and a corrupted bit should damage one sample only rather than a whole block, since a single click is tolerable where a burst of noise is not.

7. Name the one catastrophic mistake for each family. For a block cipher, using electronic codebook mode, because identical plaintext blocks produce identical ciphertext blocks and the structure of the data shows through. For a stream cipher, reusing the key stream, because subtracting two ciphertexts encrypted under the same stream removes the key entirely and leaves the difference of the plaintexts.

The rule to remember: confusion is about the KEY, diffusion is about the PLAINTEXT. Students reverse them, and it is the single commonest slip in this topic.

Neither alone is enough. A cipher with confusion and no diffusion leaves the plaintext's patterns intact within each small unit, which is a monoalphabetic cipher. A cipher with diffusion and no confusion moves the patterns around without disguising them, which is a transposition. Alternating the two over many rounds is a product cipher, and it is what every block cipher on this syllabus does.

The proof, performed

The listing below builds a four-round Feistel cipher on a 16-bit block, with a round function that is deliberately not invertible: it throws away the high four bits of its input. Then it encrypts, decrypts, and searches for two inputs to the round function that give the same output.

def f(half, subkey):
    """Not invertible on purpose: the high four bits are thrown away."""
    low = half & 0b00001111
    return (((low * 13) + 7) ^ subkey) & 0xFF

def rounds(left, right, subkeys):
    trace = [(0, left, right)]
    for i, k in enumerate(subkeys, 1):
        left, right = right, left ^ f(right, k)
        trace.append((i, left, right))
    return left, right, trace

def encrypt(block, subkeys):
    left, right = block >> 8, block & 0xFF
    l, r, trace = rounds(left, right, subkeys)
    return ((r << 8) | l), trace

def decrypt(block, subkeys):
    left, right = block >> 8, block & 0xFF
    l, r, trace = rounds(left, right, subkeys[::-1])
    return ((r << 8) | l), trace

SUBKEYS = [0x5A, 0x3C, 0xF0, 0x0F]
plain = 0x1234

cipher, etrace = encrypt(plain, SUBKEYS)
print("plaintext  = %04X" % plain)
print("subkeys    =", " ".join("%02X" % k for k in SUBKEYS))
print()
print("encryption, round by round:")
for i, l, r in etrace:
    print("   after round %d:  L = %02X  R = %02X" % (i, l, r))
print("   swap the halves: ciphertext = %04X" % cipher)
print()
back, dtrace = decrypt(cipher, SUBKEYS)
print("decryption, the SAME rounds with the subkeys reversed:")
for i, l, r in dtrace:
    print("   after round %d:  L = %02X  R = %02X" % (i, l, r))
print("   swap the halves: plaintext = %04X" % back)
print("recovered the plaintext:", back == plain)
print()
print("the round function is NOT invertible. Two different inputs, one output:")
seen = {}
for x in range(256):
    y = f(x, 0x5A)
    if y in seen:
        print("   f(%02X) = f(%02X) = %02X" % (seen[y], x, y))
        break
    seen[y] = x
print("   so a Feistel cipher does not need an invertible round function,")
print("   which is the whole reason the structure exists.")

plaintext  = 1234
subkeys    = 5A 3C F0 0F

encryption, round by round:
   after round 0:  L = 12  R = 34
   after round 1:  L = 34  R = 73
   after round 2:  L = 73  R = 26
   after round 3:  L = 26  R = D6
   after round 4:  L = D6  R = 7C
   swap the halves: ciphertext = 7CD6

decryption, the SAME rounds with the subkeys reversed:
   after round 0:  L = 7C  R = D6
   after round 1:  L = D6  R = 26
   after round 2:  L = 26  R = 73
   after round 3:  L = 73  R = 34
   after round 4:  L = 34  R = 12
   swap the halves: plaintext = 1234
recovered the plaintext: True

the round function is NOT invertible. Two different inputs, one output:
   f(00) = f(10) = 5D
   so a Feistel cipher does not need an invertible round function,
   which is the whole reason the structure exists.

Now read the two traces against each other, because that is the proof.

Encryption produced, in order, the pairs (12, 34), (34, 73), (73, 26), (26, D6), (D6, 7C). Decryption produced (7C, D6), (D6, 26), (26, 73), (73, 34), (34, 12). The second list is the first list read from the bottom up, with each pair swapped. The same rounds, in the same direction, with the subkeys reversed, walked the cipher backwards. Nothing was inverted.

And the round function is provably not invertible: f(00) and f(10) are both 5D, so given 5D you cannot say which input produced it. Yet the cipher decrypts exactly. That is the Feistel property, and the reason for it is worth stating as one sentence: the round function's output is never something you have to undo, it is only something you exclusive-or in, and an exclusive-or is undone by repeating it.

Why it works, in symbols

At round i, encryption computes L(i) = R(i-1) and R(i) = L(i-1) XOR F(R(i-1), K(i)).

To go backwards you need L(i-1) and R(i-1) from L(i) and R(i). Take them in the easy order:

R(i-1) = L(i), directly, because that is what the first equation says.

L(i-1) = R(i) XOR F(R(i-1), K(i)), and you now know R(i-1), so you can compute F again and exclusive-or it out. You never needed to invert F; you only needed to be able to run it forwards on a value you already had.

That is the whole argument, and it is worth five marks on its own.

The parameters of a Feistel cipher

A question asking you to "discuss the design features of a Feistel cipher" wants this list, each with the trade-off.

Block size. Larger means greater diffusion and greater security, and slower. 64 bits was traditional; 128 bits is the modern choice.

Key size. Larger means greater resistance to brute force, and slower. 64 bits was once thought adequate, 56 bits was DES's and is now inadequate, and 128 bits is the modern minimum.

Number of rounds. A single round gives very little; multiple rounds give increasing security. The usual figure is 16. The right number is the one after which no known attack does better than brute force.

Subkey generation algorithm. Greater complexity makes cryptanalysis harder. It must produce a different subkey per round from one master key.

Round function F. Greater complexity makes cryptanalysis harder. This is where confusion lives, and it is the part that is designed rather than chosen.

Two further considerations, which are engineering rather than security.

Fast software encryption and decryption. A cipher is often embedded in an application rather than a chip, so the speed of a software implementation matters.

Ease of analysis. A cipher whose design is easy to explain is easier to argue about, and therefore easier to trust. DES's designers did not publish their reasoning, which is exactly why DES was distrusted for years.

Distinctions that carry marks

That second table is the most useful comparison in this part of the syllabus, because the next two chapters are about DES and the one after is about AES, and their difference is exactly this.

What beginners get wrong here

Swapping confusion and diffusion. Confusion is about the key; diffusion is about the plaintext. Write it down.

Saying the round function must be reversible. It must not be, in the sense that nothing requires it, and DES's S-boxes are not. This is the point of the structure and the thing to say.

Forgetting the final swap. After the last round the halves are swapped before the ciphertext is assembled. Without it, decryption with reversed subkeys does not work, and it is the detail that breaks a hand-worked answer.

Thinking more rounds always means more security. Each round costs time, and past a certain point the gain is nothing because brute force is already the best attack. Sixteen is DES's answer, not a law.

Calling AES a Feistel cipher. It is not. It is a substitution-permutation network, it operates on the whole block each round, and its stages are individually invertible.

Quick revision

• Feistel: L(i) = R(i-1), R(i) = L(i-1) XOR F(R(i-1), K(i)), halves swapped after the last round.
• Decryption is the same algorithm with the subkeys in reverse order.
• The round function need not be invertible: proved in the run, where f(00) and f(10) both gave 5D and the cipher still decrypted.
• Why: R(i-1) = L(i) directly, and then F is recomputed forwards and exclusive-ored out.
• Confusion relates the key to the ciphertext, by substitution. Diffusion relates the plaintext to the ciphertext, by permutation. Shannon, 1949.
• Parameters: block size, key size, number of rounds, subkey algorithm, round function; plus fast software operation and ease of analysis.
• A Feistel cipher works on half the block per round; a substitution-permutation network on the whole block, and its stages must be invertible.
• DES and 3DES are Feistel. AES is not.

Test yourself

1. Write the Feistel round equations and say what happens after the last round. L(i) = R(i - 1) and R(i) = L(i - 1) XOR F(R(i - 1), K(i)). After the last round the two halves are swapped before the ciphertext is assembled.

2. How is a Feistel cipher decrypted? By running exactly the same algorithm on the ciphertext with the subkeys applied in reverse order, so K(n) first and K(1) last, with the same final swap. No separate decryption algorithm is needed.

3. Why does the round function not need to be invertible? Give the argument. Because the round output is combined by exclusive-or rather than substituted in. Going backwards, R(i - 1) is available immediately since it equals L(i); the function can then be recomputed forwards on that value and exclusive-ored out of R(i) to recover L(i - 1). The function is therefore only ever evaluated in the forward direction. The chapter's run confirms it: a round function for which f(00) and f(10) both give 5D still yields a cipher that decrypts exactly.

4. Define confusion and diffusion and say which operation provides each. Confusion makes the relationship between the key and the ciphertext as complex as possible and is provided by substitution. Diffusion spreads the statistical structure of the plaintext across the whole ciphertext, dissipating its redundancy, and is provided by permutation.

5. List the design parameters of a Feistel cipher. Block size, key size, number of rounds, subkey generation algorithm and the round function, with the two further engineering considerations of fast software encryption and decryption, and ease of analysis.

6. Why is a cipher with confusion but no diffusion weak? Give an example. Because the plaintext's statistical structure survives inside each unit that is substituted, so frequency analysis applies. A monoalphabetic substitution cipher is exactly that: the key's effect on each letter is arbitrary, but each letter keeps its own frequency and the cipher falls to counting.

7. Is AES a Feistel cipher? Justify your answer. No. AES is a substitution-permutation network: each round transforms the whole block rather than half of it, and each of its stages is individually invertible, so decryption requires the inverse of each stage rather than the same code with reversed subkeys. A Feistel cipher transforms half the block per round and needs no inverse of its round function.

Part 3: the 32-bit swap and the final permutation. After round 16 the two halves are swapped, giving R16 L16 rather than L16 R16, and the result is passed through FP, the inverse of IP. The swap is what makes decryption work with the same algorithm, and it is the step most often left out of a drawn answer.

The permutations, and the proof that they are inverses

# The two outer permutations of DES, from Tables 1 and 2 of FIPS 46-3.
# They are inverses of each other, which is proved below rather than asserted.

IP = [58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
      62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
      57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
      61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7]

FP = [40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
      38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
      36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
      34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25]

def bits(data):
    return [(b >> (7 - i)) & 1 for b in data for i in range(8)]

def unbits(bl):
    out = bytearray()
    for i in range(0, len(bl), 8):
        v = 0
        for b in bl[i:i + 8]:
            v = (v << 1) | b
        out.append(v)
    return bytes(out)

def permute(bl, table):
    return [bl[i - 1] for i in table]

block = bytes.fromhex("0123456789ABCDEF")
b = bits(block)
print("the block              :", block.hex().upper())
print("as 64 bits             :", "".join(str(x) for x in b))
print()

after_ip = permute(b, IP)
print("after the initial permutation:")
print("   bits                :", "".join(str(x) for x in after_ip))
print("   as bytes            :", unbits(after_ip).hex().upper())
print("   L0                  :", unbits(after_ip[:32]).hex().upper())
print("   R0                  :", unbits(after_ip[32:]).hex().upper())
print()

print("IP takes bit 58 of the input to position 1. Check it:")
print("   input bit 58        :", b[57])
print("   output bit 1        :", after_ip[0])
print()

restored = permute(after_ip, FP)
print("the final permutation undoes the initial one:")
print("   FP(IP(block))       :", unbits(restored).hex().upper())
print("   equals the block    :", unbits(restored) == block)
print()

print("and it holds for every one of the 64 single-bit blocks:")
bad = 0
for i in range(64):
    one = [1 if j == i else 0 for j in range(64)]
    if permute(permute(one, IP), FP) != one:
        bad += 1
print("   blocks that failed  :", bad, "of 64")

the block              : 0123456789ABCDEF
as 64 bits             : 0000000100100011010001010110011110001001101010111100110111101111

after the initial permutation:
   bits                : 1100110000000000110011001111111111110000101010101111000010101010
   as bytes            : CC00CCFFF0AAF0AA
   L0                  : CC00CCFF
   R0                  : F0AAF0AA

IP takes bit 58 of the input to position 1. Check it:
   input bit 58        : 1
   output bit 1        : 1

the final permutation undoes the initial one:
   FP(IP(block))       : 0123456789ABCDEF
   equals the block    : True

and it holds for every one of the 64 single-bit blocks:
   blocks that failed  : 0 of 64

Read four things out of the run.

How to read a permutation table. The first entry of IP is 58, which means "the first output bit is the fifty-eighth input bit". The program checked exactly that: input bit 58 is 1 and output bit 1 is 1. Students read these tables the other way round, as "bit 1 goes to position 58", and every hand-worked answer then comes out wrong. The table is read as a list of sources, not of destinations.

L0 and R0 are CC00CCFF and F0AAF0AA. Any published walk-through of DES on this block gives the same two values, so this chapter can be checked against an independent source. That is worth doing at least once with a cipher this fiddly.

FP really is the inverse of IP, and the check is not one block but all 64 single-bit blocks, which between them pin down the whole permutation. A permutation is determined by where it sends each single bit, so 0 failures of 64 is a complete proof and not a sample.

Neither permutation uses the key. Both tables are printed in the standard, so an attacker applies IP and FP as freely as you do. They add nothing to security, and an answer should say so: they are there because DES was built for hardware in 1977.

A worked example: encrypting one block, in outline

The setting. Plaintext 0123456789ABCDEF, key 133457799BBCDFF1. This pair is the standard illustration, so every intermediate value can be checked against any other source.

Step 1: the key schedule. From the 64-bit key, sixteen 48-bit subkeys K1 to K16 are produced. The next chapter but one does this in full; the first subkey comes out 1B02EFFC7072.

Step 2: the initial permutation. Done in the run above, giving L0 = CC00CCFF and R0 = F0AAF0AA.

Step 3: round 1. L1 takes the value of R0, which is F0AAF0AA. And R1 is L0 exclusive-ored with F(R0, K1). The next chapter computes that round function and it comes out 234AA9BB, so R1 is CC00CCFF exclusive-ored with 234AA9BB, which is EF4A6544.

Step 4: rounds 2 to 16. The same step fifteen more times, with K2 to K16.

Step 5: swap and permute. After round 16 the halves are swapped and FP applied, giving the ciphertext 85E813540F0AB405.

The step that carries the marks. Step 3 is the one an examination asks you to perform. Everything else is bookkeeping, and the bookkeeping is where a hand-worked answer goes wrong: the halves must be tracked in the right order, and the swap at the end must not be forgotten.

The parameters, as a table

What beginners get wrong here

Reading the permutation tables backwards. Entry i of the table names the source bit for output position i.

Calling the key 64 bits. The key is presented as 64 bits, but every eighth bit is a parity bit, so the key material is 56 bits and the keyspace is 2 to the power 56. Saying 64 bits inflates the keyspace by a factor of 256 and is the commonest error about DES.

Forgetting the 32-bit swap. After round 16 the halves are swapped before FP. It is what makes the same algorithm decrypt.

Thinking IP adds security. It does not. It is published and keyless.

Saying DES is secure, or insecure "because it is old". It is insecure because its key is 56 bits, and it was withdrawn on 19 May 2005. Give the reason and the date.

Quick revision

• DES: 64-bit block, 56-bit key (in a 64-bit key with 8 parity bits), 16 Feistel rounds, 48-bit subkeys.
• Three parts: initial permutation IP, sixteen rounds, 32-bit swap, then final permutation FP, the inverse of IP.
• Both permutations are keyless and published and add no strength; they exist for 1977 hardware.
• A permutation table is read as a list of sources: entry 1 of IP is 58, so output bit 1 is input bit 58.
• On block 0123456789ABCDEF, IP gives L0 = CC00CCFF and R0 = F0AAF0AA.
• FP is the inverse of IP, checked over all 64 single-bit blocks with 0 failures.
• History: request 1973, IBM's Lucifer-derived submission 1974, adopted 1977 as FIPS 46; key cut to 56 bits and S-box criteria classified; FIPS 46-3 in 1999 made 3DES preferred; withdrawn 19 May 2005.
• With key 133457799BBCDFF1 the ciphertext of that block is 85E813540F0AB405.

Test yourself

1. Give the block size, key size and number of rounds of DES, and its structure. A 64-bit block, a 56-bit key presented as 64 bits with every eighth bit a parity bit, and sixteen rounds of a Feistel structure with 48-bit subkeys.

2. Describe the three parts of DES encryption. First an initial permutation IP rearranges the 64 input bits. Then sixteen Feistel rounds, each taking the left and right 32-bit halves and computing L(i) = R(i - 1) and R(i) = L(i - 1) XOR F(R(i - 1), K(i)). Finally the two halves are swapped and the inverse permutation FP is applied to give the ciphertext.

3. What do IP and FP contribute to the security of DES? Nothing. Both are fixed, published permutations with no key, so an attacker can apply and undo them at will. They were included because DES was designed for hardware implementation, in which a bit permutation costs nothing.

4. How is the entry 58 at the start of the IP table read? As "output bit 1 is input bit 58". A permutation table lists, for each output position, the input position it draws from, not the destination of each input bit.

5. Why is there a 32-bit swap after the sixteenth round? So that decryption is the same algorithm with the subkeys in reverse order. Without the swap the output of the last round would be in the wrong order for the reversed schedule to unwind it, and a separate decryption algorithm would be needed.

6. Why is it wrong to say DES has a 64-bit key? Because eight of those 64 bits are parity bits, one per byte, used only to detect errors in the key. The effective key material is 56 bits, so the keyspace is 2 to the power 56 rather than 2 to the power 64, which is 256 times smaller.

7. When was DES withdrawn, and what replaced it? It was withdrawn on 19 May 2005. FIPS 46-3 of 1999 had already restricted it to legacy use and designated Triple DES as preferred, and FIPS 197 of 2001 published AES as the replacement.

Each S-box is a table of 4 rows and 16 columns holding numbers from 0 to 15. It takes six bits and gives four.

• The outer two bits, that is the first and the sixth, give the row, read as a two-bit number from 0 to 3.
• The middle four bits, that is bits two to five, give the column, read as a four-bit number from 0 to 15.
• The entry at that row and column is the output, written as four bits.

The trick is that the row comes from the first and last bits and not from the first two. Getting that wrong is the commonest error in the whole of DES, and the run below prints the two parts separately for every box so that the reader can see which bits went where.

The round function, computed on the standard values

# The DES round function F, from Tables 3, 4 and 5 of FIPS 46-3: the expansion
# permutation E, the eight S-boxes, and the permutation P.

E = [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13,
     12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21,
     22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1]

P = [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
     2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25]

S = [
 [[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
  [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
  [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
  [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],
 [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
  [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
  [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
  [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],
 [[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
  [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
  [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
  [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],
 [[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
  [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
  [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
  [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],
 [[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
  [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
  [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
  [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],
 [[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
  [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
  [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
  [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],
 [[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
  [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
  [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
  [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],
 [[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
  [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
  [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
  [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]],
]

def hex_bits(hexstr):
    n = len(hexstr) * 4
    v = int(hexstr, 16)
    return [(v >> (n - 1 - i)) & 1 for i in range(n)]

def bin_bits(binstr):
    return [int(c) for c in binstr]

def to_hex(bl):
    v = 0
    for b in bl:
        v = (v << 1) | b
    return "%0*X" % (len(bl) // 4, v)

def permute(bl, table):
    return [bl[i - 1] for i in table]

# R0 and K1 from the standard walk-through of key 133457799BBCDFF1
R = hex_bits("F0AAF0AA")
K = bin_bits("000110110000001011101111111111000111000001110010")

print("R (32 bits)       :", to_hex(R))
print("subkey K (48 bits):", to_hex(K))
print()

expanded = permute(R, E)
print("after the expansion permutation E, 32 bits become 48:")
print("   E(R)           :", to_hex(expanded))
x = [a ^ b for a, b in zip(expanded, K)]
print("   E(R) XOR K     :", to_hex(x))
print()

print("the 48 bits in eight groups of six, one per S-box:")
print("   " + " ".join("".join(str(b) for b in x[i * 6:i * 6 + 6]) for i in range(8)))
print()

out = []
print("each group of six gives four bits:")
for i in range(8):
    g = x[i * 6:i * 6 + 6]
    row = g[0] * 2 + g[5]
    col = g[1] * 8 + g[2] * 4 + g[3] * 2 + g[4]
    v = S[i][row][col]
    out += [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1]
    print("   S%d: bits %s  outer %d%d = row %d, inner %s = column %2d, entry %2d = %s"
          % (i + 1, "".join(str(b) for b in g), g[0], g[5], row,
             "".join(str(b) for b in g[1:5]), col, v,
             "".join(str(b) for b in [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1])))
print()
print("the eight S-box outputs, joined:", to_hex(out))
print("after the permutation P        :", to_hex(permute(out, P)))
print()
print("every S-box takes 6 bits to 4, so it is not invertible:")
first = S[0]
print("   S1 row 0 column 0 gives", first[0][0], "and row 1 column 1 gives", first[1][1])
print("   48 bits in, 32 bits out: F throws away one third of what it is given.")

Read five things out of the run.

E(R) is 7A15557A1555, and its 48 bits repeat in a pattern. Look at the eight groups of six: 011110 100001 010101 010101 011110 100001 010101 010101. The first four groups and the last four are identical, because R itself was F0AAF0AA, which is two identical halves. That is not a property of E; it is a property of this particular R, and it is worth noticing so that a reader does not mistake it for one.

The exclusive-or with the subkey gives 6117BA866527. From here on the values depend on the key, and this is the only place the key touches the round.

Every S-box lookup is shown with its row and column. Take S1: the six bits are 011000, the outer bits are 0 and 0 so the row is 0, the inner four bits are 1100 so the column is 12, the entry is 5, and 5 as four bits is 0101. Follow that for all eight and you can do it in an examination.

The eight outputs joined give 5C82B597, and P turns that into 234AA9BB. This is the value the previous chapter used to compute R1, and it is the value every published walk-through of DES gives for round 1 of this plaintext and key. That agreement is the check on this entire chapter.

Each S-box takes six bits to four, so it throws two away. F as a whole takes 48 bits to 32. The round function is therefore not invertible, which is exactly what the Feistel chapter said it did not need to be.

The expansion permutation, and why its rows overlap

The E table is usually printed as eight rows of six. Read it and you see that the last two entries of each row are the first two entries of the next, and that the table wraps: it begins with 32 and ends with 1.

That overlap is the point. Bit 1 of R appears in group 1 and in group 8. Bit 4 appears in group 1 and group 2. So sixteen of the 32 bits go into two S-boxes each, and a change in any one of those bits affects two S-boxes in this round, and therefore many more in the next. That is diffusion produced by duplication, and it costs nothing in hardware.

A worked example: one S-box by hand

Read S5 with the input bits 100001.

Step 1: the row. The outer bits are the first, 1, and the sixth, 1. As a two-bit number that is binary 11, which is 3. Row 3.

Step 2: the column. The middle four bits are 0, 0, 0, 0. As a four-bit number that is 0. Column 0.

Step 3: the entry. S5 row 3 column 0. Counting rows from 0, row 3 of S5 is 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, and column 0 of that row is 11.

Step 4: as four bits. 11 in binary is 1011.

So 100001 goes to 1011, which is exactly what the run printed for S5. Notice how easy it would have been to take the row from the first two bits, 10, giving row 2 and the answer 0 instead of 11.

Distinctions that carry marks

What beginners get wrong here

Taking the S-box row from the first two bits. It is the first and the last. This one error invalidates a whole answer.

Forgetting that the S-boxes are the only non-linear part. If a question asks why the S-boxes matter, that is the answer, and "they provide confusion" is the second half of it.

Thinking E is a plain permutation. It duplicates sixteen bits, so it is an expansion; the same input bit appears twice in the output.

Confusing P with IP. P is 32 bits, inside F, and contributes diffusion. IP is 64 bits, outside the rounds, and contributes nothing.

Expecting F to be invertible. It takes 48 bits to 32 and discards information. The Feistel structure is what makes that acceptable.

Quick revision

• F has four steps: expansion E (32 to 48), exclusive-or with the 48-bit subkey, eight S-boxes (48 to 32), permutation P (32 to 32).
• E duplicates sixteen bits so that one input bit feeds two S-boxes; that is diffusion, and it is why its rows overlap.
• An S-box takes 6 bits to 4. Row from the first and sixth bits; column from the middle four.
• The S-boxes are the only non-linear part of DES. Without them the cipher is linear and solvable as a system of equations.
• P spreads each S-box's four output bits to four different S-boxes in the next round.
• On the standard block and key: E(R0) is 7A15557A1555, exclusive-ored with K1 it is 6117BA866527, the S-box outputs join to 5C82B597, and after P the round function gives 234AA9BB.
• The S-box design criteria were classified in 1977; when differential cryptanalysis was published in 1990 the boxes proved unusually resistant to it.
• F takes 48 bits to 32, so it is not invertible, which the Feistel structure does not require.

Test yourself

1. Describe the four steps of the DES round function, with the bit counts. The 32-bit input is expanded to 48 bits by the expansion permutation E, which duplicates sixteen bits. The 48 bits are exclusive-ored with the 48-bit subkey. The result is split into eight groups of six, and each group is replaced by four bits through its own S-box, giving 32 bits. Those 32 bits are rearranged by the permutation P.

2. How is an S-box addressed? The first and sixth bits of the six-bit group, taken as a two-bit number, give the row from 0 to 3. The middle four bits, taken as a four-bit number, give the column from 0 to 15. The table entry at that row and column, written as four bits, is the output.

3. Read S5 with the input 100001. The outer bits are 1 and 1, so the row is binary 11, which is 3. The middle bits are 0000, so the column is 0. S5 row 3 column 0 holds 11, which as four bits is 1011.

4. Why is the expansion permutation an expansion rather than a permutation? Because it produces 48 bits from 32 by using sixteen of the input bits twice. Its purpose is both to match the 48-bit subkey and to make one input bit influence two S-boxes, which spreads the effect of a change more quickly through the rounds.

5. Why are the S-boxes the most important part of DES? Because they are the only non-linear component. Every other operation in the cipher, the permutations and the exclusive-ors, is linear, and a cipher built only from linear operations can be expressed and solved as a system of linear equations. The S-boxes supply the confusion that prevents this.

6. What does the permutation P contribute, and what would happen without it? It spreads the four output bits of each S-box across four different S-boxes in the following round, so that the influence of every input bit reaches the whole block within a few rounds. Without it the diffusion would remain local to each six-bit group, and an attacker could attack each S-box almost independently.

7. Why is the round function not invertible, and why does that not matter? Because each S-box maps six bits to four, so F maps 48 bits to 32 and discards information. It does not matter because a Feistel structure only ever evaluates F in the forward direction: going backwards, the right half of the previous round is available immediately, F is recomputed on it, and the result is exclusive-ored out.

Read five things out of the run.

Every byte of the key has odd parity, printed as eight 1s. That is what makes 133457799BBCDFF1 a well-formed DES key. A key whose parity is wrong is not rejected by the algorithm, which ignores those bits entirely, but it would be rejected by equipment that checks.

C0 and D0 are 1111000011001100101010101111 and 0101010101100110011110001111. These are the values every published walk-through gives, so this chapter is checkable against an independent source.

K1 is 1B02EFFC7072. This is the subkey the previous chapter used, and the round function it produced there came out 234AA9BB, which agrees with the published value. The two chapters therefore check each other.

The sixteen subkeys are all different, and they have to be. Two identical subkeys in a Feistel cipher create a symmetry an attacker can exploit, and the weak keys below are the extreme case of exactly that.

The shifts total 28. The program checked it and printed True. Each half is 28 bits, so sixteen rounds of shifting brings both halves round to their starting position.

The weak keys, and why they are weak

The last block of the run is the whole answer to a question that is set often.

A weak key is one for which all sixteen subkeys are identical. The run found that for all four of the classical weak keys, 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1 and 1F1F1F1F0E0E0E0E, the set of sixteen subkeys has exactly one member.

Why does that matter? Because DES decryption is the same algorithm with the subkeys reversed. If all sixteen subkeys are the same, then the reversed schedule is the same as the forward schedule, so decryption is identical to encryption. The consequences follow at once.

• Encrypting a block twice with a weak key returns the original block. The key is its own inverse.
• An attacker who suspects a weak key can test all four in four operations.
• In some protocols, a self-inverse cipher destroys a security property the protocol was relying on.

The reason those four keys behave this way is visible in their structure. 0101010101010101 is all zero bits apart from parity, so C0 and D0 are all zeros and rotating a block of zeros changes nothing. FEFEFEFEFEFEFEFE is all ones apart from parity, and the same applies. The other two give one half of all zeros and one half of all ones.

There are also semi-weak key pairs, sixteen keys forming six pairs, for which encryption under one key is decryption under the other, because their subkey schedules are each other's reverse. And a larger set of possibly weak keys produce only four distinct subkeys rather than sixteen.

How much does this cost DES? Almost nothing: there are 4 weak keys, 12 semi-weak, and 48 possibly weak, out of 2 to the power 56. The chance of choosing one at random is negligible. It is examinable because it is a clean illustration of what a key schedule is for, not because it is a practical threat.

A worked example: the first shift, by hand

The setting. Key 133457799BBCDFF1. After PC-1, from the run, C0 is 1111000011001100101010101111 and D0 is 0101010101100110011110001111.

Step 1: round 1 shifts by one. Rotate each half one place left, moving the leftmost bit round to the right-hand end.

C1 is 1110000110011001010101011111 and D1 is 1010101011001100111100011110.

Check C1 against C0: C0 began 1111 0000 and C1 begins 1110 0001, which is C0 with its first bit moved to the end. And C0 ended 1111 while C1 ends 1111 1, having gained the 1 that came round. That is the check to make, because a rotation done wrong is the commonest arithmetic slip in this topic.

Step 2: apply PC-2. Concatenate C1 and D1 into 56 bits, then take the 48 bits PC-2 names, in the order it names them. PC-2 begins 14, 17, 11, 24, 1, 5, so the subkey's first six bits are bits 14, 17, 11, 24, 1 and 5 of that 56-bit string.

Step 3: read the answer. The result is 1B02EFFC7072, as the run printed for round 1.

Step 4: note what PC-2 leaves out. PC-2 has 48 entries out of 56, so eight positions are never named. Check the table and they are 9, 18, 22, 25, 35, 38, 43 and 54. Those eight bits of C1 D1 are simply not used in round 1, and because the halves rotate, a different eight are unused in round 2.

Distinctions that carry marks

What beginners get wrong here

Saying the keyspace is 2 to the power 64. PC-1 discards the parity bits, so it is 2 to the power 56.

Rotating the two halves together. C and D are rotated separately, each within its own 28 bits.

Rotating right, or shifting instead of rotating. It is a circular left shift: the bit that leaves the left end comes back at the right.

Getting the shift schedule wrong. Rounds 1, 2, 9 and 16 shift by one; all the others by two. A useful check is that the total must be 28.

Listing the weak keys without saying why they are weak. The reason is that all sixteen subkeys are identical, so decryption is the same as encryption and the key is its own inverse.

Quick revision

• PC-1: 64 bits to 56, discarding the eight parity bits. That is where 56 comes from.
• Split into C and D, 28 bits each, rotated separately and circularly left before every round.
• Shift schedule: 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1. Rounds 1, 2, 9 and 16 shift by one.
• The shifts total 28, so after sixteen rounds both halves are back where they started.
• PC-2: 56 bits to 48, leaving out eight, and a different eight each round because the halves have rotated.
• For key 133457799BBCDFF1: C0 = 1111000011001100101010101111, D0 = 0101010101100110011110001111, K1 = 1B02EFFC7072.
• A weak key has all sixteen subkeys identical, so encryption equals decryption and the key is its own inverse. There are 4 of them, plus 12 semi-weak in 6 pairs and 48 possibly weak.
• The keyspace is 2 to the power 56, never 2 to the power 64.

Test yourself

1. Describe the DES key schedule. PC-1 takes the 64-bit key to 56 bits, discarding the eight parity bits. The 56 bits split into two 28-bit halves C and D. Before each of the sixteen rounds both halves are circularly left shifted, by one bit in rounds 1, 2, 9 and 16 and by two bits otherwise, and PC-2 then selects 48 of the 56 shifted bits as that round's subkey.

2. Why is the DES key 56 bits when it is presented as 64? Because every eighth bit is a parity bit, carrying odd parity over the preceding seven so that a corrupted key can be detected. PC-1 does not select any of those eight positions, so they contribute nothing to the subkeys and the keyspace is 2 to the power 56.

3. State the shift schedule and give the check on it. One, one, two, two, two, two, two, two, one, two, two, two, two, two, two, one: rounds 1, 2, 9 and 16 shift by one and the remaining twelve by two. The check is that the shifts total 28, the length of each half, so after sixteen rounds C and D have been rotated exactly once round and are back at their starting positions.

4. What is a weak key, and why is it weak? A key for which all sixteen subkeys come out identical. Since DES decryption is the same algorithm with the subkeys reversed, an identical schedule means decryption is the same as encryption, so the key is its own inverse and encrypting a block twice returns it. There are four such keys.

5. Name the four weak keys. 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1 and 1F1F1F1F0E0E0E0E.

6. Distinguish a weak key from a semi-weak key pair. A weak key has all sixteen subkeys the same, so encryption and decryption coincide under that one key. A semi-weak pair consists of two keys whose subkey schedules are each other's reverse, so encrypting with one key is the same as decrypting with the other. There are four weak keys and twelve semi-weak keys forming six pairs.

7. How many bits does PC-2 discard, and why is that acceptable? Eight of the 56, so each subkey uses 48 bits. It is acceptable because the halves rotate between rounds, so a different eight bits are omitted in each round and every bit of the key material is used in most rounds.

The whole cipher run, and decrypted back

import des as D

KEY = bytes.fromhex("133457799BBCDFF1")
PT = bytes.fromhex("0123456789ABCDEF")

def hx(bl):
    return D.unbits(bl).hex().upper()

ct, trace, ktrace, subkeys = D.encrypt_block_trace(PT, KEY)
print("plaintext :", PT.hex().upper())
print("key       :", KEY.hex().upper())
print()
print("round      L                R")
for r, l, rr in trace:
    print("  %2d     %s         %s" % (r, hx(l), hx(rr)))
print("  swap the halves, then the final permutation")
print("ciphertext:", ct.hex().upper())
print()
back = D.decrypt_block(ct, KEY)
print("decryption is the same algorithm with the subkeys reversed")
print("recovered :", back.hex().upper(), " equals the plaintext:", back == PT)
print()
print("the first three subkeys forwards :", " ".join(hx(k) for k in subkeys[:3]))
print("the first three used in decryption:", " ".join(hx(k) for k in subkeys[::-1][:3]))
print()

def bitcount(a, b):
    return sum(bin(x ^ y).count("1") for x, y in zip(a, b))

def flip_plaintext_bit(block, i):
    b = bytearray(block)
    b[i // 8] ^= 1 << (7 - (i % 8))
    return bytes(b)

print("the avalanche effect: ONE plaintext bit changed")
alt = flip_plaintext_bit(PT, 0)
print("   original plaintext :", PT.hex().upper())
print("   one bit flipped    :", alt.hex().upper(), " bits differing:", bitcount(PT, alt))
_, t2, _, _ = D.encrypt_block_trace(alt, KEY)
print("   round   bits differing out of 64")
for r in range(0, 17):
    a = trace[r][1] + trace[r][2]
    b = t2[r][1] + t2[r][2]
    print("     %2d      %2d" % (r, sum(1 for x, y in zip(a, b) if x != y)))
ct2 = D.encrypt_block(alt, KEY)
print("   ciphertexts differ in", bitcount(ct, ct2), "of 64 bits")
print()

print("the avalanche effect: ONE key bit changed")
altkey = bytearray(KEY)
altkey[0] ^= 0b00000010          # bit 7, not a parity bit
altkey = bytes(altkey)
print("   original key       :", KEY.hex().upper())
print("   one bit flipped    :", altkey.hex().upper(), " bits differing:", bitcount(KEY, altkey))
_, t3, _, _ = D.encrypt_block_trace(PT, altkey)
print("   round   bits differing out of 64")
for r in range(0, 17):
    a = trace[r][1] + trace[r][2]
    b = t3[r][1] + t3[r][2]
    print("     %2d      %2d" % (r, sum(1 for x, y in zip(a, b) if x != y)))
ct3 = D.encrypt_block(PT, altkey)
print("   ciphertexts differ in", bitcount(ct, ct3), "of 64 bits")
print()

print("averaged over 200 single-bit plaintext changes on random blocks and keys:")
import random
random.seed(7)
total = 0
for _ in range(200):
    p = bytes(random.randrange(256) for _ in range(8))
    k = D.set_parity(bytes(random.randrange(256) for _ in range(8)))
    i = random.randrange(64)
    c1 = D.encrypt_block(p, k)
    c2 = D.encrypt_block(flip_plaintext_bit(p, i), k)
    total += bitcount(c1, c2)
print("   mean bits changed in the ciphertext: %.2f of 64" % (total / 200))
print("   an ideal cipher would average 32.00")

Reading the trace

Every round is checkable. L0 is CC00CCFF and R0 is F0AAF0AA, from the chapter on the shape of DES. L1 is R0, as the Feistel equation requires. R1 is EF4A6544, which is L0 exclusive-ored with the 234AA9BB that the round-function chapter computed. So the three earlier chapters and this one agree, and all of them agree with the published walk-through of this plaintext and key.

The last round is not swapped in the trace. After round 16 the trace shows L16 = 43423234 and R16 = 0A4CD995. The ciphertext is formed from R16 L16, in that order, passed through the final permutation. That is the 32-bit swap, and it is printed as its own line so it cannot be missed.

The decryption subkeys are the encryption subkeys reversed. The run prints the first three of each: forwards they begin 1B02EFFC7072, and in decryption they begin CB3D8B0E17F5, which is K16. Nothing else about the algorithm changes.

Why decryption is the same algorithm

The argument was given in the Feistel chapter and is worth restating in DES's own terms, because it is a five-mark question.

Encryption takes the permuted block as L0 R0, runs sixteen rounds, swaps, and applies FP. Since FP is the inverse of IP, feeding the ciphertext back in undoes FP at once and presents the algorithm with R16 L16.

Now call that the decryption round 0, so its left half is R16 and its right half is L16. Apply the round with subkey K16. The new left half is the old right half, which is L16, and L16 equals R15 because that is what round 16 of encryption made it. The new right half is R16 XOR F(L16, K16), and R16 was L15 XOR F(R15, K16), so the exclusive-or cancels and what remains is L15. After one decryption round the halves hold R15 and L15.

That is the same relationship one step earlier, so the argument repeats fifteen more times, and after sixteen decryption rounds the halves hold R0 and L0. The final swap puts them in the order L0 R0, and FP undoes the original IP. The plaintext is back, and F was never inverted.

The avalanche effect, measured

The second half of the run is the measurement, and it is worth reading closely.

One plaintext bit changed. The plaintext went from 0123456789ABCDEF to 8123456789ABCDEF, a difference of exactly one bit. After round 0 the two states differ in 1 bit, as they must. After round 1, 7 bits. After round 2, 21. After round 3, 34, and from there the figure sits between 25 and 37 for the rest of the cipher, ending at 33 of 64 in the ciphertext.

Read what happened between rounds 1 and 3. One bit became seven, then twenty-one, then thirty-four. Three rounds took a single-bit difference to half the block. That is diffusion doing exactly the job the Feistel chapter described, and the mechanism is visible in the earlier chapters: the expansion permutation sends each changed bit into two S-boxes, each S-box changes up to four output bits, and the permutation P scatters those four bits into four different S-boxes for the next round.

One key bit changed. The key went from 133457799BBCDFF1 to 113457799BBCDFF1. Note that the bit chosen is not a parity bit, because flipping a parity bit would change nothing at all: DES ignores them. Here the spread starts more slowly, 0 bits after round 1, because that key bit does not appear in K1 at all, then 3, 11, 21, and it reaches 32 by round 7. The ciphertexts differ in 38 of 64 bits.

Averaged over 200 trials on random plaintexts and random keys, the mean is 32.60 of 64. An ideal cipher, in which each ciphertext bit is an independent fair coin, would average exactly 32. DES is within two-thirds of a bit of that, which is the honest way to state the avalanche effect: not "about half the bits change", which is vague, but 32.60 against an ideal 32.00, with the measurement in front of you.

What the numbers do NOT say

Two cautions, because a measured number invites over-reading.

A good avalanche does not make a cipher strong. It is a necessary property, not a sufficient one. DES has an excellent avalanche effect and a 56-bit key, and the key is what killed it. The next chapter is about that.

The per-round figures depend on which bit was flipped. Flip a different plaintext bit and the round-1 count will not be 7. The averaged figure over 200 random trials is the one that generalises; a single trace is an illustration.

A worked example: why a parity bit changes nothing

The claim. Flipping bit 8 of the DES key, which is the parity bit of the first byte, leaves the ciphertext completely unchanged.

Step 1: where the parity bits go. The key schedule chapter established that PC-1 has 56 entries and none of them is 8, 16, 24, 32, 40, 48, 56 or 64.

Step 2: what follows. Every subkey is derived from C and D, which are derived from PC-1's output. A bit that PC-1 never selects therefore reaches no subkey.

Step 3: the consequence. Two keys differing only in parity bits produce identical subkey schedules and identical ciphertexts. So the 64-bit key space of 2 to the power 64 collapses to 2 to the power 56 distinct behaviours, in groups of 256 keys that all behave identically.

Step 4: why the avalanche run avoided it. The listing flipped bit 7 of the first byte, not bit 8, precisely so that the measurement would be of a key bit and not of a bit the cipher ignores. Flipping bit 8 would have printed 0 for every round and 0 for the ciphertext, which would have looked like a broken cipher rather than a correct one.

Distinctions that carry marks

What beginners get wrong here

Saying DES has a separate decryption algorithm. It has one algorithm. Only the order of the subkeys changes.

Forgetting that the ciphertext is R16 L16 and not L16 R16. The swap after round 16 is what makes the reversed schedule work.

Flipping a parity bit and concluding the cipher is broken. DES ignores the eight parity bits entirely.

Saying "about half the bits change" and stopping. Give the number. One plaintext bit gives 33 of 64 here, and 32.60 of 64 averaged over 200 trials against an ideal 32.00.

Treating a strong avalanche as proof of security. It is necessary and not sufficient, and DES is the standing counter-example.

Quick revision

• Decryption is encryption with the subkeys reversed, K16 first. The same circuit does both.
• Why: R(i-1) = L(i) directly, then F is recomputed forwards and exclusive-ored out. The 32-bit swap after round 16 is what lines it up.
• The ciphertext is assembled from R16 L16, then FP.
• Full trace for 0123456789ABCDEF under 133457799BBCDFF1: L0 = CC00CCFF, R0 = F0AAF0AA, R1 = EF4A6544, ciphertext 85E813540F0AB405.
• Avalanche effect: a small change in plaintext or key changes about half the ciphertext bits.
• Measured: one plaintext bit gives 1, 7, 21, 34 bits differing after rounds 0 to 3 and 33 of 64 in the ciphertext; one key bit gives 0, 0, 3, 11 and 38 of 64.
• Mean over 200 random trials: 32.60 of 64, against an ideal cipher's 32.00.
• A key bit spreads more slowly at first because it may not appear in the early subkeys.
• Parity bits change nothing: PC-1 never selects them, so 256 keys share every behaviour.
• A strong avalanche is necessary but not sufficient: DES has one and a 56-bit key.

Test yourself

1. How is DES decrypted? By the same algorithm used for encryption, with the sixteen subkeys applied in reverse order, K16 in the first round through to K1 in the sixteenth, including the same 32-bit swap and the same outer permutations.

2. Prove that reversing the subkeys decrypts. Feeding the ciphertext in undoes FP, presenting the algorithm with R16 L16. In the first decryption round the new left half is L16, which equals R15; the new right half is R16 XOR F(L16, K16), and since R16 was L15 XOR F(R15, K16) and L16 equals R15, the two F terms cancel and what remains is L15. So after one decryption round the halves hold R15 and L15, which is the same relation one round earlier, and the argument repeats to R0 and L0.

3. Define the avalanche effect and say why a cipher needs it. That a small change in the plaintext or in the key produces a large change in the ciphertext. Without it, an attacker could vary the input slightly and watch the output respond in a predictable way, learning about the plaintext or narrowing the key; a strong avalanche makes the ciphertext's response to a small change indistinguishable from a fresh random value.

4. In this chapter's measurement, how many ciphertext bits changed when one plaintext bit was flipped, and what is the average? 33 of 64 for that particular flip. Averaged over 200 single-bit changes on random plaintexts and random keys the mean was 32.60 of 64, against the 32.00 an ideal cipher would give.

5. Why did the key-bit avalanche show 0 differing bits after round 1? Because the key bit that was flipped does not appear in K1. PC-2 selects 48 of the 56 bits for each subkey, so eight are omitted in any given round, and a changed bit has no effect until a round whose subkey includes it. It reached about half the block by round 7.

6. What happens if you flip a parity bit of a DES key? Nothing. PC-1 selects 56 of the 64 key bits and never selects positions 8, 16, 24, 32, 40, 48, 56 or 64, so a parity bit reaches no subkey. Two keys differing only in parity bits give identical ciphertexts, which is why the keyspace is 2 to the power 56 and not 2 to the power 64.

7. Does a strong avalanche effect make a cipher secure? Justify with an example. No. It is a necessary property but not a sufficient one. DES has an excellent avalanche effect, measured here at 32.60 of 64 against an ideal 32.00, and was withdrawn in 2005 because its 56-bit key can be searched exhaustively. Avalanche says nothing about keyspace.

The arithmetic, computed

# What the published DES breaks actually cost, worked from their own figures.

KEYSPACE = 2 ** 56
AVERAGE = KEYSPACE // 2

print("the DES keyspace           : 2 to the power 56 =", format(KEYSPACE, ","))
print("expected keys before a hit : half of it        =", format(AVERAGE, ","))
print()

# The EFF DES Cracker's own published rate: 88 thousand million keys a second.
eff_rate = 88 * 10 ** 9
secs = AVERAGE / eff_rate
print("EFF DES Cracker, 88 thousand million keys a second:")
print("   expected time           : %.1f hours" % (secs / 3600))
print("   and it reported         : 56 hours for the actual key it found")
print("   so the key it found was : %.2f of the way through the keyspace"
      % (56 * 3600 * eff_rate / KEYSPACE))
print()

# DES-III: under 24 hours. What rate does that imply?
for hours, label in ((22.25, "DES-III, 22 hours 15 minutes"),
                     (24.0, "DES-III, taking the full 24 hours")):
    rate = AVERAGE / (hours * 3600)
    print("%s implies about %s keys a second" % (label, format(int(rate), ",")))
print()

# What one ordinary machine would take today, at a generous rate.
for rate, label in ((10 ** 7, "a 1998 desktop, 10 million keys a second"),
                    (10 ** 9, "one modern core, 1 thousand million a second"),
                    (10 ** 12, "a graphics card, 1 million million a second")):
    years = AVERAGE / rate / (365.25 * 24 * 3600)
    if years < 1:
        print("%-50s %.1f days" % (label, years * 365.25))
    else:
        print("%-50s %.1f years" % (label, years))
print()

print("and the two cryptanalytic attacks, in plaintext rather than in time:")
for name, n, kind in (("differential cryptanalysis", 47, "chosen plaintexts"),
                      ("linear cryptanalysis", 47, "known plaintexts")):
    blocks = 2 ** n
    tb = blocks * 8 / 10 ** 12
    print("   %-28s 2 to the power %d %s = %s blocks = %s terabytes"
          % (name, n, kind, format(blocks, ","), format(int(tb), ",")))
print("   a DES block is 8 bytes, so both attacks need more data under ONE key")
print("   than any real system has ever encrypted.")

the DES keyspace           : 2 to the power 56 = 72,057,594,037,927,936
expected keys before a hit : half of it        = 36,028,797,018,963,968

EFF DES Cracker, 88 thousand million keys a second:
   expected time           : 113.7 hours
   and it reported         : 56 hours for the actual key it found
   so the key it found was : 0.25 of the way through the keyspace

DES-III, 22 hours 15 minutes implies about 449,797,715,592 keys a second
DES-III, taking the full 24 hours implies about 416,999,965,497 keys a second

a 1998 desktop, 10 million keys a second           114.2 years
one modern core, 1 thousand million a second       1.1 years
a graphics card, 1 million million a second        0.4 days

and the two cryptanalytic attacks, in plaintext rather than in time:
   differential cryptanalysis   2 to the power 47 chosen plaintexts = 140,737,488,355,328 blocks = 1,125 terabytes
   linear cryptanalysis         2 to the power 47 known plaintexts = 140,737,488,355,328 blocks = 1,125 terabytes
   a DES block is 8 bytes, so both attacks need more data under ONE key
   than any real system has ever encrypted.

Read five things out of that run.

56 hours is not the average, and this is the detail that matters. At its own published rate of 88 thousand million keys a second, the EFF machine's expected time was 113.7 hours. It finished in 56 because the key it was looking for happened to sit about a quarter of the way through the keyspace. So the honest figure for what that machine could do is about five days on average, not 56 hours, and a student who quotes 56 hours as DES's strength has understated it by a factor of two. Both numbers are worth knowing, and knowing which is which is what distinguishes an answer.

DES-III implies a rate of about 450 thousand million keys a second. That is five times the EFF machine alone, which is what adding a hundred thousand volunteer computers bought.

One modern processor core would take 1.1 years. So DES is not breakable on a laptop in an afternoon, and it is entirely breakable by anybody with a graphics card: the run shows 0.4 days. That is the practical statement to make about DES in 2026.

The two cryptanalytic attacks are costed in data, not in time. Differential cryptanalysis of the full sixteen rounds needs about 2 to the power 47 chosen plaintexts, and Matsui's linear cryptanalysis needs about 2 to the power 47 known plaintexts. The program turns that into 140,737,488,355,328 blocks, which at 8 bytes a block is 1,125 terabytes under a single key. No real system has ever encrypted that much under one DES key, and an attacker who could choose 1,125 terabytes of plaintext has access that makes the cipher irrelevant.

So the practical break was always brute force. That is the sentence to take away, and it generalises: when a cipher dies, it is usually the key length that kills it.

The three cryptanalytic attacks worth naming

Differential cryptanalysis, published by Eli Biham and Adi Shamir between 1990 and 1993. It looks at how a difference between two plaintexts propagates through the rounds, and uses pairs of ciphertexts whose plaintexts differ in a chosen way to deduce key bits. It breaks DES reduced to fewer rounds very effectively; against the full sixteen it needs about 2 to the power 47 chosen plaintexts, which is not practical.

The historically interesting part is what it revealed about the S-boxes. DES's S-box design criteria were classified in 1977, which fed twenty years of suspicion that a weakness had been built in. When differential cryptanalysis was published in 1990, the S-boxes turned out to be unusually well chosen against it: small changes to them make DES much weaker. The reasonable conclusion is that the designers knew about the attack and were protecting against it, which is the opposite of what the critics feared.

Linear cryptanalysis, published by Mitsuru Matsui at EUROCRYPT 1993. It finds linear approximations that hold with probability a little away from one half, and accumulates enough of them to deduce key bits. Against the full cipher it needs about 2 to the power 47 known plaintexts, which is a weaker requirement than differential's chosen plaintexts and still far beyond reach.

Timing attacks. Not an attack on the algorithm at all but on an implementation: measuring how long a decryption takes and inferring key bits from the variation. DES is relatively resistant because its operations are table lookups and permutations with little data-dependent branching, but the category matters enormously for the public-key ciphers of the later chapters.

Why the key was ever 56 bits

It is worth being able to answer this, because it is asked as a criticism.

Hardware in 1977. A cipher that had to run at line speed on a single chip had a real budget, and every extra key bit cost registers and wiring.

The block size. DES's 64-bit block and Feistel structure make a 64-bit key natural, and eight of those bits were given to parity, which was standard practice for keys carried over noisy links.

The assessment of the threat. The judgement was that a machine capable of exhaustive search would cost tens of millions of dollars and be available only to a state. That judgement was correct in 1977 and wrong by 1998, and the twenty-one years between are the interval over which computing became cheap. That is the security trend of this book's second chapter, stated as a single cipher's biography.

Distinctions that carry marks

What beginners get wrong here

Quoting 56 hours as DES's strength. That was one machine finding one lucky key. The expected time at that machine's own rate was 113.7 hours.

Saying DES was broken by cryptanalysis. It was broken by exhaustive search. Differential and linear cryptanalysis are real results and have never been practical against the full cipher.

Saying DES is insecure because it is old. It is insecure because 2 to the power 56 is searchable. Give the number and a date.

Thinking the classified S-box criteria hid a back door. The evidence went the other way: the S-boxes are close to optimal against an attack that was not public when they were chosen.

Forgetting the 64-bit block. Even with a longer key, a 64-bit block is a liability in bulk use, which is what finally retired Triple DES. The key is not the only parameter.

Quick revision

• Two questions: the key length, and whether cryptanalysis beats brute force. DES failed the first and passed the second.
• Keyspace 2 to the power 56, which is 72,057,594,037,927,936; expected search 2 to the power 55.
• DES-I 17 June 1997, about 96 days. DES-II-1 completed 23 February 1998, about 41 days. DES-II-2 17 July 1998, the EFF DES Cracker in 56 hours. DES-III 18 to 19 January 1999, under 24 hours.
• The EFF machine: under $250,000, 88 thousand million keys a second. Its expected time was 113.7 hours; the 56 was luck.
• Today: one core 1.1 years, a graphics card 0.4 days.
• Differential cryptanalysis (Biham and Shamir) about 2 to the power 47 chosen plaintexts; linear cryptanalysis (Matsui, 1993) about 2 to the power 47 known plaintexts. Both mean 1,125 terabytes under one key, so neither is practical.
• The S-boxes proved strong against differential cryptanalysis, which answered twenty years of suspicion about their classified design criteria.
• DES was withdrawn 19 May 2005.

Test yourself

1. On what two grounds is the strength of a cipher such as DES assessed? On the length of its key, which decides how long an exhaustive search takes; and on the nature of its algorithm, which decides whether any cryptanalytic attack does better than exhaustive search.

2. Give the size of the DES keyspace and the expected number of trials for brute force. 2 to the power 56, which is 72,057,594,037,927,936 keys. Exhaustive search succeeds after half of them on average, so about 2 to the power 55, which is 36,028,797,018,963,968 trials.

3. Describe the EFF DES Cracker and what it demonstrated. A machine built by the Electronic Frontier Foundation in 1998 from an ordinary personal computer driving an array of custom chips, costing less than $250,000 and searching 88 thousand million keys a second. On 17 July 1998 it won RSA's DES-II-2 challenge, finding the key in 56 hours. It demonstrated that a 56-bit key could be searched by a well-funded private organisation rather than only by a state.

4. Why is it misleading to quote 56 hours as the time to break DES? Because that was the time to find one particular key, which happened to lie about a quarter of the way through the keyspace. At the machine's own rate of 88 thousand million keys a second the expected time was 113.7 hours, so about five days is the honest average for that hardware.

5. Why did differential and linear cryptanalysis never break DES in practice? Because both need about 2 to the power 47 plaintexts under a single key, which is over 140 million million blocks, or about 1,125 terabytes of data. No real system has encrypted that much under one DES key, and differential cryptanalysis additionally requires the plaintexts to be chosen by the attacker.

6. What did the publication of differential cryptanalysis reveal about the DES S-boxes? That they were unusually well chosen to resist it. Small modifications to them make DES substantially weaker against the attack. Since the design criteria had been classified in 1977 and the attack was not public until 1990, the reasonable inference is that the designers knew of the attack and defended against it, which contradicted the long-standing suspicion that the secrecy concealed a weakness.

7. Why was DES given a 56-bit key, and when did that judgement fail? Because a cipher designed in 1977 to run on a single chip at line speed had a hardware budget, because eight bits of the natural 64-bit key were used for parity, and because the assessment was that a machine capable of exhaustive search would cost tens of millions and be available only to a state. That judgement held until 1997, when a volunteer effort found a key in about 96 days, and failed decisively in July 1998 when a $250,000 machine did it in 56 hours.

MixColumns. Each column of four bytes is replaced by a combination of all four, computed in the finite field GF(2 to the power 8). It provides diffusion within a column: change one byte of the input column and every byte of the output column changes. MU's syllabus says the round details are not expected, so the field arithmetic is not walked here; what a student needs is that it is a linear mixing, that it is invertible, and that it is why a one-byte change reaches the whole block in two rounds.

AddRoundKey. The 128 bits of the state are exclusive-ored with 128 bits of round key. It is the only stage that uses the key, and it is deliberately the simplest.

The structure around them: one AddRoundKey before the first round, then the four stages for each round, except that the last round has no MixColumns. That omission is not an oversight; it makes the decryption structure match the encryption structure, and it is a standing examination question.

The cipher, in one file

RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36,
        0x6C, 0xD8, 0xAB, 0x4D]


def xtime(a):
    """Multiply by x in GF(2^8), reducing by the AES polynomial 0x11B."""
    a <<= 1
    return (a ^ 0x1B) & 0xFF if a & 0x100 else a


def gmul(a, b):
    """Multiplication in GF(2^8)."""
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        b >>= 1
        a = xtime(a)
    return p


def _build_sbox():
    """FIPS 197 s.5.1.1: the inverse in GF(2^8), then the affine transformation."""
    inv = [0] * 256
    for i in range(1, 256):
        for j in range(1, 256):
            if gmul(i, j) == 1:
                inv[i] = j
                break
    box = []
    for i in range(256):
        x = inv[i]
        y = x
        for _ in range(4):
            x = ((x << 1) | (x >> 7)) & 0xFF
            y ^= x
        box.append(y ^ 0x63)
    return box


SBOX = _build_sbox()
INV_SBOX = [0] * 256
for _i, _v in enumerate(SBOX):
    INV_SBOX[_v] = _i


def key_expansion(key):
    nk = len(key) // 4
    nr = nk + 6
    w = [list(key[4 * i:4 * i + 4]) for i in range(nk)]
    for i in range(nk, 4 * (nr + 1)):
        t = list(w[i - 1])
        if i % nk == 0:
            t = t[1:] + t[:1]
            t = [SBOX[b] for b in t]
            t[0] ^= RCON[i // nk - 1]
        elif nk > 6 and i % nk == 4:
            t = [SBOX[b] for b in t]
        w.append([w[i - nk][j] ^ t[j] for j in range(4)])
    return w, nr


def _add_round_key(s, w, rnd):
    for c in range(4):
        for r in range(4):
            s[r][c] ^= w[rnd * 4 + c][r]


def _sub_bytes(s, box=None):
    box = box or SBOX
    for r in range(4):
        for c in range(4):
            s[r][c] = box[s[r][c]]


def _shift_rows(s):
    for r in range(1, 4):
        s[r] = s[r][r:] + s[r][:r]


def _inv_shift_rows(s):
    for r in range(1, 4):
        s[r] = s[r][-r:] + s[r][:-r]


def _mix_columns(s):
    for c in range(4):
        a = [s[r][c] for r in range(4)]
        s[0][c] = gmul(a[0], 2) ^ gmul(a[1], 3) ^ a[2] ^ a[3]
        s[1][c] = a[0] ^ gmul(a[1], 2) ^ gmul(a[2], 3) ^ a[3]
        s[2][c] = a[0] ^ a[1] ^ gmul(a[2], 2) ^ gmul(a[3], 3)
        s[3][c] = gmul(a[0], 3) ^ a[1] ^ a[2] ^ gmul(a[3], 2)


def _inv_mix_columns(s):
    for c in range(4):
        a = [s[r][c] for r in range(4)]
        s[0][c] = gmul(a[0], 14) ^ gmul(a[1], 11) ^ gmul(a[2], 13) ^ gmul(a[3], 9)
        s[1][c] = gmul(a[0], 9) ^ gmul(a[1], 14) ^ gmul(a[2], 11) ^ gmul(a[3], 13)
        s[2][c] = gmul(a[0], 13) ^ gmul(a[1], 9) ^ gmul(a[2], 14) ^ gmul(a[3], 11)
        s[3][c] = gmul(a[0], 11) ^ gmul(a[1], 13) ^ gmul(a[2], 9) ^ gmul(a[3], 14)


def _to_state(b):
    return [[b[r + 4 * c] for c in range(4)] for r in range(4)]


def _from_state(s):
    return bytes(s[r][c] for c in range(4) for r in range(4))


def encrypt_block(block, key, trace=None):
    w, nr = key_expansion(key)
    s = _to_state(block)
    _add_round_key(s, w, 0)
    if trace is not None:
        trace.append(('start', _from_state(s).hex()))
    for rnd in range(1, nr):
        _sub_bytes(s)
        _shift_rows(s)
        _mix_columns(s)
        _add_round_key(s, w, rnd)
        if trace is not None:
            trace.append(('round %d' % rnd, _from_state(s).hex()))
    _sub_bytes(s)
    _shift_rows(s)
    _add_round_key(s, w, nr)
    if trace is not None:
        trace.append(('round %d' % nr, _from_state(s).hex()))
    return _from_state(s)


def decrypt_block(block, key):
    w, nr = key_expansion(key)
    s = _to_state(block)
    _add_round_key(s, w, nr)
    for rnd in range(nr - 1, 0, -1):
        _inv_shift_rows(s)
        _sub_bytes(s, INV_SBOX)
        _add_round_key(s, w, rnd)
        _inv_mix_columns(s)
    _inv_shift_rows(s)
    _sub_bytes(s, INV_SBOX)
    _add_round_key(s, w, 0)
    return _from_state(s)

Run against the standard's own vectors

import aes

print("FIPS 197 Table 3, the only three configurations the standard allows:")
print("   name      key bits  Nk  block bits  Nb  rounds Nr")
for name, kb, nk, nr in (("AES-128", 128, 4, 10), ("AES-192", 192, 6, 12),
                         ("AES-256", 256, 8, 14)):
    print("   %-9s %8d  %2d  %10d  %2d  %9d" % (name, kb, nk, 128, 4, nr))
print()

print("the S-box is not a magic table: it is the multiplicative inverse in")
print("GF(2 to the power 8) followed by an affine transformation, and this")
print("module BUILDS it that way. FIPS 197 section 5.1.1 gives one example:")
print("   SBOX[0x53] = 0x%02X  (the standard says 0xED)" % aes.SBOX[0x53])
print("   SBOX[0x00] = 0x%02X  (0 has no inverse, so the affine map alone gives 0x63)"
      % aes.SBOX[0x00])
print("   and the inverse table undoes it:",
      all(aes.INV_SBOX[aes.SBOX[i]] == i for i in range(256)))
print()

print("FIPS 197 Appendix B, the worked example:")
key = bytes.fromhex("2b7e151628aed2a6abf7158809cf4f3c")
pt = bytes.fromhex("3243f6a8885a308d313198a2e0370734")
trace = []
ct = aes.encrypt_block(pt, key, trace)
print("   key        :", key.hex())
print("   plaintext  :", pt.hex())
print("   ciphertext :", ct.hex())
print("   the standard's answer is 3925841d02dc09fbdc118597196a0b32")
print("   they agree :", ct.hex() == "3925841d02dc09fbdc118597196a0b32")
print()
print("   the state after each round:")
for label, state in trace:
    print("     %-9s %s" % (label, state))
print()

print("FIPS 197 Appendix C, all three key sizes on one block:")
pt2 = bytes.fromhex("00112233445566778899aabbccddeeff")
for kh, want in (("000102030405060708090a0b0c0d0e0f", "69c4e0d86a7b0430d8cdb78070b4c55a"),
                 ("000102030405060708090a0b0c0d0e0f1011121314151617",
                  "dda97ca4864cdfe06eaf70a0ec0d7191"),
                 ("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f",
                  "8ea2b7ca516745bfeafc49904b496089")):
    got = aes.encrypt_block(pt2, bytes.fromhex(kh)).hex()
    print("   AES-%-3d  %s  matches the standard: %s"
          % (len(kh) * 4, got, got == want))
print()
print("and decryption returns the plaintext:",
      aes.decrypt_block(aes.encrypt_block(pt2, bytes.fromhex("000102030405060708090a0b0c0d0e0f")),
                        bytes.fromhex("000102030405060708090a0b0c0d0e0f")) == pt2)

FIPS 197 Table 3, the only three configurations the standard allows:
   name      key bits  Nk  block bits  Nb  rounds Nr
   AES-128        128   4         128   4         10
   AES-192        192   6         128   4         12
   AES-256        256   8         128   4         14

the S-box is not a magic table: it is the multiplicative inverse in
GF(2 to the power 8) followed by an affine transformation, and this
module BUILDS it that way. FIPS 197 section 5.1.1 gives one example:
   SBOX[0x53] = 0xED  (the standard says 0xED)
   SBOX[0x00] = 0x63  (0 has no inverse, so the affine map alone gives 0x63)
   and the inverse table undoes it: True

FIPS 197 Appendix B, the worked example:
   key        : 2b7e151628aed2a6abf7158809cf4f3c
   plaintext  : 3243f6a8885a308d313198a2e0370734
   ciphertext : 3925841d02dc09fbdc118597196a0b32
   the standard's answer is 3925841d02dc09fbdc118597196a0b32
   they agree : True

   the state after each round:
     start     193de3bea0f4e22b9ac68d2ae9f84808
     round 1   a49c7ff2689f352b6b5bea43026a5049
     round 2   aa8f5f0361dde3ef82d24ad26832469a
     round 3   486c4eee671d9d0d4de3b138d65f58e7
     round 4   e0927fe8c86363c0d9b1355085b8be01
     round 5   f1006f55c1924cef7cc88b325db5d50c
     round 6   260e2e173d41b77de86472a9fdd28b25
     round 7   5a4142b11949dc1fa3e019657a8c040c
     round 8   ea835cf00445332d655d98ad8596b0c5
     round 9   eb40f21e592e38848ba113e71bc342d2
     round 10  3925841d02dc09fbdc118597196a0b32

FIPS 197 Appendix C, all three key sizes on one block:
   AES-128  69c4e0d86a7b0430d8cdb78070b4c55a  matches the standard: True
   AES-192  dda97ca4864cdfe06eaf70a0ec0d7191  matches the standard: True
   AES-256  8ea2b7ca516745bfeafc49904b496089  matches the standard: True

and decryption returns the plaintext: True

Read four things out of that run.

The S-box is built, and the standard's example comes out right. FIPS 197 section 5.1.1 gives 0x53 mapping to 0xED, and the generated table agrees. Since the table was computed from the definition rather than copied, that agreement is evidence that the definition in section 4 above is correct. The chapter can therefore explain where the S-box comes from instead of asking the reader to accept it.

SBOX[0x00] is 0x63. Zero has no multiplicative inverse, so the construction defines its inverse as zero and the affine transformation alone produces 0x63. It is the one special case and it is worth knowing, because a reader who tries to reproduce the table will hit it first.

The state after every round matches FIPS 197 Appendix B. The standard prints exactly this sequence for exactly this key and plaintext, starting 193de3bea0f4e22b9ac68d2ae9f84808 after the initial AddRoundKey and ending at the ciphertext. Any reader with the standard open can check this chapter line by line.

All three key sizes are correct, and decryption returns the plaintext. Appendix C of the standard gives the three ciphertexts for one block under 128, 192 and 256-bit keys, and all three match.

AES against DES

That table is the most likely question in this part of the syllabus, and the two rows that carry the most marks are the structure row and the design-criteria row.

A worked example: how fast does a change spread

The question. In DES, the avalanche chapter measured that one plaintext bit reached about half the block by round 3. How does AES compare?

Step 1: one byte changes. Say byte 0 of the state changes.

Step 2: SubBytes. Still one byte, now a different value. The substitution is byte by byte, so nothing spreads.

Step 3: ShiftRows. Still one byte, now in a different column.

Step 4: MixColumns. Every byte of that column now depends on the changed byte, so four bytes differ.

Step 5: the second round's ShiftRows. Those four bytes are in one column, and ShiftRows moves them into four different columns, one in each.

Step 6: the second round's MixColumns. Each of the four columns now has a changed byte, so every byte of all four columns changes. All sixteen bytes of the state differ.

So AES reaches full diffusion in two rounds. DES took three to reach half the block and more to reach all of it. That is what operating on the whole block each round buys, and it is why AES needs ten rounds where DES needed sixteen.

What beginners get wrong here

Calling AES a Feistel cipher. It is not. Every round transforms the whole state, and decryption uses inverse stages rather than reversed subkeys.

Saying AES has a 256-bit block. The block is always 128 bits. Only the key varies. Rijndael as designed supports other block sizes; FIPS 197 standardises only the 128-bit block, and says so.

Forgetting that the last round has no MixColumns. It is asked, and the reason is that it makes the inverse cipher's structure match the cipher's.

Walking the MixColumns arithmetic when the syllabus says not to. MU prints "round details not expected". Name the stage, say what it achieves, and spend the time on the topics that are examined.

Saying AES is unbreakable. Say that no attack better than exhaustive search is known against the full cipher, and that NIST lists all three key sizes as acceptable. That is a claim with a date and a source behind it.

Quick revision

• AES: FIPS 197, published 26 November 2001, updated 9 May 2023. Rijndael, by Daemen and Rijmen, selected in 2000 after a public competition; the other four finalists were MARS, RC6, Serpent and Twofish.
• Block 128 bits always. Key 128, 192 or 256; rounds 10, 12, 14.
• Not a Feistel cipher: a substitution-permutation network on the whole block, with every stage invertible.
• Four stages: SubBytes (the only non-linear one, confusion), ShiftRows (diffusion across columns), MixColumns (diffusion within a column, in GF(2 to the power 8)), AddRoundKey (the only use of the key).
• One AddRoundKey before the first round; the last round has no MixColumns, so that the inverse cipher has the same shape.
• The S-box is the multiplicative inverse in GF(2 to the power 8) followed by an affine map; 0x53 gives 0xED, and 0x00 gives 0x63 because 0 has no inverse.
• Full diffusion in two rounds, against DES's three to reach half the block.
• The design was public and competitively reviewed, which is the answer to DES's classified S-box criteria.

Test yourself

1. Give AES's block size, key sizes and round counts, and name its structure. The block is always 128 bits. The key may be 128, 192 or 256 bits, giving 10, 12 or 14 rounds respectively. The structure is a substitution-permutation network, not a Feistel network: each round transforms the whole 128-bit state.

2. Name the four stages of an AES round and say what each contributes. SubBytes substitutes each byte through a single table and is the only non-linear stage, providing confusion. ShiftRows rotates rows 1, 2 and 3 left by one, two and three bytes, providing diffusion across columns. MixColumns replaces each column by a combination of its four bytes in GF(2 to the power 8), providing diffusion within a column. AddRoundKey exclusive-ors the state with the round key and is the only stage that uses the key.

3. Why does the last round omit MixColumns? So that the inverse cipher has the same structure as the cipher. With the omission, decryption can be expressed as the same sequence of inverse stages in the same arrangement, which makes implementations simpler and lets encryption and decryption share code paths.

4. How is the AES S-box constructed, and what does 0x53 map to? Each byte is replaced by its multiplicative inverse in the finite field GF(2 to the power 8), with zero mapping to zero, and the result is put through an affine transformation over GF(2). FIPS 197's own example is that 0x53 maps to 0xED, which this chapter's generated table reproduces.

5. Give three differences between DES and AES. DES has a 64-bit block and a 56-bit key; AES has a 128-bit block and a key of 128, 192 or 256 bits. DES is a Feistel cipher whose round function need not be invertible and whose decryption is the same algorithm with reversed subkeys; AES is a substitution-permutation network whose stages are all invertible and whose decryption uses the inverse stages. DES's S-box design criteria were classified; AES was chosen by open competition with public analysis.

6. How many rounds does a single-byte change take to affect the whole AES state, and why? Two. In the first round MixColumns spreads the change across the four bytes of its column; the next ShiftRows moves those four bytes into four different columns, and that round's MixColumns then changes every byte of all four columns, which is the whole state.

7. What can honestly be said about AES's security? That no attack materially better than exhaustive search is known against the full cipher, after public analysis since 1998, and that NIST's transition guidance lists AES-128, AES-192 and AES-256 as acceptable for encryption and decryption. Exhaustive search of a 128-bit key is beyond any foreseeable machine.

Step 2. For every possible K2, compute D(K2, C) and look the result up in the table. Every hit is a pair that maps P to C. That is another 2 to the power n operations.

Step 3. Most hits are wrong, so filter them with further known plaintext and ciphertext pairs until one pair survives.

The cost. About 2 to the power n + 1 cipher operations and 2 to the power n storage, against 2 to the power 2n for brute force on the pair. For DES that is about 2 to the power 57 rather than 2 to the power 112.

The attack, performed

The listing uses a toy block cipher with a 16-bit block and a 16-bit key, so that 2 to the power 16 is 65,536 and the whole attack runs in seconds. The arithmetic is exactly the arithmetic of the attack on double DES; only the exponents are smaller.

# The meet-in-the-middle attack, performed. A toy block cipher with a 16-bit key
# stands in for DES, so the attack finishes in seconds and the arithmetic is the
# same arithmetic.

import itertools

MASK = 0xFFFF

def E(block, key):
    """A toy 16-bit block cipher. Four rounds of add, rotate, xor, substitute."""
    x = block
    for r in range(4):
        x = (x + key + r) & MASK
        x = ((x << 5) | (x >> 11)) & MASK
        x = x ^ ((key >> 3) | ((key << 13) & MASK))
        x = ((x * 0x2545) + 0x9E37) & MASK
    return x

def D(block, key):
    """Its inverse, needed for the attack and to check E is a bijection."""
    x = block
    for r in reversed(range(4)):
        x = ((x - 0x9E37) * pow(0x2545, -1, 0x10000)) & MASK
        x = x ^ ((key >> 3) | ((key << 13) & MASK))
        x = ((x >> 5) | (x << 11)) & MASK
        x = (x - key - r) & MASK
    return x

# A cipher that is not a bijection is not a cipher. Check it before using it.
print("is E a bijection for key 0x1234?",
      len({E(b, 0x1234) for b in range(65536)}) == 65536)
print("does D undo E?", all(D(E(b, 0x1234), 0x1234) == b for b in range(0, 65536, 997)))
print()

K1, K2 = 0x2B7E, 0x1528
P = 0x3243
C = E(E(P, K1), K2)
print("double encryption with two 16-bit keys, so 32 bits of key in all")
print("   plaintext  = %04X" % P)
print("   K1         = %04X   K2 = %04X" % (K1, K2))
print("   ciphertext = %04X" % C)
print()

print("brute force on the pair would be 2 to the power 32 =",
      format(2 ** 32, ","), "trials")
print("the meet-in-the-middle attack is 2 to the power 16 twice =",
      format(2 ** 17, ","))
print()

# Step 1: encrypt P under every possible first key, and remember the middles.
table = {}
for k in range(65536):
    table.setdefault(E(P, k), []).append(k)
print("step 1: encrypted the plaintext under all", format(65536, ","),
      "first keys, and stored the middles")
print("        distinct middle values:", format(len(table), ","))

# Step 2: decrypt C under every possible second key and look the middle up.
found = []
for k2 in range(65536):
    m = D(C, k2)
    for k1 in table.get(m, ()):
        found.append((k1, k2))
print("step 2: decrypted the ciphertext under all", format(65536, ","),
      "second keys and looked each middle up")
print("        candidate key pairs found:", format(len(found), ","))
print("        the true pair is among them:", (K1, K2) in found)
print()

# Step 3: more known pairs, until one candidate is left.
extra = [0x1A2B, 0x7799, 0xC0DE]
survivors = found
for i, p2 in enumerate(extra, 1):
    c2 = E(E(p2, K1), K2)
    survivors = [(a, b) for a, b in survivors if E(E(p2, a), b) == c2]
    print("step 3.%d: a further known pair (%04X to %04X) leaves %s candidate(s)"
          % (i, p2, c2, format(len(survivors), ",")))
print()
print("the recovered key pair:", " ".join("%04X" % k for k in survivors[0]))
print("which is the real one  :", survivors[0] == (K1, K2))
print()
print("why more than one pair was needed: the key is 32 bits and a block is 16,")
print("so one pair leaves about 2 to the power 16 wrong pairs that happen to fit.")
print("Each further pair divides the survivors by about 2 to the power 16.")
print()
print("so double encryption with two n-bit keys costs the attacker about 2 to the")
print("power n + 1, not 2 to the power 2n. The second key bought ONE bit.")

Read six things out of that run.

The toy cipher was checked first. It is a bijection over all 65,536 blocks and its inverse undoes it. A demonstration of a cryptographic attack built on a function that is not a cipher would be worthless, and checking it costs one line.

Brute force on the pair would be 4,294,967,296 trials; the attack is 131,072. A factor of about 32,768, which is 2 to the power 15, and in general the saving is 2 to the power n minus 1.

Step 1 produced 40,261 distinct middle values from 65,536 keys. Not 65,536: several keys happen to send this plaintext to the same middle value. That is the birthday phenomenon and it is why the table stores a list of keys per middle rather than one key.

One known pair left 65,447 candidate pairs. This is the number every description of the attack omits. There are 2 to the power 32 key pairs and only 2 to the power 16 possible ciphertexts, so about 2 to the power 16 wrong pairs map this plaintext to this ciphertext by accident. The attack does not identify the key from one pair; it narrows it.

Two pairs left five, and three left one. Each further known pair divides the survivors by about 2 to the power 16, because it imposes 16 more bits of constraint. The number of pairs needed is about the key size divided by the block size, which for double DES is 112 over 64, so two pairs are usually enough and three are certain. That is the honest general statement.

The recovered key was 2B7E 1528, the true one. Not a candidate, not a near miss: the real key pair, found from three known plaintexts.

What this means for DES

Double DES has 112 bits of key material and about 57 bits of effective strength against an attacker willing to store 2 to the power 56 entries. That storage is enormous, which is the one honest defence of double DES: the attack is memory-bound rather than time-bound, and 2 to the power 56 eight-byte entries is about 576 petabytes.

But a security argument that rests on an attacker's storage budget is a weak argument, and it gets weaker every year. So the answer was never double encryption. It was triple encryption, and the next chapter is why three passes escape this attack where two do not.

The short version, which is worth having in advance: against triple encryption the same trick leaves the attacker with about 2 to the power 2n work rather than 2 to the power n + 1, because one of the three keys has to be guessed before the meet-in-the-middle can begin. For DES that is 2 to the power 112, which is beyond reach.

A worked example: counting the cost for DES

The setting. Double DES, K1 and K2 each 56 bits, one known plaintext and ciphertext pair.

Step 1: the table. 2 to the power 56 encryptions, each storing a 64-bit middle and a 56-bit key, so about 15 bytes an entry. 2 to the power 56 times 15 bytes is about 1,080 petabytes. That is the real obstacle, and it is storage, not time.

Step 2: the matching. Another 2 to the power 56 decryptions, each with one lookup.

Step 3: the total. About 2 to the power 57 cipher operations. From the strength-of-DES chapter, a graphics card does 2 to the power 55 in 0.4 days, so 2 to the power 57 is about 1.6 days of computing on hardware anybody can buy, plus a thousand petabytes of storage nobody has at home.

Step 4: the filtering. With a 112-bit key and a 64-bit block, one pair leaves about 2 to the power 48 candidates and two pairs leave about one, so two known pairs suffice.

The step that carries the marks. Step 3. Double DES is not broken in practice today because of the storage, and it is not used because a cipher whose security rests on the attacker's disk budget is not a cipher anybody should choose. Say both halves.

Distinctions that carry marks

What beginners get wrong here

Saying double DES gives 112 bits of security. It gives 112 bits of key material and about 57 bits of strength. The distinction is the whole topic.

Forgetting the storage. The attack needs 2 to the power n entries stored, and for DES that is hundreds of petabytes. An answer that quotes only the time has given half the cost.

Thinking one known pair identifies the key. The run shows 65,447 candidates from one pair. Several pairs are needed, and the number is about the key size divided by the block size.

Confusing "DES is not a group" with "double DES is secure". Not being a group is what makes double DES a genuinely different cipher rather than a single DES in disguise. It says nothing about the meet-in-the-middle attack, which works anyway.

Attributing the attack to the wrong people. It is Diffie and Hellman, 1977, the same pair as the key exchange of a later chapter.

Quick revision

• Double encryption: C = E(K2, E(K1, P)). 2n bits of key material, about n + 1 bits of strength.
• DES is not a group (shown 1992), so double DES is a different cipher from DES; that is necessary and not sufficient.
• Meet-in-the-middle (Diffie and Hellman, 1977): encrypt P under every K1 and store the middles; decrypt C under every K2 and look each middle up; every match is a candidate.
• Cost: about 2 to the power n + 1 operations and 2 to the power n storage, against 2 to the power 2n for brute force.
• For double DES: about 2 to the power 57 operations, and roughly a thousand petabytes of storage.
• One known pair is not enough. In the run it left 65,447 candidates; two left five; three left one. The number needed is about the key size divided by the block size.
• The attack trades memory for time, and it is the earliest clear example of that trade in cryptography.
• Triple encryption escapes it because one key must be guessed first, raising the work to about 2 to the power 2n.

Test yourself

1. Write the double encryption formula and say how much key material it uses. C = E(K2, E(K1, P)), with decryption P = D(K1, D(K2, C)). With two independent n-bit keys it uses 2n bits of key material, which for DES is 112 bits.

2. Describe the meet-in-the-middle attack. Given a known plaintext and ciphertext pair, note that the middle value X satisfies both X = E(K1, P) and X = D(K2, C). Encrypt P under every possible K1 and store each result with its key; then decrypt C under every possible K2 and look each result up in the table. Every match is a candidate key pair. Further known pairs filter the candidates until one survives.

3. What does the attack cost, and what is the effective strength of double DES? About 2 to the power n + 1 cipher operations and 2 to the power n storage, so for DES about 2 to the power 57 operations and 2 to the power 56 stored entries. The effective strength of double DES is therefore about 57 bits rather than the 112 its key material suggests: the second key buys one bit.

4. Why is one known plaintext and ciphertext pair not enough? Because there are far more key pairs than ciphertexts. With a 112-bit key and a 64-bit block there are 2 to the power 112 pairs and only 2 to the power 64 ciphertexts, so about 2 to the power 48 wrong pairs map that plaintext to that ciphertext by accident. In the chapter's 16-bit demonstration one pair left 65,447 candidates, two left five and three left one.

5. What does it mean to say DES is not a group, and why does it matter? That there is generally no single key K3 for which E(K3, P) equals E(K2, E(K1, P)). It matters because if DES were a group, double encryption would be equivalent to single encryption under some other key and would add nothing at all; not being a group is what makes double DES a genuinely larger family of mappings. It is necessary for double encryption to be worth anything, but not sufficient, since the meet-in-the-middle attack applies regardless.

6. What does the meet-in-the-middle attack trade, and why is that significant? It trades memory for time: it replaces 2 to the power 2n work with about 2 to the power n + 1 work plus 2 to the power n storage. It is significant because the only practical obstacle to breaking double DES is that storage, and a security argument resting on an attacker's disk budget weakens every year, which is why triple rather than double encryption was adopted.

7. Why does triple encryption resist the attack? Because the attacker cannot reach the middle from both ends in one pass: one of the three keys must be guessed before the meet-in-the-middle can be set up, and that multiplies the work by the size of that key's space. For three-key triple DES the work rises to about 2 to the power 112, which is beyond any foreseeable machine.

The cipher, and both claims proved

IP = [58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
      62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
      57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
      61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7]

FP = [40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
      38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
      36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
      34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25]

E = [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13,
     12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21,
     22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1]

P = [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
     2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25]

PC1 = [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
       10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
       63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
       14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4]

PC2 = [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
       23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
       41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
       44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32]

SHIFTS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

S = [
 [[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
  [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
  [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
  [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],
 [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
  [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
  [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
  [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],
 [[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
  [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
  [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
  [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],
 [[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
  [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
  [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
  [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],
 [[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
  [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
  [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
  [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],
 [[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
  [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
  [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
  [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],
 [[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
  [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
  [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
  [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],
 [[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
  [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
  [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
  [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]],
]

WEAK_KEYS = ['0101010101010101', 'FEFEFEFEFEFEFEFE',
             'E0E0E0E0F1F1F1F1', '1F1F1F1F0E0E0E0E']


def bits(data):
    """Bytes to a list of bits, most significant first."""
    return [(b >> (7 - i)) & 1 for b in data for i in range(8)]


def unbits(bl):
    out = bytearray()
    for i in range(0, len(bl), 8):
        v = 0
        for b in bl[i:i + 8]:
            v = (v << 1) | b
        out.append(v)
    return bytes(out)


def permute(bl, table):
    return [bl[i - 1] for i in table]


def left_shift(bl, n):
    return bl[n:] + bl[:n]


def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


def key_schedule(key):
    """The sixteen 48-bit subkeys, and the C and D halves at every round."""
    kb = permute(bits(key), PC1)
    c, d = kb[:28], kb[28:]
    subkeys, trace = [], []
    for r in range(16):
        c = left_shift(c, SHIFTS[r])
        d = left_shift(d, SHIFTS[r])
        k = permute(c + d, PC2)
        subkeys.append(k)
        trace.append((r + 1, SHIFTS[r], list(c), list(d), k))
    return subkeys, trace


def f(right, subkey):
    """The DES round function: expand, XOR the key, eight S-boxes, permute."""
    x = xor(permute(right, E), subkey)
    out = []
    for i in range(8):
        block = x[i * 6:i * 6 + 6]
        row = block[0] * 2 + block[5]
        col = (block[1] * 8 + block[2] * 4 + block[3] * 2 + block[4])
        v = S[i][row][col]
        out += [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1]
    return permute(out, P)


def _rounds(block, subkeys):
    b = permute(bits(block), IP)
    left, right = b[:32], b[32:]
    trace = [(0, list(left), list(right))]
    for r in range(16):
        left, right = right, xor(left, f(right, subkeys[r]))
        trace.append((r + 1, list(left), list(right)))
    return unbits(permute(right + left, FP)), trace


def encrypt_block(block, key):
    subkeys, _ = key_schedule(key)
    return _rounds(block, subkeys)[0]


def decrypt_block(block, key):
    subkeys, _ = key_schedule(key)
    return _rounds(block, subkeys[::-1])[0]


def encrypt_block_trace(block, key):
    subkeys, ktrace = key_schedule(key)
    out, trace = _rounds(block, subkeys)
    return out, trace, ktrace, subkeys


def parity_ok(key):
    """Every byte of a DES key carries odd parity in its low bit."""
    return all(bin(b).count('1') % 2 == 1 for b in key)


def set_parity(key):
    out = bytearray()
    for b in key:
        b &= 0xFE
        out.append(b if bin(b).count('1') % 2 == 1 else b | 1)
    return bytes(out)


# ------------------------------------------------------------- Triple DES
def tdea_encrypt_block(block, k1, k2, k3):
    """Encrypt, Decrypt, Encrypt: the order SP 800-67 prints."""
    return encrypt_block(decrypt_block(encrypt_block(block, k1), k2), k3)


def tdea_decrypt_block(block, k1, k2, k3):
    return decrypt_block(encrypt_block(decrypt_block(block, k3), k2), k1)

Read five things out of that run.

Three-key and two-key 3DES give different ciphertexts, 314F8327FA7A09A8 and B7835779EE26ACB7, which is a reminder that the two-key variant is a distinct cipher and not a shortcut.

With all three keys equal, 3DES gives exactly single DES. 3FA40E8A984D4815, which is the known answer for this block and key from the DES chapters. That is the backward-compatibility property, demonstrated.

With an EEE arrangement it would not hold. E(E(E(P))) under one key gives 3B8FAD2B39E386BC, which is not single DES. So the choice of EDE is doing real work, and the counterfactual proves it rather than the claim being taken on trust.

The block limit is 8,388,608 bytes. 2 to the power 20 blocks of eight bytes, which the program prints as 8.0 mebibytes. This is SP 800-67 Rev. 2's own restriction on a key bundle, and it is the most practically important fact about 3DES: an eight-megabyte limit per key is a limit on files, not on messages, and it exists because a 64-bit block starts repeating.

The key sizes, side by side. Three-key 3DES has 168 bits of key material and about 112 bits of strength; AES-128 has 128 bits of both. 3DES therefore carries more key than AES-128 and is weaker, slower and limited to eight megabytes. There is no argument for choosing it.

Why a 64-bit block was the thing that finally killed it

The key length was never 3DES's problem. The block size was.

A 64-bit block cipher has 2 to the power 64 possible blocks. By the birthday reasoning of the hash chapters, after about 2 to the power 32 blocks encrypted under one key a repeated ciphertext block becomes likely, and in a chaining mode a repeat leaks a relationship between plaintext blocks. 2 to the power 32 blocks is 32 gigabytes, and practical attacks on long-lived connections were demonstrated well below that, which is why the standard's own limit is set two orders of magnitude lower still, at 2 to the power 20 blocks.

No key length fixes this. It is a property of the block size, and the only repair is a larger block, which means a different cipher. That is why AES uses 128 bits.

The dates, from the standards themselves

Read the second-to-last row carefully, because it is the shape of every retirement in this subject: decrypting old data stays permitted, protecting new data does not. A system cannot forget how to read what it wrote, so a withdrawn cipher lives on in a read-only role. The same pattern appears with SHA-1, with SSL, and with DSA.

A worked example: what to do with a system that uses 3DES

The situation. A college's fee-payment records were encrypted with three-key 3DES in 2015 and the system is still running in 2026.

Step 1: is it broken? No. No practical attack recovers a 168-bit 3DES key, and the effective 112 bits is beyond reach.

Step 2: is it permitted? For new encryption, no. Three-key 3DES encryption was deprecated through 2023 and disallowed after, and since 1 January 2024 TDEA is not an approved block cipher at all.

Step 3: how much data is under each key? This is the question nobody asks and the one that matters. If a single key bundle has protected more than 2 to the power 20 blocks, that is eight megabytes, the standard's own limit has been exceeded and the birthday concern is real rather than theoretical.

Step 4: what to do. Keep the 3DES decryption path, because the old records must remain readable, and that use is still permitted. Encrypt everything new with AES, at 128 bits or more. Re-encrypt the old records under AES as they are next touched rather than in one operation, so that no key is stretched further.

The step that carries the marks. Steps 2 and 3 together. A question asking whether a system using 3DES is secure is asking three things: is there an attack, is it allowed, and how much data is under one key. All three have documented answers.

Distinctions that carry marks

What beginners get wrong here

Saying 3DES is secure, full stop. Say that no practical attack is known and that it has not been an approved block cipher since 1 January 2024. Both halves.

Saying the middle decryption adds strength. It is for backward compatibility with single DES. The run proves that EDE with one key gives single DES and EEE does not.

Giving three-key 3DES 168 bits of strength. It has 168 bits of key material and about 112 bits of strength.

Ignoring the block size. The 64-bit block, not the key, is what finally retired 3DES, and the 8-mebibyte limit per key is the practical consequence.

Thinking a withdrawn cipher must be switched off. Decryption of already-protected data remains permitted, by the withdrawal notice's own words. Only new protection is disallowed.

Quick revision

• 3DES: C = E(K3, D(K2, E(K1, P))). Encrypt, decrypt, encrypt.
• Why EDE: with all three keys equal it reduces to single DES, so DES equipment interoperates. Proved: 3FA40E8A984D4815 for EDE against 3B8FAD2B39E386BC for EEE.
• Three-key: 168 bits of key material, about 112 bits of strength. Two-key (K3 equals K1): 112 bits of material, about 80 bits of strength.
• It escapes meet-in-the-middle because one key must be guessed first, giving 2 to the power 112.
• The block is 64 bits, so SP 800-67 Rev. 2 limits one key bundle to 2 to the power 20 blocks, which is 8,388,608 bytes or 8 mebibytes.
• Dates: two-key encryption disallowed March 2019; three-key deprecated through 2023, disallowed after; 1 January 2024, SP 800-67 Rev. 2 withdrawn and "TDEA is no longer an approved block cipher".
• Still permitted: decryption, key unwrapping and MAC verification of already-protected data.
• AES-128 carries less key than three-key 3DES, is stronger, faster, and has no practical data limit.

Test yourself

1. Give the triple DES encryption and decryption formulas. Encryption is C = E(K3, D(K2, E(K1, P))) and decryption is P = D(K1, E(K2, D(K3, C))). The sequence is encrypt, decrypt, encrypt on the way out and the reverse on the way back.

2. Why is the middle stage a decryption rather than an encryption? For backward compatibility. Setting all three keys equal makes the second stage undo the first, so triple DES reduces exactly to single DES under that key and a 3DES device can interoperate with a DES device. It is not for security: DES decryption is no stronger than DES encryption. The chapter demonstrates both halves: EDE with one key gives the single-DES answer 3FA40E8A984D4815, and EEE gives 3B8FAD2B39E386BC, which is not single DES.

3. Distinguish two-key from three-key triple DES. Two-key triple DES sets K3 equal to K1, using 112 bits of key material with an effective strength of about 80 bits against a particular known-plaintext attack. Three-key triple DES uses three independent keys, 168 bits of material, with an effective strength of about 112 bits.

4. Why does triple DES resist the meet-in-the-middle attack when double DES does not? Because with three stages there is no intermediate value reachable from both ends without already knowing one of the keys. The attacker must therefore guess one key and then mount the meet-in-the-middle on the remaining two, multiplying the work by that key's space: about 2 to the power 112 in all for three-key triple DES.

5. State the limit SP 800-67 Rev. 2 places on a key bundle, and why it exists. No more than 2 to the power 20 blocks of 64 bits may be protected under one key bundle, which is 1,048,576 blocks or 8,388,608 bytes, about 8 mebibytes. It exists because the block is only 64 bits, so repeated ciphertext blocks become likely as the volume grows and a repeat leaks a relationship between plaintexts. No key length removes the problem; only a larger block does.

6. What is the current status of triple DES? It has not been an approved block cipher since 1 January 2024, when NIST withdrew SP 800-67 Rev. 2 in its entirety, stating that TDEA is no longer an approved block cipher. Two-key encryption had already been disallowed in March 2019 and three-key encryption deprecated through 2023. Decryption, key unwrapping and verification of message authentication codes on already-protected data remain permitted.

7. Compare three-key triple DES with AES-128 and say which to choose. Three-key triple DES has 168 bits of key material against AES-128's 128, and is nevertheless weaker at about 112 bits of effective strength; it has a 64-bit block against AES's 128, which limits it to about 8 mebibytes per key; it is several times slower in software; and it is no longer approved. AES-128 is acceptable under current guidance. Choose AES.

Read five things out of that run.

The four standard ECB blocks match SP 800-38A F.1.1, which is the check that the cipher is correct before it is used to make any argument at all.

Ciphertext blocks 3 and 4 are the same sixteen bytes, dd45f549610b679c6821498d17416abf, twice. The plaintext held MARKS=FAIL twice, and the ciphertext says so. An observer with no key knows that two fields of that record are equal.

That is worth more than it looks. Suppose the observer knows the record format and holds a thousand such records. Every record whose blocks 3 and 4 match has the same value in both fields; every record sharing a block with one the observer can read shares that value. This is how ECB leaks in practice, and no key length helps, because the key was never the problem.

The same record chained has no repeated blocks at all. Five distinct ciphertext blocks from a plaintext containing a repeat, which is the next chapter.

And all five modes agree with the standard, F.1.1, F.2.1, F.3.13, F.4.1 and F.5.1. The implementations of the other four are only a few lines each on top of the same cipher, which is itself the point: a mode is a wrapper, and the cipher underneath does not change.

When ECB is acceptable

Rarely, and it is worth being precise rather than saying "never", because a question may ask.

A single block. If the message is exactly one block long, ECB and CBC are the same thing apart from the initialisation vector, and there is no repetition to leak. Encrypting one key with another, which is what key wrapping does, is the standard case.

Nowhere else. SP 800-38A defines ECB and the security guidance around it has grown steadily narrower. For any message of more than one block, another mode is the answer.

A worked example: reading an ECB ciphertext without the key

The setting. A college portal stores each student's record as five 16-byte fields, encrypted field by field with AES in ECB mode under one key. The attacker has a copy of the encrypted table and knows the format.

Step 1: find the repeats. Sort the ciphertext blocks and count. Any ciphertext block appearing in many records corresponds to a plaintext value appearing in many records.

Step 2: guess the commonest values. In a results table, the commonest value in the result field will be PASS. The attacker does not need to decrypt anything; they need only assume that the most frequent ciphertext block is the most frequent plaintext value. This is frequency analysis, exactly as in the monoalphabetic chapter, with 16-byte blocks in place of letters.

Step 3: confirm with one known record. If the attacker knows their own record, they know their own fields, so every block of their own record is a known plaintext and ciphertext pair. Every other record sharing those blocks is read.

Step 4: what the attacker cannot do. They cannot read a value that appears only once and that they do not already know, and they cannot forge a record they have not seen a block of. So ECB is not a total break; it is a leak of equality.

The step that carries the marks. Step 2. ECB turns a block cipher into a monoalphabetic substitution cipher whose alphabet is the set of 16-byte blocks. Saying that sentence is the answer.

Distinctions that carry marks

What beginners get wrong here

Saying ECB is insecure because the cipher is weak. The cipher is whatever you chose, and AES in ECB mode leaks. The mode is the defect.

Thinking the leak needs a repeated whole message. It needs a repeated block. Structured data repeats blocks constantly: field names, padding, common values, empty fields.

Saying ECB must never be used. For a single block there is nothing to leak, and key wrapping is a real use. Give the exception and the reason.

Forgetting padding. ECB needs the message to be a whole number of blocks, so a padding rule is required, and the padding itself must be unambiguous.

Quick revision

• ECB: Cj = E(K, Pj), each block independent, no state, no initialisation vector.
• The defect: equal plaintext blocks give equal ciphertext blocks. Demonstrated: a record with MARKS=FAIL twice produced dd45f549610b679c6821498d17416abf twice.
• It is effectively a monoalphabetic substitution cipher over 16-byte blocks, and frequency analysis applies.
• The attacker learns equality without learning values, and no key length helps.
• Needs padding; a corrupted bit damages its own block only; supports random access and parallel encryption.
• Acceptable for a single block, such as wrapping one key with another. Not for anything longer.
• The same record in CBC mode had no repeated ciphertext blocks.

Test yourself

1. State the ECB rule and its defining weakness. Each plaintext block is encrypted independently under the same key, Cj = E(K, Pj). The weakness is that identical plaintext blocks always produce identical ciphertext blocks, so any repetition in the plaintext is visible in the ciphertext to an attacker with no key.

2. Why is ECB called electronic codebook? Because for a fixed key the mode behaves like a codebook: every possible plaintext block has one fixed ciphertext block, so in principle an attacker could build a table of correspondences and look messages up in it.

3. What exactly does an attacker learn from an ECB ciphertext? That certain blocks of plaintext are equal to each other, and, if the attacker knows any plaintext and ciphertext pair, the value of every block equal to it. They learn equality rather than content, which for structured records is often enough to read most of the data.

4. Give the four properties of ECB an examination usually asks for. It needs padding; it is deterministic, so the same plaintext under the same key always gives the same ciphertext; a single corrupted ciphertext bit damages only its own block; and it supports random access and parallel processing because the blocks are independent.

5. Is there any legitimate use of ECB? Yes, for a message of exactly one block, where there is nothing to repeat. Wrapping one cryptographic key with another is the standard case. For any longer message another mode should be used.

6. Why does using AES rather than DES not fix ECB? Because the leak comes from the mode and not from the cipher. Whatever block cipher is used, encrypting each block independently under one key makes the mapping from plaintext block to ciphertext block fixed, so repeats show through. A longer key or a stronger cipher changes nothing about that.

7. Relate ECB to a cipher from earlier in this module. It is a monoalphabetic substitution cipher whose alphabet is the set of all blocks of the cipher's block size. Just as a monoalphabetic cipher over 26 letters preserves letter frequencies, ECB preserves block frequencies, and the same counting attack applies with blocks in place of letters.

distinct outputs over the first 2 to the power 20 inputs: 1048576
decrypt undoes encrypt: True

plaintext : PAY 0500 TO 8817  in four-byte blocks: 'PAY ' '0500' ' TO ' '8817'
ciphertext: c97171d3853cc84cad2814776d3f4d1e
decrypts  : PAY 0500 TO 8817

a fresh initialisation vector gives an unrelated ciphertext:
   IV 01234567 -> c97171d3853cc84cad2814776d3f4d1e
   IV ffeeddcc -> a69012c96aca3d8abd69134f700ca94c

error propagation: one bit of ciphertext block 2 corrupted
   sent     : PAY 0500 TO 8817
   received : b'PAY \xf1;\x1d\xec UO 8817'
     block 1: 'PAY '   -> 'PAY '      bits wrong: 0
     block 2: '0500'   -> 'ñ;\x1dì'   bits wrong: 15
     block 3: ' TO '   -> ' UO '      bits wrong: 1
     block 4: '8817'   -> '8817'      bits wrong: 0
   block 2 is destroyed and block 3 has exactly one bit wrong.
   Blocks 1 and 4 are untouched, so CBC recovers after two blocks.

the bit-flipping attack: the attacker chooses what block 4 says
   block 4 said      : '8817'
   attacker wanted   : '9999'
   they changed block 3 of the CIPHERTEXT, by 0101080e
   receiver decrypts : 'PAY 0500 pP~9999'
   block 4 is now    : '9999'  as wanted: True
   block 3 became    : ' pP~'

no key was used and no cipher was broken, because P4 = D(K, C4) XOR C3,
so any change to C3 appears unchanged in P4.
CBC gives confidentiality and NOT integrity.

Read five things out of that run.

The small cipher is a cipher. 1,048,576 distinct outputs from 1,048,576 inputs, and decryption undoes encryption. That check comes first.

Two initialisation vectors give two unrelated ciphertexts for the same plaintext and key. CBC is not deterministic, and that is what the IV is for.

A corrupted bit in ciphertext block 2 destroys plaintext block 2 and flips exactly one bit of block 3. The program counts the bit errors per block and prints them: 0, 15, 1, 0. And the reader can see it: TO came back as UO . The reason is the decryption equation Pj = D(K, Cj) XOR C(j-1): a changed bit of C(j-1) passes straight through the exclusive-or into Pj, while a changed bit of Cj goes through the inverse cipher and ruins the whole block. Blocks 1 and 4 are untouched, so CBC is self-synchronising: it recovers after two blocks.

The bit-flipping attack worked and the receiver read the attacker's text. PAY 0500 TO 8817 became PAY 0500 pP~9999 in the receiver's hands. The attacker exclusive-ored 0101080e, the difference between 8817 and 9999, into ciphertext block 3, and block 4 came out as 9999. No key was used and no cipher was broken. The price was block 3, which became rubbish, and in most real message formats a sacrificed block is a header, a timestamp or a field the application ignores.

So confidentiality is not integrity, and CBC gives only the first. This is why every modern protocol carries a message authentication code over the ciphertext, and it is what Module 1's later chapters on MACs are for. "Is CBC secure" is answered: secure for confidentiality given an unpredictable, fresh IV, and no protection whatever against modification.

A worked example, by hand

The setting. Block size 8 bits for arithmetic that fits on a page. Plaintext blocks P1 = 10110010 and P2 = 10110010, the same block twice. IV is 01100101. Take the block cipher to be a function E whose values are given.

Step 1: block 1. P1 XOR IV is 10110010 XOR 01100101, which is 11010111. That goes into the cipher, and suppose E(K, 11010111) is 00101101. So C1 = 00101101.

Step 2: block 2. P2 XOR C1 is 10110010 XOR 00101101, which is 10011111. Suppose E(K, 10011111) is 11110000. So C2 = 11110000.

Step 3: the point. P1 and P2 were identical and C1 and C2 are not, because the second was encrypted after being exclusive-ored with the first ciphertext block. Under ECB both would have been 00101101.

Step 4: decrypt block 2. D(K, C2) gives back 10011111, and exclusive-oring C1 gives 10011111 XOR 00101101, which is 10110010, which is P2. The receiver needs C1, which they have, and does not need P1.

Distinctions that carry marks

Two rows are worth dwelling on. Encryption is sequential and decryption is parallel, because encrypting block j needs C(j-1) but decrypting it needs only Cj and C(j-1), both of which are already in hand. And the last row is the same for both modes: neither gives integrity.

What beginners get wrong here

Thinking the IV must be secret. It must be unpredictable. It is normally sent in the clear.

Reusing one IV for every message. That makes CBC deterministic for the first block and leaks whether two messages begin the same way.

Saying a corrupted bit destroys the rest of the message. It destroys its own block and one bit of the next, and then the chain recovers. CBC is self-synchronising.

Saying CBC provides integrity because a change is detected. A change produces different plaintext; it does not produce an error. Unless the application can tell that the plaintext is wrong, nothing is detected, and the bit-flipping attack shows an attacker choosing exactly what the wrong plaintext says.

Forgetting that encryption cannot be parallelised. It is the practical cost of CBC and the reason counter mode is preferred for high throughput.

Quick revision

• CBC: C1 = E(K, P1 XOR IV), Cj = E(K, Pj XOR C(j-1)). Decrypt with Pj = D(K, Cj) XOR C(j-1).
• The IV must be unpredictable, need not be secret, and must be fresh per message. A fresh IV is what makes CBC non-deterministic.
• Chaining removes the ECB leak: equal plaintext blocks give different ciphertext blocks.
• One corrupted ciphertext bit: its own plaintext block is destroyed and one bit of the next flips. ACCOUNT became @CCOUNT. Then the chain recovers, so CBC is self-synchronising.
• Encryption is sequential; decryption is parallel.
• The bit-flipping attack: changing ciphertext block j-1 lets an attacker choose the plaintext of block j exactly, destroying block j-1 in the process. Performed in this chapter with no key.
• CBC gives confidentiality and no integrity. Add a message authentication code.

Test yourself

1. Give the CBC encryption and decryption equations. C1 = E(K, P1 XOR IV) and Cj = E(K, Pj XOR C(j - 1)) for later blocks. Decryption is P1 = D(K, C1) XOR IV and Pj = D(K, Cj) XOR C(j - 1).

2. What are the requirements on the initialisation vector? It must be available to the receiver, so it is usually sent in the clear; it must be unpredictable to an attacker, so it should be random or otherwise unguessable; and it must be fresh for each message, because reusing it makes the mode deterministic and leaks whether two messages share a beginning. It need not be secret.

3. How does CBC remove the weakness of ECB? By making each ciphertext block depend on all preceding plaintext blocks. Two identical plaintext blocks are exclusive-ored with different preceding ciphertext blocks before encryption, so their ciphertexts differ and the repetition is no longer visible.

4. What is the effect of one corrupted bit in a CBC ciphertext? The plaintext block corresponding to that ciphertext block decrypts to rubbish, because the corrupted bit passes through the inverse cipher; and exactly the same one bit of the following plaintext block flips, because the corrupted ciphertext block is exclusive-ored into it directly. Later blocks are unaffected, so the mode is self-synchronising.

5. Describe the bit-flipping attack on CBC and what it shows. An attacker who knows or guesses plaintext block j exclusive-ors into ciphertext block j-1 the difference between that plaintext and the plaintext they want. The receiver then decrypts block j as the attacker's chosen text, at the cost of block j-1 becoming rubbish. It shows that CBC provides confidentiality only: the ciphertext can be modified to produce a chosen plaintext without any knowledge of the key, so a separate integrity mechanism is required.

6. Why can CBC decryption be parallelised when encryption cannot? Because encrypting block j needs C(j-1), which is not known until block j-1 has been encrypted, so encryption must proceed in order. Decrypting block j needs only Cj and C(j-1), both of which are already present in the received ciphertext, so every block can be decrypted at once.

7. Is CBC a good choice today? Give a qualified answer. For confidentiality with an unpredictable, fresh initialisation vector it is sound and widely used. It provides no integrity, so it must be combined with a message authentication code or replaced by an authenticated mode; and its encryption is sequential, so counter mode is preferred where throughput matters.

Read six things out of that run.

OFB and CTR have a key stream of their own and CFB does not. The first four blocks of each are printed. CFB's stream depends on the ciphertext, so it cannot be computed until the data arrives; OFB's and CTR's can be generated in advance, which matters for a device that must encrypt at line speed.

CFB and OFB agree on block 1 and nowhere else. Both compute the first key stream block as E(K, IV), so the first ciphertext block is identical. From block 2 they diverge, because CFB's register has taken the ciphertext and OFB's has taken the cipher's own output. That is the whole difference between the two modes, and seeing it in the output fixes it in a way the diagrams do not.

All three decrypt with the same operation that encrypts, and all three recovered PAY 0500 TO 8817. No inverse cipher is needed anywhere, which is why these modes are cheap in hardware.

No padding, for any of the three. One, three and seven bytes in; one, three and seven out.

Only CTR gives random access. Block 5 of the plaintext was recovered from block 5 of the ciphertext alone, because its key stream block is E(K, counter + 4) and depends on nothing else. CFB needs the previous ciphertext block and OFB needs the stream from the beginning, so neither can start in the middle.

One flipped ciphertext bit costs CFB three bytes and OFB and CTR one bit. CFB: the flipped bit gives one wrong plaintext bit, and then that corrupted ciphertext is fed back, so the whole of the next block's key stream is wrong. OFB and CTR: one bit, and nothing else, because their key streams never touch the ciphertext.

And the rule. Two messages under the same counter value: c1 XOR c2 came out exactly equal to p1 XOR p2. The key cancels, as in the one-time pad chapter. So a counter value or an OFB initialisation vector must never repeat under one key. That is not a subtlety; it is the whole security of the mode.

A worked example: choosing the mode

Job 1: encrypt a 10 gigabyte disk image, where any sector may be read on its own.

Counter mode. Random access is the requirement, and only CTR has it: the key stream for sector n depends only on n. CBC would force a read of the previous block, and OFB would force generating the stream from the beginning.

Job 2: encrypt a terminal session, one character at a time, over a link that drops bits.

Cipher feedback with s of 8. It can encrypt one byte as soon as it arrives, and it is self-synchronising: after a lost or corrupted byte, the register refills with correct ciphertext after 16 bytes and the mode recovers on its own. OFB and CTR do not recover from a lost byte at all, because the key stream position no longer lines up.

Job 3: encrypt a satellite telemetry stream over a noisy channel where bits flip but none are lost.

Output feedback. A flipped bit affects exactly one plaintext bit, which is what an error-correcting code above it can repair. In CFB the same flipped bit would ruin the next sixteen bytes and defeat the correction.

Job 4: the general case, in a modern protocol.

Counter mode combined with an authentication tag, which is what Galois/Counter Mode is and what TLS 1.3 requires. The pattern to remember: CTR for the encryption, a MAC for the integrity, and never one without the other.

The step that carries the marks. Each answer names the property that decided it: random access, self-synchronisation, single-bit error confinement. An answer saying "CTR is the most modern" has not answered.

Distinctions that carry marks

What beginners get wrong here

Saying OFB and CTR "use decryption" to decrypt. They do not. Both use the cipher forwards in both directions, because the key stream is exclusive-ored either way.

Confusing CFB's and OFB's feedback. CFB feeds back the ciphertext; OFB feeds back the cipher's output. It is the only difference and it is the examinable one.

Saying OFB is self-synchronising. It is not. CFB is, because its register refills with received ciphertext; OFB's register is generated locally and never resynchronises.

Thinking a single-bit error is always better. It is better against noise and much worse against an attacker, who can flip exactly the bits they want in the plaintext. These modes need integrity protection more than CBC does.

Reusing a counter or an OFB initialisation vector. It is the one fatal error, and the run proves it: the key cancels and the difference of the plaintexts is exposed.

Quick revision

• All three build a key stream and exclusive-or it with the data, use the cipher forwards only, and need no padding.
• CFB shifts the ciphertext into the register. OFB shifts the cipher's own output. CTR encrypts a counter.
• CFB and OFB agree on block 1 and diverge after, because both start from E(K, IV).
• One flipped ciphertext bit: CFB its own bit plus the whole next block (17 bytes in the run); OFB and CTR one bit.
• A lost byte: CFB recovers after a block; OFB and CTR never do.
• Only CTR has random access and parallel encryption. Its key stream block for position j is E(K, counter + j - 1) and depends on nothing else.
• OFB and CTR key streams are precomputable before the plaintext arrives.
• A counter value or an OFB IV must never repeat under one key. Proved: c1 XOR c2 equals p1 XOR p2 and the key vanishes.
• None of the three gives integrity; the modern answer is counter mode plus an authentication tag, which is what TLS 1.3 requires.

Test yourself

1. Give the defining rule of each of the three modes. Cipher feedback encrypts the shift register, takes the leftmost s bits as key stream, and shifts the resulting ciphertext back into the register. Output feedback does the same but shifts the cipher's own output back, so the key stream is independent of the data. Counter mode encrypts a counter that increases by one per block and exclusive-ors the result with the plaintext, with no feedback at all.

2. What is the single difference between CFB and OFB, and what does it cause? What is fed back: the ciphertext in CFB, the cipher's output in OFB. It causes every other difference: CFB's key stream depends on the data, so a transmission error propagates into the next block and the mode is self-synchronising; OFB's does not, so an error affects one bit only and the mode never resynchronises after a lost byte.

3. Why do none of these modes need padding? Because the block cipher is used to produce a key stream rather than to transform the plaintext directly. The stream is truncated to the length of the message and exclusive-ored with it, so the ciphertext is exactly as long as the plaintext.

4. Why is counter mode the only one of the three with random access? Because the key stream block for position j is E(K, counter + j - 1), computable from j alone. CFB needs the preceding ciphertext block and OFB needs the stream generated from the initialisation vector onwards, so neither can start in the middle.

5. Compare the damage from one flipped ciphertext bit across CBC, CFB, OFB and CTR. CBC: the whole of its own plaintext block plus the same one bit of the next. CFB: its own bit, and then the whole of the next block, because the corrupted ciphertext enters the register. OFB and CTR: that one bit and nothing else. In the chapter's run CFB lost 17 bytes where OFB and CTR each lost one.

6. State the one rule that must never be broken in OFB and CTR, and why. A counter value, or an output feedback initialisation vector, must never be used twice under the same key. If it is, two ciphertexts share a key stream, and exclusive-oring them removes the key entirely and leaves the exclusive-or of the two plaintexts. The chapter's run checks this: c1 XOR c2 equalled p1 XOR p2 exactly.

7. Which mode would you choose for a full-disk encryption product, and which for a character-at-a-time terminal link? Counter mode for the disk, because any sector must be readable on its own and its key stream depends only on the sector number. Cipher feedback with s of 8 for the terminal link, because a single character can be encrypted as soon as it is typed and the mode resynchronises by itself after a corrupted or lost byte.

Read five things out of that run.

The vector matches RFC 6229. b2396305f03dc027ccc3524a0a1118a8 for the key 0102030405, which is the first line of the RFC's own table.

Encryption and decryption are the same operation. rc4(rc4(m, k), k) is m, because exclusive-or is its own inverse. That is true of every stream cipher and is why they are cheap.

The bias is real and it is large. Over 200,000 random 16-byte keys, the second key stream byte took the value 0 on 1,555 occasions where a fair generator would give about 781. The ratio is 1.99. This is Mantin and Shamir's result of 2001: the second output byte of RC4 is zero with probability about 2 in 256 rather than 1 in 256, and that single fact is enough to distinguish RC4's output from random, which is the formal definition of a broken stream cipher.

The third and second commonest values are unremarkable. 215 appeared 856 times and 133 appeared 850, both close to the expected 781. So the bias is specific to the value 0 in position 2 and is not noise in the measurement: one value is twice as likely and the rest are where they should be.

And the key stream must never repeat. Two messages under the key Secret gave c1 XOR c2 exactly equal to p1 XOR p2. The key vanished. This is the failure that destroyed WEP.

Why RC4 is banned, with the dates

The WEP failure is worth understanding because it is the clearest example in this subject of a sound component destroyed by its use. WEP combined a 24-bit initialisation vector with a fixed secret key and fed the concatenation straight into RC4's key schedule. Three things followed. A 24-bit initialisation vector repeats after about 16 million packets, which a busy network reaches in hours, and a repeat means a reused key stream. The initialisation vector was sent in the clear, so an attacker knew part of every RC4 key. And the key schedule's weakness meant that knowing part of the key made the first key stream bytes predictable. None of those is a flaw in RC4's arithmetic; all three are flaws in how RC4 was used.

A worked example: tracing the key schedule by hand

The setting. Key 1 2 3, three bytes. Trace the first three steps of the key scheduling algorithm.

Step 0. S starts as the identity: S[0] is 0, S[1] is 1, and so on to S[255] is 255. And j starts at 0.

Step 1, i is 0. j becomes (0 + S[0] + key[0]) mod 256, which is (0 + 0 + 1) mod 256, which is 1. Swap S[0] and S[1]. Now S[0] is 1 and S[1] is 0.

Step 2, i is 1. j becomes (1 + S[1] + key[1]) mod 256, which is (1 + 0 + 2) mod 256, which is 3. Swap S[1] and S[3]. Now S[1] is 3 and S[3] is 0.

Step 3, i is 2. j becomes (3 + S[2] + key[2]) mod 256, which is (3 + 2 + 3) mod 256, which is 8. Swap S[2] and S[8]. Now S[2] is 8 and S[8] is 2.

The step that carries the marks. Notice that key[i mod keylen] cycles through the key, so a three-byte key is used about 85 times across the 256 steps, and notice that j accumulates: it is never reset, so each step depends on every step before it. Those two facts together are what makes the schedule a shuffle rather than a pattern, and they are also where the Fluhrer, Mantin and Shamir attack gets its grip: the early values of j depend on only the first few key bytes.

Distinctions that carry marks

What beginners get wrong here

Saying RC4 is insecure because its key is short. The key may be up to 256 bytes. RC4 is insecure because its output is biased and because its key schedule leaks, not for want of key length.

Blaming RC4 for WEP. WEP's failures were a 24-bit initialisation vector that repeats, an initialisation vector sent in the clear and concatenated with the key, and no integrity protection. RC4 was the victim, not the culprit, although its key schedule made the last step easy.

Thinking a stream cipher needs a separate decryption routine. It does not. The same function encrypts and decrypts.

Forgetting that the key stream must never repeat. It is the single operating rule, and the run demonstrates the consequence.

Claiming RC4 is still acceptable somewhere. RFC 7465 of February 2015 prohibits it in TLS in terms: clients must not offer RC4 cipher suites and servers must not select one.

Quick revision

• A stream cipher generates a key stream from the key and exclusive-ors it with the data, one bit or byte at a time. Encryption and decryption are the same operation.
• Design conditions: a long period, statistically random output, a key long enough to resist brute force, and the key stream must depend on the whole key.
• The operating condition: never use a key stream twice.
• RC4, Rivest 1987, key 1 to 256 bytes. KSA permutes a 256-byte array once using the key; PRGA then emits one byte per call, swapping two entries and outputting a third, and never looks at the key again.
• Verified against RFC 6229: key 0102030405 gives b2396305f03dc027ccc3524a0a1118a8.
• Measured bias: over 200,000 random keys the second output byte was 0 on 1,555 occasions against an expected 781, a ratio of 1.99, matching Mantin and Shamir's factor of 2.
• Prohibited in TLS by RFC 7465, February 2015.
• WEP failed by reusing key streams: a 24-bit initialisation vector that repeats within hours, sent in the clear and concatenated with the key.

Test yourself

1. Define a stream cipher and give RC4's two parts. A stream cipher encrypts a data stream one bit or byte at a time by generating a key stream from the key and combining it with the plaintext, normally by exclusive-or. RC4 has a key scheduling algorithm, which uses the key to permute a 256-byte state array in 256 steps, and a pseudorandom generation algorithm, which produces one key stream byte per call by swapping two entries of that array and outputting a third.

2. State the design conditions for a key stream generator. The period must be very long, at least 2 to the power 128, because a repeat causes key stream reuse within a single message. The output must be statistically indistinguishable from random. The key must be long enough to resist exhaustive search, at least 128 bits. And the key stream must depend on the whole key, so that knowing part of the key does not make part of the stream predictable.

3. What is the bias in RC4's output, and what does it mean? The second byte of the key stream takes the value zero with probability about 2 in 256 rather than the 1 in 256 a fair generator would give. The chapter measures it over 200,000 random keys and finds 1,555 occurrences against an expected 781, a ratio of 1.99. It means RC4's output is distinguishable from random, which is the formal definition of a broken stream cipher, and it allows plaintext recovery from many sessions encrypting the same data.

4. Why is encryption the same as decryption in a stream cipher? Because the plaintext is combined with the key stream by exclusive-or, and exclusive-or is its own inverse: applying the same key stream to the ciphertext returns the plaintext. The key stream is generated from the key alone and does not depend on the data, so the receiver can produce the identical stream.

5. Explain how WEP failed, and say whether RC4 was to blame. WEP concatenated a 24-bit initialisation vector, sent in the clear, with a fixed secret key, and used the result as an RC4 key. A 24-bit value repeats after about 16 million packets, which a busy network reaches within hours, so key streams were reused and exclusive-oring two ciphertexts removed the key. The initialisation vector being public also gave an attacker part of every key, and RC4's key schedule made the early key stream bytes predictable from that. The design of the protocol was the primary fault, although RC4's key schedule made the final step easy.

6. What is RC4's current status? Prohibited in Transport Layer Security by RFC 7465 of February 2015, which requires clients not to offer RC4 cipher suites and servers not to select one. It should not be used anywhere.

7. Trace the first step of RC4's key schedule for the key 1 2 3. The array starts as the identity, with S[n] equal to n, and j starts at 0. With i at 0, j becomes (0 + S[0] + key[0]) mod 256, that is (0 + 0 + 1) mod 256, which is 1; then S[0] and S[1] are swapped, so S[0] becomes 1 and S[1] becomes 0.

Read five things out of that run.

A negative remainder is brought into range. Minus 7 modulo 12 is 5, not minus 7. This is the arithmetic slip that ruins hand-worked decryptions, and Python does it correctly by default, which is worth knowing when checking your own work.

Modulo 7 every non-zero row of the multiplication table is a permutation of 1 to 6. Row 3, for instance, is 3, 6, 2, 5, 1, 4. Since 1 appears in every row, every non-zero element has an inverse, and that is what it means for the integers modulo a prime to form a field.

Modulo 12 it fails, and you can see exactly where. Row 5 is a permutation, so 5 has an inverse. Row 2 is 0, 2, 4, 6, 8, 10, 0, 2, 4, 6, 8, 10: it repeats after six entries and never reaches 1, so 2 has no inverse. Row 3 is the same story with period 4. The discriminator is the gcd: 5 shares no factor with 12, while 2 and 3 do.

Euclid's algorithm took five divisions on numbers of four digits. That is the point of it: the numbers fall fast, because each step replaces the pair by the smaller number and the remainder. For numbers of 1,024 bits it takes a few thousand steps, not 2 to the power 1,024.

The extended algorithm prints its own proof. For 7 and 160 it produced the identity with coefficients 23 and minus 1, so 7 times 23 plus 160 times minus 1 comes to one, and 23 is therefore the inverse of 7 modulo 160, which the run then checks by multiplying. That pair of numbers will reappear in the RSA chapter as e and d.

Euclid's algorithm, by hand

The algorithm rests on one observation: gcd(a, b) equals gcd(b, a mod b). Any common divisor of a and b divides a - qb for any q, and any common divisor of b and a - qb divides a, so the two pairs have the same common divisors and the same greatest one. Repeating shrinks the numbers until one is zero, and the other is the answer.

Find gcd(1180, 482). Divide and keep the remainder each time.

1180 divided by 482 is 2 remainder 216. 482 divided by 216 is 2 remainder 50. 216 divided by 50 is 4 remainder 16. 50 divided by 16 is 3 remainder 2. 16 divided by 2 is 8 remainder 0.

The last non-zero remainder is 2, and that is the gcd. The run above prints exactly those five rows.

The extended algorithm, and why it gives an inverse

The extended algorithm keeps track of how each remainder was built out of the original two numbers, so that at the end it can write

which is called Bezout's identity. Now suppose gcd(a, n) is 1. Then a x + n y = 1, and reading that modulo n the second term vanishes, leaving a x congruent to 1 modulo n. So x is the inverse of a modulo n, and if x came out negative you add n.

Find the inverse of 3 modulo 26, which the Hill chapter needed. The run gives coefficients 9 and minus 1, so 3 times 9 plus 26 times minus 1 comes to one, the inverse is 9, and 3 times 9 is 27, which is 1 modulo 26.

Find the inverse of 2 modulo 26. The algorithm returns a gcd of 2, not 1, so there is no inverse, which is exactly the Hill cipher's unusable key.

A worked example a question will actually set

"Given p of 47 and q of 71 and e of 79, find d."

Step 1: the modulus and the totient. n is 47 times 71, which is 3,337. And phi(n) is 46 times 70, which is 3,220.

Step 2: check e is usable. gcd(79, 3220). 3220 divided by 79 is 40 remainder 60. 79 divided by 60 is 1 remainder 19. 60 divided by 19 is 3 remainder 3. 19 divided by 3 is 6 remainder 1. 3 divided by 1 is 3 remainder 0. The gcd is 1, so e is usable.

Step 3: run the extended algorithm backwards. From the divisions above, substituting each remainder in turn: 1 is 19 minus 6 times 3; 3 is 60 minus 3 times 19, so 1 is 19 minus 6 times (60 minus 3 times 19), which is 19 times 19 minus 6 times 60; 19 is 79 minus 60, so 1 is 19 times (79 minus 60) minus 6 times 60, which is 19 times 79 minus 25 times 60; and 60 is 3220 minus 40 times 79, so 1 is 19 times 79 minus 25 times (3220 minus 40 times 79), which is 1,019 times 79 less 25 times 3,220.

Step 4: read off d. d is 1019.

Step 5: check. 79 times 1019 is 80,501. And 3220 times 25 is 80,500. So 80,501 is 1 more than a multiple of 3,220, which means 79 times 1019 is congruent to 1 modulo 3,220. Correct.

The step that carries the marks. Step 3, the back-substitution, is the only difficult part and it is entirely mechanical: work upwards through the divisions, replacing each remainder by its expression. Write out the divisions first, then substitute. And always do step 5.

Distinctions that carry marks

What beginners get wrong here

Writing a negative remainder. Minus 2 modulo 26 is 24. Bring every intermediate value into the range 0 to n - 1.

Assuming division works. You may not divide modulo n; you multiply by an inverse, and the inverse may not exist.

Forgetting to check the gcd before looking for an inverse. If gcd(a, n) is not 1 there is nothing to find, and the algorithm tells you so.

Confusing phi(n) with n when finding d. d is the inverse of e modulo phi(n), never modulo n. It is the commonest error in an RSA question.

Not checking the answer. e times d modulo phi(n) must be 1. It takes one multiplication and it catches every slip.

Quick revision

• a congruent to b mod n means n divides a - b; there are n residue classes.
• Addition, subtraction and multiplication are well defined on the classes, so you may reduce at any point.
• a has an inverse modulo n if and only if gcd(a, n) = 1. Modulo a prime, every non-zero element has one, so the integers modulo a prime form a field.
• Euclid: gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0. gcd(1180, 482) is 2 in five divisions.
• Extended Euclid gives a x + n y = gcd(a, n), Bezout's identity. When the gcd is 1, x is the inverse of a modulo n, brought into range by adding n if negative.
• Inverse of 7 modulo 160 is 23; of 3 modulo 26 is 9; 2 modulo 26 has none.
• d is the inverse of e modulo phi(n), not modulo n. Always check e d mod phi(n) = 1.