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

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

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