david wong

Hey! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

Breaking https' AES-GCM (or a part of it)

posted August 2016

The coolest talk of this year's Blackhat must have been the one of Sean Devlin and Hanno Böck. The talk summarized this early year's paper, in a very cool way: Sean walked on stage and announced that he didn't have his slides. He then said that it didn't matter because he had a good idea on how to retrieve them.

targeting mi5

He proceeded to open his browser and navigate to a malicious webpage. Some javascript there seemed to send various requests to a website in his place, until some MITM attacker found what they came for. The page refreshed and the address bar now whoed https://careers.mi5.gov.uk as well as a shiny green lock. But instead of the content we would have expected, the white title of their talk was blazing on a dark background.

mitmed mi5

What happened is that a MITM attacker tampered with the mi5's website page and injected the slides in a HTML format in there. They then went ahead and gave the whole presentation via the same mi5's webpage.

How it worked?

The idea is that repeating a nonce in AES-GCM is... BAD. Here's a diagram from Wikipedia. You can't see it, but the counter has a unique nonce prepended to it. It's supposed to change for every different message you're encrypting.

aes-gcm

AES-GCM is THE AEAD mode. We've been using it mostly because it's a nice all-in-one function that does encryption and authentication for you. So instead of shooting yourself in the foot trying to MAC then-and-or Encrypt, an AEAD mode does all of that for you securely. We're not too happy with it though, and we're looking for alternatives in the CAESAR's competition (there is also AES-SIV).

The presentation had an interesting slide on some opinions:

"Do not use GCM. Consider using one of the other authenticated 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 like to put it into Room 101." (Adam Langley, 2013)

"The fragility of AES-GCM authentication algorithm" (Shay Gueron, Vlad Krasnov, 2013)

"GCM is extremely fragile" (Kenny Paterson, 2015)

One of the bad thing is that if you ever repeat a nonce, and someone malicious sees it, that person will be able to recover the authentication key. It's the H in the AES-GCM diagram, and it is obtained by hashing the encryption key K. If you want to know how, check Antoine Joux' comment on AES-GCM.

Now, with this attack we lose integrity/authentication as soon as a nonce repeats. This means we can modify the ciphertext in the middle and no-one will realize it. But modifying the ciphertext doesn't mean we can modify the plaintext right? Wait for it...

Since AES-GCM is basically counter mode (CTR mode) with a GMac, the attacker can do the same kind of bitflip attacks he can do on CTR mode. This is pretty bad. In the context of TLS, you often (almost always) know what the website will send to a victim, and that's how you can modify the page with anything you want.

aes ctr

Look, this is CTR mode if you don't remember it. If you know the nonce and the plaintext, fundamentally the thing behaves like a stream cipher and you can XOR the keystream out of the ciphertext. After that, you can encrypt something else by XOR'ing the something else with the keystream :)

They found a pretty big number of vulnerable targets by just sending dozen of messages to the whole ipv4 space.

My thoughts

Now, here's how the TLS 1.2 specification describe the structure of the nonce + counter in AES-GCM: [salt (4) + nonce (8) + counter (4)].

The whole thing is a block size in AES (16 bytes) and the salt is a fixed part of 4 bytes derived from the key exchange happening during TLS' handshake. The only two purposes of the salt I could think of are:

Pick the reason you prefer.

Now if you picked the second reason, let's recap: the nonce is the part that should be different for every different message you encrypt. Some increment it like a counter, some others generate them at random. This is interesting to us because the birthday paradox tells us that we'll have more than 50% chance of seeing a nonce repeat after \(2^{32}\) messages. Isn't that pretty low?

Well done! You've reached the end of my post. Now you can leave me a comment :)

Someguy

Do you have a link for a video of the talk? I couldn't find. Appreciate the post!

David

It will be uploaded at some point. Usually if you can't wait you can buy the recordings after a couple months instead of waiting more to watch them on youtube

Karl Fritz

Great finding an talk. Wish I could have been there to see it. If I read this properly, the counter value to compute 'H' (counter(0) fed into Ek) is susceptible to not being truly random (due to incorrect usage). Therefore, the authentication key (K) could be derived (which, is also used for encryption as well).

So, in essence, would you say that this breaks forward secrecy as well? Or, just makes it less effective?

Ken

Thank you for the nice explanation. Stepping back to look at the big picture, as you noted, the largest threat contributor is the failure of an implementer to code correctly.

Address me as Pierre

This is not my typical area of focus, but I was not familiar with a lot of the terms used, such as 'nonce', and just about all the acronyms. This document would have broader appeal if the jargon were translated/defined/explained.

Just-in-case

I was marvelled....right from the start of this article to its end..

Was trying to imagine myself in the talk already...cos, it would have been more cool....seeing it real...thanks so much for this.

@Pierre...I also almost got myself lost...not until I searched for those jargon....I think I now know more. :) :) ;)

Leon

Video recording is available here: https://www.youtube.com/watch?v=2Ds427s_8k4