Virus uses a custom XOR encryption and need help possibly cracking it / Reversing EXE

Question

As stated in my previous question i was infected by a encrypting virus that encrypts two 1024 byte blocks of any given file (First 1024, and last 1024) in some type of custom CFB XOR encryption. I was able to get my hands on a decrypter that another victim paid for (of course it doesn't work for me because different keys) and find the decryption function in IDA, but the C generated code was bad and the whole EXE is obfuscated with a custom method. A user of stackexchange converted it into C# for me to better understand it (Thanks Edward) For more information on this see the last post:

IDA Pro C dump for Decryption function

So to the point. The encryption this guy uses is pretty much XOR with some trickery, so the encryption function is pretty much the same as the decryption. In the decrypter holds a 20 byte key, I found this by comparing 4 different decrypters together that victims paid for with all of them only having a 20 byte difference all in the same area, and also later confirming it in IDA when its pushed onto the stack.

Even though the key is 20 bytes, only 16 is used in the encryption and 4 is used to generate a header for each encrypted file so the decrypter can later find them. So in ida it looks something like this:

Dword: C4 67 0E 46 Dword: 99 2F D3 E4 40 BD 87 EB 8F 35 04 96 3B CE 8D 73

My guess is 4 bytes are used in each 512 block encrypted, two 512 blocks being CFB'ed to one another to make 2 1024 blocks of encrypted data. Sorry if that didn't make sense.

Sadly the Decrypter is HEAVILY Obfuscated as i said, and also uses tons of junk JMP's and functions to were its impossible to read. Took forever to find just the decryption function.

So to the code, This is the cleaned code for the decryption (Encryption also) function.

int mystery(char *buff, int bufsize, int nonce1, int nonce2)
{
  int result = 0;
  // ch is the next byte (character) in the buffer
  char ch = 0; 
  int count = bufsize; 
  char *ptr = buff; 
  int x;

  for (x = nonce1; count; --count)
  {
      // this bit of trickery just replaces the low 8 bits
      // of x with the low 8 bits of (x+ch) neglecting carry, if any
      x = (x & ~0xff) | ((x+ch) & 0xff);
      // XOR the buffer with the calculated x value
      *ptr ^= x;
      // read in the next character into ch
      ch = *ptr++;
      // obfuscate by adding nonce2 
      x += nonce2;
      // if x = 0x12345678, this would make it 0x34567812
      // for 32-bit ints.  Just a rotate left of 8 bits.
      x = (x<<8) | ((x >>((sizeof(int)-1)*8) ) & 0xff);  
  }
  result = x;
  // return the last calculated x which may be used to chain all
  // of the blocks together.  That is, the return value x is 
  // probably passed as nonce1 to encode the next block.
  return result;
}

Above 2 INT named nonce's are generated from the 16 bytes some how.

So basically, me, and many others are wondering if this is at all Brute force-able or crackable like regular XOR? Of course i do not know my key, But nearly everyone would have at least one plain and encrypted file for a plain text attack like XOR if possible.

Below is the same Decrypted (plain text), and encrypted file that goes with this decrypter, along with the decrypter itself as resources. The example key above is also the key in this decrypter. ( in no particular order sadly)

Decrypted (Plain text) File

Encrypted file

Decrypter EXE

(This EXE is in no way malicious, and will not effect any files when ran as it detects encrypted files. I have ran it hundreds of times on my personal computer with no fault. It can be attached to a debugger and ran safely. Virus total says other wise simply because its a known exe situated with the infection.)

As a last note i believe in IDA the function 4075F3 generates the nonces, but cant be 100%

Im sorry for this being so long, its quite hard to explain all at once.

Answer 1

I don't have the time at the moment to formulate a proper solution but I'll give some hints that will hopefully help you.

I would honestly break this down to a simpler problem, switch the integers down to fewer bits. For instance you could take the algorithm and modify it such that it works with 8-bit nonces, then switch your rotation amount down to 2 bits (one fourth of the nonce size). Then you switch your masks from 8 bits to 2 bits as well and your cipher xor into 2 bits. This way you're working with a more manageable problem. You could even reduce it into 4-bit nonces and 1 bit cipher.

From this simplified problem you formulate equations for each bit from the plaintext to the cipher text. Plugging it into something like Z3 might be the easiest way of getting an answer out. Here's an article using Z3 to attack a simple hash function.

Glancing at it it looks like if you have the plaintext and the ciphertext you can solve for the key (nonce1 and nonce2). The addition of nonce2 might be an issue due to it actually being an addition modulus 2^32. As it's an addition there's really only two values due to the constraints on nonce2 and x that can map to the same value so the it's not impossible to invert.

If you're not sure whether you can solve the equations yourself I would bring the problem to math.stackexchange.com once you've got it figured out.

Answer 2

If it really does ch=*prt++ (and not ch=*++ptr), then ch is the character just written in the line before, not the next character read as the comment suggests. Anyway, contrary to what you write this method is not involuntary: With nonce1=nonce2=0 the clear text 1,2,3,4,5,6,7,8 gets transformed to 1,3,0,4,1,5,0,8 (if I'm not mistaken) and that gets transformed to (1,2,2,...)