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

劉 鵬

1 引言

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

1.1 PRESENT加解密過程

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

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

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

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

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

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

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

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

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

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

1.2 PRESENT密鑰擴(kuò)展方案

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

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

2 PRESENT算法功耗分析方法

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

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

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

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

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

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

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

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

3 Random-PRESENT設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

表4 實(shí)際測量能量消耗記錄表

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

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

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

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

5 結(jié)語

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

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

［2］馮登國，吳文玲.分組密碼的設(shè)計(jì)與分析［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é)報(bào)，2005，26（08）：1629-1634.

［8］張?jiān)?，范明鈺，王宇飛.對(duì)于DES的差分能量分析攻擊及其防范對(duì)策［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］卜凡，金晨輝.針對(duì)低輪PRESENT的代數(shù)攻擊［J］.計(jì)算機(jī)工程，2010，36（6）：128-130.

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