You could have invented that Bluetooth attack | Hacker News Reader

You could have invented that Bluetooth attack

blog.trailofbits.com

94 pointsoctosphere17 comments

"You could have invented that Bluetooth attack"

Proceeds to explain elliptic curve mechanics that would make most readers completely glaze over.

Maybe they mean they just mean their normal reader base, who has an attention span for those sorts of details? Their assertion that an average reader could understand the attack might be true, but the "could have invented" is a a bit far fetched.

I think the argument is something like: you could understand what invalid curve point attacks are, and once you did, you could look for them everywhere, and if you did that, you would have found this error as well.

The math behind invalid curve point attacks is pretty straightforward, it's some polynomials and points on the Cartesian plane. You saw this stuff in elementary school.

Then, someone needs to point out to you "oh check out what happens if you allow for invalid points" and now you have a pattern to go hunting for. Then it's luck - do you get to Bluetooth before someone else, or do you find something else, or do you just re-discover other peoples stuff?

Maybe it's elitist to say "the math is pretty straightforward" but you know what, it's a system of two variables and you can plot it. You need to know about division, multiplication, and modular variants. No monads, no tensors, no mixed Gaussians or method of moments or greek letters or 128 dimensional spheroids.

Maybe that kind of math makes your eyes glaze over but I am pretty confident that if you cleared your mind and sat down with pencil and paper and gave it an hours honest effort, you would come away with an understanding.

You definitely didn't do the math for invalid curve attacks in grade school, since you also need CRT and the notion of group order. But I think your first sentence gives a great charitable interpretation of the title.

A way I like to think about these things --- from the perspective of a vulnerability researcher, not a cryptographer or mathematician (I am neither of those) --- is that there is a very little bit of math you need to put some extra tools in your belt, and then the rest of it is programming; working through these kinds of exploits feels a lot like implementing heapsort or a spanning tree reduction for the first time feels like. I find that empowering, because while I can't bang out Kruskal's algorithm off the top of my head, I know if I sit down with it for 20-30 minutes I'll get it working. After a little bit of reading (an hour or two tops), same with this attack.

Where did you go to elementary school?

Look, some attacks are just going over the RFC, finding each MUST in the text (or MUST NOT or a SHOULD that really should have been a MUST, etc.), understanding that this "MUST" means (usually) a requirement for the presence of an "if" statement in the code [1], and then looking for that if statement in the code.

If it is possible to interoperate with real world endpoints (basically Apache on openssl 1.0.2 and IIS on SChannel on latest Windows for servers, Chrome and MSIE as clients) with a codebase that lacks that if statement, someone has deployed in production a codebase that lacks this if statement. So unless someone already found it (that someone is probably Hanno Böck), you're going to be the first to find it.

Now you can look for protocols that use the same construction as other protocols but did not copy-paste the MUST sentence. If the spec forgot to say the MUST sentence, you're going to find many more implementations that lack the corresponding if statement.

1 - instead of an if statement, sometimes it means "fill this buffer by reading X bytes from /dev/urandom" but the code just does memset with 0.

For reference, here is the part of the blog where the attack is explained:

> 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 the point at infinity, 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.

tl;dr replace a thing with 0 and watch a cluster of screwups happen. You can probably learn a very limited amount of cryptography or math and, simply knowing that this behavior exists, find invalid curve point vulnerabilities in deployed cryptographic code.

Here's Sean Devlin explaining ~85% of the same detail in a general introduction to invalid curve attacks:

https://toadstyle.org/cryptopals/59.txt

I like Sean's definitions best and find them the most accessible way to get a the topic. Don't think about curves as geometric objects and don't think of points as coordinates. Think of the curve as an equation y^2 = x^3 + ax + b --- come on, you did this in high school --- and a point as an x,y pair that satisfies the equation (pick an x at random! solve for y!). Now host that equation in a finite field, so the x and y needs to be an integer mod p. You can code this in Python or Ruby, right now, and get an intuition for the basics of how it works.

For invalid curve intuition, I also think Sean is right: understand DH and subgroup confinement first:

https://toadstyle.org/cryptopals/57.txt

I think the fundamental thing to get your head around even if you're not going to take the hour or two to code the attack up (do that, though! it's a fun couple hours!) is to notice that, if for prime p a curve has order q < p points, most combinations of integers mod p can't be valid points. If you've got a "sage" prompt lying around (always have a sage prompt lying around), make a curve E = EllipticCurve(GF(17), [3,4]). Look at the length of E.points(), and notice how much smaller it is than the number of possible x's and y's.

Then, the interesting part about the attack is that if you send an x,y pair that doesn't satisfy the curve, it might satisfy the equation for some other curve. If you're smart you pick a point that lands in a curve that's insecure, for which you can quickly use brute force to solve the DLP.

I agree that the hook in this blog post title is misleading; you would not have found this attack. But it's misleading in a sort of empowering way: you are not a graduate course in mathematics from grasping the intuition of the attack or coding a model exploit. You might not even be a day away from it.

If you read this blog post and Sean's posts and you're stuck on something, I'd be interested in knowing what and seeing if I can push you through it.

This title is pretty clickbait-y, as I would most likely not have invented it. You really have to know the internals and this doesnt even apply _only_ on Bluetooth but DH implementations in general...

> This title is pretty clickbait-y, as I would most likely not have invented it.

The title is slightly tongue in cheek; it's as much a genre as "considered harmful": https://www.google.com/search?q=%22you%20could%20have%20inve... .

Can anyone explain how figure 1 is y^2=x^3-x? I feel like I'm going crazy.

I agree. I just tried substituting in a bunch of those points and none solved that equation. I don't see, for example, how the point at (12,56) fits that equation at all, since it computes to 56^2 = 12^3 - 12, or 3136 = 1728 - 12, or 3136 = 1716. That isn't even remotely close, so it's not me just slightly misreading the points.

The author omitted the mod n, where n = 71 in this case. So 3136 mod 71 = 1716 mod 71 = 12.

Oh of course! Thank you, that makes a lot more sense.

If I understand correctly, the Bluetooth exploit also requires a man-in-the-middle attack during pairing. Wouldn't the victim then see two Bluetooth devices with the same name during pairing ? Also most Operating Systems then order the list of devices by signal strength. Without physical access to the victims home/office/etc., it would be hard for the attacker to have a higher signal strength since most users would be pairing to a device in close proximity. In a public place this could be easier, but even then it would probably fail more often then it would work.

This is really poorly written. It's a perfect example of the common problem of bad teachers in tech. Many engineers think they're good at teaching topics, or try to aggressively teach others, but are only capable of explaining topics to people who already fully understand them.

To be fair - that blog post has perhaps lost some context being posted up to an unintended audience.

Their headline on their website reads:

"Deepening the Science of Security Since 2012, Trail of Bits has helped secure some of the world’s most targeted organizations and products. We combine high-end security research with a real-world attacker mentality to reduce risk and fortify code."

One would expect the target to whom they write their blog posts has some assumed understanding of "the science of security", and they are looking for articles which "deepen" understanding rather than explain it all from an ELI5 or completely non-understanding perspective.

(But you're right about a typically bad level of teaching and documentation in tech. I still remember struggling ~25 years ago with Perl docs which explain this using phrases like "This work just the same way as in awk"... Often things are not much better these days.)

I have first hand experience with such engineers, but I doubt this is unique to engineering.

Breaking down complex concepts from your expertise to an industry outsider can be a difficult skill. Especially if you're not aware of the level of understanding of your audience.

Reply on news.ycombinator.com