3

I've read some articles and tutorials about AES GCM and was using this cipher for one of my java-projects, so let's say I know some basics.

I read that you should use an IV-length of 12 bytes which means that there should be more than enough unique IV's availble because you should never use the same IV again in combination with the same key. For creating a random IV I was using the SecureRandom class in java, so not very surprising.

Now please consider the following: I have to encrypt data which is being sent out through an unsafe network and every packet has to be independent. In numbers: I'm sending 120 packets per second, which are 432000 packets per hour, all using the same key. So this number is not that impressive but if we suppose that this serivce is running the whole day then we will see 10.3 Mio. independent packets and therefore 10.3 Mio IV's which should be unique. Since nobody can guarantee that SecureRandom does not deliver duplicates, it could be that my service is using identical IV's which should be unique.

Now my questions:

How likely is a collision using SecureRandom and how could I avoid it? I mean I could keep track of all used IV's but that wouldn't be efficient as time goes on.

Is it true that someone could reconstruct the key if IV's are not being unique? How could this be done, how much effort would be neccesary to achieve this? Are there any numbers which could demonstrate this? e.g. if a "correct" implementation would need a calculation of 2^128, a wrong one would only need 2^30.

I know that some answers are probably difficult or impossible but I'd like to get a feeling about how much security is being impacted if IV's are not unique, how "easily" AES GCM could be broken under the mentioned circumstances.

Thanks a lot!

3
  • 1
    If the IV is 12 byte (96 bit) long, then the chance of randomly getting two identical IVs is very, very small.
    – user163495
    May 9, 2019 at 11:05
  • 1
    Since this question seems to focus purely on Cryptography, I flagged it for migration to Cryptography.
    – user163495
    May 9, 2019 at 11:34
  • If the answer satisfies you, could you accept to close this question?
    – kelalaka
    Aug 21, 2019 at 17:53

1 Answer 1

1

If we accept that SecureRandom is a true random then the expected collision for IV is given by the birthday paradox is sqrt(2^96) = 2^48. Your daily message is 2^24 and this will have a very low collision probability. You will have 6.783914×10-16 chance of collision probability for the day. However, once the collision occurs we have IV reuse.

IV reuse is very dangerous for GCM. Internally, GCM uses the CTR mode of operation for encryption and if the key and IV are the same then the two-time pad attack are possible as in OTP.

CTR mode, even, reveals the plaintexts due to IV reuse, doesn't leak the key. The two-time pad attack once successful reveals the keystream generated by the CTR mode. Then the attacker has to execute a known plaintext attack on AES which has known as resistance to this attack. The only applicable attack is the brute force ( other than the side-channel attacks).

Also, IV reuse can leak information about the authentication key;

In messages up to ℓ blocks long, after a single nonce reuse the adversary can narrow the authentication key down to ℓ possibilities with polynomial root-finding and thereby forge messages with high success probability 1/ℓ.

Instead of selecting randomly, you can choose your IV by applying a monotonic counter, that is usual in practice and recommended in NIST 800-38d, page 20, 8.2.1 Deterministic Construction.

2
  • Thanks very very much for this greate answer. Would it be safe to use a hash generated by currentTimeMillis() + random bytes as IV? Reuse would only be possible if the timestamp and the random bytes are equal which is for sure more less likely than only using random bytes.
    – BlackFlag
    May 19, 2019 at 12:25
  • You can use the IV as incremental, it is a general practice to avoid IV reuse. A Cryptographic collision-free hash function with expected random input will have a negligible collision.
    – kelalaka
    Aug 18, 2019 at 11:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .