# Bobcat hash, trying to find a 48-bit hash collision for x

I am trying to find a collision with the Bobcat hash of the 48-bit hash. I am a beginner coder so please point out any flaws in my modification of the bobcat program. It does find a truncated 12-bit collision of the first 12 bits. Now it has been running for 2 days trying to find a 48-bit collision with no avail.

I added a permutate function to randomize the message array x. The only code I added is in the main.. while loop and a few other stuff.

Is there a problem with my code that makes it unable to find a collision?

note: I also did this in C with the same style.. used srand(x[i]+1); x[i] = rand() % 65535; in the permutation Any help with a shortcut would be greatly appreciated!

Here is the java code:

public class Bobcat1 {
//
// 2 S-boxes, each mapping 4 bits to 16 bits
//
int[][] sbox;

public Bobcat1() {
sbox = new int[][] {
{ 0xd131, 0x0ba6, 0x98df, 0xb5ac, 0x2ffd, 0x72db, 0xd01a,
0xdfb7, 0xb8e1, 0xafed, 0x6a26, 0x7e96, 0xba7c, 0x9045,
0xf12c, 0x7f99 },
{ 0x24a1, 0x9947, 0xb391, 0x6cf7, 0x0801, 0xf2e2, 0x858e,
0xfc16, 0x6369, 0x20d8, 0x7157, 0x4e69, 0xa458, 0xfea3,
0xf493, 0x3d7e } };
}//

// save the abc values at start of F_m
// (needed for feedforward)
//

void abcSave(int[] abc, int[] old) {
old[0] = abc[0];
old[1] = abc[1];
old[2] = abc[2];

// printf("old = 0x%04x%04x%04x\n\n", old[0], old[1], old[2]);
}// end abcSave

//
// inner round functions f_{m,i}
//
void f(int[] abc, int zero, int one, int two, int x, int m) {
int aa, bb, cc;

aa = abc[zero];
bb = abc[one];
cc = abc[two];

cc = (cc ^ x) & 0xffff;
aa = (aa - (sbox[0][cc & 0xf] ^ sbox[1][(cc >> 8) & 0xf])) & 0xffff;
bb = (bb + (sbox[1][(cc >> 4) & 0xf] ^ sbox[0][(cc >> 12) & 0xf])) & 0xffff;
bb = (bb * m) & 0xffff;

abc[zero] = aa;
abc[one] = bb;
abc[two] = cc;

}// end f

//
// outer round functions F_m
//
void F(int[] abc, int m, int[] x) {
f(abc, 0, 1, 2, x[0], m);// a,b,c
f(abc, 1, 2, 0, x[1], m);// b,c,a
f(abc, 2, 0, 1, x[2], m);// c,a,b
f(abc, 0, 1, 2, x[3], m);// a,b,c
f(abc, 1, 2, 0, x[4], m);// b,c,a
f(abc, 2, 0, 1, x[5], m);// c,a,b
f(abc, 0, 1, 2, x[6], m);// a,b,c
f(abc, 1, 2, 0, x[7], m);// b,c,a

}// end F

//
// "key" schedule
//
void keySchedule(int[] x) {
x[0] = (x[0] - (x[7] ^ 0xa5a5a5a5)) & 0xffff;
x[1] = (x[1] ^ x[0]) & 0xffff;
x[2] = (x[2] + x[1]) & 0xffff;
x[3] = (x[3] - (x[2] ^ ((~x[1]) << 5))) & 0xffff;
x[4] = (x[4] ^ x[3]) & 0xffff;
x[5] = (x[5] + x[4]) & 0xffff;
x[6] = (x[6] - (x[5] ^ ((~x[4]) >> 6))) & 0xffff;
x[7] = (x[7] ^ x[6]) & 0xffff;
x[0] = (x[0] + x[7]) & 0xffff;
x[1] = (x[1] - (x[0] ^ ((~x[7]) << 5))) & 0xffff;
x[2] = (x[2] ^ x[1]) & 0xffff;
x[3] = (x[3] + x[2]) & 0xffff;
x[4] = (x[4] - (x[3] ^ ((~x[2]) >> 6))) & 0xffff;
x[5] = (x[5] ^ x[4]) & 0xffff;
x[6] = (x[6] + x[5]) & 0xffff;
x[7] = (x[7] - (x[6] ^ 0x235689bd)) & 0xffff;

}// end keySchedule

//
// add in the old values to produce new a,b,c
//
void feedforward(int[] abc, int[] old) {
abc[0] = (abc[0] ^ old[0]) & 0xffff;
abc[1] = (abc[1] - old[1]) & 0xffff;
abc[2] = (abc[2] + old[2]) & 0xffff;

}// end feedforward

//
// compression function (one outer round)
//
void bobcat(int[] abc, int[] x) {
int[] old = new int[3];

// printf("abc = 0x%04x%04x%04x\n\n", abc[0], abc[1], abc[2]);
abcSave(abc, old);
F(abc, 5, x);
keySchedule(x);
F(abc, 7, x);
keySchedule(x);
F(abc, 9, x);
feedforward(abc, old);

}// end bobcat

public static void main(String[] args) {
// len == number of 128-bit message blocks (128 = 8*16)
// x[i] contains the message, in 16-bit words
// size of x[] array must be a multiple of 8
// if message not a multiple of 8, pad with 0's
Bobcat1 bob = new Bobcat1();
int len;
int[] abc = new int[3];

// ********************************************************************
// ********************************************************************
// ********************************************************************
// 2 blocks (16 words)
// Bobcat hash = 0x2bce98fa6186
len = 2;// number of 128-bit blocks
int[] x = { 0x5920, 0xc7cc, 0x6234, 0xb111, 0x3090, 0x8ab7, 0xf373,
0x46dd, 0x35d3, 0xc06e, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
0x0000 };

int[] orig = x;
// initial constants a,b,c
abc[0] = 0xface;
abc[1] = 0xe961;
abc[2] = 0x041d;
String a = String.format("0x%04X", abc[0])
+ String.format("%04X", abc[1]) + String.format("%04X", abc[2]);
System.out.println("Original abc 48-bit : " + a);
System.out.println("Original Message: ");
print(x);
for (int i = 0; i < len; ++i) {
int block[] = { x[0 + i * 8], x[1 + i * 8], x[2 + i * 8],
x[3 + i * 8], x[4 + i * 8], x[5 + i * 8], x[6 + i * 8],
x[7 + i * 8] };
// bobcat() does one outer round
bob.bobcat(abc, block);
}

String hash = String.format("0x%04X", abc[0])
+ String.format("%04X", abc[1]) + String.format("%04X", abc[2]);
System.out.println("48-bit hash: " + hash);

int counter = 0;
String newhash = "";
while (!hash.equals(newhash)) {

//hashes.put(hash, 0);
abc[0] = 0xface;
abc[1] = 0xe961;
abc[2] = 0x041d;
x = permutate(x);
counter++;
//System.out.println(newhash + " count: " + counter);
for (int i = 0; i < 2; ++i) {
int block[] = { x[0 + i * 8], x[1 + i * 8], x[2 + i * 8],
x[3 + i * 8], x[4 + i * 8], x[5 + i * 8], x[6 + i * 8],
x[7 + i * 8] };
// bobcat() does one outer round
bob.bobcat(abc, block);

}
newhash = String.format("0x%04X", abc[0])
+ String.format("%04X", abc[1])
+ String.format("%04X", abc[2]);
}

System.out.println("Collision Message: ");
print(x);
System.out.println("48-bit hash: " + newhash);
System.out.println("collision found: count = " + counter);

}

private static void print(int[] x) {
for (int y : x) {
System.out.print(String.format("%04X", y) + ",");
}
System.out.println();
}

// creates a permutation of the message bits
private static int[] permutate(int[] x) {
Random rand = new Random();
//for (int i = 0; i < x.length; i++) {
for (int i = 0; i < 10; i++) {
x[i] = rand.nextInt(65535);
}
return x;
}

}

-
(1/2) First, a nitpick on terminology. You are not trying to find a collision, you are trying to find a pre-image. Collision finding is when you try to find any $x_1,x_2$ such that $H(x_1)=H(x_2)$ yet $x_1\neq x_2$. This is very different from the problem you are trying to solve where you are given a specific digest and told to find something that hashes to it. Anyways, we don't really do code review here, so this is off-topic. That said, if you are doing a brute force pre-image attack on a hash function that is 48-bits long, it may take a few days or weeks. – mikeazo Sep 24 at 11:45
(2/2) You can time it if you want. We would expect it would take around $2^{47}$ calls to the hash function to find a pre-image. Make a bunch of calls to it and time them. Divide to get the average time. Now multiply by $2^{47}$ to figure out how long you can expect this attack to take. If it is too long, changing how you generate inputs (assuming you have no information about the real input), won't help. Instead you must attack the hash function directly. I've never really heard of the bobcat hash function. Where does it come from? – mikeazo Sep 24 at 11:47
@mikeazo: there's attribution in there to an exercise in a book about information security: M. Stamp, Information security, principles and practice, 2nd ed., Hoboken, NJ: Wiley, 2011. There's reference code here, stating Bobcat is a 48-bit hash modeled on Tiger and this hash is insecure! – fgrieu Sep 24 at 12:38
For a 48 bit hash you could simply use a hashtable with around $2^{24}$ entries, no need for fancy algorithms like cycle finding. – CodesInChaos Sep 24 at 13:19
@CodesInChaos: Floyd's cycle-finding arguably beats a hashtable on simplicity, at least in languages like traditional C with no built-in support for associative arrays; and often in speed. – fgrieu Sep 24 at 15:36