1
$\begingroup$

I have a block of data which I know is encrypted using a chained 64-bit xor (sorry if that makes no sense, I'm not familiar with crypto lingo). I know a little bit about what the plaintext should look like, and I also know the algorithm used to decrypt the data.

What I know about the data:

  • 6 x 0x20 sized 'chunks', giving a total size of 0xC0
  • The first chunk contains a Windows DLL name (e.g. foobar.dll) with unknown (and probably mixed) case. The name is probably that of a DLL present on a typical Windows installation.
  • The other five chunks each contain a name of a procedure exported by the aforementioned DLL. The name probably starts with an uppercase letter due to it being an export in a system DLL.
  • All strings must be null terminated.
  • All strings are 'narrow' (i.e. one byte per character).

Here's the decryption algorithm:

extern unsigned int* ObfuscatedData;
extern unsigned int k1;
extern unsigned int k2;
unsigned int i = 0x18;
do
{
  ObfuscatedData[0] ^= k1;
  ObfuscatedData[1] ^= k2;
  k1 = ObfuscatedData[0];
  k2 = ObfuscatedData[1];
  ObfuscatedData += 2;
  --i;
}
while ( i );

Here is a simple brute-force test application I wrote to do some measurements on how long an exhaustive attack would take (suffice it to say, it's unacceptably slow). It contains the blob of data I'm trying to decrypt (along with a test blob I generated myself to verify my code works).

#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstring>

// Code analysis only analyzes single threaded code.
#pragma warning(disable : 6993)

bool ValidateString(std::uint8_t const* beg, std::uint8_t const* end)
{
  // If there are any non-alphanumeric characters (other than a period, due to
  // module name) in the string then it's probably garabge.
  for (std::ptrdiff_t i = 0; i < end - beg && beg[i]; ++i)
  {
    auto const c = beg[i];
    if (!((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') ||
          (c >= 'a' && c <= 'z') || c == '.'))
    {
      return false;
    }
  }

  return true;
}

int main(int /*argc*/, char* /*argv*/ [])
{
  // 6 x 0x20 chunks each containing an obfuscated null-terminated string. The
  // first chunk contains a module name, the rest contain procedure names.
  std::uint8_t const kObfuscatedData[] = {
    0x2E, 0x6B, 0x62, 0x33, 0xF2, 0x0D, 0xB1, 0x96, 0x33, 0x09, 0x1A, 0x74,
    0x79, 0x62, 0xE3, 0x67, 0x72, 0x80, 0x2D, 0x1E, 0xA9, 0x18, 0x0E, 0x4E,
    0xF4, 0xA4, 0x22, 0xF2, 0x68, 0xBE, 0x92, 0x5E, 0xA7, 0x3E, 0x17, 0xBD,
    0xAC, 0xD1, 0x64, 0x20, 0x45, 0xB8, 0x31, 0x1D, 0xE0, 0xD3, 0x86, 0x3C,
    0xC2, 0x4C, 0x75, 0x86, 0xE1, 0x25, 0x9F, 0x19, 0xD1, 0xFC, 0xE3, 0x80,
    0xE3, 0x20, 0x6E, 0x66, 0x56, 0x08, 0xA7, 0x09, 0xE5, 0xD6, 0x64, 0x4E,
    0x20, 0x24, 0x11, 0x2D, 0x16, 0x00, 0x13, 0x37, 0x0A, 0x3C, 0x11, 0x0B,
    0x1C, 0x11, 0x72, 0xAD, 0x99, 0x8B, 0x05, 0x96, 0x25, 0xD4, 0x21, 0x28,
    0xB3, 0x93, 0x05, 0xBD, 0x38, 0xD8, 0x55, 0xC6, 0x23, 0x1C, 0x31, 0xE2,
    0xFB, 0xFD, 0x25, 0xAD, 0x29, 0x4B, 0xFE, 0xA0, 0xC8, 0x3F, 0x3B, 0x50,
    0x4C, 0xDB, 0xF4, 0xEB, 0xDD, 0x78, 0x00, 0x43, 0x46, 0x8C, 0x3B, 0xB5,
    0xEE, 0xAC, 0x0E, 0xDB, 0x37, 0x76, 0x3B, 0xC7, 0x52, 0x74, 0x09, 0x28,
    0x2F, 0xDF, 0x32, 0x1E, 0x75, 0x94, 0xE7, 0x7D, 0x21, 0x77, 0xB2, 0xA2,
    0x93, 0xCD, 0x04, 0xAB, 0x39, 0xDE, 0xBB, 0x6A, 0xBD, 0x2C, 0xFD, 0xFE,
    0x45, 0x50, 0xCC, 0xC6, 0x97, 0x25, 0x26, 0xE0, 0xDA, 0xA6, 0x4B, 0x1A,
    0x11, 0x8C, 0x22, 0x84, 0x73, 0x13, 0x35, 0xF4, 0xA4, 0x80, 0x9C, 0xBA};

#if 0
  // Test data.
  // Chunk 0: SomeModuleName.dLl
  // Chunk 1: FooBarBaz
  // Chunk 2: StupidApiName
  // Chunk 3: ReallyLongStupidApiName
  // Chunk 4: Blah
  // Chunk 5: Wat
  // Key: a = 0x55555557 b = 0xDEADBEEF
  std::uint8_t const kObfuscatedData[] = {
    0x04, 0x3A, 0x38, 0x30, 0xA2, 0xD1, 0xC9, 0xAB, 0x3F, 0x0A, 0x23, 0x04,
    0x20, 0x0A, 0x4A, 0x11, 0x20, 0x09, 0x4E, 0x7F, 0xC4, 0x7D, 0x20, 0x2A,
    0xB8, 0xC8, 0x22, 0xEC, 0xC1, 0xA6, 0x9C, 0x10, 0xB2, 0xCB, 0x4D, 0xB0,
    0x09, 0xCC, 0xD0, 0x3F, 0x3C, 0x6F, 0xD7, 0x5F, 0x81, 0xA1, 0xC4, 0x5D,
    0xB8, 0x4C, 0xCD, 0x9B, 0x01, 0xF6, 0x19, 0x25, 0x13, 0xB0, 0x96, 0x06,
    0x02, 0x05, 0xF1, 0x7F, 0x82, 0x88, 0x96, 0xF0, 0x8A, 0x44, 0x2F, 0x16,
    0x3A, 0x3A, 0x14, 0x1D, 0x0C, 0x64, 0x52, 0x47, 0x63, 0x72, 0x70, 0x66,
    0x79, 0x11, 0x61, 0x9A, 0x93, 0xB7, 0x14, 0x9D, 0x39, 0xC5, 0x53, 0x85,
    0xCB, 0xEE, 0x64, 0xFA, 0x49, 0xAD, 0x6D, 0x47, 0x3C, 0x02, 0x32, 0x18,
    0x19, 0x09, 0x25, 0x0B, 0x2F, 0x17, 0x3A, 0x3A, 0x14, 0x1D, 0x0C, 0x64,
    0x0D, 0xAB, 0x9D, 0xA5, 0xBC, 0x15, 0x65, 0x43, 0x0E, 0xB7, 0x95, 0x83,
    0xDD, 0xD4, 0x0E, 0x98, 0x75, 0x1A, 0x5A, 0xAF, 0x52, 0xD8, 0x07, 0xF3,
    0x18, 0xA9, 0x09, 0xD9, 0x27, 0xE0, 0xEE, 0x55, 0x0E, 0xA8, 0x80, 0xBC,
    0xE6, 0x59, 0xE3, 0xD6, 0x76, 0x16, 0xC6, 0xA2, 0x2E, 0xE1, 0xF9, 0x55,
    0x12, 0x31, 0xB8, 0xC6, 0x2A, 0x09, 0xDB, 0x1E, 0x9F, 0xF6, 0x87, 0xDC,
    0x86, 0xA9, 0x04, 0x64, 0xA9, 0xB5, 0x7E, 0xEE, 0xB5, 0x0C, 0xBE, 0x3E};
#endif

  static_assert(sizeof(kObfuscatedData) == 0xC0, "Invalid data size.");

#pragma omp parallel for
  for (std::int64_t a = 0; a < static_cast<std::uint32_t>(-1); ++a)
  {
    for (std::uint32_t b = 0; b < static_cast<std::uint32_t>(-1); ++b)
    {
      std::uint8_t deobfuscated_data[sizeof(kObfuscatedData)];

      std::uint64_t k =
        static_cast<std::uint64_t>(b) << 32 | static_cast<std::uint64_t>(a);
      for (std::uint32_t i = 0;
           i < sizeof(kObfuscatedData) / sizeof(std::uint64_t);
           ++i)
      {
        auto const o =
          reinterpret_cast<std::uint64_t const*>(&kObfuscatedData[0]);
        auto const d = reinterpret_cast<std::uint64_t*>(&deobfuscated_data[0]);
        d[i] = (k ^= o[i]);
      }

      // Check the chunks which are expected to be procedure names first.
      std::uint32_t kChunkLen = 0x20;
      std::uint32_t kNumChunks = sizeof(kObfuscatedData) / kChunkLen;
      bool valid = true;
      for (std::uint32_t i = 1; i < kNumChunks; ++i)
      {
        // Assume that the first character must be uppercase. Not 100%
        // guaranteed but this simple check results in a large speedup and is
        // probably true.
        auto const chunk_beg = &deobfuscated_data[kChunkLen * i];
        auto const chunk_end = chunk_beg + kChunkLen;
        if (*chunk_beg < 'A' || *chunk_beg > 'Z' ||
            !ValidateString(chunk_beg, chunk_end))
        {
          valid = false;
          break;
        }
      }

      if (!valid)
      {
        continue;
      }

      // Check the module name chunk.
      auto const chunk_beg = &deobfuscated_data[0];
      auto const chunk_end = chunk_beg + kChunkLen;
      if (!ValidateString(chunk_beg, chunk_end))
      {
        continue;
      }

      // Technically the module name passed to LoadLibrary doesn't have to end
      // in .DLL, but the binary the data was extracted from always puts it so
      // I'm assuming it continues to do so here.
      auto const s = reinterpret_cast<char const*>(chunk_beg);
      if (std::strstr(s, ".DLL") || std::strstr(s, ".dll") ||
          std::strstr(s, ".Dll") || std::strstr(s, ".dLl") ||
          std::strstr(s, ".dlL") || std::strstr(s, ".DlL"))
      {
        std::printf("Found candidate key. a = 0x%08X, b = 0x%08X.\n",
                    static_cast<std::uint32_t>(a),
                    b);

        for (std::uint32_t i = 0; i < kNumChunks; ++i)
        {
          std::printf("Chunk %u: %s\n", i, &s[kChunkLen * i]);
        }
      }
    }

    std::printf("Finished outer loop pass for a = 0x%08X.\n",
                static_cast<std::uint32_t>(a));
  }
}

Finally my question... Is there any way I can reduce the keyspace, or somehow just perform a 'smarter' attack in general? My implementation is extremely naive so I suspect/hope there's a better way to go about what I'm trying to do.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is ObfuscatedData an array of integers? $\:$ If yes, how is ObfuscatedData += 2 not a type error? $\;\;\;\;$ $\endgroup$
    – user991
    Apr 30, 2015 at 20:35
  • $\begingroup$ That's how pointer arithmetic in C works. As per the first line in the snippet, ObfuscatedData is a pointer to an array of integers. In C/C++ pointer arithmetic operates based on the size of the type being pointed to. sizeof(unsigned int) == 4, hence ObfuscatedData += 2 advances two elements in the array (8 bytes). Apologies for not making that clearer. $\endgroup$
    – RaptorFactor
    Apr 30, 2015 at 20:42

1 Answer 1

Reset to default
1
$\begingroup$

There's a lot of ways to attack this.

The first thing to notice is that if you know the value of plaintext at index $i$, you can then deduce the value of all the plaintext bytes at index $i+8k$; for all integers $i$ (!).

That's because the relation between plaintext and ciphertext bytes is $P_{i} = C_{i} \oplus P_{i-8}$; if you know $P_{i-8}$ (and, of course, you know $C_{i}$), you know $P_i$ (and, if needed, you can go backwards too).

This gives us the first obvious attack method: you said that the start of the plaintext was a well known DLL name; well, go ahead and list all the DLLs on your system, and try the first 8 bytes of each of those names as the first 8 bytes of the plaintext, use that to decrypt the rest of the ciphertext, and see if it makes sense (based on the rules you know about the plaintext). If it does, well, you've done it.

As for case, well, the difference in case in ASCII is bit 5; the obvious approach is to assume one case, and if you get a string which is terminated by a 0x20 (space) rather than 0x00, then you got the case for the corresponding initial character wrong.

If that doesn't work, there are other possible approaches; let's start off with the easy one first

Improve this answer
$\endgroup$
5
  • $\begingroup$ The reason I hadn't yet tried simply using all the DLL names on my system is due to the fact that path names on Windows are not case sensitive, hence I'd need to check every single possible case permutation of each file name (Foo.dll, FOo.dll, fOo.dLl, etc...). My quick attempt at seeing how expensive that would be with a python script crashed the interpreter due to excessive memory usage... My Python sucks though so I'm going to give it a go with C so I can measure it properly. Thanks! $\endgroup$
    – RaptorFactor
    Apr 30, 2015 at 21:34
  • 1
    $\begingroup$ @RaptorFactor: actually, you don't have to try each possible case permutation individually. Bit 5 of byte $i$ affects only bit 5 in the $i+8k$ bytes, hence it is sufficient to take a guess, and if the resulting decryption makes sense (except for bit 5), then you know you're close. $\endgroup$
    – poncho
    Apr 30, 2015 at 21:40
  • $\begingroup$ Ohh right, now I understand. I'll give that a go. $\endgroup$
    – RaptorFactor
    Apr 30, 2015 at 21:47
  • $\begingroup$ Gave it a try (and verified it was working by dropping a DLL in the target directory which matched my test data) but was unable to find a match. :( $\endgroup$
    – RaptorFactor
    Apr 30, 2015 at 23:25
  • $\begingroup$ @RaptorFactor: if that didn't work, the next obvious thing to attack is that you know that the plaintext has the 5 character string ".dll\x00" near the beginning (except you don't know the case of dll). You can try assume that those 5 bytes occur at offset N (for plausible values of N), and try to decrypt the 5 out of 8 patterns and see what works. One hint is that the ciphertext byte where the 0x00 occurs must be the plaintext byte 8 characters earlier (unless it occurs within the first 8); looking for an alphabetic character early on in the ciphertext might give you a hint where it starts $\endgroup$
    – poncho
    May 1, 2015 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.