AES-like密碼算法該如何逆向？
對AES-like算法的完整逆向框架討論
背景介紹
盡管學術界認為密碼算法應該是公開的，密碼算法的安全性不應該通過隱瞞密碼算法保證，但是在工業領域依然有很多非公開密碼算法的使用，例如朝鮮算法、我國的SM1密碼算法。而對非公開密碼算法的評估是無法知道具體算法的，這導致安全評估工作很難進行。
由此引入一個問題，即如果要評價非公開密碼算法，就要先知道非公開密碼算法是什么，因此需要進行逆向工程，判斷密碼算法的類型。2021年，Andrea Caforio等人在CARDIS會議上提出了一種針對密碼算法結構框架AES-like的逆向工程。[1]
AES-like算法
上文提到，在工業領域以及軍工領域依然有很多非公開密碼算法的使用，這是因為客觀上來說隱藏密碼算法的實現的確能夠增加破解密碼算法的難度，因此非公開密碼算法的存在無法避免。但另一方面由于非公開密碼算法因為其不能夠被公開，其安全性缺少有效的證明。所以出現了一種折衷方案，即利用現有的已經被證明安全的密碼算法的結構框架，對框架的每一個模塊的具體實現進行替換。由于算法框架不變，所以密碼算法的整體安全性能夠得到相對保證，AES-like算法應運而生。其框架如圖1所示。
圖1 AES-like算法框架
AK：輪密鑰加。
KS：生成輪密鑰：本文中假定生成輪密鑰的過程和標準AES算法生成輪密鑰的過程一致，所以破解算法的各個部分時不包括該部分。
SB：S盒*替換（此處的S盒與標準AES算法S盒不同）。
PB：行移位*（實質是一種雙射，將每一個位置的字節映射到另一個不同的位置，此處的恢復的就是映射方式）。
MC：列混合*（用M矩陣左乘，此處的M矩陣也需要恢復）。
密鑰恢復
密鑰恢復的過程相對簡單，因為不知道S盒的實現，所以使用進入S盒之前的值作為中間值。如圖2所示。
圖2 根據中間值恢復漢明重量的算法
恢復部分行移位*
恢復行移位的過程基于的主要思想為：明文一個字節的不同會在加密過程中進行擴散。所以直觀思路是使兩個明文的某一個字節不同，觀察其不同在經過PB后擴散到了哪一個字節。對16個字節逐一判斷，確定其被映射到的位置。但在實際的恢復過程中沒有這么簡單，由于PB和MC有可能緊密相連，無法單獨分出波形段中的PB區域。所以真正的恢復過程需要將PB過程和MC過程結合到一起分析。
作者通過把PB和MC視作整體來看。黑色格子表示兩組明文中對應位置字節有不同的部分，當第一個字節不同時，這個不同在經過PB層后會映射到另一個位置，而這個位置的不同在經過MC層后會擴散到全列，如圖3所示。
圖3 明文字節的不同在加密中的擴散過程
不同的字節被PB映射到了某一列，則經過MC后該列都和該字節有關，因此會出現4個尖峰。如圖4所示，作者在32位STM32F303平臺上進行了實驗。由于每一列是分別進行計算的，所以在計算過程中，輸入值1個字節的不同擴散到某一列的4個字節中，進而導致出現4個尖峰。
圖4 DPA驗證一個字節不同經過MC后會出現四個尖峰
進一步，作者研究出，每一行的四個字節，都被映射到了同一列，進而映射方式的可能性被縮減到4!種。
恢復行移位*和列混合*
目前只恢復了部分的行移位，完整的行移位*將和S-box*與列混合*一起恢復。
d0，d1，d2，d3為對于兩個不同的明文，經過第一輪PB層后第一列的四個值之間的差。u0，u1，u2，u3指的是字節替換之前的第一行的四個值的索引，我們已知這四個值被映射到了同一列。pui是索引為ui位置對應的明文。進行如下操作：
第一步，令pu2，pu3的值相等。
第二步，找到使得經過s盒替換后漢明重量為0的明文字節。
第三步，找到p`u0使得經過s盒替換后漢明重量為8的明文。
第四步， 找到p`u1使得經過與M矩陣相乘后的結果反而沒有變化。
第五步，這就意味著H(b`u1,SB(1))經過S盒替換后的值的漢明重量就是H(d1)也就是H(x1)。我們可以通過這種方式構建代數關系式。
這樣我們就能夠得到如下的關系式：
通過以上方式，我們可以構建出類似的10組代數關系，如圖5所示。
圖5 構建出的代數關系組
剛才提到，PB層的映射可能性已經被縮減到4!種可能。
作者證明，對于24種可能中的20種，由以上得到的代數關系式無解。對于剩下4種可能中的3種有解，但是得到的對應的M也是經過變換后的，并能夠得到相同的計算結果，所以某種程度上說這4種是等價的，所以M和PB層的變換需要同時恢復。
恢復S盒*
因為明文可以更改 ，所以pi，ki，di我們都是已知的，T()表示為替換過程，作者希望通過找到一種特殊情況來逐步恢復S盒，這種特殊情況利用到了M的逆矩陣，我們通過以上的論述已經恢復出了M，自然也就知道了M的逆，通過自主更改明文p0，p1，p2，p3構造出一種T(pi+ki)=0，T(pi+ki+di)對于i=0，1，2，3時分別為e，f，g，h的λ倍。當成功構造出以上類型時，第一列的四個字節經過MC層計算之后會將字節間的不同反擴散回去，反而只有一個字節不同，如圖6所示。這樣我們就可以得到每個字節計算過程中經過S盒替換后的漢明重量分別為w0，w1，w2，w3。
圖6 四個不同的字節在特殊情況下
反擴散導致只有一個字節不同的示意圖
現在我們知道了e，f，g，h，w0，w1，w2，w3，那么如果我們知道了λ，知道了經過s盒后和經過s盒前的值分別是什么，而通過e，f，g，h，w0，w1，w2，w3，是可以以預計算查找表的方式恢復λ的，所以通過以上方式，我們就可以恢復S盒。
總結
本文實現的主要內容是通過側信道攻擊對一種AES-128-like算法進行實際逆向，并對AES-128-like算法的各個部分進行恢復：密鑰、行移位*、列混合*、S盒*。
本文的貢獻點在于第一個對AES-128-like算法的實際逆向，而非仿真；恢復了完整的算法，密鑰、行移位*、列混合*、S盒*；在8位及32位平臺上都成功恢復，證明方法的普適性。
