基于3DES-RC4混合加密的即時通信系統①

劉 峰,王丹丹,2,于 波,于 飛

1(中國科學院 沈陽計算技術研究所,沈陽 110168)

2(中國科學院大學,北京 100049)

即時消息是一種兩個或者兩個以上的人基于鍵入文本進行實時通信的形式.隨著計算機網絡的發展,即時通信已經由最初的計算機專家快速交換重要信息的工具演變成全球最常用的通信交流機制之一[1].其功能也由最初的文本消息傳遞擴展到語音、視頻通話以及圖片視頻等文件的實時傳遞.即時消息在移動商務、移動銀行、行政用途和日常生活等方面發揮著越來越重要的作用[2,3].

盡管即時通信技術會帶來很多便利,但同時也會引入很多風險和責任.用戶傾向于使用即時通信服務來傳輸所有類型的消息,包括信用卡和銀行賬號等信息[4].攻擊者將即時通信服務視為竊取信息的豐富來源,監聽是捕獲通過網絡傳遞即時通信消息最常用的方法[5].在公共即時消息傳遞系統中,消息從客戶端傳送到服務器,再傳遞到第二個客戶端.竊聽者可能會沿著其Internet 路徑或網絡內的任何地方看到此數據,信息隨時可能會傳給其他人[6].因此對即時通信系統的消息傳遞進行安全加密,保證消息的完整性和安全性是非常必要的.

安全加密消息傳遞是一種基于服務器的用于保護Internet 上未授權訪問的敏感數據的方法.現代密碼學涉及4 個主要特征:(1)機密性;(2)完整性;(3)不可拒絕性以及(4)身份驗證[6].隨著這些年來技術的發展,用于即時消息加密的方法和技術也大大擴展,對即時消息數據的加密強度也逐步增強.

計算機的出現使得我們保護消息發送而免受攻擊的復雜性和速度呈指數級增長.近年來,諸如AES、SHA 以及3DES 等加密算法已經用于即時通信系統的消息加密以及解密[7–14].但是隨著硬件的改進(例如GPU的改進),這些算法有可能被破壞.由于此問題可能帶來的威脅,從長遠來看,還需要尋找替代方案來提高Internet 上用戶內容的安全性[2].

本文提出一種基于3DES和RC4的混合加密算法,利用3DES 加密強度和RC4 算法的偽隨機特征,在保證加密速度的同時,提高加密強度.選擇這兩種算法的原因主要是:(1)這兩種算法同屬對稱加密算法,加密速度快,滿足即時通信系統實時性的要求;(2)模塊化的RC4 算法可以很輕易地替代3DES 算法的默認密鑰生成算法.RC4 算法的偽隨機性質將改善原本由序列移位和壓縮產生的可預見的48 bit的密鑰的安全性.

1 加密算法介紹

針對信息傳遞的安全加密算法的研究有很多,比如3DES[11],AES[15],RSA[9,16]等,這些算法通常使用密鑰來執行加密和解密的過程,基于密鑰的加密算法主要有兩大類:(1)對稱加密算法;(2)非對稱加密算法(公開密鑰算法).下文將介紹一些常用的安全加密算法.

1.1 DES 加密算法

DES (Data Encryption Standard)加密算法是一種對稱加密算法,算法密鑰長度為64 位,其中每8 位中有一位作為奇偶校驗位,即實際密鑰長度為56 位.DES算法由4 個部分組成:(1)初始置換;(2)16 輪函數迭代計算;(3)密鑰生成算法;(4)逆置換.如圖1所示.

圖1 DES 加密算法框圖

圖1中初始置換和逆置換互為逆運算,旨在將16 輪函數迭代計算前后的結果按位進行重新組合,以降低密文的統計特性并提高安全性.16 輪函數迭代計算是DES 算法的核心,其利用48 位的密鑰對輸入的低32 位進行轉換產生新的32 位的輸出,作為數據塊的高32 位塊饋入下一輪迭代計算函數.密鑰生成器產生一個64 位的密鑰作為輸入,并使用它按順序生成16 個不同的密鑰用作函數迭代計算的輸入密鑰.因此DES加密算法存在潛在弱點,如果知道初始密鑰,一旦知道P 盒置換,就可以預測出DES 算法的所有后續密鑰.

1.2 3DES 加密算法

DES 算法的缺點之一就是其密鑰空間很小,容易被暴力破解.因此3DES 算法以DES 算法作為基本模塊,以組合分組的方式設計出加密算法,對數據塊進行3 次DES 加密來擴大密鑰空間.其加密解密過程分別是對明文/密文數據進行3 次DES 加密或者解密,每一次的密鑰不同,如圖2所示.3DES 加密算法有兩個重要的參數,即密鑰數量和操作順序.3DES 可表示為:DES(k3;DES(k2;DES(k1;M))),其中M是待加密的消息塊,k1,k2,k3 分別為3 個DES 模塊的密鑰.若3 個密鑰互不相同,則相當于用一長度為168 位的密鑰進行加密.若數據對安全性要求不高,第一個密鑰可以等于第3 個密鑰,密鑰的有效長度為112 位[17].但由于其對特定明文和已知明文攻擊的敏感性,因此認為它只有80 位的有限安全性[18,19].近些年來隨著硬件計算速度的提升,窮盡搜索3DES 算法的密鑰空間成為了可能.

圖2 3DES 加密算法框圖

1.3 RC4 加密算法

RC 加密算法是由Rivest R 于1987年首次提出,是一種對稱加密算法.RC4 加密算法與DES 算法不同,它不是對明文進行分組處理,而是以字節流的方式對明文中的每一個字節進行加密,相同地,解密的時候也是針對密文中的每一個字節進行解密.該算法利用不規則置換[20],其密鑰長度可變,在8 位至2048 位之間,密鑰流完全獨立于明文[21,22].RC4 加密算法強度很高,至今尚未找對針對128 位密鑰長度的RC4 算法的攻擊方法.

RC4 加密算法流程如圖3.狀態向量S長度為256字節,用于保持所有8 位數的排列.向量由長度為1 到256 個字節的密鑰的排列初始化,算法運行的任何時候,S 都包括256 個8 位的排列組合,僅有值的位置發生了變換.為了計算初始排列,使用長度為256 個字節的臨時向量保存初始密鑰,如果密鑰長度為256 個字節,則初始向量T就是初始密鑰,否則為初始密鑰的重復排列.密鑰和臨時向量T僅用于初始狀態,加密和解密狀態僅和狀態向量S相關.密鑰調度算法根據臨時向量T初始化狀態向量S,再通過偽隨機數生成算法生成密鑰流,其長度和明文的長度是對應的.密鑰流和明文按字節進行異或就得到了密文.

圖3 RC4 加密算法

2 3DES-RC4 加密算法

2.1 提出的3DES-RC4 算法介紹

從上文對DES 算法密鑰如何生成的描述中可以看出,其存在一個主要的缺陷.如果知道了作為密鑰生成算法的初始64 位密鑰,則其后續的16 輪迭代函數的密鑰也能順序破解.另外,如果知道了某一輪迭代的密鑰,也可以破解其他回合的密鑰.對于RC4 加密算法,即使知道了初始密鑰,其生成的密鑰仍然是偽隨機的,其優勢在于加密速度快,安全性高,可以抵御密碼分析攻擊.

基于以上分析,本文提出了一種基于3DES和RC4的混合加密算法,算法的框架類似于3DES 算法,一個主要的不同在于每一個DES 算法中16 輪迭代函數的密鑰均由RC4 加密算法提供.利用RC4 加密算法的偽隨機數密鑰生成機制,以前一輪迭代函數的密鑰或者初始密鑰作為種子,可以產生所有的密鑰.算法的加密過程如下:

其中,Ki,1≤i≤3 表示用于第i個DES 過程的密鑰子集和,Ki,j,1≤i≤3,1≤j≤16 表示第i個DES 過程的密鑰子集和中第j輪迭代函數的子密鑰.

算法.3DES-RC4 算法

(1)利用RC4 偽隨機數生成器產生16 輪迭代函數的子密鑰.第一輪迭代函數的子密鑰由初始密鑰K1作為種子,其余輪迭代函數的子密鑰均由前一輪迭代函數的密鑰作為RC4 加密算法的輸入產生;

(2)將產生的16 個子密鑰與初始密鑰集(IV)進行異或操作產生新的16 個48 位的密鑰,作為DES 算法中的每一輪迭代函數的輸入;

(3)通過上述兩個規則,中間密文經過解密和加密回合,生成最終密文;

(4)解密過程類似,只不過密鑰以相反的順序提供給每一輪不同的DES 過程.

3 DES-RC4 加密算法的框架如圖4所示.圖5表示了每輪DES 如何通過RC4 加密算法密鑰生成函數獲取密鑰,通過在發送方和接收方之間共享3 個密鑰key1、key2和key3,可以生成相同的偽隨機密鑰序列,因此可以分別用于加密和解密過程.這種方式可以確保不能利用任何中間回合密鑰的信息獲取原始密鑰,可以大大提高安全性能.

圖4 3DES-RC4 加密算法框架

2.2 3DES-RC4 算法復雜度分析

3 DES-RC4 算法框架同3DES 算法類似,它們都需要額外的一個安全通道共享3 個密鑰,而且都易于在硬件上實現.與3DES 算法不同的是:(1)3DES 算法密鑰安全性低,而3DES-RC4 加密算法生成的密鑰是偽隨機的,安全性較高;(2)3DES 算法使用迭代回溯方法獲得密鑰,而3DES-RC4 算法則是利用RC4 算法生成密鑰;(3)3DES 算法中給每一個DES 迭代函數的密鑰是相互獨立的,而在3DES-RC4 算法中,本輪的密鑰依賴于前一輪的密鑰.

對3DES 加密算法來說,如果3 個密鑰互不相同,則其復雜度為O(2168).而RC4 加密算法屬于流密碼體制,其內部狀態的大小是衡量其復雜度的一個重要因素.RC4的內部狀態由256 個字節的S 盒2 個8 bit的指針i和j組成.根據S、i和j不同的取值,其內部狀態可能的取值有 216×(256!)種[23],具有l og2216×(256!)≈1700 bit信息量,因此RC4 算法復雜度為O(21700).本文提出的3DES-RC4 加密算法,核心思路是利用RC4 加密算法替代DES 算法的密鑰生成模塊,來擴大密鑰空間,因此3DES-RC4 加密算法的復雜度為O ((21700)3)=O(25100).

因此,本文改進提出的3DES-RC4 加密算法加密強度遠遠優于3DES 加密算法.同時由于其采用的算法框架類似于3DES 加密算法,故加密速度不會劣于3DES 算法,具體實驗測試結果見后文.

圖5 3DES-RC4 密鑰生成

3 即時通信系統設計

3.1 即時通信系統框架

基于提出的3DES-RC4 加密算法,本文設計了一款即時通信系統.通信系統提供登陸注冊、通訊錄、即時消息(文字、語音、群聊)等功能,加密模塊對文字、語音消息進行加密,以提升整個系統的安全性.即時通信系統密鑰分配與會話過程時序圖如圖6所示.登陸注冊到服務器的客戶端之間有一個共享密鑰,稱為主密鑰,用戶會話過程中,由服務器通過主密鑰為會話用戶分配會話密鑰.客戶端A和B登陸注冊到服務器時,由服務器對用戶信息進行安全驗證,隨后根據身份信息隨機產生主密鑰KA(KA1,KA2,KA3)和KB(KB1,KB2,KB3),并回應給用戶A和B.A和B建立會話的過程如下,首先由A向服務器發送會話請求及隨機會話標識N,服務器對A的請求進行回應,通過主密鑰KA對回應的消息進行加密,因此只有A能成功解密這一消息.回應的消息包括A需要的一次性會話密鑰KS(KS1,KS2,KS3),用于驗證消息是否被篡改的A發送給服務器的請求信息以及B需要的由主密鑰KB加密的一次性會話密鑰KS,用于對A身份進行驗證的信息IDA,其中隨機產生的KS與會話標識N直接相關,因此能保證會話密鑰的定期更新.A存儲一次性會話密鑰KS,并經服務器轉發由主密鑰KB加 密的會話密鑰KS和A的身份信息IDA,B收到密文后對其進行解密,得到會話密鑰KS以及A的身份信息IDA.至此,會話密鑰KS已經分配給用戶A和用戶B.如A要向B發送消息P,則A利用KS對P加密得到密文M,經過服務器將M轉發給用戶B.B收到消息后,利用會話密鑰KS對密文M解密得到消息P,并向A發送已讀回執,完成一次消息的發送.

3.2 即時消息加密模型

系統加密模塊基于提出的3DES-RC4 加密算法.即時消息包括文字消息和語音消息,針對不同的消息類型,加密模型略有差異.

加密模型1.文字加密模型

(1)發送方鍵入文字消息;

(2)文字消息轉化為字節序列;

(3)利用3DES-RC4 算法加密字節序列;

(4)加密的字節序列轉化位字符串;

(5)將字符串傳送給服務器;

(6)接收方從服務器端接收加密字符串;

(7)將加密字符串轉化為字節序列;

(8)對字節序列進行解密;

(9)將解密的字節序列轉換為同發送消息一樣的字符串.

加密模型2.語音消息加密模型

(1)發送方錄入語音消息;

(2)語音消息轉換為字節序列;

(3)利用3DES-RC4 算法加密字節序列;

(4)將加密字節序列存儲到語音文件;

(5)將語音文件放送到服務器;

(6)接收方從服務器接收語音文件;

(7)從接收的語音文件中提取出加密字節序列;

(8)對加密字節序列進行解密;

(9)將解密后的字節序列解析到文件輸出流;

(10)媒體播放器解析文件輸出流并播放.

圖6 消息傳遞時序圖

4 結果與討論

為了對本文提出的3DES-RC4 加密算法的功能和性能進行評估,針對即時通信系統加密算法分別進行了加密和解密功能測試、加密性能測試、“雪崩效應”驗證及攻擊模型驗證等測試.

4.1 加密解密功能及性能測試

首先將以下內容作為輸入明文:“Hello!世界”,選取3 個密鑰分別為key1:first key、key2:second key和key3:third key.結合算法分析過程,理論推導其密文,為了方便對比,明文、密文及中間過程密鑰均采用byte 數組表示.

原始明文:[72,101,108,108,111,33,–28,–72,–106,–25,–107,–116]

密鑰1:[102,105,114,115,116,32,107,101,121]

密鑰2:[115,101,99,111,100,32,107,101,121]

密鑰3:[116,104,105,114,100,32,107,101,121]

初始向量IV:[0,0,0,0,0,0]

第一個DES 子密鑰集K1,j,1≤j≤16:

[[–60,–53,–36,53,–109,–10],

[4,–58,–117,76,113,32],

[15,–13,–31,124,81,–64],

[28,44,–18,90,–127,106],

[55,–109,77,127,–68,125],

[–64,97,–123,–30,85,31],

[–107,–94,–50,23,55,–113],

[32,35,88,–31,19,53],

[114,–95,–90,97,124,98],

[–48,–79,83,–122,26,–118],

[–45,20,–22,–60,11,–6],

[–103,123,–16,–46,45,32],

[95,109,–128,–60,–23,–80],

[64,–95,–30,–128,75,–71],

[44,–47,21,–79,–3,79],

[–19,6,–54,67,–118,–8]]

明文經過第一次DES 加密,由于輸入明文長度為12,而加密過程以8 位為一個分塊,故在實際加密過程中,需要將明文補0 至16 位,密文為:

[68,103,58,–26,–121,89,57,–62,56,–81,67,120,115,90,3,27]

第2、3 次DES 子密鑰集產生方式類似,故本文不再列出.經過第2 次DES 過程之后的密文為:

[–6,–128,–87,123,20,–32,–94,–46,11,98,6,113,6,101,–45,–35]

第3 次DES 加密后的密文,即明文經過3DESRC4 加密算法加密后的密文為:

[13,–34,116,–68,–120,9,111,–5,13,–5,–60,21,–40,30,–64,74]

為了驗證即時通信系統功能,在測試中人為設定服務器回應的會話密鑰與理論分析相同.利用兩個客戶端進行通信,客戶端A向客戶端B發送消息:“Hello!世界”,日志如圖7所示,可以看出密文數據與理論計算相吻合,證明了加密系統功能是正常的.

圖7 加密解密結果

為了進一步分析算法在移動平臺的性能,我們對基于此算法加密的移動即時通信APP 進行了研究.算法實現代碼為Java.以Redmi Note 7 手機為測試設備,操作系統為Android,CPU為4 個2.2 GHz和4 個1.8 GHz的核心,運行內存4 GB,存儲空間64 GB.利用包含不同數量字符的消息對算法的性能進行了測試,每個消息字符數量范圍從100 變化到65 000.為了對比,同時測試了3DES 算法的性能.結果如圖8所示,可以看出3DES-RC4 算法加密、解密時間與3DES 算法近似相等.在字符個數為10 000 時,加密時間約為0.3 s,表現出良好的時間性能.由于此算法針對即時通信系統,即時消息的長度一般不會超過25 000,其加密解密時間均小于1 s.故可以認為本文提出的3DES-RC4 算法適用于即時通信系統.

4.2 “雪崩效應”驗證

為了對提出的3DES-RC4 加密算法的加密強度進行進一步評估,并和3DES 加密算法進行對比,分別測試分析了密鑰和明文改變某一比特或某幾比特時,密文改變的比特數,即兩個算法的“雪崩效應”.

首先設定待加密明文為“Hello World!”,初始密鑰為key1:1、key2:2 以及key3:3.密鑰key2、key3 保持不變,改變密鑰key1的某一位或者某幾位,觀察輸出密文的變化情況,結果如表1所示.可以看到當密鑰僅有很少的位數發生改變時就會引起輸出密文很大的位數改變,符合加密算法“雪崩效應”的準則.

在此基礎上,保持密鑰為key1:1、key2:2和key3:3,設定初始待加密明文為1.改變輸入明文的某一位或者某幾位,觀察輸出密文的變化情況,結果如表2所示.可以看出輸入明文發生微小的改變時,輸出密文同樣會產生劇烈的變化.

圖8 算法時間性能

表1 密鑰位數變化時密文位數變化情況

表2 明文位數變化時密文位數變化情況

根據實驗結果,3DES-RC4 加密算法和3DES 加密算法均具有較好的“雪崩效應”效果.改變密鑰某一比特或改變明文某一比特時,兩個算法加密后的密文“改變位數”很大,達到總數的一半左右.同時對比可以發現,在同樣改變密鑰或者明文的情況下,3DES-RC4 加密算法的密文“改變位數”均稍大于3DES 加密算法的密文“改變位數”.因此3DES-RC4 加密算法相較于3DES 加密算法具有更好的“雪崩效應”,加密強度更高.

4.3 攻擊模型驗證

加密算法的安全等級越高則意味著在實際使用過程中被攻擊的難度越高.為了對所提3DES-RC4 加密算法的安全等級進行評估,利用典型的攻擊模型對算法進行了進一步的評估,并和3DES 算法進行對比.

窮舉搜索攻擊是最常見的攻擊模型.如前文分析,3DES 復雜度為O(2168),隨著近年來硬件技術的發展,在一定程度上可以窮舉搜索攻擊3DES 算法.而3DESRC4 加密算法的復雜度為O(25100),相較于3DES 算法攻擊難度大大增加.

已知明文攻擊是攻擊者知道明文密文對,利用已知信息攻擊密鑰的一種攻擊模式.對于3DES 加密算法,Ottawa 等已經證明在知道232明密文對時,破解3DES 加密算法的復雜度僅有O(288),這對于如今的硬件來說難度并不大[19].而3DES-RC4 加密算法密鑰生成模塊RC4 能夠抵抗已知明文攻擊[24],故而已知明文攻擊模型不能有效攻擊提出的3DES-RC4 算法.

選擇明文攻擊是另外一種攻擊強度更高的攻擊模式,攻擊者可以指定一定數量的明文,讓待攻擊的加密算法進行加密,得到相應的密文.Merkle-HeIIman 已經證明了2-key 3DES 算法利用選擇明文攻擊時其時間和空間復雜度可以降至O(256)[18].由于3DES 算法和本文提出的3DES-RC4 加密算法均以DES(16 輪)算法加密為基礎,為了簡單驗證,我們實現了3DES 6 輪子過程的差分攻擊算法模型,分別對3DES和3DESRC4 算法子過程進行攻擊實驗,攻擊過程如圖9所示.結果如表3所示,可以看出差分攻擊可以攻擊得到3DES的子密鑰及初始密鑰,而對于3DES-RC4 算法來說,雖然可以攻擊獲得子密鑰,但是由于RC4 算法對選擇明文攻擊免疫,無法攻擊得到初始密鑰[24].

圖9 差分攻擊過程

表3 差分攻擊結果

5 結論與展望

本文提出了一種新的基于3DES和RC4的混合加密算法,用于即時通信系統安全加密.該算法使用RC4 加密算法作為3DES 加密算法的密鑰生成器,在保持加密解密速度不變的情況下有效地將密鑰位寬從64 位提高到了2048 位,算法復雜度由O(2168)提升至O(25100),這使得該算法通過簡單的密碼分析很難破解.除此之外,算法使用了初始密鑰向量,確保一次密鑰的信息不會損害其他密鑰的保密性,從而增強了算法的安全性.以3DES-RC4 算法為基礎,設計了一款即時通信系統,對通信系統的加密解密功能、加密性能、加密強度進行了分析和研究,結果證明了提出的3DESRC4 算法的可行性,在加密強度和適應性等方面優于其構成算法.接下來的研究工作是對此算法進行進一步的改進,包括增加輸出反饋機制等.