一種可抵抗功耗分析的改進型PRESENT加密算法設(shè)計?

劉 鵬

1 引言

PRESENT算法是2007年由A.Bogdanov，L.R.Knuden和G.Lender等學(xué)者提出來的一個超級輕量級算法，它的設(shè)計結(jié)合了DES與AES的部分特點，采用4進4出的S盒，進行異或運算與移位運算，在硬件實現(xiàn)時具有較好的適應(yīng)性［1～3］，不會對硬件設(shè)備的體積造成影響而且比軟件實現(xiàn)的速度更快，更加適用于運算資源受限的系統(tǒng)。

1.1 PRESENT加解密過程

該算法為分組密碼算法，明文每64比特分為一組，用于加、解密的主密鑰長度可以有80比特或128比特兩種選擇。如圖1所示，經(jīng)過31輪的迭代變換，輸入64比特的明文塊得到64比特的密文塊。在每一輪中，分別經(jīng)過輪密鑰加、S盒變換、P置換這三個操作。

每輪子密鑰的長度為64比特，第i輪加密的子密鑰為Ki=Ki63Ki62……Ki0，明文塊的存放形式為M=m63m62……m0，每一步數(shù)據(jù)轉(zhuǎn)換之后的狀態(tài)為b，其中密鑰加操作為

中間狀態(tài)的每一位依次與64比特的密鑰進行異或運算，得到新的中間狀態(tài)。S盒是非線性結(jié)構(gòu)，算法的安全性對其依賴性很大，其構(gòu)造如表1所示。

表1 PRESENT算法S盒結(jié)構(gòu)

與明文分組相適應(yīng)，它是一個4進4出的結(jié)構(gòu)，將每一輪運算結(jié)束后的64比特數(shù)據(jù)結(jié)果按順序分成16個4比特的數(shù)據(jù)塊，w15，w14，…，w0。

每一個數(shù)據(jù)塊對應(yīng)一個16進制的數(shù)字，按照S盒將數(shù)據(jù)進行非線性的轉(zhuǎn)換，同樣輸出一個16進制的數(shù)字，同時得到一個與其對應(yīng)的4比特數(shù)據(jù)塊，16個數(shù)據(jù)塊依次進行轉(zhuǎn)換，最后得到64位的數(shù)據(jù)。

P置換是將中間狀態(tài)的64位數(shù)據(jù)中的每一位按照P置換表置換到新的位置，其詳細設(shè)計如表3所示。

每一步置換也可以由如下公式表達［4］：

其中bj代表中間64比特中間狀態(tài)的第j位數(shù)據(jù)，(0≤j≤15)。

表3 PRESENT算法P置換規(guī)則表

1.2 PRESENT密鑰擴展方案

以長為80比特的主密鑰為例介紹PRESENT的密鑰擴展方案。在加密芯片中初始主密鑰以K=k79k78…k0的形式存在，在進行第i輪的密鑰加時提取位數(shù)最高的64比特作為該輪的輪子密鑰，Ki=k79k78……k17k16。每次提取出一個輪子密鑰后進行下一輪子密鑰的擴展生成。首先，將寄存器中的80比特密鑰數(shù)據(jù)循環(huán)左移61比特，然后將最左邊的4比特按照S盒的變換方式進行轉(zhuǎn)換，最后將k19k18k17k16k15這5比特數(shù)據(jù)與輪計數(shù)器x進行異或操作，取代原來的5位數(shù)據(jù)，其公式表達如下［1］：

當(dāng)密鑰長度為128比特時，其擴展方法與之類似，只是取左邊最高的8比特，分成兩組分別進行兩次S盒變換，取k66k65k64k63k62這5位與輪計數(shù)器的值x進行異或。

2 PRESENT算法功耗分析方法

密碼分析與設(shè)計是現(xiàn)代密碼學(xué)中的相輔相成的兩個方向，共同促進了密碼技術(shù)的提高［5］。在進行密碼算法的設(shè)計時必須要考慮算法是否可以抵擋這些手段的攻擊。

其中，能量分析也叫功耗分析，是側(cè)信道攻擊中的一種，1999年由Kocher等提出的，經(jīng)過大量的實踐證明該分析方法適用于絕大部分由硬件實現(xiàn)的密碼算法的分析。進行差分功耗分析一般有五個特定的步驟：

1）在密碼算法中挑選一個合適的中間值；

2）對中間值函數(shù)的執(zhí)行過程進行多次測量并完整記錄能量的消耗值；

3）利用每一個可能的密鑰（或密鑰的一部分）計算出相應(yīng)的中間值；

4）將中間值利用仿真技術(shù)映射為能量消耗值；

5）將3）中計算出的能量跡與4）中的能量跡進行對比，然后分析出正確的密鑰［6～8］。

自從2007年P(guān)RESENT算法被提出以后，相關(guān)學(xué)者利用各種不同的方法對該算法進行了大量的分析研究，并取得了一定的成果。在文獻［9］中研究者利用線性分析方法實現(xiàn)了25輪PRESENT的破解，并計算出如果利用相同的方法破解28輪的PRESENT則需要284組明文-密文對；文獻［10］中中國學(xué)者利用差分分析的方法在已知264個密文的情況下最多可以實現(xiàn)16輪PRESENT的破解；文獻［11］中利用代數(shù)分析的方法將密鑰長度為80比特的6輪PRESENT算法進行選擇明文破解也需要203個小時。大量學(xué)者利用復(fù)雜的方法，在苛刻的條件下對減輪PRESENT算法進行攻擊也需要相當(dāng)長的時間，而目前還沒有在合理時間內(nèi)攻破31輪PRESENT的技術(shù)。而文獻［12］中作者利用功耗分析計算漢明重量的方法僅用0.63s就實現(xiàn)了對3輪PRESENT的分析，而文獻［11］中采用傳統(tǒng)分析方法在同等條件下對其進行分析耗時達3593.6s。

3 Random-PRESENT設(shè)計

目前，PRESENT算法對傳統(tǒng)的密碼分析技術(shù)具有一定的免疫力，而正在不斷發(fā)展的功耗分析對其造成了巨大的威脅。而且，為了提高算法處理數(shù)據(jù)的速度，PRESENT算法大多采用硬件的形式來實現(xiàn)，這就為功耗攻擊創(chuàng)造了便利條件。

在原始算法中每輪加密開始階段是輪子密鑰與64比特中間狀態(tài)異或，然后分成16個4比特的數(shù)據(jù)塊經(jīng)S盒進行轉(zhuǎn)換，最后S盒輸出的16×4比特數(shù)據(jù)經(jīng)P置換打亂順序。由此，可以將4比特的數(shù)據(jù)塊看作最小的處理單元，每一輪加密開始實際上是對16個數(shù)據(jù)單元依次進行異或、S盒替換、P盒轉(zhuǎn)換的操作，其原理如圖2所示。

為了提高算法對功耗攻擊的防護能力，現(xiàn)對PRESENT實現(xiàn)過程中的細節(jié)進行改進，設(shè)計出了一種改進型算法—Random-PRESENT，算法第一輪的加密過程如圖3所示，重復(fù)進行31輪迭代完成數(shù)據(jù)的加密處理。

改進的主要思想是在原始PRESENT硬件中加入隨機數(shù)發(fā)生器，對要進行加密的明文以及與其相對應(yīng)的密鑰進行隨機化的分組，再對分組后數(shù)據(jù)依次進行加密操作，使攻擊者測量的各個階段的功耗曲線不具有統(tǒng)計特性。

在Random-PRESENT算法中用隨機數(shù)控制數(shù)據(jù)分組，將這16個數(shù)據(jù)單元打亂順序，隨機分配成x個“加密操作塊”，而且每個加密塊中含有若干個“4比特數(shù)據(jù)組”，數(shù)量由隨機數(shù)決定。在進行下一步的加密操作時，同樣按照隨機化處理過的順序進行，隨機對數(shù)據(jù)組進行運算。

雖然在硬件中對數(shù)據(jù)的處理順序發(fā)生了變化但是并不影響輸出結(jié)果的準(zhǔn)確性，同一密鑰對同一明文的加密結(jié)果是相同的。但是攻擊者在進行差分功耗分析時，在同一密鑰下對不同的明文進行加密，這一過程中對能量消耗進行分析，所采集的功耗曲線是混亂的，并不具備較強統(tǒng)計特性，因為利用隨機數(shù)控制執(zhí)行順序，攻擊者無法確定測量的功耗曲線究竟是哪個操作的能量跡。這一方法可以適用于多種由硬件實現(xiàn)的分組密碼算法當(dāng)中，可以有效地抵抗簡單功耗分析與差分功耗分析。

解密時，按照同樣的方式進行數(shù)據(jù)的處理，每4比特的密文數(shù)據(jù)當(dāng)作一個小的數(shù)據(jù)分組，利用隨機數(shù)再對這16個數(shù)據(jù)組進行分組，然后依次完成解密操作。解密時生成的隨機數(shù)不會影響最終輸出的結(jié)果。

4 Random-PRESENT抵抗功耗攻擊原理與效果分析

由3節(jié)可知由于差分功耗分析具有不要求攻擊者了解被攻擊設(shè)備的詳細知識、可以多次測量功耗軌跡消除噪聲等特點，成為了目前比較流行的功耗攻擊方法之一。而其攻擊過程中的關(guān)鍵是要對硬件執(zhí)行過程中的能量消耗曲線進行測量記錄，而且要精確對齊每一個邏輯運算的功耗軌跡。

Random-PRESENT中每一輪程序的執(zhí)行順序都是隨機的，攻擊者利用假設(shè)的密鑰對數(shù)據(jù)進行處理，在對能量消耗值進行測量的過程中，每一次測量時數(shù)據(jù)處理的次序都發(fā)生了改變，每次處理的數(shù)據(jù)量也不確定，這導(dǎo)致攻擊者每次測量的功耗曲線順序也是隨機的，不可能將同一個邏輯運算的功耗軌跡對齊、比較。

例如，在PRESENT算法中第一輪開始時先進行輪子密鑰與明文塊的異或運算，在硬件中由邏輯指令控制算術(shù)邏輯單元完成，輸入特定的明文，當(dāng)密鑰為1時執(zhí)行一個特定的指令，當(dāng)密鑰為0時又是另外一個結(jié)果，不同的邏輯運算將導(dǎo)致很明顯的功耗差異。在PRESENT算法中，輸入同樣的明文，用同一個密鑰進行加密，在算法芯片中這些微控制器工作順序以及每次運行所執(zhí)行的操作是一樣的，這將導(dǎo)致輸出相同的功耗曲線，當(dāng)攻擊者猜想的密鑰k與真實加密密鑰相同或相似時將導(dǎo)致功耗曲線的相同或相似。在攻擊過程的第二步中攻擊者會記錄如表4所示的數(shù)據(jù)。

表4 實際測量能量消耗記錄表

該列表相當(dāng)于一個D×T的矩陣，每一行可以看作是對一個數(shù)據(jù)分組進行加密的過程，在這一過程中記錄了T個操作過程中的能量消耗曲線。每一列則可以看作是同一操作過程在處理不同數(shù)據(jù)分組時的能量消耗曲線。這一步驟的難點是精確地對齊每一個操作過程，即保證ti記錄的是對不同數(shù)據(jù)進行“操作i”時的能量消耗曲線，這也是攻擊成功的關(guān)鍵所在。在后續(xù)的攻擊過程中，攻擊者將利用所有假設(shè)密鑰信息K依次對D個數(shù)據(jù)分組進行處理，并記錄其進行每一個操作時的能量消耗曲線，經(jīng)仿真后比較究竟哪個k處理分組數(shù)據(jù)時與之前的真實能量曲線最接近，從而恢復(fù)出密鑰信息。

而在Random PRESENT算法中，對程序執(zhí)行過程進行了隨機化處理，當(dāng)攻擊者對D個數(shù)據(jù)分組進行測量時，不能保證能量跡ti都對應(yīng)“操作i”，在ti對應(yīng)的D個操作中會出現(xiàn)不同的硬件執(zhí)行過程，不能對齊能量跡將導(dǎo)致差分功耗分析的失敗。當(dāng)然，當(dāng)攻擊者將多次測量的假設(shè)能量消耗值與經(jīng)隨機處理的“真實能量消耗值”進行匹配時，也幾乎不能發(fā)現(xiàn)高度吻合的曲線峰值。利用不同的假設(shè)密鑰信息對數(shù)據(jù)組進行加密或解密處理后，保存如表5中記錄的能量值，每一個能量跡都是對數(shù)據(jù)進行加密過程的完整記錄。當(dāng)攻擊者試圖尋找究竟該密碼設(shè)備是用哪一組密鑰信息在對D個數(shù)據(jù)分組進行加密或者解密操作時會將每一個假定k值對應(yīng)的假設(shè)測量值與表4中的實際能量測量值進行對比，顯而易見，攻擊者找到兩條相似的能量跡的可能性幾乎為0。由第4節(jié)中對Random-PRESENT的介紹可知，如果隨機化控制每一位密鑰與中間狀態(tài)進行異或的順序后，輸入與真實密鑰相同的假設(shè)密鑰后，可能出現(xiàn)峰值的概率也極低，雖然可以利用先進的分析手段確定信息的漢明重量排除一些不可能的密鑰值，但是也不容易做到多次測量相同的曲線求平均值來消除噪聲，這依然有相當(dāng)大的工作量，因此Random PRESENT可以在合理時間內(nèi)抵抗差分功耗分析。

表5 假設(shè)密鑰能量消耗測量值

當(dāng)然，不排除攻擊者發(fā)現(xiàn)一個與真實能量跡高度吻合的假設(shè)能量跡，但是其所使用的假設(shè)密鑰信息k與真實密鑰信息相同的概率也是很小的，因為這很可能是一個錯誤的密鑰經(jīng)過不同順序的邏輯處理之后產(chǎn)生了這種效果，當(dāng)再次利用該錯誤的密鑰對消息進行加解密時必然不會得到系統(tǒng)的認可。由此可見，Random PRESENT算法對差分功耗分析有一定的抵抗能力。

5 結(jié)語

本文對現(xiàn)有PRESENT算法進行了改進，設(shè)計出了一個Random-PRESENT算法，通過隨機化數(shù)據(jù)處理的順序達到防止差分功耗分析的目的。并對改進的算法進行抗攻擊分析，保證算法具有一定的實用價值，更加適應(yīng)運算資源受限的系統(tǒng)。

［1］張婧.輕量級分組密碼PRESENT功耗攻擊的研究［D］.上海：上海交通大學(xué)，2011.

［2］馮登國，吳文玲.分組密碼的設(shè)計與分析［M］.北京：清華大學(xué)出版社，2000：231-257.

［3］馮登國，裴定一.密碼學(xué)導(dǎo)引［M］.北京：科學(xué)出版社，1999：145-158.

［4］Bogdanow A，Knudseu L R，Leander G．PRESENT：An Ultra-Lightweight B1ock cipher［C］//9th International Workshop for Cryptographic Hardware and Embedded Systems-CHES2007． Vienna：Springer-Verlag， 2007：450-466.

［5］張美玲.分組密碼分析技術(shù)的研究［D］.西安：西安電子科技大學(xué)，2010.

［6］馮登國，周永彬，劉繼業(yè).能量分析攻擊［M］.北京：科學(xué)出版社，2010：145-167.

［7］李翔宇，孫義和.用于密碼芯片抗功耗攻擊的功耗平衡加法器［J］.半導(dǎo)體學(xué)報，2005，26（08）：1629-1634.

［8］張詠，范明鈺，王宇飛.對于DES的差分能量分析攻擊及其防范對策［J］.電子技術(shù)應(yīng)用，2005，27（05）：23-24.

［9］Joo Yeon Cho． Linear cryptanalysis of reduced-round PRESENT［C］//Topics in Cryptology-CT-RSA． San Francisco：Springer，2010：302-317.

［10］ Meiqin Wang． Differential cryptanalysis of reducedround PRESENT［C］//First International Conference on Cryptology in Africa． Casablanca Morocco：Springer-Verlag，2008：40-49.

［11］卜凡，金晨輝.針對低輪PRESENT的代數(shù)攻擊［J］.計算機工程，2010，36（6）：128-130.

［12］吳克輝，王韜，趙新杰.基于漢明重的PRESENT密碼代數(shù)旁路攻擊［J］.計算機科學(xué)，2011，38（12）：53-56.