You could have invented that bluetooth attack

A serious bluetooth bug has received quite a bit of attention lately. It’s a great find by Biham and Newman. Given BLE’s popularity in the patch-averse IoT world, the bug has serious implications. And yet, it’s remarkably clean and simple. Unlike many elliptic curve bugs, an average human can totally understand the bug and how it can be exploited. It’s a cool application of a conceptually approachable attack.

This post describes the bug, how to exploit them, and how that specifically happened with the bluetooth protocol. But first, let’s take a crash course in elliptic curves and invalid curve point attacks.

What is an elliptic curve?

It’s quite a misnomer. In cryptography, an “elliptic curve” is neither elliptical nor a continuous curve. Instead, it’s a collection of (x, y) coordinates where x and y are between 0 and n, such that y\exp{2} = x\exp{3} + ax + b mod n, plus a bonus “point at infinity,” which counterintuitively behaves much like zero; if you add it to anything, you get the same number back. Fig. 1 shows such a curve, where y2 = x3 - x, and x and y range from 0 to 71. (Technically, x and y are defined over a finite field, but all finite fields of the same order are isomorphic, so our definition is equivalent).

Fig. 1: An elliptic curve (as used in cryptography)

Elliptic curves have a few useful properties:

  • You can add elliptic curve points to one another with rules that look a lot like regular addition: x + y = y + x, x + (y + z) = (x + y) + z, etc. This is because points on the curve form an Abelian group. You can see a visualization of this addition in fig. 2, below.
  • A point can be multiplied by some natural number (call it n) by adding it to itself n times.
  • For each point (x, y), there’s an inverse, (x, -y) such that any point plus its inverse is the point at infinity.
  • Most notably, if you pick a, b, and n in the equation above well, multiplying by a regular number is a trapdoor function: given a point P and a number n, computing a point Q such that Q = n * P is very easy, but given a point P and a point Q, finding n such that Q = n * P is extremely hard. This simple hardness assumption lets us construct hosts of cryptographic algorithms.

Fig. 2: Addition, and the point at infinity (note: these illustrations use a continuous curve for visualization, but that’s still not what we’re working with)

Usually, elliptic curve algorithms are written around a specific curve. Parties exchange points on the curve and scalars, and do computations like we’ve defined above using them. However, problems arise when these algorithms are exposed to (x, y) pairs that don’t satisfy the curve equation, and these can be exploited to perform what’s called an “invalid curve point attack.”

What is an invalid curve point attack?

Remember, a point is a pair (x, y) such that y2 = x3 + ax + b mod n for some a, b, and n. However, if that equation doesn’t hold, (x,y) is an invalid curve point. Quite a few cryptographic algorithms ask a user to provide a curve point and, by design, assume the point is valid and the equation holds. Failing to verify that received curve points are on the curve before doing math with them isn’t too far from violating the cryptographic doom principle and has similar consequences.

In elliptic curve schemes, the secret is usually a regular number (remember, finding n such that Q = n * P is the hard problem). When an attacker can send an unvalidated point that’s multiplied by n and see the results, they can exploit that lack of validation to learn the secret key. Frequently, attackers can pick points that belong to a different curve than the algorithm specifies, one with very few points on it.

For instance, an attacker might pick a point not on the curve with a y coordinate of zero. Any point like this must be on some curve with only two elements! We know this because we calculate inverses by multiplying the y coordinate by negative one, but zero times negative one is zero, and so any point with a y coordinate of zero is its own inverse. Thus when we add it to itself, the only other point we can get is the point at infinity.

If the attacker picks a point like this, then by viewing the secret multiplied by some point on that curve, they learn whether the secret is even or odd! The input point was one of the two possible points. Adding it to itself will get the other point. Thus, if the secret is the point entered, the number is odd; otherwise, it’s even. We can submit similar points in elliptic curves of three elements to learn the secret mod 3, in curves of five elements to learn the secret mod 5, and so on until we can just use the Chinese Remainder Theorem to compute the actual secret.

This isn’t the only way to use invalid curve points to find out a secret key, but it’s perhaps the easiest to understand, and has been used in real life to break TLS libraries from Oracle and Google.

While the recent attack on Bluetooth wasn’t quite as simple as the above example, it was conceptually very similar, and used the same technique of small subgroup confinement to achieve key disclosure.

How did the Bluetooth attack work?

The Bluetooth protocol uses elliptic curve Diffie-Hellman to agree on a shared secret key for encryption. Using Diffie-Hellman algorithms correctly is super hard. Subtle mistakes can compromise the security of your entire system. In this case, the protocol did in fact require curve point validation, but only for the x coordinate. This is an innocent-enough looking mistake to go unnoticed for a decade. And it lets a smart attacker break the whole system.

Elliptic curve Diffie-Hellman is a simple algorithm. Suppose Alice and Bob want to agree upon some secret. Both parties have a secret number, and there’s a commonly agreed-upon “base point” on some elliptic curve.

Alice sends Bob the base point multiplied by her secret number, and Bob sends Alice the base point multiplied by his. Then, Alice multiplies Bob’s message by her secret number, and Bob multiplies Alice’s message by his secret number. If we call the point P and the secrets a and b, Alice sends Bob P * a, Bob sends Alice P * b. Alice then calculates (P * b) * a (the shared secret) and Bob calculates (P * a) * b (the same number.)

Even if an attacker, Chuck, can see either message, he can’t deduce a or b, and he can’t combine P * a and P * b to get the secret, so he’s totally out of luck! However, problems arise when Chuck can modify messages instead of just viewing them. Since the y coordinate isn’t valid, Chuck can modify it to always be zero.

Remember, if a point has a y coordinate of zero, it must be on a curve with exactly two elements: itself and the point at infinity. If you multiply it by a random number, it has a 50% chance of being either element, and no chance of being anything else.

Putting this all together, if Chuck replaces one of the points Alice and Bob send each other, (x, y), with (x, 0), then Alice or Bob multiplies it by their secret key, there’s a 50% chance they get the point at infinity and a 50% chance they get (x, 0). If Chuck replaces both intermediate messages, there’s a 25% chance that Alice and Bob agree the secret key is zero, and no chance they agree on any other key. This means either ECDH fails and Alice and Bob have to retry (giving Chuck another chance), or Chuck knows the secret key and can read and insert messages.

How can you avoid bugs like this?

The most important takeaway from all of this isn’t anything about this particular attack; it’s that this whole class of attacks is totally preventable. A few more concrete pieces of advice:

  • Diffie-Hellman is an unusually dangerous algorithm to implement. You almost certainly don’t want to be using it in the first place (ref. Latacora’s excellent cryptographic right answers). If you find someone using it, you have a good chance of finding bugs. Seriously, almost no one needs this, and it’s extraordinarily hard to do right.
  • Use X25519 for ECDH or Ed25519 for ECDSA. On those curves any 32-byte string is a valid curve point; invalid curve points are thus impossible.
  • If your input can be invalid and you’re performing cryptographic operations with it, do the validation before anything else.

I’ve deliberately left out instructions for validating points yourself, since that’s far too subtle a topic for the conclusion of a blog post. If you’re interested in that sort of thing, you could do worse than this paper. If you’d like to practice exploiting these kind of bugs (and some way cooler ones) you should check out Cryptopals set 8. If this is the kind of thing you do for fun already, get in touch. We’d love to work with you.



*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored by JP Smith. Read the original post at: https://blog.trailofbits.com/2018/08/01/bluetooth-invalid-curve-points/