本月初我写了一篇文章“加密的压缩包”,说是一道 CTF 题需要根据已知的 CRC32 值反向破解文本文件(6 bytes)的内容。当时是暴力破解。总共需要破解 3 个 CRC32 值,暴力破解 1 个 CRC32 值平均需要 5 个多小时,还好我的计算机有 4 个逻辑 CPU,可以同时破解这 3 个 CRC32 值。

后来,根据我同事的解题方法,知道可以计算 CRC32 的逆函数。我们把明文存储在一个长度为 6 的 byte 数组中,该数组的前 2 个字节遍历所有可能的明文字符,然后根据给定的 CRC32 值(以及该数组的前 2 个字节)计算逆函数,填入该数组的后 4 个字节,然后判断它们是否在明文字符范围内。这个方法只需要 0.1 秒。

  • 暴力破解的计算量:656 = 75,418,890,625
  • 计算逆函数计算量:652 = 4225

这个方法如下所示:

$ csc reversecrc32.cs ~/src/apps/lib/Crc32.cs
$ mono reversecrc32.exe 4B10DEBA
$ mono reversecrc32.exe 1FD8A07A
$ mono reversecrc32.exe E7F7E18C

当然,明文的长度不必须是 6 个字符,不论是上篇文章的暴力破解,还是这篇文章的计算 CRC32 的逆函数,都很容易修改以适应其他明文长度,或者明文有特定的前缀或后缀等情况。

下面是相应的 C# 源程序:

reversecrc32.cs:

using System;
using System.Text;
using System.Collections.Generic;
using Skyiv.Utils;

static class ReverseCrc32
{
  static readonly Encoding ascii = new ASCIIEncoding();
  static readonly HashSet<byte> a = new HashSet<byte>();

  static ReverseCrc32()
  {
    for (var i = '0'; i <= '9'; i++) a.Add((byte)i);
    for (var i = 'A'; i <= 'Z'; i++) a.Add((byte)i);
    for (var i = 'a'; i <= 'z'; i++) a.Add((byte)i);
    a.Add((byte)'+'); a.Add((byte)'/'); a.Add((byte)'=');
  }

  static bool Valid(byte[] bs)
  {
    foreach (var b in bs) if (!a.Contains(b)) return false;
    return true;
  }

  static void Main(string[] args)
  {
    var z = Convert.ToUInt32(args[0], 16);
    var bs = new byte[6];
    foreach (var i in a)
      foreach (var j in a) {
        bs[0] = i; bs[1] = j;
        bs.ReverseCrc32(z, 2);
        if (Valid(bs)) Console.WriteLine("{0}", ascii.GetString(bs));
      }
  }
}

Crc32.cs:

using System;
using System.Linq;
using System.Collections.Generic;

namespace Skyiv.Utils
{
  public static class Crc32
  {
    static readonly uint[] t1 = new uint[256];
    static readonly uint[] t2 = new uint[256];

    static Crc32()
    {
      uint p = 0xEDB88320;
      for (uint f, r, j, i = 0; i < t1.Length; t1[i] = f, t2[i] = r, i++)
        for (f = i, r = i << 24, j = 8; j > 0; j--) {
          f = ((f & 1) == 0) ? (f >> 1) : ((f >> 1) ^ p);
          r = ((r & 0x80000000) == 0) ? (r << 1) : (((r ^ p) << 1) | 1);
        }
    }

    public static void ReverseCrc32(this byte[] bs, uint crc, int n)
    {
      if (bs.Length < n + 4) return;
      uint z = 0xFFFFFFFF;
      for (int i = 0; i < n; i++) z = (z >> 8) ^ t1[(z ^ bs[i]) & 0xFF];
      Array.Copy(BitConverter.GetBytes(z), 0, bs, n, 4);
      z = crc ^ 0xFFFFFFFF;
      for (int i = bs.Length-1; i >= n; i--) z = (z<<8)^t2[z>>24]^bs[i];
      Array.Copy(BitConverter.GetBytes(z), 0, bs, n, 4);
    }

    public static uint GetCrc32<T>(this IEnumerable<T> bs)
    {
      return ~bs.Aggregate(0xFFFFFFFF, (r, b) =>
        (t1[(r & 0xFF) ^ Convert.ToByte(b)] ^ (r >> 8)));
    }
  }
}

参考资料

  1. GitHub: CRC32 tools: reverse, undo/rewind, and calculate hashes
  2. Daniel's Software Blog: Calculating Reverse CRC