張琛嶺

(上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240)

一種基于分段式字符集的彩虹表明文生成方式?

張琛嶺

(上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240)

Oechslin提出的彩虹表應(yīng)用時間空間折中思想,是密碼學(xué)中逆轉(zhuǎn)單向函數(shù)的有效工具,但現(xiàn)在廣泛使用的單一字符集彩虹表,在明文位數(shù)較大時,因明文空間的迅速膨脹,消耗計算資源的迅速增加,其應(yīng)用遇到了瓶頸。為此,針對人為口令字符集構(gòu)成特點(diǎn),提出分段式字符集彩虹表明文生成方式,將取自不同字符集的不同位數(shù)明文拼接組成新的明文,可以有效地壓縮明文空間,增加覆蓋的最大明文位數(shù)。對取自CSDN的1000個真實口令哈希進(jìn)行實驗,結(jié)果表明,在原始彩虹表的基礎(chǔ)上,使用分段式字符集彩虹表使恢復(fù)成功率提升39.1%。

單向函數(shù);時間空間折中;彩虹表;真實口令;分段式字符集;哈?；謴?fù)成功率

0 引言

單向函數(shù)的逆轉(zhuǎn)問題是密碼學(xué)中一個重要的研究方向,當(dāng)所針對的明文空間較大時,單純的時間暴力破解或查表破解往往無法滿足要求。1980年Hellman首次提出時間空間折中算法(TMTO)[1],以部分存儲空間為代價,縮減在線破解時間,并將其應(yīng)用于DES的破解。之后Rivest提出可區(qū)分點(diǎn)算法(DP)[2],仍以時間空間折中思想為基礎(chǔ),對Hellman的算法進(jìn)行了一些改動,使得所需查表次數(shù)明顯減少。彩虹表算法是Oechslin于2003年提出的基于時間空間折中思想的算法[3],它的預(yù)計算表在結(jié)構(gòu)上與前兩種算法均不相同,表的數(shù)量很少,但每張表中使用了多個R函數(shù),且鏈長保持一致。Oechslin將其應(yīng)用于PC上Windows口令的破解,并取得了很好的效果。

彩虹表算法在其被提出后的十多年中得到了很好的發(fā)展,在理論上,文獻(xiàn)[4]對完美的經(jīng)典Hellman表、DP表[5]以及彩虹表[3]進(jìn)行了分析,并使用一種基于檢查點(diǎn)(checkpoint)的新技術(shù)[6],通過概率性地排除誤警來進(jìn)一步減小破解時間;Thing和Ying等通過改進(jìn)初始鏈生成方式[7]、排序方法[8]和增加針對字典口令的恢復(fù)方式[9]等來進(jìn)一步優(yōu)化彩虹表;Jin Hong等對彩虹表等時間空間折中算法做了大量計算工作,包括對誤警的分析[10]、對非完美模糊彩虹表的分析[11]以及對多種時間空間折中算法的分析和比較[12,13]。而在工程上,也有很多項目或個人對彩虹表進(jìn)行研究和使用。

近年,GPU運(yùn)算能力發(fā)展迅速,GPGPU廣泛用于密碼學(xué)領(lǐng)域,也包括單向函數(shù)的運(yùn)算,并出現(xiàn)了應(yīng)用于彩虹表的研究[14]和項目。GPU帶來的運(yùn)算性能的提升使得生成針對更大明文空間的彩虹表更為容易,擴(kuò)大了彩虹表的使用范圍,而另一方面,當(dāng)進(jìn)行人為口令哈?；謴?fù)時,我們通過改變明文的生成方式,壓縮長口令明文空間,可以進(jìn)一步提升彩虹表的明文恢復(fù)成功率。

1 分段式字符集彩虹表

1.1 提出

原始的Oechslin彩虹表僅針對單一字符集覆蓋不同長度明文,如選自大小寫字母、數(shù)字以及特殊符號構(gòu)成的字符集的1至8位的明文,其明文空間大小為6161234432565770,即6.16×1015,若生成一張破解成功率約57%左右的彩虹表,以每秒5×108明文的GPU生成速度為例,需要約148天,雖然可以覆蓋全部1至8位的由大小寫字母、數(shù)字以及特殊符號構(gòu)成的明文,但所需計算資源量很大,且覆蓋最長明文位數(shù)僅為8位。

本文提出一種新的分段式字符集明文生成方式,將原始彩虹表的單一字符集明文生成方式擴(kuò)展為多字符集構(gòu)成的分段式明文拼接生成方式,剔除掉人為口令中不常見的隨機(jī)字符明文(如取自由大小寫字母、數(shù)字以及特殊符號構(gòu)成的字符集的8位明文“＠o:＝Ks＾o”),有針對性地生成出現(xiàn)概率更高的明文(如同樣是取自由大小寫字母、數(shù)字以及特殊符號構(gòu)成的字符集的8位明文“Love＠250”),以縮減明文空間。

分段式字符集明文拼接生成方式,是將多段可變長度的由不同字符集的字符構(gòu)成的明文拼接為最終明文的生成方式。如由1位大寫字母、1至3位小寫字母、1位特殊符號以及1至3位數(shù)字構(gòu)成的分段式字符集,可以覆蓋形如“Love＠250”、“Good＆520”、“Abc:123”、“Bug?99”等 8 位及 8 位以內(nèi)明文,而其明文空間大小只有16880098560,即1.69×1010,若生成一張破解成功率約57%左右的彩虹表,同樣以每秒5×108明文的GPU生成速度為例,只需約36秒。

1.2 彩虹鏈生成流程

彩虹表有若干彩虹鏈組成,彩虹鏈由若干彩虹表節(jié)點(diǎn)構(gòu)成,各彩虹表節(jié)點(diǎn)由與明文一一對應(yīng)的序號表示,每一個節(jié)點(diǎn)經(jīng)過“序號轉(zhuǎn)明文”、“明文轉(zhuǎn)哈?！?、“哈希轉(zhuǎn)序號”等三步生成同一條彩虹鏈的下一個節(jié)點(diǎn)(如圖1所示)。其中“明文轉(zhuǎn)哈希”用H表示,即對一個明文字符串進(jìn)行哈希運(yùn)算;“哈希轉(zhuǎn)序號”和“序號轉(zhuǎn)明文”共同構(gòu)成還原函數(shù),用R表示,其中“哈希轉(zhuǎn)序號”截取哈希前64比特,加上當(dāng)前節(jié)點(diǎn)在彩虹鏈的位置序號,再加上彩虹表序號與65536的乘積,最后模明文空間大小,得到節(jié)點(diǎn)序號;而“序號轉(zhuǎn)明文”的過程決定了明文的構(gòu)成方式,包括原始彩虹表明文生成方式和分段式字符集明文生成方式;還原函數(shù)R和哈希函數(shù)H共同構(gòu)成彩虹鏈的生成函數(shù)F＝R°H。

圖1 彩虹鏈生成流程

1.2.1 原始彩虹表明文生成方式

原始彩虹表的明文生成方式主要包括計算明文長度和生成明文兩個部分,過程如下:

0)準(zhǔn)備過程:計算明文空間大小和不同長度明文對應(yīng)最大序號。

準(zhǔn)備過程只在生成彩虹表之前進(jìn)行一次,不屬于明文生成過程。

1)計算明文長度

a)初始化明文長度為最大長度。

b)判斷序號是否屬于該長度所對應(yīng)的序號范圍,如果是,確定明文長度,過程結(jié)束。

c)長度減少1,然后重復(fù)進(jìn)行上一步b),直到確定明文長度。

2)生成明文

a)序號減去與所得長度減1對應(yīng)的最大序號,更新為新的序號。

b)序號模字符集長度,根據(jù)結(jié)果找到字符集中對應(yīng)的字符,拼接至明文。

c)序號除以字符集長度,然后重復(fù)上一步b),直到達(dá)到明文長度。

1.2.2 分段式彩虹表明文生成方式

分段式字符集明文拼接生成方式,在原始彩虹表的明文生成方式基礎(chǔ)之上進(jìn)行了擴(kuò)展,將多段取自不同字符集的明文進(jìn)行拼接(允許多個分段的字符集相同,但相鄰字符集若相同則沒有意義,反而會帶來性能下降,應(yīng)該合并為一個字符集),形成新的明文,總的明文空間大小是各段明文的明文空間大小之積。在開始生成彩虹鏈之前計算總的明文空間大小和各分段明文空間大小。明文生成過程如下:

1)序號模一段明文空間大小,結(jié)果作為原始彩虹表明文生成方式的輸入序號,進(jìn)行原始彩虹表明文生成過程,獲得該段明文。

2)序號除該段明文空間大小,然后按序選擇下一段明文,重復(fù)上一步1),直到生成所有分段的明文。

3)將生成的各段明文按序拼接為最終明文。

1.3 明文空間計算

原始彩虹表只有一段字符集,分別用L、Min和Max表示其字符集大小、最小明文長度和最大明文長度,則其明文空間大小為

分段式字符集彩虹表包括一至多段字符集,分別用Li、Mini和Maxi表示各字符集大小、與各字符集對應(yīng)的最小明文長度和最大明文長度,用n表示段數(shù)。

分段式字符集彩虹表明文空間大小為

2 CSDN真實口令處理能力分析

本文對CSDN真實口令數(shù)據(jù)進(jìn)行明文字符集組成的分析,得到如下結(jié)果。

表1 CSDN真實口令字符集組成統(tǒng)計信息

以真實口令作為數(shù)據(jù),我們分析分段式字符集彩虹表對不同字符集組合的明文處理能力。以比例較大的“小寫字母和數(shù)字”字符集組合方式的明文為數(shù)據(jù),分析分段式字符集彩虹表對明文空間的壓縮情況。將字符集組合方式分為三類:若干位小寫字母連接若干位數(shù)字、若干位數(shù)字連接若干位小寫字母、其他。經(jīng)過對口令的統(tǒng)計分析,三類口令數(shù)量依次為:1680061、378252、226200。明文長度主要分布在15位以內(nèi)(98.4%),最長的為19位。1至15位取自由小寫字母和數(shù)字構(gòu)成的字符集的明文,其明文空間大小為227390317427040025268340,即2.27×1023,這是一個巨大的數(shù)字,以至現(xiàn)有的計算資源幾乎無法針對該位數(shù)范圍的單一字符集生成一張有效的彩虹表(事實上,原始彩虹表在處理11位明文時,已顯得捉襟見肘)。于是我們可以采用分段式字符集構(gòu)成方式縮減明文空間,以擴(kuò)大明文覆蓋范圍。

下面分別計算原始彩虹表(表2)和分段式字符集彩虹表(表3)對CSDN用戶口令中小寫字母和數(shù)字組成的明文的處理能力,并進(jìn)行對比分析,其中以3×106節(jié)點(diǎn)/秒和5×108節(jié)點(diǎn)/秒分別作為CPU和GPU生成彩虹表的估計速率。

表2 原始彩虹表口令處理能力

表3 分段式字符集彩虹表口令處理能力

觀察可知,在較小明文空間大小的情況下(小于1013),分段式字符集彩虹表可以通過選擇明文覆蓋率更高的字符集和位數(shù)組合的方式,以更小的明文空間大小(更少的彩虹表計算資源消耗),達(dá)到更高的命中率(0.13%提高至1.38%,0.27%提高至19.4%,24.18%提高至38.2%);在較大明文空間大小的情況下,分段式字符集彩虹表在消耗的計算資源和命中率方面都不比原始彩虹表差,甚至表現(xiàn)更好,而且更為重要的是,前者可以覆蓋到的明文長度范圍更廣(平均提高了3位),而后者在處理10位以上明文時,則很難生成有效的彩虹表;另外,我們注意到,隨著明文空間大小的增加,無論是原始彩虹表還是分段式字符集彩虹表,生成相應(yīng)有效彩虹表所需的計算資源很快超出可接受范圍,而且命中率增長緩慢,很快達(dá)到極限,這時如果將兩者結(jié)合使用,則可以有效提高命中率,以1015數(shù)量級的明文空間大小達(dá)到近80%命中率。

3 實驗與結(jié)果分析

針對常見的小寫字母和數(shù)字字符集,我們分別生成原始彩虹表和分段式字符集彩虹表,詳細(xì)信息如下表所示。

表4 實驗信息

從6428632個CSDN口令中隨機(jī)挑選1,000個生成SHA1哈希,然后使用以上彩虹表對其進(jìn)行恢復(fù),獲得如下結(jié)果。

表5 實驗結(jié)果

由統(tǒng)計數(shù)據(jù)可知,原始彩虹表與分段式字符集彩虹表相結(jié)合,可以使哈?；謴?fù)成功率由30.4%提升至42.3%,恢復(fù)效果提升39.1%。結(jié)果表明,分段式字符集彩虹表針對人為口令特點(diǎn),可以對明文空間進(jìn)行有效壓縮,擴(kuò)展明文的覆蓋范圍,提高恢復(fù)成功率。

4 結(jié)語

針對原始彩虹表處理較大位數(shù)明文能力不足的問題,本文結(jié)合人為口令字符集構(gòu)成特點(diǎn),提出一種分段式字符集彩虹表明文生成方式,將取自不同字符集的明文拼接為新的明文,以擴(kuò)展可以覆蓋的明文位數(shù)。以CSDN真實口令數(shù)據(jù)為基礎(chǔ),對分段式字符集彩虹表的應(yīng)用進(jìn)行了分析與實驗,結(jié)果表明,分段式字符集彩虹表可以有效壓縮明文空間,在原始彩虹表的基礎(chǔ)上明顯提高口令哈?；謴?fù)成功率。因新的明文生成方式較原始彩虹表復(fù)雜,R函數(shù)在GPU上的執(zhí)行速度有明顯下降,下一步的工作是繼續(xù)優(yōu)化R函數(shù)在GPU上的執(zhí)行過程,以提升彩虹鏈生成速度。

[1] Hellman M E.A cryptanalytic time－memory trade－off[J].Information Theory:IEEE Transactions on,1980,26(4):401－406.

[2] Robling Denning D E.Cryptography and data security[M].Addison－Wesley Longman Publishing Co.Inc..USA:Addison－Wesley,1982:100.

[3] Oechslin P.Making a faster cryptanalytic time－memory tradeoff[M].Advances in Cryptology－CRYPTO.Berlin:Springer Berlin Heidelberg,2003:617－630.

[5] Borst J,Preneel B,Vandewalle J.On the time－memory tradeoff between exhaustive key search and table precomputation[C]//Symposium on Information Theory in the Benelux.Veldhoven(NL):TECHNISCHE UNIVERSITEIT DELFT,1998:111－118.

[6] Avoine G,Junod P,Oechslin P.Time－memory trade－offs:False alarm detection using checkpoints[M].Progress in Cryptology－INDOCRYPT.2005.Berlin:Springer Berlin Heidelberg,2005:183－196.

[8] Ying H M,Thing V LL.A novel rainbow table sorting method[C]//The Second International Conference on Technical and Legal Aspects of the e－Society.Gosier,Guadeloupe,France:CYBERLAWS,2011:35－40.

[9] Thing V LL,Ying H M.Enhanced Dictionary Based Rainbow Table[M]//Information Security and Privacy Research.Berlin:Springer Berlin Heidelberg,2012:513－524.

[11] Kim B I,Hong J.Analysis of the non－perfect table fuzzy rainbow tradeoff[C]//Information Security and Privacy.Berlin:Springer Berlin Heidelberg,2013:347－362.

[13] Lee G W,Hong J.A Comparison of Perfect Table Cryptanalytic TradeoffAlgorithms[J].IACR Cryptology ePrint Archive,2012:540－540.

[14] Kim JW,Seo J,Hong J,Park K,Kim SR.High－speed parallel implementations of the rainbow method in a heterogeneous system[J].INDOCRYPT,2012:303–316.

A Rainbow－Table Plain Generation Method based on Segmented Charset

ZHANG Chen－ling
(School of Electronic Information and Electrical Engineering,SJTU,Shanghai 200240,China)

TMTO(Time Memory Trade Off)－based rainbow table method,proposed by Oechslin,is a useful one－way function reversing method in cryptography.However,the world widely used original rainbow table method,which uses a single charset,could not be applied efficiently when dealing with a long plain due to the lack of computing resource and the significant increase of plain space.In considering the character of human passwords constitution,a new plain generation method based on segmented charset is introduced,which splices the plains from different charsets and forms a new plain.This method could effectively reduce the plain space and increase the max plain length the rainbow table is able to cover.The experiment recovering 1000 hashes corresponding to plains taken from the revealed CSDN password library indicates that the rainbow－table plain generation method based on segmented charset could raise the success rate of hash recovering by 39.1%when used in combination of the original rainbow table method.

one－way function,time－memory tradeoff,rainbow table,human password,segmented charset,success rate of hash recovering

TP309－7

A

1009－8054(2015)01－0099－04

2014－08－25

上海市科委計劃項目(No.13JG0500400)

張琛嶺(1990—),男,碩士研究生,主要研究方向為密碼學(xué)?！?/p>