2
$\begingroup$

I'm having some trouble understanding the Blowfish encryption algorithm. From the Wikipedia article...

The secret key is then, byte by byte, cycling the key if necessary, XORed with all the P-entries in order

Can someone explain this in more detail? For example, the first few P entries are 0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344,...

Supposing the secret key is abcd, how would I implement this part of the algorithm?

$\endgroup$

migrated from security.stackexchange.com Apr 13 '15 at 11:58

This question came from our site for information security professionals.

  • $\begingroup$ Definitely too many commas in that sentence... $\endgroup$ – hft Apr 13 '15 at 3:00
  • $\begingroup$ dude let me tell a thing or two. First find a source code for blowfish.h. i got my header file from defuse.ca/blowfish.htm blowfish.h is in c++. it contains a lot of data. not sure if it will make blowish algorithm any clearer but it provides some useful tips, you can modify the code itself ofc. i am not sure how secure this implementation is but atleast it does the job in terms of encrypting and decrypting string. $\endgroup$ – user32612 Mar 19 '16 at 1:56
  • $\begingroup$ If you think the code behind the link answers the question, please at least quote that part in the answer. Link-only answers can become useless if the link breaks. (Also, it would be preferable if you could answer in words rather than code.) $\endgroup$ – otus Mar 19 '16 at 8:25
5
$\begingroup$

The quoted passage of the Wikipedia article is wrong does not at first reading seem to match Blowfish as in Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in proceedings of the first FSE conference, held Dec. 1993) which for this same operation reads:

XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

In C++, if P and key are arrays of 32-bit words, and keylen (from 1 to 14) is the key size in 32-bit increments, this can be implemented as shown in the wikipedia article:

for (int i=0 ; i<18 ; ++i)
   P[i] ^= key[i % keylen];

Customarily conversion of key bytes to the array key, and constants for initialization of P, is big-endian (as traditional in cryptography for many things such as DES, RSA, SHA, AES, but not MD5).

Many actual implementations of Blowfish accept keys with size any multiple of 8-bit, and there's nothing in Bruce Schneier's description to forbid that. To cover this, if P is an array of 32-bit words, key is an array of 8-bit bytes, and keylen is the key size (from 4 to 56) in 8-bit increments, the loop can become, on an big endian machine:

for (int i=0 ; i<72; ++i)
   ((uint8_t*)P)[i] ^= key[i % keylen];

or, to keep the code endian-neutral:

for (unsigned i=0 ; i<72; ++i)
   P[i>>2] ^= ((uint32_t)key[i % keylen])<<((3&~i)<<3);

Note: the shift count computed as (3&~i)<<3 is 24, 16, 8, 0, 24, 16, 8, 0, 24.. when i is 0, 1, 2, 3, 4, 5, 6, 7, 8..

Note: while Blowfish's definition states a minimum key size of 32 bits, some implementations lower that to 8 bits, including the one that was used for these test vectors of Blowfish with variable key length (also available as a C header). Further, some implementations (especially of Blowfish as used in Bcrypt) allow up to 576-bit keys (72 bytes), rather than 448-bit (56 bytes).


Example 1: if the key is the string abcd in ASCII, the array key (viewed as a 32-bit array) is the single element 0x61626364; thus after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x61626364 that is 0xE4C16BB7,..
P[17] is 0x8979FB1B^0x61626364 that is 0xE81B987F.

Example 2: if the key is the string abcdJKL in ASCII, after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x4A4B4C61 that is 0xCFE844B2,..
P[17] is 0x8979FB1B^0x4B4C6162 that is 0xC2359A79.

Note: there are further transformations of P but they are rather unambiguous; refer to either of the articles.


Final Caution: some Blowfish implementations (especially those used in Bcrypt) are known to vary in how they convert text to bytes before applying the above transformation of key to P; some bugs have even crept there, for example

Versions of jBCrypt before 0.3 suffered from a bug related to character encoding that substantially reduced the entropy of hashed passwords containing non US-ASCII characters. An incorrect encoding step transparently replaced such characters by ? prior to hashing. In the worst case of a password consisting solely of non-US-ASCII characters, this would cause its hash to be equivalent to all other such passwords of the same length.

Notice that if "of the same length" is necessary in this quotation, then some length, padding or terminating character must have been included in the key converted to bytes (otherwise all passwords consisting solely of non-US-ASCII characters would have been equivalent, regardless of length).

$\endgroup$
  • $\begingroup$ Probably the best answer I've gotten in any stackexchange site. The examples really help clarify things for me. $\endgroup$ – Ben Apr 13 '15 at 16:43
  • $\begingroup$ @Ben: unfortunately this answer is not enough to fully cover the variations found in the field; see new Final Caution! $\endgroup$ – fgrieu Apr 13 '15 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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