好题分享系列 - 2023 N1CTF - e2$m4

admin 2024年2月9日01:04:02评论8 views字数 14141阅读47分8秒阅读模式

首先声明,这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣;或是很新颖;或是出题人对这道题各个知识点的衔接处理的很好,而不是单纯套娃;或是看了出题人的题解觉得特别优雅,或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性,可能我看到这道题的时候它已经是被抄袭过的,但我并没有遇到过原题。 (题好,但不对比赛给予评价)另外为了避免纯粹的拿来主义,以给读者一定的思考、操作空间,这个系列也不会直接给出完整的解题 exp,大家自己也多试试叭!

今天这道题目来自 2023 N1CTF - e2$m4

标签:分组密码,类SM4,差分故障分析

难度:中等偏上

e2$m4

task.py

import util
import os
FLAG = os.environ.get('FLAG''n1ctf{XXXXFAKE_FLAGXXXX}')
key = os.urandom(16)

ct = []
for _ in range(5):
    ct.append(util.crypt_ecb(FLAG.encode(), key, 31-_).hex())

print(f"Dance_Box = {util.Dance_Box}")
print(f"{ct = }")
"""
Dance_Box = [[46, 38, 43, 106, 114, 176, 12, 69, 1, 21, 82, 27, 184, 109, 170, 0, 179, 25, 4, 145, 33, 61, 66, 223, 85, 238, 22, 23, 59, 64, 19, 174, 180, 240, 111, 128, 187, 65, 72, 35, 77, 221, 157, 172, 13, 197, 44, 229, 226, 130, 220, 49, 198, 24, 103, 76, 39, 211, 191, 115, 165, 206, 30, 7, 98, 156, 205, 181, 89, 252, 58, 138, 253, 104, 212, 236, 54, 224, 166, 155, 118, 8, 93, 140, 28, 95, 225, 248, 80, 182, 112, 63, 192, 116, 47, 217, 91, 84, 144, 53, 124, 117, 16, 73, 218, 254, 188, 18, 11, 107, 222, 5, 52, 129, 194, 173, 81, 9, 137, 246, 242, 143, 175, 147, 74, 195, 41, 133, 207, 120, 92, 17, 164, 169, 171, 48, 241, 57, 31, 83, 55, 96, 29, 185, 68, 232, 70, 148, 243, 209, 100, 214, 37, 244, 219, 131, 203, 139, 126, 183, 167, 199, 101, 159, 50, 230, 168, 45, 149, 123, 119, 87, 134, 75, 127, 67, 250, 228, 247, 135, 113, 60, 62, 177, 150, 121, 162, 227, 142, 34, 178, 42, 15, 160, 161, 216, 235, 234, 163, 186, 154, 141, 233, 208, 78, 151, 204, 190, 86, 152, 245, 239, 108, 196, 158, 210, 99, 237, 251, 3, 40, 90, 125, 132, 36, 215, 193, 71, 255, 200, 102, 56, 32, 136, 146, 79, 97, 110, 249, 20, 202, 231, 122, 88, 94, 6, 153, 105, 14, 10, 2, 201, 189, 213, 51, 26], [246, 56, 103, 21, 181, 105, 216, 118, 145, 183, 169, 211, 27, 242, 190, 162, 237, 179, 244, 199, 206, 35, 120, 38, 95, 133, 25, 231, 3, 70, 40, 238, 223, 45, 127, 245, 4, 15, 250, 11, 52, 215, 142, 129, 167, 191, 61, 241, 188, 226, 249, 146, 221, 184, 104, 109, 157, 39, 176, 114, 236, 240, 254, 253, 251, 158, 198, 37, 42, 19, 87, 230, 153, 43, 77, 76, 208, 26, 32, 18, 150, 195, 122, 90, 80, 148, 197, 44, 83, 51, 166, 75, 88, 73, 64, 252, 20, 119, 46, 201, 196, 121, 222, 115, 22, 128, 164, 102, 97, 5, 217, 172, 177, 81, 58, 234, 168, 60, 29, 124, 147, 101, 224, 151, 130, 65, 98, 225, 155, 91, 108, 152, 140, 219, 9, 24, 189, 203, 138, 160, 59, 48, 193, 14, 69, 159, 233, 53, 135, 143, 33, 165, 41, 132, 57, 187, 227, 93, 200, 1, 0, 149, 137, 194, 23, 117, 170, 247, 17, 255, 92, 205, 47, 213, 136, 66, 2, 209, 6, 110, 78, 63, 28, 74, 235, 229, 30, 139, 154, 94, 131, 49, 86, 185, 163, 79, 68, 8, 72, 174, 99, 111, 141, 107, 210, 34, 207, 239, 106, 144, 228, 186, 89, 204, 55, 54, 171, 161, 100, 16, 13, 7, 50, 182, 112, 173, 212, 31, 214, 85, 156, 180, 175, 116, 248, 243, 36, 82, 134, 123, 220, 10, 125, 96, 67, 62, 12, 202, 126, 71, 84, 113, 232, 178, 192, 218], [46, 38, 43, 106, 114, 176, 12, 69, 1, 21, 82, 27, 184, 109, 170, 0, 179, 25, 4, 145, 33, 61, 66, 223, 85, 238, 22, 23, 59, 64, 19, 174, 180, 240, 111, 128, 187, 65, 72, 35, 77, 221, 157, 172, 13, 197, 44, 229, 226, 130, 220, 49, 198, 24, 103, 76, 39, 211, 191, 115, 165, 206, 30, 7, 98, 156, 205, 181, 89, 252, 58, 138, 253, 104, 212, 236, 54, 224, 166, 155, 118, 8, 93, 140, 28, 95, 225, 248, 80, 182, 112, 63, 192, 116, 47, 217, 91, 84, 144, 53, 124, 117, 16, 73, 218, 254, 188, 18, 11, 107, 222, 5, 52, 129, 194, 173, 81, 9, 137, 246, 242, 143, 175, 147, 74, 195, 41, 133, 207, 120, 92, 17, 164, 169, 171, 48, 241, 57, 31, 83, 55, 96, 29, 185, 68, 232, 70, 148, 243, 209, 100, 214, 37, 244, 219, 131, 203, 139, 126, 183, 167, 199, 101, 159, 50, 230, 168, 45, 149, 123, 119, 87, 134, 75, 127, 67, 250, 228, 247, 135, 113, 60, 62, 177, 150, 121, 162, 227, 142, 34, 178, 42, 15, 160, 161, 216, 235, 234, 163, 186, 154, 141, 233, 208, 78, 151, 204, 190, 86, 152, 245, 239, 108, 196, 158, 210, 99, 237, 251, 3, 40, 90, 125, 132, 36, 215, 193, 71, 255, 200, 102, 56, 32, 136, 146, 79, 97, 110, 249, 20, 202, 231, 122, 88, 94, 6, 153, 105, 14, 10, 2, 201, 189, 213, 51, 26], [206, 165, 193, 37, 187, 108, 248, 246, 44, 139, 152, 201, 173, 214, 77, 72, 97, 35, 70, 24, 3, 79, 178, 175, 30, 66, 18, 198, 114, 125, 32, 210, 180, 224, 235, 28, 62, 136, 149, 227, 82, 147, 90, 119, 85, 199, 126, 121, 51, 20, 88, 4, 75, 101, 38, 151, 109, 115, 110, 223, 43, 17, 146, 249, 226, 26, 222, 232, 87, 195, 200, 131, 245, 81, 113, 157, 220, 12, 16, 184, 204, 192, 84, 31, 197, 215, 129, 94, 93, 181, 218, 194, 65, 148, 158, 112, 221, 34, 25, 33, 243, 78, 10, 67, 209, 6, 252, 196, 237, 42, 172, 164, 161, 244, 111, 191, 46, 170, 128, 69, 183, 212, 60, 99, 8, 122, 49, 86, 247, 96, 179, 57, 135, 106, 0, 58, 100, 202, 55, 98, 1, 254, 53, 155, 156, 83, 132, 9, 19, 171, 48, 95, 166, 68, 22, 104, 7, 14, 142, 211, 213, 50, 150, 234, 182, 203, 217, 64, 185, 163, 73, 45, 41, 118, 103, 134, 186, 230, 241, 250, 52, 207, 162, 124, 140, 116, 167, 228, 92, 63, 47, 176, 239, 238, 5, 216, 225, 188, 137, 160, 80, 231, 102, 11, 89, 91, 59, 23, 240, 105, 153, 177, 138, 219, 174, 123, 36, 159, 76, 21, 56, 242, 61, 107, 133, 143, 154, 130, 233, 15, 145, 255, 13, 189, 120, 251, 236, 117, 208, 190, 169, 168, 74, 229, 54, 2, 39, 127, 29, 253, 141, 71, 205, 40, 144, 27]]
ct = ['e5a304ea2ffc53a1ff94337c2b2ae5368b46c6da3cc37f8438eb967b29249d4e', '6733baa353d4cfc4ff94337c58dc7fdbd6df83f4fbf6e5e838eb967b98d7e8d3', 'e77dbfe7868701fbd7072e6358dc7fdba067d296707bad1b0f4541dc98d7e8d3', '54b772d532556d5573a6ab667c9ff76857b5efc3b62130668e46a79b163138e4', '47339f6738dd9f4c9581fbd496dde76ea320d95b457e0373cddb910acc41fe35']
"""

util.py

from random import sample

i2l = lambda x: [(x >> 24) & 0xff, (x >> 16) & 0xff, (x >> 8) & 0xff, x & 0xff]
l2i = lambda x: (x[0] << 24)|(x[1] << 16)|(x[2] << 8)|x[3]
rotl32 = lambda x, n: ((x << n) & 0xffffffff) | ((x >> (32-n)) & 0xffffffff)
rotl8 = lambda x, n: ((x << n) & 0xff) | ((x >> (8-n)) & 0xff)
xor = lambda x, y: list(map(lambda a, b: a ^ b, x, y))
pad = lambda data, block=16: data + [16 - len(data) % block]*(16 - len(data) % block)


SM4_BOXES_TABLE = [
    0xd60x900xe90xfe0xcc0xe10x3d0xb70x160xb60x140xc20x280xfb0x2c,
    0x050x2b0x670x9a0x760x2a0xbe0x040xc30xaa0x440x130x260x490x86,
    0x060x990x9c0x420x500xf40x910xef0x980x7a0x330x540x0b0x430xed,
    0xcf0xac0x620xe40xb30x1c0xa90xc90x080xe80x950x800xdf0x940xfa,
    0x750x8f0x3f0xa60x470x070xa70xfc0xf30x730x170xba0x830x590x3c,
    0x190xe60x850x4f0xa80x680x6b0x810xb20x710x640xda0x8b0xf80xeb,
    0x0f0x4b0x700x560x9d0x350x1e0x240x0e0x5e0x630x580xd10xa20x25,
    0x220x7c0x3b0x010x210x780x870xd40x000x460x570x9f0xd30x270x52,
    0x4c0x360x020xe70xa00xc40xc80x9e0xea0xbf0x8a0xd20x400xc70x38,
    0xb50xa30xf70xf20xce0xf90x610x150xa10xe00xae0x5d0xa40x9b0x34,
    0x1a0x550xad0x930x320x300xf50x8c0xb10xe30x1d0xf60xe20x2e0x82,
    0x660xca0x600xc00x290x230xab0x0d0x530x4e0x6f0xd50xdb0x370x45,
    0xde0xfd0x8e0x2f0x030xff0x6a0x720x6d0x6c0x5b0x510x8d0x1b0xaf,
    0x920xbb0xdd0xbc0x7f0x110xd90x5c0x410x1f0x100x5a0xd80x0a0xc1,
    0x310x880xa50xcd0x7b0xbd0x2d0x740xd00x120xb80xe50xb40xb00x89,
    0x690x970x4a0x0c0x960x770x7e0x650xb90xf10x090xc50x6e0xc60x84,
    0x180xf00x7d0xec0x3a0xdc0x4d0x200x790xee0x5f0x3e0xd70xcb0x39,
    0x48,
]

SM4_FK = [0xa3b1bac60x56aa33500x677d91970xb27022dc]

SM4_CK = [
    0x00070e150x1c232a310x383f464d0x545b6269,
    0x70777e850x8c939aa10xa8afb6bd0xc4cbd2d9,
    0xe0e7eef50xfc030a110x181f262d0x343b4249,
    0x50575e650x6c737a810x888f969d0xa4abb2b9,
    0xc0c7ced50xdce3eaf10xf8ff060d0x141b2229,
    0x30373e450x4c535a610x686f767d0x848b9299,
    0xa0a7aeb50xbcc3cad10xd8dfe6ed0xf4fb0209,
    0x10171e250x2c333a410x484f565d0x646b7279
]

box = sample(SM4_BOXES_TABLE, 256)
Dance_Box = [box, sample(box, 256), box, sample(box, 256)]

def dance():
    global Dance_Box
    Dance_Box = Dance_Box[2:]+Dance_Box[:2]

def round_key(k):
    ar = [SM4_BOXES_TABLE[i] for i in i2l(k)]
    b = l2i(ar)
    return b ^ rotl32(b, 13) ^ rotl32(b, 23)

def expand_key(master_key):
    master_key = list(master_key)
    MK = [l2i(master_key[:4]), l2i(master_key[4:8]),
           l2i(master_key[8:12]), l2i(master_key[12:])]
    k = [0]*36
    k[0:4] = xor(MK, SM4_FK)
    for i in range(32):
        k[i + 4] = k[i] ^ (round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[i]))
    return k[4:]

def tfunc(bk):
    ar = [SM4_BOXES_TABLE[i] for i in i2l(bk)]
    b = l2i(ar)
    return b ^ rotl32(b, 2) ^ rotl32(b, 10) ^ rotl32(b, 18) ^ rotl32(b, 24)

def pfunc(bk):
    res = []
    for i in range(4):
        sbox = Dance_Box[i]
        ar = [sbox[_] for _ in i2l(bk[i])]
        b = [rotl8(ar[i], i+3for i in range(4)]
        res.append(l2i(b))
    return res

def one_round(bk, rk, dt):
    out = []
    buf = [0]*36
    buf[:4] = [l2i(bk[:4]), l2i(bk[4:8]), l2i(bk[8:12]), l2i(bk[12:])]
    for i in range(32):
        if dt == i:
            dance()
        buf[i+4] = buf[i] ^ tfunc(buf[i+1]^buf[i+2]^buf[i+3]^rk[i])
        buf[i+1:i+5] = pfunc(buf[i+1:i+5])
    dance()
    for _ in range(4):
        out += i2l(buf[-1-_])
    return out
    
def crypt_ecb(pt, key, dance_time=-1):
    pt = pad(list(pt))
    rk = expand_key(key)
    block = [pt[_:_+16for _ in range(0, len(pt), 16)]
    result = b''
    for i in block:
        result += bytes(one_round(i, rk, dt=dance_time))
    return result

整体分析

这道题目的题面比较简单,就是用类 sm4 加密了 flag 总共五次,唯一有区别的点在于每次的 dance_time 不同,分别是倒数第一、二、三、四、五轮。

对于这样多轮的分组加密,我们关注到单独一轮上,

def pfunc(bk):
    res = []
    for i in range(4):
        sbox = Dance_Box[i]
        ar = [sbox[_] for _ in i2l(bk[i])]
        b = [rotl8(ar[i], i+3for i in range(4)]
        res.append(l2i(b))
    return res

...
        if dt == i:
            dance()
        buf[i+4] = buf[i] ^ tfunc(buf[i+1]^buf[i+2]^buf[i+3]^rk[i])
        buf[i+1:i+5] = pfunc(buf[i+1:i+5])
...

以此画出一个很美丽的流程图

好题分享系列 - 2023 N1CTF - e2$m4

区别于经典的 SM4,这里的轮加密在经过 f_func 后,还做了一个额外的 p_func,不过这里的 盒已知, 是一个循环移位,也是可逆的。

用的是代码中的 Dance_Box,而 dance 会将 4 个 Dance_Box 的前两个和后两个互换一下位置,不过 Dance_Box 的第一个和第三个box是一样的,所以其实换的只是第 2,4 两个子 box

box = sample(SM4_BOXES_TABLE, 256)
Dance_Box = [box, sample(box, 256), box, sample(box, 256)]

def dance():
    global Dance_Box
    Dance_Box = Dance_Box[2:]+Dance_Box[:2]

这里 dance 使得 更新,其实可以类比于一个故障注入:

首先我们需要知道这个 即 p_func 是可逆的,于是我们可以构造对应的逆向函数 p_revfunc

对于第一个密文,我们对其进行反反序操作(sm4加密最后一轮有一个对密文的反序操作)后,再接一个 p_revfunc 操作(注意这里 p_revfunc 用的是 dance 后的 box)是可以获取到第32轮(从1开始计数)的sm4 的 f_func 函数输出结果 x1|x2|x3|o 的。

对于第二个密文,我们对其进行反反序操作(sm4加密最后的密文有一个反序操作)后,再接一个 p_revfunc 操作,也是可以获取到第32轮(从1开始计数)的 f_func 函数输出结果的,不过这个结果的输入,和前面的输入是不同的。

虽然输入都是由前一轮的 p_func 输出而来,但是前面的输入用的 p_func 是没dance过的 box,这里的输入用的 p_func 是dance过的box。也就是说 dance 的存在,使得第一个密文和第二个密文不同,这个不同具体发生在第三十二轮的输入,也就是三十一轮的输出。即相当于对最后一轮的加密做了一个输入的故障注入。

好题分享系列 - 2023 N1CTF - e2$m4

我们设第一个密文的第三十一轮输出是 ,那么第二个密文的第三十一轮输出就是 (因为不管 dance 与否,第一个和第三个box是不变的)。

于是第一个密文的第三十二轮输出就是 ,第二个密文的第三十一轮输出是

此时两边 p_func 用的盒子都是 dance过的了,我们简记第三十二轮的输出分别为 和

最后的密文输出再进行一个反序操作,就是 和

这和我们所得到的前两个密文的形式是符合的,第 8-12 个字节相同。

好题分享系列 - 2023 N1CTF - e2$m4

流程理清楚之后我们再回到单轮加密流程

由于其四分之一的 fesitel 结构,通过密文(进行一些逆向操作)我们是可以获取到进入 S盒(非线性部分)的输入 的。针对第一条和第二条密文,就是第三十二轮的输入   和

然后反序密文,再接一个 p_revfunc 我们能获取到第三十二轮 f_func 的输出差分 ,由于需要针对 盒,所以我们关注这个 ,

我们爆破最后一轮的轮密钥 , 通过两个输入,计算可得到输出: ,计算它们的差分,如果等于 ,则该 可作为轮密钥的一个候选。

随后我们就可以利用候选 解密最后一轮密文,再往上走一轮。利用第二条和第三条密文,这里的 dance 就相当于对倒数第二轮的 盒输入做了一个扰动,于是故技重施我们就能搞到候选 ,继而恢复 。有了四个轮密钥,我们也就能推出前面所有的轮密钥了。从而也就能解密密文,恢复密文获得flag了。

下面是一些攻击的实现细节。

攻击细节

首先我们获取一下输出差分 ,需要先操作(先反序,再 p_revfunc )一下密文。

def rev(data):
    c0 = bytes.fromhex(data)
    cl0 = [c0[:4], c0[4:8], c0[8:12], c0[12:]][::-1]
    for _ in range(4):
        cl0[_] = int(cl0[_].hex(), 16)
    return cl0
    
block = []
for _ in range(5):
    block.append((rev(ct[_][:32]), rev(ct[_][32:])))

p_revfunc 函数

p_func  函数分为 和 两个环节,首先是循环移位的逆,反着来就好了

ar = [rotl8(b[i], 5-i) for i in range(4)]

而 盒是一个可以看作是一个满射的函数,所以也是可逆的,相应的求逆也是比较简单

记 是 P 盒的输出, 是 盒的输入,那么已知 求 :

tp = [sbox.index(ar[i]) for i in range(4)]

所以

l2i = lambda x: (x[0] << 24)|(x[1] << 16)|(x[2] << 8)|x[3]
rotl8 = lambda x, n: ((x << n) & 0xff) | ((x >> (8-n)) & 0xff)

def invp(bk, db):
    res = []
    for i in range(4):
        sbox = db[i]
        b = i2l(bk[i])
        ar = [rotl8(b[i], 5-i) for i in range(4)]
        tp = [sbox.index(ar[i]) for i in range(4)]
        res.append(l2i(tp))
    return res

_Dance_Box = Dance_Box[2:]+Dance_Box[:2]
cl0 = invp(block[0][0],_Dance_Box)
cl1 = invp(block[1][0],_Dance_Box)

最后计算输出差分

df_out = cl0[-1]^^cl1[-1]

不过这还不是 盒的输出差分,因此我们还要进一步逆 函数。

逆循环自异或 L 函数

函数具体在源代码的 tfunc 中(也就是上文,或者图中的 f_func)内容是

b ^^ rotl32(b, 2) ^^ rotl32(b, 10) ^^ rotl32(b, 18) ^^ rotl32(b, 24)

即已知 a = b ^^ rotl32(b, 2) ^^ rotl32(b, 10) ^^ rotl32(b, 18) ^^ rotl32(b, 24)

b

这一部分的内容我们需要一点线性代数的知识。

我们知道异或是可以看作在模 2 下的加法的,而ab 是一个 32 比特的比特串。并且针对这条式子,例如输出 a 的第一个比特 其实是由 而来,实际上我们有

对于 a 的 32 个比特,我们可以构造 32 条关系式,于是我们可以将其写作矩阵的形式,然后解一下即可还原 a

def invl(num):
    A = matrix(GF(2), 3232)
    shift = [02101824]
    for delta in shift:
        for _ in range(32):
            A[_, (_+delta)%32] = 1
    u = vector(GF(2), list(map(int, bin(num)[2:].zfill(32))))
    v = A^(-1)*u
    m = ''.join(list(map(str, v)))
    return int(m, 2)

好题分享系列 - 2023 N1CTF - e2$m4

随后我们就能获得 盒的四个输出,并计算相应的输出差分了。

df_out_s = invl(df_out)

爆破轮密钥 recover_key

有了输出差分,我们再获取一下两个输入

in0 = 0
in1 = 0
for _ in range(3):
    in0 ^^= cl0[_]
    in1 ^^= cl1[_]

再准备爆破密钥,并放入 盒计算输出,如果输出差分于 df_out_s,则该密钥加入候选

def search(in0, in1, do, S):
    candidate=[]
    for i in range(256):
        in00 = in0^^i
        in01 = in1^^i
        if S[in00]^^S[in01] == do:
            candidate.append(i)
    return candidate
        
RK=[]
for _ in range(4):
    RK.append(search(in0&0xff, in1&0xff, df_out_s&0xff, SM4_BOXES_TABLE))
    in0 >>= 8
    in1 >>= 8
    df_out_s >>= 8
    
RK=RK[::-1]

由于 S[in00]^^S[in01] == S[in01]^^S[in00] ,即假设候选密钥 符合要求,那么 也能通过判断。所以会出现至少两个符合的候选密钥,不过刚好 flag 的密文有两个分组,因此可以用第二组密文再跑一组候选密钥出来,然后两组合并一下取交集,最后合并一下就能获取这一轮的轮密钥了。

后续也能利用最后一轮的轮密钥,往上恢复一轮,再利用第二、三条密文,获取倒数第二轮的轮密钥,以此类推。

就这样吧!(完整解密脚本可以去 N1CTF 官方仓库翻翻,https://github.com/Nu1LCTF/n1ctf-2023/tree/main/crypto/e2%24m4)

(PS:这里为啥要用差分分析呢?因为我们无法获得上一轮输入的前四个字节,所以无法准确的计算出 S 盒的输出。但是 dance 操作不影响第一个子 box,所以通过计算差分,能够消除前四个字节的影响,获取到准确的 S 盒的输出差分。不过差分信息并不能倒推出轮密钥来,所以我们还需要再爆破一下。)

好题分享系列 - 2023 N1CTF - e2$m4

原文始发于微信公众号(Van1sh):好题分享系列 - 2023 N1CTF - e2$m4

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年2月9日01:04:02
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   好题分享系列 - 2023 N1CTF - e2$m4https://cn-sec.com/archives/2420866.html

发表评论

匿名网友 填写信息