安全生产管理先进安全密码模组分析报告.docx
《安全生产管理先进安全密码模组分析报告.docx》由会员分享,可在线阅读,更多相关《安全生产管理先进安全密码模组分析报告.docx(18页珍藏版)》请在冰点文库上搜索。
安全生产管理先进安全密码模组分析报告
{安全生产管理}先进安全密码模组分析报告
先進安全密碼模組分析報告
曾享煥、劉燦雄、單懷靈、歐崇明、王鯨洋
中華電信研究所‧應用科技研究室
1.AES介紹及現況
1.1源由
最近美國國家技術標準局(NIST)已經在招攬繼DES演算法之後,有關於先進的加密標準(AES)的候選者。
他們要求加密區塊的明文長度為128位元,可接受的密鑰長度為128位元、192位元和256位元(含以上)。
判定的標準為安全性、效率與適應性三方面。
NIST希望在這個世紀結束之前,能夠預備好一個新的加密標準。
AdvancedEncryptionStandard(AES)-二十一世紀的一種加密演算法。
在1998年8月20日第一次AES候選者的研討會中,NIST正式宣布十五個加密標準:
CAST-256,CRYPTON,DEAL,DFC,E2,FROG,HastyPuddingCipher(HPC),LOKI97,MARS,Magenta,RC6,RIJNDAEL,SAFER+,SERPENT,TWOFISH。
正式官方的評論:
如有任何公開的意見可mail至AESFirstRound@,經採納後於9915公布結果,非正式(網路線上)的評論:
進入AES站內的公開討論版上刊載意見,9922-23NIST在義大利羅馬的奎爾諾飯店召開第二次AES候選者的研討會,根據第一回合的評論及結果選出最後的五個候選者。
網站內容包括:
(1)AES候選者演算法的介紹;
(2)網路上的資料包括演算法的提出者及作者、摘要、內容及規格、提案等相關文件;
(3)可下載的測試表(包括由不同的金鑰長度做加(解)密等各種的中間值及測試值);
(4)註冊名稱;文件;作者的簽名、提出者的版權登記、專利書;
美國聯邦政府的註冊及評論、提案的正式評論、公開的分析及勘誤表。
1.2介紹
AES的需求:
經由公開的程序對外徵求;是對稱性的金鑰加密法;
秘密金鑰的長度是可變的;可以同時由硬體及軟體來實作;
沒有專利的限制或必須符合ANSI的專利政策,可以自由的使用;
AES的評選標準:
安全性:
必須通過現有的密碼攻擊法;效率:
執行必須有效率;
記憶體的需求;是否適合硬體及軟體來實作;演算法必須簡單易懂;
可變性:
金鑰長度必須是可變更的;專利的問題;
網站.govaes/aes_中有談到DEAL,FROG,LOKI97,MARS,Magenta等五種具有攻擊法(訊息更新於9823)。
目前對各AES演算法的攻擊有下列五種〔備註1〕:
名稱
攻擊法類型
參考
DEAL
S.Lucks,``OntheSecurityofthe128-bitBlockCipherDEAL''
FROG
差分和線性攻擊法(Differentialandlinearattacks)
D.Wagner,N.Ferguson,andB.Schneier,
"CryptanalysisofFrog,"
LOKI97
K=56bits,C=56bits
V.Rijmen,L.R.Knudsen,``WeaknessesinLOKI97''
K:
56/./.,C:
56/./.〔備註2〕
Magenta
選擇明文攻擊法(Chosenplaintextattack)
E.Biham,A.Biryukov,N.Ferguson,L.Knudsen,
B.Schneier,A.Shamir,CryptanalysisofMAGENTA
MARS
有weakkeys
M-J.Saarinen,"EquivalentkeysinMARS"
備註:
[1]參考網站.
TheBlockCipherLounge–AES:
TheAESProposals(資料更新於199824)。
[2]K:
ac:
表示最佳的已知明文攻擊法需要2a個明文/密文對,有2b個加密的工作量,並且需要。
Hasaworkloadof2bencryptionsandrequires2cwordsofmemory.
[3]C:
ac:
denotesthatthebestchosenplaintextattackrequires2aplaintext/ciphertexts,
Hasaworkloadof2bencryptionsandrequires2cwordsofmemory.
[4]A`.':
表示資料的來源不是很重要或是我們不知道的。
[5](r):
表示攻擊法運算的回合數,如果是空白,則r=Rounds。
[6][SA]:
表示在文章內有描述攻擊法。
[7]?
:
表示沒有已知的攻擊法。
1.3演算法結構表
由於AES是希望能夠在未來的二十年內能夠完全取代DES成為新的對稱式形加密演算法,因此對於明文大小、金鑰(key)長度、演算法的運算回合數、以及所使用的演算法技巧都被廣泛的加以討論,並針對不同的狀況提出實做的數據加以比較,或針對不同的模組提出有效的攻擊,期望能夠真正找到一個兼顧安全與效能的演算法。
我們在下表提供15個入圍的AES候選演算法的相關資料,包括運算回合數、區塊資料大小、金鑰長度以及在每一個演算法所用到的特殊技巧。
AEScandidates的結構表
Algo
Rithm
Serialnumber
Datasize(bits)
Block(Subdata)size(bits)
Keysize(bits)
Subkeysize(bits)
Numberofsubkeys
Memoryofsubkeys(bytes)
On-the-Flykey
Speedofdifferentkeylengths.
NonlinearlyFunction
FeistelNetwork
Whitening
NumberofRounds
Min.SecureRounds
RIJNDAEL
12
128,192,256
8
128,192,256
32
Nb(Nr+1)
160
(Nb=4,Nr=4)
Two-way
Increasing
S-Box
No
Yes
[Table2]
8
RC6
11
128
32
0~255bytes
32
44
176
Notavailable
Constant
DR,IR
Yes
Yes
20
20
TWOFISH
15
128
32
128,192,256
32(words)
40
160
Two-way
Increasing
S-Box
Yes
Yes
16
12
MARS
10
128
32
128~1248
32
40
160
Notavailable
Constant
DR,IR,S-Box
Yes
Yes
8,8,8,8
10
SERPENT
14
128
32
256
128
33
528
Forward
Constant
DR,S-Box
No
No
32
17
E2
5
128
64
128,192,256
16
16
256
Notavailable
Constant
S-Box
Yes
Yes
12
10
CAST-256
1
128(2~4blocks,64bits/block)
32
128~256
Rotatekey:
5
Maskkey:
32
12
55.5
Forward
Constant
DR,S-Box
Yes
No
32(Opts:
48)
10
SAFER+
13
128
8
128,192,256
2bytes
2r+1
272
(r=8)
Two-way
Increasing
FunctionTable
No
Yes
128:
8
192:
12
256:
16
7
DFC
4
128
64
0~256
128
8
128
Forward
Constant
S-Box
Yes
No
Key:
4
Crypt8
9
CRYPTON
2
128
324
0~256
324
52
208
Two-way
Constant
S-Box
No
Yes
12
11
DEAL
3
128
322
128,192,256
64
(DESkey)
128/192:
6
256:
8
48
Forward
Increasing
S-Box
Yes
Yes
128/192:
6
256:
8
6
HPC
7
隨意
35,35~64,65~128,129~512,513
隨意
256(words)
1280
10240
Notavailable
Constant
Rotate
Yes
No
8
8
MAGENTA
9
128
Increasing
>10
FROG
6
128
(64~1024)
128
(64~1024)
40~1000
288
8
2304
Notavailable
Constant
S-Box
No
No
8
8
LOKI97
8
128
64
128,192,256
64
48
384
Forward
Decreasing
S-Box
Yes
No
16
>36
[1]Datasize:
表示此一Blockcipher可以一次看待資料的的長度,也就是加密資料一次的單位長度,以位元(bits)為單位。
[2]Blocksize:
表示在內部加密時,以多大的資料段來處理,可以視其為以此大小為導向的cipher,如:
Blocksize=8:
Byte-oriented、Blocksize=32:
Word-oriented、Blocksize=64:
Doubleword-oriented。
[3]Keysize:
為秘密鑰匙(Secretkey)的長度,以位元(bits)為單位。
對單一加密演算法而言,長度越長表示越安全,但相對地也要付出更多的加解密時間。
[4]Subkey:
由秘密鑰匙所算出,在每一個round中真正參予與資料運算的子密鑰,除於後標出長度單位者,其餘皆以位元(bits)
為單位。
[5]Numberofsubkeys:
全部所需的子密鑰的數量。
[6]Memoryofsubkeys(bytes):
所有子密鑰所佔用的記憶體,當子密鑰越多、越長就越佔記憶體,若應用在chip、smartcard時,會提高成本與設計製造的難度。
[7]On-the-Flykey:
所有的子密鑰可以到了加解密時才造出,及每一個Round加解密所需的子密鑰都是到了當時才即時產生出來,如此可以節省已用過/尚未用的子密鑰;又可以分為單向產生(Forward)或雙向/隨意產生(Two-way)。
[8]Speedofdifferentkeylengths:
不同鑰匙長度時,加密所需的時間。
大部分都為定值,但也有些會隨著鑰匙長度變化而有正反比的關係。
(這兩項資料參考自/AES-)
[9]NumberofRounds:
AEScandidates在其演算法中所建議的Rounds數。
[10]DR:
資料相依於旋轉(DataDependentRotation);IR:
資料和旋轉無關(DataIndependentRotation)。
[11]Whitening:
這個技巧是在第一個round函數前,先將明文與key做運算(exclusive-OR或byteaddition),在最後
一個round函數之後,再將所得結果與key做運算(exclusive-OR或byteaddition)成為密文。
Whitening隱藏
第一個round的輸入與與最後一個round輸出之間的關係,這可以增加攻擊的困難度,因為通常攻擊法都是
針對第一個round的輸入至最後一個round的輸出作分析,而第一個round的輸入與最後一個round的輸出的
實際值已經被隱藏。
這個方法對於chosenplaintextattack亦非常有效。
1.4相關網站
./~larsr/
AES_15_Algorithm
..twAES
..twAES
.:
8000/cast
.:
8000
AES
.gov/aes
Cast128Paperrfc2144.txt
.rfcrfc2144.txt
CryptographicAlgorithms
#asymmetric
ACryptographicCompendium
fn2../~jsavard/
AESCandidateAlgorithmsArchitecture
..twAES/AES_
FTPDirectory
ftp:
//.ficryptsymmetric/
AES_Cipher_Speed
.eeaes/
Test_EBC_
/ecb_
Twofish
/
1.5時程總表
AES時程總表(AESTimelineSummary)
April15,1999
Round1Commentperiodcloses.
第一評論回合結束
May15,1999
Explanation/justificationofproposedweaksandupdatedspec.aredue.
說明題案的補充及更新的規格書
Summer1999
AnnouncementofFinalists.
公佈決賽選手
AnnouncementofFinalists+1month
UpdatedcodeforRound2isdue.
更新第二回合題案的程式碼
January15,2000
PapersdueforAES3.
提出AES3的論文
WeekofApril10,2000
AES3(NewYorkCity)
在紐約的AES3選拔會
May15,2000
Round2Commentperiodcloses.
第二評論回合結束
~August2000
AnnouncementofAESWinner(s)
公佈AES最後候選者
1.6現況
AES2會議結束後,NIST發出問卷調查,由參加者選出五種演算法。
結果如下表:
2.五種演算法的介紹
以下是最後五個候選者的演算法:
2.1Rijndael演算法
Rijndael是一種對稱式的區塊加密法,它提供加密的明文區塊為和金匙長度
範圍都為128、192、256位元。
Rijndael的設計原理不同於一般的對稱式加密
演算法,它並未採用Feistel結構來做為演算法的主要架構,而是使用三個函數
運算來做加密的動作,其安全性是沒有問題的,能夠抵擋差分攻擊法與線性攻
擊法。
而在實做速度方面來說,如果以32-bits的處理器使用C語言來撰寫程式
的話,其加密速度大約為27Mbit/s。
2.2RC6演算法
RC6演算法是由RC5演變出來的,它是被設計成為了符合AdvancedEncryptionStandard(AES)的要求。
RC6也像RC5一樣大量使用資料相依旋轉。
而RC6新的特色是輸入的明文由原先兩個區塊擴展為四個亦即有128bits的輸入,另外在運算方面則是使用了整數乘法,而整數乘法的使用則在每一個運算回合中增加了擴散(diffusion)的行為,並且使得即使很少的回合數也有很高的安全性。
RC6是一個安全、架構完整而且簡單的區塊加密法。
它提供了好的測試結果和參數方面相當大的彈性,而且由於它的簡單易懂使得我們能夠很快做一個完整的分析報告來增加我們對它的安全性做一個估計的準確性。
因此RC6可以說是近幾年來相當優秀的一種加密法。
RC6和RC5在加解密方面是不一樣的,RC6把明文分為四個區塊A、B、C、D,它們剛開始分別包含明文的初使值,經過加密運算後則為四個密文的輸出值。
一般而言,我們把明文或密文第一個位元組放在區塊A的第一個位元組,而把明文或密文最後一個位元組放在區塊D的最後一個位元組。
另外我們也使用(A,B,C,D)=(B,C,D,A)來做為區塊之間的平行轉換,其加密演算法如下:
B=B+S[0];
D=D+S[1];
fori=1tordo
{
t=B*(2B+1))<<u=D*(2D+1))<<A=((A⊕t)<<
C=((C⊕u)<<(A,B,C,D)=(B,C,D,A)
}
A=A+S[2r+2];
C=C+S[2r+3];
最後演算法則輸出A、B、C、D將其合併為密文。
而解密演算法則可由加密法反向推演出來。
2.3Twofish演算法
Twofish是一種可改變金匙長度(最大可到256bits)的區塊加密法。
這種加密法是一個16回合的Feistelnetwork,每個回合中包含了一個bijective函數F,它是由四個與密鑰有關的88-bit之S-box、一個44的MDS(maximumdistanceseparable)矩陣、一個PHT(pseudo-Hadamardtransform)所組成,另外再加上位元旋轉和一個無缺點的金鑰產生過程。
假如我們將Twofish完全充分運用於加密,在實作平台為PentiumPro時,每一個位元組(byte)加密須要17.8clockcycles,而在8-bit的智慧卡(smartcard)上執行則須1820clockcycles。
事實上針對Twofish已經有廣泛的密碼分析,針對5回合的Twofish差分攻擊法須要222.5明文對而且複雜度須要到251,因此對16回合的Twofish來說是不受差分攻擊法的威脅。
2.4MARS演算法
MARS是一種對稱式的區塊加密法,它提供加密的明文區塊為128位元,金匙長度的範圍:
128~1248位元。
MARS的設計原理主要是利用到現今電腦提供的一些高效率的運算,在現有的加密法中成為更先進的安全/效能方法。
MARS提供比3-DES更佳的安全性,並且速度顯著地比DES更快。
如用C語言的程式實作速率在200MHzPentium-Pro上約為65Mbit/sec;在200MHzPowerPC上則為85Mbit/sec。
MARS在軟硬體上的實作皆相當簡潔且容易適用在智慧卡及其他有限資源的環境。
由於高度的安全、速度及適應性,使得MARS成為下一世紀資訊網路加密需求的聰明抉擇。
2.5Serpent演算法
Serpent是一種為了符合AES標準而設計的區塊加密法,它雖然是一種很傳統的設計,但是在運算速度上仍然非常有效率。
它使用了一種類似DES所使用的S-boxes在一個新的結構上,並且有非常迅速的雪崩效應(avalanche)和有效率的位元運算,同時也使得我們在安全性的分析方面能夠很簡單提出論證來說明它能夠有效的抵擋目前已知的攻擊法。
這一個演算法所輸入的明文區塊為128-bits,密鑰長度為256-bits。
雖然它在IntelPentium/MMX的作業平臺上的速度表現是和DES一樣快,但是我們相信它在安全性的表現上會比triple-DES更好。
3.結論
目前從網站及相關論文可蒐集到AES十五個加密演算法有關的資料:
包含演算法的原理、步驟、分析、特性、程式碼、攻擊法、測試表等,可下載及測試並將資料儲存於設定之目錄下。
俟美國國家技術標準局(NIST)於200015宣布結果後,即可立即將獲選之加密演算法提供出來並建立完整之資料。
緊接著我們提供一些關於最後五個AES候選者的一些相關資料以做為參考。
六種演算
法的比較
明文
(bits)
密鑰
(bits)
替換盒
個數
運算回
合數
DES
64
64
8
16
MARS
128
128~1248
1
32
RC6
128
0~2048
none
20
Rijndael
128
128~256
1
10,12,14
Serpent
128
128
8
32
Twofish
128
128~256
1
16
加密速度之比較
演算法
加密128bits明文所須之clockcycle
DES
5600
MARS
376
RC6-3220
243
Rijndael
284
Serpent
992
Twofish
258
數據(除DES外)參考自NIST所公布之報告中
攻擊法之比較
差分攻擊法
線性攻擊法
DES(16round)
258
247
MARS
2190
2128
RC6(20round)
2264
2182
Rijndael
2300
2150
Serpent
2120
2240
Twofish
2131
2120
由以上所提供的數據我們可以得知:
最後五個AES候選者無論在效率或安全性來講都能滿足目前有關資訊安全方面的需求。
因此我們可以很確定只要最後AES選出來必定可以滿足未來二十年內有關對稱式加密方面的需求。
4.其他特殊技巧
接下我們將介紹一些在對稱式加密演算法常用到的特殊技巧,我們將其簡略的介紹一下,以便做為參考。
4.1FeistelNetworks
FeistelNetwork的架構於1973年在HorstFeistel所設計的Lucifer加解密演算法中提出,至今已廣泛的運用在大多數加解密演算法的設計原則之中,包含DES、FEAL、GOST、LOKI、CAST-128等知名的加解密演算法,都是採用這個架構。
在Feistelnetwork最基本的架構中(見圖一),每一個輸入的區塊(長度n)被分為左右兩個區塊(長度n/2),在每一個round中,右邊的區塊為下一個round的左區塊,而右邊的區塊經由一個由金鑰值所控制且非線性的函數f運算後,其輸出與左區塊做exclusive-OR所得到的值為下一個round的右邊區塊。
也就是說
Li+1=Ri
Ri+1=Lif(RiKi)
其中函數f是任一個與key相關的對應,通常為非線性的,其定義如下:
f:
{0,1}n/2{0,1}N{0,1}n/2
n為區塊的長度,N為所輸入key的長度。
oneroundKi
Onecycle
Ki+1
oneround
圖一.FeistelNetwork的基本架構
Feistelnetwork的優點是不論函數f是什麼形式,每一個round都是可逆的(reversible)。
這是因為以下式子恆成立:
Lif(RiKi)f(RiKi)=Li
區塊(長度n)經過一個round所得到的兩個區塊(長度n/2)左右位置對調後,再重新做為round的輸入即可得到和原來相同的區塊。
這樣的優點使得採用Feistelnetwork架構的加解密演算法有著加密與解密可使用同一套演算法的好處,這種加解密相同性(“encryption/decryptionsimilarity”)的優點,使得一個加解密演算法在硬體的實作上可以加密與解密使用同一個元件,此便利性對於演算法的推廣是很有幫助的。
4.2S-boxes
在大部分的區塊加密演算法中常常利用S-boxes來執行非線性替換的運算,S-boxes它的輸入和輸出大小是不同的,並且能夠用隨機的方法或是演算法生成。
S-boxes