[关闭]
@romangol 2014-10-26T15:23:09.000000Z 字数 5457 阅读 2907

Hack.lu 2014 Re400 Cryptochief Writeup

Hack.lu 2014年比赛，我们拿到了全球参赛队伍中第二名的好成绩，在这次比赛的逆向分析题目中，出现了一道逆向分析+密码学误用的综合题目，非常有趣。同时，我们在解题过程中也使用了一些有趣的解法，使得我们在比赛过程中能够比较快速地解开这个题目，特地将这个分析和解题过程写下来与大家分享。

首先，这个题目给出了一个加密解密程序和一个77字节的密文，从程序界面上看不像是专门为比赛开发的程序（想起来浙大ACTF 两个re800的题目……），于是动员Google搜索一下，发现在安全界大哲学家、偶像Bruce Schneier的博客上居然吐槽了这个软件hiahia，说这是个德国民科作品（又想起来看雪上密码学版经常出现的国内密码学民科，人家德国民科好歹还写了个软件，我们的民科连算法都不描述！），根据blog文章和底下一众人的描述（包括一群德国人），大概估计出来这个软件做的是简单的Vernam流密码也就是one time pad。

接下来思路就集中在检查一下该软件的密钥安全性，但是作为一个优秀的软件分析人员，阅读代码前的测试工作必不可少。我们先黑盒测试一下该软件，用相同的keyfile加密两个只相差一字节的文件，发现果然密文只是在对应的位置上出现一个字节的差异。然后选择一些全null字节的明文来加密，想看看密钥流的规律，并没有发现什么特别的问题，感觉生成的keyStream还蛮随机的（这里偷懒没有去测试一下压缩率和entropy了……），遂决定进入调试器时间。

上调试器发现里面很多帮助理解的字符串，再结合调试跟踪一遍，定位到加密过程中几个关键函数

  • 0040451C
  • 00404D92
  • 00405AF4
  • 00423310

然后，我们使用比较简易的人工information flow分析方法：观察外部读入的数据在内存中的流向。这个方法其实非常简单，就是简单的观察输入的数据（一般来说对于文件操作和网络操作型的程序，外部数据都可以事先观察记录下内容）在内存中被整体操作（memcpy或者整体的in-place操作）的情况，然后顺着线索分析下去。
我们根据观察到的线索，给几个关键函数打上如下标签

  • 0040451C
  • 00404D92
  • 00405AF4
  • 00423310

接下来，我们整理一下整个加密流程，发现程序会先执行init_key()和gen_keyStream()，然后重复执行vernam_init() + vernam_xor()三次，而且在vernam_xor()函数中跟踪下去会看到在如下指令

  1. 00405CF6    XOR     EAX, ESI
  2. 00405CF8    MOV     BYTE PTR [EBX], AL

完成了xor加密操作（第一次看到明文变成密文A，第二次看到密文A变成密文B，第三次看到密文B变成密文C，密文C和最后输出的文件相同）。

基本摸清流程后，开始研究如何去攻破这个程序，很自然想到这个程序的问题多半出在key的不安全上，前面说到keyfile扩展出来的keyStream看上去好像没什么问题，而且这个程序是GUI界面每次触发加密解密都要手工操作很烦，所以去仔细检查了代码中keyfile内容到keyStream的过程。首先发现有两个很有意思的memcpy

  1. 00404976   CALL    <JMP.&msvcrt.memcpy>
  2. 00404E68   CALL    <JMP.&msvcrt.memcpy>

根据我们的人肉信息流分析大法简单追踪一下（善用硬件断点），第一个memcpy会复制8个字节的数据给gen_keyStream()用到，而第二个memcpy被gen_keyStream()内部循环调用，每次还是复制8个字节，把它们都留神一下拼接起来（或者关注memcpy的目的地址）就能发现这是接下来的vernam_xor()用到的密钥流。这时候我们会考虑到程序是否把输入变换成了8字节的初始密钥然后来扩展？但是，一般CTF比赛都会选择一些可以在短时间内能暴力破解的问题算法，而8字节输入还是太长而无法枚举，因此我们继续看下去，看看到底这8个字节的输入是如何而来的，我们调试跟踪到

  1. 004050DF   CALL    <JMP.&msvcrt.srand>

此处我们怀疑程序使用了srand来初始化密钥流，然后随后的代码使用rand来产生密钥流，但是接下来的密钥生成算法十分的繁琐，作为比较懒惰的逆向分析人员，我们通常会忽略一些代码实现细节，代之以猜测和实验验证，以加快分析速度。于是我们开始第一个猜测性分析，我们观察到srand的输入只有3字节，而且观察发现它取的是keyfile的头字节、尾字节和长度（这里我们用了一些比较小的keyfile所以长度没超过255，此处srand输入只有3字节说法欠严谨但是我们还是继续往下先分析），这时候我们有理由相信其实输入只有2个字节加上一些长度信息量被置入了密钥伪随机数发生器的熵池中去，所以我们做了实验，给出两个长度相同，头尾字节相同但是中间内容完全不同的keyfile，发现确实对相同的文件，加密出来内容完全一致，因此我们验证了第一个猜想，即确实是程序存在密钥生成问题。

接下来第二个问题很自然的是，如何暴力搜索整个密钥空间然后恢复那个77字节的密文？很多人这时候可能会想到既然明文只有2个字节加上长度这么点信息量来决定keyStream，我们是否可以马上把程序本身的keyGeneration算法还原出来，然后跑一个bruteforce算法就好了？当然可以，但是略显笨拙。我们应该有点耐心的先观察程序的更多特质，首先，我们发现程序加密流程是

  1. A = vernam(input_content, keyA)
  2. B = vernam(A, keyB)
  3. C = vernam(B, keyC)

调试的时候比较容易确定KeyB是一串固定的字符串（我就不想黑这个作者了，大家可以自己去看看这个字符串），keyC虽然没有仔细去看，但是调试多次发现每次都是固定的，因此懒得理睬（后来同伴表示是根据0x1337CAFE作为seed发生出来的），根据我们一贯的做法，凡是程序中固定的操作，我们都可以无视而直接取中间数据使用。因此我们将密文先和keyC与keyB异或得到中间密文。接下来就要搞定的是keyA了。

我们发现程序的keyA生成主要在函数00404FA6处，但是函数本身相当复杂（虽然有ida hexrays但仍然表示逆向能力和耐心都弱得不行），于是大胆地决定把该函数当成黑盒过程（记为keyScheduler）来使用。回到开始的init_key()和gen_keyStream()函数上，观察到init_key()在读取keyfile后，会使用keyScheduler()生成8个字节，然后这8个字节传递给gen_keyStream()，作为初始值去从头开始产生新的密钥流！！！记得我们前面提到过，keyScheduler()函数里面使用了srand配合输入的字节流来作为初始化，并且输出也为8字节，而这时候因为init_key()不管读入什么样的keyfile，提供给gen_keyStream()的输入字节总是固定的8字节！！！因此，我们再一次将输入空间缩小到了2个字节（输入的头、尾字节，长度固定为8）！！！

接下来就是另一个技巧性的工作，如何去枚举所有0x10000种输入可能性产生所有的值，一般会想到阅读理解代码然后自己重新实现，但是我们这里观察发现就地patch代码也是可行的，下面是我们认为比较巧妙的patching code，注意到从004044CF开始全部是我们的patch:

  1. 004044BA  MOV     DWORD PTR [ESP+8], EBX ; 参数3
  2. 004044BE  MOV     DWORD PTR [ESP+4], ESI ; 参数2，指向输入的8字节
  3. 004044C2  MOV     DWORD PTR [ESP], EDX ; 参数1
  4. 004044C5  MOV     ECX, EAX ; 参数0，指向输出的8字节
  5. 004044C7   CALL    <gen_keyStream>
  6. 004044CC   SUB     ESP, 0C
  7. 004044CF   MOV     ECX, EAX ; 恢复参数0（观察发现EAX寄存器不会变）
  8. 004044D1   MOV     EBP, EDI ; 利用用不到的EDI寄存器来做一个计数器从0到0x10000循环
  9. 004044D3   AND     EBP, 0FF
  10. 004044D9   MOV     DWORD PTR [3E74E0], EBP ; 将计数器的低位放入输入的8字节的头字节（注意这里硬编码了地址）
  11. 004044DF   MOV     EBP, EDI
  12. 004044E1   SHR     EBP, 8
  13. 004044E4   MOV     DWORD PTR [3E74E7], EBP ; 将计数器的低位放入输入的8字节的尾字节（注意这里同样硬编码了地址）
  14. 004044EA   INC     EDI
  15. 004044EB   JMP     SHORT 004044C7 ; !!! 强制gen_keyStream重新执行

也许你会问，你这样第一产生了一个死循环，第二哪里提取了数据？别急我们动用了odbgscript脚本，非常简单的几句话

  1. var ptr
  3. gogogo:
  4. run
  5. mov ptr, [eax]
  6. dma ptr, 8, "test.bin"
  7. cmp edi, 10000
  8. jne gogogo

将每次产生的8字节输入dump出来！！！这样我们得到了keyScheduler在输入为8字节的情况下（其实是所有2字节）的完整输入输出关系映射表！！！通过输入输出关系的映射表，我们就能产生出所有密钥流（这里就说明了该软件的最大问题：最多只能产生0x10000个不同的密钥流，何谓安全？）

于是接下来给出分析程序，其实这里还有一个小小的坑，分析时忽略了，实际调试验证时候才发现，那就是8字节的输出在用来做下一次密钥流生成迭代前，会有一个mask操作，在代码中可以看到，我们偷懒只对头字节和尾字节做了操作~（这也说明了这个算法的问题，中间的6个字节都没用嘛！！！）

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "md5_xty.h"
  5. unsigned long long Table[0x10000];
  7. size_t Len = 10;
  9. /* 此处的数据是直接从中间运行过程中dump出来的，并非原始的secret.krytpo */
  10. unsigned char cipher[] = 
  11. {
  12. 0x41, 0xA8, 0xA0, 0xCF, 0x61, 0xFD, 0xC1, 0x6F, 0x31, 0x53, 
  13. 0x70, 0xEA, 0xE6, 0x19, 0x26, 0x64, 0xFA, 0x74, 0x3B, 0x51, 
  14. 0x72, 0x2D, 0x6E, 0xAA, 0x34, 0x66, 0x23, 0x63, 0xD4, 0x4C, 
  15. 0x0C, 0x7D, 0x60, 0x15, 0x72, 0x12, 0xF6, 0xA5, 0xA6, 0x40, 
  16. 0xD7, 0x71, 0x75, 0x86, 0x65, 0xDB, 0xA2, 0x71, 0xB5, 0x82, 
  17. 0x13, 0xAC, 0x0E, 0x38, 0x11, 0xD0, 0x43, 0x61, 0x1F, 0x5C, 
  18. 0x2E, 0xB7, 0x60, 0x4D, 0x60, 0x79, 0xA1, 0xDD, 0xDC, 0x7B, 
  19. 0x74, 0x6C, 0xB8, 0x76, 0x38, 0x23, 0x97
  20. };
  23. int main( int argc, char *argv[] )
  24. {
  25.     static unsigned char keyStream[80];
  26.     static unsigned char rKeyStream[80];
  27.     FILE * fp = fopen("test.bin", "rb");
  29.     static union
  30.     {
  31.         unsigned int d[4];
  32.         unsigned char digest[16];
  33.     } roman;
  35.     fread( &Table, sizeof(Table), 1, fp );
  37.     for ( unsigned int init = 0; init < 0x10000; ++init)
  38.     {   
  39.         unsigned int next = init;
  40.         for ( size_t i = 0; i < Len; ++i )
  41.         {
  42.             memcpy( keyStream + i * 8, Table + next, 8 );
  43.             memcpy( rKeyStream + i * 8, Table + next, 8 );
  45.             keyStream[i * 8 + 7] += 7 % (i + 2);
  46.             if ( 1 == i % 2 )
  47.             {
  48.                 keyStream[i * 8 + 0] ^= 0xFF;
  49.                 keyStream[i * 8 + 7] ^= 0xFF;
  50.             }
  52.             next = keyStream[i * 8] + 0x100 * keyStream[i * 8 + 7];
  53.         }
  55.         for ( size_t i = 0; i < sizeof(cipher); ++i )
  56.             keyStream[i] = cipher[i] ^ rKeyStream[i];
  58.         MD5_Text( keyStream, 77, roman.digest );
  60.         if ( roman.d[0] == 0x19cea02a && roman.d[1] == 0x87a626d6 && roman.d[2] == 0xf6557251 && roman.d[3] == 0x40764e8e )
  61.         {
  62.             for ( size_t i = 0; i < sizeof(cipher); ++i )
  63.                 printf("%c", keyStream[i]);
  64.             puts("=========");
  65.         }
  67.     }
  69.     fclose(fp);
  70.     return 0;
  71. }

最后给出flag

You made it!
flag{Y34h_Lucky_Luk3_Cr4ck5_B4dCryp70_F4573r_T45n_H15_5h4d0w}

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注