前言

本文是对RCTF 2021中ASM Crypto题目的完整技术复现。这道题目提供了一个x86汇编编写的加密程序和加密后的密文，需要通过逆向分析还原出明文。

本文将采用正向分析 + 逆向求解 + 代码验证的方式，确保每一步都有理论依据和实践验证，让新手也能完全理解整个过程。

题目材料

解压附件后得到：

asm/
├── crypto.asm    # MASM32汇编源码（加密程序）
└── flag.enc      # 加密后的密文（256个十六进制字符）

快速观察flag.enc：

• 长度为256个字符

• 只包含[0-9a-f]（小写十六进制）

• 推测：128字节的二进制数据经过十六进制编码

第一步：静态分析汇编源码

程序主流程

start:
    ; 1. 读取输入
    invoke  ReadConsole,hStdin,offset buffer,bufferSize+2,offset cLen,NULL
    sub     cLen,1          ; 只减去1个字符（\n），保留\r

    ; 2. 四步加密流程
    invoke  mInit,addr buffer,cLen
    invoke  Encode,addr buffer,bufferSize
    invoke  c2w,addr buffer,addr buffer2,bufferSize
    mov     tt,0
    invoke  dfs,addr buffer2,0

    ; 3. 输出密文
    invoke  WriteConsole,hStdout,offset buffer3,bufferSize*2+1,offset dwNum,NULL

关键点：

• sub cLen,1只减去了换行符\n

• 在Windows控制台下，输入通常以\r\n结尾

• 因此明文末尾会保留\r字符（这个细节很重要！）

加密流程：输入 → mInit → Encode → c2w → dfs → 输出

函数1：mInit - 扩展与异或

mInit proc s,l
    ; 第一阶段：循环填充到128字节
    mov @temp,1        ; 递增值从1开始
    .while ecx<bufferSize
        mov dl,[eax+ebx]       ; 读取 buffer[eax]
        add edx,@temp          ; 加上递增值
        mov [ecx+ebx],dl       ; 写入 buffer[ecx]
        inc ecx
        inc eax
        .if eax==l             ; 读完一轮原始输入
            xor eax,eax        ;   重置读取位置
            add @temp,1        ;   递增值+1
        .endif
    .endw

    ; 第二阶段：所有字节异或长度
    mov eax,l
    .while ecx<bufferSize
        mov dl,[ebx+ecx]
        xor dl,al              ; buffer[ecx] ^= length
        mov [ebx+ecx],dl
        inc ecx
    .endw
    ret
mInit endp

数学化描述

设输入明文为P[0..L-1]，输出S[0..127]：

阶段1 - 循环填充：

Init[i] = (P[i mod L] + floor(i / L)) mod 256

解释：

• 位置i的值 = 原始字符P[i mod L]+ 当前是第几轮填充floor(i / L)

• 这样前L个字节保持原样，后面的字节是循环复制+递增偏移

示例（L=3，明文"ABC"）：

阶段2 - 异或长度：

S[i] = Init[i] XOR L

所有128字节都与输入长度进行异或。

函数2：Encode - 就地滚动异或

Encode proc s,l
    mov @k,8
    .while ecx<l
        xor edx,edx
        mov eax,ecx
        div @k              ; eax = ecx/8, edx = ecx%8

        .if edx!=0          ; 如果 i % 8 != 0
            mov dl,[ebx+ecx-1]     ; 读取左邻 buffer[i-1]
        .endif
        .if eax!=0          ; 如果 i / 8 != 0
            mov al,[ebx+ecx-8]     ; 读取上邻 buffer[i-8]
        .endif

        mov ah,[ebx+ecx]    ; 读取当前值
        xor ah,al           ; 异或上邻
        xor ah,dl           ; 异或左邻
        mov [ebx+ecx],ah    ;  原地写回！
        inc ecx
    .endw
    ret
Encode endp

关键理解：原地更新

这是最容易出错的地方！代码是原地修改（in-place），即：

E[i] = S[i] ⊕ (i≥8 ? E[i-8] : 0) ⊕ (i%8≠0 ? E[i-1] : 0)

注意：

• E[i-1]和E[i-8]使用的是已经更新过的值，不是原始的S[i-1]！

• 处理顺序是从0到127（forward）

• 后面的字节依赖前面已处理的字节

依赖关系图：

位置:  0  1  2  3  4  5  6  7  8    9   10  ...
依赖:  无 0  1  2  3  4  5  6  0    1+8  2+9 ...

这种设计产生了强烈的雪崩效应：一个字节的改变会影响后续所有字节。

函数3：c2w - 二进制转十六进制

func1 proc var1
    mov eax,var1
    mov ah,al
    and al,00001111b        ; 低4位
    and ah,11110000b        ; 高4位
    shr ah,4
    lea ebx,ca              ; ca = '0123456789abcdef'
    movzx ecx,al
    mov al,[ebx+ecx]        ; 低4位→字符
    movzx ecx,ah
    mov ah,[ebx+ecx]        ; 高4位→字符
    ret
func1 endp

c2w proc s1,s2,l
    .while dword ptr ecx<l
        mov dl,[ebx+ecx]
        invoke func1,edx
        mov edx,s2
        mov byte ptr [ecx*2+edx],ah
        mov byte ptr [ecx*2+edx+1],al
        inc ecx
    .endw
    ret
c2w endp

功能：将128字节转换为256个十六进制字符

示例：

• 输入字节：0x4A

• 输出字符：'4'(0x34) 和 'a'(0x61)

• 结果："4a"

函数4：dfs - 完全二叉树中序遍历

dfs proc s,t
    mov ecx,t
    .if ecx>=bufferSize*2       ; 如果节点>=256，返回
        jmp dfs_jmp
    .endif

    mov eax,t
    add eax,eax
    inc eax                     ; eax = 2*t+1（左子节点）
    invoke dfs,s,eax            ; 递归访问左子树

    mov dl,[ebx+ecx]            ; 访问当前节点
    mov ecx,tt
    lea ebx,buffer3
    mov [ebx+ecx],dl            ; 输出到buffer3
    inc ecx
    mov tt,ecx

    inc eax                     ; eax = 2*t+2（右子节点）
    invoke dfs,s,eax            ; 递归访问右子树
dfs_jmp:
    ret
dfs endp

完全二叉树与中序遍历

将256个字符视为完全二叉树的节点：

0
          /       \
        1           2
       / \         / \
      3   4       5   6
     /\   /\     /\   /\
    7  8 9 10  11 12 13 14
   ...

节点关系：

• 父节点：(i-1) // 2

• 左子节点：2*i + 1

• 右子节点：2*i + 2

中序遍历（左→根→右）：

访问顺序: [255, 127, 63, 128, 31, 129, 64, 130, ...]

效果：彻底打乱数据顺序，第0个位置输出的是节点255的数据！

第二步：数学建模（正向流程）

设明文为P[0..L-1]，完整的加密过程：

Step 1: mInit扩展

Init[i] = (P[i mod L] + floor(i/L)) mod 256
S[i] = Init[i] XOR L

Step 2: Encode依赖编码

E[i] = S[i] ⊕ (i≥8 ? E[i-8] : 0) ⊕ (i%8≠0 ? E[i-1] : 0)

Step 3: c2w十六进制

H[2*i] = hex_high(E[i])
H[2*i+1] = hex_low(E[i])

Step 4: dfs树遍历

C = inorder_traverse(H)  # 按中序遍历重排

第三步：逆向解密方案

逆向步骤总览

解密: 密文C → 逆dfs → 逆c2w → 逆Encode → 逆mInit → 明文P

步骤A：还原中序遍历置换

原理：生成中序遍历的索引序列，建立逆映射

# 生成中序遍历序列
order = []
def dfs(t):
    if t >= 256: return
    dfs(2*t + 1)      # 左子树
    order.append(t)    # 记录节点
    dfs(2*t + 2)      # 右子树
dfs(0)

# order[i]表示：第i个访问的节点编号
# 逆向：密文C[i]应该放回H[order[i]]位置

H = [''] * 256
for i in range(256):
    H[order[i]] = C[i]

正确性：中序遍历是确定性的，逆映射唯一存在。

步骤B：十六进制转二进制

E = bytes.fromhex(''.join(H))  # 256字符 → 128字节

直接转换，无歧义。

步骤C：逆向Encode - 关键洞察！

回顾Encode的公式：

E[i] = S[i] ⊕ E[i-8] ⊕ E[i-1]

因为异或的自逆性（A ⊕ B ⊕ B = A），我们有：

S[i] = E[i] ⊕ E[i-8] ⊕ E[i-1]

关键点：

• E[i], E[i-1], E[i-8]都是已知的（在数组E中）

• 不需要知道S[i-1]或S[i-8]

• 可以从前往后直接计算！

def decode_encode(E):
    S = bytearray(128)
    for i in range(128):  # 从前往后处理
        v = E[i]
        if i >= 8:
            v ^= E[i-8]
        if i % 8 != 0:
            v ^= E[i-1]
        S[i] = v
    return bytes(S)

为什么可以forward处理？

因为Encode是"原地更新"，即更新E[i]时使用的是已经更新过的E[i-1]和E[i-8]。逆向时，我们知道最终的E数组，可以直接用同样的索引关系反推S。

这与普通的"先算后更新"不同：

# 如果是这样（非原地）：
E_new[i] = S[i] ^ S[i-1] ^ S[i-8]  # 使用S的旧值

# 那么逆向就需要从后往前：
for i in range(127, -1, -1):
    S[i] = E[i] ^ S[i-1] ^ S[i-8]

但汇编代码是：

mov ah,[ebx+ecx]    # 读当前
xor ah,al           # 异或（使用已更新的值）
mov [ebx+ecx],ah    # 写回同一位置

这是原地操作，所以逆向也用同样的公式即可。

步骤D：逆向mInit - 爆破长度

从S恢复Init很简单：

Init[i] = S[i] XOR L

但我们不知道L！需要利用填充的规律性。

约束条件：

Init[i] = P[i mod L] + floor(i / L)  (mod 256)

对于同一个原始字符P[j]，在不同位置会呈现等差数列：

Init[j]      = P[j] + 0
Init[j+L]    = P[j] + 1
Init[j+2L]   = P[j] + 2
...

爆破方法：

for L in range(1, 129):
    # 验证每个位置是否满足等差递增
    valid = True
    P = bytearray(L)

    for j in range(L):
        x0 = (S[j] ^ L) & 0xFF  # Init[j]
        P[j] = x0

        # 检查后续位置
        m = 1
        while j + m*L < 128:
            expected = (x0 + m) & 0xFF
            actual = (S[j + m*L] ^ L) & 0xFF
            if expected != actual:
                valid = False
                break
            m += 1

        if not valid:
            break

    if valid:
        return L, bytes(P)

唯一性：在128字节的全局约束下，只有真正的L能让所有位置都满足等差关系。

第四步：完整解密脚本

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
RCTF 2021 ASM Crypto - 完整解密脚本
"""

import binascii

# 读取密文
with open('flag.enc', 'r', encoding='ascii') as f:
    enc_hex = f.read().strip()

print(f"[*] 密文长度: {len(enc_hex)}")

# ========== 步骤A: 还原中序遍历置换 ==========
print("[*] 步骤1: 还原中序遍历...")

N = 256
order = []

def dfs(t):
    if t >= N:
        return
    dfs(2*t + 1)
    order.append(t)
    dfs(2*t + 2)

dfs(0)

# 逆向置换
buf3 = list(enc_hex)     # 密文序列
buf2 = [''] * N          # 原始顺序
for k, idx in enumerate(order):
    buf2[idx] = buf3[k]

hex_str = ''.join(buf2)
print(f"    还原后: {hex_str[:60]}...")

# ========== 步骤B: 十六进制转二进制 ==========
print("[*] 步骤2: 十六进制转二进制...")

E = bytearray(binascii.unhexlify(hex_str))
print(f"    得到{len(E)}字节")

# ========== 步骤C: 逆向Encode ==========
print("[*] 步骤3: 逆向Encode（依赖编码）...")

S = bytearray(128)
for i in range(128):
    v = E[i]
    if i >= 8:
        v ^= E[i-8]
    if i % 8 != 0:
        v ^= E[i-1]
    S[i] = v

print(f"    完成")

# ========== 步骤D: 逆向mInit（爆破长度） ==========
print("[*] 步骤4: 爆破原始长度...")

def recover_plain(M):
    for L in range(1, 129):
        P = bytearray(L)
        ok = True

        for j in range(L):
            # 获取Init[j]
            x0 = (M[j] ^ L) & 0xFF
            P[j] = x0

            # 验证等差递增
            m = 1
            while j + m*L < 128:
                expected = (x0 + m) & 0xFF
                actual = (M[j + m*L] ^ L) & 0xFF
                if expected != actual:
                    ok = False
                    break
                m += 1

            if not ok:
                break

        if ok:
            return L, bytes(P)

    return None, None

L, P = recover_plain(S)

if L is None:
    print("    [!] 未找到有效长度")
else:
    print(f"    [+] 找到长度: L = {L}")
    print(f"\n{'='*70}")
    print(f"[FLAG] 原始字节: {P}")
    print(f"[FLAG] 可见文本: {P.rstrip(b'\\r').decode('latin1')}")
    print(f"{'='*70}")

# ========== 步骤E: 正向验证 ==========
print("\n[*] 步骤5: 正向加密验证...")

def mInit(P):
    l = len(P)
    buf = bytearray(128)
    buf[:l] = P
    i, t, eax = l, 1, 0
    while i < 128:
        buf[i] = (buf[eax] + t) & 0xFF
        i += 1
        eax += 1
        if eax == l:
            eax = 0
            t += 1
    al = l & 0xFF
    for i in range(128):
        buf[i] ^= al
    return bytes(buf)

def encode_forward(s):
    s = bytearray(s)
    for i in range(128):
        dl = s[i-1] if (i % 8) != 0 else 0
        al = s[i-8] if i >= 8 else 0
        s[i] = s[i] ^ al ^ dl
    return bytes(s)

def c2w(b):
    ca = b'0123456789abcdef'
    out = bytearray(256)
    for i, x in enumerate(b):
        out[2*i]   = ca[(x >> 4) & 0xF]
        out[2*i+1] = ca[x & 0xF]
    return bytes(out)

def inorder_permute(buf2):
    o = []
    def dfs(t):
        if t >= len(buf2):
            return
        dfs(2*t+1)
        o.append(t)
        dfs(2*t+2)
    dfs(0)
    return ''.join(buf2[i] for i in o)

# 重新加密
re_enc = inorder_permute(c2w(encode_forward(mInit(P))).decode())

if re_enc == enc_hex:
    print("    [] 验证成功！加密结果完全匹配")
else:
    print("    [] 验证失败")
    print(f"    期望: {enc_hex[:60]}...")
    print(f"    实际: {re_enc[:60]}...")

print("\n[*] 解密完成！")

第五步：运行结果

将脚本保存为solve.py，与flag.enc放在同一目录下，运行：

$ python3 solve.py

输出：

[*] 密文长度: 256
[*] 步骤1: 还原中序遍历...
    还原后: 473c1e38740b4b0714640c4652333461546e7c7c544657452a030c22...
[*] 步骤2: 十六进制转二进制...
    得到128字节
[*] 步骤3: 逆向Encode（依赖编码）...
    完成
[*] 步骤4: 爆破原始长度...
    [+] 找到长度: L = 19

======================================================================
[FLAG] 原始字节: b'Th15_lS_@_easy_ASM\r'
[FLAG] 可见文本: Th15_lS_@_easy_ASM
======================================================================

[*] 步骤5: 正向加密验证...
    [] 验证成功！加密结果完全匹配

[*] 解密完成！

关键技术点深度解析

1. 为什么明文末尾有\r？

在Windows控制台下：

• 用户输入后按回车，系统读取的是...\r\n

• 汇编代码只执行了sub cLen,1，减去了\n

• 因此\r被保留在输入中成为明文的一部分

这是一个细节，但影响最终的字节数和内容。

2. Encode的"原地更新"如何理解？

关键区别：

方式A（非原地）：

temp = S[i] ^ S[i-1] ^ S[i-8]  # 使用S的原始值
E[i] = temp                     # 写入新数组

这种情况需要反向遍历解密。

方式B（原地，汇编实现）：

mov ah,[ebx+ecx]     # ah = buffer[i]（可能已被修改）
xor ah,al            # 使用buffer[i-8]（可能已被修改）
xor ah,dl            # 使用buffer[i-1]（已被修改）
mov [ebx+ecx],ah     # 写回buffer[i]

这是典型的原地算法，后续值依赖前面已更新的值。

逆向时：由于异或的性质A ⊕ B ⊕ B = A，使用相同的公式：

S[i] = E[i] ^ E[i-8] ^ E[i-1]

其中E[i-8]和E[i-1]是密文中已知的值，可以直接计算。

3. 长度爆破的数学依据

填充规律：

Init[j]      = P[j] + 0
Init[j+L]    = P[j] + 1
Init[j+2L]   = P[j] + 2
...
Init[j+kL]   = P[j] + k  (mod 256)

对于错误的L'：

• 不同的j位置会有不同的"基础值"

• 很难在所有128个位置上都恰好形成连贯的等差数列

• 特别是模256运算下，错误的L'几乎不可能满足全局约束

实验验证：

# 尝试L=18, 19, 20
for L in [18, 19, 20]:
    valid_positions = 0
    for j in range(L):
        x0 = (S[j] ^ L) & 0xFF
        m, ok = 1, True
        while j + m*L < 128:
            if (S[j+m*L] ^ L) != ((x0 + m) & 0xFF):
                ok = False
                break
            m += 1
        if ok:
            valid_positions += 1
    print(f"L={L}: {valid_positions}/{L} 位置满足约束")

只有L=19时所有位置都满足。

4. 完全二叉树中序遍历的应用

遍历顺序特性：

• 最左的叶子节点（255）最先访问

• 根节点（0）在中间位置访问

• 完全打乱了线性顺序

在密码学中的作用：

• 数据置换（permutation）

• 增加分析难度

• 与线性变换结合形成SP网络结构

常见错误与调试技巧

错误1：Encode逆向方向错误

症状：解密出的数据完全乱码

原因：误以为需要从后往前处理

正确做法：理解"原地更新"的含义，从前往后用相同公式

错误2：忽略\r字符

症状：长度始终对不上，找到的是18而不是19

原因：未考虑Windows控制台的输入特性

解决：查看汇编代码的sub cLen,1，只减了一个字符

错误3：长度爆破没有充分验证

症状：找到多个"可能"的长度

原因：只检查了部分约束条件

正确做法：检查所有128字节的等差关系

调试技巧

1. 分步验证：

# 每一步都打印中间结果
print(f"Step 1: {data[:20]}")
print(f"Step 2: {data[:20]}")
...

2. 正向对照：

# 用已知明文加密，对比中间步骤
test_plain = b"test"
step1 = mInit(test_plain)
# 与解密过程的同一步骤对比

3. 边界条件：

# 检查特殊位置
# i=0: 不依赖前面
# i=7: 只依赖左邻
# i=8: 只依赖上邻
# i=9: 同时依赖左邻和上邻

安全性分析

优点

1. 多层变换：组合了填充、异或、编码、置换四种操作

2. 依赖关系：Encode建立了字节间的依赖，形成雪崩效应

3. 非线性置换：树遍历打乱了顺序

缺点

1. 算法公开：给出源码后成为纯数学问题

2. 无密钥：所有操作都是确定性的，没有密钥参与

3. 固定长度：128字节固定长度可能泄露信息

4. 可逆性强：每一步都是可逆的简单操作

改进建议

如果要将其改造为实用的加密算法：

1. 引入密钥：

   • 用密钥控制填充的递增值

   • 用密钥派生异或值，而不是固定使用长度

2. 增加轮数：

   • 多轮Encode，每轮使用不同的依赖模式

   • 类似AES的多轮结构

3. 动态置换：

   • 根据密钥选择不同的置换方式

   • 不固定使用中序遍历

4. 加入S盒：

   • 在Encode后加入非线性的S盒替换

   • 增强抗差分和线性分析能力

总结

本题是一道优秀的CTF密码学题目，涵盖了：

技术点：

• x86汇编阅读与逆向

• 数学建模与算法分析

• 数据结构（完全二叉树）

• 密码学基础概念

解题思路：

1. 静态分析：逐函数理解加密逻辑

2. 数学建模：用公式描述每一步

3. 逆向设计：为每步设计可验证的逆向算法

4. 代码实现：Python实现完整流程

5. 正向验证：用明文加密验证解密正确性

关键洞察：

• Encode的"原地更新"特性决定了逆向方法

• 填充的等差规律提供了唯一性约束

• 控制台I/O的细节影响明文内容

最终答案：

明文（含回车）: b'Th15_lS_@_easy_ASM\r'
明文（可见）:   Th15_lS_@_easy_ASM
长度:          19字节

本文通过分析 → 建模 → 逆向 → 实现 → 验证的完整流程，确保了每一步都有理论支撑和实践检验。希望能帮助读者深入理解这道题的精妙之处！

参考资料：

• MASM32程序设计

• 完全二叉树与树遍历

• 异或密码学应用

• CTF密码学题型分析

作者注：本文所有代码和结论均可在本地复现验证，欢迎读者动手实践！