• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Why is Blowfish limited to a 448-bit key length?

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Goto page 1, 2  Next
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Tue Oct 12, 2004 11:08 pm    Post subject: Why is Blowfish limited to a 448-bit key length? Reply with quote

hi everybody,

me new here greetings to all :)

now could one of you cracks PLEASE explain to me this:

blowfish has a max keysize of 448 bits - AS IT SAYS.
because consider the following code fragment of bfinit() [the only place where the key is EVER used directly in all of the algorithm]

j = 0;
for (i = 0; i < N + 2; ++i) {
data = 0x00000000;
for (k = 0; k < 4; ++k) {
data = (data << 8) | key[j];
j = j + 1;
if (j >= keybytes) {
j = 0;
}
}
P[i] = P[i] ^ data;
}

now again and again and again I BREAK MY HEAD
but since N = 16 (defined) this nested slope makes (16+2)*4 rounds
so that is --> 576 <-- bits of key that could max be used... sigh
but why why why schneier & everyone say max keysize is 448 bits????

I JUST DONT UNDERSTAND IT *booohooo*

please please somebody explain thx a lot

greetz, michael

ps: the code is original - taken from schneiers implementation http://www.schneier.com/code/bfsh-sch.zip
pps: schneier himself has in his code the "choking" flaw he mentions under http://www.schneier.com/blowfish-bug.txt (key is signed char in his implementation)... *g*. maybe somebody knows him and could tell him?
Back to top
View user's profile Send private message
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Wed Oct 13, 2004 12:07 am    Post subject: Reply with quote

this is the formatted code hope this will work & sorry for the mess

Code:

    j = 0;
    for (i = 0; i < N + 2; ++i) {
      data = 0x00000000;
      for (k = 0; k < 4; ++k) {
        data = (data << 8) | key[j];
        j = j + 1;
        if (j >= keybytes) {
          j = 0;
        }
      }
      P[i] = P[i] ^ data;
    }
Back to top
View user's profile Send private message
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Thu Oct 14, 2004 11:27 am    Post subject: this is really amazing... Reply with quote

... that no one wants to answer something here. or is it that nobody CAN?

i have now further investigated into the matter and did a practical test: blowfish init with a key size of 576 bits, encipher, blowfish init with the same key, but shortened to a size of 448 bits, and decipher.

well this does NOT work. meaning if i feed 576 bits into the algorithm the result is distinctively different than feeding in this keys first 448 bits only... as i had concluded from the source and which any programmer can see easily i'd say.

so now this is NOT a trivial problem. either - 448 bits is the cryptographical, number theoretical security that will not raise if more bits are feeded into the init-cycle. but schneier never mentions anything like this anywhere. not in his books, not on his website.

OR

there is a major implementation bug in schneiers code which was copied by EVERYBODY. this were the case if the statement should actually read: for (i = 0; i < N - 2; i++) / note: i - 2, not i+2 !!! were this the case it would mean that the last 4 elements of the P[Array] are intended to be some sort of constants NOT to be xored with keybits.... and that would yield a keysize of 448 bits max then... but these last P values are ALWAYS xored with whatever keybits because there is a turnaround for key as the slope is programmed as it stands. (however many bits you feed in all 18 P values are xored with some of these bits that is)

so... really REALLY nobody interested to investigate into this or explain this further?

AND! wouldn't it be GREAT fun to find an implementation flaw in schneiers code repeated in every blowfish implementation anywhere?

THERE IS A BUG so far this is confirmed / i am absolutely positive about that. cause feeding a 576 bit key is NOT the same as feeding the same key, shortened to 448 bit... so this means stating the max keysize to be 448 bit is WRONG. at least as the implementation stands you can also feed with 576 bits with a DISTINCTIVE different result (may or may this be more, or the same, secure as with 448 bits - but that's a different question actually regarding the overall "rightness" / congruency of the source)

and to summon up: schneiers code HAS a flaw or at least a major inconsistency undiscovered for many years and copied by so many... and additionally it might WELL be - if the last 4 values of P were INTENDED to be constants by original cipher design - that this raises SERIOUS security concerns.

greetz,
and hoping very much that some of you cracks could decide to join this discussion,
michael
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Thu Oct 14, 2004 4:05 pm    Post subject: Reply with quote

hi,

Did that code come from bruce schneier's book. I also thought there was some thing wrong with the key(in the c code) but then forgot it all together. I will just relook the code in schneier's book today and get back to you.

If you want to write to him you can do so at
http://www.schneier.com/

If you can wait for a day or two, i can look at the code and get back to you.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Thu Oct 14, 2004 5:01 pm    Post subject: Confused about diffusion. Reply with quote

This is wondered by many; it isn't so much of a functional anomaly as it is a design consideration with security in mind. You see, Blowfish contains what they refer to as a "P-array", which holds 18 subkeys of 32 bits in length (P1, ..., P18, respectively). Specifying 448-bit keys, as a maximum, was more of a means of designating a secure parameter that complements the design strategy used within its Feistel network; this size was used because of the assurance that the subkeys would be completely dependent of the key, bit for bit. However, in the P-array, P15 through P18 do not completely have this effect on the ciphertext (their avalanche effects vary, respectively); any given S-box entry has a small probability of doing so on any single block of ciphertext.

So, to keep this nice avalanche property that Blowfish was built upon, you generally want to XOR, with each 32 bits of the key, P1 through [up to] P14, accordingly; systematically, P1 through P18 would be used. Because diffusion is such a vital property of modern block cipher design theory, you may understand why offsetting this with a larger, 576-bit, key could actually weaken the intended effect. Besides, when you find yourself in key lengths larger than 256 bits, you aren't really sacrificing much with that type of trade-off - especially for a 448-bit key. So, in short, you can use 576-bit keys with Blowfish; it will work. However, 448-bit was a maximum limitation given because of its suitability to diffusion; using anything larger may likely decrease the probability of that taking place. Note that this issue can be addressed by tweaking the key schedule, but that makes it a variation from the original specification, so we'll stick to that, since you are using original source code. (Also, consider possible related-key attacks because of it.)

This is quite confusing, since it's not a systematic impossibility (as the specification does suggest it); it's just a limitation suggested to cope with the design of the algorithm, so unless you understand the reasoning for this limitation, it might not be obvious. Another reason this baffles many is because they don't associate "larger" with "less secure", when indeed, because of the specified semantics of an algorithm, sometimes this is the case; larger parameters may actually aid in cryptanalysis or weaken the properties that security bounds rest upon. If you see implementations that utilize 576-bit keys for Blowfish - be wary. They should at least understand the complications and potential risks involved. Besides, something that would require a threat model involving a key space larger than 2^448 complexity should probably not be using Blowfish in the first place. Oh, and for the record, this is mentioned on Schneier's site, but perhaps in a way that may be rather subtle if you're expecting a "jump-out-and-grab-you" type of answer.
Back to top
View user's profile Send private message Visit poster's website
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Thu Oct 14, 2004 11:21 pm    Post subject: Reply with quote

thanks so much justin,
this is just the answer i was hoping for.
drove me mad thought there is something in the code which i can't follow. and i have to admit i actually did read through the design paper on schneiers webpage you are referring to, but as he does not have your talent to put things in such a clear and understandable way as you i didn't grasp that the particular section was actually answering my prob until i had read YOUR explanation of the phenomena.
now well this must be one of those pieces of "black magic" in cryptography i guess... but not an inability of mine to understand code execution thank god :)
and at least i was a little bit nearing the track (>"either ... 448 bits is the cryptographical, number theoretical security that will not raise if more bits are feeded into the init-cycle")... which is a small step into the right direction but also by far not close enough i readily admit.
and hey sorry for getting somewhat provocative - just couldn't understand why everybody seemed to have me, a completely fresh newbie, put on a kind of ignore list. and no, two days of waiting, and seeing so many other trivial and not so trivial things being answered almost immediately while myself "sitting on the dry", i don't feel that is too impatient.
but however. thanks a lot again, you have pacified my mind A LOT.
greetz, michael


Last edited by michael-b on Fri Oct 15, 2004 9:39 am; edited 1 time in total
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Fri Oct 15, 2004 9:17 am    Post subject: Re: Why is Blowfish limited to a 448-bit key length? Reply with quote

michael-b wrote:


ps: the code is original - taken from schneiers implementation http://www.schneier.com/code/bfsh-sch.zip
pps: schneier himself has in his code the "choking" flaw he mentions under http://www.schneier.com/blowfish-bug.txt (key is signed char in his implementation)... *g*. maybe somebody knows him and could tell him?


The code in it is correct. however there is a code for blowfish I had earlier posted in the link below has a problem.

http://www.security-forums.com/forum/viewtopic.php?t=14756&highlight=blowfish+c+code

It is exactly as taken from bruce schneier's book of applied cryptography.

Code:
/*Initalize S-box without file read */

for(i=0; i<256;i++)
{
   c->S[0][i]=ks0[i];
   c->S[1][i]=ks1[i];
   c->S[2][i]=ks2[i];
   c->S[3][i]=ks3[i];
}

j=0;

for(i=0;i<N+2; i++)
{
   data= 0x00000000;
   
    for(k=0;k<4;++k)
    {
         data=(data<<8) | key[j];
         j=j+1;
         
         if(j>=keybytes)
         {   
              j=0;
         }//end if//
    }//end for//
    c->P[i]=c->P[i] ^ data;
}//end for//



Problem is c->P[i] has not been initialized with the digits of Pi any where in the code. In effect for


Quote:
c->P[i]=c->P[i] ^ data;



what we are doing is c->p[i]= 0x00000000 ^data =data.

This is done when the compiler is smart enough to initilaize the uninitilaized array to zero. Otherwise we are left to the mercy of the compiler. Even then the code is incorrect as we are not xoring the key with the digits of pi.

The correct code link is posted by michael-b and is availabe at
http://www.schneier.com/code/bfsh-sch.zip along with the bug report at
http://www.schneier.com/blowfish-bug.txt


thanks.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Fri Oct 15, 2004 9:51 am    Post subject: Reply with quote

hi datah :)
what still puzzles me about schneiers ref implementation is that he states very firmly "NOTE: There is a bug in some source code implementations of Blowfish. Here are the details. The reference implementation does not have this bug." (http://www.schneier.com/blowfish.html) but the ref implement DOES have this bug. at least it has a "char" for key and although it's compiler dependant whether this is signed or unsigned this is exactly the type of definition leading to the "choking" flaw described in the bug paper. and i had to correct schneiers code insofar as my compilers default is signed and i'd had otherwise run into the security prob associated with the flaw.
why is schneier so convincingly stating that his code does not have the flaw while on the same page his own link to his mentioned ref code DOES have the flaw?
oh and sincerest thanks for you trying to help me out although justin was faster :)
greetz, michael
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Fri Oct 15, 2004 11:36 pm    Post subject: No worries. Reply with quote

michael-b wrote:

and hey sorry for getting somewhat provocative - just couldn't understand why everybody seemed to have me, a completely fresh newbie, put on a kind of ignore list. and no, two days of waiting, and seeing so many other trivial and not so trivial things being answered almost immediately while myself "sitting on the dry", i don't feel that is too impatient.


No worries, just understand that many of us prefer to give the most thorough, yet concise, answer as possible, so we may dwell on how to arrange our wording in our answers; this may take a day or two, depending on the subject matter. Questions do vary in triviality, and are subject to how fresh that subject matter is in our memory, so don't feel ignored if your response is delayed. This delay is affected by many other factors, such as our careers and engagements outside of this forum, which is merely an educational pastime for us all, albeit taken seriously.

datah wrote:

Even then the code is incorrect as we are not xoring the key with the digits of pi.


Aye - the P-array was not initialized, and is listed as errata that applies to all prints of Applied Cryptography, 2nd Edition.

Code:

unsigned long ps[18]={0x243f6a88, 0x85a308d3, 0x13198a2e,
0x03707344, 0xa4093822, 0x299f31d0, 0x082efa98, 0xec4e6c89, 0x452821e6,
0x38d01377, 0xbe5466cf, 0x34e90c6c, 0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5,
0xb5470917, 0x9216d5d9, 0x8979fb1b};
 /* Initialize P array */
 for(i=0;i<18;i++) c->P[i]=ps[i];
Back to top
View user's profile Send private message Visit poster's website
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Sat Oct 16, 2004 12:21 am    Post subject: Reply with quote

hi datah and justin,

sorry for insisting on this point i only think if i paste some code-info it might become more clear what i am up to.

a quote from http://www.schneier.com/blowfish-bug.txt this is the document describing the "choking" flaw.

Code:

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 continues to say -

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;


now this is an ORIGINAL quote from the bug-describing doc taking direct from schneier's website.

next, please consider this ORIGINAL paste of the ref-installation by schneier also taken DIRECTLY and UNCHANGED from his c ref-code http://www.schneier.com/code/bfsh-sch.zip

Code:

short InitializeBlowfish(char key[], short keybytes)
{
   unsigned long  data;

  ... //lots of code ommitted

      j = 0;
      for (i = 0; i < N + 2; ++i) {
        data = 0x00000000;
        for (k = 0; k < 4; ++k) {
          data = (data << 8) | key[j]; //(my comment) CHOKE! see above
          j = j + 1;
          if (j >= keybytes) {
            j = 0;
          }
        }
        P[i] = P[i] ^ data;
      }

  ... //lots of code ommitted
}


please verify for yourself and download the aforementioned docs if you don't trust or believe me in this. but schneiers implement DOES have the bug and i concluded for myself that i have to use the fix described in the choke-doc to work around that.

or am i overseeing something?

greetz, michael
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sat Oct 16, 2004 12:11 pm    Post subject: Re: No worries. Reply with quote

JustinT wrote:


Aye - the P-array was not initialized, and is listed as errata that applies to all prints of Applied Cryptography, 2nd Edition.


thanks for the corrected code. Mine is an old print that didn't figure in the errata.


Michael-B wrote:
Quote:
and no, two days of waiting, and seeing so many other trivial and not so trivial things being answered almost immediately while myself "sitting on the dry", i don't feel that is too impatient


Usually very heavy schedule and more familiar things are easy to look up.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun Oct 17, 2004 2:49 pm    Post subject: Reply with quote

michael-b wrote:

The following fix has been verified to work:

data<<=8;
data|=(unsigned long)key[j]&0xff;

now this is an ORIGINAL quote from the bug-describing doc taking direct from schneier's website.

next, please consider this ORIGINAL paste of the ref-installation by schneier

Code:

short InitializeBlowfish(char key[], short keybytes)
{
   unsigned long  data;

  ... //lots of code ommitted

      j = 0;
      for (i = 0; i < N + 2; ++i) {
        data = 0x00000000;
        for (k = 0; k < 4; ++k) {
          data = (data << 8) | key[j]; //(my comment) CHOKE! see above
          j = j + 1;
          if (j >= keybytes) {
            j = 0;
          }
        }
        P[i] = P[i] ^ data;
      }

  ... //lots of code ommitted
}






... //lots of code ommitted
(3rd line whence) its written.
data = 0x00000000;


That should set data to zero explicity even if data was declared as a signed variable.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Sun Oct 17, 2004 3:06 pm    Post subject: Reply with quote

Hi datah :)
??? Did you really read into the bug-description?
The prob ain't data but key; plus a sign extension (not an init failure).
But thanks anyhow,
Greetz Michael

PS I am so ABSOLUTELY positive that Schneier's code contains this bug... I wouldn't even care to ask here about that because it is so blatantly obvious a schoolboy could see it. The only reason why I am so much insisting is that... well it's Schneier :)))
And, this has SOME implications, if Schneier distributes erroneous code, you see. If HIS code has the error I won't trust any blowfish implement no more if I can't review the code. How many people would take the effort and check a code of the greatest cryptographical guru, that's why. Most would probably just copy it unchanged, trusting completely in his authority. And that's why I feel this thing is so important, and that's why I seek confirmation here.
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun Oct 17, 2004 3:48 pm    Post subject: Reply with quote

Quote:
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.



That looks to be a compiler specific problem. A signed char is 8 bit(usually) and 0x80 fits into 8 bits. The higher bits should be masked before being ORed. According to the code this what it should precisely do. You can check what result your compiler gives for the code you posted and verify it.

In the bug report it is also written

Quote:
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.


It is pretty much a compiler issue.

Quote:
And, this has SOME implications, if Schneier distributes erroneous code, you see. If HIS code has the error I won't trust any blowfish implement no more if I can't review the code.


The code may work correctly on some compilers. this is why the programmer should use test vectors to verify the correctness of the algorithm. You can write to Mr. Schneier requesting him to change it so that it works in all cases.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
michael-b
Just Arrived
Just Arrived


Joined: 12 Oct 2004
Posts: 0
Location: non-english

Offline

PostPosted: Sun Oct 17, 2004 4:24 pm    Post subject: Reply with quote

Thanks data,

then that's what I should probably do (write to Mr. Schneier). You see he states on his website "The reference implementation does NOT have this bug", and that's what makes it so dangerous... but maybe there is some misunderstanding of mine evolved also. Because there is another download there called bfsh-ref.zip. This file does not include code, only definition primitives... and the definition for bfinit of THAT -ref.zip actually declares key to be unsigned char (which is one way to avoid the prob). But, if someone wants/needs the source, he'll download bfsh-sch.zip, since only there is source within... so you see, maybe Schneier is absolutely correct stating that his reference does not include the bug, but that is very misleading, since everybody who is interested in source will HAVE to download the other file which DOES contain the bug.

And as you put it that this is "mainly a compiler issue", I wouldn't agree with that really. First the sign extension is pretty much standard this way (as described in the bug doc, that is) in today's compilers and what second you still seem to oversee is that the masking op /edit: is part of the fix, not the original source, or did I get you wrong on that?

Also the bug IS a very serious security issue if you read into the bug doc, making Blowfish a very easy crackable cipher... and yes you are right every responsible programmer should use test vectors etc., I do, but how do I know someone else did if I can't review the code and have no other means of testing, for example with (proper - see below) test vectors?

And... (you really did not read into the bug-doc)... standard test vectors DO NOT SHOW the bug. Which is why it is such an evil one, aside the extreme security loss.

150 products use Blowfish so far, as counterpane.org states, and many of them don't have a verification scheme at all. I recall a Secure Shell for example, implementing Blowfish as an optional cipher to choose from among others. Now with that (commercial) product I would choose Blowfish never more since I can't review the code or test with selected test vectors. And this is the point. The bug thing coming directly from Schneier does create a general distrust in Blowfish for me. Could I make myself understood? (sorry I'm no native English speaker so I am not always sure about my wording)

Also I did for fun a search on the internet for blowfish source codes. I found with a very loose effort 3 sites offering the wrong code, quite obviously a copy and paste from Schneier. One of them even was an university. And there must be thousands of locations with that error more, I guess.

ok. You think if I post to Schneier he'll read it? He must be getting thousands of mails daily and I of course never had any contact with him (apart from reading his brilliant and much beloved books :)) Don't you or someone here know someone who knows him, that would be a more effective way maybe? But of course I can try to mail the info@-account and land among 10.000 spam-mails hehe.

Greetz & thanks a lot for your effort, Michael
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Mon Oct 18, 2004 10:39 am    Post subject: Reply with quote

hi there,

I looked it at the bug report 'more carefully'.I am in total agreement with you.

michael-b wrote:
Thanks data,

then that's what I should probably do (write to Mr. Schneier). You see he states on his website "The reference implementation does NOT have this bug", and that's what makes it so dangerous... but maybe there is some misunderstanding of mine evolved also. Because there is another download there called bfsh-ref.zip. This file does not include code, only definition primitives... and the definition for bfinit of THAT -ref.zip actually declares key to be unsigned char (which is one way to avoid the prob). But, if someone wants/needs the source, he'll download bfsh-sch.zip, since only there is source within... so you see, maybe Schneier is absolutely correct stating that his reference does not include the bug, but that is very misleading, since everybody who is interested in source will HAVE to download the other file which DOES contain the bug.


Yes, you need to write to Mr.Schneier and you also need to put it up on cypherpunks or sci.crypt.

Quote:

And as you put it that this is "mainly a compiler issue", I wouldn't agree with that really. First the sign extension is pretty much standard this way (as described in the bug doc, that is) in today's compilers and what second you still seem to oversee is that the masking op /edit: is part of the fix, not the original source, or did I get you wrong on that?


You are right on both counts. Firstly, it doesn't look like a compiler issue(Shall try to explain that below). Secondly, it is not part of the original source code.


Michael-B said
Quote:

Also the bug IS a very serious security issue if you read into the bug doc, making Blowfish a very easy crackable cipher... and yes you are right every responsible programmer should use test vectors etc., I do, but how do I know someone else did if I can't review the code and have no other means of testing, for example with (proper - see below) test vectors?

And... (you really did not read into the bug-doc)... standard test vectors DO NOT SHOW the bug. Which is why it is such an evil one, aside the extreme security loss.



You are right again.

Bug-fix-document-says
Quote:
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.



We also can't say for sure if Mr.Schneier used that code in his website to make the test vectors in the first place.

Quote:

150 products use Blowfish so far, as counterpane.org states, and many of them don't have a verification scheme at all. I recall a Secure Shell for example, implementing Blowfish as an optional cipher to choose from among others. Now with that (commercial) product I would choose Blowfish never more since I can't review the code or test with selected test vectors. And this is the point. The bug thing coming directly from Schneier does create a general distrust in Blowfish for me. Could I make myself understood? (sorry I'm no native English speaker so I am not always sure about my wording)



I am more than glad that you share this with us. I heard that Blowfish was to be integrated as an optional cipher in the linux kernel. Here is the link
http://rw4.cs.uni-sb.de/~theiling/blowfish.html

In the website, the link points to Mr.Schneier's code that you posted. This makes it a serious problem. The website mentions a patch but the url doesnot open and I couldnot verify it.


Quote:

ok. You think if I post to Schneier he'll read it? He must be getting thousands of mails daily and I of course never had any contact with him (apart from reading his brilliant and much beloved books Smile) Don't you or someone here know someone who knows him, that would be a more effective way maybe?


I can post on your behalf on the cypher-punks@al-qaeda.net node, if you wish. Its a good way for peer review.

I think he replies to most of his mail on 15th of every month, when cryptogram comes out. Otherwise, you can freely subscribe to any of the cypherpunks nodes and post it there.


bug-report-says
Quote:
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.


Lets analyze this closely.

We note that the 'union' keyword is no where used in the C code in Mr.Schneier's web site. The definitions in the code are exactly
Code:


unsigned long data;
char key[];



The code also has the step
Code:

data=(data<<8) | key[j];


An automatic type conversion is performed from signed char to unsigned long, before the two operators are ORed with one another. I.e. signed char is type casted to unsigned long

Assume
Code:
key[j]=0x80;  --->(1)


On an Intel 80x86 architecture with 32 bit registers, the type conversions from byte to word and word to double word, with out changing the value of the variable being converted is as follows.


Code:

Byte to word conversion
----------------------------

Since key[j] is a signed character, it is a negative byte with (MS bit=1). The MS byte of the word is made 0xff.

In our case, for (1)


        before        after
AH      0x32         0xff       (AH:Before holds garbage information)
AL       0x80        0x80

Therefore, AX=AH_AL=0xff80 with 'FF' being the sign extension of '80'.
This procedure is done using the 'Convert Byte to Word',(CBW) instruction.

Word to double word conversion
-------------------------------------

We now have AX=0xff80. Similarly, we use the 'Convert Word to Double Word',(CWD) instruction.

        before       after
DX    0x1222      0xffff    (DX:Before holds garbage information)
AL     0xff80       0xff80


The register pair DX_AX=0xfffff80. When a type cast is performed on a signed character, it is first converted to a word and then to a double word in the manner mentioned above. This makes me convinced that the 'union' is not responsible for the problem as mentioned in the bug report. It is reasonable to assume this(byte to word and word to double word) is what compilers internally call for typecast and will always give rise to the same bug in the code always.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Goto page 1, 2  Next
Page 1 of 2


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register