-----BEGIN PGP SIGNED MESSAGE----- - From a recent comp.risks post: Newsgroups: comp.risks Subject: RISKS DIGEST 16.39 Message-ID: <CMM.0.90.1.778901594.risks@chiron.csl.sri.com> Date: 7 Sep 94 01:33:14 GMT Sender: usenet Reply-To: risks@csl.sri.com Distribution: world Organization: The Internet Gateway Service Approved: risks@csl.sri.com Lines: 624 RISKS-LIST: RISKS-FORUM Digest Tuesday 6 September 1994 Volume 16 : Issue 39 FORUM ON RISKS TO THE PUBLIC IN COMPUTERS AND RELATED SYSTEMS ACM Committee on Computers and Public Policy, Peter G. Neumann, moderator ***** See last item for information on RISKS (comp.risks) ***** Contents: PKZIP encryption broken (known plaintext attack) (Paul Carl Kocher) - ---------------------------------------------------------------------- Date: Sun, 4 Sep 1994 17:31:28 -0700 From: Paul Carl Kocher <kocherp@leland.Stanford.EDU> Subject: PKZIP encryption broken (known plaintext attack) I finally found time to take a closer look at the encryption algorithm by Roger Schlafly that is used in PKZIP and have developed a practical known plaintext attack that can find the entire 96-bit internal state. The basic encryption algorithm has four steps, two of which are based on linear shift registers, one is like a linear congruential, and the final converts the contents of an internal state register into an 8-bit value to XOR onto a plaintext byte. A complete description of the algorithm is included in the file APPNOTE.TXT, which is included with PKZIP version 1.1 (check Archie for "pkz110.exe"). Although the algorithm is substantially better than the toy ciphers used in many products, I have developed a practical known plaintext attack that finds the 96 bit internal state. Unlike the ZipCrack program I released a couple years ago, this attack finds the internal state registers directly and does not involve a brute-force attack on the password. If adequate known plaintext is available, my attack will find the state, regardless of the password's size or content. My attack is an improvement on a known plaintext attack described in a paper by Biham (unpublished work) that takes 2^38+ operations. My improvements reduce the amount of work required by approximately a factor of 1500 with 200 bytes of plaintext. With less plaintext the attack will take somewhat more time, but just 40 bytes should be enough to be practical. I've written code for all steps of the attack; a version written in C with a few optimizations in inline assembly runs in less than a day on my '486. The attack will work with versions 1.1 or 2.xx of PKZIP and other programs using the same algorithm. A more in-depth description of the attack will be made available soon, but I wanted to let people using PKZIP (and any other programs that use the same algorithm) know immediately about the weakness. Paul C. Kocher kocherp@leland.stanford.edu Independent data security consultant/contractor. 415-323-7634 [Disclaimers removed. PGN] - -- Ed Carp, N7EKG Ed.Carp@linux.org, ecarp@netcom.com Finger ecarp@netcom.com for PGP 2.5 public key an88744@anon.penet.fi ** PGP encrypted email preferred! ** "What's the use of distant travel if only to discover - you're homeless in your heart." --Basia, "Yearning" -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAwUBLnqUyiS9AwzY9LDxAQECcQP/cYtGpd8882KPmdPN0N1MZf4sjo4Mu8SY V9zEcRnU7VXU1WgqJiGSgyOQbYAaRxDSudtYKH5DHY+qvqLE397nkRuv1qjf5d9b PZ5Pw4YOEhAxVeq4DDSLYO5Lf2T4qs7IjVMETZjibV0feodbridG9XliEFdhrPWK vVhX3ZMWXH8= =oH6T -----END PGP SIGNATURE-----