From: williams@va.arca.com (Jeff Williams)
Date: Fri, 12 Jul 1996 05:54:28 +0800
To: wprice@primenet.com
Subject: Re: ANNOUNCEMENT: PGPfone Beta 7 Now Available for Download
Message-ID: <3257270267.87025315@va.arca.com>
MIME-Version: 1.0
Content-Type: text/plain


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.