Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Schneier says:

Fewer and smaller S-boxes. It may be possible to reduce the number of S-boxes from four to one. Additionally, it may be possible to overlap entries in a single S-box: entry 0 would consist of bytes 0 through 3, entry 1 would consist of bytes 1 through 4, etc. The former simplification would reduce the memory requirements for the four S-boxes from 4096 bytes to 1024 bytes, the latter would reduce the requirements for a single S-box from 1024 bytes to 259 bytes. Additional steps may be required to eliminate the symmetries that these simplifications would introduce. Additionally, four different 10- or 12-bit indexes into a single large S-box could be used instead of the current series of S-boxes.

Just theoretically, how would using same s-box instead of 4 different affect the security of Blowfish (considering no other change is made)?

By "eliminate the symmetries", he probably means rotations? Is this really required, since round keys already break the symmetries?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Because I didn't get any answer, I did some experments with Blowfish's F function and here are my observations:

Because Blowfish's F function is not bijective, on average only every second value is returned and therefore different input can output same value (F(x) = F(y)). By reducing number of S-boxes this non-bijectivity becomes even worse. About 8 to 32 of inputs will result in F(x) = 0. But problem is worse, because addition hides problem; With F() with XORs instead of additions about 2^18 inputs will output 0. This happens, because (S(X) xor S(X) xor S(X) xor S(X)) or (S(X) xor S(X) xor S(Y) xor S(Y)) ... is always 0. So addition breaks symmetries a bit.

I have also found comment by David Wagner on question about strength of Blowfish with broken F (((S_1[a] + S_1[a]) ^ S_1[a]) + S_1[a]). He overlooked that also the same input byte is used. So he was answering my question.

For what it's worth (which is not very much), I don't immediately see any plausible way to exploit this on the full Blowfish, though I haven't spent any serious amount of time thinking about this. 16 rounds, with key-dependent S-boxes, forgives many sins.

https://groups.google.com/forum/#!topic/sci.crypt/21SwIdSqOo8

Considering the S-box is unknown, addition and 16 rounds I think it should be fine, but I don't think it's a good idea.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.