BlockCipher5

huangx607087学习分组密码的笔记5

0.About

上一篇我们讲到了DES的差分攻击，这一次就讲一下AES的积分攻击中的比较有名的Square Attack。

5. AES的Square Attack

5o01 从[DASCTF2024.10] symmetric_cipher 引入Square Attack

这一次我们直接先从题目出发

r_con = (0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,0x80, 0x1B, 0x36)
s_box = [
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
]

     
def xor_bytes(a, b):
    return bytes(i^j for i, j in zip(a, b))

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

def mix_single_column(a):
    
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def _expand_key(s):
    for i in range(10):
        word = list(s[-1])
        word.append(word.pop(0))
        word = [s_box[b] for b in word] 
        word[0] ^= r_con[i]

        s.append(xor_bytes(word, s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))

    return [s[4*i : 4*(i+1)] for i in range(len(s) // 4)]

def bytes2matrix(text):
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def encrypt(plain,r,skeys):
    plain = bytes2matrix(plain)
    add_round_key(plain, skeys[0])

    for i in range(1, r+1):
        sub_bytes(plain)
        if i %2 == 1:
            shift_rows(plain)
        if i % 2 == 0 :
            mix_columns(plain)
         
        add_round_key(plain, skeys[i])
    enc = bytes(plain[0]+plain[1]+plain[2]+plain[3])
    return enc

from Crypto.Util.number import *

for i in range(2 ** 8):
    if i == 0:
        p = b"\x00" + b"\xCB" * 15
    else:
        p = long_to_bytes(i) + b"\xCB" * 15
    pt.append(p)
    c = encrypt(p, 7, skeys)
    ct.append(c)

pt_serializable = [list(p) for p in pt]
ct_serializable = [list(c) for c in ct]

data = {'pt': pt_serializable, 'ct': ct_serializable}

with open("out1.json", "w") as f:
    json.dump(data, f)

这个题目给出了 $256$ 组明文及其对应的密文。明文格式均为 $(i,203,203,…,203)$，其中 $i$ 从 $0$ 遍历到 $256$。

回顾一下AES的过程：每一轮分别进行了字节代换、行移位、列混合和轮密钥加 4 步，其中最后一轮没有列混合操作。之所以叫积分积分攻击，可以看下面的图（参考striving师傅的博客）：

在上面的图中，对于已知的 $256$ 个密文，白色的部分表示恒定值，绿色部分在 $256$ 个密文中会遍历 $0\sim255$。我们在下面用 $x$ 代表遍历$0\sim255$ 的值，$c$ 代表恒定值，下标 $00\sim33$ 表示在矩阵中的位置。也就是我们初始的结构为：

x00 c01 c02 c03
c10 c11 c12 c13
c20 c21 c22 c23
c30 c31 c32 c33

下面我们来分析图1中产生的效果：

在轮密钥加阶段：因为AES中，对于单个字节 $x_{00} \oplus k_{00}$，由于密钥相同意味着 $k_{00}$ 恒定，因此当 $x_{00}$ 遍历 $0\sim255$ 时，$x_{00}\oplus k_{00}$ 也会遍历 $0\sim255$，而对于不变的 $c_{01}$ 等其他值，异或一个相同的 $k_{01}$，结果依然是恒定的 $c_{01}\oplus k_{00}$（两个数都恒定，当然得到恒定值）。

在字节代换阶段，由于 $S$ 盒的可逆性，因此当 $x_{00}$ 遍历 $0\sim255$ 时，$S(x_{00})$ 也会遍历 $0\sim255$ 。而对于相同的 $c_{01}$ 等其他 $15$ 个字节，由于其不变性，最终也会导致字节代换后，得到的 $S(c_{01})$ 保持不变。

在行移位阶段，由于我们考虑的是 $x_{00}$，而AES中第一行的值不会变动位置，因此 $x_{00}$ 经过行移位还是 $x_{00}$。当然，如果一开始选择下面一行，将 $x_{10}$ 作为遍历值，则 $(x_{10},c_{11},c_{12},c_{13})$ 会变成 $(c_{10}^{(1)},c^{(1)}{11},c^{(1)}{12},x^{(1)}_{13})$。

在列混合阶段，由于涉及到矩阵乘法，因此对于第 $0$ 列的数字而言，有：

由于四个 $d$ 都有 $x$ 的参与，因此第 $0$ 列的所有值由于列混合的存在，这 $4$ 个值在 $256$ 个密文中都会遍历 $0\sim255$。

随后，图1中第二轮和第三轮到列混合前的步骤，经过第一轮的讲解，也就不难理解了。也就是到第三轮列混合前，对应给定的 $256$ 个明文，$16$ 个字节全部都会遍历 $0\sim255$。

但经过第三轮的列混合后，结果出现了变化，此时矩阵中每个数字并不会遍历 $0\sim255$ 的所有值了，也就是随着 $x_{ij}^{(3)}$ 的遍历， $d^{(3)}$ 并不会遍历 $0\sim255$。

但我们将 $d^{(3)}$ （以 $d_{00}^{(3)}$ 为例）的表达式重写一下。由于四个 $x$ 都是会遍历 $0\sim255$ 的，也就是构成一个 $0\sim255$ 的排列，因此下面分别用 $p_i$表示，也就是第 $i$ 组明文中，$x_{00}^{(3)}=p_0(i)$（剩下三个以此类推）
$$
\bigoplus_{i=0}^{255}d_{00}^{(3)}=\bigoplus_{i=0}^{255}(p_{0}(i)\oplus p_1(i)\oplus p_2(i)\oplus p_3(i))=\bigoplus_{i=0}^{255}p_0(i)\oplus\bigoplus_{i=0}^{255}p_1(i)\oplus\bigoplus_{i=0}^{255}p_2(i)\oplus\bigoplus_{i=0}^{255}p_3(i)
$$
因为 $p_0,p_1,p_2,p_3$ 都是 $0\sim255$ 的一个排列，因此
$$
\bigoplus_{i=0}^{255}p_0(i)=\bigoplus_{i=0}^{255}p_1(i)=\bigoplus_{i=0}^{255}p_2(i)=\bigoplus_{i=0}^{255}p_3(i)=\bigoplus_{i=0}^{255}i=0
$$
因此，图1中红色的数据代表的意思就是：不保证这个值会遍历 $0\sim255$，但将 $256$ 组红色部分异或起来，结果仍然为 $0$。

然而在第 4 轮，经过字节代换之后，上面的性质也消失了（红色数据变成了紫色数据）。但由于字节代换、行移位是可逆的；如果猜测轮密钥的单个字节，异或回去、再逆行移位、逆字节代换就可以得到第3轮结果的对应字节；根据前面得到的性质，可以验证该猜测是否正确，如果正确则是一个可能的轮密钥字节。平均情况下，会得到两个可能的密钥字节，最后也会有 $256$ 种情况。枚举一下应该就OK了。

故这个题可以根据这一原理出解：

s_inv=[82, 9, 106, 213, 48, 54, 165, 56, 191, 64, 163, 158, 129, 243, 215, 251, 124,
    227, 57, 130, 155, 47, 255, 135, 52, 142, 67, 68, 196, 222, 233, 203, 84, 123,
    148, 50, 166, 194, 35, 61, 238, 76, 149, 11, 66, 250, 195, 78, 8, 46, 161, 102,
    40, 217, 36, 178, 118, 91, 162, 73, 109, 139, 209, 37, 114, 248, 246, 100, 134,
    104, 152, 22, 212, 164, 92, 204, 93, 101, 182, 146, 108, 112, 72, 80, 253, 237,
    185, 218, 94, 21, 70, 87, 167, 141, 157, 132, 144, 216, 171, 0, 140, 188, 211,
    10, 247, 228, 88, 5, 184, 179, 69, 6, 208, 44, 30, 143, 202, 63, 15, 2, 193,
    175, 189, 3, 1, 19, 138, 107, 58, 145, 17, 65, 79, 103, 220, 234, 151, 242, 207,
    206, 240, 180, 230, 115, 150, 172, 116, 34, 231, 173, 53, 133, 226, 249, 55, 232,
    28, 117, 223, 110, 71, 241, 26, 113, 29, 41, 197, 137, 111, 183, 98, 14, 170, 24,
    190, 27, 252, 86, 62, 75, 198, 210, 121, 32, 154, 219, 192, 254, 120, 205, 90, 244,
    31, 221, 168, 51, 136, 7, 199, 49, 177, 18, 16, 89, 39, 128, 236, 95, 96, 81, 127,
    169, 25, 181, 74, 13, 45, 229, 122, 159, 147, 201, 156, 239, 160, 224, 59, 77, 174,
    42, 245, 176, 200, 235, 187, 60, 131, 83, 153, 97, 23, 43, 4, 126, 186, 119, 214, 38,
    225, 105, 20, 99, 85, 33, 12, 125]
K=[]
for loc in range(16): #枚举位置
    D=[]
    for i in range(256): #爆破可能的key
        res=0
        for j in range(256):#对密文的对应位算异或和
            res^=s_box.index(i^givenC[j][loc])
        if(res==0):
            D.append(i)
    K.append(D)
# 总而言之，在只做四轮的时候存在这样一个可以被证明的公式:
# 每一个byte的256次明文选择加密的第四轮的最后一次addroundkey之前的XOR和为0。例用这个结论可以挨个爆破每一位key。
print(K)
def func(k, ind):
    for i in range(ind)[::-1]:
        tmp = [
            xor_bytes(k[-3], k[-4]),
            xor_bytes(k[-2], k[-3]),
            xor_bytes(k[-1], k[-2]),
        ]
        word = list(tmp[-1])
        word.append(word.pop(0))
        word = [s_box[b] for b in word] 
        word[0] ^= r_con[i]
        tmp = [xor_bytes(k[-4], word)] + tmp
        k = tmp
    return b''.join(k)
def dfs(ind, key):
    if ind == 16:
        key = func([bytes(key[i:i+4]) for i in range(0, 16, 4)], 7)
        skeys = _expand_key(bytes2matrix(key))
        for i in range(2**8):
            pti = givenP[i]
            cti = givenC[i]
            if encrypt(pti, 7, skeys) != bytes(cti):break
        else:
            print(key.hex())
            #print("DASCTF{"+ sha256(key).digest().hex()+"}")
        return
    for i in range(len(K[ind])):
        dfs(ind+1, key + [K[ind][i]])
dfs(0,[])
#output:
#K=[[204, 247], [112, 251], [158, 205], [50, 73, 137], [236], [17, 219, 221, 237], [34, 55], [5, 90], [205], [63, 86], [47, 52], [32, 39, 63], [90, 194, 213], [30, 113, 182], [0, 113, 130], [8, 45, 154]]
#key.hex()=86f3e2d49c86425ba4d772a5f81af7b9

5o02 另一个例题：0xGame2024 AES

这个题目其实还是AES-Square Attack，只是将 $4\times4$ 的矩阵变成了 $3\times 3$ 的矩阵，然后从 $GF(2^{8},x^8+x^4+x^3+x+1)$ 域中的运算变成了 $GF(3^{5},x^5+x^2+1)$ 上的运算。题目目标是拿到正确的Key，没有询问次数限制和交互时间限制。

#Util.py
from GF import GF

SBOX, INV_SBOX = dict(), dict()
for i in range(3 ** 5):
    v = GF(23) + (GF(0) if i == 0 else GF(i).inverse())
    SBOX[GF(i)] = v
    INV_SBOX[v] = GF(i)

class BlockCipher:
    def __init__(self, key: bytes, rnd: int):
        assert len(key) == 9
        sks = [GF(b) for b in key]
        for i in range(rnd * 9):
            sks.append(sks[-1] + SBOX[sks[-9]])
        self.subkeys = [sks[i:i+9] for i in range(0, (rnd + 1) * 9, 9)]
        self.rnd = rnd

    def _add_key(self, l1, l2):
        return [x + y for x, y in zip(l1, l2)]

    def _sub_key(self, l1, l2):
        return [x - y for x, y in zip(l1, l2)]
    
    def _sub(self, l):
        return [SBOX[x] for x in l]

    def _sub_inv(self, l):
        return [INV_SBOX[x] for x in l]
    
    def _shift(self, b):
        return [
            b[0], b[1], b[2],
            b[4], b[5], b[3],
            b[8], b[6], b[7]
        ]
    
    def _shift_inv(self, b):
        return [
            b[0], b[1], b[2],
            b[5], b[3], b[4],
            b[7], b[8], b[6]
        ]
    
    def _mix(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(7) * b[i] + GF(2) * b[3 + i] + b[6 + i]
            y = GF(2) * b[i] + b[3 + i] + GF(7) * b[6 + i]
            z = b[i] + GF(7) * b[3 + i] + GF(2) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def _mix_inv(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(86) * b[i] + GF(222) * b[3 + i] + GF(148) * b[6 + i]
            y = GF(222) * b[i] + GF(148) * b[3 + i] + GF(86) * b[6 + i]
            z = GF(148) * b[i] + GF(86) * b[3 + i] + GF(222) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def encrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]
        
        b = self._add_key(b, self.subkeys[0])
        for i in range(self.rnd):
            b = self._sub(b)
            b = self._shift(b)
            if i < self.rnd - 1:
                b = self._mix(b)
            b = self._add_key(b, self.subkeys[i + 1])
        
        return bytes([x.to_int() for x in b])
    
    def decrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]

        for i in reversed(range(self.rnd)):
            b = self._sub_key(b, self.subkeys[i + 1])
            if i < self.rnd - 1:
                b = self._mix_inv(b)
            b = self._shift_inv(b)
            b = self._sub_inv(b)
        b = self._sub_key(b, self.subkeys[0])
        
        return bytes([x.to_int() for x in b])

一开始交了几次，发现flag老出不出来。结果本地测试后发现，因为这边基数是 $3$，需要区分正负了，最后你记录的可能的轮密钥的值，其实取负后才是真正的轮密钥（基数 $2$ 不区分正负）

from Cipher import *
from os import urandom
from GF import GF
from random import getrandbits
from datetime import *
def invKey(karr,T):
    prevK=karr[:]
    while T:
        T=T-1
        prevK=[GF(i) if type(i)==int else i for i in prevK]
        for _ in range(9):
            prevK= [INV_SBOX[prevK[-1] - prevK[-2]]] + prevK[:-1]
    return prevK
def randomkey(n):
    ktmp=[]
    for i in range(n):
        ktmp.append(getrandbits(8)%243)
    return bytes(ktmp)
key = randomkey(9)
keyarr=[i%243 for i in key]
cipher = BlockCipher(key, 4)

STime=datetime.now()
Msgg=[bytes([i,0,0,0,0,0,0,0,0]) for i in range(243)]
Ciph=[cipher.encrypt(i) for i in Msgg]

K=[]
for loc in range(9):
    D=[]
    for i in range(243):
        res=GF(0)
        for j in range(243):
            res=res+INV_SBOX[GF(i)+GF(Ciph[j][loc])]
        if(res==GF(0)):
            D.append(GF(0)-GF(i)) #这个应该是负的
    K.append(D)


print(cipher.subkeys[-1]) #for debug, blind for solving problems.
print(keyarr)

guessKey=None
def dfs(step,kkk):
    global guessKey
    if(step==9):
        kinit=invKey(kkk[:],4)
        #print(kinit,keyarr)
        kkk=[i.to_int() for i in kinit]
        testkey=bytes(kkk)
        tciph=BlockCipher(testkey,4)
        if(tciph.encrypt(Msgg[0])==Ciph[0]):
            guessKey=testkey
        return
    for i in K[step]:
        dfs(step+1,kkk+[i])
dfs(0,[])
print(key.hex(),guessKey.hex(),key==guessKey)
TTime=datetime.now()
print(f'Time Cost:{TTime-STime}')

可能的运行结果：

[GF(132), GF(129), GF(104), GF(77), GF(103), GF(174), GF(168), GF(120), GF(231)]
[161, 8, 145, 192, 109, 179, 62, 234, 29]
a10891c06db33eea1d a10891c06db33eea1d True
Time Cost:0:00:02.891690