From: jbuhler@owlnet.rice.edu (Jeremy Daniel Buhler) Newsgroups: alt.security.pgp Subject: PKZIP mark II Summary: The new and improved -AV proposal Keywords: PKZIP -AV RSA Message-ID: Date: 10 Jan 93 19:26:58 GMT Organization: Rice University Lines: 284 Hi again. After receiving many helpful suggestions and corrections to my original post (thanx, y'all), I have made considerable revisions to the PKZIP -AV proposal. The new and improved text follows. If this draft passes muster, I will post it on comp.compression (home of PKZIP flames) and send a copy to PKWARE. I might even stamp it with the alt.security.pgp seal of approval: /~\ P /~(0)~\ P /~~~~~~~~~\ ------------- G ;-). ___begin_hysterics___ Towards a Secure -AV system for PKZIP A Proposed Public Key Scheme For .ZIP Protection By Jeremy Buhler v1.2 - 1/10/93 INTRODUCTION: PKZIP is an extremely popular compression utility which should become even more so following the release of the improved version 2.04c. However, one thing has definitely NOT improved with age: the -AV system, which in theory guarantees that files in an archive have not been modified or deleted. The -AV protection in version 1.10 was notoriously easy to break; that in 2.04c, which was released only a few days ago, has in principle already been broken. Clearly, a radically new scheme for -AV is in order. THE SPECS: The -AV system must prevent tampering with the files in the archive by maintaining specific information, such as CRC's, about the files in a tamperproof fashion. The system must be able to generate a unique identification for each of its users which cannot be easily duplicated. It must be reasonably quick in processing files when extracting them from the archive but may be slower when creating the archive, since that process occurs only once per .ZIP. THE INTERFACE (PROPOSED): The creator of the .ZIP archive executes a PUTAV program (sent by PKWARE upon -AV registration) after creating her archive. The PUTAV program accepts a password chosen by the creator, which allows it to generate the -AV protection and store it in the .ZIP. Alternatively, the PUTAV program may be invoked automatically by using a special command line switch (-! has been suggested) when calling PKZIP; the path to PUTAV may be stored in PKZIP.CFG. The recipient sees "-AV" next to the name of each file that passes the protection check as it is decrypted. If a file fails the check, or if one or more protected files are missing from the archive, a warning is signaled as the archive is unpacked. The PKUNZIP program displays a verification line after unpacking the archive, for example, -AV Key fingerprint: 3B 11 28 A6 54 16 92 2F AD 0F C4 43 22 A9 DA C2 Owner: PKWARE Inc. The fingerprint may be used to verify that the -AV protection was in fact generated by a particular creator by comparing it with a fingerprint calculated from the public key in that creator's PUTAV program. THE MECHANISM (PROPOSED): The mechanism, as stated, must give reliable protection in a format that is difficult to modify simply by editing bytes in the .ZIP. This rules out such simple mechanisms as CRC alone, because the CRC numbers may be changed in the .ZIP if one of its contents is modified. Instead, I propose that a public key encryption system such as RSA be used to create digital signatures for each file in the archive. How does it work? ___ The PUTAV program which the .ZIP creator receives in the mail contains a unique pair of keys, a public key and a secret key, of suitable size (say, 512 bits) for commercial security. Optionally, the key size may be increased, but this will degrade performance. PUTAV signs each file in the archive with the creator's secret key, producing a unique signature for each file which is very difficult to duplicate (read on for just how difficult). The header of the distributed .ZIP file includes the creator's public key as well as the signature of each compressed file. At decompression time, the signature is checked against the included public key. Only those files in the .ZIP which have -AV protection enabled are processed in this way. To further increase security, the key pair in the PUTAV program is signed with PKWARE's own secret key. PKWARE's public key is distributed as part of the PKUNZIP executable. PKUNZIP can verify that the creator's public key was generated and authorized by PKWARE by checking the signature using PKWARE's public key. PKWARE generates the key pair for each creator. The keys should be based on a good random number source, perhaps commercially available random number hardware, and generated automatically in much the same fashion as ID numbers are generated for the current -AV system. Is it secure? ___ A suitably large RSA, LUC, DSS, or other key provides secure protection from individual file tampering as long as the secret key is not compromised. The PUTAV program containing the secret key may be stored securely by the .ZIP creator, say on a write-protected floppy in a safe, since it is not necessary other than to create new -AV'd .ZIP's. The PUTAV program should also be protected using some form of conventional encryption with a key based on a password chosen by the creator. For maximum security, the PUTAV program should be compressed prior to encryption with PKLITE to decrease redundancy that would allow an attacker to defeat the cipher. It is computationally infeasible for most attackers to factor a 512-bit public key to derive the corresponding secret key. The average attacker of an -AV'd .ZIP uses only a PC, or at most a workstation, and has little knowledge of cryptography. However, even a determined attacker using a supercomputer will have to sweat considerably before breaking a 512-bit key. An even larger key size practically guarantees security from this type of attack, pending advances in factoring and faster hardware. Of course, the key size can be increased arbitrarily if security warrants the extra time required to create or extract from the archive. There is another method by which -AV may be compromised, however. The attacker could generate a new public/secret key pair, create their OWN -AV'd .ZIP file, and alter the message in the .ZIP which identifies the creator, for example Authentic files Verified! # PKW655 PKWARE Inc. The test on decompression would succeed with the fake public key, and the end user would be unaware that the key was bogus. This is called "spoofing." A partial defense against this kind of attack is PKWARE's signing of the creator's key pair with its own secret key. Since PKWARE is a trusted intermediary between the creator and the end user (else why is the end user using PKZIP at all?), its signature on the public key guarantees that the key belongs to a registered PKZIP user. This trust is valid, however, only as long as PKWARE's own secret key is not compromised. The PKWARE secret key should be stored as securely as possible because of its place at the top of the key trust hierarchy. The -AV'd .ZIP file will include a verification line containing the creator's name. This block could be encrypted using a conventional cypher, though not necessarily a very secure one, to prevent "creative editing" by an attacker. The primary reason for encrypting the verification block is that it should also contain the number of -AV'd files in the .ZIP to guard against deletions from the archive. A better alternative for protecting the verification line would be as follows: the PUTAV program could generate a single signature for *all* -AV'd files plus the verification line together in addition to the signatures for each file; deleting a file from the .ZIP would cause a check based on the whole-file signature to fail. This kind of check should be limited to -AV'd files only to allow for the later inclusion of extra files such as BBS ads in the .ZIP. The identification number displayed in the verification line should not be an arbitrary serial number but rather a signature unique and intrinsic to the creator's key pair, based on a cryptographically strong hash of the public key. It is statistically extremely unlikely that two public keys would ever be generated with the same signature. The hash therefore is a unique, human-readable identifier, or fingerprint, for the public key. The problem now becomes, "Is the public key in the .ZIP really the creator's?" This is, of course, the essential problem with public key cryptography :-), but it is no worse a weakness than the verification of the serial number in the present .ZIP. In fact, because PKWARE signs every key pair, any spoofed archive must have been generated with a legitimate PUTAV program. PKWARE could take action to notify the owner of the stolen key of its compromise and generate a replacement key pair. Although PKWARE's signature on the creator's public key narrows the number of possible spoofs considerably, it does not eliminate them altogether. The creator and the end user must work out a secure method for communicating the public key's fingerprint. Possible solutions include posting the public key or its fingerprint widely before distribution of the .ZIP, maybe in the previous version of the archived software [thanks to virus researcher Vesselin Bontchev for this suggestion - J.B.]. In all cases, the creator must decide what level of confidence in the public key is acceptable to her end users, and each user must decide whether to trust the public key. Programs requiring very high confidence could require confirming the key's fingerprint over the phone; creators less subject to spoofing could either list the fingerprint in hard copy manuals or use some form of prerelease of the key as described above. It is still advisable to distribute the public key in the .ZIP header, however, for those too lazy or unable to check the key's validity or those who have received the file through secure channels. THE DEGREE OF SECURITY IN THIS -AV SYSTEM ULTIMATELY DEPENDS ON THE END USER. This is as true for all previous -AV systems as for this one. Of course, even an unchecked signature, if signed by PKWARE, will still prevent an attacker from modifying part of an originally secure .ZIP or generating a totally random bogus key, forcing her to resort to whole-archive spoofing with a stolen key. Against partial modification, digital signature by public key is significantly more secure than almost any method available today, and certainly more than any method practical for a personal computer. Weaknesses of the scheme ___ The above discussion assumes an attacker will try to break the RSA cipher or spoof the archive with an existing secret key. However, other methods of attack are: - The attacker could distribute a bogus version of PKUNZIP with a false public key. This can be partially remedied by using only copies of PKUNZIP distributed legitimately in the PKWARE SFX, but this is not a spoof-proof solution. - The attacker could doctor PKUNZIP so as to disable the verification routines. A sabotaged program would appear to execute the -AV check but pass unsecure archives. See above for partial prevention. - The attacker could order a legitimate key pair from PKWARE, then pretend to be a known creator. This defeats the security of PKWARE's signature on the key. Secure communication of a creator's fingerprint to her end users is the only defense against this attack, though PKWARE should check for suspicious orders from someone purporting to be a known creator but using a different check or credit ID, address, etc. - The attacker could acquire either a creator's or PKWARE's secret keys. While this is covered above, the extent of security required to prevent it depends on the author's paranoia :-). The attacker could steal the creator's computer to get at the key and perhaps read the password from a distance with a telescope or EM sensing equipment to capture the creator's keystrokes. Sensible precautions against placing either the password or the secret key in a vulnerable location will defeat this type of attack. Of course, sensible precautions vary with the level of security. - A bug in the code could render the entire apparatus unsecure. Caveat hacker. - The factoring or other hard problem underlying the whole public key scheme could be solved with an easy method. This is highly unlikely with RSA in the near future, but it cannot be ruled out. - Insert your own method. Attackers are infinitely devious, while the software author is as a rule only finitely so. Infinite protection requires infinite code, infinite time, and infinite luck. This is why Phil Zimmerman, author of the popular PGP public key encryption software, named his program "Pretty Good Privacy." Where are the algorithms available? ___ The requisite algorithms for implementing this system are licensed by various companies. The time-tested RSA algorithm may be licensed from RSA Data Security (rsa.com on the Net). For information on LUC, or Lucas Number, encryption, see the article in the January 1993 Doctor Dobb's Journal; for information on DSS, talk to the National Institute for Standards and Technology (NIST). To see an implementation of RSA in action, see the popular PGP software by Philip Zimmerman or RSA's RIPEM mailer add-on. Technical information, a non-commercial use license agreement, whom to call for info, and the C source code for RSA are available to U.S. citizens for anonymous FTP at rsa.com . It is the de facto policy of the NSA (and therefore of the Commerce Department) to allow arbitrarily large key sizes in public key software for export which is used only for digital signatures. There should be no problem getting an export license for PKZIP due to the presence of the RSA or other algorithm, provided the routines are written so as to be useful ONLY for digital signatures and not for encryption. This makes advisable the use of the whole-archive signature method described above for protecting the verification line rather than any attempt to encrypt that line. Of course, a possible objection to export could stem from the encryption used on the PUTAV program itself. CONCLUSION: -AV protection has been problematical for PKZIP ever since its inception. With the advent of public key digital signatures, this problem may at last be solved. Public key should provide excellent protection against modification of part of the archive or random spoofing by average attackers and very good protection against the same by determined attackers with great resources (e.g., governments, large corporations, etc). While protection against the worst case, whole-file spoofing with a stolen key, is less effective, it does not demonstrate a loss of security versus previous methods. The algorithm's lifetime may be arbitrarily prolonged by increasing the key size, and the decompression check code may be written so as not to penalize operation unduly. This protection could make PKZIP the archiver of choice for the distributor worried about file tampering within .ZIP's. Thanks to Vesselin Bontchev, Jan-Pieter Cornet, and the rest of the alt.security.pgp newsgroup, who made many helpful additions and corrections to this document. Jeremy Buhler jbuhler@owlnet.rice.edu ___end_hysterics___ -- < Jeremy Buhler * In real life: jbuhler@owlnet.rice.edu > < Rice U., Houston, TX, USA * Ceci n'est pas une .sig - zut alors! > < All opinions expressed herein are my own and should not be in any > < way construed to represent the views held by Jeremy Buhler fnord. >