一種高效的隨機混淆匿名算法
2008-01-01 00:00:00張林吳振強
計算機應用研究 2008年5期
摘要：現有的混淆算法都無法適應高速網絡的匿名需求，為此提出了一種隨機數混淆（RM）算法。RM算法在網絡低流量下采用時延轉發方式，在高流量時采用隨機數轉發方式。這樣既保證了匿名系統的匿名性，同時又解決了SGM算法中的溢出問題。對RM算法的安全性和效率進行了分析，仿真結果與理論分析相一致，表明RM算法在開放式高速網絡下有較好的自適應性和實用價值。
關鍵詞：匿名算法； 高速網絡； 隨機數混淆； 消息緩沖
中圖分類號：TP309； TP393．08文獻標志碼：A
文章編號：1001-3695(2008)05-1345-04
0引言
為了保護用戶身份信息的安全與隱私，電子投票、電子銀行、電子商務等系統都把匿名作為重要衡量指標。在現有匿名技術中，廣播隱式地址 [1，2]和DC網絡(dining cryptographers network)[3]要求系統的參與方在一個封閉的匿名集合中，因此無法適應Internet這樣的開放式網絡。為此，D.Chaum[4]提出了一個經過多個混淆器（mix）的數據轉發技術。該技術假設發送者選定N個連續目標，其中之一為真正接收者，竊聽者在一段路徑上獲取真正接收者的概率為1/N，并且中間節點在傳送消息時可采取重新排序、延遲和填充等手段使獲取真正目標的概率更低，從而加大攻擊者流量分析的難度。 Mix是一種特殊類型的路由器，通過改變消息順序和其外表來隱藏出入mix消息之間的關系，增強了系統的匿名效果。Mix要求具有以下功能：發送方集合盡可能大；拒絕直接轉發消息；對消息進行密碼學加/解密操作；消息的重新排序。
為了阻止攻擊者分析出入mix的數據包外表信息，加/解密方法可以改變數據包的外表信息。匿名混淆技術中惟一不同點就是消息混淆算法。目前提出的混淆算法有三種：a)批量混淆(batch mix，BM)算法。D.Chaum在文獻[4]中提出BM算法模型，批量的大小是mix的公開參數，輸入的批量消息經過加/解密后形成一個輸出的批量消息，并對批量輸出消息在轉發前進行簡單排序以實現混淆效果。BM算法的突發轉發工作方式易受到(n-1)型攻擊，且在高速網絡下將會加重網絡擁塞現象。b)混淆池(pool mix，PM)[5]算法。 PM算法是在內存中保留一定數量的消息，當有消息到來時，mix先對該消息進行加/解密變換，再將變換后的結果加入PM中，最后從PM中隨機選取一個消息進行轉發 。由于消息在PM的時延沒有上界，這種不確定性難以驗證PM算法的正確性。c)停走混淆(stop and go mix，SGM)算法[6]。SGM算法是對每個消息延遲一定數量的時間，具體時延大小是由發送方確定。SGM與PM算法相比，降低了網絡突發性。SGM算法中消息的時延保持獨立的決策機制。為了保證mix的匿名效果，SGM算法要求每個消息的時延應大于消息到達mix的平均時間，即使在緩沖區（混淆用的緩沖空間，下同）滿時仍嚴格按消息中規定的時延進行延遲，導致mix不得不丟棄新進入的消息。 在高速網絡下發送方重發丟棄的消息也會導致mix的擁塞現象。 由于SGM算法只有時延機制而無緩沖區溢出的解決策略，導致mix傳輸效率低下，緩沖區成為mix的瓶頸。
本文考慮到網絡高速化趨勢，基于隨機混淆思想提出了一種適合高速網絡的隨機數混淆（random mix，RM）算法。 RM算法采用隊列方法組織混淆數據包，由隨機數決定隊列中的消息轉發順序，從而保證了緩沖區滿時不丟包，減輕了mix的擁塞現象。 同時結合時間戳技術，保證了算法在低流量下的匿名效果。
本文概述了匿名技術研究現狀和實現混淆的三種算法，指出現有混淆算法不能適應高速網絡的匿名需求；針對開放式高速網絡環境提出了一種RM匿名算法，給出了RM算法模型和形式化描述；從跟蹤式攻擊和(n-1)型攻擊方面對RM算法進行安全性和性能分析，并對RM算法從安全性和性能兩個方面進行仿真驗證，從理論上進行了比較。
1隨機數混淆匿名算法
1．1RM算法描述
RM算法采用自適應設計思想，將mix緩沖區中的消息用隊列進行管理。當緩沖區未滿時采用時延混淆方法；緩沖區滿后采用隨機數轉發，此時忽略消息的延遲時間。圖1為RM混淆算法模型。消息編碼變換器（recode message）的主要功能包括：a)消息包的解密和填充操作，目的是改變消息進出mix的外表；b)判斷時鐘窗口值的有效性，若無效則丟棄。隨機數生成器（random generator）的作用是產生一個隨機位，根據產生的結果（0或1）和緩沖區的情況進行決策。 消息緩沖器（buffer message）的作用是對消息進行緩沖處理。緩沖區的消息采用隊列進行管理。當消息mi的緩沖時間Ti變為0時，緩沖區就轉發該消息mi。
RM算法描述如下：若消息緩沖區已滿，且又有新的消息加入，則由隨機數生成器來決定立即轉發隊列中的哪個消息；當產生的隨機數為0時，就從隊頭輸出消息，否則輸出隊列中間的第h個消息，并將新到的消息加入到隊列尾部。其中h 為一常數，可由系統管理員進行設定，1
1．2RM算法的形式化描述
RM算法中m表示mix收到的消息包，key←get_key(m)表示從消息m中獲取的密鑰送給變量key。RM模型不區分密鑰是對稱密鑰還是公鑰。其中key可以是m中的一部分經過mix的私鑰解密獲取的對稱密鑰，也可以是從m的標志獲取鏈路協商的密鑰。m′←MsgRec(m，key)表示消息m經過mix的消息編碼變換器利用密鑰key進行加/解密變換后的結果記為m′，實現m和m′的外表不同。本文緩沖區隊列中出現的m實際就是m′。為了討論方便，在文中其他部分不再區分m和m′，而是將消息變換前后用同一個m表示。函數check_time_window(m)的功能是檢測當前時間是否在時間窗口[TSmin，TSmax]區間上，返回結果是邏輯值。當返回結果為真時繼續執行后續操作；否則就丟棄m。為了阻止DoS和DDoS攻擊，提高算法效率，RM算法采用了兩次檢查時間窗口值的辦法，這樣可以檢測各種攻擊造成的超時。Q表示消息變換器的隊列集合；length(Q)是隊列長度；Msg_in_buffer(Q，m′)是將消息m′加入到緩沖隊列尾部；Fs是時延Ti為零的轉發集合，則Msg_out_buffer(Q，Fs)是將Fs集合所指示位置的緩沖消息進行轉發。則Fs={1}是隊頭消息出列，Fs={h}是轉發隊列中的第h個消息。Updata_Ti(Q)表示更新Q中消息的Ti值，并將Ti為零的消息位置記錄到Fs中。RM算法處理過程可用Mix()和RM(m)兩個函數來描述。Mix()表示混淆器mix的處理函數；RM(m)表示匿名混淆算法的處理函數。消息m可以用四元組表示為（TSmini，TSmaxi，Ti，m）。其中m代表消息內容。RM算法形式化描述如下：
functionRM(m)
{ first_check←check_time_window(m);
ifnot first_checkthen { dropped(m)， return(0) };
key←get_key (m); m′ ←MsgRec(m，key);
second_check←check_time_window (m′);
if not second_check then { dropped(m′)， return(0)};
if length(Q)=n then
{ if rand( )=0 then Msg_out_buffer(Q， {1})
elseMsg_out_buffer (Q， {h});
}
Msg_in_buffer (Q， m′);
return(1)
}
functionMix( )
{Fs=; initial(Q);
do while true
{ if receive(m) then RM(m);
Fs←Updata_Ti(Q);
Msg_out_buffer(Q，Fs);
}
}
算法中dropped(m)函數表示丟棄消息m；return()表示函數返回操作。其中：0或1表示返回時所帶回的邏輯值，0表示1，1表示true。Initial(Q)是隊列Q的初始化操作；receive(m)是檢測是否收到了新的消息m，返回為邏輯值。
2RM算法的安全性分析
2．1跟蹤式攻擊分析
RM算法的安全性主要取決于消息m到達和離開mix之間的關系，為防止攻擊者對進出mix的消息m進行跟蹤分析，從而獲取某種優勢信息。在RM算法模型中，只要mix節點中存在一個以上的消息，攻擊者就無法獲取進入mix的特定消息與流出mix的消息之間的關系。為了分析方便，設有如下兩個事件：
事件A——當消息m到達mix時，該mix隊列為空（假設攻擊者事先知道這一點）；
事件B——在消息m的時延內沒有其他消息到達。
由于事件A和B是兩個獨立事件，則攻擊者實施成功攻擊的概率是P(success)=P(A∩B)=P(A)×P(B)。
在高速網絡下，mix的數據處理可以看成是一個近似的M/M/∞模型。當消息按泊松流到達mix節點，且平均到達率為λ。由于mix網絡中各個mix節點都是獨立工作，轉發時間均為負指數分布，平均服務率為μ。當消息m為隨機到達時，根據M/M/∞模型的排隊理論，在平穩條件下，事件A的概率是P(A)=e-λ/μ。若事件A發生后且其時延內沒有新的消息m到達，則該消息m在mix內的處理就退化為M/M/1/1模型，P(B)=μ/(λ+μ)=1/(1+λ/μ)。
攻擊者在沒有獲得其他優勢的條件下，可以跟蹤到消息包的概率是
P(success)=P(A)×P（B）=e-λ/μ/(1+λ/μ)。
當攻擊者跟蹤某個匿名消息的路徑長度為k，由于RM網絡中各個節點間的獨立性，則攻擊者通過跟蹤方法獲取匿名通信雙方的概率為
上式說明，在網絡負載強度λ/μ固定時，攻擊者攻擊成功的概率隨著匿名路徑長度k的增加呈現指數級下降。同理，在路徑長度k固定時，攻擊者成功的概率也與λ/μ呈負指數關系。
2．2（n-1）型攻擊分析
（n-1）型攻擊是攻擊者利用mix緩沖區空間受限的特點而設計的一種攻擊。當緩沖區可容納最大消息數為n時，攻擊者可以通過控制匿名集合中多達n-1個消息對某個mix節點實施阻塞。這樣在網絡流量小的情況下，最后進入的消息可能最先流出網絡。這樣攻擊者就可以獲取有價值的信息或跟蹤某個匿名消息。為了阻止（n-1）型攻擊，RM算法采用時間戳（TSmin，TSmax）機制來檢測流入數據包的延遲情況。若收到的數據包超出這一窗口，mix就丟棄該包，這樣RM算法就可以阻止(n-1)型攻擊。由于發送方預先知道消息需要的延遲時間，可以精確地計算出RM算法的時間窗口。具體計算過程參見文獻[6]。為了方便分析，設有如下三個事件：
事件C——當消息m到達mix時，該mix隊列已有n-1個消息（設攻擊者事先知道這一點）；
事件D——在消息m的時延內沒有其他消息到達；
上式說明， (n-1)型攻擊成功的概率與k和λ/μ呈負指數關系。攻擊者惟一可以成功實施(n-1)型攻擊的情況是，攻擊者在消息到達前阻塞RM網絡中所有流入消息相當長一段時間。在攻擊者不知道所有用戶發送消息時選擇某些mix節點的情況下，不可能做到按需阻塞整個RM網絡；并且這種阻塞的結果會導致大部分消息的時間戳超時，從而導致消息被mix丟棄。因此，要保證用戶檢測不出攻擊是不可能的。
3RM算法性能分析
RM算法性能取決于任意時刻緩沖區內的消息數和消息丟包率。在流入消息相同的情況下，緩沖區內消息越多，說明算法的混淆效果越好，性能就高。RM算法采用時延轉發與隨機轉發相結合，消息的丟包率為零。由于RM算法中消息共有四次轉發機會，RM算法的性能可以按圖2中的四階段開馬爾可夫排隊系統進行分析。其中：time delay 1和time delay 2分別表示消息m在緩沖區間[Δt，(n-h)Δt]和[(n-h+1)Δt，(n+h)Δt]的延遲隊列;n-h和h-2分別為兩個隊列長度；RM1和RM2分別表示消息在隊列中第h位置和隊頭第1位置時的隨機轉發隊列，其長度均為1。在這種四階段的開馬爾可夫排隊系統中，由于采用的是隊列對這四個階段進行統一管理，當隊列中有消息被轉發時，該轉發位置之后的消息立即前移。這四個階段是非獨立的。當網絡流量較大時，time delay 2將始終保持隊滿狀態。RM算法的平均隊列長度為L=h-2+1+1+E(l1)=h+ E(l1)。其中：E(l1)是time delay 1隊列長度的數學期望值。
由于time delay 1的消息轉發不是嚴格按隊列方式，若將消息的隨機時延理解為消息的“忍耐”程度，則這種排隊模型可以抽象為具有不耐煩顧客的M/M/1排隊模型。設排隊等候轉發的消息有i個，隊列中進行時延轉發而離開隊列的強度與i有關，記為Δi，設Δi=iδ。當消息以泊松流為λ的平均到達率時，根據不耐煩顧客的M/M/1排隊模型理論：
從分析可以看出，在大流量的高速網絡下RM算法保證隊列長度始終大于h。當選取h＞n/2時，RM算法不僅可以保證系統的匿名性，且隊列長度始終保持在[h，n]之間變化。
4仿真與比較
4．1RM算法的仿真分析
為了進一步反映RM算法的有效性，本文數據是在Pen-tium 4 CPU，頻率為2．4 GHz，RAM為256 MB的方正電腦，在MATLAB 6．1環境下仿真得出的結果。
圖3是RM算法在不同匿名路徑長度下所受到的攻擊概率P與λ/μ變化關系。其中圖3(a)反映的是跟蹤式攻擊概率P與網絡流量強度λ/μ的對應關系。從圖中可以看出，P隨著λ/μ的增加而減少。當λ/μ＞0．6，k＞5時，RM匿名網絡系統受到跟蹤式攻擊的概率就接近于零。k>5在開放式高速網絡下是非常普遍的。圖3(b)是(n-1)型攻擊概率P與網絡流量強度λ/μ的關系。當λ/μ=2．4時，RM算法受(n-1)型攻擊的概率達到最大值，為3．2×10-13。當k=5時，RM算法受(n-1)攻擊的概率為零。因此RM算法在開放式高速網絡下防止攻擊是非常有效的。
RM與SGM算法在不同時刻緩沖區消息數和SGM丟包數變化曲線。橫坐標是混淆網絡所經歷的繁忙和空閑的周期數；縱坐標是緩沖區中的消息數或SGM丟棄的消息數。其中消息的時延是在[1，20]內均勻分布，每一個周期的消息數是隨機產生的，且遵循泊松分布。每經過一個周期，對系統緩沖區中的消息數和丟棄的消息數進行一次統計。由于消息的時延和消息流強度都具有隨機性，每次實驗仿真的結果都不盡相同。其中圖4(a)和(b)是在若干次不同實驗中選取具有代表性的一組圖。圖4(a)的前5個周期緩沖區未滿，因此兩算法曲線重疊，SGM算法的丟包曲線為零；從第6個周期開始，SGM和RM算法的緩沖區消息數出現變化，且SGM算法開始出現丟包現象。可以看出，300個消息分布在33個周期內，SGM算法丟包達71個，丟包率為23．67%。進一步仿真結果是在500個包下的丟包率為27．2%，而1 000個包時丟包率高達32．4%。圖4(b)是600個消息下的仿真結果。為了讓緩沖區的變化更清晰，舍去了丟包數的變化曲線。可以看出，600個消息分布到57個周期內，緩沖區數不相等的次數是21次。其中19次是RM算法大于SGM算法；另外2次是RM算法在轉發消息時恰好將時延大的消息在h處被轉發，導致在后面的周期內出現SGM緩沖區數多于RM緩沖區。從整體看，RM算法緩沖空間利用率優于SGM算法。RM算法除了開始和中間連續多個空閑周期外，緩沖區的消息數都大于設定的門限h，且不丟棄消息。因此RM算法在整體性能上優于SGM算法。
4．2RM與SGM算法比較
表1對RM與SGM算法在理論模型、緩沖區管理、緩沖區滿時的處理方法以及不同λ/μ下的抗攻擊能力、緩沖區的平均消息數等進行了比較。
與SGM相比，RM算法在抗(n-1)型攻擊方面優于SGM，尤其是在高速網絡大流量的情況下，SGM算法只有一次轉發機會，而RM有四次轉發機會，這方面可以加強混淆效果。另一方面，RM在緩沖區滿時通過調整消息轉發方式和轉發速率，可以繼續轉發匿名消息，系統性能不受任何影響，匿名度不會下降。因此，RM算法成功地解決了SGM算法中時延、匿名性、緩沖區溢出三者之間的關系，且不丟棄新加入的消息。
5結束語
本文針對網絡技術的高速化趨勢，根據混淆網絡與網絡流量之間存在的矛盾關系，提出了適應開放式高速網絡的隨機混淆匿名算法。RM算法相對于其他算法的一個顯著特點是，RM算法對mix的緩沖區管理算法進行了改進，使mix能在系統繁忙和空閑期間保證系統的匿名性，同時解決了高速網絡中因mix緩沖而造成的溢出問題。算法具有一定的自適應性和實用性。仿真結果與理論分析相一致，說明RM算法在開放式高速網絡下既能保持系統匿名效果，同時又能較好地解決匿名系統因強制消息時延而造成的丟包問題，對提高匿名系統的傳輸效率具有一定的實用價值。
參考文獻：
[1]FARBER D J， LARSON K C. Network security via dynamic process renaming[C]//Proc of the 4th Data Communication Symp. Quebec City:[s.n.]， 1975:8－18.
[2]KARGER P A. Non－discretionary access control for decentralized computing system， Report MIT/LCS/TR－179[R].[S.l.]: MIT， Laboratory for Computer Science， 1977.
[3]CHAUM D. The dining cryptographers problem: unconditional sender and recipient untraceability[J]. Journal of Cryptology， 1988，1(1):65-75.
[4]CHAUM D. Untraceable electronic mail， return addresses， and digi-tal pseudonyms[J]. Communications of the ACM， 1981，24(2):84-88.
[5]COTTREL L. Mixmaster remailer attacks[EB/OL].(1995).http://www.obscura.com/~loki/remailer－essay.html.
[6]KESDOGAN D， EGNER J， BUSCHKES R. Stop－and－go mixes providing probabilistic anonymity in an open system[C]//Proc of Information Hiding Workshop.[S.l.]: Springer－Verlag， 1998.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
