攻破LedgerCTF的AES白盒挑战：逆向工程与密码学分析

本文详细解析了如何通过逆向工程和密码学技术攻破LedgerCTF的AES白盒挑战，包括二进制分析、算法逆向和密钥恢复过程，最终生成有效序列实现登录成功。

攻破LedgerCTF的AES白盒挑战

引言

大约一个月前，我的伙伴b0n0n正在研究ledgerctf谜题，并挑战我查看ctf2二进制文件。最终我接受了挑战，本文讨论了保护方案以及我如何破解它。在深入之前，先提供一些背景信息。

ledger是一家成立于2014年的法国安全公司，专注于密码学、加密货币和硬件。他们最近在线上发布了三个不同的谜题，以庆祝其漏洞赏金计划的正式启动。第二个挑战称为ctf2，我们今天将讨论它。ctf2是一个ELF64二进制文件，可在此处下载（如果你想跟随操作）。该二进制文件大约11MB，用C++编写，甚至包含符号；很好。

开始吧！

目录

  • 引言
  • 整体概览
    • 侦察
    • 扩散
    • 混淆
    • 生成
  • 深入分析
    • 调度
    • 案例0：编码
    • 案例1、5、9、13、17、21、25、29、33、37：SubBytes
    • 案例2、6、10、14、18、22、26、30、34、38：ShiftRows
    • 案例3、7、11、15、19、23、27、31、35：MixColumns
    • 案例4、8、12、16、20、24、28、32、36：AddRoundKey
    • 案例39：解码
  • 反轮
  • 如何获胜？
  • 结论

整体概览

侦察

首先，你肯定已经注意到二进制文件中包含大量数据，如下图所示。这意味着二进制文件要么是打包的，IDA难以识别代码部分，要么确实是真实数据。

由于我们已经知道二进制文件未被剥离，第一种假设很可能错误。通过浏览反汇编器中的代码，没有发现异常；一切看起来健康。没有混淆、代码加密或任何类型的打包迹象。此时我们确信这是一个纯粹的反向工程挑战，一帆风顺！

扩散

二进制文件期望一个序列作为输入，该序列是由32个十六进制字符组成的字符串，例如：00112233445566778899AABBCCDDEEFF。然后，有一个包含16轮的循环，逐字符遍历序列并构建15个 blob，每个16字节长；我称它们为i0、i1、…、i14（这非常自解释）。此循环的每一轮初始化每个i的一个字节（因此有16轮）。当前输入序列字节通过一个巨大的替换盒（我称为sbx，长度为11534336字节）发送。这基本上将输入序列扩散到这些blob中。如果上述解释不够清晰，以下是美化后的C代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

while(Idx < 16) {
  sbx++;
  char CurrentByteString[3] = {
    Serial[Idx],
    Serial[Idx + 1],
    0
  };
  Idx += 2LL;
  uint8_t CurrentByte = strtol(CurrentByteString, 0LL, 16);
  i0[sbx[-1]] = CurrentByte;
  i1[sbx[15]] = CurrentByte;
  i2[sbx[31]] = CurrentByte;
  i3[sbx[47]] = CurrentByte;
  i4[sbx[63]] = CurrentByte;
  i5[sbx[79]] = CurrentByte;
  i6[sbx[95]] = CurrentByte;
  i7[sbx[111]] = CurrentByte;
  i8[sbx[127]] = CurrentByte;
  i9[sbx[143]] = CurrentByte;
  i10[sbx[159]] = CurrentByte;
  i11[sbx[175]] = CurrentByte;
  i12[sbx[191]] = CurrentByte;
  i13[sbx[207]] = CurrentByte;
  i14[sbx[223]] = CurrentByte;
}

混淆

之后，发生了一堆事情，目前不一定有太多意义。但就我而言，这还不关心，因为我还没有看到与输入序列字节或i的明确关系。由于这两者是唯一用户输入派生的数据，目前我只关心这些。

接下来，我们遇到这段代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

do
{
  v16 = v15 + 4;
  do
  {
    rd = rand();
    v18 = (unsigned __int8)(((unsigned __int64)rd >> 56) + rd) - ((unsigned int)(rd >> 31) >> 24);
    mask[v15] = v18;
    mask3[v15] = v18;
    shiftedmask[v15++] = v18;
  }
  while ( v15 != v16 );
}
while ( v15 != 16 );

我从这部分学到的是，有新玩家加入。基本上，三个16字节的blob，分别称为mask、mask3和shiftedmask，使用从rand()派生的值进行初始化。起初，看到伪随机值参与其中确实有点令人困惑，但我们可以假设这些操作稍后会被其他操作取消。让一些类似加密的算法产生非确定性结果是没有意义的。PRNG使用time(NULL)进行种子设置。

之后还有其他一些我们不关心的操作。你可以将它们视为黑盒，生成确定性输出。这意味着我们可以在需要时方便地转储生成的值。值得一提的是，它基本上在mask3内部混合了一堆值。

1
2
3
4

shiftrows((unsigned __int8 (*)[4])shiftedmask);
shiftrows((unsigned __int8 (*)[4])mask3);
v19 = mul3[(unsigned __int8)byte_D03774] ^ mul2[mask3[0]] ^ byte_D03778 ^ byte_D0377C;
// ... 更多操作

mul3和mul2基本上是数组，构造为mul2[idx] = idx * 2和mul3[idx] = idx * 3在GF(2**8)中。

一个可能有趣的事情是，其中有一个小的反调试。文件被打开并使用std::vector的构造函数读取，该构造函数接受std::ifstreambuf_iterator作为输入。生成某种校验和，并将在稍后的调度例程中使用。这意味着如果你要修补二进制文件，算法最终会生成错误的值。同样，这几乎不是一个不便，因为我们可以将其转储并继续我们的生活。

生成

此时，上述15个i用于初始化我称为s0、s1、…、s14的内容。再次，这是15个blob，每个16字节。它们被传递给调度函数，该函数将在s数组上执行大量算术操作。再次，尚不需要理解调度；就我们而言，它是一个黑盒，接受s作为输入并返回不同的s作为输出，句点。

每个这些16字节（方便的是，XMM寄存器是16字节长，允许编译器优化操作这些blob的代码）（s0、…、s14）被异或在一起，如果结果的xmmword遵守一堆约束，那么你会得到好消息。

这些约束看起来像这样：

1
2

h1 = mxor.m128i_u8[0] | ((mxor.m128i_u8[4] | ((mxor.m128i_u8[8] | ((mxor.m128i_u8[12] | ((mxor.m128i_u8[1] | ((mxor.m128i_u8[5] | ((mxor.m128i_u8[9] | ((unsigned __int64)mxor.m128i_u8[13] << 8)) << 8)) << 8)) << 8)) << 8)) << 8)) << 8);
// ... 更多约束

这垃圾简单地转化为win = (mxor == 0x42424242696969693737373713131313ULL) :)。

深入分析

现在是时候深入并动手一点了。我们有点知道我们需要实现什么，但我们不确定如何到达那里。我们知道我们需要进行一些转储：mask、mask3、shiftedmask、crc、sbx、mul2和mul3。容易。机械。

最重要的未知部分是更多地理解调度。你可以将其视为挑战的核心。所以让我们这样做。

调度

乍一看，该函数看起来并不太糟糕，这总是好的。该函数的第一部分是随机选择s变量之一（变量i用于索引状态数组，其中所有s都在）。

1
2

for(i = rand() % 15; scheduling[i] == 40; i = rand() % 15);
nround = scheduling[i];

随后的switch case对选定的s变量应用一种类型的转换（算术转换）。为了跟踪已应用于每个s变量的轮数，使用了一个称为调度的数组。当四十轮已应用于每个s时，算法停止。还值得指出的是，这里有一个小的反调试；一轮开始时启动计时器（t1），结束时停止（t2）。如果发现t1和t2之间的任何异常延迟，后续计算将产生错误结果。

我们可以在switch case中观察到6种不同类型的操作。其中一些看起来非常容易反转，而其他一些则需要更多工作。但在这一点上，它让我想起了我在2013年分析过的这个AES白盒。这个没有任何混淆，这使得处理起来容易得多。我当时做的是非常简单：分而治之。我将每轮分解为四个部分。每个这些四分之一轮作为一个黑盒函数，接受4字节输入并生成4字节输出（因此每轮将生成16字节/128位）。我需要找到4字节输入，这将给我想要的4字节输出。解决这些四分之一可以同时完成，从所需的输出开始，你可以从第N轮走回第N-1轮。这基本上是我对ctf2的计划。

此时，我已经将调度函数提取到我自己的程序中。我清理了代码并确保它产生与程序本身相同的结果（总是有趣的调试）。换句话说，我准备继续分析所有算术轮。

案例0：编码

这个案例非常简单，如下所示：

1
2
3

case 0:
  s0[i] = _mm_xor_si128(_mm_load_si128(&s0[i]), *(__m128i *)mask);
  break;

因此，反转它是一个简单的XOR操作：

1
2
3

void reverse_0(Slot_t &Output, Slot_t &Input) {
    Input = _mm_xor_si128(_mm_load_si128(&Output), mask);
}

案例1、5、9、13、17、21、25、29、33、37：SubBytes

这个案例与上一个相比可能看起来更令人生畏（笑）。一旦我清理并美化它，它看起来像这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

case 1:
case 5:
case 9:
case 13:
case 17:
case 21:
case 25:
case 29:
case 33:
case 37: {
    // ... 代码细节
}

我总是关注的是：输入和输出字节之间的关系。请记住，每轮作为一个函数，接受16字节blob输入（我的代码中的Slot_t）并返回另一个16字节blob作为输出。由于我们感兴趣的是编写一个可以找到生成特定输出的输入的函数，因此识别输出如何构建以及使用哪些输入字节来构建它非常重要。

让我们仔细看看输出的第一个字节是如何生成的。我们从函数末尾开始，并回溯引用，直到遇到输入状态的字节。在这种情况下，我们回溯v57的来源，然后v55和v56。v55是输入状态的第一个字节，很好。v56是一个编码轮数的数字。我们现在不一定关心它，但意识到轮数是此函数的一个参数是好的；而不仅仅是输入字节。好的，所以我们知道输出的第一个字节是通过输入的第一个字节构建的，容易。比我在查看Hex-Rays输出时最初预期的要简单。但我会接受简单:)。

如果你对每个字节重复上述步骤，你基本上会意识到输出的每个字节依赖于输入的一个字节。它们都彼此独立，这甚至更好。这意味着我们可以非常容易地暴力破解输入值以生成特定的输出值。这很好，因为它…非常便宜计算；如此便宜，我们甚至不麻烦，我们继续下一个案例。

理论上，我们甚至可以并行化以下内容，但可能不值得这样做，因为已经很快。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void reverse_37(const uint32_t nround, Slot_t &Output, Slot_t &Input) {
    uint8_t is[16];
    for (uint32_t i = 0; i < 16; ++i) {
        for (uint32_t c = 0; c < 0x100; ++c) {
            Input.m128i_u8[i] = c;
            round(nround, &Input);
            if (Input.m128i_u8[i] == Output.m128i_u8[i]) {
                is[i] = c;
                break;
            }
        }
    }
    memcpy(Input.m128i_u8, is, 16);
}

有趣的是，如果你修补了挑战二进制文件，这是另一个事情会出错的地方。crc值在函数末尾用于XOR输出状态，并会污染你的结果 here，狡猾:)。

案例2、6、10、14、18、22、26、30、34、38：ShiftRows

不错，我们已经弄清楚了六种案例中的两种。这个案例看起来也不坏，它非常短，编写反转看起来足够容易：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

case 2:
case 6:
case 10:
case 14:
case 18:
case 22:
case 26:
case 30:
case 34:
case 38: {
    // ... 代码细节
}

显然，通过快速查看此函数，你理解它是某种洗牌操作。出于某种原因，这是我不擅长的脑力体操。我通常使用的技巧是给它一个看起来像这样的输入：\x00\x01\x02\x03…并观察结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void test_reverse38() {
    const uint8_t Input[16] {
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f
    };
    Slot_t InputSlot;
    memcpy(&InputSlot.m128i_u8, Input, 16);
    round(38, &InputSlot);
    hexdump(stdout, &InputSlot.m128i_u8, 16);
}

如果我们应用上述技巧，我们得到：

1

0000:   00 01 02 03 05 06 07 04   0A 0B 08 09 0F 0C 0D 0E    ................

从这里，更容易（至少对我而言）弄清楚洗牌的效果。例如，我们已经知道我们不需要对前四个字节做任何事，因为它们没有被洗牌。我们知道我们需要取Output[7]并将其放入Input[4]，Output[4]放入Input[5]，依此类推。经过一点脑力体操，我最终得到这个例程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void reverse_38(Slot_t &Output, Slot_t &Input) {
    uint8_t s4 = Output.m128i_u8[4];
    Output.m128i_u8[4] = Output.m128i_u8[7];
    uint8_t s5 = Output.m128i_u8[5];
    Output.m128i_u8[5] = s4;
    uint8_t s6 = Output.m128i_u8[6];
    Output.m128i_u8[6] = s5;
    uint8_t s7 = Output.m128i_u8[7];
    Output.m128i_u8[7] = s6;
    uint8_t s8 = Output.m128i_u8[8];
    Output.m128i_u8[8] = Output.m128i_u8[10];
    uint8_t s9 = Output.m128i_u8[9];
    Output.m128i_u8[9] = Output.m128i_u8[11];
    Output.m128i_u8[10] = s8;
    Output.m128i_u8[11] = s9;
    uint8_t s12 = Output.m128i_u8[12];
    Output.m128i_u8[12] = Output.m128i_u8[13];
    uint8_t s13 = Output.m128i_u8[13];
    Output.m128i_u8[13] = Output.m128i_u8[14];
    Output.m128i_u8[14] = Output.m128i_u8[15];
    Output.m128i_u8[15] = s12;
    memcpy(Input.m128i_u8, Output.m128i_u8, 16);
}

下一个！

案例3、7、11、15、19、23、27、31、35：MixColumns

这个案例基本上是最烦人的一个。乍一看，它看起来非常类似于我们之前分析的案例1，但…不完全相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

case 3:
case 7:
case 11:
case 15:
case 19:
case 23:
case 27:
case 31:
case 35: {
    // ... 代码细节
}

这次如果我们仔细看，我们注意到每四个字节的输出依赖于四个字节的输入。并且那四个输出字节的每个字节都依赖于那四个输入字节。

这意味着你不能像之前那样逐字节暴力破解。你必须暴力破解四个字节…这比我们上面看到的要昂贵得多。我们唯一的好处是我们可以并行暴力破解它们，因为它们彼此独立。每个一个线程应该可以完成工作。

在这个阶段，我已经在各种错误或愚蠢的事情上浪费了一堆时间；所以我决定编写这个非常简单的天真暴力破解函数（它既不漂亮也不快…但此时我已经与它和平相处）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void reverse_35(Slot_t &Output, Slot_t &Input) {
    uint8_t final_result[16];
    std::thread t0([Input, Output, &final_result]() mutable {
        for (uint64_t a = 0; a < 0x100; ++a) {
            for (uint64_t b = 0; b < 0x100; ++b) {
                for (uint64_t c = 0; c < 0x100; ++c) {
                    for (uint64_t d = 0; d < 0x100; ++d) {
                        Input.m128i_u8[0] = uint8_t(a);
                        Input.m128i_u8[4] = uint8_t(b);
                        Input.m128i_u8[8] = uint8_t(c);
                        Input.m128i_u8[12
comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次