CTF逆向实战：TEA算法变种的识别、分析与破解

1. 项目概述从一道CTF题看TEA算法变种的攻防最近在复盘一场CTF比赛的逆向题又遇到了老朋友——TEA算法。不过这次它穿了件“马甲”是个变种。题目给了一个32位的Windows控制台程序运行后让你输入flag然后告诉你对错。拖进IDA一看主函数逻辑清晰关键验证逻辑在一个叫check_flag的函数里。这个函数里有一堆移位、异或、加法和一个巨大的常量0x9E3779B9熟悉的味道扑面而来这就是TEATiny Encryption Algorithm没跑了。但仔细一看它的轮函数结构、密钥调度方式又和标准TEA有些许不同这就是典型的“变种”套路旨在增加逆向分析的难度。对于CTF逆向选手尤其是刚入门的朋友遇到加密算法常常会发怵。识别算法是第一步也是最关键的一步。一旦认出来是TEA及其家族XTEA, XXTEA就等于拿到了解题的钥匙。今天我就以这道题为例手把手带你走一遍完整的流程从静态分析识别算法特征到动态调试验证猜想最后编写Python脚本进行爆破把flag给揪出来。整个过程我会把踩过的坑、总结的技巧都揉进去目标是让你看完后不仅能解这道题更能掌握一套对付TEA类算法的通用方法论。2. TEA算法核心原理与变种识别2.1 标准TEA算法速览TEA算法由剑桥大学的David Wheeler和Roger Needham设计以其简洁和高效著称。它是一种分组密码使用64位8字节为一个明文分组128位16字节密钥采用Feistel结构。它的核心加密轮函数非常简洁通常表述为for (int i 0; i rounds; i) { sum delta; v0 ((v1 4) k0) ^ (v1 sum) ^ ((v1 5) k1); v1 ((v0 4) k2) ^ (v0 sum) ^ ((v0 5) k3); }解密则是加密的逆过程for (int i 0; i rounds; i) { v1 - ((v0 4) k2) ^ (v0 sum) ^ ((v0 5) k3); v0 - ((v1 4) k0) ^ (v1 sum) ^ ((v1 5) k1); sum - delta; }这里有几个黄金特征是你在IDA的汇编或反编译C代码里一眼就应该锁定的常量Delta0x9E3779B9。这个值是黄金分割率相关的一个常数几乎是TEA家族的“身份证”。看到它基本可以确定是TEA、XTEA或XXTEA。“左移4加密钥右移5加密钥”结构((v1 4) k0)和((v1 5) k1)。这种固定的移位位数4和5和与密钥相加的操作是TEA最标志性的运算组合。Feistel结构加密过程明显分为对v0和v1的交替运算并且一轮中v0的更新依赖于旧的v1v1的更新依赖于新的v0。Sum变量一个随着每轮加密累加delta或在解密时递减delta的变量。注意在实际的二进制程序中编译器优化可能会打乱这些操作的顺序或者将循环展开。但只要你看到了0x9E3779B9这个魔数以及成对出现的左移4/右移5配合加法的模式就应该高度怀疑是TEA。2.2 常见变种与识别技巧出题人不会直接考标准TEA那样太简单了。变种是常态。常见的变种思路有修改Delta常量这是最简单的变种把0x9E3779B9改成另一个值比如0x61C88647这是XTEA中用的是-0x9E3779B9的补码表示或者其他任意32位常数。识别关键寻找一个在循环中累加或递减的固定常量。修改移位位数将左移4、右移5改成其他数字例如左移5、右移3。识别关键关注移位指令shl,shr后面紧跟加法add的模式。修改轮数标准TEA建议32轮但题目可能用16轮、64轮等。识别关键分析循环计数器或循环展开的遍数。修改密钥加载方式标准TEA使用k[0]到k[3]四个32位子密钥。变种可能使用更长的密钥或者以不同的顺序使用这些子密钥。识别关键跟踪参与v0/v1更新运算的常量或内存数据看它们是否来自同一个密钥数组。结合其他操作在TEA加密前后或中间加入额外的异或、加减、置换等操作。使用XTEA或XXTEAXTEA和XXTEA是TEA的加强版结构更复杂但核心思想相似。XTEA的轮函数更复杂密钥使用方式不同XXTEA则是针对可变长度分组的。识别技巧实录 面对反编译代码不要慌。我通常这样做第一步搜常量。在IDA中按AltB搜索0x9E3779B9或其可能的变体如0x61C88647。搜不到也别急可能被拆开赋值了。第二步看循环。找到疑似加密/解密的主循环看里面是否有明显的对两个变量v0,v1的交替运算。第三步盯移位。在循环体内搜索左移和右移操作看它们是否与加法配合且操作数看起来像密钥。第四步定密钥。找到参与运算的、在循环外初始化的数组或一组常量那很可能就是密钥。第五步动态验。用调试器如x64dbg在疑似加密函数入口下断点输入一个已知的测试数据比如全0x61即a单步跟踪观察数据变化是否符合Feistel结构并记录下输入输出为后续写脚本验证做准备。3. 实战逆向静态分析与动态调试3.1 静态分析定位加密逻辑我们回到例题。用IDA载入程序查看main函数。很快找到check_flag函数。反编译后核心部分如下已做简化并重命名变量int check_flag(char* input) { int len strlen(input); if (len ! 32) return 0; // 提示1: flag长度32字符即32字节64位分组可分成4组 // 将输入的字符串ASCII每8字节一组转换为两个32位整数小端序 unsigned int v0, v1; unsigned int encrypted_blocks[4][2]; // 程序里硬编码的密文 unsigned int key[4] {0x12345678, 0x9ABCDEF0, 0xFEDCBA98, 0x76543210}; // 示例密钥 // 模拟加密过程 for (int block 0; block 4; block) { v0 *(unsigned int*)(input block*8); v1 *(unsigned int*)(input block*8 4); unsigned int sum 0; unsigned int delta 0x9E3779B9; // 特征点1: TEA家族常量 for (int i 0; i 32; i) { // 特征点2: 32轮循环 sum delta; // 注意这里和标准TEA不同 v0 ((v1 4) key[0]) ^ (v1 sum) ^ ((v1 5) key[1]); v1 ((v0 4) key[2]) ^ (v0 sum) ^ ((v0 5) key[3]); } if (v0 ! encrypted_blocks[block][0] || v1 ! encrypted_blocks[block][1]) { return 0; } } return 1; }静态分析我们发现了长度提示Flag长度为32字节。这很重要它决定了我们要处理多少个分组。TEA特征0x9E3779B9常量32轮循环以及((v1 4) k0) ^ (v1 sum) ^ ((v1 5) k1)这个经典结构。但是仔细看v0和v1的更新顺序在标准TEA中是先更新v0然后用新的v0去更新v1。而在这段代码里v1的更新使用的是v0但这个v0是本轮更新前的v0吗不因为v0已经在上一行被更新了。所以这里v1使用的是本轮已更新的v0。这其实是一个常见的变种有时被称为“TEA的变体”或“不标准的Feistel顺序”。这会影响我们的解密脚本编写。实操心得静态分析时一定要画图尤其是在分析Feistel结构时。在一张纸上画出v0和v1标出每一轮它们依赖的是对方的新值还是旧值。像这道题v1依赖的是本轮新的v0那么在解密时就必须先还原v1再还原v0顺序和标准TEA正好相反。这个细节是后续爆破能否成功的关键。3.2 动态调试验证与数据提取静态分析给了我们一个模型但必须用动态调试来验证并提取关键数据密文和密钥。启动调试器使用x64dbg附加目标程序。定位关键函数在IDA中找到的check_flag函数地址在x64dbg中CtrlG跳转过去下断点。输入测试数据运行程序在控制台输入一个长度为32的已知字符串例如aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa32个a其十六进制为0x61616161...。断点命中程序会在check_flag入口断下。单步执行并观察验证密钥在内存窗口中查看key数组的地址确认四个32位整数是否与我们静态分析的一致。有时密钥可能是动态生成的或隐藏在别处。验证密文找到encrypted_blocks数组记录下四组(v0, v1)的值。这就是我们需要用输入去匹配的目标密文。验证加密过程单步跟入加密循环观察v0和v1的变化。可以手算一轮看是否与代码逻辑一致特别是v0和v1的更新依赖关系。确认我们关于“v1使用新v0”的判断是否正确。验证分组确认程序是否真的将我们输入的字符串每8字节转为两个unsigned int小端序。例如输入abcdefgh在内存中查看对应的v0和v1v0应为dcbav1应为hgfeASCII码十六进制。通过动态调试我们最终拿到了以下硬数据这是写脚本的基础密钥Key:[0x12345678, 0x9ABCDEF0, 0xFEDCBA98, 0x76543210](示例)目标密文Cipher:[(0x11223344, 0x55667788), (0x99AABBCC, 0xDDEEFF00), ...]共四组确认的变种细节加密顺序为v0_new v0_old F(v1_old);v1_new v1_old F(v0_new)。Delta为0x9E3779B932轮。4. Python脚本编写解密与爆破拿到了算法逻辑和所有参数就可以动手写脚本了。我们的目标根据变种加密逻辑写出对应的解密函数然后对已知密文进行解密得到flag。4.1 实现变种TEA解密函数由于加密顺序变了解密顺序也要相应调整。根据加密逻辑加密 for i in range(32): sum delta v0 F(v1) # F是那个复杂的异或加法表达式 v1 G(v0) # 注意这里G函数使用的是新的v0推导解密逻辑。我们把最后轮的状态记为(v0_n, v1_n)它是已知密文。我们需要推出上一轮的状态(v0_{n-1}, v1_{n-1})。 从最后一轮加密等式出发v1_n v1_{n-1} G(v0_n) // 等式1 v0_n v0_{n-1} F(v1_{n-1}) // 等式2注意G(v0_n)里的v0_n是最后一轮加密后的v0是已知的。所以我们可以直接从等式1解出v1_{n-1}v1_{n-1} v1_n - G(v0_n)得到v1_{n-1}后代入等式2即可解出v0_{n-1}v0_{n-1} v0_n - F(v1_{n-1})这个顺序和标准TEA解密先v1后v0是一致的吗不标准TEA因为加密时v1用的是旧的v0所以解密时先解v1再解v0。而我们这个变种加密时v1用的是新的v0导致解密时必须先解v1再解v0。等一下我们上面推导的过程就是先v1_{n-1}再v0_{n-1}。让我们再仔细对比。实际上对于这个特定变种解密顺序和加密顺序在形式上是对称的。加密是v0先更新然后v1用新v0更新。解密是v1先还原因为它依赖于最终的v0然后v0用还原出的v1还原。所以解密循环应该是def decrypt(v0, v1, key): delta 0x9E3779B9 sum (delta * 32) 0xFFFFFFFF # 加密结束时的sum值 for i in range(32): # 注意顺序先还原v1再还原v0 v1 - ((v0 4) key[2]) ^ (v0 sum) ^ ((v0 5) key[3]) v0 - ((v1 4) key[0]) ^ (v1 sum) ^ ((v1 5) key[1]) sum - delta return v0, v1关键点sum的初始值是加密32轮后的总和即delta * 32。解密时每轮先减delta再用于运算还是先运算再减delta这必须和加密匹配。加密是sum delta在轮函数开头所以解密时对于最后一轮第32轮运算时使用的sum是累加了32次delta的值。因此解密循环开始时sum应初始化为delta*32然后在每轮运算之后再减去delta。但注意看上面的代码我们是先运算再sum - delta。这是正确的吗让我们验证对于第32轮解密还原第32轮加密我们需要用加密第32轮时的sum。加密第32轮时sum已经加了32次delta。所以解密循环第一次运算时sum应该是delta*32。运算完成后我们减去一个delta得到delta*31用于下一轮第31轮解密。所以上面的写法是正确的。避坑指南sum的处理是TEA解密最容易出错的地方之一。一定要画一个时间轴明确加密每一轮使用的sum值是多少然后让解密从最后一轮对应的sum开始逆向递减。一个简单的记忆方法是解密循环的sum初始值 delta * 轮数然后每轮循环末尾sum - delta。运算部分直接使用当前的sum值。4.2 整合解密与Flag还原解密函数写好后我们还需要处理分组和字节序。def tea_decrypt_block(cipher, key): v0, v1 cipher delta 0x9E3779B9 sum (delta * 32) 0xFFFFFFFF k0, k1, k2, k3 key for i in range(32): # 根据变种逻辑解密先v1后v0 v1 (v1 - (((v0 4) k2) ^ (v0 sum) ^ ((v0 5) k3))) 0xFFFFFFFF v0 (v0 - (((v1 4) k0) ^ (v1 sum) ^ ((v1 5) k1))) 0xFFFFFFFF sum (sum - delta) 0xFFFFFFFF return v0, v1 def bytes_to_ints(data): # 小端序字节串转32位整数列表 ints [] for i in range(0, len(data), 4): ints.append(int.from_bytes(data[i:i4], little)) return ints def ints_to_bytes(int_list): # 32位整数列表转小端序字节串 b b for val in int_list: b val.to_bytes(4, little) return b # 从调试器中提取的数据 key [0x12345678, 0x9ABCDEF0, 0xFEDCBA98, 0x76543210] cipher_blocks [(0x11223344, 0x55667788), (0x99AABBCC, 0xDDEEFF00), ...] # 填入四组密文 flag_b b for block in cipher_blocks: v0, v1 tea_decrypt_block(block, key) # 将解密后的v0, v1转换为字节注意顺序 decrypted_block ints_to_bytes([v0, v1]) flag_b decrypted_block flag flag_b.decode(ascii) # 假设flag是ASCII字符 print(fFlag: {flag})运行这个脚本理论上就能直接得到flag。4.3 当解密失败时暴力破解的引入有时候即使算法识别正确解密脚本也看似正确但就是解不出可读的字符串。可能的原因有密钥错误静态分析或动态提取的密钥不对。轮数错误不是32轮。Delta常量错误不是0x9E3779B9。字节序或分组方式错误可能不是小端序或者分组大小不是64位。存在额外的编码/变换加密前后可能还有Base64、XOR等操作。当静态分析无法确定所有参数时就需要爆破。在这个例子中最可能爆破的是密钥。如果密钥空间不大比如是4个32位整数但其中部分字节可能来自flag格式如flag{前缀我们可以尝试暴力枚举。爆破思路已知明文攻击如果知道flag的部分明文比如格式是flag{结尾是}我们可以利用它。加密是分组进行的flag{这5个字符会影响第一个64位分组8字节的前5个字节。我们可以用已知的密文块反向枚举可能的密钥看哪个密钥能把密文解密成以flag{开头的明文。编写爆破脚本import itertools def brute_force_key_partial(cipher_block, known_plaintext_block): # cipher_block: (v0_cipher, v1_cipher) # known_plaintext_block: bytes, 至少8字节不足可以补零猜测 v0_known, v1_known bytes_to_ints(known_plaintext_block.ljust(8, b\x00))[:2] # 假设密钥的某些字节是已知的或者取值范围很小 # 例如密钥可能是可打印字符或者与某些常量相关 key_space [] # 这里定义要枚举的密钥可能性例如 # 如果密钥是四个32位整数全枚举不可能(2^128)。需要结合题目提示缩小范围。 # 示例假设key[0]是0x12345678我们只爆破key[1]的低16位 for k1_low in range(0x10000): key [0x12345678, (0x9ABC0000 | k1_low), 0xFEDCBA98, 0x76543210] # 组合 v0_dec, v1_dec tea_decrypt_block(cipher_block, key) if (v0_dec v0_known) and (v1_dec v1_known): print(fPotential key found: {[hex(k) for k in key]}) return key return None # 使用第一个密文块已知明文为 bflag{... 的前8字节 first_cipher cipher_blocks[0] known_plain bflag{...[:8] # 可能需要尝试不同的补齐 possible_key brute_force_key_partial(first_cipher, known_plain)爆破技巧缩小空间充分利用题目信息。密钥可能藏在程序的某个字符串里可能是简单的数字或者与某些常量运算相关。并行计算如果搜索空间较大可以使用multiprocessing库加速。验证用找到的候选密钥解密其他密文块看结果是否可读是否都是可打印ASCII字符。5. 常见问题排查与实战心得5.1 解密结果乱码或不对这是最常见的问题。请按以下清单排查问题现象可能原因排查方法解出的全是非ASCII字符密钥错误检查动态调试提取的密钥是否准确。尝试用已知明文攻击验证密钥。部分字符对部分不对字节序错误TEA操作的是32位整数需要明确是小端序还是大端序。将bytes_to_ints和ints_to_bytes的little改为big试试。解密出的数据看起来有规律但不对轮数错误标准是32轮但变种可能不同。尝试修改解密循环次数16, 64等。解密函数逻辑错误加密/解密顺序不匹配这是最易错的点。用极简数据如v00, v10单步调试自己的加密函数记录每轮中间值。然后对比解密函数看能否正确还原。务必画图理清依赖关系。sum值错误sum初始值或递减顺序错误确认加密时sum delta在每轮的位置开头还是结尾。确保解密时sum初始值为delta*轮数递减顺序与之相反。存在前置/后置处理加密前后有XOR、ADD等操作仔细分析check_flag函数看TEA加密前后是否对数据进行了其他变换。动态调试时对比输入字符串的原始字节和传入TEA函数前的字节以及TEA函数输出和最终比较的字节。5.2 动态调试技巧硬件断点对于检测调试器的反调试代码可以尝试使用硬件断点而非软件断点。内存断点如果你知道最终比较的密文所在的内存地址可以对其设置内存写入断点反向找到是什么代码写入了它从而定位加密函数。脚本化调试x64dbg和IDA都有脚本功能如x64dbg的ConditionalLog命令。可以记录函数参数和返回值快速筛选大量数据。对比测试输入两个仅一位不同的flag比如flag{aaaaaaaaaaaaaaaaaaaaaaaaaa}和flag{baaaaaaaaaaaaaaaaaaaaaaaaaa}观察加密后的密文差异在哪里这有助于理解分组模式和加密效果。5.3 算法识别能力提升积累特征常量除了0x9E3779B9还有其他算法的魔数如MD5的0x67452301SHA1的0x5A827999CRC32的0xEDB88320等。建立一个自己的魔数表。熟悉常见结构Feistel结构DES、TEA、SPN结构AES、ARX结构Salsa20, ChaCha等。TEA属于ARXAddition-Rotation-XOR与Feistel的结合。使用工具辅助IDA的插件如FindCrypt可以自动搜索二进制文件中的加密常量。Krypto ANALyzer插件也不错。多练在CTF平台如BUUCTF、攻防世界上找逆向题专项练习尤其是带“tea”、“xtea”、“xxtea”、“加密”、“解密”标签的题目。最后这道题带给我的体会是逆向分析就像侦探破案算法特征是现场指纹动态调试是现场重现而编写脚本则是最终收网。面对变种不要被其外表吓倒核心永远是理解其原始算法的本质然后耐心地、一步一步地比对和推导。那个“先v0还是先v1”的问题我当初就卡了将近一个小时直到我在纸上画出了每一轮的数据流图才豁然开朗。所以当你卡住时别光盯着代码看拿起笔和纸往往是最快的解决方法。