Session
Fahrplan 34C3
Security

Squeezing a key through a carry bit

No bug is small enough
Saal Dijkstra
Filippo Valsorda
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.

Carry bugs are fairly common, and usually too small to have big impact, or so they are considered. This one was no exception.

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. Elliptic Curve Diffie-Hellman involves a secret scalar, a peer-provided point, and fails to establish a key if the result is incorrect.

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.

The precomputation involves a lot of unusable points and edge cases, but by modifying the optimized assembly implementation and generating points intelligently, we can produce a full round of points in seconds on 1000 machines (or spot instances). Each round depends on the previous ones, so must be computed live during each attack.

Normal ECDH does not offer an attacker multiple attempts against the same scalar, making the attack impossible. However, a variant of ECDH with a static scalar is used as a public key encryption scheme, for example in JSON Web Encryption. The attack can fully recover the private key in that scenario.

No bug is small enough.

Additional information

Type lecture
Language English

More sessions

12/27/17
Security
oranav
Saal Dijkstra
How I hacked Sasmung eMMC chips: from an indication that they have a firmware - up until code execution ability on the chip itself, relevant to a countless number of devices. It all started when Samsung Galaxy S3 devices started dying due to a bug in their eMMC firmware. I will cover how I figured out there's a firmware inside the chip, how I obtained it, and my journey to gaining code execution on the chip itself — up until the point in which I could grab a bricked Galaxy S3, and fix it ...
12/27/17
Security
Mathias Dalheimer
Saal Adams
Wir retten das Klima mit Elektroautos — und bauen die Ladeinfrastruktur massiv aus. Leider werden dabei auch Schwachstellen auf allen Ebenen sichtbar: Von fehlender Manipulationssicherheit der Ladesäulen bis hin zu inhärent unsicheren Zahlungsprotokollen und kopierbaren Zahlkarten. Ladesäulenhersteller und Ladenetzbetreiber lassen ihre Kunden im Regen stehen — geht das schnelle Wachstum des Marktanteils zu Lasten der Kundensicherheit?
12/27/17
Security
Artem Kondratenko
Saal Clarke
Year 2017 was rich in vulnerabilities discovered for Cisco networking devices. At least 3 vulnerabilities leading to a remote code execution were disclosed. This talk will give an insight on exploit development process for Cisco IOS for two of the mentioned critical vulnerabilities. Both lead to a full takeover of the target device. Both PowerPC and MIPS architectures will be covered. The presentation will feature an SNMP server exploitation demo.
12/27/17
Security
Saal Borg
Positive Technologies researchers Maxim Goryachy and Mark Ermolov have discovered a vulnerability that allows running unsigned code. The vulnerability can be used to activate JTAG debugging for the Intel Management Engine processor core. When combined with DCI, this allows debugging ME via USB.
12/27/17
Security
argp
Saal Clarke
This talk presents the technical details and the process of reverse engineering and re-implementation of the evasi0n7 jailbreak's main kernel exploit. This work was done in late 2013, early 2014 (hence the "archaeology" in the title), however, it will provide insight into the kernel debugging setup for iOS devices (iDevices), the encountered difficulties and how they were overcome, all of which can be useful for current iOS kernel vulnerability research.
12/27/17
Security
Saal Dijkstra
Do you want to learn how modern binary code obfuscation and deobfuscation works? Did you ever encounter road-blocks where well-known deobfuscation techniques do not work? Do you want to see a novel deobfuscation method that learns the code's behavior without analyzing the code itself? Then come to our talk and we give you a step-by-step guide.
12/27/17
Security
Sebastian Eschweiler
Saal Borg
In this presentation we will outline our findings about (Not)Petya's crypto flaws and how we were able to exploit them to decrypt infected computers.