用于實現(xiàn)嵌入式安全的開源硬件

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

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

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

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

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

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

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

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

硬件和軟件都計算：

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

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

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

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

嵌入式安全性測試平臺

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

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

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

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

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

開源硬件

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

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

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

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

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

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

一些背景

并行求冪

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

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

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

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

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

模乘

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

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

圖5：一個脈動陣列單元計算中間結(jié)果a的一個位。

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

圖6：脈動流水線操作。

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

圖7：蒙哥馬利乘法器結(jié)構(gòu)。

性能

乘法器資源使用率取決于操作數(shù)(n)的長度和流水線的級數(shù)(k)。

對FPGA來說可以表示為：

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

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

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

圖8：流水線級長度對最高時鐘頻率的影響。

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

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

圖9：流水線級長對最短執(zhí)行時間的影響。

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

圖10：流水線級長對時間與面積乘積的影響。

首次測試

基于NFC的ZKPK

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

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

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

軟件控制方案對比全自動操作

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

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

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

小結(jié)和未來發(fā)展

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

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

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

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