How can I determine if a piece of code is an encryption algorithm?

Question

I am trying to reverse engineer a malware, and came across a piece of code that I suspect is an encryption/decryption procedure, however I do not know for sure. I can recognize that it extracts its payload from it's own .rsrc section. I scanned this algorithm with FindCrypt and IDAScope, Both plugins failed identifying it as a cryptographic algorithm.

I am not familiar with cryptographic algorithms. What are some good indications of code being an encryption or decryption algorithm, and what indications rule it out?

The extraction algorithm is(generated by IDA):

int __stdcall sub_9001320(int a1, unsigned int a2, int a3)
{
// a1 = a3 = 0x09003000
// a2 = 0x7600



  int result; // eax@2
  char v4; // al@23
  unsigned int l; // [sp+4h] [bp-4Ch]@33
  unsigned int k; // [sp+10h] [bp-40h]@19
  unsigned int v7; // [sp+14h] [bp-3Ch]@19
  int v8; // [sp+18h] [bp-38h]@40
  signed int j; // [sp+1Ch] [bp-34h]@13
  unsigned int v10; // [sp+20h] [bp-30h]@5
  unsigned int i; // [sp+24h] [bp-2Ch]@5
  unsigned int v12; // [sp+28h] [bp-28h]@5
  unsigned int v13; // [sp+2Ch] [bp-24h]@5
  signed int v14; // [sp+30h] [bp-20h]@13
  unsigned int v15; // [sp+34h] [bp-1Ch]@5
  unsigned int v16; // [sp+38h] [bp-18h]@5
  unsigned __int8 v17; // [sp+3Fh] [bp-11h]@5
  signed int v18; // [sp+40h] [bp-10h]@5
  _DWORD *lpAddress; // [sp+44h] [bp-Ch]@11
  unsigned int v20; // [sp+48h] [bp-8h]@13
  unsigned int v21; // [sp+4Ch] [bp-4h]@16

  if ( a2 > 0xC )
  {
    if ( *(_DWORD *)a1 == 1083581807 )
    {
      v16 = sub_9001300(a1);
      v18 = 12;
      v17 = 0;
      v15 = 9;
      v12 = 256;
      v13 = 256;
      v10 = 8 * a2 - 96;
      for ( i = 9; v10 >= i; v10 -= i )
      {
        if ( i != 12 && v13 == 1 << i )
          ++i;
        ++v13;
      }
      lpAddress = VirtualAlloc(0, 0xC000u, 0x1000u, 4u);
      if ( lpAddress )
      {
        v20 = 0;
        v14 = 256;
        for ( j = 0; j <= 255; ++j )
        {
          lpAddress[3 * j] = 0;
          lpAddress[3 * j + 2] = 0;
          lpAddress[3 * j + 1] = 1;
        }
        v21 = 0;
        while ( v21 < v16 && v12 < v13 )
        {
          v7 = 0;
          for ( k = 0; k < v15; ++k )
          {
            if ( (1 << (7 - (v17 + 8 * v18) % 8)) & *(_BYTE *)(a1 + (v17 + 8 * v18) / 8) )
              v7 |= 1 << k;
            v4 = (v17 + 1) % 8;
            v17 = (v17 + 1) % 8;
            if ( !v4 )
              ++v18;
          }
          if ( v7 > 0xFF )
          {
            if ( v20 < 0xF00 && v7 > v20 + 255 )
              return 0;
            if ( v21 + lpAddress[3 * v7 + 1] > v16 )
              return 0;
            for ( l = 0; l < lpAddress[3 * v7 + 1]; ++l )
              *(_BYTE *)(a3 + l + v21) = *(_BYTE *)(a3 + l + lpAddress[3 * v7]);
          }
          else
          {
            *(_BYTE *)(v21 + a3) = v7;
          }
          if ( v20 == 3840 )
          {
            if ( (unsigned int)++v14 >> 12 )
              v14 = 256;
          }
          if ( v20 >= 0xF00 )
          {
            v8 = v14 - 1;
            if ( v14 == 256 )
              v8 = 4095;
          }
          else
          {
            v8 = v20 + v14;
          }
          lpAddress[3 * v8] = v21;
          lpAddress[3 * v8 + 1] = lpAddress[3 * v7 + 1] + 1;
          lpAddress[3 * v8 + 2] = 0;
          if ( v20 < 0xF00 )
            ++v20;
          v21 = v21 + lpAddress[3 * v8 + 1] - 1;
          ++v12;
          if ( v15 < 0xC && 1 << v15 == v12 )
            ++v15;
        }
        if ( v21 >= v16 )
        {
          // sub_9001000 is only called onece and always return 0
          if ( *(_DWORD *)(a1 + 8) == sub_9001000(a3, v16) )
          {
            VirtualFree(lpAddress, 0, 0x8000u);
            result = 0;
          }
          else
          {
            result = 0;
          }
        }
        else
        {
          result = 0;
        }
      }
      else
      {
        result = 0;
      }
    }
    else
    {
      result = 0;
    }
  }
  else
  {
    result = 0;
  }
  return result;
}


int __stdcall sub_9001300(int a1)
{
  int result; // eax@2

  if ( *(_DWORD *)a1 == 1083581807 )
    result = *(_DWORD *)(a1 + 4);
  else
    result = 0;
  return result;
}

File info: file format pei-i386

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .text         00001000  09001000  09001000  00001000  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .rdata        00001000  09002000  09002000  00002000  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  2 .rsrc         00005000  09003000  09003000  00003000  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  3 .reloc        00001000  09008000  09008000  00008000  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA

Answer 1

TL;DR: What we have here is probably not an encryption algorithm, it is more likely a decompression loop, by the look of it. It simply does not do anything that could be considered even remotely similar to encryption.

Encryption algorithms are divided into two classes. First is a stream cipher. From wikipedia:

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation an exclusive-or (XOR).

Second is a block cypher. From wikipedia:

In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key. Block ciphers operate as important elementary components in the design of many cryptographic protocols, and are widely used to implement encryption of bulk data.

The modern design of block ciphers is based on the concept of an iterated product cipher. In his seminal 1949 publication, Communication Theory of Secrecy Systems, Claude Shannon analyzed product ciphers and suggested them as a means of effectively improving security by combining simple operations such as substitutions and permutations.1 Iterated product ciphers carry out encryption in multiple rounds, each of which uses a different subkey derived from the original key. One widespread implementation of such ciphers, named a Feistel network after Horst Feistel, is notably implemented in the DES cipher.2 Many other realizations of block ciphers, such as the AES, are classified as substitution-permutation networks.

What we have here is probably not an encryption algorithm. It simply does not do anything that could be considered even remotely similar to encryption. Some of the things that are often found in encryption algorithms but are missing here (not a complete list but just the first few things I came up with):

1. There's no pseudo-random stream generated based on an internal state and seed like in stream ciphers
2. no sequential character combination of generated stream with input buffer using a XOR (or any other operation).
3. No block structure - a sequence executed multiple times on each nicely chunked portion of the input message.
4. no long and complex permutation (and no permutation table).
5. No multiple iterations of a permutation code common to block ciphers.
6. no key sequence initialization (used in both stream and block ciphers).
7. Not enough substitutions over either input message or stream/state.

Encryption algorithms are usually long (and one might say ugly). Usually structured and meticulous on performing operations on all bytes in long repeated sequences. You'll often see multiple iterations of a fixed length performing a single or few operations.

This is more resembling a compression/decompression algorithm, as sequences of bytes are copied on certain conditions, while bytes are constructed into the decompressed buffer on others.

Lets go over the code and see:

int __stdcall sub_9001320(int a1, unsigned int a2, int a3)
{
// a1 = a3 = 0x09003000
// a2 = 0x7600

  int result; // eax@2
  char v4; // al@23
  unsigned int l; // [sp+4h] [bp-4Ch]@33
  unsigned int k; // [sp+10h] [bp-40h]@19
  unsigned int v7; // [sp+14h] [bp-3Ch]@19
  int v8; // [sp+18h] [bp-38h]@40
  signed int j; // [sp+1Ch] [bp-34h]@13
  unsigned int v10; // [sp+20h] [bp-30h]@5
  unsigned int i; // [sp+24h] [bp-2Ch]@5
  unsigned int v12; // [sp+28h] [bp-28h]@5
  unsigned int v13; // [sp+2Ch] [bp-24h]@5
  signed int v14; // [sp+30h] [bp-20h]@13
  unsigned int v15; // [sp+34h] [bp-1Ch]@5
  unsigned int v16; // [sp+38h] [bp-18h]@5
  unsigned __int8 v17; // [sp+3Fh] [bp-11h]@5
  signed int v18; // [sp+40h] [bp-10h]@5
  _DWORD *lpAddress; // [sp+44h] [bp-Ch]@11
  unsigned int v20; // [sp+48h] [bp-8h]@13
  unsigned int v21; // [sp+4Ch] [bp-4h]@16

Function definiton

  if ( a2 > 0xC )
  {

Assert a certain length is at least 96 bytes. Although there are some block ciphers accepting this as block size, it's not too common and most widely accepted block ciphers do not support this block size.

    if ( *(_DWORD *)a1 == 1083581807 )
    {

Assert certain first bytes of buffer are fixed, this just looks odd without context.

      v16 = sub_9001300(a1);

Set v16 to second dword of input buffer

      v18 = 12;
      v17 = 0;
      v15 = 9;
      v12 = 256;
      v13 = 256;
      v10 = 8 * a2 - 96;

Some more variable initializations

      for ( i = 9; v10 >= i; v10 -= i )
      {
        if ( i != 12 && v13 == 1 << i )
          ++i;
        ++v13;
      }

Increase v13 according to original length. Without going too much into specifics here, this doesn't look like any cipher seed/initialization.

      lpAddress = VirtualAlloc(0, 0xC000u, 0x1000u, 4u);
      if ( lpAddress )
      {

Allocate a hardcoded length buffer to work on as temporary data

        v20 = 0;
        v14 = 256;
        for ( j = 0; j <= 255; ++j )
        {
          lpAddress[3 * j] = 0;
          lpAddress[3 * j + 2] = 0;
          lpAddress[3 * j + 1] = 1;
        }

Initialize said buffer, 2/3 with 0s, 1/3 with 1s. this is probably a boolean buffer.

        v21 = 0;
        while ( v21 < v16 && v12 < v13 )
        {

Loop v16 times. remember v16 is user supplied as the second dword in provided buffer. The second dword after the magic is probably a length.

          v7 = 0;
          for ( k = 0; k < v15; ++k )
          {

Another loop, this time for 9 iterations. This means we have 9 iterations for each character in the guessed length parameter. Most block ciphers will have more iterations, and those won't be per character. Most stream ciphers will not process data but instead generate a stream of bytes to XOR with. We don't see a XOR here either.

            if ( (1 << (7 - (v17 + 8 * v18) % 8)) & *(_BYTE *)(a1 + (v17 + 8 * v18) / 8) )
              v7 |= 1 << k;

Bits are only added to v7, also not productive for any type of encryption algorithm.

            v4 = (v17 + 1) % 8;
            v17 = (v17 + 1) % 8;

These two are byte-sized counters.

            if ( !v4 )
              ++v18;
          }

Increase another counter, used for determining how many bits in v7 will be set. This entire loop decides which bits of v7 will be set, depending on a fixed sequence and wether certain bits of the input buffer are

          if ( v7 > 0xFF )
          {
            if ( v20 < 0xF00 && v7 > v20 + 255 )
              return 0;
            if ( v21 + lpAddress[3 * v7 + 1] > v16 )
              return 0;
            for ( l = 0; l < lpAddress[3 * v7 + 1]; ++l )
              *(_BYTE *)(a3 + l + v21) = *(_BYTE *)(a3 + l + lpAddress[3 * v7]);
          }

If v7 is above 0xff do some sanity (and return on invalid state/data) and then copy a sequence of bytes until a null terminator is reached from a3 to a3, at offsets determined by the value of lpAddress at a specific offset determined by v7.

          else
          {
            *(_BYTE *)(v21 + a3) = v7;
          }

if v7 is below or equal to 255, simply assign it in specified location.

          if ( v20 == 3840 )
          {
            if ( (unsigned int)++v14 >> 12 )
              v14 = 256;
          }
          if ( v20 >= 0xF00 )
          {
            v8 = v14 - 1;
            if ( v14 == 256 )
              v8 = 4095;
          }
          else
          {
            v8 = v20 + v14;
          }

Reset values of v8 and v4 based on values of offset variables, namely v20 and themselves.

          lpAddress[3 * v8] = v21;
          lpAddress[3 * v8 + 1] = lpAddress[3 * v7 + 1] + 1;
          lpAddress[3 * v8 + 2] = 0;

Set a few other values in lpAddress based hardcoded values (0) and a copy of a single value.

          if ( v20 < 0xF00 )
            ++v20;
          v21 = v21 + lpAddress[3 * v8 + 1] - 1;
          ++v12;
          if ( v15 < 0xC && 1 << v15 == v12 )
            ++v15;
        }

Some more counter update based on input and reset of overflows.

        if ( v21 >= v16 )
        {
          // sub_9001000 is only called onece and always return 0
          if ( *(_DWORD *)(a1 + 8) == sub_9001000(a3, v16) )
          {
            VirtualFree(lpAddress, 0, 0x8000u);
            result = 0;
          }
          else
          {
            result = 0;
          }
        }
        else
        {
          result = 0;
        }
      }
      else
      {
        result = 0;
      }
    }
    else
    {
      result = 0;
    }
  }
  else
  {
    result = 0;
  }
  return result;
}

In case of any invalid input, return 0

int __stdcall sub_9001300(int a1)
{
  int result; // eax@2

  if ( *(_DWORD *)a1 == 1083581807 )
    result = *(_DWORD *)(a1 + 4);
  else
    result = 0;
  return result;
}

Assert buffer starts with a hardcoded dword (which we already know is the case because of a previous if statement) and return the value in the second dword.