基于gpu的md5密碼并行攻擊算法研究

基于gpu的md5密碼并行攻擊算法研究

1md5并行攻擊算法及實現(xiàn)最近，基于模型單元減少分析的md5沖突攻擊方法（sd5）引起了許多科學(xué)家對sd5的研究興趣。然而,由于該MD5碰撞攻擊方法不能直接由MD5散列值逆向得出明文,因此這種攻擊方法在實際MD5密碼破解中還無法得到很好的應(yīng)用。本文分析了當(dāng)前MD5密碼攻擊中存在的安全性問題,提出一種MD5密碼并行攻擊算法,并基于圖形處理單元(GraphicProcessingUnit,GPU)設(shè)計和實現(xiàn)了MD5高速密碼破解系統(tǒng)。該系統(tǒng)能充分利用GPU的高性能計算能力,對MD5散列值進(jìn)行大規(guī)模并行密碼分析,從而快速破解出經(jīng)MD5加密的密碼,因此,在計算機(jī)安全與取證中具有一定的實際應(yīng)用意義。2基于碰撞的md5密碼破解算法一般破解MD5需要3個基本條件:(1)對于任意y,找x,使得MD5(x)=y。(2)給定x1,找x2,使得MD5(x1)=MD5(x2)。(3)找x1、x2,使得MD5(x1)=MD5(x2)。任何能夠滿足上述3個條件之一的方法稱為MD5破解。目前還沒有一個算法能滿足條件(1)。文獻(xiàn)給出了符合條件(2)或條件(3)的碰撞算法,即可以很快找到2條信息,使之產(chǎn)生相同的MD5散列值。這種基于碰撞的MD5密碼破解方法是在知道x1的情況下可以找到x2,但是x2的內(nèi)容具有不確定性。也就是說,即使知道了x1的內(nèi)容,仍然無法將x1的內(nèi)容篡改為有意義的x2,使x2和x1的MD5值相同。因此,它無法直接威脅當(dāng)前MD5密碼的安全體系。目前對MD5密碼的直接攻擊有窮舉法或彩虹法。窮舉法是把可能出現(xiàn)的密碼明文用MD5運(yùn)算后,把得到的散列值直接與需要破解的MD5散列值進(jìn)行比較,判斷該明文是否是已知MD5散列值所對應(yīng)的密碼明文。當(dāng)密碼空間確定時,窮舉法的破解效率取決于計算機(jī)的運(yùn)算性能。彩虹法是在窮舉法的基礎(chǔ)上把得到的MD5散列值和原始的明文數(shù)據(jù)構(gòu)成一對一的映射表,然后通過搜索和匹配的方式從映射表中找出破解密碼所對應(yīng)的原始明文。當(dāng)明文數(shù)據(jù)的隨機(jī)性很強(qiáng)時,彩虹法要求海量的存儲設(shè)備來存儲映射表和高效的搜索引擎,因此,其破解效率取決于計算機(jī)的存儲空間和搜索方式。3sd5高速解密算法的設(shè)計和實現(xiàn)3.1基于gpu的密碼并行攻擊算法在傳統(tǒng)的MD5密碼破解中,基于CPU的密碼遍歷是串行的循環(huán)計算過程,因此,其效率和計算速度都非常低。本文為此提出一種MD5密碼并行攻擊算法。圖1顯示了基于GPU的MD5密碼并行攻擊算法原理。在CPU中調(diào)用GPU內(nèi)核程序后,GPU通過其內(nèi)部的線程執(zhí)行管理器控制密碼生成器同時產(chǎn)生多個可能的不同密碼。將這些同時產(chǎn)生的多個不同的密碼輸入GPU的不同線程后,這些線程就可以對不同的密碼進(jìn)行MD5并行計算,并與已知的MD5散列值進(jìn)行分析比較,最后輸出比較結(jié)果。通常GPU的線程數(shù)量能夠達(dá)到十萬的數(shù)量級,因此,GPU的密碼破解具有很高的并行計算效率。3.2速md5密碼破解系統(tǒng)基于上述算法原理,本文開發(fā)了GPU高速M(fèi)D5密碼破解系統(tǒng)。該系統(tǒng)采用NVIDIAG80GPU芯片,軟件開發(fā)平臺使用CUDA。其實現(xiàn)過程如下:(1)密碼相關(guān)變量在MD5密碼破解中,需要在GPU內(nèi)核中設(shè)置密碼相關(guān)變量,包括:密碼字符集,密碼字符集長度,密碼長度,待破解的密碼散列數(shù)量,密碼變量指針。這些環(huán)境變量的具體設(shè)置如下:(2)gpu內(nèi)核信息獲取模塊不同的設(shè)備具有不同的GPU硬件資源,如GPU數(shù)量、流處理器數(shù)量以及內(nèi)存大小。為了能夠充分利用GPU硬件資源,需要在GPU初始化中獲取設(shè)備的GPU內(nèi)核信息。本文的破解系統(tǒng)通過以下方式獲取設(shè)備的GPU內(nèi)核信息:其中,變量GPU_N用來存儲當(dāng)前系統(tǒng)中GPU的數(shù)量;變量DeviceProp用來顯示GPU內(nèi)核的相關(guān)信息,如流處理器數(shù)量、存儲器容量。根據(jù)已獲得的GPU硬件信息,為GPU內(nèi)核函數(shù)的參數(shù)變量分配相應(yīng)的GPU內(nèi)存空間,包括已知的MD5散列值、比較結(jié)果變量和每輪內(nèi)核調(diào)用中新的密碼變量指針:最后通過函數(shù)cudaMemcpyToSymbol()把密碼字符集、密碼字符集長度、密碼長度以及散列數(shù)量等數(shù)據(jù)從CPU拷貝到GPU:(3)密碼生成器簡介由于GPU線程是并行執(zhí)行的,因此需要為每個線程分配不同的測試密碼。本文的破解系統(tǒng)通過一個密碼生成器來實現(xiàn),其實現(xiàn)偽代碼如下:其中,變量t_id為GPU中的線程ID號;g_PasswordLength為密碼的長度;g_plain[i]為密碼的第i位對應(yīng)于密碼字符集的指針位置;變量Password為線程t_id所對應(yīng)的密碼。(4)實現(xiàn)md5密碼并行攻擊算法本文在GPU的內(nèi)核代碼中實現(xiàn)了3.1節(jié)的MD5密碼并行攻擊算法,其偽代碼如下:(5)gpu內(nèi)核函數(shù)及參數(shù)由于GPU的程序是以內(nèi)核方式運(yùn)行的,因此需要在CPU中調(diào)用GPU內(nèi)核函數(shù)。與普通的C語言函數(shù)只執(zhí)行一次的方式不同,在調(diào)用GPU的內(nèi)核函數(shù)時,它將由N個不同的線程并行執(zhí)行N次。執(zhí)行內(nèi)核的每個線程都會被分配一個唯一的線程ID。其調(diào)用方式如下:其中,crackmd5為GPU內(nèi)核函數(shù)名。參數(shù)block用于指定內(nèi)核的柵格維數(shù)和大小,即每個柵格內(nèi)線程塊的數(shù)量。為了不使流處理器組在線程同步過程中出現(xiàn)空閑,設(shè)置線程塊的數(shù)量是GPU中流處理器組數(shù)量的4倍。這樣線程塊在線程同步等待時就能使其他線程塊繼續(xù)運(yùn)行,充分利用流處理器組的計算資源。參數(shù)thread用于指定每個線程塊的維數(shù)和大小,即每個線程塊內(nèi)的線程數(shù)量,它取決于每個流處理器組的存儲器資源。假設(shè)每個流處理器組的寄存器總數(shù)是R,每個線程需要占用的寄存器數(shù)量是M,B是每個流處理器組線程塊的數(shù)量,那么每個線程塊的線程數(shù)量T=32×int(R/(B×M)),其中,int為取整函數(shù)。因此,每個GPU內(nèi)核程序的并行線程總數(shù)等于每個線程塊的線程數(shù)量乘以線程塊的數(shù)量。內(nèi)核函數(shù)crackmd5的參數(shù)hash表示已知的MD5散列值。(6)gpu測試密碼結(jié)果根據(jù)第(4)步測試密碼的MD5運(yùn)算結(jié)果及第(5)步GPU內(nèi)核調(diào)用中提供的已知MD5散列值,GPU線程通過比較分析可以判斷其測試密碼是否為已知MD5散列值所對應(yīng)的密碼。其實現(xiàn)偽代碼如下:3.3主機(jī)及主機(jī)的實現(xiàn)下面對2種MD5破解系統(tǒng)進(jìn)行測試和比較分析。在本文的MD5破解系統(tǒng)中,CPU采用最新的IntelCore2QuadQ9300四核中央處理器,內(nèi)存為4GB,操作系為WindowsXP。此外配置了4張GeForce9800GX2的GPU顯卡。圖2顯示了MD5密碼破解速度的比較結(jié)果。其中,Core2QuadQ9300表示采用Intel四核CPU的工作站,其MD5破解速度為每秒9.6×106個密碼;4*9800GX2表示采用本文算法的GPU工作站,其MD5平均破解速度超過每秒30億個密碼,速度是單CPU破解服務(wù)器的300倍以上。4gp