How hard is “too hard”?

A fictional file-storage company advertises: “We use a 256-bit key, so nobody can read your files.” During a review, you discover that the company includes the decryption key in the same downloadable folder as the encrypted files.

Would a larger key solve that problem? An attacker who can read the key does not need to search for it. The impressive number describes a possible brute-force attack, while the actual system offers an easier route.

This lesson develops the missing reasoning: what an attacker must accomplish, how much work that takes, and which assumptions make the estimate meaningful.

Textbook connection: Chapter 3, “Cryptographic Security,” in Serious Cryptography, second edition. Focus on security definitions, bits of security, full attack cost, confidence in a design, and generating and protecting keys. The calculations below use original teaching examples and hypothetical speeds.

Bring the first two topics with you

Encryption transforms plaintext into ciphertext under a key. A security claim identifies what is protected and what an attacker can do. Randomness matters because the attacker should not be able to predict the key.

Now add a third question: How much work would the attacker need?

“Break” also needs a definition. Recovering a key, recovering a message, and forging an authenticated message are different goals. An attacker may learn a message without ever recovering a key. A result about one goal does not automatically cover another.

Two meanings of impossible

Unconditional security

Unconditional security does not rely on the attacker's lack of computing power. Under the stated model, unlimited computation still does not reveal the protected information beyond what the model permits.

A correctly used one-time pad gives a useful confidentiality example. Its key is uniformly random, independent of the message, as long as the message, secret, and never reused. The ciphertext alone cannot identify which same-length plaintext was sent: every candidate plaintext is compatible with a possible key. This preserves uncertainty about the content; it does not hide the message length or provide authentication.

The conditions matter. Reusing the pad removes that guarantee. So does exposing it. This example introduces a definition; it is not a proposal for a home-built encryption system.

Computational security

Computational security says the specified attack is infeasible within the assumed resources and time. An attack may exist in principle but be far too expensive to carry out.

An ideal large-key cipher can be attacked by trying every possible key. That does not make the search practical. The key question is whether any feasible method achieves the attacker's goal, including a shortcut that avoids full search.

Count possible keys before estimating time

A bit can take two values. Adding another independent bit doubles the combinations.

We write the number of possible n-bit keys as 2^n, pronounced “two to the power n.” The exponent counts repeated doubling. It does not mean 2 multiplied by n.

Going from 20 to 21 bits doubles the key space. Going from 20 to 24 bits doubles it four times: 2^4 = 16 times as many keys. A small increase in bit count can produce a large increase in work.

The calculation assumes every bit string is a valid candidate. Public-key systems often require special mathematical structure, so do not apply this raw-bit model to every key-generation scheme.

Search coverage is a probability

Suppose one target key is selected uniformly from 64 possibilities. The attacker tries 8 distinct candidates. The chance that those candidates contain the target is:

success probability = distinct candidates tried / possible keys
                    = 8 / 64
                    = 0.125 = 12.5%

Trying 32 of the 64 candidates gives a 50% chance. Trying all 64 covers the whole set. Repeating a failed candidate adds no coverage.

This model assumes one uniformly selected target, different guesses, and a reliable way to recognize the correct key. It does not describe a biased password list or an attack with another route to plaintext.

The Search Coverage interaction makes this visible. Highlighted squares are the candidates searched. The target is equally likely to be in any square. You do not need to run an actual attack to calculate the probability.

Worst case, average, and scale

For N equally likely candidates searched without replacement:

• Full search / worst case: N trials.
• Expected trials until success: (N + 1) / 2, approximately half the space for large N.
• Probability after t distinct trials: t / N, capped at 1.

Halfway through a search is not a guarantee of success. “Expected” describes an average over possible target positions. In discussions of bit security, constant factors are often suppressed, so exhaustive search of an n-bit key space is described as work on the scale of 2^n operations.

Turn work into elapsed time

An operation count is not a clock reading. We also need a rate.

full-search seconds = candidate keys / effective trials per second

For a teaching example, assume a rate of 1,024 trials per second. This is an invented rate for practicing arithmetic, not a benchmark for AES, RSA, a laptop, or a password cracker.

Four additional bits multiplied the work by 16. Sixteen perfectly cooperating workers canceled that increase in elapsed time. They did not make the key shorter or reduce the total number of candidate evaluations.

The Attack Budget workbench also shows expected time. For the 20-bit example, it is about 512 seconds. Always label which estimate you report.

Key length and security level are different

Key length describes the size of a key or a scheme-specific key parameter. Bits of security describe the approximate work required by the best relevant attack, for a stated goal and success level.

An attack requiring roughly 2^40 comparable operations corresponds to about 40 bits of work. An ideal uniformly generated n-bit symmetric key offers at most n-bit resistance to exhaustive key search. An easier attack can lower the effective resistance.

Consider a fictional 128-bit key field that is generated from only 2^20 equally likely starting states. If an attacker can enumerate those states and reconstruct the candidate keys cheaply, the field's 128-bit size does not force a 2^128 search. The generator offers a much smaller search path.

For asymmetric cryptography, do not compare printed key sizes directly with symmetric key sizes. The algorithms rely on different mathematical problems and attacks. A public-key parameter with thousands of bits does not automatically offer thousands of bits of security.

Pause and explain: What information is missing from “this system has a 2,048-bit key”? You need the algorithm, security goal, key generation, relevant attacks, and implementation context before interpreting that number.

The full cost of an attack

Chapter 3 asks us to look beyond one operation count. Four factors deserve attention.

Parallelism: can the work be divided?

Independent key guesses can be split among workers. In an ideal model, 16 equal workers finish the same total work in one-sixteenth the time. Real systems have coordination, hardware, energy, and data-transfer costs.

Some attacks contain a sequence in which each step needs the previous result. More workers do not automatically shorten that sequence. Switch the workbench to Sequential dependency: extra workers no longer improve its idealized time.

Memory: can the attacker store and access the data?

An attack with fewer arithmetic operations may need a huge lookup table. Storage capacity, memory speed, and access patterns can make it impractical. “Fewer operations” is not enough to choose a winner when operations and memory costs differ.

Precomputation: what work happened before the stopwatch started?

A lookup attack may spend days preparing a table, then answer a later query in seconds. Those seconds are the online stage, not the whole cost. When the same preparation can be reused, it can become worthwhile across many targets. Whether it can be reused depends on the system.

Targets: one particular secret or any useful secret?

An attacker seeking any one of many accounts may have more opportunities than an attacker seeking one specific account. Some attacks can reuse work or compare a trial against multiple targets efficiently. This does not mean that every attack becomes exactly M times faster for M targets; target structure and comparison costs matter.

Our calculator models one target. It does not model memory costs, reusable tables, many targets, quantum algorithms, or measured hardware performance.

How do we gain confidence in security?

A mathematical argument has a scope

Provable security often connects breaking a construction to breaking an underlying primitive or solving an assumed-hard problem. The argument has a security goal, assumptions, and bounds. It does not establish that every deployed program using the construction is safe.

Imagine a valid proof that protects confidentiality when the key remains secret. Publishing the key does not contradict the proof; it violates an assumption. A proof about one security goal also does not automatically establish another goal, such as message authenticity. Proofs themselves require review and can contain errors.

Public attack analysis supplies another kind of evidence

Heuristic security refers here to confidence built through analysis and unsuccessful attempts to find effective attacks. Experienced researchers examining a design over time provide more useful evidence than a vendor saying nobody has complained.

Neither approach is a promise that no new attack will appear. Mathematical arguments and public cryptanalysis contribute different evidence. Both must be joined with correct implementation and key handling.

Generate the right key, then protect it

Chapter 3 identifies three broad ways to establish keys: random generation, derivation from a password, and key agreement. We focus on what each claim must account for.

• Random generation: Use the appropriate cryptographic generator and the scheme's key-generation routine. Many symmetric schemes accept a fixed number of random key bits. Asymmetric schemes generally need a routine that constructs valid related mathematical objects.
• Password-based derivation: A password-based key derivation function increases the cost of testing guesses, but it cannot turn a predictable password into a source of unlimited entropy. Output length is not proof of password strength.
• Key agreement: Parties establish a shared secret through a protocol. The protocol's authentication and other assumptions need their own analysis; those details come later.

Protection must continue after generation. Key wrapping encrypts a key under another protected key, moving part of the trust to that wrapping key and its access controls. A hardware-backed store can restrict extraction, but a compromised application may still misuse permitted operations. No storage choice removes the need to examine who can use the key.

Do not place a private key in a public repository, ship it beside the encrypted data under the same access permissions, or confuse a public key with a private key.

Repair a security claim

Original claim:

“Our large key makes the backup impossible to break.”

A more useful version:

“The backup is intended to keep stored records confidential from someone who copies the encrypted files but cannot access the decryption key. Our brute-force estimate assumes uniformly generated keys, distinct trials, and no more efficient attack. We must separately evaluate key storage, access to the running application, and implementation errors.”

This does not promise safety against every attacker. It identifies the protection being claimed and the evidence still needed.

The next topic studies block ciphers. Keep asking the same questions: Which attack? How much work? At what success probability? Under which assumptions?

Measuring security: review sheet

Keep these ideas separate

Small calculation toolkit

For one uniformly selected key, distinct guesses, and reliable recognition:

N = 2^n possible n-bit strings
P(success after t distinct guesses) = min(t / N, 1)
full-search trials = N
expected trials = (N + 1) / 2
full-search seconds = N / effective trials per second
ideal independent rate = rate per worker × workers
adding k key bits multiplies the space by 2^k

Examples to anchor the notation: 2^8 = 256; 2^10 = 1,024; 2^20 = 1,048,576. Half the search space means 50% coverage, not guaranteed success.

These are teaching models, not measurements of real cryptographic implementations.

Common mistakes

• Reading 2^20 as 2 × 20.
• Saying four extra key bits multiply the search space by four.
• Reporting an attack time without a rate, units, or assumptions.
• Treating average time as a deadline by which success is certain.
• Assuming all work parallelizes perfectly.
• Comparing operation counts without checking what each operation costs.
• Treating a long key field as proof of high entropy.
• Comparing public-key and symmetric key lengths directly.
• Believing a proof includes stolen keys or every implementation behavior.
• Reporting only an online lookup time while ignoring table-building work.

Retrieve the ideas

Explain these aloud or in your notes. This is optional study practice, not a graded assessment.

1. What conditions make a one-time pad's confidentiality guarantee possible?
2. What is the difference between impossible in principle and infeasible in practice?
3. How many times larger is a 22-bit raw key space than a 20-bit space?
4. In a 256-key uniform space, what probability does 64 distinct guesses cover?
5. If 16 workers split independent work ideally, what happens to time and total work?
6. Why can a 128-bit key field have much less than 128 bits of effective resistance?
7. What evidence does public cryptanalysis contribute? What does it fail to guarantee?
8. Why does wrapping a key require protecting another key?

Before trusting an estimate

Name the target and goal. Check key generation and protection. Identify the best relevant attack rather than only the obvious one. Distinguish its operation count from its time, memory, preparation, and target assumptions. State what remains outside the claim.