用于實(shí)現嵌入式安全的開(kāi)源硬件

想像一下你正在排隊等待參加一個(gè)重要活動(dòng)。門(mén)票是通過(guò)網(wǎng)上購買(mǎi)的，存儲在你的智能手機中。你需要將手機放到某個(gè)指定區域上，建立起NFC連接，門(mén)票隨之得到確認，大門(mén)開(kāi)啟允許你進(jìn)入。好消息是，所有這一切都是在匿名情況下發(fā)生的。

在這類(lèi)應用中，你的匿名信息可以通過(guò)使用最近開(kāi)發(fā)的匿名信任協(xié)議(如IBM的Idemix或微軟的U-Prove)得到保護。這些協(xié)議基于知識的零知識證明(ZKPK)。你可以證明你擁有某個(gè)屬性的知識而不用透露具體數值。這種屬性與所謂的承諾中的公鑰是捆綁在一起的。

圖1給出了這種ZKPK——本例中的Schnorr協(xié)議的簡(jiǎn)要示意圖。其中y是x的承諾。在強大的RSA假設下，是很難從y找出x的，即使你知道g和m。

仔細觀(guān)察協(xié)議我們會(huì )發(fā)現x仍然是隱藏的。驗證方只知道y是正確的承諾。我們還能發(fā)現，協(xié)議主要由通信和算法組成——這正是我們研究的對象。

圖1： Schnorr ZKPK協(xié)議的簡(jiǎn)化版本。

----------------------------------------------------------------------------------------------------------------------------------------------

在嵌入式平臺上計算并行求冪所需時(shí)間的例子

在我們的測試裝置(后面會(huì )討論到)上，我們比較了硬件加密內核和軟件實(shí)現方法的執行時(shí)間。

硬件和軟件都計算：

在匿名信任協(xié)議中經(jīng)常使用的并行求冪。

我們規定指數長(cháng)度在32位和2048位之間變化?；鶖档拈L(cháng)度是固定的，本例中是1024位。軟件運行在嵌入式Linux操作系統上，并在多精度算法中使用了GMP庫。

處理器和IP內核都以相同速度(100MHz)運行。我們發(fā)現，兩種方法的執行時(shí)間都隨指數長(cháng)度成比例的增加。然而，采用硬件卸載方式的運算要快10至50倍。

圖2：在嵌入式平臺上分別用硬件卸載和不用硬件卸載時(shí)的并行求冪執行時(shí)間。

嵌入式安全性測試平臺

我們很快發(fā)現，當這些ZKPK在嵌入式系統上實(shí)現時(shí)，通信和算法都會(huì )引起瓶頸(見(jiàn)例子)。我們不希望用戶(hù)保持NFC連接超過(guò)比方說(shuō)5秒鐘，不然會(huì )與通過(guò)“接觸”交換數據的NFC概念發(fā)生沖突。

為了詳細研究這個(gè)問(wèn)題，我們構建了一個(gè)測試平臺(見(jiàn)圖3)，以便我們能夠方便地改變協(xié)議的不同方面。例如，如果我們將算法卸載到硬件加速器來(lái)提升算法速度會(huì )怎么樣？或者操作數的長(cháng)度對通信和算法的速度有何影響？

我們開(kāi)發(fā)的平臺如圖3所示，它基于的是賽靈思的ML605評估板。我們增加了恩智浦的PN532開(kāi)發(fā)套件用于NFC通信。運行嵌入式Linux的MicroBlaze用于控制整個(gè)系統。使用Linux(本例中用的是PetaLinux發(fā)行版)有很大的優(yōu)勢，即在嵌入式系統中可以用標準庫，比如用于算法的GMP和用于NFC通信的libnfc。

圖3：用于測試和評估匿名信任協(xié)議的嵌入式平臺。

使用FPGA可以很方便地增加和開(kāi)發(fā)加密硬件加速器。本文余下部分將討論我們開(kāi)發(fā)用于測試目的的這種IP內核設計。

開(kāi)源硬件

因此我們想要一個(gè)可以用作硬件加速器的加密內核?？赡艿脑?huà)，它可以計算：

市場(chǎng)上有多種IP內核可以用來(lái)執行單次模冪運算。然而，像DAA或Idemix等協(xié)議要求至少兩次這種求冪的產(chǎn)品。這意味著(zhù)我們仍然必須執行大操作數的多次(模)乘法，這將進(jìn)一步增長(cháng)總的執行時(shí)間。另外，我們希望能夠改變所有操作數的長(cháng)度，但不顯著(zhù)降低性能。也許我們還希望在其它平臺上測試硬件。

這份希望清單促成了開(kāi)源IP內核的設計，并符合以下規范：

● 針對嵌入式平臺的開(kāi)源IP內核(控制要求的軟件)
● VHDL代碼獨立于器件和制造商，并得到良好歸檔
● 基數g0、g1和模數m的長(cháng)度可以在綜合前自由選取
● 為指數準備了一個(gè)FIFO，因此e0和e1的長(cháng)度可以完全取決于控制軟件
● 將流水線(xiàn)式蒙哥馬利乘法器作為IP內核的核心，并具有自由選擇的級長(cháng)，從而允許調整內核獲得想要的速度/面積
● 操作數RAM專(zhuān)門(mén)針對并行求冪進(jìn)行了優(yōu)化

然而，這不是一個(gè)(完美的)商用產(chǎn)品。我們知道可以實(shí)現更快或更小的設計。但每個(gè)人都可以自由使用并用這個(gè)設計做試驗。這是我們設計的最初目的，也是我們做得盡可能可定制的原因。

目前這個(gè)內核還沒(méi)有任何JTAG接口或自檢功能。然而，可以對某些測試矢量執行求冪并比較結果來(lái)驗證操作是否正確。

一些背景

并行求冪

最直接也是高效的模冪運算方法是通過(guò)重復平方和乘法運算獲得最終結果。這種方法很容易擴展到并行求冪運算。下面就是這種算法的描述，其中Mont()表示蒙哥馬利乘法。這是一種用硬件執行模乘運算的有效方法，我們對此還將進(jìn)一步討論。我們假設R2 (= 22n ,n是m的長(cháng)度)可以通過(guò)控制軟件提供甚至計算。

仔細觀(guān)察這個(gè)算法可以發(fā)現，采用要么運行單次乘法(用于預運算和最終乘法)要么自動(dòng)運行主環(huán)的方式只實(shí)現一個(gè)乘法器并實(shí)現控制邏輯是合理的設計選擇。

遵循標準的設計思路，我們將IP內核實(shí)現為存儲器映射的外設。內核行為可以通過(guò)驅動(dòng)軟件使用控制寄存器改變(圖4)。由于主環(huán)要求4個(gè)操作數，因此需要提供內存進(jìn)行存儲。中斷線(xiàn)允許硬件就某些事件提醒處理器。

普通32位總線(xiàn)接口可以很容易擴展到多種流行的總線(xiàn)標準，如AXI或Wishbone。下面給出了最終設計的框圖(n代表操作數的寬度)。

圖4：我們開(kāi)發(fā)的并行求冪IP內核的框圖。

模乘

現在我們的工作將簡(jiǎn)化為設計一個(gè)乘法器，并且它能根據我們的需要方便地進(jìn)行定制。當操作數長(cháng)度大于512位(對我們的應用來(lái)說(shuō)這是顯然的情況)時(shí)，一種被稱(chēng)為脈動(dòng)陣列蒙哥馬利的乘法器(2)是最有效的實(shí)現。此外，它很容易轉換成硬件，從而簡(jiǎn)化生成通用描述的任務(wù)。

Mont(x,y)可以通過(guò)計算x的每一位的中間結果(a)進(jìn)行運算。因此在經(jīng)過(guò)n位后，乘法運算就完成了。a的每一位都可以用加法器和乘法器進(jìn)行運算，最后一起形成脈動(dòng)陣列單元(圖5)。當大量單元級聯(lián)時(shí)，為了中斷進(jìn)位鏈，我們將它們組成級。這樣我們就可以控制設計的最大可達到頻率，而這個(gè)頻率主要受限于這個(gè)進(jìn)位鏈。另外，還允許流水線(xiàn)運算。作為蒙哥馬利算法一部分的右移操作可以確保a永遠不會(huì )大于n+2位。

圖5：一個(gè)脈動(dòng)陣列單元計算中間結果a的一個(gè)位。

流水線(xiàn)操作見(jiàn)下圖所示(圖6)。每個(gè)圓代表一級。圓內的數字代表當時(shí)由那個(gè)級正在執行的步驟(x的哪一位)。非活動(dòng)級用虛線(xiàn)表示。我們可以看到，一個(gè)級只能每2τc計算一步。這是右移操作的原因。τc表示一個(gè)級實(shí)際完成一個(gè)步驟所花的時(shí)間。在本例中，τc就是1個(gè)時(shí)鐘周期。

圖6：脈動(dòng)流水線(xiàn)操作。

移位寄存器用于將x的位移進(jìn)脈動(dòng)流水線(xiàn)。兩個(gè)額外加法器在必要時(shí)計算m+y(這是脈動(dòng)陣列要求的)和a-m(確保結果小于m)。最終乘法器結構如下所示(圖7)。

圖7：蒙哥馬利乘法器結構。

性能

乘法器資源使用率取決于操作數(n)的長(cháng)度和流水線(xiàn)的級數(k)。

對FPGA來(lái)說(shuō)可以表示為：

對于大的n來(lái)說(shuō)，整個(gè)IP內核只使用另外一小部分FF和LUT比如用于控制邏輯和總線(xiàn)接口。然而，它也需要多個(gè)RAM單元來(lái)存儲操作數。

執行乘法的時(shí)鐘周期數也取決于n和k：

不過(guò)如前所述，級數——因此這些級的長(cháng)度——對乘法器的最大可達時(shí)鐘頻率也有影響。這可以從圖7看出來(lái)(n=2048)。

圖8：流水線(xiàn)級長(cháng)度對最高時(shí)鐘頻率的影響。

在使用這個(gè)設計時(shí)，可以有幾種方法：

1．我們預先知道我們的工作頻率。然后就足以選擇級數以便讓時(shí)鐘頻率至少能那么高。選擇更多的級數只會(huì )導致耗用更多的資源(觸發(fā)器)。
2．盡量縮短運算時(shí)間。這將由級數和最大時(shí)鐘頻率來(lái)確定。如果我們認為設計將在這個(gè)頻率運行(理論上)，我們可以獲得下圖所示的運算時(shí)間(n=1536)。我們可以看到，對我們的器件(Virtex 6)來(lái)說(shuō)，當級長(cháng)為4位時(shí)可以獲得最短運算時(shí)間。

圖9：流水線(xiàn)級長(cháng)對最短執行時(shí)間的影響。

我們想要盡可能地減小時(shí)間與面積乘積。事實(shí)上，我們可以專(zhuān)注于最大限度地減小時(shí)間與FF數量的乘積，因為L(cháng)UT數量基本上是常數。下圖顯示了不同流水線(xiàn)級長(cháng)下的時(shí)間與FF數量乘積。當級長(cháng)為8位時(shí)達到最小值。

圖10：流水線(xiàn)級長(cháng)對時(shí)間與面積乘積的影響。

首次測試

基于NFC的ZKPK

作為第一次實(shí)際測試，我們實(shí)現了基于NFC的簡(jiǎn)化Schnorr ZKPK，詳見(jiàn)我們的嵌入式測試平臺介紹。這種個(gè)嵌入式平臺是驗證方，而PC(連接有PN532電路板)用作證明方。

下表給出了不同操作數長(cháng)度下的時(shí)序結果。很明顯，當使用我們的硬件IP內核時(shí)，操作數長(cháng)度對總的協(xié)議時(shí)間基本上沒(méi)有影響。增加操作數長(cháng)度會(huì )稍稍增加通信時(shí)間(這是預料中的)。然而，驗證所需的時(shí)間將大大增加。

我們需要指出的是，通信占總時(shí)間的很大一部分。像產(chǎn)生隨機數等一般數據操作也需要一定的時(shí)間。然而，我們的IP內核還無(wú)法克服這些挑戰。

軟件控制方案對比全自動(dòng)操作

實(shí)現完整的并行求冪內核是一個(gè)英明的決策嗎？為什么不只是乘法器和一些控制軟件來(lái)實(shí)現算法1？因為我們可以將我們的IP內核用作乘法器，我們能夠非常容易的測試它。我們可以在相同的系統上比較這兩種方法。

即使我們將操作數存儲在IP內核的RAM中(因此沒(méi)有額外的總線(xiàn)業(yè)務(wù)量)，全自動(dòng)操作的速度仍要比軟件控制方案快一個(gè)數量級(見(jiàn)圖2)。這是意料之中的。Linux不是一種實(shí)時(shí)操作系統。在操作系統處理中斷之前，或者應用程序訪(fǎng)問(wèn)它們需要的資源(本例中為我們的存儲器映射外設)之前，可能需要等待一定的時(shí)間。如果你知道一次求冪要求大約(7/4)t乘法(見(jiàn)算法1)，這種“損失時(shí)間”會(huì )很快累加起來(lái)。

如果你知道將乘法器轉變成并行求冪內核所需的額外邏輯只由FIFO和一些計數器組成，那么我們可以說(shuō)額外的硬件是比較值得的。

小結和未來(lái)發(fā)展

我們已經(jīng)表明，這種用于模并行求冪運算的IP內核的可定制VHDL設計是非常適合匿名信任加密系統的嵌入式實(shí)現的。我們已經(jīng)見(jiàn)證了如何調整內核參數來(lái)滿(mǎn)足用戶(hù)的需要。

除了更為理論性的性能分析外，我們還在實(shí)際的嵌入式裝置中使用了這個(gè)設計。作為我們未來(lái)工作的一部分，我們將繼續為匿名信任證書(shū)開(kāi)發(fā)完整的嵌入式應用程序。

進(jìn)一步開(kāi)發(fā)對象還將導向內核本身。目前內核只提供PLB接口。提供對AXI和Wishbone接口的支持“已經(jīng)列在任務(wù)清單上”。

包括所有乘法與求冪技術(shù)文檔和測試基準的完整VHDL設計已經(jīng)在開(kāi)源網(wǎng)站OpenCores上公開(kāi)上線(xiàn)。只要有GNU較寬松通用公共許可(LGPL)協(xié)議就能免費下載VHDL源代碼。