光阴冢

We make choices and life has a way of making us pay for them.

RAR 5.0 密码破解

Nov 14, 2017   # Code  # Recording 

实验概述

在这个实验中,我们尝试不使用其他的解密函数库,来破解一个 RAR5.0 格式的压缩文件。通过查阅资料可知,RAR 5.0 的破解没有捷径可循,只能使用尝试的办法进行测试。而提供的 RAR 文件的密码均为4位数。

因此,大致的想法就是使用猜测密码的方式,遍历 0000 - 9999 一共 10000 个密码,验证是否正确。

实验过程

我的实验过程大致分为以下几个阶段:

  1. RAR 5.0 文件格式的了解。
  2. 对于几个核心算法(PBKDF2,HMAC,SHA-256)的思考。
  3. 具体编程。

对RAR 5.0 文件格式的了解

由于不能使用外部的程序,我们必须用二进制的方式读取 RAR 文件。使用 C++ 标准库中的 ifstream可以方便地读取二进制文件。另外写了一个辅助函数,以便以 16 进制逐字节打印该压缩文件。

通过阅读 RAR 官方的文档,可以了解到,RAR 文件由 Archive blocks所组成,每一个 Block 存储的数据与其他相对独立。与解密压缩文件密码最相关的是 Archive encryption header。其数据结构如下:

Content Data Type Description
Header CRC32 uint32
Header size vint
Header type vint 4
Header flags vint Flags common for all headers
Encryption version vint 0 for AES-256.
Encryption flags vint 0x0001   Password check data is present.
KDF count 1 byte Binary logarithm of iteration number for PBKDF2 function.
Salt 16 bytes Salt value used globally for all encrypted archive headers.
Check Value 12 bytes Value used to verify the password validity.

其中 vint 是 RAR 定义的变长整型数据类型。具体如何读不在此赘述。由于我们的 RAR 文件全部都是文件名加密的,因此,根据官方文档描述,在最开始表示 RAR 5.0 格式的 RAR 5.0 signature(8 bytes)之后,就是第一个 Archive encryption header。这也使得阅读数据更简单了。

如下是我读到的前 48 bytes 的数据。

52 61 72 21 1a 07 01 00 da 47 1e fa 21 04 00 00
01 0f dd 9c 1c 17 d1 44 50 03 48 c4 d4 46 ae 17
70 e5 0e e1 7c bf 33 76 5d 58 34 6f cd 2a 61 65

根据文档所述,可以进行分析:

  1. RAR 5.0 Signature

    52 61 72 21 1a 07 01 00
    
  2. CRC32

    da 47 1e fa
    
  3. Size

    21
    
  4. Header Type

    04
    
  5. Header Flag

    00
    
  6. Encrypt Type

    00
    
  7. Encrypt Flag

    01
    
  8. KDF count

    0f
    
  9. Salt

    dd 9c 1c 17 d1 44 50 03 48 c4 d4 46 ae 17 70 e5
    
  10. PSWCheckValue(First 8 bytes)

0e e1 7c bf 33 76 5d 58

在以上值中,最重要的是 Salt,KDF Count 和 PSWCheckValue。这几个值将用来和密码结合,并算出该密码的 CheckValue,与文件中的 PSWCheckValue 比较,验证密码是否能正确解密该文件。

对于几个核心算法的思考

要得到 CheckValue,阅读材料中的论文,可知需要实现 PBKDF2(其中的 PRF 函数使用 HMAC),而 HMAC 中使用的散列函数为 SHA-256。由于具体的算法都有比较详细的文档说明,我在这里只写了遇到的问题以及相关的思考。

  1. PBKDF2

    PBKDF2 是用来生成密钥的算法,循环使用上一次的输出作为输入,然后进行有限次的计算。

    循环次数由 KDF Count 决定,第一次使用的盐是 Salt 拼接 0x0001,之后的使用的盐依赖上一次的输出结果。

    最后通过一些异或运算得到 8 bytes 的 CheckValue。

  2. HMAC

    使用 SHA-256 作为散列函数的 HMAC 接受两个输入,一个是 Password,另一个是 Message。一般的 HMAC 实现中,由于 Password 和 Message 都在变化,因此在输入的时候分别输入,同时进行计算。

    但是在此实验的情况下,每次尝试一个 Password 时,其值是不会变的。也就是因此计算出的临时参数 $T_1$ 和 $T_2$ 在一次 CheckValue 计算中是不变的。故在实现一次 PBKDF2 时,我们可以把可预计算拆开计算,以避免重复。

  3. SHA-256

    SHA-256 是一个散列函数,输入一条长度在 $(2^{64} -1)$ 以内的信息,并输出一条长度为 256 bit 的信息摘要。其中比较重要的是信息填充。由于输入的信息长度并不确定,需要填充成比较规范的形式才能进行下一步的计算。

    首先,在信息后填一个1,及后继的若干个0,使得连同信息的比特长度与(512 - 64) 对 512 同余。再在接下来的 64 bits 中填写源信息的长度。这样完成信息的填充。

    需要注意的一点是,这里填充的长度均是大端序,也就是低位地址存高位字节。而在常见的 x86 处理器均为小端序,在进行信息填充的时候需要多一步处理,避免出错。

编程实现

简要的步骤如下:

  1. 扫描第一个Header,读出 Salt,PswCheckValue,和 KDF Count。
  2. 将密码用 UTF-8 表示。
  3. 实现 PBKDF2 函数,计算出 CheckValue,与文件中的值进行比较。
  4. 如果不符,测试下一个密码,循环 2 - 4 步。直至有匹配的密码或者所有的密码都测试完成。

其中有几个问题需要注意:

  • 由于密码均是数字,包含在 ASCII 中,而 ASCII 为 UTF-8 的真子集,故在 C++ 实现中不需要转换编码。

  • 小端到大端的转换(在填充长度和置数 0x80000000 的时候需要注意)。

  • HMAC 的可预计算,计算好 T1 和 T2。

但是,在使用附件提供的 hmac_sha256_runhmac_sha256_pad 时遇到了一些问题。我的理解是,先将 Password 填充为 512 bits 的长度的信息,然后输入 hmac_sha256_pad 中,计算出中间变量 T1 和 T2,之后,在循环时每次使用将每步的盐再输入到 hmac_sha256_run 中,之后仅循环后一部分即可。我一开始认为是我的信息填充不正确,但是仔细尝试了各种可能性都没能得到正确的结果。

因此,最终使用了网络上的其他计算 hmac_sha256 的代码,但是缺点是,它的每一次计算都需要同时输入 Password 和 Message,这样就使得计算出现了很多重复(如前文所述,每一次的 Password 是一样的)。在此基础上,我将源码进行了修改,最终可以得到正确的结果。

实验结果

成功的案例:

文件错误:

实验心得

本次实验中,我对文件如何在计算机上一个字节一个字节存储有了比较清晰的认识,而且也理解了 C++ 中的指针的本质实际上是字节地址。

指针的类型并不影响数值,而只影响每次读取地址所代表的值时的方式。比如 char* 类型的指针,取值时每次只读取一个字节,但是 unsigned int* 类型的指针,每次读取 4 个字节,并在 x86 机器上是以小端序的方式读入的。

对于二进制文件如何读取也有了一些经验。

除此之外,了解到了加密的一些方法,对于 RAR 的加密部分的流程有了一定的认识。