RC4

暗号学において、RC4 （Rivest Cipher 4、 ARC4またはARCFOURとも呼ばれ、Alleged RC4の略、下記参照）はストリーム暗号である。ソフトウェアにおけるシンプルさと速度で注目に値するが、RC4には複数の脆弱性が発見されており、安全ではない。^{[3] [4]出力}キーストリームの先頭が破棄されていない場合や、非ランダムまたは関連キーが使用されている場合に特に脆弱である。RC4の特に問題のある使用法は、 WEPなどの非常に安全でないプロトコルにつながっている。^[5]

2015年現在、一部の国家暗号機関がTLSプロトコル^{[アップデート]}で使用されるRC4を解読する能力を持っている可能性があるという憶測があります。^[6] IETFはTLSでのRC4の使用を禁止するRFC 7465を発行しました。^[3] MozillaとMicrosoftも同様の勧告を出しています。^{[7] [8]}

RC4 を強化するための試みは数多く行われており、特に Spritz、RC4A、VMPC、RC4 ^{+ が}有名です。

RC4は1987年にRSAセキュリティのロン・リベストによって設計されました。正式には「Rivest Cipher 4」と呼ばれていますが、RCの頭字語は「Ron's Code」の略とも解釈されています^{[9] （} RC2、RC5、RC6も参照）。

RC4 は当初企業秘密であったが、1994 年 9 月にその説明が匿名でCypherpunksメーリング リストに投稿された。^[10]これはすぐにsci.crypt ニュース グループに投稿され、数日のうちにBob Jenkinsによって解読された。^{[11]そこからインターネット上の多くのサイトに広まった。漏洩したコードは、その出力がライセンスされた}RC4を使用するプロプライエタリ ソフトウェアの出力と一致することが判明したため、本物であることが確認された。アルゴリズムが知られているため、もはや企業秘密ではない。RC4 という名前は商標登録されているため、商標の問題を避けるために、 RC4 はARCFOURまたはARC4 (疑惑の RC4を意味する) ^[12]と呼ばれることが多い。RSA Security はアルゴリズムを公式に公開したことはないが、Rivest は2008 年の自身の講義ノートで RC4 に関する英語版 Wikipedia の記事にリンクし^[13]、2014 年の自身の論文で RC4 とそのコードの歴史を確認した。^[14]

RC4 は、1997 年のWEP 、 2003/2004 年のワイヤレス カード向けWPA 、 1995 年のSSL 、 1999 年の後継TLSなど、一般的に使用される暗号化プロトコルや標準の一部になりましたが、SSL/TLS で使用される RC4 がRC4 攻撃によって弱体化または破壊されたため、2015 年に RFC 7465 によってすべてのバージョンの TLS で禁止されました。RC4 が幅広いアプリケーションで成功した主な要因は、その速度とシンプルさです。ソフトウェアとハ​​ードウェアの両方で効率的な実装を開発するのは非常に簡単でした。

RC4 は、疑似ランダム ビット ストリーム(キー ストリーム) を生成します。他のストリーム暗号と同様に、ビット単位の排他的論理和を使用してプレーンテキストと組み合わせることで、暗号化に使用できます。復号化も同じ方法で実行されます (指定されたデータとの排他的論理和は反転であるため)。これは、準備されたストリームではなく、 生成された疑似ランダム ビットが使用される点を除いて、ワンタイム パッドに似ています。

キーストリームを生成するために、暗号は次の 2 つの部分で構成される秘密の内部状態を利用します。

1. 可能な 256バイトすべての順列(以下では「S」で示されます)。
2. 2 つの 8 ビット インデックス ポインター (「i」と「j」で示される)。

順列は、キー スケジューリングアルゴリズム (KSA)を使用して、通常 40 ～ 2048 ビットの可変長キーで初期化されます。これが完了すると、疑似乱数生成アルゴリズム(PRGA)を使用してビット ストリームが生成されます。

キースケジューリングアルゴリズムは、配列 "S" 内の順列を初期化するために使用されます。"keylength" はキーのバイト数として定義され、1 ≤ keylength ≤ 256 の範囲で指定できます。通常は 5 から 16 の間で、 40 から 128 ビットのキー長に相当します。まず、配列 "S" が恒等順列に初期化されます。次に、メイン PRGA と同様の方法で S を 256 回繰り返して処理しますが、同時にキーのバイトも混合します。

iは0から255まで
    S[i] := i
終わり
0 := 0 です
iは0から255まで
    j := (j + S[i] + key[i mod keylength]) mod 256
    S[i]とS[j]の値を交換する
終わり

必要な回数だけ繰り返し、PRGA は状態を変更し、キーストリームのバイトを出力します。各繰り返しで、PRGA は次の処理を実行します。

• i を増分します。
• Sのi番目の要素S[ i ]を検索し、それをjに追加します。
• S[ i ]とS[ j ]の値を交換し、合計S[ i ] + S[ j ] (モジュロ256)をインデックスとして使用して、 Sの3番目の要素(以下のキーストリーム値K ) を取得します。
• 次に、メッセージの次のバイトとビット単位の排他的論理和 ( XOR ) をとって、暗号文または平文の次のバイトを生成します。

S の各要素は、256 回の反復ごとに少なくとも 1 回、別の要素と交換されます。

私 := 0
0 := 0 です
出力を生成中:
    i := (i + 1) を 256 で割ったもの
    j := (j + S[i]) 法 256
    S[i]とS[j]の値を交換する
    t := (S[i] + S[j]) を 256 で割ったもの
    K := S[t]
    出力K
終わりまで

これにより、 K[0]、K[1]、...のストリームが生成され、平文とXORされて暗号文が得られます。つまり、暗号文[ l ] = 平文[ l ] ⊕ K[ l ]です。

いくつかのオペレーティングシステムには、 OpenBSDarc4random発祥の APIである が含まれており、RC4 をベースとした乱数ジェネレータへのアクセスを提供します。この API では、関数が/dev/random を使用して初期化されるため、シードは許可されません。この API を実装しているほとんどのシステムでは、RC4 の使用は段階的に廃止されています。新しい arc4random のマニュアルページには、ARC4 の略語である「A Replacement Call for Random」がニーモニックとして含まれています。これは、 rand()よりも優れたランダムデータを提供するためです。^[15]

• 2014年5月にリリースされたOpenBSD 5.5では、ChaCha20をarc4random使用するように変更されました。^{[16] [17]} FreeBSD、NetBSDのarc4randomの実装^{[18] [19]}もChaCha20を使用しています。
  • Linuxは通常glibcを使用しますが、2022年までarc4randomは提供されていませんでした。代わりに、別のライブラリlibbsdがこの関数を提供しており、2016年にChaCha20を使用するように更新されました。 ^[20] 2022年に、glibcはChaCha20をベースにした独自のarc4randomバージョンを追加しました。^[21]
• オペレーティング システムに同梱されているマニュアル ページによると、2017 年リリースのmacOSおよびiOSオペレーティング システムでは、Apple は arc4random の実装で RC4 を AES に置き換えました。

提案されている新しい乱数生成器は、RC4乱数生成器とよく比較されます。^{[22] [23]}

RC4に対するいくつかの攻撃は、その出力をランダムシーケンスと区別することができます。^[24]

多くのストリーム暗号は線形フィードバックシフトレジスタ(LFSR)に基づいていますが、これはハードウェアでは効率的ですが、ソフトウェアではそれほど効率的ではありません。RC4 の設計では LFSR の使用を避けており、バイト操作のみを必要とするためソフトウェア実装に最適です。RC4 では、状態配列 S[0] から S[255] に 256 バイトのメモリ、キー key[0] から key[k−1] に k バイトのメモリ、および整数変数 i、j、K を使用します。256 を法とする値のモジュラー減算は、255とのビット単位の ANDで実行できます(これは、問題の値の下位バイトを取得することと同じです)。

これらのテスト ベクトルは公式ではありませんが、独自の RC4 プログラムをテストする人にとっては便利です。キーとプレーン テキストはASCIIで、キー ストリームと暗号テキストは16 進数です。

RC4 は、現代のストリーム暗号 ( eSTREAMのものなど) とは異なり、キーとともに別のnonce を必要としません。つまり、1 つの長期キーを使用して複数のストリームを安全に暗号化する場合、プロトコルは nonce と長期キーを組み合わせて RC4 のストリーム キーを生成する方法を指定する必要があります。これに対処する 1 つの方法は、長期キーをnonceでハッシュして「新しい」RC4 キーを生成することです。ただし、RC4 を使用する多くのアプリケーションは、キーと nonce を単純に連結します。RC4 の弱いキー スケジュールにより、 Fluhrer、Mantin、Shamir 攻撃( WEP標準を破ったことで有名)などの関連キー攻撃が発生します。^[25]

RC4はストリーム暗号であるため、一般的なブロック暗号よりも柔軟性があります。強力なメッセージ認証コード（MAC）と一緒に使用しないと、暗号化はビット反転攻撃に対して脆弱になります。また、この暗号は、正しく実装されていない場合、ストリーム暗号攻撃に対しても脆弱です。 ^[26]

しかし、注目すべきは、RC4はストリーム暗号であるため、TLS 1.0に対する2011年のBEAST攻撃に対して耐性を持つ唯一の一般的な暗号であった時期があったことです^{[27] 。この攻撃は、TLS 1.0でサポートされている他のすべての暗号（すべてブロック暗号）で}暗号ブロック連鎖モードが使用される方法 の既知の弱点を悪用します。

2013年3月には、磯部、大東、渡辺、森井^[28]やアルファルダン、バーンスタイン、パターソン、ポエタリング、シュルトらによって、RC4鍵表^[29]の新しい統計的バイアスを利用して、多数のTLS暗号化による平文を復元する新しい攻撃シナリオが提案された^{[30] [31] 。}

TLS での RC4 の使用は、2015 年 2 月に公開された RFC 7465 によって禁止されています。

1995 年、Andrew Roos は、キーストリームの最初のバイトがキーの最初の 3 バイトと相関しており、KSA 後の順列の最初の数バイトがキー バイトの何らかの線形結合と相関していることを実験的に観察しました。 ^{[32]これらのバイアスは、2007 年に Goutam Paul、Siddheshwar Rathi、Subhamoy Maitra [33]}がキーストリームとキーの相関を証明し、別の研究で Goutam Paul と Subhamoy Maitra ^{[34] が}順列とキーの相関を証明したときまで説明されませんでした。後者の研究でも、順列とキーの相関を使用して、キーまたは初期化ベクトルに関する仮定なしに、KSA 後の最終順列から完全なキーを再構築する最初のアルゴリズムを設計しました。このアルゴリズムは、時間内に成功する確率が一定であり、これは網羅的なキー検索の複雑さの平方根です。その後、RC4 の内部状態からのキー再構築に関する他の多くの研究が行われてきました。^{[35] [36] [37]} Subhamoy MaitraとGoutam Paul ^[38]も、S[S[i]]やS[S[S[i]]]のような入れ子になった順列インデックスを考慮した場合でも、Roos型のバイアスが依然として残ることを示しました。これらのタイプのバイアスは、成功確率を高めるために、後のいくつかの重要な再構成方法で使用されます。

RC4 によって生成されるキーストリームは、特定のシーケンスに対してさまざまな程度に偏っており、識別攻撃に対して脆弱です。そのような攻撃の最も優れた例は、Itsik Mantin とAdi Shamirによるもので、暗号の 2 番目の出力バイトが 1/128 の確率 (1/256 ではなく) でゼロに偏っていることを示しました。これは、元の状態の 3 番目のバイトがゼロで、2 番目のバイトが 2 でない場合、2 番目の出力バイトは常にゼロになるという事実によるものです。このような偏りは、256 バイトを観察するだけで検出できます。^[24]

COSICのソウラデュティ・ポールとバート・プレニールは、 RC4の1バイト目と2バイト目も偏っていることを示しました。この偏りを検出するために必要なサンプル数は225^バイトです 。^[39]

スコット・フルラーとデビッド・マクグルーは、1ギガバイトの出力を与えられたRC4のキーストリームとランダムストリームを区別する攻撃も示した。^[40]

RC4 PRGAの単一ステップの完全な特性評価は、Riddhipratim Basu、Shirshendu Ganguly、Subhamoy Maitra、およびGoutam Paulによって実行されました。^[41]すべての順列を考慮すると、iとjが与えられた場合の出力の分布は均一ではなく、結果としてjに関する情報は常に出力に漏れていることを証明しました。

2001 年、Fluhrer、Mantin、 Shamirによって、新しく驚くべき発見がなされました。考えられるすべての RC4 キーについて、出力キーストリームの最初の数バイトの統計は、非常に非ランダムであり、キーに関する情報が漏洩します。ノンス キーと長期キーを単純に連結して RC4 キーを生成すると、このキーで暗号化された多数のメッセージを分析することで、この長期キーを発見できます。^[42]この効果と関連する効果は、802.11ワイヤレス ネットワークで使用されるWEP (「有線同等プライバシー」) 暗号化を破るために使用されました。これにより、802.11 市場では WEP の標準ベースの代替品を求める争いが起こり、IEEE 802.11i の取り組みとWPAにつながりました。^[43]

プロトコルは、キーストリームの最初の部分を破棄することでこの攻撃を防御できます。このような修正されたアルゴリズムは、伝統的に「RC4-drop[ n ]」と呼ばれています。ここで、nは破棄される最初のキーストリームバイトの数です。SCANのデフォルトはn = 768バイトですが、控えめな値はn = 3072バイトです。^[44]

Fluhrer、Mantin、Shamirの攻撃はRC4ベースのSSLには当てはまりません。SSLはRC4に使用する暗号化キーをハッシュによって生成するため、異なるSSLセッションには無関係なキーが存在することになります。^[45]

2005年、アンドレアス・クラインはRC4ストリーム暗号の分析を発表し、RC4キーストリームとキーの間により多くの相関関係があることを示しました。^[46]エリック・テウス、ラルフ・フィリップ・ウェインマン、アンドレイ・ピチキンはこの分析を使用して、128ビットWEPで使用される104ビットRC4を1分以内に解読するツールであるaircrack-ptwを作成しました。^[47] Fluhrer、Mantin、およびShamirの攻撃では約1000万のメッセージが使用されましたが、aircrack-ptwは40,000フレームで50%の確率で、または85,000フレームで95%の確率で104ビットキーを解読できます。

RC4 暗号の入力と出力の数に関する組み合わせ問題は、2001 年にItsik Mantin とAdi Shamirによって初めて提起されました。それによると、RC4 の典型的な状態にある合計 256 個の要素のうち、 x個の要素 ( x ≤ 256)のみがわかっている場合 (他のすべての要素は空であると想定できます)、次の 256 ラウンドで決定論的に生成できる要素の最大数もxになります。この予想は、2004 年にSouradyuti PaulとBart Preneelによって正式な証明が示され、解決されました。^[48]

2013年、ロンドン大学ロイヤル・ホロウェイ校の情報セキュリティグループのセキュリティ研究者グループは、わずか2 ^{34 の}暗号化メッセージを使用して有効になる攻撃を報告しました。^{[49] [50] [51]}ほとんどの目的にとってまだ実用的な攻撃ではありませんが、この結果は実際の攻撃に十分近いため、一部の国家暗号機関がすでにRC4を安全でないものにするより優れた攻撃を持っている可能性があるという推測につながっています。^[6] 2013年時点で^{[アップデート]}、大量のTLSトラフィックが暗号ブロック連鎖を使用するブロック暗号への攻撃を回避するためにRC4を使用していることを考えると、これらの仮想的なより優れた攻撃が存在する場合、多くの実用的なシナリオでTLSとRC4の組み合わせはそのような攻撃者に対して安全でないことになります。^[6]

2015年3月、ロイヤル・ホロウェイの研究者は、TLSで使用されるRC4で暗号化されたパスワードに対する2 ²⁶攻撃を提供し、攻撃の改良を発表しました。 ^[52]

ブラックハットアジア2015カンファレンスで、イツィク・マンティンはRC4暗号を使用したSSLに対する別の攻撃を発表しました。^{[53] [54]}

2015年、ルーヴェン・カトリック大学のセキュリティ研究者は、 TLSとWPA-TKIPの両方でRC4に対する新しい攻撃を発表しました。^[55]これは、Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE)攻撃と呼ばれ、実際に実証された初めての攻撃です。TLSに対する攻撃では、 75時間以内に安全なHTTP Cookieを復号化できます。WPA- TKIPに対する攻撃は1時間以内に完了し、攻撃者は任意のパケットを復号化して挿入することができます。

上で述べたように、RC4の最も重要な弱点は不十分なキースケジュールから来ています。出力の最初のバイトはキーに関する情報を明らかにします。これは、出力ストリームの最初の部分を破棄するだけで修正できます。^[56]これはRC4ドロップNとして知られており、Nは通常768や1024などの256の倍数です。

RC4 を強化するための試みは数多く行われており、特に Spritz、RC4A、VMPC、RC4 ^{+ が}有名です。

ソウラデュティ・ポールとバート・プレニールはRC4の変種を提案し、RC4Aと呼んでいる。^[57]

RC4A は 2 つの状態配列S1とS2、および 2 つのインデックスj1とj2を使用します。iが増加するたびに、2 つのバイトが生成されます。

1. まず、基本的なRC4アルゴリズムがS1とj1を使用して実行されますが、最後のステップでは、S1[ i ]+S1[ j1 ]がS2で検索されます。
2. 次に、 S2とj2に対して（ iを再度増分せずに）操作が繰り返され、S1[S2[ i ]+S2[ j2 ]]が出力されます。

したがって、アルゴリズムは次のようになります。

すべての演算は256を法として実行されます
私 := 0
j1 := 0
j2 := 0
出力を生成中:
    私 := 私 + 1
    j1 := j1 + S1[i]
    S1[i]とS1[j1]の
    値を入れ替え、 S2[S1[i] + S1[j1]]を出力する。
    j2 := j2 + S2[i]
    S2[i]とS2[j2]の値を交換する
    出力S1[S2[i] + S2[j2]]
 endwhile

このアルゴリズムでは出力バイトごとに同じ数の操作が必要ですが、RC4 よりも並列性が高く、速度が向上する可能性があります。

RC4よりも強力ではあるが、このアルゴリズムも攻撃されており、Alexander Maximov ^[58]とNECのチーム^[59]は、その出力を真にランダムなシーケンスと区別する方法を開発している。

可変修正順列合成（VMPC）は、別のRC4の変種である。^[60]これはRC4と同様の鍵スケジュールを使用し、 j := S[(j + S[i] + key[i mod keylength]) mod 256]を256回ではなく3 × 256 = 768回繰り返し、オプションで初期ベクトルを組み込むためにさらに768回の反復を行う。出力生成関数は次のように動作する。

すべての演算は 256 を法として実行されます。
私 := 0
出力を生成中:
    a := S[i]
    j := S[j + a]
    
    出力S[S[S[j] + 1]]
    S[i]とS[j]を入れ替える          （b:=S[j];S[i]:=b;S[j]:=a）
    
    私 := 私 + 1
終わりまで

^{これはRC4Aと同じ論文で攻撃されており、 238}出力バイト以内で区別できる。 ^{[61] [59]}

RC4 ⁺は、より複雑な3段階のキースケジュール（RC4の約3倍、またはRC4-drop512と同じ時間がかかります）と、各バイト出力に対してS配列で4回の追加ルックアップを実行するより複雑な出力関数を備えたRC4の修正版であり、基本的なRC4の約1.7倍の時間がかかります。^[62]

すべての算術演算は256を法とします。   <<と>>は左シフトと右シフト、 ⊕ は排他的論理和です。
出力を生成します。
    私 := 私 + 1
    a := S[i]
    j := j + a
    
    S[i]とS[j]を入れ替える               （b:=S[j];S[j]:=S[i];S[i]:=b;）
    
    c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3]
    出力(S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]
 endwhile

このアルゴリズムは十分に分析されていません。

2014年にロナルド・リベストはSpritzと呼ばれる更新された再設計に関する講演を行い、論文^{[14]を共同執筆しました。Spritzのハードウェアアクセラレータは2016年のSecrypt [63]}で公開され、出力バイトを生成するために複数のネストされた呼び出しが必要なため、SHA-3やRC4の最もよく知られているハードウェア実装などの他のハッシュ関数と比較して、Spritzのパフォーマンスがかなり遅いことを示しています。

他のスポンジ関数と同様に、Spritzは暗号ハッシュ関数、決定論的乱数ビットジェネレータ（ DRBG ）、関連データによる認証暗号化（AEAD）をサポートする暗号化アルゴリズムなどを構築するために使用できます。 ^[14]

2016年に、BanikとIsobeはSpritzをランダムノイズと区別できる攻撃を提案した。^[64] 2017年に、Banik、Isobe、Moriiは、最初の2つのキーストリームバイトの識別子を削除する簡単な修正を提案した。これにより、ソフトウェアのパフォーマンスを大幅に低下させることなく、1回の追加メモリアクセスのみが必要になる。^[65]

• ウェブ
• TKIP ( WPAのデフォルトアルゴリズムですが、 RC4 の代わりにAES-CCMP を使用するように設定できます)
• BitTorrent プロトコル暗号化
• Microsoft Office XP（文書が変更されてもノンスが変更されないため、安全でない実装^[66]）
• Microsoft ポイントツーポイント暗号化
• トランスポート層セキュリティ/セキュア ソケット レイヤー(以前はオプションでしたが、RFC 7465 では RC4 の使用が禁止されました)
• セキュア シェル(オプション)
• リモート デスクトップ プロトコル(オプション)
• Kerberos (オプション)
• SASLメカニズム ダイジェスト MD5 (オプション、歴史的、RFC 6331 で廃止)
• Gpcode.AK は、2008 年 6 月初旬に Microsoft Windows を標的としたコンピュータ ウイルスで、RC4 および RSA-1024 暗号化で文書を隠蔽して人質に取り、身代金を要求する。
• PDF
• Skype（改変版）^[67]

プロトコルに「(オプション)」とマークされている場合、RC4 はシステムで使用するように構成できる複数の暗号の 1 つです。

• TEA、ブロック TEA (eXtended TEAおよびCorrected Block TEAとも呼ばれる) は、RC4 と同様に実装が非常に簡単になるように設計されたブロック暗号のファミリです。
• 高度暗号化標準
• サイファーセイバー

• ポール、ゴータム、スバモイ・マイトラ（2011）。RC4 ストリーム暗号とその変種。CRC プレス。ISBN 9781439831359。
• Schneier, Bruce (1995)。「第 17 章-その他のストリーム暗号と実際のランダム シーケンス ジェネレーター」。応用暗号化: C 言語のプロトコル、アルゴリズム、ソース コード(第 2 版)。Wiley。ISBN 978-0471117094。

• Cypherpunks メーリング リストへの RC4 アルゴリズムのオリジナル投稿、アーカイブ版
• RFC 4345 – セキュア シェル (SSH) トランスポート層プロトコルの改良された Arcfour モード
• RFC 6229 – ストリーム暗号 RC4 のテストベクトル
• RFC 7465 – RC4 暗号スイートの禁止
• カウコネン。セイヤー。ストリーム暗号暗号化アルゴリズム「Arcfour」。 ID ドラフト-kaukonen-cipher-arcfour-03。
• SCANのRC4へのエントリー
• Wayback Machineでの RC4 への攻撃(2015 年 2 月 21 日アーカイブ)
• RC4 のキー スケジューリング アルゴリズムの脆弱性に対する RSA セキュリティの対応

WEP の RC4

• WEPアルゴリズムのセキュリティ
• Fluhrer、Mantin、Shamir (2002年夏～秋)。「RC4とWEPへの攻撃」。CryptoBytes 5 (2) 。 2015年1月2日時点のオリジナル(PostScript)からのアーカイブ。