Subject: [Cfrg] Collision issue in ciphertexts.

From: "Dang, Quynh" <[email-masked]>
Date: Mon, 2 Nov 2015 07:13:39 +0000

Hi Eric,

As you asked the question about how many ciphertext blocks should be safe under a single key, I think it is safe to have 2^96 blocks under a given key if the IV (counter) is 96 bits.

When there is a collision between two ciphertext blocks when two different counter values are used , the chance of the same plaintext was used twice is 1^128.  Collisions start to happen a lot when the number of ciphertext blocks are above 2^64. However, each collision just reveals that the corresponding plaintext blocks are probably different ones.

Quynh.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 2 Nov 2015 05:07:45 -0500

On Nov 2, 2015 2:14 AM, "Dang, Quynh" <[email-masked]> wrote:
>
> Hi Eric,
>
>
> As you asked the question about how many ciphertext blocks should be safe
under a single key, I think it is safe to have 2^96 blocks under a given
key if the IV (counter) is 96 bits.

This is wrong for PRP, right for PRF. It's not that hard to find the right
result.

>
>
> When there is a collision between two ciphertext blocks when two
different counter values are used , the chance of the same plaintext was
used twice is 1^128.  Collisions start to happen a lot when the number of
ciphertext blocks are above 2^64. However, each collision just reveals that
the corresponding plaintext blocks are probably different ones.

Which breaks IND-$. Let's not be clever, but stick to ensuring proven
definitions are true.

>
>
>
> Quynh.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Dang, Quynh" <[email-masked]>
Date: Mon, 2 Nov 2015 20:00:27 +0000

Now, you talked about a MAC function (with AES). I previously talked about encryption.

If I , the only person, uses the MAC key, when I generate more than 2^64 MAC values (Let's say each MAC value is 96 bits), I have many collided MAC pairs. But, I am the only one (beside the person(s) verifying my MACs) who knows the MAC key in order to generate those  verified MAC values.

If the MAC length is k bits, an attacker is allowed to send 2^n failed verifications, his or her chance of success is approximately 2^n / 2^k. Let's imagine n is 64 and k is 96, the success chance is 1/2^36 which is practically ZERO!

If I am an attacker, I would choose a message that I want to be verified, and I keep changing the MAC key to generate different MAC values with different keys and hope one of them will get verified.  Let's assume the MAC key to be 96 bits ( 96 bits of random bits, the other 32 bits are known). In theory, when I get close to 2^96 attempts, I would expect some chance of success. To deal with this attacker, one would change the MAC key when the number of failed attempts gets close to a number that you don't want. For example, if you don't want a success chance of an attack to be above 1 / 2^36, then you need to change your MAC key when the number of failed verifications reaches 2^64 when your MAC length is 96 bits.

After you change the MAC key, I ( the attacker) will have to start everything again because all of the failed MACs I generated before are useless now.

________________________________
From: Watson Ladd <[email-masked]>
Sent: Monday, November 2, 2015 5:07 AM
To: Dang, Quynh
Cc: [email-masked]; [email-masked]; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.

> As you asked the question about how many ciphertext blocks should be safe under a single key, I think it is safe to have 2^96 blocks under a given key if the IV (counter) is 96 bits.

This is wrong for PRP, right for PRF. It's not that hard to find the right result.

> When there is a collision between two ciphertext blocks when two different counter values are used , the chance of the same plaintext was used twice is 1^128.  Collisions start to happen a lot when…

Which breaks IND-$. Let's not be clever, but stick to ensuring proven definitions are true.

> [email-masked]<mailto:[email-masked]>