Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
> On Sat, Jul 13, 2019 at 02:41:34PM -0400, Joe Conway wrote:
> >On 7/13/19 9:38 AM, Joe Conway wrote:
> >[5] has this to say which seems independent of mode:
> >
> >"When encrypting data with a symmetric block cipher, which uses blocks
> >of n bits, some security concerns begin to appear when the amount of
> >data encrypted with a single key comes close to 2n/2 blocks, i.e. n*2n/2
> >bits. With AES, n = 128 (AES-128, AES-192 and AES-256 all use 128-bit
> >blocks). This means a limit of more than 250 millions of terabytes,
> >which is sufficiently large not to be a problem. That's precisely why
> >AES was defined with 128-bit blocks, instead of the more common (at that
> >time) 64-bit blocks: so that data size is practically unlimited."
> >
>
> FWIW I was a bit confused at first, because the copy paste mangled the
> formulas a bit - it should have been 2^(n/2) and n*2^(n/2).
>
> >But goes on to say:
> >"I wouldn't use n*2^(n/2) bits in any sort of recommendation. Once you
> >reach that number of bits the probability of a collision will grow
> >quickly and you will be way over 50% probability of a collision by the
> >time you reach 2*n*2^(n/2) bits. In order to keep the probability of a
> >collision negligible I recommend encrypting no more than n*2^(n/4) bits
> >with the same key. In the case of AES that works out to 64GB"
> >
> >It is hard to say if that recommendation is per key or per key+IV.
>
> Hmm, yeah. The question is what collisions they have in mind? Presumably
> it's AES(block1,key) = AES(block2,key) in which case it'd be with fixed
> IV, so per key+IV.
I've spent a while trying to understand where the formula comes from. If the
problem can be expressed as "avoidance of repeating blocks of ciphertext",
then it's basically the known "birthday problem". Then we can use this formula
[1]
n ~ sqrt(2 * m * p(n))
(note that the meaning of "n" is different form the formula introduced
upthread) and substitute
1) 0.5 for the probability p(n)
2) 2^b for the number of distinct blocks "m", where "b" is number of bits in
an encryption block
Then the formula becomes
n ~ sqrt(2^b)
and thus
n ~ 2^(b/2)
So if the number of safely encrypted blocks was derived this way, I agree that
IV was not taken into consideration: if there is an IV, then identical blocks
of ciphertext are not a problem because they represent different blocks of
plaintext.
[1] https://en.wikipedia.org/wiki/Birthday_problem#Square_approximation
--
Antonin Houska
Web: https://www.cybertec-postgresql.com
