Attacking AES GCM with 16 byte IV?


#1

Hi,

Just looking for some advice from the experts…

Cutting to the chase - Is it possible at all to break AES-128 decryption in GCM mode with a 16 byte IV? (but not knowing the IV) If so, what strategy should I use? Have you done it in the past?

As I understand it, when using a 16-byte IV, AES-128 GCM will encrypt the IV and increment it in each iteration, so I cannot see how to predict any input text. (In contrast, when using a 12-byte IV, at least I would know that the last 4 bytes of the plaintext are a counter starting at 1). Note I obviously cannot see the plaintext after decrypting. I thought about trying to play with the knowledge that the IV will increase by one unit in each iteration, and possibly even trying with all starting values, but I am not sure how to make that work (or whether it is possible at all).

Any hints how to tackle this one?

Thanks in advance!!

Jose


#2

Hi Jose,

AES GCM can definitely be broken with side-channel attacks. I know it’s been done however I’m not an expert in doing it :wink:
I can note a couple of things though:

  1. Some attacks require only the plaintext to be known, others only the ciphertext. So you don’t necessarily need to know the AES counter.
  2. When the IV is anything other than 12 bytes, the initial counter is obtained by running the IV through the GHASH function. That function is also vulnerable to side-channel attacks – see e.g. this paper.
  3. In practice, I think that every use of GCM that I’ve seen uses 12-byte IV, likely for efficiency reasons.

That’s pretty much all I know about side-channel attacks against GCM, hope it helps.
Jean-Pierre


#3

Hi Jean-Pierre,

Thanks for your comment. To give a bit more context, this is used in a secure bootloader, which loads the encrypted application from flash and decrypts it into internal memory (but it does not expose the plaintext). Both the key and IV are derived from an ECDH operation (so I cannot see either of them), and the IV is indeed 16-byte long.

If I understand it correctly, when using AES in GCM mode, the input ciphertext is simply XOR’ed with the encrypted counter. For a 16-byte IV I believe this is more or less: output_plaintext = input_ciphertext ^ E( hashed_iv + counter ). If I had the ciphertext and the plaintext I would be able to XOR them to calculate the encrypted iv+counter, so I could mount an attack. But because the bootloader does not expose the plaintext output, I could possibly attack the XOR operation, but at most I would be able to extract the encrypted counter, not the IV or key. Am I making any sense?

On the other side, you mentioned that the GHASH function can also be attacked. Do you know if I would be able to do it given that I cannot control the input plaintext? I can predict some bits of it (the zeros and IV length), but those are fixed so I don’t think I can extract any statistical knowledge from them?

The only option that I can think of is to:

  1. Capture N traces of the decryption of the first 16 bytes while feeding random ciphertext, and attack the XOR to try and extract the encrypted counter
  2. Repeat this M times at different offsets, to try and extract M different encrypted counters
  3. Use these M traces with now-known-encrypted-counters to attack AES-ECB as usual

This might work if I can extract enough leakage from the XOR operation, but it would still require M*N traces. In my tests so far I need in the order of 500-2000 traces to break the bare AES implementation, so I can expect this approach to easily require more than 1M traces.

Does this make any sense? Am I missing an obvious simplification of the problem, or a better approach to it?

Sorry for the long exposition and thanks again for your response :slight_smile:

Thanks,
Jose


#4

Hi Jose,

I am not an expert in this so there is a chance I am wrong, but my understanding is that the plaintext is not required if you are attacking the last round of AES.

For an example of this, have a look at the CW305 hardware AES attack. The CW GUI hides what’s happening under the hood, but if you look at the updated version with Jupyter, you’ll see the attack only needs to know the ciphertext.

If this succeeds, then you have the AES key… but without knowing the IV you can’t decrypt yet (note it doesn’t matter if the IV is 12 bytes or not: in both cases you’re still stuck). But if you can predict what any of the plaintext blocks should be (perhaps it’s an executable that always starts with a particular pattern?), then you have E(IV, counter) for that block, which you can now decrypt, and now you have the IV :slight_smile:

I’m not familiar with GHASH attacks beyond being aware that there are papers on the subject. But I think the only reason one would want to attack GHASH is either:

  1. attacks on AES aren’t successful (e.g. due to strong countermeasures against side-channel attacks)
  2. you don’t care about decrypting: you only care about getting the hash key so that you may forge MACs, and attacking GHASH is perhaps faster than attacking AES to reach that goal

Good luck,
Jean-Pierre


#5

Hi Jean-Pierre,

Thanks for the pointers; I wasn’t aware of PA_HW_CW305.ipynb (although I don’t have the CW305 target, but the code is useful to read).

The difficulty in my case is that I have the ciphertext input for a counter mode decryption, and I do not have the plaintext output. PA_HW_CW305.ipynb seems to be using the last round state diff leakage model, but that assumes that you know the output from the last round of AES, and I don’t. The ciphertext that I can see never touches the AES block, so I don’t think I can make any prediction on the hamming weight of any value inside the AES block. If I got it right, to apply the same approach as in PA_HW_CW305 I would need the output from the AES block (ie: the encrypted counter), but I don’t have that; the only text I can see just gets XOR’ed with it. Does that make sense?

I suspect that I won’t be able to attack the GHASH function for a similar reason - that I cannot see or control any of its inputs or outputs, but I will look for papers; I will let you know if I find something :slight_smile:

BTW, I have already looked at the other tutorials and information, and I have managed to successfully mount an attack on the bare AES block in our platform, both using the tomcrypt 32 bit AES implementation and using the SAML11 HW accelerator. However for these attacks I had to modify the firmware so I knew the input and output of the AES block (ie: the encrypted counter); now I am trying to mount the attack in the same way a real attacker would (ie: knowing only the ciphertext data stored in flash). BTW, in our platform I always need far more traces than what the tutorials show (both for SW and HW, the PGE starts converging around 2k traces but I need about 5k to “complete” the attack), and there always seems to be one or two bytes that resist. Do you guys do anything in particular to reduce the noise in the measurements?

Thanks,
Jose


#6

Hi Jose,

Yes, I understand; I’m not sure which attack and leakage model would be best applicable in your case – it will depend of course on the implementation – but the point remains that some attacks require only the plaintext to be known, others only the ciphertext.

Regarding noise, one thing you can easily do with CW (but not with the GUI) is to average several measurements of the same key/text pair and feed those averages to the analyzer. Whether this saves you time depends on how much time it takes to acquire a trace and how much time it takes to attack.

2-5k traces doesn’t sound extraordinary if this is a real platform with other things adding noise. If there is any jitter in your trigger signal, that will also have an impact.

Jean-Pierre


#7

Hi Jean-Pierre,

Thanks for all the advice. I couldn’t find much about power analysis on the GHASH; they seem to concentrate on timing attacks which are not that useful for me as I don’t expect attackers to have control on the cache.

On the bright side, I think I found a potential approach: my target is not really to recover the encryption key, but to extract the decrypted plaintext. This simplifies the problem because then I can just recover each of the encrypted counters (by using chosen ciphertext for the analysis and attacking the final XOR), and then use the recovered encrypted counters as an “one time pad” for decrypting the actual ciphertext with a simple XOR. This doesn’t give me the key or IV, but I get the original plaintext. However, this approach can only be used in the cases where I can inject chosen ciphertext, so I am not done yet :slight_smile:

I am now looking at the ECDH operation where the key is derived, but the ECC library used has some countermeasures so I am struggling a bit with it :slight_smile:

Thanks,
Jose