RC4是美國密碼學家Ron Rivest在1987年設計的密鑰長度可變的流加密算法。它加解密使用相同的密鑰，因此也屬于對稱加密算法。RC4曾被用在有線等效加密（WEP）中，但由于其錯誤的使用的方式已被有效破解，而如今，它又被TLS協議所放棄。
在2015年2月發布的RFC7465中,RC4密碼套件被禁止在TLS各版本的客戶端和服務端使用。客戶端禁止在ClientHello中包含RC4套件，服務端禁止從ClientHello中提供的密碼套件中選擇RC4，如果客戶端只提供了RC4，服務端必須終止握手。另外，谷歌、微軟、Mozilla也宣布將于明年年初在各自的瀏覽器中停止對RC4的支持。
從1994年RC4被匿名公開在Cypherpunks郵件列表，到如今RC4被TLS協議放棄，安全研究員們做出了很多貢獻。
RC4算法分為兩個部分。第一部分是密鑰調度算法（key-scheduling algorithm）,根據key初始化S盒，第二部分是偽隨機數生成算法(Pseudo-random generation algorithm)，生成密鑰流，同時更新S盒的狀態。
密鑰調度算法:
Input： 密鑰K ，K長度Ｌ字節
Output:初始化后的S盒子
For i=0 to 255 do
S[i] = i
j=0
for i=0 to 255 do
j = ( j+S[i]+key[i mod L] )mod 256
Swap(S[i],S[j])
Return S
偽隨機數生成算法:
Input: S盒
Output：生成的密鑰流
i=0
j=0
while GeneratingOuput
I = (i+1) mod 256
j = (j+S[i]) mod 256
Swap（S[i],S[j]）
Z = S[ (S[i]+S[j]) mod 256]
Output z
密鑰key實際可用的長度最大為256字節，但典型的長度是40-128 bit。
Rc4的最初若干字節密鑰流的非均勻分布
在密鑰隨機的前提下，如果密鑰流是均勻的話，每個字節出現的概率應該是1/256=0.3906%,但從理論分析和實驗結果來看，密鑰流某些位置上的某些字節出現的概率要明顯高于(或低于)其他字節，即偏移（biase）
RC4單字節偏移現象最初由Mantin and Shamir等人發現。他們指出密鑰流的第二個字節,Z2=0的概率約為1/128,而不是1/256
在S盒初始化結束，生成密鑰流的過程中，假設S2=0,S1=X≠2,S[X]=Y,根據偽隨機數生成算法，第一輪，S[X]和S1互換，生成的密鑰字節是S[X+Y];第二輪，S2和S[X]互換，生成的密鑰字節是S[X]=0，即Z2=0。
由條件概率公式，計算出z2=0的概率約為1/128
P[z2 = 0] = P[z2 = 0|S[2]= 0] * P[S[2]= 0]
+ P[z2 = 0|S[2] ≠ 0] * P[S[2] ≠ 0]
≈ 1*1/256 + 1/256*(1-1/256)
≈ 1/128
實驗結果表明其他位置處的密鑰字節也存在偏移現象。
單字節偏移的局限性在于偏移現象只在初始的約256個字節出現。
多字節偏移又稱long term biase,一些字節對出現的概率高于其他字節，會在密鑰流中周期性的出現，最初由Fluhrer 和McGrew等人發現。
2015年Mathy Vanhoef及Frank Piessens發表了對RC4新的攻擊方法，他們發現了新的偏移，只需要約9*2^27個密文就可以使cookie破解成功率達到94%，破解時間為75小時。這是第一個被證實可行的此類攻擊。他們的論文《All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS》發表在USENIX Security2015，并被評為Best Student Paper
學過概率與統計課程的同學應該對下面的題目有印象
“隨機拋n次硬幣，求恰好出現m次正面向上的概率”
這個概率符合二項分布，每次實驗只有兩種可能的結果。二項分布的名字來源于其概率公式符合二項展開的公式。
每次實驗，兩種結果出現的概率分別為a和b，重復實驗n次，展開式中的每一項都是一個獨立事件，如n*a^(n-1)*b表示第一種結果發生了n-1次，第二種結果發生了1次，這個現象發生的概率是n*a^(n-1)*b
將兩種結果推廣到更多的結果，就產生了多項分布。
“隨機拋n次正方體骰子，點數1-6出現的次數分別為(x1,x2,x3,x4,x5,x6)的概率是多少,其中x1+x2+x3+x4+x5+x6=n”
更一般的情況是不規則的骰子。這種概率仍然符合多項展開公式
基于概率論的相關公式，我們就可以利用RC4密鑰流中的偏移特性，對明文某一字節出現的概率進行計算，從而攻破RC4.
在預處理階段，通過大量的實驗，生成隨機的key，統計密鑰流中各字節出現的概率，類似求出前面多項展開式中的p1，p2
在獲取密文階段，通過一些手段，不斷用RC4加密同樣的明文，記錄出現的密文.類似求出前面多項展開式中的n1，n2
最后，計算明文各個字節的概率，從概率較高的候選字節中恢復明文。
最后給出針對單字節偏移的明文概率估計的整體算法。
實驗結果：當搜集的密文數為2^26時，前96個字節恢復的概率均超過50%；當密文數為2^32時，恢復的概率基本為100%。
對于多字節偏移，還要用到更加復雜的概率公式，在此就不詳細介紹了，但總體的思路還是一樣的。此外，針對HTTP cookie，有簡化運算的條件，如cookie字段總是以“Cookie:”開頭，以換行符結尾，大部分cookie中的字符都是16進制字符。有興趣的同學可以參考USENIX security2013年的論文《On the Security of RC4 in TLS and WPA》
或許有人會說，“既然密鑰流初始的若干字節有偏移問題，拋棄那些字節不就可以繼續用了么？”的確，RC4后來也出現了拋棄初始字節的版本RC4-drop N,但有問題的原始版本已經被大范圍實現和部署，RC4的速度優勢在當今硬件條件下也不是特別重要，因此TLS協議放棄RC4是一個方便、安全的選擇。