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.

Transport Layer Security (TLS) 1.3 is almost here. The protocol that protects most of the Internet secure connections is getting the biggest ever revamp, and is losing a round-trip. We will explore differences between TLS 1.3 and previous versions in detail, focusing on the security improvements of the new protocol as well as some of the challenges we face around securely implementing new features such as 0-RTT resumption. At Cloudflare we will be the first to deploy TLS 1.3 on a wide scale, and we’ll be able to discuss the insights we gained while implementing and deploying this protocol.

Version 1.3 is the latest Transport Layer Security (TLS) protocol, which allows client/server applications to communicate over the Internet in a way that is designed to prevent eavesdropping, tampering, and message forgery. TLS is the S in HTTPS. A lot has changed between 1.2 (2008) and 1.3. At the a high level, 1.3 saves a round-trip, making most connections much faster to establish. We'll see how the 1.2 handshake worked, and what had to change to enable 1-RTT handshakes. But even more importantly, the 1.3 design shifted towards putting robustness first. Anything that is not strictly necessary to the main function of TLS was removed (compression, renegotiation); choices of suboptimal security aren't offered at all (static RSA, CBC, RC4, SHA1, MD5); secure, easy to implement designs are introduced or privileged (RSA-PSS, AEAD implicit nonces, full handshake signatures, Curve25519, resumption forward secrecy). We will go into the why and how of all of these. But two major trade-offs had to be made: first, 1-RTT handshakes inherently prevent the introduction of encrypted domain names (SNI). We'll see why and what can replace them to provide similar privacy. Most interestingly, 1.3 comes with 0-RTT resumption. The catch there is that the protocol itself provides no complete protection against replay attacks. We'll unpack the problem, see what mitigations are available, what the risks and attacks are and how that requires careful API design and deployment. Finally, deployment hasn't been entirely smooth. Many servers out there turned out to be intolerant to 1.3 clients. We'll see what this causes, how it was worked around, and how downgrade protection provides defense in depth. TLS 1.3 is not in the distant future. The draft is almost finalized, and at Cloudflare we developed an open source stack in Go and support the protocol in beta for all websites. Chrome Canary and Firefox Nightly implement 1.3 clients.

Other people: Nick Sullivan

Entropy, the randomness used in many critical cryptography processes including key generation, is as important as it is misunderstood. Many myths are fueled by misleading documentation. This presentation aims to provide simple and actionable information while explaining the core technical details and real world implementations.

Randomness is as simple as critical. An application wants some bytes which an attacker can't predict. The clearest example is generating a cryptographic key, but a wide array of functions depend on randomness. Any time a key is generated, any time a DSA signature is made, any time the memory layout is randomized, applications rely on being able to create strings of bytes impossible to predict. If that comes short everything fails: cryptographic keys are compromised, exploits protections are ineffective. Entropy, the unpredictable raw material, is usually collected by the Operating System and exposed to the applications that need it. Once enough bits of entropy have been collected, it becomes impossible to predict the output of the CSPRNG (cryptographically secure pseudo-random number generator), a stirrer of sorts that expands a seed into unlimited whitened random bytes, often based on stream ciphers or hashes. Real risks include trying to use a CSPRNG early on in the boot process, when not enough random events have been collected, or using a userspace CSPRNG instead of the kernel one and forgetting to seed it. Or using a non-CS PRNG. That's just about it. However, there is a lot of misunderstanding on "decreasing entropy". It's a widespread myth that using random bytes decreases the "amount" of entropy. Reality is, to an attacker who's basically trying to predict the CSPRNG output there's no decrease in difficulty no matter how much output is drawn, so developers can avoid introducing additional complexity because of this. This is all backed up by showing a simple toy CSPRNG design, and reasoning about its properties. More practically, the points above translate into "in Linux, just use /dev/urandom or the get_random syscall". That's the kernel interface for the system CSPRNG. Its inner working are presented and they will hopefully make it clear why there is no meaningful difference from the "counting" /dev/random.