Generating Blowfish Encryption Subcategories
Ok so I am doing a little blowfish implementation in PHP as a programming exercise for myself and know better what the encryption method is. I ended up with a bunch of functions that work as I can encrypt the data and decrypt it again, but the test vectors I found disagree with my encrypted values ββ... Since the encoding / decoding seems to work, I assume that the error lies in my setting up the function of applying the secret key to the array P and S-sides coming to a different set of P values ββand S-box values, so the encoded values ββare different. Can anyone find where my logic is going against?
For the test case of key 0x0000000000000000 and text input 0x0000000000000000, the first step would be to XOR the key with the array P, but with the key of all zeros, which will cause the array P to remain unchanged, so it will still have the hex values ββpi that it starts with. The 64-byte text string (0x0000000000000000) is then encoded using the current array of P and S-boxes, and the result is split to replace P1 and P2. Then the same result is re-encoded (using the new values ββof P1 and P2) to get another output that is used to replace P3 and P4. This continues until all P and S-box values ββhave been changed. By doing this process, I get the following (original values ββon the left, value after propagating through the secret key process on the right):
P1: 243f6a88 β 99f2ff37
P2: 85a308d3 β 9ce5cb96
P3: 13198a2e β d8bf7d9a
P4: 03707344 β eba1db37
P5: a4093822 β 5954010a
P6: 299f31d0 β 2b121658
P7: 082efa98 β e7a5b7ed
P8: ec4e6c89 β 21a6717f
P9: 452821e6 β b2bb1bf8
P10: 38d01377 β 937f0244
P11: be5466cf β e111a3da
P12: 34e90c6c β 67170ab6
P13: c0ac29b7 β 5d1db61b
P14: c97c50dd β cdf63d96
P15: 3f84d5b5 β c4935141
P16: b5470917 β ad859868
P17: 9216d5d9 β 0ca32381
P18: 8979fb1b β 50964a67
S1,0: d1310ba6 β a96eceb6
S1,1: 98dfb5ac β 3480051c
S1,2: 2ffd72db β 8d315fa7
S1,3: d01adfb7 β 936c585a
S1,4: b8e1afed β cd9cd593
...
S4,251: c208e69f β cc091e06
S4,252: b74e6132 β 2e7b8ad3
S4,253: ce77e25b β dc3d8ec5
S4,254: 578fdfe3 β c52e90ab
S4,255: 3ac372e6 β e1866c06
When I encode 0x0000000000000000 with this dataset, I get 0x3b8a9fa06e840430, but in the test case, I should get 0x4ef997456198dd78.
Can you see where I go wrong?
EDIT; Detailed encryption after fixing 32-bit solid issue Here's how I interpret (and I think my program interprets) the way blowfish encryption happens. Given a bunch of P-arrays and S-boxes, initialized with hex values ββpi and a zero-keyed XORed array P (so it's still the same), I do the following:
0x0000000000000000 the input is divided by two, the left half becomes L0 and the right half becomes R0:
L0 = 0x00000000
R0 = 0x00000000
R1 = L0 ^ P1 = 0x00000000 ^ 0x243f6a88 = 0x243f6a88
L1 = F(R1) ^ R0 = F(0x243f6a88) ^ 0x00000000 = 0xdb2f9c4e ^ 0x00000000 = 0xdb2f9c4e
R2 = L1 ^ P2 = 0xdb2f9c4e ^ 0x85a308d3 = 0x5e8c949d
L2 = F(R2) ^ R1 = F(0x5e8c949d) ^ 0x243f6a88 = 0x33002cc0 ^ 0x243f6a88 = 0x173f4648
R3 = L2 ^ P3 = 0x173f4648 ^ 0x13198a2e = 0x426cc66
L3 = F(R3) ^ R2 = F(0x426cc66) ^ 0x5e8c949d = 0xd8a68913 ^ 0x5e8c949d = 0x862a1d8e
....
R16 = L15 ^ P16 = 0xf5e1fd40 ^ 0xb5470917 = 0x40a6f457
L16 = F(R16) ^ R15 = F(0x40a6f457) ^ 0xea27e3cc = 0x66509b85 ^ 0xea27e3cc = 0x8c777849
Now untwist and apply final P values
R_final = L16 ^ P17 = 0x8c777849 ^ 0x9216d5d9 = 0x1e61ad90
L_final = R16 ^ P18 = 0x40a6f457 ^ 0x8979fb1b = 0xc9df0f4c
Final ciphered output: 0xc9df0f4c1e61ad90, should be 0x706d9fcc1792d23a...
source to share
There is something wrong with your encryption function. These should be the results of initializing a P-array with the all-zeroes key (my P array is zero-based, but that shouldn't change):
P0: 243f6a88 => 706d9fcc
P1: 85a308d3 => 1792d23a
P2: 13198a2e => 2db9d714
P3: 03707344 => 966e1439
P4: a4093822 => ac21a76d
P5: 299f31d0 => 8324e988
P6: 082efa98 => ac0dc9dd
P7: ec4e6c89 => 2c38f6b3
P8: 452821e6 => 70619520
P9: 38d01377 => fa23ecbe
P10: be5466cf => 17b2f676
P11: 34e90c6c => eba13a04
P12: c0ac29b7 => 8b949e61
P13: c97c50dd => 7a147caf
P14: 3f84d5b5 => 56ccc6b6
P15: b5470917 => 4461b24d
P16: 9216d5d9 => 7361e6a1
P17: 8979fb1b => 196a7c43
If you need some help tracking down the error, you will need to post how the algorithm progresses as it goes through the rounds of the first encryption step in initialization, where block zero is encrypted by the original P and S boxes.
Appendix 1:
Your calculation will be erratic at F(0x5e8c949d)
- it should be 0x33002cc0
. However, your first one is F()
correct, so I'm guessing the problem occurs when your function additions F()
overflow instead of packaging correctly. This question is about PHP integer overflow, and has a solution in the accepted answer that should work for you (and, in fact, the calculation it does is exactly the same as the Blowfish function F()
, which I assume is not a coincidence;)
Here's how the first two calculations go F()
:
F(0x243f6a88) = byte0 = 0x24, S0(byte0) = 0xe65525f3 byte1 = 0x3f, S1(byte1) = 0x183eb331 byte2 = 0x6a, S2(byte2) = 0x647d0862 byte3 = 0x88, S3(byte3) = 0x4040cb08 ((0xe65525f3 + 0x183eb331) ^ 0x647d0862) + 0x4040cb08 = 0xdb2f9c4e F(0x5e8c949d) = byte0 = 0x5e, S0(byte0) = 0x7d84a5c3 byte1 = 0x8c, S1(byte1) = 0xeecea50f byte2 = 0x94, S2(byte2) = 0x1a6b1018 byte3 = 0x9d, S3(byte3) = 0xbcc7d1f6 ((0x7d84a5c3 + 0xeecea50f) ^ 0x1a6b1018) + 0xbcc7d1f6 = 0x33002cc0
Appendix 2:
There F()
is still something amiss in your implementation - this is how this third call should work:
F(0x0426cc66) = byte0 = 0x04, S0(byte0) = 0xb8e1afed byte1 = 0x26, S1(byte1) = 0x8e7d44ec byte2 = 0xcc, S2(byte2) = 0x1ab93d1d byte3 = 0x66, S3(byte3) = 0x5121ce64 ((0xb8e1afed + 0x8e7d44ec) ^ 0x1ab93d1d) + 0x5121ce64 = 0xaf099828
source to share