Encryption

減少對鍊式 64 位異或進行暴力攻擊的密鑰空間

  • April 30, 2015

我有一個數據塊，我知道它是使用鍊式 64 位 xor 加密的（對不起，如果這沒有意義，我不熟悉加密術語）。我對明文應該是什麼樣子略知一二，也知道用於解密數據的算法。

我對數據的了解：

  • 6 x 0x20 大小的“塊”，總大小為 0xC0
  • 第一個塊包含一個 Windows DLL 名稱（例如 foobar.dll），其大小寫未知（並且可能是混合的）。該名稱可能是典型 Windows 安裝中存在的 DLL 的名稱。
  • 其他五個塊每個都包含由上述 DLL 導出的過程的名稱。該名稱可能以大寫字母開頭，因為它是系統 DLL 中的導出。
  • 所有字元串都必須以 null 結尾。
  • 所有字元串都是“窄的”（即每個字元一個字節）。

解密算法如下：

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

這是我編寫的一個簡單的蠻力測試應用程序，用於測量窮舉攻擊需要多長時間（可以說，它的速度慢得令人無法接受）。它包含我要解密的數據塊（以及我自己生成的一個測試塊，以驗證我的程式碼是否有效）。

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

最後我的問題……有什麼辦法可以減少密鑰空間，或者以某種方式只是執行“更智能”的攻擊？我的實現非常幼稚，所以我懷疑/希望有更好的方法來完成我正在嘗試做的事情。

有很多方法可以攻擊它。

首先要注意的是，如果您知道索引處明文的值 $ i $ ，然後可以推導出索引處所有明文字節的值 $ i+8k $ ; 對於所有整數 $ i $ (!).

這是因為明文和密文字節之間的關係是 $ P_{i} = C_{i} \oplus P_{i-8} $ ; 如果你知道的話 $ P_{i-8} $ （當然，你知道 $ C_{i} $ ）， 你知道 $ P_i $ （並且，如果需要，您也可以倒退）。

這給了我們第一個明顯的攻擊方法：你說明文的開頭是一個眾所周知的 DLL 名稱；好吧，繼續列出系統上的所有 DLL，並嘗試將每個名稱的前 8 個字節作為明文的前 8 個字節，用它來解密其餘的密文，看看它是否有意義（根據您了解的有關明文的規則）。如果是這樣，那麼，你已經做到了。

至於大小寫，好吧，ASCII 中大小寫的區別是第 5 位；顯而易見的方法是假設一種情況，如果你得到一個以 0x20（空格）而不是 0x00 結尾的字元串，那麼你得到的相應初始字元的情況是錯誤的。

如果這不起作用，還有其他可能的方法；讓我們先從簡單的開始

引用自：https://crypto.stackexchange.com/questions/25358

相關問答

Encryption

在 XEX 分組密碼模式中添加更多 XOR 層會提高其安全性還是加倍？

  • January 13, 2022
檢視問答
Encryption

如果 Blowfish 沒有被破解，我們為什麼不使用它？

  • December 22, 2021
檢視問答
Encryption

暴力破解最簡單的加密/密碼是什麼？

  • August 25, 2021
檢視問答
Encryption

使用 DHE 的帶有密鑰的簡單 XOR 是否安全？

  • April 18, 2021
檢視問答
Encryption

雜湊作為相互獨立的鍵

  • March 6, 2021
檢視問答
Encryption

破譯密碼能否揭示密鑰？

  • February 23, 2021
檢視問答