Will Price writes:
PGPfone uses Diffie-Hellman public-key technology to provide encryption keys for the user's selection of CAST, TripleDES, or Blowfish encryption algorithms
Does the Blowfish implementation address the weakness described below? --Jeff ------------------------ 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.