Raindrop差分攻击

#密码学

Raindrop概述

Raindrop是中国密码算法设计竞赛的分组密码候选者之一，由CACR协会赞助。

将128位的明文从右到左编号为0-127，64-127位为左枝，0-63位为右枝。每个分枝可表示为一个4x4维的状态矩阵，按如下规则映射：
|Pi|表示Pi的长度，当i为偶数时 |Pi| = 3，i为奇数时 |Pi| = 5。

轮函数 RF64 通过 S-box, MixRow, BitRot 这三个操作更新状态矩阵。

S-box
S盒由 Keccak’s S-boxes 设计而来, 分别是 3-bit 和 5-bit S盒。

MixRow
按以下图示对矩阵进行操作。

BitRot
对于状态矩阵第i列，计算一个级联值 Coli = P4i || P4i+1 || P4i+2 || P4i+3, 对 Coli 进行循环移位操作：Col0 不变，Col1 左移 6 位，Col2 左移 7 位，Col3 左移 12 位。

针对Raindrop的差分攻击

这里介绍了如何找到了一个有效的差分攻击算子 𝛼→𝛽 的方法。

首先，计算并绘制差分表：

# Raindrop Differential Attack
# Xiaolin Zhang, 2019-11-2 

import seaborn as sns
import matplotlib.pyplot as plt

# s-boxes
s1 = { 0: 0, 1: 5, 2: 3, 3: 2, 4: 6, 5: 1, 6: 4, 7: 7}
s2 = { 
    0:  0,  1:  5,  2: 10,  3: 11,  4: 20,  5: 17,  6: 22,  7: 23,
    8:  9,  9: 12, 10:  3, 11:  2, 12: 13, 13:  8, 14: 15, 15: 14, 
    16: 18, 17: 21, 18: 24, 19: 27, 20:  6, 21:  1, 22:  4, 23:  7,
    24: 26, 25: 29, 26: 16, 27: 19, 28: 30, 29: 25, 30: 28, 31: 31
} 
dt3 = np.zeros((8,8))    # 3 bits s-box differential table 
dt5 = np.zeros((32,32))  # 5 bits s-box differential table

# get differential table of s-box in f6
def getDt():
    global s1, s2
    dt3 = np.zeros((8,8))
    dt5 = np.zeros((32,32))
    for i in range(8):
    for j in range(8): 
            dt3[i^j][s1[i]^s1[j]] += 1 			
    for i in range(32):
        for j in range(32): 
            dt5[i^j][s2[i]^s2[j]] += 1 
    # draw heat map of dt3, dt5 to show them better
    sns.set()               
    f, ax = plt.subplots(figsize = (8, 8))
    sns.heatmap(dt3, annot=True, cmap="OrRd")
    plt.savefig("dt3.png")
    f, ax = plt.subplots(figsize = (8, 8))
    sns.heatmap(dt5, annot=True, cmap="OrRd")
    plt.savefig("dt5.png") 
    return dt3, dt5

写出 MixRow, BitRot 函数，模拟加密过程，为攻击做准备

# the first permutation function in rf64
def mixRow(matrix):
    res = np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
    res[0][0] = matrix[0][1]^matrix[0][3]
    res[0][1] = matrix[0][2]^matrix[0][3]
    res[0][2] = matrix[0][0]
    res[0][3] = matrix[0][0]^matrix[0][1]

    res[1][0] = matrix[1][1]^matrix[1][3]
    res[1][1] = matrix[1][2]^matrix[1][3]
    res[1][2] = matrix[1][0]
    res[1][3] = matrix[1][0]^matrix[1][1]

    res[2][0] = matrix[2][1]^matrix[2][3]
    res[2][1] = matrix[2][2]^matrix[2][3]
    res[2][2] = matrix[2][0]
    res[2][3] = matrix[2][0]^matrix[2][1]

    res[3][0] = matrix[3][1]^matrix[3][3]
    res[3][1] = matrix[3][2]^matrix[3][3]
    res[3][2] = matrix[3][0]
    res[3][3] = matrix[3][0]^matrix[3][1]
    return res

# the second permutation function in rf64, cyclically move bits
def bitRot(matrix):
    bit = [0, 6, 7, 12]     
    res = np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
    for j in range(4):
        col = []
        for i in range(4):
            w = 3 if i%2==0 else 5   
            arr = decimal2array(matrix[i][j], w)
            col.extend(arr)                   # concatenate the column
        k = bit[j]
        col2 = col[k:]+col[:k]                # cyclically move bits
        res[0][j] = array2decimal(col2[0:3])  # split the binary string into 4 parts
        res[1][j] = array2decimal(col2[3:8])
        res[2][j] = array2decimal(col2[8:11])
        res[3][j] = array2decimal(col2[11:16])
    return res

# the 64-bit round function (containing s-box, mixRow, bitRot)
def rf64(matrix):
    global s1, s2
    s = np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
    for i in range(4):
        for j in range(4):
        k = matrix[i][j]
            s[i][j] = s1[k] if i%2==0 else s2[k]
    return bitRot(mixRow(s))

3. findPath()函数可自动找到最佳攻击路径，同时计算概率

prob = 0   # attack probability is 1/(2^prob), prob < 128

# automatically find the attacking path, calculate probability
def findPath(left, right, round):	
    global dt3, dt5, prob
    print("+ + + + + + attackOneRound + + + + + +")
    print(left)
    print(right)
    temp = left
    # only left matric need to cross the s-box
    for i in range(4):     
        for j in range(4):
            if temp[i][j]!=0:
                if i%2==0:
                    # target is the output of s-box
                    target = findTarget(dt3, temp[i][j])
                    # accumulate the probability			
                    prob += math.log(8/dt3[temp[i][j]][target], 2) 
                else:
                    target = findTarget(dt5, temp[i][j])	
                     prob += math.log(32/dt5[temp[i][j]][target], 2) 
                temp[i][j] = target     # update status matrix

    temp = bitRot(mixRow(temp))        
    xor = np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
    for i in range(4):
        for j in range(4):
            xor[i][j] = temp[i][j]^right[i][j]
    print("round", round+1)
    print("probability", prob)
    if prob > 128:               # attack over
        return	
    findPath(xor, left, round+1) # find the next round path

# find the target output with highest probability in differential table
# in raindrop case, the first non-zero value in a row is suitable
def findTarget(table, row):
    for col in range(len(table)):
        if table[row][col]!=0:
            return col

# convert decimal to binary array, k is the target length
def decimal2array(val, k):
    res = []
    while val!=0: 
        res.append(val%2) 
        val = int(val/2) 	
    res = res[::-1]     # reverse list
    res2 = []
    if len(res)<k:      # padding with zero
        for i in range(k-len(res)): 
            res2.append(0)
    res2.extend(res)
    return res2

# convert binary array to decimal
def array2decimal(arr):
    res = 0
    arr2 = arr[::-1]
    for i in range(len(arr)):
        if (arr2[i]==1):
            res += pow(2,i)
    return res


if __name__=='__main__':
    dt3, dt5 = getDt()  
    # randomly choose a start status
    # the more zero, the greater the probability 
    left = np.array([     
        [ 0, 0, 0, 0],
        [ 0, 0, 0, 0],
        [ 0, 0, 0, 1],
        [ 0, 0, 0, 0]
    ])
    right = np.array([
        [ 0, 0, 0, 0],
        [ 0, 0, 0, 0],
        [ 0, 0, 0, 0],
        [ 0, 0, 0, 0]
    ])
	findPath(left, right, 0)