5

I have been working on rewriting a program, although it uses a hash to fingerprint the file, I have used IDA to find the function doing the hash and what it is doing to the file before it sends it to the hash function.

I just have a couple questions about what is going on, I know I can simply invoke it as it is in a DLL, but I want to understand what is going on as well.

unsigned int __cdecl newhash(int a1, unsigned int a2, int zero)
{
  int content; // ebx@1
  int v4; // ecx@1
  int v5; // edx@1
  int i; // eax@1
  int v7; // ecx@2
  unsigned int v8; // eax@2
  int v9; // edx@2
  int v10; // ecx@2
  int v11; // eax@2
  int v12; // edx@2
  int v13; // ecx@2
  int v14; // eax@2
  unsigned int v15; // eax@3
  int v16; // edx@15
  int v17; // ecx@15
  int v18; // eax@15
  int v19; // edx@15
  int v20; // ecx@15
  int v21; // eax@15
  int v22; // edx@15
  unsigned int contentLength; // [sp+Ch] [bp-4h]@1

  content = a1;
  contentLength = a2;
  v4 = -1640531527;
  v5 = -1640531527;
  for ( i = zero; contentLength >= 12; contentLength -= 12 )
  {
    v7 = (*(_BYTE *)(content + 7) << 24)
       + (*(_BYTE *)(content + 6) << 16)
       + (*(_BYTE *)(content + 5) << 8)
       + *(_BYTE *)(content + 4)
       + v4;
    v8 = (*(_BYTE *)(content + 11) << 24)
       + (*(_BYTE *)(content + 10) << 16)
       + (*(_BYTE *)(content + 9) << 8)
       + *(_BYTE *)(content + 8)
       + i;
    v9 = (v8 >> 13) ^ ((*(_BYTE *)(content + 3) << 24)
                     + (*(_BYTE *)(content + 2) << 16)
                     + (*(_BYTE *)(content + 1) << 8)
                     + *(_BYTE *)content
                     + v5
                     - v7
                     - v8);
    v10 = (v9 << 8) ^ (v7 - v8 - v9);
    v11 = ((unsigned int)v10 >> 13) ^ (v8 - v9 - v10);
    v12 = ((unsigned int)v11 >> 12) ^ (v9 - v10 - v11);
    v13 = (v12 << 16) ^ (v10 - v11 - v12);
    v14 = ((unsigned int)v13 >> 5) ^ (v11 - v12 - v13);
    v5 = ((unsigned int)v14 >> 3) ^ (v12 - v13 - v14);
    v4 = (v5 << 10) ^ (v13 - v14 - v5);
    i = ((unsigned int)v4 >> 15) ^ (v14 - v5 - v4);
    content += 12;
  }
  v15 = a2 + i;
  switch ( contentLength )
  {
    case 0xBu:
      v15 += *(_BYTE *)(content + 10) << 24;
      goto LABEL_5;
    case 0xAu:
LABEL_5:
      v15 += *(_BYTE *)(content + 9) << 16;
      goto LABEL_6;
    case 9u:
LABEL_6:
      v15 += *(_BYTE *)(content + 8) << 8;
      goto LABEL_7;
    case 8u:
LABEL_7:
      v4 += *(_BYTE *)(content + 7) << 24;
      goto LABEL_8;
    case 7u:
LABEL_8:
      v4 += *(_BYTE *)(content + 6) << 16;
      goto LABEL_9;
    case 6u:
LABEL_9:
      v4 += *(_BYTE *)(content + 5) << 8;
      goto LABEL_10;
    case 5u:
LABEL_10:
      v4 += *(_BYTE *)(content + 4);
      goto LABEL_11;
    case 4u:
LABEL_11:
      v5 += *(_BYTE *)(content + 3) << 24;
      goto LABEL_12;
    case 3u:
LABEL_12:
      v5 += *(_BYTE *)(content + 2) << 16;
      goto LABEL_13;
    case 2u:
LABEL_13:
      v5 += *(_BYTE *)(content + 1) << 8;
      goto LABEL_14;
    case 1u:
LABEL_14:
      v5 += *(_BYTE *)content;
      break;
    default:
      break;
  }
  v16 = (v15 >> 13) ^ (v5 - v4 - v15);
  v17 = (v16 << 8) ^ (v4 - v15 - v16);
  v18 = ((unsigned int)v17 >> 13) ^ (v15 - v16 - v17);
  v19 = ((unsigned int)v18 >> 12) ^ (v16 - v17 - v18);
  v20 = (v19 << 16) ^ (v17 - v18 - v19);
  v21 = ((unsigned int)v20 >> 5) ^ (v18 - v19 - v20);
  v22 = ((unsigned int)v21 >> 3) ^ (v19 - v20 - v21);

  return (((v22 << 10) ^ 
           (unsigned int)(v20 - v21 - v22)) >> 15) ^ 
           (v21 - v22 - ((v22 << 10) ^ (v20 - v21 - v22)));
}

a1 is an address location a2 is the length of the file to hash zero I renamed as it always sends zero for whatever reason.

Now for the questions:

  1. First and foremost, is this a standard algorithm like CRC or something?
  2. Is there a reason for the v4 and v5 variables to be -1640531527?
  3. What is the purpose of (*(_BYTE *)(content + 7) << 24) isn't a byte only 8 bits, so won't it be 0 every time? I looked up the order of operations and it seems that the casting is first then the bit operations, so it means it converts it to the 8th byte in the file and bit shifts it 24 bits right? why?
  4. Why are some bits signed and some unsigned, and would it change the outcome if there is a mix?

Those are most of my questions, I understand it is going through all the bytes and getting a total to figure out the "hash" for the file, I understand that the switch case is taking care of the situation of the file not being exactly divisible by 12. I think once I understand the logic behind the bitwise operations then it will be more clear.

7

-1640531527 is hexadecimal '0x9e3779b9'. This number is used in boost hash function. The code here in function ub4 hash( k, length, initval) looks similar to yours, at least in the last part. I think that it is a good point to start googling from.

As far as I can say it is probably intermediate variant(lookup2) of Jenkins Hash

4

Just a small addition to the previous answers.

The following shift construct, asked in 3, is a widely used way to convert a byte stream into a 32-bit integer.

   (*(_BYTE *)(content + 7) << 24)
 + (*(_BYTE *)(content + 6) << 16)
 + (*(_BYTE *)(content + 5) << 8)
 + *(_BYTE *)(content + 4)

31    24    23    16    15     8    7      0
AAAAAAAA    BBBBBBBB    CCCCCCCC    DDDDDDDD
  ^^^         ^^^         ^^^         ^^^
content[7]  content[6]  content[5]  content[4]

If content is the address of a byte array, you can simply write

*(_BYTE *)(content+7)

as

content[7]

But of course, you should declare content in a different way as the decompiler did, but the decompiler see only a pointer and don't know that it is a byte array really.

  • I figured it was getting the different bytes, I just didn't understand that the bitshift was on an int and not a 8 bit byte, and since the conversion from byte to int will always put it on the right, they shift it. So it seems they are being inverted in the int, Right? 7 is on the left instead of on the right? – Krum110487 May 13 '15 at 14:19
  • 1
    The inverting is depend on the endianness of the current architecture. Since the example is seems to be x86, it is little-endian, so the result of the byte shifts will not invert the int finally. So, the int could be extracted in an easier way also ((int*)content)[1], but this is the platform independent way of doing this. – ebux May 14 '15 at 7:25
6

Some more low-level details:

  1. What is the purpose of (*(_BYTE *)(content + 7) << 24) isn't a byte only 8 bits, so won't it be 0 every time?

In C, shifts implicitly promote the operand to at least an int/unsigned int, so the _BYTE value gets promoted to an unsigned int. This is probably because most processors support shifts on a single word size and not bytes.

There's another problem, where the result is assigned to an int instead of an unsigned int, which brings you to the next question...

  1. Why are some bits signed and some unsigned, and would it change the outcome if there is a mix?

The assembler for signed left shift and unsigned left shift are the same, as bits shifted outside the register just disappear. This means the decompiler can't tell if a left shift was unsigned, so it uses a safe guess of int.

Signed right shift and unsigned right shift are different, because the sign bit has to be filled correctly. This allows the decompiler to guess unsigned correctly only for right shifts.

In general, a decompiler cannot detect if a variable is unsigned because so many operations are the same as on a signed variable.

  • 1
    I would love to up-vote you and give you the correct answer too!!! but I can't up-vote, so if anyone sees this, please up-vote for me :) – Krum110487 May 12 '15 at 17:42
  • no, it's always promoted to int regardless of signness, unless sizeof(_BYTE) >= sizeof(int) – phuclv May 14 '15 at 7:54

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.