SM4 算法快速軟件實現*

張笑從, 郭 華, 張習勇, 王 闖, 劉建偉

1. 北京航空航天大學 軟件開發環境國家重點實驗室, 北京100191

2. 密碼科學技術國家重點實驗室, 北京100878

3. 北京航空航天大學 空天網絡安全工業與信息化部重點實驗室, 北京100191

4. 北京衛星信息工程研究所, 北京100086

1 引言

SM4 分組密碼算法[1]是我國自主設計的對稱分組密碼, 為眾多信息系統提供安全、完整的數據加密方案. SM4 算法的高效軟件實現為我國應用在安全產品(如IPSec、VPN、SSL、TLS 等)上的密碼算法由國際標準替換為國家標準提供了強有力的支撐, 為SM4 算法廣泛用于政府辦公、公安、銀行、稅務、電力等自主可控要求高的信息系統提供了可靠的保障. 目前關于SM4 算法的軟件優化實現方面的相關工作不多, 多使用查表的方法[2], 但由于代替表規模相對較大, CPU 在做查表操作時, 表中數據在內存和cache之間頻繁對換導致查表延時較大, 且不利于高效并行加/解密多組消息. 此外, 查表法無法抵抗緩存-計時側信道攻擊, 因此在一定程度上制約了SM4 的軟件實現性能和安全性.

1996 年Intel 推出單指令多數據的SSE (Streaming SIMD Extensions) 指令集后, Biham[3]于1997年提出一種新的對稱分組密碼快速軟件實現方法, 核心思想是將處理器視為以1 比特為單位的單指令多數據處理器, 隨后被Matthew Kwan 稱為比特切片(bit slicing)[4].比特切片方法在64 位平臺上實現了64 組DES 消息的并行加解密, 將邏輯門個數從理論上需要的132 個每比特輸出優化到100 個每比特輸出.之后研究者們對門函數個數進一步進行了優化, 使得標準邏輯門(與、或、非、異或) 和非標準邏輯門均達到了平均50+ 個每比特輸出.2011 年Roman Rusakov[5]又將門函數的個數降至平均44 個邏輯門每比特輸出.比特切片方法可大大提高實現效率, 也可用于搜索密鑰, 對RISC 和CISC 的指令集平臺均適用, 且具有更好的安全性.

為了提高軟件實現速度, 國內外許多學者嘗試將采用SIMD (Single Instruction Multiple Dada, 單指令多數據) 技術用于密碼算法的軟件實現.A. Adomnicai 和T. Peyrin[6]給出改進的比特切片方法“Fixslicing”,在ARM 和RISC-V 平臺實現了AES.2012 年Intel 推出高級向量指令集(Advanced Vector Extensions,AVX) 后, 眾多學者開始研究如何利用AVX 指令集加速對稱分組密碼算法的實現速度, 尤其是輕量級密碼算法的實現速度.Seiichi Matsuda 和Shiho Moriai[7]利用AVX 指令集加速切片實現, 給出了輕量級密碼算法面向云端的實現, 將SSE 指令與比特切片方法結合并應用到PRESENT/Piccolo, 使兩者的實現吞吐量分別達到4.3 cycle/byte 和4.57 cycle/byte.2013 年,Neves 和Aumasson[8]將AVX2指令應用到SHA-3 候選算法BLAKE 上并提高了其實現性能.最近,郎歡等[9]利用X86 架構下的SIMD指令給出了高效的SM4 實現, 他們采用C 語言調用AVX2 指令接口方式實現, 在并行查表的基礎上, 給出了兩種不同的方法.2014 年Kostas Papapagiannopoulos 等人[10]將比特切片方法修改為nibble 切片方法, 并減少了訪問內存, 在AVR 處理器上給出了高效實現.

此外, 研究者們將比特切片方法和其它方法結合, 對SM4 算法進行軟件實現, 也取得了較好的效果.SM4 算法公布不久, Fen Liu 等[11]破解了SM4 算法S 盒的結構, 公布了S 盒的代數表達式及具體參數值.之后, Hao Liang 等[12]基于已破解的SM4 中S 盒結構, 提出了基于復合域的SM4 實現方法, 將S盒的有限域求逆運算變換到復合域中實現, 并在FPGA 上進行驗證.Jingbin Zhang 等[13]提出了SM4在復合域中的軟件實現, 使用X86 架構普通指令實現, 速率達到20 Mbps.最近, A. Eldosouky 和W.Saad[14]針對物聯網應用的效率、安全需求改進了輕量級密碼算法LED 的比特切片方法, 并在嵌入式處理器ARM Cortex-A53 進行了實現驗證.O. Hajihassani 等[15]利用比特切片方法進一步提高了高級加密算法AES 的加解密吞吐率.總的來說, 在國密標準SM4 算法的軟件優化實現方法取得了一些進展, 但和其他對稱加密算法如AES 相比, SM4 的軟件優化實現仍需進一步研究.

本文利用比特切片方法, 結合支持單指令多數據(SIMD) 的AVX2 指令集, 提出了一種SM4 算法的快速軟件優化實現方法, 使用256 位的YMM 寄存器實現了SM4 算法的256 分組數據并行加解密.該方法首先對待加密的明文消息通過SIMD 版本的數據編排算法進行預處理; 之后提出了一種改進的化簡邏輯表達式的新方法, 將實現邏輯表達式所需的邏輯門電路數量由3000 降至497; 最后使用反編排算法得到密文.在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 處理器上, 結合x86 平臺拓展指令集AVX2和上述方法對SM4 算法進行軟件實現, 實現速度達到了2580 Mbps.相比于傳統的查表實現(Intel Core i7-5500U(Broadwell-U)@2.40 GHz)、未優化的比特切片實現(Intel Core i7-5500U(Broadwell-U)@2.40 GHz)、SM4 軟件優化實現公開文獻的最佳結果[9](Intel Core i7-5500U (Broadwell-U) @2.40 GHz), 新方法的實現效率分別提升了1.8 倍、2.6 倍和43%.綜上所述, 本文主要貢獻如下:

(1) 提出了一種通用的對稱分組密碼算法的軟件優化實現方法, 該方法通用于所有對稱加密算法的快速軟件實現.

(2) 提出的基于比特切片的軟件優化實現方法無需內存或高速緩存查表, 因此可抵抗緩存-計時側信道攻擊[16], 從而安全性得到了提升.

(3) 提出的優化方法具有較強的通用性.該方法可用于所有對稱加密算法的軟件優化實現, 并適用于不同的軟件架構: 在CISC 架構平臺如X86 適合借助SSE、AVX2、AVX512 等拓展指令集實現, 在RISC 架構(ARM,RISC-V) 的平臺可使用普通指令集實現.

(4) 新的選擇函數和搜索算法具有通用性, 可用于一般邏輯函數的化簡.

本文其余內容組織如下: 第2 節介紹SM4 算法及AVX2 指令; 第3 節介紹新的選擇函數及基于選擇函數的改進的搜索算法; 第4 節介紹SM4 的基于比特切片和AVX 指令的軟件優化實現方法; 第5 節介紹實驗結果; 第6 節總結全文.

2 預備知識

2.1 SM4 簡介

對于每個S 盒的8 位輸入, 前4 位作為行, 后4 位作為列, 輸出即為查找表中對應行列所對應的值.S 盒如圖2 所示.

圖1 SM4 輪函數Figure 1 Round function in SM4 algorithm

圖2 SM4 代替表Figure 2 Substitution table in SM4 algorithm

2.2 SIMD 技術及AVX2 指令集

SIMD (single instruction multiple data) 技術可實現同一操作并行處理多組數據.目前支持SIMD技術的處理器廠商主要有Intel、AMD、ARM 等.目前大多數PC 及服務器采用的是Intel 處理器, 而Intel 處理器中的SSE/AVX 指令集采用的正是SIMD 技術.AVX (Advanced Vector Extensions) 指令集[18]是256-bit 寬向量指令集, 指令操作對象稱為YMM 的256-bit SIMD 寄存器.該寄存器內容分為2 個128-bit lane.AVX 指令操作對象為lanes, 該指令不支持跨越lanes 的操作.

AVX2 指令集是AVX 指令集的擴展和改進, 也稱為Haswell New Instructions, 支持跨越lanes 的操作.AVX2 支持8 道32-bit 整數異或(vpxor)、移位(vpslld)、置換(vpermd)、查表(vpgatherdd) 等.2013 年Inter 在22 nm Haswell 微架構處理器上正式推出AVX2 指令集.表1 給出了部分AVX2 指令,這些指令可用于對稱分組密碼的切片實現.

3 構造新的選擇函數及搜索算法

“選擇函數”[19]是Mattew 為比特切片方法中簡化實現S 盒邏輯門電路數量而提出的一種邏輯函數表達形式.選擇函數的思想為二分法, 每次分得兩個子函數, 直至最終分解到的子函數可以直接實現.經研究發現, 對于上述特定問題選擇函數形式比其他常用的標準形式優越許多.如上所述, 對于SM4 算法的S 盒, 使用最簡與或形式、最簡或與形式、最簡與或非形式等需要邏輯門數約為3000, 而使用已知的3個選擇函數形式時, 可將邏輯門數限制在:NSM4= 12+8×(21+22+···+28?2) = 1032.使用本文提出的新的選擇函數及改進的搜索算法, 可進一步將邏輯門數減至497 門.一般來說, 使用的選擇函數越多,搜索越充分, 越能減少邏輯門數量.

表1 相關AVX2 指令總結Table 1 Summary of relevant AVX2 instructions

本節首先基于已有的選擇函數構造新的選擇函數, 之后基于新的選擇函數給出改進的搜索算法, 最后介紹如何使用新的選擇函數及改進的搜索算法化簡S 盒的邏輯表達式.

3.1 選擇函數簡介

為化簡比特切片方法中實現S 盒所用的邏輯門電路數量, Mattew 提出了化簡邏輯門電路的算法及“選擇函數” 的概念.使用選擇函數, DES 中實現S 盒的邏輯門電路數量從平均70 門每比特輸出被約簡到平均45 門每比特輸出.

設Fo為8 比特邏輯函數, 即Fo(abcdefgh), 從輸入abcdefgh中任選一個比特, 記為sel, 給出選擇函數基本形式:

Mattew 指出, 還可使用nand、nor 等非標準邏輯門構造更多選擇函數.生成選擇函數形式的邏輯表達式過程如下: 從需要實現的邏輯函數出發, 進行選擇, 逆向生成整個邏輯電路, 直至最終得到許多2 比特邏輯函數.理論上共有16 種不同的2 比特邏輯函數, 其中有4 個是平凡的(常量0、1 和直接連接兩個輸入), 另外12 個非平凡的邏輯函數可由兩個輸入連接12 個邏輯門實現, 如圖3 所示.每次選擇時都有上述3 個選擇函數形式可以使用, 需要逐個嘗試以取得較好結果.對于DES 的6 比特輸入4 比特輸出S盒來說, 先后處理4 個輸出, 每個輸出最多需要4 次“選擇”.處理過程中, 對1 個邏輯函數做“選擇” 前,可以嘗試直接連接到之前已實現的中間結果, 這是化簡的主要實現方式.

圖3 16 種2 輸入邏輯門的一種實現Figure 3 Example of 16 logic combinations of two gates

通過對選擇函數的分析, 我們發現換入不同邏輯門, 得到的新選擇函數與原形式可能有不同的子函數, 從而帶來不同的結果.

針對上述問題, 本文對選擇函數及其搜索算法進行了研究, 給出了9 種實質不同的“選擇函數” 表達式, 并改進了基于“選擇函數” 的邏輯門電路生成算法(稱為搜索算法), 以利用9 種“邏輯表達式” 得到更簡化的S 盒邏輯表達式.

3.2 構造新的選擇函數及搜索算法

本小節介紹對“選擇函數” 的擴展和搜索算法的改進.

3.2.1 構造新的選擇函數

令m表示邏輯函數輸入的比特數.由于“選擇函數” 表達式每次將函數Fo分解為F1、F2、F3, 每次減少1 比特輸入, 從而保證在有限次(m ?2 次) 選擇后得到可直接實現的表達式.對于輸入為m比特的Fo, 可用2m比特表示; 限定F1、F2、F3的輸入為m ?1 比特時, 它們均可用2m?1比特表示, 且F1,F2,F3唯一.

換入非標準邏輯門, 可以找到的所有表達形式都包含于上述9 種形式之中.

這種遞歸生成“選擇函數” 的算法處理Fo與notFo可能得到差異較大的結果, 即Fo與notFo對于“選擇函數” 生成表達式的算法來說是兩個不同的表達式, 因此應分別嘗試.

3.2.2 改進搜索算法

下面給出改進的搜索算法(算法1). 對40 320×40 320 種輸入輸出排序, 分別調用此生成算法, 搜索其中邏輯門數最少的邏輯電路.算法輸入邏輯電路、sel 比特排序和輸出排序, 輸出邏輯電路和邏輯電路的總門數.算法包括5 個步驟.

注: 改進之處在于4 中提供更多選擇函數形式, 5 是新加入的步驟.

4 SM4 算法的優化實現

本節首先介紹SM4 算法優化實現方法的總體結構, 之后介紹具體的優化實現.

4.1 總體實現

SM4 算法的優化實現包括三部分: 數據編排、迭代計算、數據反編排.對于數據(反) 編排部分, 主要采用SIMD 技術實現轉置并優化; 對于迭代部分, 主要使用選擇函數優化法優化S 盒的邏輯表達式.具體過程如圖4 所示.

圖4 總體實現結構Figure 4 Overall structure of implementation

4.1.1 數據編排

4.1.5 數據反編排

從切片后的 128 組 256 比特數據恢復到 256×128 比特數據, 需要構造比特矩陣轉置變換inv_TRANS(), 輸入為128×256 比特, 輸出為256×128 比特.若將輸入第i比特表示為二維數組M[128][256]的M[i/256][imod256]項, 則轉置為二位數組M[256][128]的M[imod256][i/256]項.

4.2 AVX2 指令集的的使用

4.2.1 實現數據(反) 編排

數據編排中, 對256×128 比特數據, 分為兩個比特方陣, 對方陣進行比特粒度的轉置[20].使用vpor、vpslld、vpxor 等AVX2 指令優化實現轉置算法.

數據反編排中的128×256 比特數據也可分成兩個比特方陣類似處理.

4.2.2 實現密鑰編排

若并行加解密的分組使用不同密鑰, 編排方法同數據編排, 不需要反編排; 若并行加解密的分組使用相同密鑰, 編排不需要比特粒度轉置, 可以將密鑰每一比特復制為256 比特, AVX2 指令或普通指令均可平凡地實現.

4.2.3 實現S 盒

使用AVX2 指令集中提供的邏輯指令實現, 具體為vpor, vpand, vpxor, vpnand.指令為三操作數指令(其中一個為目的操作數), 不修改源操作數, 必須選擇16 個YMM 寄存器作為操作數.需要在內存中暫存數據, 可使用指令vmovdqa、vmovdqu 進行數據加載、存儲.

4.3 化簡S 盒邏輯表達式

下面介紹如何使用新的“選擇函數” 及改進的搜索算法化簡S 盒邏輯表達式.利用上節給出的9 種選擇函數表達式, 可得到9 種改進的表達式.下面以式(1) 為例:

在上述四種處理方式中, 前兩種利用已存在的邏輯門, 無需額外代價; 后兩者基于選擇函數的遞歸處理在沒有直接可用的邏輯門的情況下使用.

圖5 連接到已存在的邏輯門Figure 5 Appending to generated logic gates

圖6 連接到兩個邏輯門的組合Figure 6 Appending to combination of two logical gates

圖7 使用選擇函數公式遞歸生成邏輯電路Figure 7 Generating logical circuit using selection function recursively

圖8 引入可變的Fseed 生成邏輯電路Figure 8 Generating logical circuit via almost arbitrary Fseed

4.4 S 盒實現結果比較

表2 列出了使用選擇函數和未使用選擇函數時S 盒實現中需要的邏輯門電路數量及實現時間.由于AVX2 指令集中數據加載存儲指令相對于邏輯操作指令迅速許多, 因此S 盒的實現時間大致由邏輯門數決定.未使用選擇函數實現S 盒所需邏輯門數約為3000 (最簡與或式), 使用9 個選擇函數和改進的搜索算法所需的邏輯門數為497.對31 250 Mb 數據加密測試結果顯示, 未使用選擇函數的實現時間為30 秒,使用9 個選擇函數和改進的搜索算法后, 實現時間減少至10.3 秒.

表2 S 盒實現所需要的邏輯門數及實現時間比較Table 2 Logical gate count and time for implementing S box

5 實驗結果

本節比較已有公開文獻中關于SM4 軟件實現的效率, 包括傳統查表法、SIMD 技術查表法及比特切片方法.利用C 語言和匯編語言對SM4 算法進行優化實現, 在相同的硬件環境中, 比較SM4 算法不同實現方法的效率.由于PC 端內存資源相對豐富, 故對于4 GB、8 GB 內存不做區分; 處理器微架構和主頻對性能有較大影響.具體測試環境如表3 所示.

表4 總結在不同處理器上SM4 算法采用查表法、選擇函數優化法的軟件實現性能.評估分組密碼算法軟件實現性能的指標是每秒鐘加/解密的比特數, 即bps.對31 250 Mbit 數據進行加密測試.表4 的8-32 表示采用8-bit 輸入32-bit 輸出表.

表4 軟件實現方法在不同處理器上效率對比Table 4 Efficiency of software implementations on different processors

由表4 可以看出, 使用AVX2 指令的并行查表方法比普通查表方法在效率上有明顯提升, 由908 Mbps 到1795 Mbps 提升接近1 倍.未優化的比特切片+AVX2 指令方法效率不佳, 而本文的比特切片+AVX 指令+ 選擇函數優化方法在Intel Core i5-6200U(Skylake)@2.40 GHz 和Intel Core i7-7700HQ(Kabylake)@2.80 GHz 分別達到2387 Mbps 和2580 Mbps, 相對于近似的主頻(2.40 GHz)、微架構(Intel Core i7-5500U(Broadwell-U)) 的AVX2 指令并行查表方法有明顯優勢.

對于算法所需的內存開銷, 普通查表和并行查表需要4 KB 內存存放代換表, 對于資源受限的終端并不合適; 而本文的比特切片實現無需任何額外的內存開銷來存儲代換表, 因此所需內存開銷為0.此外,查表法在內存中存儲代換表并需要在加解密時訪問對應的內存, 除了需要額外的內存開銷, 還不能抵抗緩存-計時側信道攻擊.本文的軟件優化實現方法不需查表, 因此能夠抵抗該類側信道攻擊.

下面進一步給出對31 250 Mb 數據加密測試的詳細結果.

表5 軟件實現方法效率測試Table 5 Test on efficiency of software implementations

由表5 可知, 在Intel Core i5-6200U(Skylake)@2.40 GHz 下, 本文的基于選擇函數優化法的實現時間為13.09 秒, 加密效率提升2.04 倍.在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 下, 該方法的實現時間為12.11 秒, 加密效率提升2.18 倍.此外, 由表5 可以看出, S 盒計算占全部計算約80%, 進一步提升效率的關鍵仍在于優化S 盒的實現.

6 總結

本文基于比特切片方法和SIMD 技術, 提出了一種新的SM4 算法軟件優化實現方法, 并利用X86 平臺的AVX2 指令集給出了高效的實現.新方法首先利用AVX2 指令優化了數據編排算法, 之后基于選擇函數提出了更靈活的化簡S 盒邏輯表達式的算法.在基于選擇函數的優化方法中, 構造了新的選擇函數,并基于新的選擇函數改進了搜索算法, 從而將S 盒所使用的門電路數量從3000 門降至497 門; 在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 環境下, 同目前公開文獻中SM4 軟件實現的最快速度1.7 G 相比, 基于選擇函數的優化方法加解密速度提升至2.5 G, 提高了43%.同基于查表的軟件實現方法相比, 本作品的軟件實現方法可以抵抗cache 攻擊, 從而提高了算法實現的安全性.本文提出的新的選擇函數和搜索算法具有通用性, 可用于其它一般邏輯函數的化簡.此外, 優化方法具有可擴展性, 不僅可以從SM4 算法擴展至目前所有的對稱加密算法的軟件優化實現, 而且可以從X86 平臺的拓展指令集AVX2 實現擴展至利用RISC 指令集在資源受限、安全性要求高的ARM 等嵌入式平臺上實現.