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，也就是
在上一节我们学习过了SM4算法，结合之前对MT19937逆向的知识，可以知道的是，如果我们获得了一个完整的
因为
由于不允许msg为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值爆破一下。
Comments NOTHING