張琛嶺

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

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

張琛嶺

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

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

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

0 引言

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

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

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

1 分段式字符集彩虹表

1.1 提出

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

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

分段式字符集明文拼接生成方式,是將多段可變長(zhǎng)度的由不同字符集的字符構(gòu)成的明文拼接為最終明文的生成方式。如由1位大寫(xiě)字母、1至3位小寫(xiě)字母、1位特殊符號(hào)以及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)由與明文一一對(duì)應(yīng)的序號(hào)表示,每一個(gè)節(jié)點(diǎn)經(jīng)過(guò)“序號(hào)轉(zhuǎn)明文”、“明文轉(zhuǎn)哈?！?、“哈希轉(zhuǎn)序號(hào)”等三步生成同一條彩虹鏈的下一個(gè)節(jié)點(diǎn)(如圖1所示)。其中“明文轉(zhuǎn)哈?！庇肏表示,即對(duì)一個(gè)明文字符串進(jìn)行哈希運(yùn)算;“哈希轉(zhuǎn)序號(hào)”和“序號(hào)轉(zhuǎn)明文”共同構(gòu)成還原函數(shù),用R表示,其中“哈希轉(zhuǎn)序號(hào)”截取哈希前64比特,加上當(dāng)前節(jié)點(diǎn)在彩虹鏈的位置序號(hào),再加上彩虹表序號(hào)與65536的乘積,最后模明文空間大小,得到節(jié)點(diǎn)序號(hào);而“序號(hào)轉(zhuǎn)明文”的過(guò)程決定了明文的構(gòu)成方式,包括原始彩虹表明文生成方式和分段式字符集明文生成方式;還原函數(shù)R和哈希函數(shù)H共同構(gòu)成彩虹鏈的生成函數(shù)F＝R°H。

圖1 彩虹鏈生成流程

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

原始彩虹表的明文生成方式主要包括計(jì)算明文長(zhǎng)度和生成明文兩個(gè)部分,過(guò)程如下:

0)準(zhǔn)備過(guò)程:計(jì)算明文空間大小和不同長(zhǎng)度明文對(duì)應(yīng)最大序號(hào)。

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

1)計(jì)算明文長(zhǎng)度

a)初始化明文長(zhǎng)度為最大長(zhǎng)度。

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

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

2)生成明文

a)序號(hào)減去與所得長(zhǎng)度減1對(duì)應(yīng)的最大序號(hào),更新為新的序號(hào)。

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

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

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

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

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

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

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

1.3 明文空間計(jì)算

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

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

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

2 CSDN真實(shí)口令處理能力分析

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

表4 實(shí)驗(yàn)信息

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

表5 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語(yǔ)

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

[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

上海市科委計(jì)劃項(xiàng)目(No.13JG0500400)

張琛嶺(1990—),男,碩士研究生,主要研究方向?yàn)槊艽a學(xué)?！?/p>