巅峰极客SM4

发布于 2021-08-16  107 次阅读





差分攻击3

learnSM4

逆算法解法

鸽了好久的这题,一定是因为本地不好跑task脚本(实际上就是自己懒狗),今天魔改了一下task脚本,直接在python里交互了,去掉了POW的部分。

import signal,os,random,string
from hashlib import sha256
from sm4 import encrypt,decrypt,encrypt_
from Crypto.Util.number import long_to_bytes,bytes_to_long
key = os.urandom(16)
key = bytes_to_long(key)
print("Welcome to the Crypto System.")
from sm4 import _round_keys
keys = _round_keys(key)
hint1 = sha256(str(keys[0]).encode()).hexdigest()
print('hint is : '+hint1+'\n')
hint = 'Next you have 16 shots.\n'
print(hint)
for i in range(8):
    print('r:')
    r = input()
    r = int(r)
    if r <2:
        print('i:')
        i = input()
        i = abs(int(i))
        if i <4:
            print('msg(hex):\n')
            msg = input()
            msg = int(msg[:32],16)
            if msg == 0:
                print('Dont cheat\n')
                break
            else:
                msg,leak = encrypt_(msg,key,r,i)
                print(hex(msg)[2:10]+'\n')
                print(str(leak)+'\n')
        else:
            print('Dont cheat\n')
            break
    else:
        print('Dont cheat\n')
        break
print('Give me answer:')
k1 = int(input())
if k1 == keys[0]:
    print('flag')
def _crypthack(num, mk, rou,index):
    x_keys = list(_byte_unpack(num, byte_n=16))
    round_keys = _round_keys(mk)
    leak = 0 
    for i in _range(32):
        reg = _round_f(x_keys[i:i+4], round_keys[i])
        x_keys.append(reg)
        reg = _byte_unpack(reg)
        if i == rou:
            leak = reg[index]
    return _byte_pack(x_keys[-4:][::-1], byte_n=16),leak

上面分别是魔改的本地运行task和SM4加密的函数。题目需要我们得到key0,也就是​,先给了我们它的sha256值,去cmd5查一下,有答案但是要氪金,自己本地做就不氪了。我们可以给服务端发送msg,以及我们想知道的密文的一个字节(即的第个字节)。

在上一节我们学习过了SM4算法,结合之前对MT19937逆向的知识,可以知道的是,如果我们获得了一个完整的,就可以恢复

因为​对应的盒有​盒,而线性变换又可以恢复,所以恢复方法如下

由于不允许msg为0,我们可以让,其余位均为0,即令

当然也可以取别的,这里只是为了方便,这样的运算简化为

from Crypto.Util.number import long_to_bytes
def getnum(arr):
    HEX = ''
    for i in arr:
        HEX += hex(i)[2:]
    return int(HEX, 16)
def shift_left(int_value, k, bit):
    b = '0' * (bit - int_value.bit_length()) + str(bin(int_value)[2:])
    b = b[k:] + b[:k]
    print(b)
    return int(b, 2)
def L_1(c):
    bit = [2, 4, 8, 12, 14, 16, 18, 22, 24, 30]
    b = c
    for i in bit:
        b ^= shift_left(c, i, 32)
    return b
S_BOX = {
    ......
}
x4 = [161, 203, 79, 94]
S_1Box = {value: key for key, value in S_BOX.items()}
X4 = getnum(x4)
c = X4 ^ 1
b = long_to_bytes(L_1(c))
key = ''
for i in b:
    key += hex(S_1Box[i])[2:]
print(int(key, 16))
#https://tearsjin.github.io/2021/07/31/writeup-for-2021-%E5%B7%85%E5%B3%B0%E6%9E%81%E5%AE%A2/

差分解法

这题除了这样做,也有密码爷爷用差分做出来的,以下是用差分攻击对这题的分析。

Case Study: Differetial Cryptanalysis Attack | Soreat_u's Blog (soreatu.com)

from pwn import *
from collections import Counter
import itertools
import random
from hashlib import sha256
SM4_BOXES_TABLE = [
    0xd6,0x90,0xe9,0xfe,0xcc,0xe1,0x3d,0xb7,0x16,0xb6,0x14,0xc2,0x28,0xfb,0x2c,
    0x05,0x2b,0x67,0x9a,0x76,0x2a,0xbe,0x04,0xc3,0xaa,0x44,0x13,0x26,0x49,0x86,
    0x06,0x99,0x9c,0x42,0x50,0xf4,0x91,0xef,0x98,0x7a,0x33,0x54,0x0b,0x43,0xed,
    0xcf,0xac,0x62,0xe4,0xb3,0x1c,0xa9,0xc9,0x08,0xe8,0x95,0x80,0xdf,0x94,0xfa,
    0x75,0x8f,0x3f,0xa6,0x47,0x07,0xa7,0xfc,0xf3,0x73,0x17,0xba,0x83,0x59,0x3c,
    0x19,0xe6,0x85,0x4f,0xa8,0x68,0x6b,0x81,0xb2,0x71,0x64,0xda,0x8b,0xf8,0xeb,
    0x0f,0x4b,0x70,0x56,0x9d,0x35,0x1e,0x24,0x0e,0x5e,0x63,0x58,0xd1,0xa2,0x25,
    0x22,0x7c,0x3b,0x01,0x21,0x78,0x87,0xd4,0x00,0x46,0x57,0x9f,0xd3,0x27,0x52,
    0x4c,0x36,0x02,0xe7,0xa0,0xc4,0xc8,0x9e,0xea,0xbf,0x8a,0xd2,0x40,0xc7,0x38,
    0xb5,0xa3,0xf7,0xf2,0xce,0xf9,0x61,0x15,0xa1,0xe0,0xae,0x5d,0xa4,0x9b,0x34,
    0x1a,0x55,0xad,0x93,0x32,0x30,0xf5,0x8c,0xb1,0xe3,0x1d,0xf6,0xe2,0x2e,0x82,
    0x66,0xca,0x60,0xc0,0x29,0x23,0xab,0x0d,0x53,0x4e,0x6f,0xd5,0xdb,0x37,0x45,
    0xde,0xfd,0x8e,0x2f,0x03,0xff,0x6a,0x72,0x6d,0x6c,0x5b,0x51,0x8d,0x1b,0xaf,
    0x92,0xbb,0xdd,0xbc,0x7f,0x11,0xd9,0x5c,0x41,0x1f,0x10,0x5a,0xd8,0x0a,0xc1,
    0x31,0x88,0xa5,0xcd,0x7b,0xbd,0x2d,0x74,0xd0,0x12,0xb8,0xe5,0xb4,0xb0,0x89,
    0x69,0x97,0x4a,0x0c,0x96,0x77,0x7e,0x65,0xb9,0xf1,0x09,0xc5,0x6e,0xc6,0x84,
    0x18,0xf0,0x7d,0xec,0x3a,0xdc,0x4d,0x20,0x79,0xee,0x5f,0x3e,0xd7,0xcb,0x39,
    0x48]
conn = remote("47.104.94.208", 54740)
context.log_level = 'debug'
#proof of work
rec = conn.recvline().decode()
suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0]
digest = re.findall(r'== (.*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")
print('Calculating hash...')
for i in itertools.product(string.ascii_letters + string.digits, repeat=4):
    prefix = ''.join(i)
    guess = prefix + suffix
    if sha256(guess.encode()).hexdigest() == digest:
        print(guess)
        break
conn.sendlineafter(b'Give me XXXX:', prefix.encode())


def ltor(b, l):
    bits = bin(b)[2:]
    return int(bits[-l:] + bits[:-l], 2)


def diff_attack(r_bytes,f_bytes,diff_outs):
    candidate_keys = Counter()
    for rk_byte in range(256):
        for r_byte, f_byte, d_out in zip(r_bytes, f_bytes, diff_outs):
            if SM4_BOXES_TABLE[r_byte^rk_byte] ^ SM4_BOXES_TABLE[f_byte^rk_byte] ==d_out:
                candidate_keys[rk_byte] += 1
    print(candidate_keys)
    return candidate_keys.most_common()[0][0]


conn.recvuntil(b'hint is : ')
digest = conn.recvline().strip().decode()
#4 bytes
rk_bytes = [0, 0, 0, 0]
for j in [1,3]:
    inp_out_bytes = []
    msg = [random.randint(0, 255) for _ in range(4)]
    for _ in range(1, 5):
        byte = random.randint(0, 255)
        msg[j] = byte
        send_msg = int.from_bytes(bytes(msg), 'little')
        conn.sendlineafter(b"r:", b"0")
        conn.sendlineafter(b"i:", str((j-1)%4).encode())
        conn.sendlineafter(b"msg(hex):", hex(send_msg)[2:])
        conn.recvline() # msg[2:10]
        conn.recvline() # msg[2:10]
        X4_j_1_byte = int(conn.recvline())
        inp_out_bytes.append((byte, X4_j_1_byte))

    r_bytes = []
    f_bytes = []
    diff_outs = list()
    for comb in itertools.combinations(inp_out_bytes, 2):
        a, b = comb
        r_bytes.append(a[0])
        f_bytes.append(b[0])
        diff_outs.append(ltor(a[1]^b[1], 2))
    rk_byte = diff_attack(r_bytes, f_bytes, diff_outs)

    rk_bytes[j] = rk_byte
    #rk = (rk << 8) + rk_byte
    print(f"[{j}] rk_byte: {rk_byte}")

print(rk_bytes)

for guess in range(2**16):
    rk_bytes[0], rk_bytes[2] = divmod(guess, 256)

    key = int.from_bytes(bytes(rk_bytes), 'little')
    if sha256(str(key).encode()).hexdigest() == digest:
        print(f"key: {key}")
        conn.sendlineafter(b"Give me answer:", str(key).encode())
        flag = conn.recvline()
        print(flag)
        break
conn.close()

SM4差分攻击,需要恢复出第⼀组⼦密钥,⼀共4bytes。有8次机会,理论上每⼀个byte都可以消耗掉2次机会来获 取,但是成功率太低了。所以改⽤4次机会分别对第1、3个byte进⾏恢复,剩下第0、2个byte可以根据摘要值来爆 破(总共65536次hash运算,很快的)。

密码爷爷的叙述:

子密钥32字节,给了8次机会,可以拿前两轮状态的某个中间值,可以用差分的方法,逐字节算出第1轮子密钥,但是只给了8次机会,差分需要两组输入,要32bits,就需要4次差分,但是对于每一次差分,它很大概率上不能求出准备的那一byte。所以,对于4bytes中的2个byte,分别用4个输入,可以组成6次差分,可以很准确求出来这2个byte,然后剩余的另外2个byte,根据hash值爆破一下。