Identify a decryption scheme

Question

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

Answer 1

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...