BlueZero: A Major (and Sloppy) Bluetooth Vulnerability … Patch Now!
BlueZero: A Major (and Sloppy) Bluetooth Vulnerability … Patch Now!
Introduction
In the past, wireless security has been compromised by poor standards and weak implementations. WEP, for example, broke almost every rule in the security book [here], and where it could be cracked within hours, and cracked for the whole network. But it is now Bluetooth which is showing some poor implementation standards due to an attack on its core key exchange method: ECDH (Elliptic Curve Diffie Hellman).
The discloser was published by an Israeli team here, and implements a man in the middle (MITM) attack, with a 50% chance of success. On a successful pairing, the researchers were able to compromise data transfers and even forge keystrokes.
The attack gives us a great chance to learn a bit about key exchange and elliptic curve methods, so I’ll try and cover some of the basics, so that you get a better idea of the problem (and hopefully not fall into the same trap).
Every great vulnerability deserves a great name — Poodle, BEAST, Heartbleed, FREAK, Wanna Cry, and so on, so I’m going to name it BlueZero, as it is all about Bluetooth and the zero-ing of the parameters involved in the key exchange in the pairing process.
Some basics
The weakness relates to the implementation of the elliptic curve method for key exchange involved in the pairing process between two devices, and where the two devices involved in the pairing can be forced to generate a predictable shared key.
As background, here is an outline of ECDH [here]:
In the basic ECDH key exchange method, Bob and Alice generate their random private key values (dA and dB), and then calculate an associated public key (QA and QB). These take an agreed point on the elliptic curve (G) and multiply the private key values — which are scalars — to give the public keys — this will be a point on the agreed elliptic curve. This will then be an x- and a y-coordinate on the curve. Next the swap their public keys and then multiply their secret key, and end up with the same shared key point. Normally we then just take the x-coordinate as the shared value (and create a key from this):
Some simple code to implement the ECDH method is:
from elliptic import *
from finitefield.finitefield import FiniteField
import os
def generateSecretKey(numBits):
return int(os.urandom(numBits // 8).encode('hex'), 16)
F = FiniteField(3851, 1)
curve = EllipticCurve(a=F(324), b=F(1287))
#curve = EllipticCurve(a=486662, b=1)
basePoint = Point(curve, F(920), F(303))
print "Basepoint:\t",basePoint
aliceSecretKey = generateSecretKey(16)
bobSecretKey = generateSecretKey(16)
print "Alice\'s secret key:\t", aliceSecretKey
print "Bob\'s secret key:\t", bobSecretKey
print "=========================="
alicePublicKey = aliceSecretKey*basePoint
bobPublicKey = bobSecretKey*basePoint
print "Alice's public key:\t",alicePublicKey
print "Bob's public key:\t",bobPublicKey
sharedSecret1 = bobSecretKey*alicePublicKey
sharedSecret2 = aliceSecretKey*bobPublicKey
print "=========================="
print "Alice\'s shared key:\t",sharedSecret1
print "Bob\'s shared key:\t",sharedSecret2
print "=========================="
print "The shared value is the x-value:\t", (sharedSecret1.x.n)
A simple sample run with a prime number of 3,851 and two random values of 53,249 (from Alice) and 40,519 (from Bob), with a base point of (920,3030) gives a share of 2,530 (and where we just take the value of the x-coordinate for the share) [here]:
Basepoint: (920 (mod 3851), 303 (mod 3851))
Alice's secret key: 53249
Bob's secret key: 40519
==========================
Alice's public key: (3776 (mod 3851), 2797 (mod 3851))
Bob's public key: (2291 (mod 3851), 750 (mod 3851))
==========================
Alice's shared key: (2530 (mod 3851), 2232 (mod 3851))
Bob's shared key: (2530 (mod 3851), 2232 (mod 3851))
==========================
The shared value is the x-value: 2530
The attack
The MITM attack has been well-known in the Diffie-Hellman (DH) method, and where Eve can sit in-between Bob and Alice and change their values, and thus create keys which are known to her. She uses one key for Bob and another for Alice. In diagram below, Eve generates a random value of c, and is able to generate key two keys — one for Bob and one for Alice. She will then encrypt and decrypt to and from Alice with Key₁ (A^c mod P) and encrypt and decrypt traffic to and from Bob with Key₂ (B^c mod P):
In ECDH, though, we pass public key points (x,y), and where Eve could change both the x- and y-value of the points passed, and again could generate two shared keys. To protect against this, Bluetooth has built-in protection to verify the x co-ordinate of the public key points. But the designers did not check the validity of the y-coordinate values. The researchers were then able to reset the y-coordinates to zero and generate a known key:
Now that we have reset the y-coordinate of each public key passed to zero, we will now not be able to hit the point on the elliptic curve, as it is an invalid point, and the gradient will now point to an incorrect place. If we do this in our code:
alicePublicKey = aliceSecretKey*basePoint
bobPublicKey = bobSecretKey*basePoint
alicePublicKey=Point(curve,alicePublicKey.x,0)
bobPublicKey=Point(curve,bobPublicKey.x,0)
When working correctly the code should generate an exception when we create a shared value:
Exception: The point (1213 (mod 3851), 0) is not on the given curve y^2 = x^3 + 324x + 1287!
But the Bluetooth stack has a bug, and half of the time it creates an exception, but the other half of the time it will create a fairly predictable point. The intruder — Eve — just has to create a table of values and can generate the same shared key. As we have placed the point off the curve, the resultant point may shoot off into infinite, and never end up as a point on the curve. If the secret keys are even, there will be a valid point on the curve, and the key will succeed. If any of them are odd, it will fail as the point will be at infinite. Our chances of success with this passive attack is then 1-in-4 (and where both values are even). The researchers then applied an improved method, and achieved a success rate of 50% with an active attack.
The researchers define:
We would like to point out two major design flaws that make our attack possible. The first design flaw is sending both the x-coordinate and the y-coordinate during the public key exchange. This is unnecessary and highly inadvisable, since it greatly increases the attack surface, while calculating the y-coordinate from a given x-coordinate is simple.
for the second attack:
The second major flaw is that although both coordinates of the public keys are sent during the second phase of the pairing, the protocol authenticates only the x-coordinate. We are not aware of any reason why the designers decided to leave the y-coordinate unauthenticated, other than for saving a tiny computational effort. Even though the point validity should be checked by the implementation, our attack could have also been avoided if both coordinates were authenticated.
The researchers thus highlight that there is no need to send the y-coordinate value, but if it is, the returning value should be checked against the curve.
Conclusions
The attack is about as simple as it gets, and the writers of the specification should be pin-pointed for their slopping implement. All devices will be vulnerable to this, as the method is built into the stack. You should patch your devices as soon as possible.
Overall the research team had success rates of 25% and 50% for their methods. As Bluetooth is a fairly robust protocol, it will retry the connection several times, so the chance of succeeding in cracking a device is actually high.
There are now patches for several operating systems, including for Mac OSX, Android, and iOS, and only one of the devices involved needs to be patched, for the connection to be secured.