摘 要：當前網絡犯罪越來越嚴重，破解犯罪嫌疑人計算機中的的密碼信息則需要技術支持。文章研究了彩虹表的構造原理、破解密碼口令的過程，并結合MIC眾核協處理器強大的計算能力，設計實現了密碼口令破解彩虹表查找系統，并行化的設計提高了彩虹表的生成速度，歸約函數的設計提高了明文查找成功率。

　　關鍵詞：密碼破解;彩虹表;眾核協處理器;并行化

　　1 引言

　　哈希算法可以將任意長度的二進制值串通過一定的映射規則映射為固定長度的二進制值串。被廣泛應用于密碼學領域。對于一個優秀的哈希算法需要具備三個特點：(1)單向性—通過哈希值無法反向推到出原始數據;(2)對輸入數據極其敏感—兩個即使只有1bit差異的輸入數據，其對應的散列值會有很大的不同;(3)碰撞幾率極小—如果兩個散列值不同，那么其對應的原始數據也是不相同的。哈希算法有非常多的應用，比如安全加密、唯一標識、數據校驗、分布式存儲等。

　　窮舉法和查表法通常被用于破解哈希函數。窮舉法，顧名思義，就是需要將所有可能的結果進行列舉，具體地說，遍歷明文空間，然后使用哈希算法求出明文空間中的每一個密碼的哈希值，最后將哈希值與密文進行比對，其計算量非常大，破解密碼口令的時間非常久。查表法是從預先保存好的明文組合與哈希值的映射中，通過密文查找對應的明文來破解密碼口令。雖然查表法的破解速度高于窮舉法，但其對存儲空間的要求極大。結合窮舉法和查表法存在的特點，Hellman[1]和Oechslin[2]等人提出了彩虹表(Rainbow Table)，這種方法既保證了密碼口令的破解速度，又降低了存儲空間，是一種實用且有效的技術。為有效且高效地破解密碼口令，本文提出了彩虹表查找系統的設計與實現方案。

　　2 相關工作

　　Hellman于1980年首次提出了基于時空權衡(Time-Memory Trade-Off，TMTO)的表方法。這種方法分為兩個階段，即預計算階段和在線階段。為了建立密文空間與明文空間的映射，引入了可以用于交替地計算明文和密文的規約函數從而形成一個鏈表，鏈表的首節點和末尾節點被記錄存儲，而大量的首節點-末尾節點又組成了一張表，但由于規約函數與密文-明文映射非一一對應，會導致哈希碰撞問題的出現[1]。Rivest于1982年改進了Hellman的方法，為了降低鏈的重合率，他引入了區分點(Distinguished Points)[3]。Oechslin于2003年，在Hellman的方法的基礎上提出了彩虹表(Rainbow Table)，他將Hellman方法中每次計算都使用相同的規約函數，改為每次計算時采用不同的規約函數，顯著地降低了鏈的重合率[2]。2009年Thing在彩虹表的基礎上，改進了TMTO方法，將存儲首節點和末尾節點改為只存儲末尾節點值，通過相應的數學運算來獲得首節點，因此減少了表的存儲空間[4]。2012年，梁艷等人提出了基于生成元的彩虹表，該方法根據常用的口令設置方法減少長口令的生成空間過濾掉不滿足要求的口令，從而降低了表的存儲空間[5]。2015年張悅等人設計了基于HBase的彩虹表MD5哈希密碼解密系統，其引入Map/Reduce框架與HBase，為完成計算與存儲，MD5彩虹表的生成和查找分配給集群節點，并使用HBase實現彩虹表的存儲，明顯地提高了彩虹表的生成速度和破解密碼的效率[6]。2017年王偉兵等人在經典彩虹表的算法基礎上，提出了構造分布式完美彩虹表的思路，通過MPI了并行編程接口，將彩虹表分布存儲于集群中的每臺計算機中。在破解階段，通過集群中的多臺計算機并行計算，可以明顯地加快和提高密碼破解的速度和有效率[7]。

　　3 彩虹表算法

　　彩虹表(Rainbow Table)技術可以理解成一種針對哈希算法的破解技術。其核心思想是按一定的規則將密文映射為明文空間中的口令，這個規則稱之為歸約函數()。

　　3.1 彩虹表的生成

　　在彩虹表的構造階段，首先使用哈希算法將明文空間中的一個口令映射為密文，然后再使用規約函數，將密文映射為另一明文，使用哈希函數、規約函數依次迭代，得到，，，，…，，，，和分別是該條鏈的首節點和末尾節點，將這兩個節點都存儲下來。多條彩虹鏈構成了彩虹表：

　　其中，表示明文空間中的s條文明，H表示要破解的哈希函數，表示規約函數，s和k是算法的參數，不同的參數值將直接影響彩虹表的存儲空間及密碼破解時間。

　　3.2 基于彩虹表的密碼口令破解

　　對某一已知密文C來說，想要得到其對應的密文，可按三個流程步驟進行。

　　步驟一：對密文C使用規約函數，計算出明文，檢索彩虹表，如果末尾節點中包含，則說明C對應的明文可能存在于該條彩虹鏈中，從該鏈的首節點開始進行哈希函數、歸約函數依次迭代，若鏈中存在與C相等，那么上一步的計算結果則為C對應的正確明文，破解成功。

　　步驟二：如果在末尾節點中未找到，則以為起點，依次使用哈希函數和規約函數計算一次得到明文，按步驟一流程在查找末尾節點，若未找到則重復步驟二繼續查找。

　　步驟三：當重復次數大于彩虹表中的鏈條總數時，說明該密文C未存儲在該彩虹表中，破解失敗。

　　基于彩虹表的密碼口令破解過程流程步驟，如圖1所示。

　　4 系統設計

　　4.1 基于MIC集群的彩虹表的生成

　　4.1.1 系統總體框架

　　眾核協處理器(Many Integrated Core，MIC)是Intel公司針對高性能并行計算而設計的協處理器，其擁有非常強大的計算性能，可以給程序應用提供強大的并行度[8]。彩虹表的生成和查詢就是基于MIC而設計實現的。生成系統主要包含四個硬件結構：PC端、管理服務器、MIC服務器和存儲服務器，生成系統框架如圖2所示。

　　其中，PC終端依照搜索空間表達式、算法等發布指定的任務文件。管理服務器收到終端發來的任務文件后，平均分配需要計算的任務給各個MIC服務器。MIC服務器具備多塊MIC卡設備，可以進行并行計算來生成彩虹表的子表。存儲服務器接收到各個MIC服務器發來的子表，對這些子表的數據進行一致性檢測、完整性檢測，并存儲起來。

　　系統實現了三層并行，即節點間并行、節點上并行和MIC卡上的并行。

　　節點間并行：采用MPI技術實現并行。對于需要生成規模很大的彩虹表，使用MIC集群，MIC管理節點將彩虹表的計算空間平均分配給每一個獨立的計算節點，彩虹表鏈末尾節點的生成任務則由這些獨立的計算節點共同完成。

　　節點上并行：采用Pthread多線程庫函數實現并行。MIC計算服務器具有多塊MIC卡設備，檢測函數可檢測MIC節點上MIC卡設備的塊數，有多少塊就開啟多少個線程，并將任務均分給每一個線程來共同完成。

　　MIC卡上的并行：采用OpenMP技術實現并行。MIC的眾核具有非常厲害的計算能力，只需保留一個核心來進行任務的調度，其余的核心均可用來計算，除此之外，每個核心可以開啟4個線程進行并行計算。

　　4.1.2 彩虹表結構設計

　　彩虹表的配置文件包括八個部分：算法(生成的表使用何種散列函數)、搜索空間表達式、彩虹表鏈長、彩虹表鏈數、首個起始點的值、起始點值遞增步數、塊大小、彩虹表生成需使用計算節點的數量。

　　在原有配置文件的信息的基礎上，彩虹表的子表還添加了用于記錄子表節點號的頭文件，需要生成的塊數及已生成的塊數等信息。這種設計有利于解決由計算節點失效帶來的問題，一旦計算節點失效，可以根據子表中頭文件里的信息從中斷計算的地方恢復任務。

　　4.1.3 規約函數設計

　　規約函數是建立起密文到明文之間的映射的橋梁，他的設計對整個彩虹表的成功率至關重要。該系統將縮減函數和轉換函數相結合定義歸約函數，主要階段包括縮減和明文轉換。

　　縮減函數可將密文通過與特殊的掩碼值進行一系列的與、或、位移等固定操作，獲取固定的索引值。在MIC上利用MIC內嵌原語使縮減函數可以完成16路的并行縮減操作。

　　轉換函數可以憑借縮減函數得到的索引值，將其映射到字符空間來轉換成相對應的明文。為優化傳統的轉換函數，減小求于操作的時延，因此在MIC端和GPU端采用與、異或、移位方法。

　　4.2 基于MIC的彩虹表在線查找

　　彩虹表的在線查找需要用到的結構：PC終端、MIC計算服務器和存儲節點，具體的查找框架如圖3所示。

　　PC終端將任務文件信息發送給MIC計算服務器;MIC計算服務器接收任務信息后對該信息進行解析，生成彩虹鏈的末尾節點并發送給存儲服務器;存儲服務器接收到末尾節點信息后索引末尾節點對應的首節點，并將匹配到的首節點返回給MIC計算服務器;MIC計算服務器接收到首節點信息后進行以該節點為首節點的哈希函數、規約函數迭代計算，生成鏈進行密碼口令破解，并將破解結果返回給PC終端;PC終端接收查詢結果，查找結束。

　　5 結束語

　　本文首先對彩虹表的基本原理進行分析，包含彩虹表的構造方法和破解密碼口令的彩虹表法?；贛IC強大的計算性能，提出了利用MIC集群實現并行的彩虹表生成和在線查找。彩虹表的生成實現了節點間并行、節點上并行和MIC卡上并行。大大提高了彩虹表的生成速度。結合縮減函數和轉換函數定義規約函數提高明文查找成功率。該系統將在公安機關開展應用測試。接下來將重點研究基于彩虹表的破解速度與彩虹表的大小和彩虹鏈的長度之間的關系。

　　參考文獻

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

　　[2] Oechslin P.Making a faster cryptanalytic time-memory trade-off[M] // Advances in Cryp-tology-CRYPTO 2003.Springer Berlin Heidelberg，2003： 617-630.

　　[3] Dorothy Denning.Cryptography and Data Security[M].Boston， Massachusetts， USA： Addison-Wesley，1982：100.

　　[4] Thing V L L， Ying H M.A novel time-memory trade-off method for password recovery[J].Digital Investigation， 2009， 6： S114-S120.

　　[5] 梁艷，張琛嶺，邱衛東.基于生成元的彩虹表[J].信息安全與通信保密，2012 (12)： 85-87.

　　[6] 張悅.基于HBase的彩虹表MD5哈希密碼解密[J].深圳職業技術學院學報，2015，1： 005.

　　[7] 王偉兵，文伯聰.基于彩虹表技術的分布式密碼破解研究[J].中國人民公安大學學報(自然科學版)， 2017，23(01)：79-84.

　　[8] Intel Corporation.Intel? Many Integrated Core Architecture - Advanced[EB/OL].http：//www.intel.com/content/www/us/en/architecture-and-technology/many-integrated-core/intel-many-integrated-core-architecture.html， 2017

　　推薦閱讀：網絡安全工程師的論文文獻