I'm building a Blowfish cipher algorithm in Java. I used these test vectors to see if it works and I found out worst possible thing - it works for some inputs and not for others.
I used Blowfish paper as a guide to create my implementation. Bellow are relevant parts of it.
public class Blowfish {
// Binary Digits of Pi
// ...
private static final int N = 16;
private final long S[][] = new long[4][256];
private final long P[] = new long[N + 2];
Bruce says:
(1) Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of pi (less the initial 3)
public void keyExpansion(String key) {
System.arraycopy(p, 0, P, 0, N + 2);
for (int i = 0; i < 4; i++) {
System.arraycopy(s[i], 0, S[i], 0, 256);
}
I realize this is not really readable, but lowercase p[] and s[][] contain fixed values (hex digits of pi) and uppercase P[] and S[][] are attributes of a Blowfish object, which are going to change.
Bruce says:
(2) 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 (int i = 0; i < N + 2; i++) {
int begin = (i * 8) % key.length();
int end = ((i + 1) * 8) % key.length();
String keySubstring;
if (begin < end) {
keySubstring = key.substring(begin, end);
} else {
keySubstring = key.substring(begin) + key.substring(0, end);
}
long keyChunk = Long.parseLong(keySubstring, 16);
P[i] ^= keyChunk;
}
Since key is varied length (up to 56 bytes), I figured easiest way to pass it is as a String. Perhaps I should've used BigInteger?
Bruce says:
(3) Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2).
(4) Replace P1 and P2 with the output of step (3).
(5) Encrypt the output of step (3) using the Blowfish algorithm with the modified subkeys.
(6) Replace P3 and P4 with the output of step (5).
(7) Continue the process, replacing all entries of the P- array, and then all four S-boxes in order, with the output of the continuously-changing Blowfish algorithm.
long e = 0;
for (int i = 0; i < N + 2; i += 2) {
e = encrypt(e);
long eL = trim(e >>> 32);
long eR = trim(e);
P[i] = eL;
P[i + 1] = eR;
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 256; j += 2) {
e = encrypt(e);
long eL = trim(e >>> 32);
long eR = trim(e);
S[i][j] = eL;
S[i][j + 1] = eR;
}
}
This is a good time as any to mention my helper function trim which removes higher 32 bits.
private static long trim(long value) {
return value & 0xFFFFFFFFL;
}
Bruce says:
Blowfish is a Feistel network consisting of 16 rounds. The input is a 64-bit data element, x.
Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
Next i
Swap xL and xR (Undo the last swap.)
xR = xR XOR P17
xL = xL XOR P18
Recombine xL and xR
public long encrypt(long plaintext) {
long xL = trim(plaintext >>> 32);
long xR = trim(plaintext);
for (int i = 0; i < N; i++) {
xL = xL ^ P[i];
xR = F(xL) ^ xR;
//swap
xL = xL + xR;
xR = xL - xR;
xL = xL - xR;
}
//swap
xL = xL + xR;
xR = xL - xR;
xL = xL - xR;
//final step
xR = xR ^ P[N];
xL = xL ^ P[N + 1];
return (xL << 32) | xR;
}
}
I simply ran this code against aforementioned test vectors, like so:
public void testBlowfish() {
long key[] = {
...
};
long clear[] = {
...
};
long cipher[] = {
...
};
Blowfish b = new Blowfish();
for (int i = 0; i < 34; i++) {
b.keyExpansion(Long.toHexString(key[i]));
long result = b.encrypt(clear[i]);
if (result == cipher[i]) {
System.out.println("Test " + i + " passed!");
} else {
System.out.println("Test " + i + " failed: ");
System.out.println("\tKey:\t" + Long.toHexString(key[i]));
System.out.println("\tClear:\t" + Long.toHexString(clear[i]));
System.out.println("\tCipher:\t" + Long.toHexString(cipher[i]));
System.out.println("\tResult:\t" + Long.toHexString(result));
}
}
}
And here are test results:
Test 0 passed!
Test 1 passed!
Test 2 passed!
Test 3 passed!
Test 4 failed:
Key: 123456789abcdef
Clear: 1111111111111111
Cipher: 61f9c3802281b096
Result: 65a2dfe88702a6bf
Test 5 passed!
Test 6 passed!
Test 7 passed!
Test 8 passed!
Test 9 failed:
Key: 131d9619dc1376e
Clear: 5cd54ca83def57da
Cipher: b1b8cc0b250f09a0
Result: fbd7e706e563d21a
Test 10 failed:
Key: 7a1133e4a0b2686
Clear: 248d43806f67172
Cipher: 1730e5778bea1da4
Result: 7d11a2563bbf76f1
Test 11 passed!
Test 12 failed:
Key: 4b915ba43feb5b6
Clear: 42fd443059577fa2
Cipher: 353882b109ce8f1a
Result: d747d42ef2bc89c0
Test 13 failed:
Key: 113b970fd34f2ce
Clear: 59b5e0851cf143a
Cipher: 48f4d0884c379918
Result: c559acf605825008
Test 14 failed:
Key: 170f175468fb5e6
Clear: 756d8e0774761d2
Cipher: 432193b78951fc98
Result: 8761d08e81a796d
Test 15 passed!
Test 16 failed:
Key: 7a7137045da2a16
Clear: 3bdd119049372802
Cipher: 2eedda93ffd39c79
Result: db47a054a5a0d496
Test 17 failed:
Key: 4689104c2fd3b2f
Clear: 26955f6835af609a
Cipher: d887e0393c2da6e3
Result: 40f96e5f9f3affe1
Test 18 passed!
Test 19 passed!
Test 20 passed!
Test 21 failed:
Key: 25816164629b007
Clear: 480d39006ee762f2
Cipher: 7555ae39f59b87bd
Result: a6cb030922383650
Test 22 passed!
Test 23 passed!
Test 24 passed!
Test 25 failed:
Key: 18310dc409b26d6
Clear: 1d9d5c5018f728c2
Cipher: d1abb290658bc778
Result: d45634df2f8eb002
Test 26 passed!
Test 27 failed:
Key: 101010101010101
Clear: 123456789abcdef
Cipher: fa34ec4847b268b2
Result: 30ce63f436ff5475
Test 28 passed!
Test 29 passed!
Test 30 passed!
Test 31 passed!
Test 32 failed:
Key: 123456789abcdef
Clear: 0
Cipher: 245946885754369a
Result: 291c4bd096af70e5
Test 33 passed!
As I said, some inputs work and some don't. And I can't figure out why, it seems arbitrary to me, and I refuse to live in the world where computers can make arbitrary decisions. In other words, where is the error?
As suggested, I was losing leading zeros in conversions. Implementation was fine, but in test the line
b.keyExpansion(Long.toHexString(key[i]));
was causing errors. Replacing it with
b.keyExpansion(String.format("%016x", key[i]));
worked.
Seems obvious now, since each failed test at least one had leading zero.
I assumed that every key will be longer than 8 bytes, for some reason. To get keyExpansion to work for short keys, I changed reading from key like so:
for (int i = 0; i < N + 2; i++) {
StringBuilder keySubstring = new StringBuilder();
for (int j = 0; j < 8; j++) {
int index = (i * 8 + j) % key.length();
keySubstring.append(key.charAt(index));
}
long keyChunk = Long.parseLong(keySubstring.toString(), 16);
P[i] ^= keyChunk;
}