Is there a way to find out which hash standard by studying the source code?

Question

We have an embedded product, which we are carrying for several hardware iterations since more than 5 years ago. We have all the source code, most of it nicely documented. As the product is actively sold and needs an upgrade, I have been tasked to design next generation improved version.

While we have all the source code, and most of it is well documented, the security part is not, especially its slowest part, a 128-bit hash function with 72 rounds. I can step trough it in our debugger, execute it, and the code works fine except its slowness. If I would know which cryptography standard it is, I could attempt to upgrade it to be executed in hardware, which would drastically speed it up. (The original consultant who wrote this function is not with our company and I cannot find her).

Is there any logical way to find out which encryption are we executing? I do not need a help to do my work, I am asking for an advice if there is any strategy how to look at code ('unoptimized mess'); learning the principle of it (like this one has 72 rounds and hashes 128 bits); then finding candidate standards doing the same thing.

I would think that after finding a documented standard, I should be able to hash various numbers by using both our hash and the standard hash, and simply see if the results match?

I looked on the web for information about known functions using 72 rounds, like the Skein algorithm, but could not find anything similar.

Are there any known hash values for known standards, for example results of hashing 0? This hash converts 0 to these 16 hexadecimal bytes:

ae c5 40 44 df 2d 91 1c 87 ab 1a ff 59 09 aa b7

Function beginning and end is below, as some of you requested, the full function is at: full_function_code

It looks like the previous programmer let the old C compiler to convert it, and then used it in 'assembly' style. Maybe it was due to avoid compiler optimizing, just my guess.

There are 72 rounds, each of which ends with a call to function TricoreDextr(); which is the C equivalent of Infineon TriCore DEXTR instruction. Think of DEXTR as splitting a 64-bit number into two parts (at the selected bit location) and swapping them.

Any concept explanations is a great help, thank you!

/*
 * @param in_arr    16 byte long array, input data (128 bits)
 * @param out_arr   16 byte long array, output data (128 bits)
 */
void Hash16bytes(unsigned char *in_arr, unsigned char *out_arr) 
{
  long d0, d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d15;
  long IN[16];

  d4 = 0xB12E8FB5;

  int i;
  for (i = 0; i < 16; i++)
  {
      IN[i] = (long) (*(in_arr + i));
  }

  d11 = (IN[3] << 24) | (IN[2] << 16) | (IN[1] << 8) | IN[0];
  d10 = (IN[7] << 24) | (IN[6] << 16) | (IN[5] << 8) | IN[4];
  d12 = (IN[0xB] << 24) | (IN[0xA] << 16) | (IN[9] << 8) | IN[8];
  d13 = (IN[0xF] << 24) | (IN[0xE] << 16) | (IN[0xD] << 8) | IN[0xC];

  /* block like this below repeats 72 times... */
  d3 = 0x7025BD47;
  d8 = 0xCCEE4EFE;
  d8 += d13; 
  d8 += d3;
  d8 = TricoreDextr(d8, 6);

  /* 
     etc., TricoreDextr is called total of 72 times 
   */

  d0 += d15;
  d0 += 0x5C4E0000;
  d0 -= 0x2EDC;
  d0 = TricoreDextr(d0, 5);

  *(out_arr + 3) = (unsigned char) ((d5 >> 24) & 0xFF);
  *(out_arr + 2) = (unsigned char) ((d5 >> 16) & 0xFF);
  *(out_arr + 1) = (unsigned char) ((d5 >> 8) & 0xFF);
  *(out_arr + 0) = (unsigned char) ((d5) & 0xFF);

  *(out_arr + 7) = (unsigned char) ((d6 >> 24) & 0xFF);
  *(out_arr + 6) = (unsigned char) ((d6 >> 16) & 0xFF);
  *(out_arr + 5) = (unsigned char) ((d6 >> 8) & 0xFF);
  *(out_arr + 4) = (unsigned char) ((d6) & 0xFF);

  d8 += d0;
  d8 += 0x10320000;
  d8 += 0x5476;

  *(out_arr + 0xB) = (unsigned char) ((d8 >> 24) & 0xFF);
  *(out_arr + 0xA) = (unsigned char) ((d8 >> 16) & 0xFF);
  *(out_arr + 9) = (unsigned char) ((d8 >> 8) & 0xFF);
  *(out_arr + 8) = (unsigned char) ((d8) & 0xFF);

  *(out_arr + 0xF) = (unsigned char) ((d7 >> 24) & 0xFF);
  *(out_arr + 0xE) = (unsigned char) ((d7 >> 16) & 0xFF);
  *(out_arr + 0xD) = (unsigned char) ((d7 >> 8) & 0xFF);
  *(out_arr + 0xC) = (unsigned char) ((d7) & 0xFF);
}

Answer 1

This is quite likely either a botched RIPEMD128 or something very similar, as otus also commented.

You wanted to know how to approach such a task so I'll explain what I did.

Typically, when trying to identify crypto-related code you rely on spotting constants. In this case, the constants seem to be obfuscated on purpose, so you need to play around with the numbers, throw it into Google and hope some results come up.

Assuming this might be the RIPE-family (by constant hunting), I sought out to find some code. As the input/output is 128 bits, I downloaded the code for RIPE128 from here:

https://homes.esat.kuleuven.be/~bosselae/ripemd160/ps/AB-9601/rmd128.c

I then looked over it. I noticed that the operations in compress() seem to use a left rotate (check the header file for the macro definitions), and that odd TricoreDextr() is effectively something similar.

So then I grepped your full code for all TricoreDextr() lines, and compared it to the ops in compress() and some similarities appeared:

GG(aa, bb, cc, dd, X[ 7],  7);
GG(dd, aa, bb, cc, X[ 4],  6);
GG(cc, dd, aa, bb, X[13],  8);
GG(bb, cc, dd, aa, X[ 1], 13);

compare to:

d8 = TricoreDextr(d8, 7);
d6 = TricoreDextr(d6, 6);
d5 = TricoreDextr(d5, 8);
d7 = TricoreDextr(d7, 0xD);

for example. The TricoreDextr calls don't fully match the ripe128 implementation. I also noticed that only some of the magic numbers used inside these operations appear in your code.

For example

#define GG(a, b, c, d, x, s)        {\
  (a) += G((b), (c), (d)) + (x) + 0x5a827999UL;\
  (a) = ROL((a), (s));\
}

does appear:

d5 += 0x5A820000;
d5 += 0x7999;

but others don't, so some operations that should be there if it was RIPE128 are definitely missing.

Reading Wikipedia taught me that before RIPE160 (and RIPE128), there was an original design for a 128 bit RIPEMD hash function but I could not locate any sourcecode from back then.

The only reference to the original 128 bit RIPEMD hash function pointed to

https://www.springer.com/in/book/9783540606406

which should contain the original algorithm I suppose, but it's a book that costs money.

Knowing all that, my best guess would be that this is the original RIPEMD 128 bit hash function obfuscated on purpose seeing as some but not all operations from the modern implementation are there, hinting that they could be an addition from the 2nd version which would explain why they are missing. That or someone used the modern RIPEMD128 implementation and did weird things to it.