3

I'm trying to identify a decryption scheme used by some licencing mechanism. It took me some time to realize that this was encryption and this is some kind of follow up to this other question of mine : Create key generator algorithm from validation algo

I did some homework and it seems to me that the key characteristics of this decryption are the following:

1-The input is base64 decoded first (with some non standard key tables, but the algo is quite identical)
2-It is decrypted with a key of the same length as the input. This might be a one time pad or simply a very long key for very short data (both are 512 bits)
3-Most importantly and what baffles me is that the decryption algo uses NO xor. Every cipher I've seen use XOR at some point in the decryption but there simply is none here.

Point 3 is what I really don't understand here. I fail to see how to generate data that can be decrypted without XOR. Using bitshifting and AND/OR masking seems to lose a lot of information during the process.

Are there any known ciphers which match those characteristics?

Edit :

Ok here is some deeper description of the algo :

There is one function that is called multiple times. It first creates 2 tables with the data and the decryption key. The second one is based on the first one.

This function first creates a table with the data and then processes that data with the decryption key in another table.

The table created from the data is made by manipulating each 32 bits blocks (master block) from the data with the entire data with additions so that it yields a single unsigned int for each of the 16 32 bit blocks. The call for this looks like this

hash_block(&result1, &result2, current_master_block, data_array[i]);

hash_block looks like this :

void hash_block(int *result1, int *result2, unsigned int pMaster_block, unsigned int pCurrent_block)
{
    int current_block;
    unsigned int current_high_short;
    int master_high_times_master; 
    unsigned int master_high_master_short;
    int master_high_times_current;
    unsigned int sum_of_mixes;

    current_block = (unsigned __int16)pCurrent_block;

    current_high_short = pCurrent_block >> 16;
    master_high_times_master = HIWORD(pCurrent_block) * (unsigned __int16)pMaster_block;
    master_high_master_short = pMaster_block >> 16;
    *(_DWORD *)result1 = current_block * (unsigned __int16)pMaster_block;
    master_high_times_current = current_block * HIWORD(pMaster_block);
    sum_of_mixes = master_high_times_current + master_high_times_master;
    *(_DWORD *)(result2) = (unsigned __int16)current_high_short * (unsigned __int16)master_high_master_short;
    if ( master_high_times_current > sum_of_mixes )
        *(_DWORD *)(result2) += 65536;
    *(_DWORD *)result1 += sum_of_mixes << 16;
    if ( sum_of_mixes << 16 > *(_DWORD *)result1 )
        ++*(_DWORD *)(result2);
    *(_DWORD *)(result2) += sum_of_mixes >> 16;
}

I'm currently cleaning up the code a bit, I'll follow up with more information on how the second part of the algo works

EDIT 2 :

There is also a very complex function that I can't make sense of which is run 248 times in this function :

void __fastcall sub_4D5AC0(int* result, int* serial_copy, unsigned int last_keyitem)
{
  unsigned int v3; // edi@1
  unsigned int v4; // edi@2
  int v5; // eax@4
  int v6; // eax@7
  unsigned int v7; // eax@11
  //int return_value; // ecx@25
  int* v10; // [sp+0h] [bp-24h]@1
  unsigned int v11; // [sp+4h] [bp-20h]@4
  int v12; // [sp+4h] [bp-20h]@16
  unsigned __int64 v13; // [sp+4h] [bp-20h]@18
  int v14; // [sp+8h] [bp-1Ch]@1
  unsigned int v15; // [sp+8h] [bp-1Ch]@6
  unsigned int v16; // [sp+10h] [bp-14h]@16

  v3 = *(serial_copy + 1);
  v14 = *(serial_copy + 1);
  if ( HIWORD(last_keyitem) == -1 )
    v4 = v3 >> 16;
  else
    v4 = v3 / ((unsigned int)HIWORD(last_keyitem) + 1);
  v5 = (unsigned __int16)last_keyitem * (unsigned __int16)v4 << 16;
  v11 = *serial_copy - v5;
  //if ( -1 - v5 < v11 )
  if ( ~v5 < v11 )
    --v14;
  v15 = v14 - ((unsigned __int16)last_keyitem * (unsigned int)(unsigned __int16)v4 >> 16) - HIWORD(last_keyitem) * (unsigned __int16)v4;
  while ( 1 )
  {
    if ( HIWORD(last_keyitem) >= v15 )
    {
      v7 = HIWORD(last_keyitem);
      if ( HIWORD(last_keyitem) != v15 )
        break;
      v7 = (unsigned __int16)last_keyitem << 16;
      if ( v7 > v11 )
        break;
    }
    v6 = (unsigned __int16)last_keyitem << 16;
    v11 -= v6;
    if ( -1 - v6 < v11 )
      --v15;
    v15 -= HIWORD(last_keyitem);
    ++v4;
  }
  if ( HIWORD(last_keyitem) == -1 ){
    //LOWORD(v7) = v15;
    v7 &= 0xFFFF0000;
    v7 |= v15 & 0xFFFF;
  }else{
    v7 = ((v11 >> 16) + (v15 << 16)) / ((unsigned int)HIWORD(last_keyitem) + 1);
  }
  v16 = HIWORD(last_keyitem) * (unsigned __int16)v7;
  v12 = v11 - (unsigned __int16)last_keyitem * (unsigned __int16)v7;
  if ( v12 > -1 - (unsigned __int16)last_keyitem * (unsigned int)(unsigned __int16)v7 )
    --v15;
  //LODWORD(v13) = v12 - (v16 << 16);
  v13 &= 0xFFFFFFFF00000000;
  v13 |= (v12 - (v16 << 16)) & 0xFFFFFFFF;
  if ( -1 - (v16 << 16) < (unsigned int)v13 )
    --v15;
  // HIDWORD
  v13 &= 0x00000000FFFFFFFF;
  v13 |= (v15 - (v16 >> 16)) & 0xFFFFFFFF00000000;
  while ( last_keyitem <= v13 )
  {
      v13 &= 0xFFFF0000;
      v13 |= (v13 - last_keyitem) & 0xFFFF;
    //LODWORD(v13) = v13 - a3;
    v13 = (v13 - last_keyitem) & 0xFFFF;
    if ( (unsigned int)v13 > -1 - last_keyitem ){
      //--HIDWORD(v13);
        unsigned __int64 high_word = v13 & 0xFFFFFFFF00000000;
        high_word++;
        v13 &= 0x00000000FFFFFFFF;
        v13 |= high_word;
    }
    ++v7;
  }
  *result = (unsigned __int16)v7 + ((unsigned __int16)v4 << 16);
}
  • RSA would be one such cipher from the realm of cryptographic algorithms, as opposed to home-brewed ones. However, you haven't given us a lot to go on. What about a bit of code, by way of example? As regards the presumed loss of information: XOR is bijective and its own inverse, but any pair of bijective functions will do, starting with ADD and SUB. And permutation ciphers don't perform any arithmetic ops on the input elements at all, they just shuffle them around. Some home-brewed algos simply shift bits around or rotate them, even across byte/word boundaries. – DarthGizka Jan 3 '15 at 6:54
  • Very nice, thank you! Would it be possible to post the disassembly for the two functions on pastebin? Some things are easier to see in the disassembly (less misleading). Some of the bits seem akin to home-brewed big integer math... – DarthGizka Jan 3 '15 at 10:10
  • 1
    pastebin.com/4yZN2huw – Eric Jan 3 '15 at 11:57
4

The first function (the one at .text:004D5A40) computes the 64-bit product of two 32-bit unsigned operands and stores the result through EAX. It is probably some half-assed 16-bit code recompiled with a half-assed 32-bit compiler...

For a quick test you can paste the disassembly into an __asm block to make it recompilable. Then you can make a call stub to aid experimentation:

__declspec(naked)
void sub_4D5A40 ()
{
   __asm
   {
/*4D5A40*/                 push    ebx
... BIG SNIP ...
/*4D5ABE*/                 pop     ebx
/*4D5ABF*/                 retn
   }
}

__declspec(noinline)
uint64_t halfassed_mul (uint32_t multiplicand, uint32_t multiplier)
{
   uint64_t result;

   __asm
   {
      mov   ecx, multiplicand
      mov   edx, multiplier
      lea   eax, result

      call sub_4D5A40
   }

   return result;
}

That way you can easily compare/verify the result against the 64-bit product of the parameters.

Note: the listing won't compile unless you change the stack variable references to word ptr [esp]. If you forget the word qualifier then the compiler will assume byte-sized access, and this will b0rken things.

The compiler used for your target is so poor that Hex-Rays obviously cannot make much sense of the code... You may have more success if you recompile the decompiler output for selected functions with a decent compiler and full optimisation, in order to remove as much redundancy as possible (don't forget __declspec(noinline)). If you decompile that then things should be a lot clearer.

Browse a couple of the bigint-related topics on Stack Overflow and Code Review to refresh your memory on what bigint code looks like where the rubber meets the road, especially the contest-related topics where people have to reinvent the wheel instead of just calling some bigint library. For example the topic Sum of digits in a^b. That should make it much easier to recognise related patterns in the code.

Update: I tackled sub_4D5AC0 because I wanted to know what mysterious calculation it performs, but trying to understand the code made my head swim, even after I removed a lot of redundant instructions. So I decided to give it the black box treatment, on the assumption that it performs some basic arithmetic computation. The elementary operations of the code indicated division, in a rather convoluted way. Combined with the signature (64-bit op 32-bit, with 32-bit result), the only op that fitted was MOD. So I pasted the code into an .asm, which compiled without a hitch (kudos to IDA!), made a call stub and fed some inputs into the black box. It turns out that the function divides a 64-bit integer at *EDX by ECX and stores the lower 32 bits of the quotient through EAX.

When I wrote a test to verify the function output for some random inputs I typed 1000000000 for the loop count as usual. Biiig mistake, since 1000 calls take about a second already...

  • The compiler is some older version of Borland C++. Seriously, hat off to you sir. I'll accept your answer for now since it gets me unstuck. I doesn't really answer the question but I can make sense of all of this. Thanks – Eric Jan 3 '15 at 21:06
  • Thanks for posing such an interesting and intriguing question (fingers doing boring stuff at work at this time of the month, brain often idle). If you find more cryptic code and want a couple more eyes on it, it'll be our pleasure to chip in again. bcc32 had a lot of qualities but its code generator/optimiser was only servicable at best and unable to optimise away the effects of substellar coding; this explains the shape of the object code and also the odd register calling convention. – DarthGizka Jan 4 '15 at 12:49
  • Wow, that is incredibly insightful of you! I'm also interested in how you proceeded to recompile the asm. Is this a feature from IDA? I tried pasting it to visual studio and enclose it in an __asm {} instruction, but this lead to a lot of pain. Also VS does not like when we play with ebp which borland seems not to care about. I was trying to recompile the disassembly from IDA with like -O3 in VS, then redisassemble it again. Is this something that usually works? You seemed to suggest it does. Finally, it is Borland Delphi and not C++, which leads to more uglyness =) – Eric Jan 5 '15 at 18:53
  • dcc32 and bcc32 supposedly share the same backend, a fact which was much stressed advertising... And bcc32 allowed it to combine C++ with the VCL (true two-way RAD), when MS-based programmers still had to battle with MFC or buy third-party UI kits. Not to mention things like closures which pure C++ still doesn't have. But I digress. The question of reassembling/recompiling IDA output for a bit of hands-on testing deserves a topic in its own right, which I'm sure will elicit interesting answers. Why don't you post a question for it, using this topic's listing as example? I'll definitely respond – DarthGizka Jan 5 '15 at 20:46
  • Just a note: you can use IDA's appcall to call application functions. – rev Jan 6 '15 at 4:59

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.