類型：Crypto
題目地址：https://github.com/google/google-ctf/tree/master/2018/quals/crypto-dm-col
參考連接：https://github.com/nguyenduyhieukma/CTF-Writeups/tree/master/Google%20CTF%20Quals/2018/Crypto-DM-COLLISION
考察知識點：DES
題目描述：
Can you find a collision in this compression function?
通過代碼閱讀扰藕，可以獲得一些信息：
- 題目使用了一種近似DES加密的算法，調(diào)換了8個S-box的順序芭挽，其他都沒變
- 題目需要我們求：
- 求兩組不同的輸入(key,inputblock) 使input
block^ outputblock相同，即找到一個沖突 - 求一組(key,inputblock)使 inputblock==outputblock悲靴，即一個不動點
- 求兩組不同的輸入(key,inputblock) 使input
為了求解這兩個問題屁擅，我們需要先對DES加密做一些介紹妇智。
- DES(Data Encryption Standard)是一種塊加密算法，輸入為64位長的明文和64位長的密鑰为狸，輸出長為64位的密文。
- 首先會將 輸入的64位明文進行置換并切成兩個長為32位的塊 a[0] a[1]遗契。
- 然后遞推計算 a[i+2] = a[i] XOR f(a[i+1], k[i]) for i = 0,1,...,15 f位一個加密函數(shù)
- f每次接受一個32位長的待加密塊和48位長的subkey辐棒，來生成一個32位長的新塊
- f內(nèi)部會使用s-box 來進行混淆
- 最后會對(a[17],a[16])進行逆置換來得到最終的輸出結(jié)果
- 盡管DES會接受一個64位長的密鑰做輸入，但其實只有其中的56位會被真正用于加密過程牍蜂，另外8位是用于奇偶校驗的漾根，并不影響加密的結(jié)果。64位長的密鑰將用于生成16個48位長的subkey參與f運算鲫竞。
有了以上知識辐怕，對于要求一，找到一個沖突从绘，我們可以利用7寄疏，密鑰中有一個byte不會對outputblock產(chǎn)生影響是牢，很容易構(gòu)造一對滿足要求的(key, inputblock)。
對于要求二陕截，找到一個不動點驳棱，還需要介紹另外一個知識點。
- 對于DES來說农曲，有一類很特殊的key社搅，會使得Key scheduler生成16個相同的subkey
- 具有這種性質(zhì)的key被稱為 weak key
- 對于DES，所有bit位都為0 的key和 所有bit位都為1的key都是weak key
那么使用weak key會有什么危害呢乳规？
對于DES形葬，當所有的subkey相同時，如果我們要使(a[0], a[1]) == (a[17], a[16])驯妄，可以推出一個充要條件是 a[8] == a[9] 荷并。推導過程如圖。
對于這道題青扔，改變s-box的順序只會影響f函數(shù)內(nèi)部源织，這個結(jié)論依舊成立。
因此我們可以讓a[8] == a[9] 位任意值微猖，然后復用代碼反推 a[0]和a[1]
具體過程：
檢查是否所有subkey都相同
WEAK_KEY = b'\xff' * 8 # the all ones weak key
L = list(KeyScheduler(Str2Bits(WEAK_KEY)))
S = set(map(tuple, L)) # this will contain only unique element(s).
len(S) == 1
任取一些值給 a[8] a[9]
a = [None] * 18
a[8] = a[9] = Str2Bits(b'c001') # I just want to be c001
倒推所有的a[i]
subkey = S.pop() # get the unique subkey
def f(block): return CipherFunction(subkey, block)
for i in range(10,18):
a[i] = Xor(a[i-2], f(a[i-1]))
for i in range(7,-1,-1):
a[i] = Xor(a[i+2], f(a[i+1]))
(a[0], a[1]) == (a[17], a[16])
根據(jù)a[i] 構(gòu)造最終的inputblock
key3 = WEAK_KEY
def InvIP(block): return [block[IP_INV[i] - 1] for i in range(64)]
block3 = Bits2Str(InvIP(a[0] + a[1]))
DESEncrypt(block3, key3) == block3
即構(gòu)造出了符合要求二的一組(key,inputblock)
