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)*