# Case Study: Differetial Cryptanalysis Attack

(2021.11.20更新）可以看这位师傅的文章

## WMCTF idiot box

hellman yyds!

c’为第3个F函数input的差分值，D’为第4个F函数input的差分值，F’为第6个F函数output的差分值，$T_L’$是密文左半部分的差分值。

DES里面就sbox比较难搞，其他的部分就是一些线性置换，可以通过一些差分特性去操作一下这个sbox，然后就能得到key。

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import Counter ... def gen_diff_output(diff): p1 = getRandomNBitInteger(32) p2 = p1 ^ diff k = getRandomNBitInteger(48) c1, c2 = F(p1, k), F(p2, k) return c1^c2, (p1,p2,c1,c2) counter = Counter() for i in range(10000): P_ = 0x00000040 X_, _ = gen_diff_output(P_) counter[X_] += 1 X_, freq = counter.most_common(1)[0] print(hex(X_)[2:].rjust(8,'0'), freq / 10000) # 0x00000002 -> 0x00000002 0.217 # 0x00000040 -> 0x00000000 0.2534 # 0x00000400 -> 0x00000000 0.251 # 0x00000000 -> 0x00000000 1 # 0x00002000 -> 0x00000000 0.25 # 0x00004000 -> 0x00000040 0.22 # 0x00020000 -> 0x00020000 0.18

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import re from json import dump from tqdm import tqdm from Crypto.Util.number import long_to_bytes, getRandomNBitInteger from pwn import * def gen_diff_input(diff): p1 = getRandomNBitInteger(64) p2 = p1 ^ diff return p1, p2 r = remote("81.68.174.63", 34129) # context.log_level = "debug" rec = r.recvuntil(b"required").decode() cipher_flag = re.findall(r"\n([0-9a-f]{80})\n", rec)[0] print(cipher_flag) r.recvline() pairs = [] for i in tqdm(range(10000)): p1, p2 = gen_diff_input(0x0000000000000040) r.sendline(long_to_bytes(p1).hex().encode()) c1 = int(r.recvline(keepends=False), 16) r.sendline(long_to_bytes(p2).hex().encode()) c2 = int(r.recvline(keepends=False), 16) pairs.append(((p1,p2), (c1,c2))) r.close() dump([cipher_flag, pairs], open("data", "w"))

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 from collections import Counter from json import load from tqdm import tqdm cipher_flag, pairs = load(open("data", "r")) ... def inv_key(key): inv_key = [0]*48 key_bin = bin(key)[2:].rjust(48, '0') for j in range(48): inv_key[pc_key[j]] = key_bin[j] return int(''.join(inv_key), 2) def inv_keys(k6): keys = [0]*6 keys[-1] = k6 for i in range(4,-1,-1): keys[i] = inv_key(keys[i+1]) return keys def inv_p(x): x_bin = [int(_) for _ in bin(x)[2:].rjust(32, '0')] y_bin = [0]*32 for i in range(32): y_bin[pbox[i]] = x_bin[i] y = int(''.join([str(_) for _ in y_bin]), 2) return y # -------------------------- candidate_keys = [Counter() for _ in range(8)] for _, cs in tqdm(pairs): c1, c2 = cs if c1 ^ c2 == 0x0000004000000000: continue l1, l2 = c1 >> 32, c2 >> 32 r1, r2 = c1 & 0xffffffff, c2 & 0xffffffff # print(r1, r2) F_ = l1^l2^0x00000040 F_ = inv_p(F_) # xor of the two outputs of sbox, 32bit Ep1 = e(r1) # 48bit Ep2 = e(r2) # 48bit for i in range(8): inp1 = (Ep1 >> (7-i)*6) & 0b111111 # 6bit inp2 = (Ep2 >> (7-i)*6) & 0b111111 # 6bit out_xor = (F_ >> (7-i)*4) & 0b1111 # 4bit for key in range(64): if s(inp1^key, i) ^ s(inp2^key, i) == out_xor: candidate_keys[i][key] += 1 print(candidate_keys) # ---------------------- key6 = [] for c in candidate_keys: print(c.most_common(2)) key6.append(c.most_common(1)[0][0]) print(key6) # key6 = [53, 44, 38, 7, 7, 30, 29, 52] k6 = sum(key6[i]<<(7-i)*6 for i in range(8)) # k6 = 236161043654516 keys = inv_keys(k6) print(keys) ps, cs = pairs[0] p1, c1 = ps[0], cs[0] assert enc_block(p1) == c1 # Ok! key is right! # To decrypt, reverse the keys. keys = keys[::-1] print(enc(bytes.fromhex(cipher_flag))) # b'WMCTF{D1ff3r3nti@1_w1th_1di0t_B0X3s}\x00\x00\x00\x00'

WMCTF{D1ff3r3nti@1_w1th_1di0t_B0X3s}

## 强网杯2020 fault

differential fault attack SM4

Min WANG,Zhen WU,Jin-tao RAO,Hang LING. Round reduction-based fault attack on SM4 algorithm[J]. Journal on Communications, 2016, 37(Z1): 98-103.

We show that if a random byte fault is induced into either the second, third or fourth word register at the input of the 28-th round, the 128-bit master key could be derived with an exhaustive search of 22.11 bits on average.

28轮的第2、3、4个寄存器出错，可以直接整出master key，很对头

The procedure of the round-key generation indicates that the master key can be easily retrieved from any four consecutive round-keys.

paper：https://wenku.baidu.com/view/df86818e79563c1ec5da71c4.html

r_byte: raw input byte f_byte: fault input byte

paper里有具体的分析，看不懂，直接看到结论。这个结论就是说sbox输出的差分值diff_out也能确定下来。

ok，然后穷举这个sbox所对应那一byte子密钥rk_byte（仅256种可能，一个子密钥有4byte，每1byte对应一个sbox），计算sbox(r_inp ^ rk_byte) ^ sbox(f_inp ^ rk_byte)，看是否等于diff_out，如果等于就说明这个byte可以作为备选子密钥byte（理论值是说这边有2.0236个可能的子密钥byte）。两次这么操作后，基本上就可以确定下这个byte到底是哪一个了。

key schedule可逆，能直接搞到master key

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 from collections import Counter import random from itertools import product from hashlib import sha256 from pwn import * from sm4 import * from func import xor, rotl, get_uint32_be, put_uint32_be, \ bytes_to_list, list_to_bytes, padding, unpadding token = b"icq3f18237ca27013a7969864ab40836" r = remote("39.101.134.52", 8006) # context.log_level = 'debug' # PoW rec = r.recvline().decode() suffix = re.findall(r'XXX\+([^\)]+)', rec)[0] digest = re.findall(r'== ([^\n]+)', rec)[0] print(f"suffix: {suffix} \ndigest: {digest}") print('Calculating hash...') for i in product(string.ascii_letters + string.digits, repeat=3): prefix = ''.join(i) guess = prefix + suffix if sha256(guess.encode()).hexdigest() == digest: print(guess) break r.sendafter(b'Give me XXX:', prefix.encode()) r.sendafter(b"teamtoken", token) r.recvuntil(b"your flag is\n") enc_flag = r.recvline().strip() print(enc_flag) plaintext = b"\x00" * 15 def ltor(b, l): bits = bin(b)[2:] return int(bits[-l:] + bits[:-l], 2) def inv_Y(cipher): # bytes -> list Y0 = get_uint32_be(cipher[0:4]) Y1 = get_uint32_be(cipher[4:8]) Y2 = get_uint32_be(cipher[8:12]) Y3 = get_uint32_be(cipher[12:16]) # X32, X33, X34, X35 return [Y3, Y2, Y1, Y0] def inv_round(Xs): return [Xs[-1], Xs[0], Xs[1], Xs[2]] def get_rk_byte(raw_cipher, fault_ciphers, j): r_res, r_X32, r_X33, r_X34 = inv_round(raw_cipher) r_byte = put_uint32_be(r_X32 ^ r_X33 ^ r_X34)[j%4] ios = [] for f_cipher in fault_ciphers: f_res, f_X32, f_X33, f_X34 = inv_round(f_cipher) diff_out = ltor(put_uint32_be(r_res ^ f_res)[(j-1)%4], 2) f_byte = put_uint32_be(f_X32 ^ f_X33 ^ f_X34)[j%4] ios.append((f_byte,diff_out)) # print(ios) candidate_keys = Counter() for rk_byte in range(256): for f_byte, diff_out in ios: if SM4_BOXES_TABLE[r_byte^rk_byte] ^ SM4_BOXES_TABLE[f_byte^rk_byte] == diff_out: candidate_keys[rk_byte] += 1 return candidate_keys.most_common()[0][0] def get_r_cipher(): r.sendlineafter(b"> ", b"1") r.sendlineafter(b"your plaintext in hex:", plaintext.hex().encode()) cipher = bytes.fromhex(r.recvline().strip().decode().split("hex:")[1]) return cipher def get_f_cipher(round, j): r.sendlineafter(b"> ", b"2") r.sendlineafter(b"your plaintext in hex:", plaintext.hex().encode()) r.sendlineafter(b"give me the value of r f p:", f"{round} {random.getrandbits(8)} {j}") cipher = bytes.fromhex(r.recvline().strip().decode().split("hex:")[1]) return cipher def f(x0, x1, x2, x3, rk): # "T algorithm" == "L algorithm" + "t algorithm". # args: [in] a: a is a 32 bits unsigned value; # return: c: c is calculated with line algorithm "L" and nonline algorithm "t" def _sm4_l_t(ka): b = [0, 0, 0, 0] a = put_uint32_be(ka) b[0] = SM4_BOXES_TABLE[a[0]] b[1] = SM4_BOXES_TABLE[a[1]] b[2] = SM4_BOXES_TABLE[a[2]] b[3] = SM4_BOXES_TABLE[a[3]] bb = get_uint32_be(b[0:4]) c = bb ^ (rotl(bb, 2)) ^ (rotl(bb, 10)) ^ (rotl(bb, 18)) ^ (rotl(bb, 24)) return c return (x0 ^ _sm4_l_t(x1 ^ x2 ^ x3 ^ rk)) def decrypt_one_round(cipher, rk): return [f(cipher[3], cipher[0], cipher[1], cipher[2], rk), cipher[0], cipher[1], cipher[2]] def decrypt_rounds(cipher, rks): for rk in rks: cipher = decrypt_one_round(cipher, rk) return cipher raw_cipher = inv_Y(get_r_cipher()) print(raw_cipher) rks = [] for round in range(31, 27, -1): # print(round) rk = 0 for j in range(4): fault_ciphers = set() for k in range(10): fault_ciphers.add(get_f_cipher(round, j)) fault_ciphers = [inv_Y(i) for i in fault_ciphers] fault_ciphers = [decrypt_rounds(f_cipher, rks) for f_cipher in fault_ciphers] rk_byte = get_rk_byte(raw_cipher, fault_ciphers, j) rk = (rk << 8) + rk_byte print(f"round {round+1} subkey: {rk}") rks.append(rk) raw_cipher = decrypt_one_round(raw_cipher, rk) def _round_key(ka): b = [0, 0, 0, 0] a = put_uint32_be(ka) b[0] = SM4_BOXES_TABLE[a[0]] b[1] = SM4_BOXES_TABLE[a[1]] b[2] = SM4_BOXES_TABLE[a[2]] b[3] = SM4_BOXES_TABLE[a[3]] bb = get_uint32_be(b[0:4]) rk = bb ^ (rotl(bb, 13)) ^ (rotl(bb, 23)) return rk # def set_key(key, mode): # key = bytes_to_list(key) # sk = []*32 # MK = [123, 456, 789, 145] # k = [0]*36 # MK[0] = get_uint32_be(key[0:4]) # MK[1] = get_uint32_be(key[4:8]) # MK[2] = get_uint32_be(key[8:12]) # MK[3] = get_uint32_be(key[12:16]) # k[0:4] = xor(MK[0:4], SM4_FK[0:4]) # for i in range(32): # k[i + 4] = k[i] ^ ( # _round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[i])) # sk[i] = k[i + 4] # return sk def inv_key_schedule(rks): k = [0] * 32 + rks[::-1] for i in range(31, -1, -1): k[i] = k[i+4] ^ (_round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[i])) print(k[4:]) Mk = [0] * 4 for j in range(4): Mk[j] = SM4_FK[j] ^ k[j] master_key = [] for i in range(4): master_key += put_uint32_be(Mk[i]) return list_to_bytes(master_key) Mk = inv_key_schedule(rks) print(Mk) r.sendlineafter(b"> ", b"3") r.sendlineafter(b"your key in hex:", Mk.hex().encode()) r.sendlineafter(b"your ciphertext in hex:", enc_flag) r.recvuntil(b"your plaintext in hex:") flag = r.recvline().strip().decode() print(bytes.fromhex(flag)) r.interactive()

## 太湖杯 Aegis

flag{50eec693-3014-4123-b285-361a68ab78e4}

## FEAL-4

Reference:

FEAL-4（Fast data Encipherment ALgorithm）是一个Fesitel结构（4轮）的block cipher. 两个日本人于1987年提出来的，打算用来取代DES（DES：“怎么可能？想多了”）。

The cipher is susceptible to various forms of cryptanalysis, and has acted as a catalyst in the discovery of differential and linear cryptanalysis.

64-bit输入，64-bit输出。

64-bit的key经过key schedule后，生成6个32-bit的round keys.

round keys之间似乎没有多少关系，无法从一个round key推出其他的round keys，更无法反推出64-bit的主密钥。

Fesitel结构，4轮操作，其中非线性的f函数是核心，其构造如下：

Python版本

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 # -*- coding: utf-8 -*- # AUTHOR: Soreat_u (2020-10-12) ''' Feal-4 Symmetric Cipher Implementation. ''' __all__ = [ 'FEAL4' ] class FEAL4(): def __init__(self, rks): self._rks = rks def encrypt(self, msg): assert isinstance(msg, bytes) assert len(msg) == 8 L = int.from_bytes(msg[:4], 'big') R = int.from_bytes(msg[4:], 'big') L = L ^ self._rks[4] R = (R ^ self._rks[5]) ^ L for r in range(3): L, R = R, L ^ FEAL4._F(R^self._rks[r]) L = L ^ FEAL4._F(R^self._rks[3]) R = L ^ R return L.to_bytes(4, 'big') + R.to_bytes(4, 'big') def decrypt(self, cipher): assert isinstance(cipher, bytes) assert len(cipher) == 8 L = int.from_bytes(cipher[:4], 'big') R = int.from_bytes(cipher[4:], 'big') ^ L for r in range(3, 0, -1): L, R = R, L ^ FEAL4._F(R^self._rks[r]) L = L ^ FEAL4._F(R^self._rks[0]) R = R ^ L L = L ^ self._rks[4] R = R ^ self._rks[5] return L.to_bytes(4, 'big') + R.to_bytes(4, 'big') @staticmethod def _G(A, B, delta): return FEAL4._rol2((A + B + delta) % 256) @staticmethod def _rol2(i): return ((i << 2) | (i >> 6)) & 0xFF @staticmethod def _F(a): A = int.to_bytes(a, 4, 'big') G1 = FEAL4._G(A[0]^A[1], A[2]^A[3], 1) G2 = FEAL4._G(G1, A[2]^A[3], 0) G3 = FEAL4._G(G2, A[3], 1) G0 = FEAL4._G(A[0], G1, 0) return int.from_bytes(bytes([G0, G1, G2, G3]), 'big') def test(): import os rks = [int.from_bytes(os.urandom(4), 'big') for _ in range(6)] # print(rks) feal4 = FEAL4(rks) msg = b"01234567" cipher = feal4.encrypt(msg) decrypted = feal4.decrypt(cipher) print(msg, cipher, decrypted, sep="\n") if __name__ == "__main__": test()

C版本

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 #include #include #define u8 uint8_t #define u32 uint32_t u32 combine(u8 *inp) { return ((u32)inp[0] << 24) | ((u32)inp[1] << 16) | ((u32)inp[2] << 8) | ((u32)inp[3]); } void split(u32 inp, u8 *res) { res[0] = inp >> 24; res[1] = inp >> 16; res[2] = inp >> 8; res[3] = inp; } u8 rol2(u8 i) { return (i << 2) | (i >> 6); } u8 G(u8 A, u8 B, u8 delta) { return rol2(A + B + delta); } u32 F(u32 A) { u8 A0 = A >> 24, A1 = A >> 16, A2 = A >> 8, A3 = A; u8 tmp[4] = {0}; tmp[1] = G(A0^A1, A2^A3, 1); tmp[2] = G(tmp[1], A2^A3, 0); tmp[3] = G(tmp[2], A3, 1); tmp[0] = G(A0, tmp[1], 0); return combine(tmp); } void encrypt(u8 *msg, u32 *rks, u8 *res) { u32 L = combine(msg), R = combine(msg+4); L = L ^ rks[4]; R = (R ^ rks[5]) ^ L; for (int r = 0; r < 3; r++) { u32 tmp = R; R = L ^ F(R^rks[r]); L = tmp; } L = L ^ F(R^rks[3]); R = L ^ R; split(L, res); split(R, res+4); } void decrypt(u8 *cipher, u32 *rks, u8 *res) { u32 L = combine(cipher), R = combine(cipher+4); R = R ^ L; for (int r = 3; r > 0; r--) { u32 tmp = R; R = L ^ F(R^rks[r]); L = tmp; } L = L ^ F(R^rks[0]); R = R ^ L; L = L ^ rks[4]; R = R ^ rks[5]; split(L, res); split(R, res+4); } int main(int argc, char const *argv[]) { u32 rks[] = { 534262442, 2244115112, 1494586470, 520548913, 2665478657, 3764657957 }; u8 msg[] = {'0', '1', '2', '3', '4', '5', '6', '7'}; u8 cipher[8] = {0}; u8 decrypted[8] = {0}; encrypt(msg, rks, cipher); decrypt(cipher, rks, decrypted); for (int i = 0; i < 8; i++) { printf("%d ", cipher[i]); } printf("\n"); for (int i = 0; i < 8; i++) { printf("%d ", decrypted[i]); } printf("\n"); return 0; }

ok，该去日它了。

• 寻找差分特征（differential characteristic）
• 构造差分路径
• 爆破子密钥

FEAL-4没有sbox，其最关键的非线性结构是最里面的G函数：模256的加法 + 循环左移2位

![Screen Shot 2020-10-12 at 4.18.14 PM](/Users/Soreat_u/Library/Application Support/typora-user-images/Screen Shot 2020-10-12 at 4.18.14 PM.png)

ok，这样我们就可以得到G函数的一个差分特征：G函数有多个输入，当其中一个输入的差分值为0x80，其他输入均相同（差分值为0x00）时，G函数输出的差分值为0x02。

6对明密文，大概率上可以得到4个可能的round key；

10对明密文，也能得到4个等价的round key；

20对明密文，也能得到4个等价的round key。