Subject: BoS: implementation error in blowfish.
Resent-Date: Mon, 8 Jul 1996 08:20:28 +1000
Resent-From: best-of-security@suburbia.net
Date: Sun, 7 Jul 1996 14:05:46 GMT
From: Bill Sommerfeld <sommerfeld@orchard.medford.ma.us>
To: coderpunks@toad.com

-----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-----