Squeezing a Key through a Carry Bit

The presentation discusses a successful attack on elliptic curve cryptography using kangaroo algorithms and parallel computing.

• The attack targets a JWT receiving application using ECDH algorithm
• The attack uses kangaroo algorithms and parallel computing to find the private key
• The attack is cost-effective and can be done using spot instances on EC2
• The presentation includes a demonstration of the attack and a UI showing the progress of the attack

The presenter mentions that the cost of the attack was initially miscalculated and was relieved to find out that it only cost around $60 instead of $1000. They also mention that they are not brave enough to run the attack live due to trust issues with the infrastructure.

The Go implementation of the P-256 elliptic curve had a small bug due to a misplaced carry bit affecting less than 0.00000003% of field subtraction operations. We show how to build a full practical key recovery attack on top of it, capable of targeting JSON Web Encryption.Go issue #20040 affected the optimized x86_64 assembly implementation of scalar multiplication on the NIST P-256 elliptic curve in the standard library.p256SubInternal computes x - y mod p. In order to be constant time it has to do both the math for x >= y and for x < y, it then chooses the result based on the carry bit of x - y. The old code chose wrong (CMOVQNE vs CMOVQEQ), but most of the times compensated by adding a carry bit that didn't belong in there (ADCQ vs ANDQ). Except when it didn't, once in a billion times (when x - y < 2^256 - p). The whole patch is 5 lines.The bug was found by a Cloudflare engineer because it caused ECDSA verifications to fail erroneously but the security impact was initially unclear. We devised an adaptive bug attack that can recover a scalar input to ScalarMult by submitting attacker-controlled points and checking if the result is correct, which is possible in ECDH-ES.We reported this to the Go team, Go 1.7.6 and 1.8.2 were issued and the vulnerability was assigned CVE-2017-8932.At a high level, this P-256 ScalarMult implementation processes the scalar in blocks of 5 bits. We can precompute points that trigger the bug for each specific 5 bit value, and submit them. When the protocol fails, we learned 5 key bits, and we move on to the next 5, Hollywood style. In about 500 submissions on average we recover the whole key.