01/2020

# 128 Bits of Security and 128 Bits of Security: Know the Difference

It might save some CPU. :-)

When I started working on Monocypher, I quickly noticed something strange about Daniel J. Bernstein's choices of ciphers and curves. On the one hand, he favoured (and designed) ciphers that have 256 bits of security, and explained in painstaking details that 128-bit encryption keys may not be quite enough for all applications. On the other hand, he designed Curve25519, whose security goal is… 128 bits.

That apparent contradiction stumped me for months, during which I simply chose to blindly trust DJB's reputation. Unsurprisingly, it turned out he thought this through, and there's no contradiction. "128 bits of security" just means different things in different contexts.

## Naive brute force

### Key search

It goes pretty much like this:

- Encrypt your plaintext with some key.
- Compare with the ciphertext.
- If it's the same, you have found the key! Otherwise, try again with another key.

Finding a 128-bit key requires about 2¹²⁸ tries.

### Hash preimage

Finding a preimage of a given hash is very similar:

- Hash some input.
- Compare with the hash you were trying to obtain.
- If it's the same, you have found a preimage! Otherwise, try again with another input.

Finding the preimage of a 128-bit hash requires about 2¹²⁸ tries (note: 128-bit hashes are generally too small, because of collisions).

### Hash collisions

Hash collisions are different. They're much easier to find than preimages. You basically take advantage of the birthday paradox to perform a birthday attack.

- Hash some input.
- Compare the hash with previously recorded hashes.
- If there's an equality, you found a collision! Otherwise, record the input/hash pair and try again.

Okay, I lied. If we did it like that, we'd have to remember every hash,
which would then take humongous amounts of memory. To avoid that, we can
use Pollard's *rho method*: repeatedly hash a value until you
spot a cycle (which you *will*, since the number of possible hashes is
finite). The point where you enter the cycle is where you'll find your
collision. *(Hence the name "rho": the path is like a straight line of
dots, ending in a loop.)* Let's try again:

- Chose a starting number
*x0*. - Compute
*x1 = Hash(x0)*,*x2 = Hash(x1)*, and so on. - Spot the cycle, and remember some
*xi*that is on that cycle. - Backtrack from the beginning, and find the point where you enter the cycle.

There are efficient ways to run this in parallel, with little memory. They're about as fast as a naive birthday attack, even if we ignore memory accesses. Overall, finding a collision on a 256-bit hash requires about 2¹²⁸ hash computations, and little else.

### Breaking elliptic curves (ECDLP)

To break an elliptic curve (that is, to solve the Discrete Logarithm Problem in the elliptic curve's cyclic group), you'd actually use the same methods as you'd use to break a hash.

Let's say you want to find the private key *k* of the public key *K*.
With elliptic curves, *K = [k]B*, where *B* is the base point of the
curve (a generator of the group). One way to do it is to find *a*, *b*,
*a'*, and *b'* such that: *[a]B + [b]K = [a']B + [b']K*, and
*b ≠ b'*. From there:

```
[a]B + [b]K = [a']B + [b']K
[a]B - [a']B = [b']K - [b]K
[a-a']B = [b'-b]K
[(a-a')/(b'-b)]B = [(b'-b)/(b'-b)]K = K = [k]B
[(a-a')/(b'-b)]B = [1]K
[(a-a')/(b'-b)]B = [k]B
(a-a')/(b'-b) = k
```

First though, we have to find that collision. One way to find it is to
define two random mappings *m* and *n* from curve points to scalars, and
use them to perform a random walk:

- Pick scalars
*a0*and*b0*. - Define
*P0 = [a0]B + [b0]B*. - Recursively define the walk with
*P(i+1) = [m(Pi)]B + n(Pi)K*. - Spot the cycle, where
*Pi = Pj*, for different*i*and*j*. - Backtrack from the beginning, and find the point where you enter the cycle.
- You now have found
*a = m(Pi)*,*b = n(Pi)*,*a' = m(Pj)*, and*b' = n(Pj)*, and the secret key*k = (a-a')/(b'-b)*.

The same optimisations used for hash collisions apply. In addition,
there are more efficient walks, that use point addition instead of full
blown scalar multiplications. When all known optimisations are applied,
breaking a curve of order 2²⁵⁶ requires about 2¹²⁸ point additions, just
like hashes. *(Or a large quantum computer. As of 2020, we have yet to
build one, so let's ignore the issue for now.)*

## "128 bits of security"

Depending on context, "128 bits of security" can mean:

- Finding a key requires about 2¹²⁸ cipher computations.
- Finding a hash preimage requires about 2¹²⁸ hash computations.
- Finding a hash collision requires about 2¹²⁸ hash computations.
- Finding a private key in a curve requires about 2¹²⁸ point additions.

Computing a cipher, a hash, or a point addition takes a comparable amount of work (like within an order of magnitude or so). The algorithms involved all have massively parallel versions, whose memory and time overhead is minimal. So at a first approximation, any of the above will require as much resources.

At first sight, "128 bits of security" does mean the same thing everywhere. But that's only so from a narrow point of view.

## Scaling down key search (and hash preimages)

In the context of ciphers, we're not just worried about an attacker
finding our key with reasonable certainty. We're often worried about an
attacker having *any* chance of finding *any* key.

For a key space of size *K*, searching *N* keys at once, while
tolerating *1/C* chances of success, means you need about *K/NC*
cipher computations. (Most ciphers target a security level equal to the
length of their keys. There are some exceptions, though.) Simply put:

- Chances of success scale down
*linearly*with cost. - Chances of finding one key scale up linearly with the number of keys
(as long as
*N*is much lower than*sqrt(K)*).

DJB gave an excellent example in Understanding Brute Force:

Consider again the standard parallel machine in Section2, with 2³² AES circuits. Recall that, after 2⁶⁴ AES computations [per circuit], this machine has chance close to 2⁻³² of finding a target key k1, and chance close to 2⁻²² of finding at least one of the 2¹⁰ target keys

Is this an acceptable level of security? Many people don't think so.

*(For reference, 2⁻²² is a little under 1 over 4 millions. Such odds are
better than many national lotteries.)*

Brute forcing hash preimages works basically the same: for a hash space
of size *H*, trying to find preimages of *N* hashes at once, while
tolerating *1/C* chances of success, means you need about *H/NC* hash
computations.

## Scaling down hash collisions (and ECDLP)

Hash collisions are much easier to find than specific preimages, because
of the birthday paradox. Achieving 128-bits of security requires a
256-bit hash. *The search space is much bigger than the complexity of
the best attack.* This kinda changes everything.

First, there's no such thing as a multi-hash attack when talking about
collisions. Finding *any* collision with reasonable certainty on a
256-bit hash is going to require approximately 2¹²⁸ hash computations.
*(In a sense, we could say that collision attacks are a degenerate case
of multi-hash second preimage attacks, where we're searching preimages
for every possible hash. This is as "multi-hash" as you'll ever get.)*

Second, reducing the cost have even more drastic effects on your chances
of success. Cutting down the search space in half divides your chances
by *four*. The drop off is now *quadratic* (the drop off for key search
was linear).

If we used that 2³² circuits standard parallel machine for 2⁶⁴ cycles, our chances of finding a collision in a 256-bit hash would only be 2⁻⁶⁴. Much less scary than the 2⁻²² chance of finding a 128-bit key, even though both ostensibly offer "128 bits of security".

As we've seen, breaking an elliptic curve is like finding a hash collision. Same structure, same optimisations, same chances. Like hash collision, no significant advantage can be gained by attacking several keys at once. Finding the first key among many will still require about 2¹²⁸ point additions (assuming a 256-bit curve).

## Conclusion

"128 bits of security" means something much stronger when it's about hash collisions and elliptic curves, compared to ciphers and hash preimages.

My conclusions as of 2020, are:

- We don't really need big curves like Curve448. Curve25519 is enough.
- We don't really need big 512-bit hashes like Blake2b-512 or SHA3. 256-bit hashes are enough.
- We
*do*need stronger ciphers than AES-128. At the very least, I would be uncomfortable using an 128-bit cipher if my threat model included a state level attacker. (When designing software for others to use, we generally assume three letter agencies might want a peek.) - We
*do*need hashes bigger than 128 bits, even if collisions don't matter. Think hard before you reduce the size of your Schnorr signatures.

*(Discuss on Reddit, Lobsters, or Hacker News)*