From proff Mon Jul 8 08:20:25 1996 Received: (proff@localhost) by suburbia.net (8.7.4/Proff-950810) id IAA00851 for best-of-security; Mon, 8 Jul 1996 08:20:23 +1000 Received: from toad.com (toad.com [140.174.2.1]) by suburbia.net (8.7.4/Proff-950810) with ESMTP id AAA21488 for ; Mon, 8 Jul 1996 00:31:55 +1000 Received: (from majordom@localhost) by toad.com (8.7.5/8.7.3) id HAA29015 for coderpunks-outgoing; Sun, 7 Jul 1996 07:17:16 -0700 (PDT) Received: from bloom-beacon.MIT.EDU (BLOOM-BEACON.MIT.EDU [18.181.0.26]) by toad.com (8.7.5/8.7.3) with SMTP id HAA29010 for ; Sun, 7 Jul 1996 07:17:08 -0700 (PDT) Received: (from uucp@localhost) by bloom-beacon.MIT.EDU (8.6.13/25-eef) with UUCP id KAA14943 for coderpunks@toad.com; Sun, 7 Jul 1996 10:11:11 -0400 Received: by orchard.medford.ma.us (8.6.9/1.34) id OAA23922; Sun, 7 Jul 1996 14:05:46 GMT Date: Sun, 7 Jul 1996 14:05:46 GMT Message-Id: <199607071405.OAA23922@orchard.medford.ma.us> From: Bill Sommerfeld To: coderpunks@toad.com Subject: implementation error in blowfish. Sender: proff Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Seen on sci.crypt. Out of curiosity, has anyone playing with blowfish seen this in practice? What about systems like PGPphone? - Bill From: mmorgan@dgii.com (Mike Morgan) Subject: Blowfish can be cracked! (Fix included...) Newsgroups: sci.crypt Date: 6 Jul 1996 18:53:18 GMT Organization: Digi International Path: news-central.tiac.net!news-in.tiac.net!news.kei.com!newsfeed.internetmci.com!mr.net!news.mr.net!gw.dgii.com!mmorgan Lines: 111 Message-ID: <4rmcmu$kjd@gw.dgii.com> NNTP-Posting-Host: digibd.dgii.com X-Newsreader: NN version 6.5.0 #6 (NOV) Warning: Blowfish can be cracked. (I apologize for the sensationalism. I also apologize if this has been mentioned before. This needs your attention.) I have found a way to crack 80 bytes of ciphertext encrypted with the blowfish algorithm (ECB mode), 25% of the time. Blowfish, as printed in "Applied Cryptography, Second Edition", and as corrected in Bruce Schneier's Errata Sheet, using a randomly generated 64 bit key, can be cracked in much less than 10 minutes on a Pentium 120MHz (10 minutes is worst case). According to my calculations, with optimizations, I could cut this down to about 5 seconds to 2.5 minutes worst case. Previously, I wrote: >... >I have come up with several sets of vectors, >{k1,k2,pl,pr,cl,cr} such that when you use >k1 or k2 to encrypt pl and pr you will always >get cl, and cr, where k1={b10,b11,b1...,b1n}, >where b1i is the ith byte in the key k1, and >where n is divisible by 4. >... > > >Mike Morgan I investigated this further, and it turned out to be a source code implementation error. There is an implementation error in published Blowfish Code. The program chokes on the commented "choke" statement, below: bfinit(char *key,int keybytes) { unsigned long data; ... j=0; ... data=0; for(k=0;k<4;k++){ data=(data<<8)|key[j];/* choke*/ j+=1; if(j==keybytes) j=0; } ... } It chokes whenever the most significant bit of key[j] is a '1'. For example, if key[j]=0x80, key[j], a signed char, is sign extended to 0xffffff80 before it is ORed with data. For examle, when: (j&0x3)==0x3 (that is j=0x3,0x7,0xf, etc.) - -and- (key[j]&0x80)==0x80 (or when k[j]=0x80,0x81,etc.) data=0xffffff80 (0xffffff81,etc.) upon exit from the above "for(k=...)" loop. ORing all of these 1's into data effectively wipes out 3/4 of the key characters! (that is, 3/4 of the key characters are known to be set to 1 when the 4th key byte to be ORed into data has a 1 in the most significant bit.) For a randomly selected 32-bit key, there is a 50% chance that 3/4 of the key could be considered as all '1's, even if they weren't that way to begin with. This is obviously a security issue. Note, contrary to my previous statement, the key length in bytes _does not_ need to be divisible by 4 to exploit this implementation flaw. The following fix has been verified to work: data<<=8; data|=(unsigned long)key[j]&0xff; Another fix is to declare 'key' as 'unsigned char *'. Other fixes are possible. NOTE: Most test vectors will not check for this bug because they use keys comprised of ASCII (value<0x80) strings. This bug does not show up when every character in the key has a value less than 0x80. This should be corrected and noted in the source code for blowfish. Also, test vectors with unsigned character values greater than 0x80 should be generated and published. I did not notice this bug in the "Applied Cryptography" errata. It should be noted there, too. This flaw may or may not be present in other implementations of the Blowfish algorithm. Thanks to non-standard use of the 'union' construct, I think others who use blowfish may or may not have avoided this bug. In cases where this bug has been avoided, it may have been done purposefully or inadvertantly. Regards, Mike Morgan, Hardware Engineer Digi International, mmorgan@dgii.com - -- I do not speak for my company in this post. -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMd/ENrT+rHlVUGpxAQGBiQP+Ko37nEMS0K7pYXDc83rbrBo08SYjlW7V I32jEZFy/nqRxRGfGKj88f8Gy/Ilr00TCcrpKDUri33X99lpxLyNSerXuKnJ8WBC noSuCMl7FcOGM8MRG8QUN6lZ5EQHEOq0DHVjAuQDk+LBiMwdqJgHPtwNNtbOGTX1 +V4HkJIxuCs= =eLK1 -----END PGP SIGNATURE-----