ELF 三层可逆校验逆解:256 字节 S-box + 前缀异或链 + 8 位重排
ctf/reverse · verified
一句话结论
strip ELF 校验输入长度 37,依次做 256 字节 S-box 替换、state=0x37*len+0x42 的前缀异或链、8 位重排 [5,2,7,0,6,1,4,3],最后 memcmp;三层都可逆,从目标数组反推 flag。
原理
- S-box 替换:
tmp[i] = table[input[i]];表是 0~255 的置换,可构造逆表inv_table[table[i]] = i。 - 前缀异或链:
state = 0x37*len + 0x42(len=37 时为 0x35);state ^= tmp[i]; tmp[i] = state。逆推:old[i] = prev ^ new[i]; prev = new[i]。 - 位重排:
out[i]的第map[b]位来自tmp[i]的第 b 位;对[5,2,7,0,6,1,4,3]求逆映射,逐位还原。 - 可逆性:三层都是双射,无需爆破;从
target逆 bit → 逆 rolling → 逆 S-box 即得输入。
触发条件
- 二进制 strip 但有
Wrong./Correct!/长度校验等字符串。 - 反汇编可见 S-box 查表、
xor链、bit 测试/移位组合。 - 存在固定目标数组与
memcmp。 - 输入长度/格式可推断(如 37 字节
SDG{32hex})。
利用步骤
strings/objdump定位长度校验、S-box 表、bit map、目标数组。- 从
.rodata提取 256 字节 table 与 8 字节 bit map。 - 逆 bit 重排:对每个目标字节,按
inv_map把位放回原位置。 - 逆 rolling XOR:用同一 seed(
0x37*len+0x42)从前往后old = prev ^ new。 - 逆 S-box:
inv_table[b]还原输入字节,拼字符串。
PoC
table = bytes.fromhex("7bce2174...") # 256 字节
target = bytes.fromhex("70dcd4050afe0aa37dc35ca8286f05cd...")
bit_map = [5, 2, 7, 0, 6, 1, 4, 3]
length = 37
seed = (0x37 * length + 0x42) & 0xFF
inv_map = [0] * 8
for src, dst in enumerate(bit_map):
inv_map[dst] = src
def inv_bit(b):
x = 0
for dst in range(8):
if (b >> dst) & 1:
x |= 1 << inv_map[dst]
return x
stage2 = bytes(inv_bit(b) for b in target)
stage1, prev = [], seed
for b in stage2:
stage1.append(prev ^ b)
prev = b
inv_table = [0] * 256
for i, v in enumerate(table):
inv_table[v] = i
print(bytes(inv_table[b] for b in stage1).decode())
变体与关联
- S-box 变体:表有重复值(需爆破/约束)、动态生成、AES S-box;可先验证是否为置换。
- rolling 变体:初值依赖输入长度/常量、反向滚动、加/减而非 XOR;逆推方向要对应。
- bit 置换变体:map 长度 8/16/32、按字节/字重排、结合 rotate。
- 关联卡片:[[ctf-reverse-png-lsb-custom-sbox-aes256-decrypt]](自定义 S-box)、[[ctf-reverse-self-referential-key-tea-variant]](可逆混合层)、[[ctf-reverse-upx-vm-rolling-hash-per-char-inversion]](滚动哈希逆推)。
- 边界:若某层不可逆(哈希/有损),需爆破或换路径;若目标数组被加密/压缩,先解外层。
检测与防御
- CTF/验证:逆出的输入应满足长度与格式;正向重跑三层应等于 target。
- 防御:客户端校验只用于体验,最终由服务端验证;不要依赖简单可逆变换作为授权;加壳/混淆提高成本。
- 检测信号:ELF 中出现 256 字节置换表、bit map、固定目标数组;
memcmp前有多层可逆变换。