Squeezing a Key through a Carry Bit

Presented at Black Hat USA 2018, Aug. 8, 2018, 4 p.m. (50 minutes)

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.<br><br>Go issue #20040 affected the optimized x86_64 assembly implementation of scalar multiplication on the NIST P-256 elliptic curve in the standard library.<br><br>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.<br><br>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.<br><br>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.<br><br>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.<br>

Presenters:

• Filippo Valsorda - Cryptogopher, Google
  Filippo Valsorda (@FiloSottile) is a cryptography engineer building and breaking systems in Go. He works at Google on the Go Open Source Project, where he owns the Go cryptography standard libraries. Previously at Cloudflare, he developed its experimental TLS 1.3 stack and kicked DNSSEC until it became something deployable. Nevertheless, he's probably best known for making popular online vulnerability tests, including the original Heartbleed test.

Links:

• https://www.blackhat.com/us-18/briefings/schedule/#squeezing-a-key-through-a-carry-bit-11773
• https://infocon.org/cons/Black Hat/Black Hat USA/Black Hat USA 2018/Squeezing a Key through a Carry Bit.mp4
• https://www.youtube.com/watch?v=zPj5tTFDql0

Similar Presentations:

• Still Hacking Anyway (SHA2017) / Hormones and Hysteria - what every person should know: are you not curious now? ;)
• Black Hat Asia 2021 Virtual / Threat Hunting in Active Directory Environment
• Still Hacking Anyway (SHA2017) / Parkour communications: How you can communicate, free running style, using nothing but the 'fixtures' of the Internet.