1
$\begingroup$

Is keystream reuse a meaningful concern in AES-256 encrypted ZIP files that adhere to the AE-2 spec? From “Attacking and Repairing the WinZip Encryption Scheme” by Tadayoshi Kohno

when using 256-bit AES keys, we expect collisions after encrypting 2^64 files

This seems extremely high to me. So high that I'm wondering if it can't be hit in a practical sense. And can't be hit for two reasons:

  • The time/memory needed to construct a ZIP with so many member files
  • And even with unlimited time/memory, not even Zip64 files allow getting close to this. Zip64 uses 2^64-1 as the upper bound for lots of things, but this includes offsets for blocks of bytes and they all take much more than one byte.

So if you're definitely using AES-256, this isn't a concern?

Context: I'm trying to construct a meaningful list of practical concerns if using AES-256 + AE-2 encrypted ZIP files. I'm considering not including the keystream reuse issue stemming from including a large number of files, because the chance of encountering it is so low it can be ignored.

$\endgroup$
4
  • $\begingroup$ did you read the next paragraph? $\endgroup$
    – kelalaka
    Jan 6 at 11:28
  • $\begingroup$ @kelalaka I think yes. The next paragraph seems to focus on the reasons for collisions, with focus on AES-128. It’s not obvious to me that it answers my question on if this is a concern for AES-256 $\endgroup$ Jan 6 at 11:34
  • $\begingroup$ The key generated for 128-bit salt with a randomized ( not mentioned there) assumes a hash or hash based key derivations, then the usual collision applies.. $\endgroup$
    – kelalaka
    Jan 6 at 11:40
  • $\begingroup$ @kelalaka So yes, in AE-2 with AES-256 that uses a 128 bit random salt for each file, after around 2^64 files you would expect a collision as the paper suggests. I'm trying to work out if this is so high that the chance of this can be safely ignored because when making a ZIP file, even with Zip64, you just can't get anywhere near this. I'm leaning to yes for the reasons in the question, but I think I want someone else to say it! Or: if the answer is no: why should it not be ignored? $\endgroup$ Jan 6 at 12:35

1 Answer 1

1
$\begingroup$

I'm going to venture an answer. For most purposes this isn't a meaningful concern and the chance can be ignored.

But I think it's not quite a "1 proton in the known universe" level of "can be ignored". For cases with high numbers of files where very little risk is acceptable... I think it's worth more consideration. And specifically consideration around smaller probabilities of collisions - i.e. more risk averse than a probability of 0.5 which I think the linked paper is assuming(?)

Being inspired by https://stackoverflow.com/questions/62664761/probability-of-hash-collision and converting some of it to a Python function that works out how many files you need in a ZIP to get a certain probability of a collision:

from math import sqrt, log

def num_files_to_get_p_chance_collision(bits, p):
    return 2**((bits+1)/2) * sqrt(-log(1 - p))

I can then run

# The number of bits in AES-256 salt
salt_bits = 128

# Some very small probability
probability = 1/1_000_000_00
print(num_files_to_get_p_chance_collision(salt_bits, probability))

Which outputs 2608763578142670.0. So to get a 1 in a billion chance of a collision, I would need to make a ZIP with ~2.6 quadrillion member files. This would be in the peta/exabyte size range at least I suspect. I'm hesitant to say no-one would ever put so many files in a ZIP, lest it becomes another:

640K ought to be enough for anyone

:-)

Bringing it back to the aim of the question:

So if you're definitely using AES-256, this isn't a concern?

Context: I'm trying to construct a meaningful list of practical concerns if using AES-256 + AE-2 encrypted ZIP files. I'm considering not including the keystream reuse issue stemming from including a large number of files, because the chance of encountering it is so low it can be ignored.

I am tempted to include a concern for extremely high numbers of files in extremely risk averse situations. Although I'm not quite sure how to quantify "extremely"...

$\endgroup$
1
  • 1
    $\begingroup$ The problem is of course that if you go for AES-256 instead of AES-128 then you're already considering such a situation... But since the salt size of AES-128 is set to 8 bytes / 64 bits I'd suggest that you have to go for AES-256 to get any kind of decent protection. $\endgroup$
    – Maarten Bodewes
    Jan 6 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.