破解LedgerCTF的AES白盒挑战
引言
大约一个月前，我的伙伴b0n0n正在研究ledgerctf谜题，并邀请我查看ctf2二进制文件。我最终接受了挑战，本文将讨论该保护方案及其破解过程。在深入之前，先提供一些背景信息。
ledger是一家成立于2014年的法国安全公司，专注于密码学、加密货币和硬件。他们最近上线了三个不同的谜题，以庆祝其漏洞赏金计划的正式启动。第二个挑战名为ctf2，正是我们今天要讨论的对象。ctf2是一个ELF64二进制文件，可在此处下载（如果你想跟随操作）。该二进制文件约11MB，用C++编写，甚至包含符号信息，这很好。
让我们开始吧！
概览
侦察
首先，你肯定注意到了二进制文件中包含大量数据，如下图所示。这意味着要么二进制文件被压缩且IDA难以识别代码片段，要么这些确实是真实数据。
由于我们已经知道二进制文件未被剥离，第一种假设很可能不成立。通过浏览反汇编器中的代码，没有发现明显异常；一切看起来都很健康。没有混淆、代码加密或任何形式的压缩迹象。此时，我们基本确定这是一个纯逆向工程挑战，一帆风顺！
扩散
二进制文件期望输入一个序列，即由32个十六进制字符组成的字符串，例如：00112233445566778899AABBCCDDEEFF。然后，有一个包含16轮的循环，逐字符遍历序列，并构建15个各16字节的块，我称之为i0、i1、…、i14（这非常直观）。该循环的每一轮初始化每个i的一个字节（因此共16轮）。当前输入的序列字节通过一个巨大的替换盒（我称为sbx，大小为11534336字节）进行处理。这基本上将输入序列扩散到这些块中。如果上述解释不够清晰，以下是美化后的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字节的块（分别称为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;
// ... 更多混合操作
|
mul2和mul3基本上是构造的数组，使得在GF(2**8)内mul2[idx] = idx * 2且mul3[idx] = idx * 3。
一个可能有趣的点是，这里有一个小的反调试机制。文件被打开并使用std::vector的构造函数读取，该构造函数接受std::ifstreambuf_iterator作为输入。生成某种校验和，并将在稍后的调度例程中使用。这意味着如果你修补二进制文件，算法最终将生成错误的值。同样，这几乎不构成障碍，因为我们可以直接转储它并继续。
生成
此时，上述15个i用于初始化我称为s0、s1、…、s14的块。同样，这是15个各16字节的块。它们被传递给调度函数，该函数将在s数组上执行大量算术操作。同样，目前无需理解调度函数；就我们而言，它是一个黑盒，接受s作为输入并返回不同的s作为输出。
每个这16字节（方便的是，XMM寄存器是16字节长，允许编译器优化操作这些块的代码）（s0、…、s14）被异或在一起，如果结果的xmm字满足一系列约束，则显示成功消息。
这些约束如下所示：
1
2
3
4
5
|
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);
h2 = mxor.m128i_u8[2] | ((mxor.m128i_u8[6] | ((mxor.m128i_u8[10] | ((mxor.m128i_u8[14] | ((mxor.m128i_u8[3] | ((mxor.m128i_u8[7] | ((mxor.m128i_u8[11] | ((unsigned __int64)mxor.m128i_u8[15] << 8)) << 8)) << 8)) << 8)) << 8)) << 8)) << 8);
if ( BYTE6(h2) == 'i'
&& BYTE5(h2) == '7'
// ... 更多约束
|
这堆垃圾简单地转化为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变量的轮数，使用了一个名为scheduling的数组。当每个s应用了四十轮后，算法停止。还值得注意的是，这里有一个小的反调试机制；一轮开始时启动计时器（t1），结束时停止（t2）。如果发现t1和t2之间的任何异常延迟，后续计算将产生错误结果。
我们在switch case中观察到6种不同类型的操作。其中一些看起来很容易反转，而另一些则需要更多工作。但此时，这让我想起了2013年分析的一个AES白盒。这个没有混淆，使得处理起来容易得多。我当时做的是非常简单的：分而治之。我将每轮分解为四个部分。每个四分之一轮作为一个黑盒函数，接受4字节输入并生成4字节输出（因此每轮生成16字节/128位）。我需要找到能生成所需输出的4字节输入。解决这些四分之一可以同时进行，从期望的输出开始，你可以从第N轮回溯到第N-1轮。这基本上是我对ctf2的计划。
此时，我已经将调度函数提取到自己的程序中。我清理了代码，并确保它产生与程序本身相同的结果（调试总是有趣的）。换句话说，我已经准备好继续分析所有算术轮。
case 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);
}
|
case 1, 5, 9, 13, 17, 21, 25, 29, 33, 37: SubBytes
这个案例相比前一个可能看起来更令人畏惧（笑）。清理和美化后如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
case 1:
case 5:
// ... 其他case
{
v54 = nround >> 2;
v55 = Slot->m128i_u8[0];
v77.m128i_u64[0] = mask.m128i_u8[0];
v56 = v54;
v54 <<= 20;
v79 = mask.m128i_u8[1];
v81 = mask.m128i_u8[2];
v57 = &sboxes[256 * (v55 + (v56 << 12))];
// ... 更多初始化
Slot->m128i_u8[0] = v57[mask.m128i_u8[0]];
// ... 其他字节赋值
*Slot = _mm_xor_si128(*Slot, crc);
break;
}
|
我始终关注的是：输入和输出字节之间的关系。请记住，每轮作为一个函数，接受一个16字节的块输入（我的代码中的Slot_t）并返回另一个16字节的块作为输出。由于我们感兴趣的是编写一个能生成特定输出的输入的函数，识别输出如何构建以及使用哪些输入字节来构建它非常重要。
让我们仔细看看输出的第一个字节是如何生成的。我们从函数末尾开始，回溯引用直到遇到输入状态的字节。在这种情况下，我们回溯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输出状态，会污染你的结果，狡猾：）。
case 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
{
v42 = Slot->m128i_u8[6];
v43 = Slot->m128i_u8[4];
v44 = Slot->m128i_u8[5];
Slot->m128i_u8[6] = Slot->m128i_u8[7];
Slot->m128i_u8[5] = v42;
// ... 更多交换操作
break;
}
|
通过快速查看该函数，你理解到它是某种洗牌操作。出于某种原因，这是我不擅长的脑力体操。我通常使用的技巧是给它一个如下所示的输入：\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);
}
|
下一个！
case 3, 7, 11, 15, 19, 23, 27, 31, 35: MixColumns
这个案例基本上是最烦人的。乍一看，它看起来非常类似于我们之前分析的case 1，但…不完全一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
case 3:
case 7:
// ... 其他case
{
v7 = Slot->m128i_u8[0];
v8 = Slot->m128i_u8[4];
v9 = Slot->m128i_u8[1];
v10 = Slot->m128i_u8[5];
v11 = Slot->m128i_u8[14] ^ Slot->m128i_u8[10];
v12 = mul3[v8] ^ mul2[v7] ^ Slot->m128i_u8[12] ^ Slot->m128i_u8[8];
// ... 更多计算
Slot->m128i_u8[0] = v78x;
Slot->m128i_u8[1] = v79x;
// ... 其他字节赋值
break;
}
|