7

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);
}

migrated from crypto.stackexchange.com Mar 19 '17 at 12:01

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • 3
    You haven't shown how the out_arr[] is populated in Hash16bytes(). Also, the constants that appear in your snippet (i.e.: 0xB12E8FB5, 0x7025BD47, 0xCCEE4EFE) don't appear in Google anywhere but in this question, which makes this puzzle a little challenging. I would infer that either: 1) this hash function is homegrown, 2) this is a keyed hash function and the constants somehow represent the key, or 3) this was code-generated and/or converted in a weird way. – mhum Mar 18 '17 at 3:22
  • mhum: I added the end of the function as well – EmbeddedGuy Mar 18 '17 at 4:06
  • 1
    that code is an unoptimized mess, almost certainly not a standard, you should post a link to it complete as the commented block cannot possibly be repeated precisely – Richie Frame Mar 18 '17 at 9:11
  • 1
    Looks like it could be an obfuscated RIPEMD-128. The constants seem to match like 0x5C4E0000 - 0x2EDC = 0x5C4DD124 and 0x50A30000-0x741A = 0x50A28BE6. Ought to be easy to confirm. (Reverse engineering is off topic here, flagging for migration.) – otus Mar 19 '17 at 7:01
  • 1
    The code looks a little ugly but you do have it in source form. Why not profile a few runs and try to speed it up as-is instead of trying to find another algorithm which might look similar but produce slightly different results, breaking the protocol? – Igor Skochinsky Apr 23 '18 at 21:21
5

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.

  • Thank you for the book link, I ordered it, will be educational or maybe more, describes the code – EmbeddedGuy Apr 25 '18 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.