NONCE-DISRESPECTING
ADVERSARIESPRACTICAL FORGERY ATTACKS ON GCM IN
TLS
Hanno Böck, Aaron Zauner, Sean Devlin, Juraj Somorovsky,
Philipp Jovanovic
1

TLS ENCRYPTION
Step 1: Asymmetric key exchange (RSA, DHE, ECDHE) togenerate shared keys
Step 2: Symmetric encryption and authentication
Today we're interested in Step 2.

2

TLS SYMMETRIC MODES
CBC/HMAC
RC4 (stream cipher)
GCM(new: ChaCha20/Poly1305)

3

CBC/HMAC
Vaudenay Padding Oracle (2002), Vaudenay/Moeller(2003/2004), BEAST (2011), Lucky Thirteen (2013), POODLE(2014), POODLE-TLS (2014), more POODLEs (2015), LuckyMicroseconds (2015), Padding Oracle in OpenSSL / CVE2016-2107

4CBC/HMAC PROBLEMS
CBC/HMAC in TLS used an implicit IV in TLS 1.0.
The padding content in SSLv3 was undefined.
All TLS versions use MAC-then-Pad-then-Encrypt.
Encrypt-then-MAC extension, but it's rarely used.

5

TLS 1.2 PREDICTS LUCKY THIRTEEN
This leaves a small timing channel, since MAC performance
depends to some extent on the size of the data fragment, butit is not believed to be large enough to be exploitable, due tothe large block size of existing MACs and the small size of thetiming signal. (TLS 1.2, RFC 5246)

6

LUCKY THIRTEEN IS A BIG MESS
Amazon tried to implement countermeasures that didn'twork.
Some implementations (Go, TLS Lite) are known vulnerable
and don't want to fix it.
OpenSSL introduced another (worse) padding oracle while
fixing Lucky Thirteen.

7

RC4
A er Lucky Thirteen many sites switched to RC4.
Fluhrer/Shamir/Mantin (2001), attack on TLS by
AlFardan/Bernstein/Patterson (2013), Bar-MitzvaAttack/Mantin (2015), Garman/va der Merwe/Paterson(2015), Vanhoef/Piessens (2015).
RFC 7465: "Prohibiting RC4 Cipher Suites"

8

GCM
GCM - Galois/Counter Mode.
Usually used with AES.
Only available in TLS 1.2.
"This seems like a good moment to reiterate that everything
less than TLS 1.2 with an AEAD cipher suite is
cryptographically broken." (Adam Langley)

9

WHAT IS GCM?
GCM is an AEAD (Authenticated Encryption with AdditionalData)
Rationale: If you give people an encryption mode and anauthentication mechanism they will combine it in aninsecure way. So give them a standard that combines both.
GCM is a combination of Counter Mode and a GHASH
authentication tag.

10GCM - OPINIONS"Do not use GCM. Consider using one of the otherauthenticated encryption modes, such as CWC, OCB, or CCM."(Niels Ferguson)"We conclude that common implementations of GCM are
potentially vulnerable to authentication key recovery via
cache timing attacks." (Emilia Käsper, Peter Schwabe, 2009)"AES-GCM so easily leads to timing side-channels that I'd liketo put it into Room 101." (Adam Langley, 2013)"The fragility of AES-GCM authentication algorithm" (ShayGueron, Vlad Krasnov, 2013)"GCM is extremely fragile" (Kenny Paterson, 2015)

11

GCM
Everybody uses GCM, but nobody likes it.

12

"There's also an annoying niggle with AES-GCM in TLS
because the spec says that records have an eight byte, explicit
nonce. Being an AEAD, the nonce is required to be unique for agiven key. Since an eight-byte value is too small to pick atrandom with a suﬀiciently low collision probability, the onlysafe implementation is a counter. [...] Thankfully, all the major
implementations use a counter and I did a scan of the Alexa,
top 200K sites to check that none are using random values and none are." (Adam Langley)

13

NONCE
Number used once.
If you use the same Nonce twice (with the same key) it's nolonger a nonce.
TLS: 8 Byte / 64 Bit nonce

14

THE SPEC (RFC 5288 / TLS 1.2)
"Each value of the nonce_explicit MUST be distinct for eachdistinct invocation of the GCM encrypt function for any fixedkey. Failure to meet this uniqueness requirement cansignificantly degrade security. The nonce_explicit MAY be the64-bit sequence number."

15

INTERNET-WIDE SCAN RESULTS
184 hosts with repeating nonces
72445 hosts with random looking nonces

16

FINDING AFFECTED VENDORS
Certificate info, website content, HTTP "Server:" header.
O en load balancers hiding their true identity.
Contacting website owners hardly works.

17

IT LOOKS RANDOM, BUT ISN'T
Check Point devices using LFSR - this is secure.

18

DUPLICATE NONCES
We could identify two vendors
Radware (Cavium chip), update from vendorSeveral pages from VISA Europe (vendor not yet disclosed)

19

DEVICES WITH RANDOM NONCES
A10, IBM Lotus Domino (both published updates).
Sangfor (no vendor response).

20

MORE?
There are more devices with diﬀerent behaviors that wewere unable to identify.
Security test tools and pen testers should checks for this.

21

WHAT'S THIS? (RADWARE ANDOTHERS)
0100000003001741
0100000003001741
f118cd0fa6ff5a15
f118cd0fa6ff5a16
f118cd0fa6ff5a74

22

OPENSSL 1.0.1J
t1_enc.c:if (EVP_CIPHER_mode(c) == EVP_CIPH_GCM_MODE){
EVP_CipherInit_ex(dd,c,NULL,key,NULL,(which & SSL3_CC_WRITE))
EVP_CIPHER_CTX_ctrl(dd, EVP_CTRL_GCM_SET_IV_FIXED, k, iv);}

e_aes.c (EVP_CIPHER_CTX_ctrl/aes_gcm_ctrl):if (c->encrypt &&RAND_bytes(gctx->iv + arg, gctx->ivlen - arg) <= 0)
return 0;

23

THE FORBIDDEN ATTACK
Described by Joux during NIST GCM standardization (2006).
Nonce reuse allows an attacker to recover theauthentication key.
Attacker can modify messages with high precision.

24

GCM BACKGROUNDK: the encryption key: the authentication key derived by encrypting
the all-zero block under K
H = EK (0)N: the per-encryption nonce

25

GCM AUTHENTICATION
high level view:format the message as apolynomialmask with E (N )plug in H
K

26

GCM AUTHENTICATION
high level attacker's view:find a polynomial with H a root
factor the polynomial (this is easy!)
each root is a candidate for H (usually only afew!)

27

GCM AUTHENTICATIONFor concreteness, consider a message with no AAD and one
block of ciphertext.
2f (x) = C1 x+ Lx + EK (N )f (H) = T: 128-bit block encoding the messagelength
T : the output authentication tagL28

THE ATTACKER KNOWS ALGEBRA!
Subtract T:′2f (x) = C1 x+ Lx + EK (N ) − T′f (H) = 0

is a root of f , and we have eﬀicient algorithms forfinding roots of a polynomial!
H′Problem: we don't know f .
′29

NONCE REUSE
Suppose we have two messages encrypted under the samenonce:
2′f (x) = C1,1 x12′f (x) = C2,1 x
2+ L1 x + EK (N ) − T1+ L2 x + EK (N ) − T2′′

12g(x) = f (x) − f (x)2g(x) = (C1,1 − C2,1 )x+ (L1 − L2 )x − (T1 − T2 )30

NONCE REUSE
2g(x) = (C1,1 − C2,1 )x+ (L1 − L2 )x − (T1 − T2 )g(H) = 0

is fully known to the attacker: we can factor it to recover
H.
g

31

A MITM ATTACK ON TLS
1. User visits
http://attacker.com.

32

A MITM ATTACK ON TLS1. User visits http://attacker.com.
2. Attacker serves JavaScript to poll https://noncerepeater.com.

33

A MITM ATTACK ON TLS
1. User visits http://attacker.com.
2. Attacker serves JavaScript to poll https://noncerepeater.com.
3. Attacker collects responses indexed by nonce.

34

A MITM ATTACK ON TLS
1. User visits http://attacker.com.
2. Attacker serves JavaScript to poll https://noncerepeater.com.
3. Attacker collects responses indexed by nonce.
4. When the server repeats a nonce, attacker executes Joux's
attack to recover the authentication key.

35

A MITM ATTACK ON TLS
1. User visits http://attacker.com.
2. Attacker serves JavaScript to poll https://noncerepeater.com.
3. Attacker collects responses indexed by nonce.
4. When the server repeats a nonce, attacker executes Joux's
attack to recover the authentication key.
5. Attacker redirects user to a known resource, e.g.
https://nonce-repeated.com/index.html.
36

A MITM ATTACK ON TLS
1. User visits http://attacker.com.
2. Attacker serves JavaScript to poll https://noncerepeater.com.
3. Attacker collects responses indexed by nonce.
4. When the server repeats a nonce, attacker executes Joux's
attack to recover the authentication key.
5. Attacker redirects user to a known resource, e.g.
https://nonce-repeated.com/index.html.
6. Attacker replaces the ciphertext C in the server responsewith (C XOR index.html XOR malicious.html) and updates
the tag.

37

A MITM ATTACK ON TLS

38

FUTUREDra for Chacha20/Poly1305 and TLS 1.3 uses fully implicit
nonce based on record number.
Synthetic IVs and nonce misuse resistant schemes.

39CONCLUSION
TLS 1.2 tells implementors to use a nonce, but gives noguidance how to do that properly.
Some people get it wrong.
We need better test tools for TLS implementation flaws (TLSFuzzer looks promising).

40

THANKS FOR LISTENING
https://github.com/nonce-disrespect/nonce-disrespect
Test your hosts:
https://gcm.tlsfun.de/

41