9
$\begingroup$

I have an old sourcecode backup from my DOS days stored in a ZIP 2.0 encrypted archive, but I lost the password.

The password was written on a paper slip, but I remember that it consisted of 30+ completely random alphanumeric characters with some special symbols in between.

I have read that a GPU cluster will crack old ZIP 2.0 archives almost instantly, and that there is a vulnerability in the ZIP 2.0 encryption allowing an attacker to recover the password instantly if there are multiple files in the archive.

But what if there is only one file in the archive, and the password consists of 30 completely random characters?

Can I expect fast recovery if I can run the process on a GPU cluster?


Addition: The archive was created with PKZIP 2.04C and there is nothing known about the filename extension and nothing known about the plaintext.

Does it change the calculus that the archiver was 2.04C and not 2.04G?

$\endgroup$
  • $\begingroup$ I've made the title more generic and added known plaintext attack, although the latter isn't mentioned in the question but is an evident attack vector in the answer. $\endgroup$ – Maarten Bodewes Oct 7 at 17:02
10
$\begingroup$

I will start with all relevant references I found, then tentatively answers the question. Feel free to improve this community wiki.


It was originally asked the effort to break PKZIP 2 encryption, described in section 6.1 of the .ZIP File Format Specification (with some refinements in the derived Info-ZIP appnote), assuming a high-entropy password (that is, next to 96-bit entropy for the internal key after password preprocessing), and a single file in a zip archive.

A most relevant attack on this cipher was made by Eli Biham and Paul C. Kocher: A known plaintext attack on the PKZIP stream cipher (1994, in proceedings of the 2nd FSE workshop).

That was improved by Michael Stay: ZIP Attacks with Reduced Known Plaintext (in proceedings of FSE 2001).

Peter Conrad's PkCrack is an implementation of the above with source and additional comments. It is the basis of the PKZIP section in Mark Stamp and Richard M. Low's Applied Cryptanalysis: Breaking Ciphers in the Real World (2007, Wiley-IEEE Press), nicely summarized in these slides.

In a single-file setup, these attacks depend heavily on the availability of some of the plaintext (formed by a 12-byte header, and the compressed form of the original file). At least about 13 known plaintext bytes are required (for a complexity of $2^{39}$ operations), more plaintext makes the attack easier. In the aforementioned 12-byte header, at least 1 byte is always known (part of the CRC in the archive's directory), or 2 bytes in archives made to be decipherable by PKZIP prior to version 2. Depending on the encryption/archiving program, some of the 11 or 10 other header bytes maybe low-entropy, for they are generated by a non-cryptographic RNG (sometimes rand() with 31-bit state as described in Michael Stay's article, or a variant where the additive constant is omitted according to this source; for a generator once in PKZIP 1.xx, refer to the Paul Kocher's ZIPCRACK documentation).

Further improvements are claimed by Kyung Chul Jeong, Dong Hoon Lee and Daewan Han's: An Improved Known Plaintext Attack on PKZIP Encryption Algorithm (in proceedings of ICISC 2011, paywalled); from the abstract, there seem to be improvements including in the single-file setup.

The following is thus very relevant (and unstated in the original question):

  • the exact program that generated the archive (that may be ambiguous from the archive);
  • the compression format/parameters (mostly known from the archive's directory);
  • the type/extension of the file (typically known from the archive);
  • whatever else is known about the plaintext and context of the creation of the zip file.

I have so far failed to locate information about details relevant to cryptanalysis:

  • the RNG (and its seeding) as in various versions of PKZIP 2;
  • the nature of the changes documented in late PKZIP 2 (see whatsnew.204) as:

    The security of (encryption) has been significantly improved in PKZIP/PKUNZIP 2.04c

  • how many files enciphered under the same password, each giving 1 plaintext byte, allow carrying an efficient attack (but that's irrelevant to the question).

It was added:

The archive was created with PKZIP 2.04C and there is nothing known about the filename extension and nothing known about the plaintext.

Notice that in this sentence plaintext likely refers to the original file data, when everywhere else in this answer (following the terminology in the quoted literature) plaintext refers to the 12-byte header and the compressed form of the original file data.

It would be unusual that the filename and extension are not in the archive: by default, PKZIP 2 includes it in clear starting at offset 30, and before the PK marker at offset -22 from end-of-file. At least, the compression method used to produce the plaintext from the original file data, and one byte of the 12-byte header (taken from CRC), are bound to be in any undamaged archive (and readily shown by opening it with a modern zip tool such as 7-zip). The file name and extension, and ensuing reminiscence of the legitimate file owner, usually give some information on the original file. Let's, however, consider that a random file was given as input.

As stated, I found no analysis of the RNG used to prepare the 11 bytes of the header in PKZIP 2.04c and later; I'm incompetent about x86 code reverse-engineering; and anyway, from the whatsnew.204 citation above, likely this RNG is not nearly as bad as it was assumed to be in early ZIPCRACK, so I can best describe these bytes as random. I am not aware that the compression methods in PKZIP leave an easily modeled redundancy in their output. The only method that I can imagine to recover the (internal) key is to subject some of $2^{88}$ candidates to an impractically expensive test: that the plaintext could not have been generated by the compression method used (assuming the file is compressed rather than stored, I guess that a test of the CRC of the deciphered and uncompressed file can not help by a huge factor: if the original file data is short enough that this test is relatively inexpensive, too many candidate keys will remain that pass whatever automatic test we apply). Baring hypothesis change or progress in some of the above, it is inconceivable that the original file data can be recovered from the archive using anything remotely comparable to the computing effort that a GPU cluster can make in its operational life: if we had a thousand units of some kind each weeding a hundred thousand keys per microsecond for a century, odds are one in a thousand that the right key would be found.

Addition following partial quotation: I want to stress that the above bold statement makes multiple hypothesis:

  • a single file is encrypted; this is often not the case with real ZIP archives; multiple files enciphered with the same key, including in the same zip archive, do ease breaking PKZIP crypto;
  • nothing exploitable is known about the file's content; like, it is fully random, including its start; this is seldom the case for real files, to the point of making my statement theoretical in nature;
  • PKZIP 2.04g was used (which has become increasingly uncommon);
  • the PKZIP 2.04g TRNG has no major weakness (which I have not verified, and may depend on context; like, running in a VM);
  • the key has 96-bit entropy (most passwords used in practice have much less entropy);
  • the compression method used does not introduce exploitable redundancy (I only stated that I am not aware that this occurs).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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