基于彩虹表技術(shù)的分布式密碼破解研究

王偉兵, 文伯聰

(廣東警官學(xué)院計(jì)算機(jī)系, 廣東廣州 510230)

基于彩虹表技術(shù)的分布式密碼破解研究

王偉兵, 文伯聰

(廣東警官學(xué)院計(jì)算機(jī)系, 廣東廣州 510230)

在打擊計(jì)算機(jī)類型的犯罪過程中，為了獲得偵查線索或者證明案情的電子證據(jù)，經(jīng)常需要通過技術(shù)手段破解犯罪嫌疑人計(jì)算機(jī)中的各種密碼。本文研究了彩虹表的基本原理以及常用操作系統(tǒng)的密碼加密流程，提出了利用MPI分布式編程模型構(gòu)造彩虹表以及基于彩虹表破解密碼的方法。實(shí)驗(yàn)表明，這些方法是有效的，可以滿足偵查實(shí)戰(zhàn)的需要。

彩虹表； 密碼破解； MPI； 電子取證； 分布式

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，利用計(jì)算機(jī)及其網(wǎng)絡(luò)進(jìn)行計(jì)算機(jī)犯罪的問題越來越嚴(yán)重。在這類案件的偵破過程中，為了獲得偵查線索或者提取用于證明犯罪事實(shí)的電子證據(jù)，往往需要在犯罪嫌疑人的計(jì)算機(jī)中查看有關(guān)文件。在通過口供無法獲得密碼的情況下，登錄涉案計(jì)算機(jī)或者打開涉案文件，是非常困難的。這種情況下，密碼破解技術(shù)可能就成了唯一的選擇。

無論是理論還是實(shí)踐中，直接破解密碼算法幾乎是不可能的。所以通常情況下，破解密碼往往采用窮舉法或查表法。使用窮舉法破解每一個(gè)密碼時(shí)，都要遍歷密碼明文空間中的每一個(gè)密碼，對(duì)每一個(gè)密碼都要計(jì)算加密后的結(jié)果，然后和存儲(chǔ)在計(jì)算機(jī)或文檔中的密文進(jìn)行對(duì)比。這種方法破解密碼所需時(shí)間非常長(zhǎng)，沒有實(shí)用價(jià)值。而查表法剛好相反，先把密碼明文空間中的所有密碼的密文計(jì)算一遍，將計(jì)算結(jié)果以線性表的形式存儲(chǔ)起來。密碼破解時(shí)，以需要破解的密文為關(guān)鍵字，在預(yù)先計(jì)算并存儲(chǔ)的線性表中查找比對(duì)。這種方式破解密碼的速度比窮舉法快，但是需要非常海量的存儲(chǔ)空間，在實(shí)際辦案工作中幾乎沒有這樣的資源。而Hellman和Oechslin等人提出的時(shí)空折中算法(彩虹表法)，則在破解時(shí)間和存儲(chǔ)空間兩個(gè)維度上折中，在滿足破解速度要求的前提下，大大降低對(duì)存儲(chǔ)空間的要求，因此是一種能滿足實(shí)戰(zhàn)需求的實(shí)用性方法。

本文在經(jīng)典彩虹表的算法基礎(chǔ)上，提出構(gòu)造分布式完美彩虹表的思路，通過MPI并行編程接口，將彩虹表分布存儲(chǔ)于集群中的每臺(tái)計(jì)算機(jī)中。在破解階段，通過集群中的多臺(tái)計(jì)算機(jī)并行計(jì)算，可大大加快和提高密碼破解的速度和有效率。

1 彩虹表算法分析

1.1 概念提出

無論是操作系統(tǒng)的登錄密碼，還是文檔資料的打開密碼，通常都是采用單向散列函數(shù)(Hash函數(shù))處理后存儲(chǔ)。在單向散列算法中，對(duì)于某個(gè)明文P(明文有N種可能性)，使用單向散列函數(shù)H計(jì)算，得到固定長(zhǎng)度的散列值C(密文)，記作：

C=H(P)

采用查表法破解密碼的過程是：首先遍歷整個(gè)密碼明文空間中的每個(gè)密碼，對(duì)每個(gè)密碼按照上述函數(shù)計(jì)算密文(散列值)，然后將所有的密文排序并連同明文一起存儲(chǔ)成一張線性表。破解密碼時(shí)，首先要拿到該密碼的密文，然后使用折半查找法在該線性表中查找比對(duì)，進(jìn)而獲得密碼明文。這個(gè)過程中，查找比對(duì)次數(shù)不超過log2N，哈希計(jì)算次數(shù)為N，預(yù)先計(jì)算存儲(chǔ)的線性表可重復(fù)使用。但是由于明文空間尺寸N非常巨大，這個(gè)預(yù)處理表的占用的存儲(chǔ)空間將非常大。

Hellman在1980年提出采用時(shí)空折中的思想破解DES算法的密鑰。Oechslin于2013年發(fā)表論文提出了對(duì)經(jīng)典方法的改進(jìn)，大大提高了密碼破解的速度。改進(jìn)后的方法稱為彩虹表法。

彩虹表方法的核心思想是一系列簡(jiǎn)化函數(shù)(R1,R2,R3,…,Rk)，每個(gè)簡(jiǎn)化函數(shù)的功能是將一個(gè)密文映射為明文空間中的一個(gè)密碼。在彩虹表構(gòu)造階段，先從一個(gè)明文P0開始，計(jì)算哈希函數(shù)H(P0)，得到密文C1后，再使用化簡(jiǎn)函數(shù)R1(C1)，計(jì)算出另一明文P1，然后重復(fù)使用哈希函數(shù)H和簡(jiǎn)化函數(shù)R進(jìn)行計(jì)算，就生成了一條密碼明文與密文交替出現(xiàn)的鏈：

這種預(yù)計(jì)算出來的鏈結(jié)構(gòu)就稱為彩虹鏈，多條彩虹鏈組成的預(yù)計(jì)算表稱之為彩虹表。

1.2 構(gòu)造彩虹表

在彩虹表構(gòu)造階段，首先從密碼的明文空間中隨機(jī)選擇s個(gè)明文{P1,0,P2,0,…,Ps,0}作為計(jì)算起點(diǎn)，然后按下列方式依次計(jì)算，形成s條彩虹鏈：

其中s和k是彩虹表方法的參數(shù)，不同的參數(shù)值決定了彩虹表的構(gòu)造時(shí)間和所占存儲(chǔ)空間，也決定了基于此彩虹表破解密碼的時(shí)間。為了減少存儲(chǔ)空間，不需要保存彩虹鏈中間各個(gè)結(jié)點(diǎn)，只存儲(chǔ)每條彩虹鏈的鏈?zhǔn)缀玩溛步M成的記錄，并按鏈尾進(jìn)行排序。

1.3 破解過程

彩虹表構(gòu)造完成并存儲(chǔ)后，就可依此表破解密碼了。對(duì)于已知的某個(gè)密文C，想要找到對(duì)應(yīng)的明文P，過程如下：

(1)首先使用簡(jiǎn)約函數(shù)Rk(C)計(jì)算出Pk，用Pk作為關(guān)鍵字在彩虹表中存儲(chǔ)的所有鏈尾構(gòu)成的線性表中進(jìn)行折半查找，如果匹配到對(duì)應(yīng)鏈尾，則從該彩虹鏈的鏈?zhǔn)字匦掠?jì)算整條彩虹鏈，計(jì)算出Ck后，比較Ck和C，如果相等則表明上一步的計(jì)算結(jié)果Pk-1就是密文C對(duì)應(yīng)的明文，如果不相等，就稱為一次誤警。

(2)如果Pk在彩虹表中的所有鏈尾上折半查找不成功，則認(rèn)為明文不可能出現(xiàn)在Pk-1的位置上。于是對(duì)密文C進(jìn)行Rk-1(H(Rk-2(C)))函數(shù)運(yùn)算，用計(jì)算結(jié)果在彩虹表中的所有鏈尾結(jié)點(diǎn)中進(jìn)行二分查找。查找結(jié)果的處理與(1)相同，若查找成功，從鏈?zhǔn)子?jì)算時(shí)只需計(jì)算至Ck-1位置即可與密文C進(jìn)行比較。

(3)依次類推，直至破解成功。若所有k步操作完成后，仍沒有比對(duì)成功，則說明破解失敗。

1.4 性能分析

相對(duì)于散列函數(shù)H的計(jì)算復(fù)雜度，簡(jiǎn)約函數(shù)R的計(jì)算通常非常簡(jiǎn)單，基于鏈長(zhǎng)為k，條數(shù)為s的彩虹表，破解一個(gè)密碼時(shí)的性能計(jì)算如下：

多張彩虹表破解成功率=1-(1-T)t，其中T為使用單張彩虹表的破解成功率，t為彩虹表的張數(shù)。

隨著t的增大，1-(1-T)t>T，由此可見，采用多張彩虹表可以提高密碼破解的成功率，當(dāng)然，這需要花費(fèi)更多的時(shí)間和存儲(chǔ)空間構(gòu)造彩虹表。

2 分布式計(jì)算

為了獲得更高的破解成功率和更快的破解速度，需要較快地構(gòu)造多張尺寸更大的的彩虹表，以及更快的Hash函數(shù)計(jì)算速度和二分查找速度。這對(duì)計(jì)算機(jī)的處理能力要求非常高，僅依賴于單臺(tái)計(jì)算機(jī)(處理器可能是多核)計(jì)算速度的提高，遠(yuǎn)遠(yuǎn)達(dá)不到辦案實(shí)戰(zhàn)的要求。因此需要尋求一種利用現(xiàn)有的資源高效完成復(fù)雜任務(wù)的方法。一種有效的辦法是通過高速網(wǎng)絡(luò)，將多臺(tái)計(jì)算機(jī)連接起來協(xié)同工作，并行地構(gòu)造多張彩虹表，并分布式存儲(chǔ)于每臺(tái)計(jì)算機(jī)中，在破解階段，多臺(tái)計(jì)算機(jī)并行工作，就可高效快速地完成密碼破解任務(wù)。

2.1 為什么選擇MPI

MPI(Message Passing Interface)是一種并行程序編程模型，可基于消息傳遞機(jī)制開發(fā)并行程序。MPI提供一系列消息傳遞的函數(shù)庫，這些函數(shù)庫與具體的語言無關(guān)，編程者在使用時(shí)可與具體的編程語言綁定，例如C語言、C++語言和FORTRAN語言。也就是說，只要編程者熟悉這些語言中的任一種，就可以很快掌握MPI編程，而且對(duì)于原來用這些語言編寫的程序，只要稍加修改，調(diào)用個(gè)別用于并行控制的函數(shù)，就能輕松實(shí)現(xiàn)原有程序的并行化。

除過MPI之外，Hadoop Map/Reduce也是一種非常流行的并行編程模型。Map/Reduce使用簡(jiǎn)單，以一種可靠、高容錯(cuò)的方式并行處理上T級(jí)別的數(shù)據(jù)集，但只適合特定任務(wù)的并行處理，而且使用不靈活。而彩虹表的構(gòu)造以及根據(jù)彩虹表破解密碼，需要大量的計(jì)算，不僅要解決數(shù)據(jù)并行的問題，更要實(shí)現(xiàn)并行計(jì)算，使用Map/Reduce編程模型，效率和速度無法滿足要求。

而MPI并行編程模型以消息傳遞為基礎(chǔ)，相對(duì)于Map/Reduce而言，雖然編程難度較大，但并行控制方式更靈活，適合那些用數(shù)據(jù)并行方法很難實(shí)現(xiàn)或者實(shí)現(xiàn)代價(jià)很高的并行算法。MPI使用的消息傳遞方式既適用于共享存儲(chǔ)多處理機(jī)，也可適用于分布式存儲(chǔ)多處理機(jī)。將多臺(tái)具有多核處理器的計(jì)算機(jī)高速連接起來的集群，既有分布式內(nèi)存，又有共享式內(nèi)存。這種架構(gòu)的集群，采用MPI編程模型對(duì)處理彩虹表密碼破解這類數(shù)據(jù)量和計(jì)算量都非常大的情況非常有效。

2.2 并行程序框架設(shè)計(jì)

在MPI并行程序設(shè)計(jì)中, 計(jì)算任務(wù)需要提前分割成若干個(gè)子任務(wù)， 然后將它們分配到各個(gè)節(jié)點(diǎn)的計(jì)算機(jī)上去執(zhí)行。執(zhí)行過程中，各個(gè)子任務(wù)之間為了協(xié)調(diào)工作需要進(jìn)行通信。子任務(wù)的劃分要根據(jù)具體情況調(diào)整，以便保持負(fù)載平衡, 減少通信開銷以提高執(zhí)行效率。MPI支持主從模式和對(duì)等模式，這兩種模式分別適用于不同類型的并行計(jì)算任務(wù)。

主從模式中, 需要設(shè)計(jì)一個(gè)主進(jìn)程負(fù)責(zé)任務(wù)的劃分、分派及計(jì)算結(jié)果的收集和歸并，并負(fù)責(zé)所有從進(jìn)程間的網(wǎng)絡(luò)調(diào)度和協(xié)調(diào)。而從進(jìn)程則負(fù)責(zé)接收子任務(wù)、完成計(jì)算和結(jié)果的發(fā)送。無論是彩虹表的構(gòu)造，還是基于彩虹表進(jìn)行密碼破解，在每臺(tái)計(jì)算機(jī)上執(zhí)行的程序都是相同的，各進(jìn)程之間不需要傳輸大量的數(shù)據(jù)，只需要交換消息即可。顯然，彩虹表的構(gòu)造不適合這種主從模式。

對(duì)等模式又稱為SPMD(Single Program，Multiple Data)模式。在這種模式下，所有進(jìn)程不分主從，地位相等，均執(zhí)行同一個(gè)程序，但處理不同的數(shù)據(jù)。這非常適合分布式彩虹表構(gòu)造和基于彩虹表進(jìn)行密碼破解，每個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行相同的程序，但是產(chǎn)生不同的彩虹表，其數(shù)據(jù)分布式存儲(chǔ)在各自的節(jié)點(diǎn)上。在破解階段，每個(gè)節(jié)點(diǎn)查找各自的彩虹表數(shù)據(jù)。這樣節(jié)點(diǎn)之間不需要大量彩虹表數(shù)據(jù)的傳輸，只需要傳遞少量的消息，通信開銷小?；趯?duì)等模式的彩虹表構(gòu)造程序基本框架如圖1所示，密碼破解程序的基本框架如圖2所示。

圖1 彩虹表構(gòu)造框圖

圖2 密碼破解框圖

在密碼破解過程中，只要任意進(jìn)程破解成功，則表示破解任務(wù)完成，這時(shí)該進(jìn)程給其他各進(jìn)程發(fā)送消息，其他各進(jìn)程收到消息后立即停止各自的工作，整個(gè)任務(wù)完成。只有每個(gè)進(jìn)程都破解失敗，才表示任務(wù)失敗。

彩虹表是按進(jìn)程分布存放在每臺(tái)計(jì)算機(jī)上，每臺(tái)計(jì)算機(jī)都可能存儲(chǔ)多張彩虹表。每個(gè)彩虹表構(gòu)造時(shí)使用的簡(jiǎn)約函數(shù)系列均不相同，這是減少彩虹表碰撞而產(chǎn)生誤警的關(guān)鍵。密碼破解時(shí)使用的簡(jiǎn)約函數(shù)系列要與彩虹表構(gòu)造時(shí)使用的簡(jiǎn)約函數(shù)一致，否則會(huì)出現(xiàn)錯(cuò)誤。

3 密碼加密流程分析

在利用彩虹表方法破解密碼之前，首先需要對(duì)密碼的加密方式和流程分析清楚才能正確地構(gòu)造彩虹表，并基于構(gòu)造的彩虹表完成破解密碼工作。下面以Windows操作系統(tǒng)和Linux操作系統(tǒng)為例，說明常用操作系統(tǒng)密碼加密以及存儲(chǔ)方式。

3.1 Windows密碼加密分析

在Windows操作系統(tǒng)中，用戶設(shè)定或修改密碼時(shí)，系統(tǒng)先計(jì)算密碼的哈希值，然后將該哈希值存儲(chǔ)在安全賬號(hào)管理器SAM(Security Account Manager)中。系統(tǒng)采用的哈希算法是LM(Lan Manager)和NTLM(NT Lan Manager)。LM算法的流程如圖3所示，NTLM算法的計(jì)算流程如圖4所示。

圖3 LM算法流程

圖4 NTLM算法流程

在Windows XP中，通過工具QuarksPwDump得到SAM中的密碼哈希值為Administrator:500:25095F8EBC4E5DA67B5219BCA4D8709F:2C8D34DED13A284801B697B2C19028A2:::。其中“Administrator”是用戶名，“500”是用戶ID，“25095F8EBC4E5DA67B5219BCA4D8709F”是該用戶的密碼通過LM哈希計(jì)算后的值，“2C8D34DED13 A284801B697B2C19028A2” 是該用戶的密碼通過NTLM哈希計(jì)算后的值，兩個(gè)哈希值均以十六進(jìn)制字符串表示。

但是在Windows7操作系統(tǒng)中，通過工具QuarksPwDump提取到的超級(jí)管理員用戶的密碼哈希值為Administrator:500:AAD3B435B51404EEAAD3B4 35B51404EE:2C8D34DED13A284801B697B2C190 28A2:::。其中“AAD3B435B51404EEAAD3B435B5 1404EE”是用“0000000000000000”作為密鑰對(duì)魔幻字符串“KGS!@#$%KGS!@#$%”進(jìn)行DES加密的結(jié)果，“2C8D34DED13A284801B697B2C190 28A2” 則是該用戶的密碼通過NTLM哈希計(jì)算后的值。

3.2 Linux密碼加密分析

在Linux操作系統(tǒng)中，每個(gè)用戶登錄密碼的哈希值記錄在文件/etc/shadow中，該文件的每一行對(duì)應(yīng)一個(gè)用戶，每行內(nèi)容分為若干個(gè)字段，內(nèi)容與含義為：

用戶名:登錄密碼的哈希值:最后一次修改時(shí)間:最小時(shí)間間隔:最大時(shí)間間隔:警告時(shí)間:不活動(dòng)時(shí)間:失效時(shí)間:標(biāo)志。一個(gè)具體的例子如下所示：

root:$6$9lovYHZM$fDVrlQ.etYY/xrF3Hc-AShGVfRKwshcfbZXp3yv3ueHoAFHtfS3nNNuUCxgLz-errzbG9rJtci8vzz8I5h7D.5U1:17193:0:99999:7:::

其中第二個(gè)字段“$6$9lovYHZM$fDVrlQ.etYY/xrF3HcAShGVfRKwshcfbZXp3yv3ueHoAFHtfS-3nNNuUCxgLzerrzbG9rJtci8vzz8I5h7D.5U1”就是root用戶登錄密碼的哈希值。分析該哈希值的產(chǎn)生過程，對(duì)密碼破解非常重要。該字段格式為$id$salt$encrypted，每個(gè)部分的含義如下：

id表示使用的哈希算法，可能的取值如表1所示。

表1 Linux登錄密碼的各種哈希算法

salt是使用各種哈希算法進(jìn)行計(jì)算時(shí)的一個(gè)干擾字符串，在生成或修改登錄密碼時(shí)由系統(tǒng)隨機(jī)產(chǎn)生。

encrypted即是對(duì)密碼進(jìn)行哈希計(jì)算的結(jié)果，但不是直接對(duì)登錄密碼進(jìn)行哈希計(jì)算，而是對(duì)登錄密碼和salt進(jìn)行混合，再進(jìn)行多次哈希函數(shù)計(jì)算，然后再經(jīng)過base64編碼的結(jié)果。

分析Linux源碼可知，具體的哈希計(jì)算由函數(shù)char *crypt(const char *key, const char *salt)完成，該函數(shù)的第一個(gè)參數(shù)就是用戶設(shè)定的密碼，第二個(gè)參數(shù)salt是由另一個(gè)函數(shù)char *crypt_make_salt (const char *meth, void *arg) 生成，參數(shù)meth就是哈希算法名稱，使用不同的哈希算法作為參數(shù)，該函數(shù)生成不同長(zhǎng)度的隨機(jī)串。

針對(duì)Linux這種帶salt的的密碼破解問題，構(gòu)造彩虹鏈的構(gòu)造流程要調(diào)整，過程如下所示：

其中P0為隨機(jī)產(chǎn)生的明文空間中的某個(gè)密碼，S0可使用Linux源代碼中函數(shù)crypt_make_salt生成，H可以直接使用Linux源代碼中的函數(shù)crypt。R函數(shù)則負(fù)責(zé)負(fù)責(zé)從crypt函數(shù)的輸出中分離出新的明文密碼和salt串。利用彩虹表破解密碼時(shí)，函數(shù)形式相應(yīng)調(diào)整即可。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 可行性測(cè)試

實(shí)驗(yàn)集群環(huán)境由15臺(tái)Dell服務(wù)器搭建，節(jié)點(diǎn)機(jī)器配置如下: CPU: Xeon E5-2620*2；內(nèi)存：48 GB；硬盤：500 GB；以太網(wǎng)卡：1 000 Mb/s 全雙工；操作系統(tǒng): CentOS6.8 Linux。

實(shí)驗(yàn)是針對(duì)目前在偵查實(shí)戰(zhàn)中最常見的Windows7操作系統(tǒng)的密碼破解任務(wù)而設(shè)計(jì)的。Windows7操作系統(tǒng)用戶登錄密碼的加密算法是NTLM，明文由最長(zhǎng)128個(gè)任意字符組成?？紤]到實(shí)際案件中的需要，密碼空間中的字符串遵循以下規(guī)則：

(1) 密碼長(zhǎng)度不超過8個(gè)字符；

(2) 密碼字符只包括小寫字母、大寫字母和阿拉伯?dāng)?shù)字；

因此，密碼空間的大小為：

N=62+622+623+…+628≈2.219×1014

在彩虹表構(gòu)造階段，設(shè)計(jì)每條彩虹鏈長(zhǎng)度為1 000 000，每條彩虹鏈存儲(chǔ)包括鏈?zhǔn)缀玩溛膊怀^30個(gè)字節(jié)的數(shù)據(jù)。為了涵蓋所有密碼空間中的密碼，則總的彩虹表大小為：

M=2.219×1014÷1 000 000×30≈6.2G

集群中共有15臺(tái)機(jī)器，每臺(tái)機(jī)器上啟動(dòng)24個(gè)進(jìn)程，共360個(gè)進(jìn)程，每個(gè)進(jìn)程負(fù)責(zé)產(chǎn)生一個(gè)17.6 M的彩虹表，每臺(tái)機(jī)器上的彩虹表尺寸大約423 M。

經(jīng)過實(shí)驗(yàn)測(cè)試，按照以上設(shè)計(jì)，完成彩虹表的構(gòu)造大約需要45小時(shí)?；谶@樣的彩虹表，給定100個(gè)任意密碼的NTLM散列值，平均每個(gè)密碼破解時(shí)間<1分鐘。

4.2 對(duì)比測(cè)試

針對(duì)現(xiàn)有實(shí)驗(yàn)條件，設(shè)計(jì)不同大小的密碼空間進(jìn)行比對(duì)。集群中有15臺(tái)機(jī)器，每臺(tái)機(jī)器上啟動(dòng)24個(gè)進(jìn)程。需要構(gòu)造的彩虹表總尺寸和預(yù)計(jì)構(gòu)造時(shí)間如表2所示。

按照以上設(shè)計(jì)，在集群中啟動(dòng)程序，構(gòu)造彩虹表以及基于彩虹表破解100個(gè)任意密碼的平均時(shí)間如圖5和圖6所示。

由實(shí)驗(yàn)結(jié)果可知，隨著密碼限長(zhǎng)以及構(gòu)成密碼的字符種類增多，密碼空間的大小呈指數(shù)增長(zhǎng)，構(gòu)造彩虹表的空間成本和時(shí)間成本也呈指數(shù)增長(zhǎng)，這就需要投入更大成本增加更多的計(jì)算結(jié)點(diǎn)。

表2 不同密碼限長(zhǎng)所需構(gòu)造的彩虹表尺寸

圖5 不同密碼限長(zhǎng)時(shí)彩虹表構(gòu)造時(shí)間

圖6 不同密碼限長(zhǎng)時(shí)平均破解時(shí)間

一旦彩虹表構(gòu)造完成，破解密碼所花時(shí)間隨密碼限長(zhǎng)的增加而線性增加。分析原因，雖然彩虹表的尺寸隨密碼限長(zhǎng)的增加呈指數(shù)增加，但是彩虹鏈的長(zhǎng)度保持不變，破解密碼時(shí)所需要進(jìn)行哈希運(yùn)算的次數(shù)不變，只是增加了待查詢的彩虹表中所有鏈尾所構(gòu)成的線性表長(zhǎng)度。但是由于采用的是二分查找，查找所需時(shí)間隨彩虹表的長(zhǎng)度增加而呈對(duì)數(shù)增加，所以總的破解時(shí)間增加的很慢。

5 結(jié)束語

本文首先分析了彩虹表的基本原理，包括彩虹表的構(gòu)造方法和基于彩虹表破解密碼的方法，研究了常見操作系統(tǒng)登錄密碼的加密流程。根據(jù)這些研究結(jié)果，提出了利用MPI分布式編程模型實(shí)現(xiàn)構(gòu)造彩虹表以及基于此彩虹表破解密碼的過程。通過實(shí)際編程實(shí)驗(yàn)表明，這些方法是有效的，能滿足實(shí)際工作需要。

下一步將重點(diǎn)研究以下幾個(gè)問題：彩虹表的存儲(chǔ)模式，探討使用Redis緩存服務(wù)器存儲(chǔ)彩虹表，在內(nèi)存中查找彩虹表，進(jìn)一步加快破解速度；優(yōu)化簡(jiǎn)化函數(shù)系列的設(shè)計(jì)，盡量減少誤警率；研究彩虹表的大小和彩虹鏈的長(zhǎng)度對(duì)破解速度的影響，找出最優(yōu)或次優(yōu)參數(shù)。

[1] HELLMAN M. A cryptanalytic time-memory trade off[J]. IEEE Transactionson Information Theory, 1980,26(4):401-406.

[2] OECHSLIN P. Making a Faster Cryptanalytic Time-Memory Trade-Off[J]. Lecture Notes in Computer Science, 2003,2729(4): 617-630.

[3] BORST J, PRENEEL B, VANDEWALLE J. On time-memory trade off between exhaustive key search and table precomputation[C]. Symposium on Information Theory in the Benelux,1998:111-118.

[4] 李昕,曹天杰,米國(guó)粹,等. 基于分布式環(huán)境下的彩虹表密碼攻擊[J]. 計(jì)算機(jī)應(yīng)用與軟件,2011(2):290-293.

[5] 李永達(dá),王黨輝,黃小平. 采用GPU的ZIP密碼恢復(fù)算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2015,51(2):190-193.

[6] 仇李寅. 基于的擴(kuò)展彩虹表生成研究[D]. 上海:上海交通大學(xué),2011.

[7] 陳國(guó)良,安虹,陳嶙,等. 并行算法實(shí)踐[M]. 北京:高等教育出版社,2004.

[8] Windows LM/NTLM HASH加密及獲取工具. http:∥blog.csdn.net/gscaiyucheng/article/details/9151257.

(責(zé)任編輯 于瑞華)

王偉兵(1977—),男,陜西歧山人，碩士，講師。研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)攻防與電子取證。

TP309.7