Blowfish encryption sub-key generation

Question

Okay, so I'm doing a little blowfish implementation in PHP as a programming exercise for myself, and to get to know that encryption method better. I arrived at a set of functions that work, in that I can encrypt data and decrypt it again, but the test vectors I found don't agree with my encrypted values... Since the encode/decode seems to work, I'm guessing the error is in my function's setup of applying the secret key to the P array and S-boxes, arriving at a different set of P values and S-box values, so the encoded values are different. Can someone find where my logic is going awry?

For the test case of a key of 0x0000000000000000 and a text input of 0x0000000000000000, the first step is to XOR the key with the P array, but with a key of all zeroes, that will result in the P array being unchanged, so will still have the hex values of pi that it starts with. Then a 64-byte text string (0x0000000000000000) is encoded using the current P array and S-boxes, and the result gets split to replace P1 and P2. Then that same output is encoded again (using the new P1 and P2 values) to get another output, which is used to replace P3 and P4. This continues until all the P values are changed, and the S-boxes. Doing that 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 that data set, I get 0x3b8a9fa06e840430, but the test case says I should get 0x4ef997456198dd78.

Can you see where I'm going awry?

EDIT; Detailed enciphering, after fixing 32-bit integer issue Here's how I interpret (and I think my program is interpreting) the way that the blowfish enciphering happens. Given a P array and S-box set initialized with the hex values of pi and the P array XORed with a null key (so it's still the same), I do the following:

0x0000000000000000 input gets split into 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...

Answer 1

There's something wrong with your encrypt function. These should be the init P-array results with an all-zeroes key (my P array is zero-based but that shouldn't make a difference):

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 want some help tracking the bug down, you'll have to post how the algorithm progresses as it goes through the rounds of the first enciphering step in the initialisation, where the zero block is enciphered with the initial P and S boxes.

Addendum 1:

Your calculation is going awry at F(0x5e8c949d) - this should be 0x33002cc0. Your first F() is correct, though - so I imagine the problem is occuring when your additions in the F() function overflow instead of wrapping properly. This question is about PHP integer overflow, and has a solution in the accepted answer which should work for you (and in fact, the calculation he is doing is exactly the same as the Blowfish F() function, which I assume is not a coincidence ;)

Here is how the first two F() calculations should go:

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

Addendum 2:

There's still something awry with your implementation of F() - here's how that third invocation should run:

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