魏海州,楊 云,李凌燕
(揚(yáng)州大學(xué) 信息工程學(xué)院,江蘇 揚(yáng)州 225127)
匿名通信正在快速增長,越來越多的互聯(lián)網(wǎng)用戶使用匿名系統(tǒng)(如Tor或I2P[1])來隱藏其在線活動.從安全角度出發(fā),對這些網(wǎng)絡(luò)的研究也越來越多.
Tor網(wǎng)絡(luò)是一個“覆蓋網(wǎng)絡(luò)”[2,3],其設(shè)計理念是允許用戶匿名訪問外部Internet服務(wù)和提供隱藏服務(wù),因此,Tor提供了兩種操作方式:Web服務(wù)方式和洋蔥服務(wù)方式.Web服務(wù)方式是用戶通過Tor網(wǎng)絡(luò)可以匿名訪問Internet Web,網(wǎng)站無法知道用戶IP地址.洋蔥服務(wù)方式是用戶通過Tor網(wǎng)絡(luò)的洋蔥瀏覽器,訪問Tor網(wǎng)絡(luò)提供的洋蔥服務(wù),用戶無法得知服務(wù)器IP地址.
Internet DNS是基于IP地址的、提供本地化域名解析服務(wù)協(xié)議,它是Internet最重要的基礎(chǔ)設(shè)施,而Tor網(wǎng)絡(luò)不使用IP地址,Tor DNS是基于內(nèi)容的(洋蔥地址)、提供遠(yuǎn)程域名解析服務(wù)協(xié)議,主要協(xié)議有Hidden service協(xié)議和Onion routing協(xié)議等[4].
洋蔥服務(wù)最初被稱為“隱藏服務(wù)”,隱藏服務(wù)本來是為合法內(nèi)容提供商提供匿名性,它包括私人內(nèi)部網(wǎng)(如公司、政府機(jī)構(gòu)或大學(xué)等內(nèi)部網(wǎng)絡(luò))、學(xué)術(shù)論文數(shù)據(jù)庫、商業(yè)數(shù)據(jù)庫或內(nèi)部論壇才能搜索的網(wǎng)站內(nèi)容,需要賬號密碼或訪問權(quán)限才能訪問.但目前一些非法內(nèi)容的論壇/聊天平臺、黑市等提供商,利用為內(nèi)容服務(wù)商提供的的匿名性提供洋蔥服務(wù).洋蔥服務(wù)在2015年重新命名,以反映他們提供更多的服務(wù)事實而不只是服務(wù)的“隱藏”,更重要的是,它們提供端到端的安全性和自我認(rèn)證的主要名稱.洋蔥服務(wù)是基于TCP的網(wǎng)絡(luò)服務(wù),只能通過Tor網(wǎng)絡(luò)訪問并提供相互聯(lián)系匿名:Tor客戶端對服務(wù)器是匿名的,并且服務(wù)器對客戶端也是匿名的.
為了保護(hù)提供洋蔥服務(wù)的服務(wù)器端在線隱私、防止網(wǎng)站被假冒或攻擊、逃避監(jiān)管等,服務(wù)器端必須匿名,隱藏真實網(wǎng)絡(luò)地址與地理位置信息,因此,提供洋蔥服務(wù)的Tor網(wǎng)站采用公鑰字符串,并且在后綴添加.onion構(gòu)成自己的域名.由于采用公鑰的域名不友好、難以記憶,使用不方便,限制了洋蔥服務(wù)的推廣應(yīng)用.
為了使域名具有一定可讀性、便于記憶,在不降低安全性的前提下,設(shè)計具有指定字符的.onion域名,即:生成自定義.onion地址.國外許多學(xué)者進(jìn)行了大量研究,開發(fā)了匿名域名生成工具,發(fā)布了自定義.onion域名,其中最經(jīng)典的是2010年3月發(fā)布的 katmagic的Shallot域名生成工具、2014年10月Facebook發(fā)布了著名的公鑰域名洋蔥地址(1)facebookcorewwwi.onion、2019年5月7日,美國中央情報局CIA在Twitter上公布其暗網(wǎng)鏈接(2)ciadotgov4sjwlzihbbgxnqg3xiyrg7so2r2o3lt5wz5ypk4sxyjstad.onion等.事實上,生成具有指定字符串的公鑰域名是非常困難的,尤其是隨著指定字符串個數(shù)的增加,計算復(fù)雜度呈指數(shù)級增長,屬于NP完全問題.值得注意的是,F(xiàn)acebook或CIA的洋蔥地址生成算法都是基于Shallot的改進(jìn).
通過分析比較,基于Shallot算法,作者設(shè)計的Shallot++算法,可以減少計算的復(fù)雜度,對于指定字符串,Shallot++算法比Shallot算法可以更快地生成符合要求的域名.
Tor的洋蔥服務(wù)以其特殊域名而聞名,.onion是一個特殊用途的頂級域名后綴,可依據(jù).onion TLD中的地址(一般稱為“洋蔥地址”)通過Tor網(wǎng)絡(luò)訪問匿名洋蔥服務(wù).洋蔥地址不是實際的DNS名稱,并且.onion TLD不在Internet DNS根目錄中,Internet DNS上無法解析它,是通過Tor DNS進(jìn)行解析.
.onion TLD中的洋蔥地址通常是不透明的、非助記符,包括所有字母和數(shù)字2-7,它們不區(qū)分大小寫.洋蔥服務(wù)地址是從服務(wù)器的公共RSA密鑰算法生成的,地址是服務(wù)器RSA密鑰的、SHA-1哈希的前16個字節(jié)的base32編碼.
在Tor中依據(jù)生成洋蔥地址的私鑰對用戶進(jìn)行身份驗證,再使用公鑰哈希的洋蔥地址作為聯(lián)系洋蔥服務(wù)的URL.
一般的域名名稱應(yīng)具有全球性、安全性和令人難忘的特征,但由于匿名網(wǎng)絡(luò)的洋蔥服務(wù)要“隱藏”,所以它的名稱不具有“令人難忘”的特征,因此,操作不方便,影響其服務(wù)的推廣應(yīng)用.在保證安全的前提下,為了其具有“令人難忘”的特征,即:名稱中包含熟知的字符串或指定字符串,Tor工程師和許多學(xué)者進(jìn)行了大量的研究,開發(fā)了幾個洋蔥地址生成工具,取得了一些成果.
2010年3月發(fā)布的katmagic的Shallot,密碼規(guī)格為RSA1024和SHA1、操作系統(tǒng)面向OpenBSD或Linux、采用C語言編譯器的單模式哈希域名生成器,洋蔥地址長度為16個字符.由于RSA1024密鑰和SHA1散列的計算都是在CPU完成的,所以速度較慢.
由于Shallot的密碼規(guī)格僅支持1024b的RSA,密碼強(qiáng)度不夠;操作系統(tǒng)不支持Windows,影響了推廣使用;基于CPU計算RSA和SHA處理速度慢.2012年10月發(fā)布的lachesis的Scallion,支持多種RSA密鑰長度(1024b、2048b和4096b)和SHA1、操作系統(tǒng)面向Linux或Windows7、采用C#語言編譯器的多模式哈希域名生成器,洋蔥地址長度為16個字符.由于RSA(1024、2048、4096)密鑰和SHA1散列的計算都是在GPU上完成的,處理速度快.
使用Scallion需要強(qiáng)大的計算資源,一般用戶無法達(dá)到此要求,因此,可以考慮部分使用GPU,另一方面RSA的強(qiáng)度是建立在密鑰長度基礎(chǔ)上的,而橢圓曲線ECC[5]的強(qiáng)度是不依賴于密鑰長度的.2013年2月發(fā)布的Unperson Hiro的Eschalot,密碼規(guī)格支持ECC160和SHA1、操作系統(tǒng)面向OpenBSD或Linux、采用C語言編譯器的單模式哈希域名生成器,洋蔥地址長度為16個字符.ECC160密鑰計算是在CPU上完成,而SHA1散列是在GPU完成的,處理速度沒有Scallion快.
隨著計算機(jī)性能的提高,利用云和GPU計算破解散列函數(shù)SHA1成為可能,存在安全隱患[6].2017年10月發(fā)布的cathugger的mkp224o,密碼規(guī)格支持ECC160和SHA3、操作系統(tǒng)面向OpenBSD或Linux、采用C語言編譯器的單模式哈希域名生成器,洋蔥地址長度為56個字符.ECC160密鑰計算是基于CPU,而SHA3散列計算是基于GPU的,速度較快.
遵循傳統(tǒng),作者保持匿名,katmagic、lachesis、Unperson Hiro和cathugger都是作者的假名.事實上Scallion、Eschalot和mkp224o都是基于Shallot的,只是算法實現(xiàn)不同.域名生成算法實現(xiàn)的難點(diǎn)在于如何合理地利用計算資源和存儲資源,提高處理速度,獲得安全等級更高、具有“令人難忘”特征的域名或地址.
Shallot算法的最大缺點(diǎn)是將奇數(shù)作為RSA公鑰中的加密指數(shù)e,而模數(shù)n的歐拉函數(shù)φ(n)為偶數(shù),為了滿足RSA算法的條件,要求e與φ(n)互素,因此會浪費(fèi)大量的時間去計算非互素的情況.同時,Shallot算法中加密指數(shù)e限制為小于1099511627775,經(jīng)驗上e選取為16位的素數(shù),這樣既可以有效的防止攻擊,又可以獲得較快的加、解密速度.針對這個問題,Shallot++對公鑰中的加密指數(shù)e的選取進(jìn)行優(yōu)化,并且重新設(shè)計了對公鑰進(jìn)行哈希的方式,可以顯著地減少計算量,加快處理速度,提高域名地址的安全性.
為了能夠更好地描述算法性能,引入一個概念:有效測試率.想要生成指定的.onion域名,需要不斷的變換公鑰,然后對公鑰進(jìn)行哈希運(yùn)算.在不斷的碰撞測試中,大量的哈希運(yùn)算是算法性能的瓶頸.因此,進(jìn)行有效的測試會大大提高算法的性能.
基于RSA的.onion域名生成,由模數(shù)n和加密指數(shù)e組成公鑰(n,e),其中n=p×q,p與q為大素數(shù).設(shè)Max為需要測試的總次數(shù),即需要進(jìn)行哈希運(yùn)算的次數(shù),取e不大于Max,φ(n)=(p-1)×(q-1),令集合K為所有滿足gcd(e,φ(n))=1的e的取值,如式(1)所示.
K={e|gcd(e,φ(n))=1,e≤Max}
(1)
取集合K內(nèi)元素的個數(shù)為m,則有效測試率P可以表示為式(2).
(2)
定義每次進(jìn)行哈希運(yùn)算的速率為V,則無效的計算時間T表示為式(3).
T=(1-P)×V
(3)
式(3)中,有效測試率P的值越大,無效的計算時間T就越少.假設(shè)在測試時,滿足指定域名的公鑰(n,e)中加密指數(shù)e的取值不在集合K內(nèi),雖然生成的域名符合預(yù)期值,但是不滿足RSA算法.因此,有效測試率P的增加,算法的效率也會隨之提高.
對Shallot算法基本步驟進(jìn)行概述,并對算法中存在問題進(jìn)行分析.
3.2.1 算法基本步驟
步驟1.隨機(jī)選取兩個大素數(shù)p(512bit)和q(512bit),令n=p×q;
步驟3.選取整數(shù)e=65537作為加密指數(shù),滿足條件1 步驟4.判斷e是否小于m(算法里設(shè)置m最大值為0xFFFFFFFFFF),是則轉(zhuǎn)步聚5,否則轉(zhuǎn)步驟1; 步驟5.對公鑰(n,e)使用SHA-1,產(chǎn)生160bit哈希值.取哈希值前半段(80bit); 步驟6.對哈希值使用Base32進(jìn)行轉(zhuǎn)碼,得到16個字符的域名.檢查域名是否符合預(yù)期,并且判斷gcd(e,φ(n))是否為1,即e與n的歐拉函數(shù)φ(n)的最大公約數(shù)是否為1.是則轉(zhuǎn)步驟8,否則轉(zhuǎn)步驟7; 步驟7.令e=e+2,轉(zhuǎn)步驟4; 步驟8.求解解密指數(shù)d,即d=invert(e,φ(n)),滿足條件e×d=1modφ(n),算法結(jié)束; 在Shallot算法中,步驟1-步驟4是計算RSA1024,獲得公鑰(n,e);步驟5計算SHA-1,獲得160bit哈希值;步驟6分為兩個部分:第1部分對獲得的160bit哈希值使用Base32進(jìn)行轉(zhuǎn)碼,得到16個字符的域名;第2部分對得到的16個字符域名進(jìn)行符合性檢查:是否包含指定字符串. 3.2.2 Shallot算法存在問題 從有效測試率和安全性兩個方面分析. 1.有效測試率.在Shallot中,e的取值為小于Max的所有奇數(shù).為了驗證其算法有效測試率P的值,首先隨機(jī)生成RSA對象,取e不大于4294967295(十六進(jìn)制數(shù)為FFFFFFFF),計算出n的歐拉函數(shù)φ(n),即φ(n)=(p-1)×(q-1).根據(jù)式(1)、式(2),通過計算得到集合K內(nèi)的元素個數(shù)m為1711315240,測試總次數(shù)Max為2147483646,有效測試率P為79.68%,在Shallot算法中,會有20.32%的無效碰撞測試,這不僅增加了CPU的負(fù)擔(dān),同時也降低了產(chǎn)生指定域名的命中率,會產(chǎn)生大量無效的計算時間,導(dǎo)致算法效率不高.并且隨著公鑰中加密指數(shù)e的不斷加大,在判斷gcd(e,φ(n))是否為1時需要的計算量會增加.因此,產(chǎn)生指定域名的字符個數(shù)所需要時間會呈指數(shù)級增長; 2.安全性.主要有3個方面: 1)在Shallot算法中,選取隨機(jī)大素數(shù)p與q時,均為512bit,故生成的模數(shù)n為1024bit,已經(jīng)不能滿足現(xiàn)如今密碼學(xué)安全性的要求[7].RSA1024計算公鑰,2009年12月12日,編號為RSA-768(768 bits,232 digits)數(shù)被成功分解; 2)SHA-1計算散列,2017年2月23日,Cryptology Group at Centrum Wiskunde & Informatica(CWI)和Google的研究人員發(fā)表了“SHATTERED”論文,宣布發(fā)現(xiàn)了2個不同的PDF文檔,但是它們的SHA-1校驗值是一樣的,即:SHA-1碰撞問題; 3)Shallot算法中,僅對公鑰進(jìn)行了一次哈希運(yùn)算,在面對如今的高性能計算機(jī),被尋找到碰撞的可能性很大. 這些事件威脅了現(xiàn)在通行的1024bit密鑰、SHA1散列的安全性,Shallot算法存在安全隱患. 對Shallot++算法思想進(jìn)行闡述,在此基礎(chǔ)上提出Shallot++算法. 3.3.1 算法思想 為了解決Shallot算法中存在的兩大問題,Shallot++算法主要將從以下3點(diǎn)進(jìn)行改進(jìn). 1)RSA模數(shù)n=p×q是RSA算法安全性的核心,如果模數(shù)n被成功分解,則RSA公鑰密碼體制將被攻破[8,9],Shallot++算法產(chǎn)生 RSA對象時,生成的大素數(shù)p與q大小均為1032bit,故模數(shù)n大小為2056bit,產(chǎn)生的RSA密鑰長度符合2048bit,隨著n的增大,因子分解的困難性也增大,這樣嚴(yán)格符合RSA密碼規(guī)格的要求. 2)在Shallot算法中,加密指數(shù)e是奇數(shù),在滿足RSA算法gcd(e,φ(n))=1的條件下,有效測試率P僅為79.68%.其中存在20.32%的無效碰撞測試,這不僅浪費(fèi)了大量的時間,同時也降低了產(chǎn)生指定域名的命中率.加密指數(shù)e不能過小,一般采用不少于16位的素數(shù),并且解密指數(shù)d要大于n0.3.Shallot++算法選用質(zhì)數(shù)作為加密指數(shù)e,模數(shù)n的歐拉函數(shù)φ(n)=(p-1)×(q-1)為偶數(shù),若φ(n)不是e的倍數(shù),則gcd(e,φ(n))=1.選取e是不大于4294967295(十六進(jìn)制為FFFFFFFF)的整數(shù),e為Max內(nèi)所有大于65537的質(zhì)數(shù),使用與Shallot算法中相同的RSA對象,根據(jù)式(1)、式(2),計算可得有效測試率P為99.99%. 3)Shallot++算法對公鑰進(jìn)行雙重哈希并行壓縮的算法,如圖1所示.第1輪將公鑰(n,e)作為輸入進(jìn)行SHA-256運(yùn)算,將第1輪哈希運(yùn)算的輸出作為輸入,再次進(jìn)行SHA-256運(yùn)算,將第1輪運(yùn)算輸出結(jié)果的前40bit,與第2輪輸出結(jié)果的后40bit組合,作為新的輸入進(jìn)行BASE32壓縮.最后將輸出的結(jié)果在后綴加上.onion作為洋蔥域名. 圖1 雙重哈希并行壓縮Fig.1 Double hash parallel compression 3.3.2 Shallot++算法 輸入:指定的字符DomainName,生成符合指定字符的域名個數(shù)number 輸出:公鑰(n,e),解密指數(shù)d,洋蔥域名DomainID 1.Whilenumber>0 do 2. 產(chǎn)生2048位RSA對象(包含大素數(shù)p與q,模數(shù)n) 3.m=(p-1)×(q-1),e=2,test=0 4. Whilee≤Maxandnumber>0 do 5. 標(biāo)記Max內(nèi)所有e的倍數(shù)flage為1 6. While 1 do 7.e=e+1 8. ifflage≠1 Then/*未被標(biāo)記的數(shù)為素數(shù)*/ 9. break 10. End if 11. End While 12. ife>0xFFFFThen 13. 雙重哈希并行壓縮產(chǎn)生匿名域名 14. End if 15. test=test+1/*記錄測試次數(shù)*/ 16. if 產(chǎn)生的域名符合指定字符并且滿足gcd(e,φ(n))=1 Then 17. 求解密指數(shù)d 18. ifd>n0.3 19. 輸出公鑰(n,e),解密指數(shù)d,洋蔥域名DomainID,測試次數(shù)test 20.number=number-1 21. End if 22. End if 23. End While 為了對比Shallot算法與Shallot++算法的性能與安全性,選用百度智能云服務(wù)器BCC進(jìn)行編程實驗,在保證實驗軟硬件環(huán)境相同的條件下,對實驗的結(jié)果進(jìn)行對比分析. 實驗采用百度智能云服務(wù)器BCC平臺,系統(tǒng)為Windows Server 2016 Datacenter 64位,處理器為英特爾Xeon(至強(qiáng))Gold6148 2.40GHz CPU 2核,內(nèi)存為4G.集成開發(fā)環(huán)境IDE選為PyCharm,開發(fā)語言選用python3. Shallot算法與Shallot++算法的目的都是消耗盡可能少的時間計算出指定的域名.隨著指定字符串個數(shù)的增多,生成符合要求的域名所需要的時間也呈指數(shù)增長.同時,通過測試不同的公鑰來產(chǎn)生域名的時候具有偶然性,所以在指定的域名字符個數(shù)較少時,不能準(zhǔn)確的反映算法的性能. 實驗選用指定域名字符串為yzuedu(代表Yangzhou University Educational institutions).為了能更好的反映Shallot算法與Shallot++算法的性能,設(shè)計兩個算法的輸入分別為指定的域名字符DomainName與需要生成符合要求域名的個數(shù)N.算法的輸出為N次,每次分別為符合指定字符串的.onion域名DomainID、公鑰(n,e)、大素數(shù)p與q(保密)、解密指數(shù)d(保密)以及算法耗時和計算哈希次數(shù).為了排除偶然性并且在理論上可行的計算時間內(nèi),獲得指定域名字符串,分別輸入4組測試數(shù)據(jù),依次為(yzu,100)、(yzue,20)、(yzued,10)、(yzuedu,1).實驗中產(chǎn)生的域名與私鑰均已保存,由于進(jìn)一步研究和安全性的需要,不在此公開,如需要可以后期提供.實驗結(jié)果如表1所示. 表1 Shallot與Shallot++實驗結(jié)果Table 1 Shallot and Shallot++ experimental results 第1組測試數(shù)據(jù)分析:Shallot算法比Shallot++算法多進(jìn)行131138次碰撞測試,耗時卻比Shallot++算法少117秒,因為Shallot++算法中,為了優(yōu)化空間復(fù)雜度,節(jié)省空間并且減少CPU的I/O操作,算法在選取Max內(nèi)所有素數(shù)時,并不將計算出的素數(shù)保存,每次計算Max內(nèi)的素數(shù)要花費(fèi)一定的時間,所以在指定的字符較少時,Shallot算法的耗時會優(yōu)于Shallot++算法. 后3組測試數(shù)據(jù)分析:Shallot算法對比Shallot++算法的碰撞測試次數(shù)分別高于自身的49%、34%、33%,算法耗時分別高于自身的31%、23%、25%,Shallot碰撞測試次數(shù)和耗時均高于Shallot++是因為算法的有效測試率僅為79.68%,這不僅會有20.32%的無效碰撞測試,同時降低了生成域名的命中率. 為了對比兩種算法的性能,對前4組數(shù)據(jù)進(jìn)行進(jìn)一步分析,在生成指定域名時,進(jìn)行測試的次數(shù)越少則算法效率越高.在4次實驗中,所進(jìn)行的測試次數(shù)與計算時間如圖2、圖3所示. 圖2 測試次數(shù)對比圖Fig.2 Comparison chart of test times 隨著指定域名字符的增多,雖然Shallot與Shallot++所需要的碰撞測試次數(shù)與運(yùn)行時間都呈指數(shù)級增長,但是Shallot++算法的增幅低于Shallot算法.這表明指定域名字符越多,Shallot++算法的效率越高. 圖3 所需時間對比圖Fig.3 Comparison of time required Shallot++采用雙重哈希并行壓縮的方式來產(chǎn)生域名,提高了算法防碰撞能力和域名的安全性.由于計算量的增加,單次碰撞的耗時將會增多,但Shallot++選取素數(shù)作為公鑰中的加密指數(shù)e,將有效測試率提高到99.99%.當(dāng)指定的域名字符較多時,Shallot++的總體耗時會明顯少于Shallot算法. 為了使域名具有一定可讀性、便于記憶,在Shallot算法的基礎(chǔ)上,提出了一種有效的基于RSA的快速域名生成算法Shallot++,能夠快速有效的生成指定的匿名域名.從算法時間效率上分析,Shallot++算法采用素數(shù)來作為加密指數(shù)e,這樣極大的提高了e與模數(shù)n的歐拉函數(shù)φ(n)互素的概率,即將有效測試率從79.68%提高到99.99%,并且在指定較長字符的域名時,Shallot++算法的耗時明顯優(yōu)于Shallot算法.從算法安全性分析,采用素數(shù)來作為加密指數(shù)e,能夠有效的預(yù)防模數(shù)n被攻擊分解,同時,將Shallot算法中的SHA1改為SHA256,并且使用雙重哈希并行壓縮來產(chǎn)生域名,進(jìn)一步增強(qiáng)抗碰撞能力. 雖然Shallot++算法相比Shallot算法能夠更加快速有效地生成符合要求的域名,但是當(dāng)指定字符數(shù)超過一定數(shù)量時,并不能從本質(zhì)上解決巨大的時間消耗問題,提高哈希計算能力是提高算法效率的關(guān)鍵.Shallot++與Shallot都是基于CPU的,CPU適合做復(fù)雜的運(yùn)算,而生成指定的域名需要將數(shù)億次不同的公鑰進(jìn)行哈希計算,讓CPU來完成重復(fù)的哈希計算會消耗大量的時間. GPU相比CPU具有更多的核心,能夠通過大量的并行計算提高浮點(diǎn)運(yùn)算.下一步的研究工作重點(diǎn)是將算法的哈希計算移植到GPU上,同時采用具有更好地安全性與性能的ECC作為產(chǎn)生域名的公鑰.可利用CPU先產(chǎn)生一部分公鑰,將公鑰拷貝到GPU中進(jìn)行哈希運(yùn)算,同時CPU繼續(xù)產(chǎn)生公鑰.當(dāng)GPU完成哈希計算后,將結(jié)果返回CPU,CPU將計算的公鑰再次拷貝到GPU,同時篩選符合要求的域名,完成后繼續(xù)計算公鑰.這樣就能夠充分發(fā)揮CPU和GPU各自的計算特點(diǎn),進(jìn)一步提高算法的計算處理性能.3.3 Shallot++算法
4 實 驗
4.1 實驗環(huán)境
4.2 實驗步驟和結(jié)果分析
5 總結(jié)與展望