Loading article…
暗号学において、RC4 （ ARC4またはARCFOURとも呼ばれ、Alleged RC4の略、下記参照）はストリーム暗号です。ソフトウェアではそのシンプルさと速度が際立っていますが、RC4には複数の脆弱性が発見されており、安全性が損なわれています。[ 3 ] [ 4 ]特に、出力キーストリームの先頭が破棄されない場合、または非ランダムなキーや関連キーが使用される場合に脆弱です。RC4の特に問題のある使用法は、かつてWiFiネットワークのセキュリティ確保に使用されていた旧式のWEPプロトコルなどの安全性の低いプロトコルにつながっています。[ 5 ]
TLS プロトコルで使用される RC4 を解読する能力を一部の国家暗号機関が持っている可能性があるという憶測が長らくあった。[ 6 ]これに対し、IETF はRFC 7465を公開し、TLS での RC4 の使用を禁止した。[ 3 ] MozillaとMicrosoftも同様の勧告を出している。[ 7 ] [ 8 ]
RC4を強化するための試みが数多く行われており、特にSpritz、RC4A、VMPC、RC4 +などが挙げられる。
RC4は、1987年にRSA Securityのロナルド・リベストによって設計されたストリーム暗号です。リベストによれば、RCは「Ron's Code」の略ですが[ 9 ]、一般的には単にRC4と呼ばれています。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は、無線LANカード向けの1997年のWEPや2003/2004年のWPA、1995年のSSL 、そして1999年の後継であるTLSなど、一般的に使用されている暗号化プロトコルや標準の一部となりました。しかし、SSL/TLSで使用されるRC4がRC4攻撃によって弱体化または破られることが判明したため、2015年にRFC 7465によってTLSのすべてのバージョンでRC4の使用が禁止されました。RC4がこれほど幅広いアプリケーションで成功を収めた主な要因は、その速度とシンプルさにあります。ソフトウェアとハードウェアの両方で効率的な実装が非常に容易に開発できたのです。
RC4は擬似乱数ビットストリーム（キーストリーム）を生成します。他のストリーム暗号と同様に、これらはビットごとの排他的論理和を使用して平文と組み合わせることで暗号化に使用できます。復号化も同様に行われます（与えられたデータとの排他的論理和は対合であるため）。これはワンタイムパッドに似ていますが、準備されたストリームではなく、生成された擬似乱数ビットが使用される点が異なります。
キーストリームを生成するために、暗号は2つの部分からなる秘密の内部状態を利用します。
順列は、キースケジューリングアルゴリズム（KSA）を用いて、通常40～2048ビットの可変長キーで初期化されます。これが完了すると、擬似乱数生成アルゴリズム（PRGA）を用いてビット列が生成されます。
キースケジューリングアルゴリズムは、配列「S」内の置換を初期化するために使用されます。「keylength」はキーのバイト数として定義され、1 ≤ keylength ≤ 256 の範囲で、通常は 5 ～ 16 であり、40 ～ 128 ビットのキー長 に対応します。まず、配列「S」は恒等置換で初期化されます。次に、S はメインの PRGA と同様の方法で 256 回処理されますが、同時にキーのバイトも混合されます。「Text」や「TextText」など、多くの異なるキーが同じ暗号につながることに注意してください。
iが0から255まで S[i] := i endfor j := 0 iが0から255まで j := (j + S[i] + key[i mod keylength]) mod 256 S[i]とS[j]の値を交換する endfor
必要な回数だけ反復処理を行い、PRGAは状態を変更し、キーストリームの1バイトを出力します。各反復処理において、PRGAは次の処理を行います。
Sの各要素は、少なくとも256回の反復ごとに1回は他の要素と交換される。
i := 0 j := 0 出力生成中: i := (i + 1) mod 256 j := (j + S[i]) mod 256 S[i]とS[j]の値を交換する t := (S[i] + S[j]) mod 256 K := S[t] 出力K endwhile
したがって、これによりK[0]、K[1]、...のストリームが生成され、これらが平文とXOR されて暗号文が得られます。つまり、ciphertext[ l ] = plaintext[ l ] ⊕ K[ l ]となります。
いくつかのオペレーティングシステムには、元々は RC4 に基づいていた乱数生成器へのアクセスを提供するOpenBSDarc4random由来の APIが含まれています。この API は、 /dev/randomを使用して関数を初期化するため、シードを許可しません。この API を実装しているほとんどのシステムでは、RC4 の使用は段階的に廃止されています。新しい arc4random のman ページには、ARC4 の頭字語「A Replacement Call for Random」がニーモニックとして含まれています。これは、32 ビットの内部状態を持つ線形合同擬似乱数生成器に基づく元の非常に安全性の低いrand()関数よりも優れた乱数データを提供したためです。[ 15 ] [ 16 ] [ 17 ]
RC4に対するいくつかの攻撃は、その出力をランダムなシーケンスから区別することができる。[ 18 ]その結果、ARC4の使用はarc4random最終的に、より優れた擬似乱数生成器に置き換えられた。
arc4randomより優れたストリーム暗号ChaCha20を使用するように変更されました。[ 19 ] [ 20 ] FreeBSD、NetBSD [ 21 ] [ 22 ]のarc4randomの実装もChaCha20を使用しています。多くのストリーム暗号は線形フィードバックシフトレジスタ（LFSR）に基づいていますが、これはハードウェアでは効率的であるものの、ソフトウェアではそれほど効率的ではありません。RC4の設計ではLFSRの使用を避けており、バイト操作のみを必要とするため、ソフトウェア実装に最適です。状態配列S[0]からS[255]に256バイトのメモリ、鍵key[0]からkey[k-1]にkバイトのメモリ、および整数変数i、j、Kを使用します。ある値を256で割った余りを求めるには、 255とのビットごとのAND演算（これは、問題の値の下位バイトを取ることと同等です）で行うことができます。
これらのテストベクトルは公式のものではありませんが、独自のRC4プログラムをテストする際に便利です。鍵と平文はASCII形式、キーストリームと暗号文は16進数です。
現代のストリーム暗号（ eSTREAMなど）とは異なり、RC4 は鍵とは別にnonce を必要としません。つまり、単一の長期鍵を使用して複数のストリームを安全に暗号化する場合、プロトコルは nonce と長期鍵を組み合わせて RC4 のストリーム鍵を生成する方法を規定する必要があります。この問題を解決する 1 つの方法は、長期鍵とnonceをハッシュ化して「新しい」 RC4 鍵を生成することです。しかし、RC4 を使用する多くのアプリケーションは、鍵と nonce を単純に連結します。その結果、RC4 の脆弱な鍵スケジュールにより、Fluhrer、Mantin、Shamir 攻撃（ WEP標準を破ったことで有名）のような関連鍵攻撃が発生します。[ 27 ]
RC4はストリーム暗号であるため、一般的なブロック暗号よりも柔軟性が高い。強力なメッセージ認証コード（MAC）と併用しない場合、暗号化はビット反転攻撃に対して脆弱になる。また、正しく実装されていない場合は、ストリーム暗号攻撃に対しても脆弱になる。[ 28 ]
しかし、RC4はストリーム暗号であるため、TLS 1.0に対する2011年のBEAST攻撃[ 29 ]に対して耐性のある唯一の一般的な暗号であったことは注目に値する。この攻撃は、TLS 1.0でサポートされている他のすべての暗号（すべてブロック暗号）で暗号ブロック連鎖モードが使用される方法の既知の脆弱性を悪用する。
2013 年 3 月には、磯部、大東、渡辺、森井[ 30 ]および AlFardan、Bernstein、Paterson、Poettering、Schuldt らによって、多数の TLS 暗号化を使用して平文を復元するために RC4 キー テーブルの新しい統計的バイアス[ 31 ]を使用する新しい攻撃シナリオが提案されました。[ 32 ] [ 33 ]
TLSにおけるRC4の使用は、2015年2月に公開されたRFC 7465によって禁止されています。
1995 年、Andrew Roos は、キーストリームの最初のバイトがキーの最初の 3 バイトと相関があり、KSA 後の順列の最初の数バイトがキー バイトの線形結合と相関があることを実験的に観察しました。[ 34 ]これらのバイアスは、2007 年に Goutam Paul、Siddheshwar Rathi、Subhamoy Maitra [ 35 ]がキーストリームとキーの相関を証明し、別の研究で Goutam Paul と Subhamoy Maitra [ 36 ]が順列とキーの相関を証明するまで説明されませんでした。後者の研究では、キーや初期化ベクトルに関する仮定なしに、KSA 後の最終順列から完全なキーを復元するための最初のアルゴリズムを設計するために順列とキーの相関も使用しました。このアルゴリズムは、全数的なキー検索の複雑さの平方根である時間で一定の成功確率を持ちます。その後、RC4 の内部状態からのキー復元に関する他の多くの研究が行われました。[ 37 ] [ 38 ] [ 39 ] Subhamoy Maitra と Goutam Paul [ 40 ]は、 S[S[i]]やS[S[S[i]]]のような入れ子になった順列インデックスを考慮しても、Roos 型のバイアスが依然として存在することを示しました。これらのタイプのバイアスは、成功確率を高めるために、後の鍵再構成方法の一部で使用されています。
RC4 によって生成されるキーストリームは、さまざまな程度で特定のシーケンスに偏っており、識別攻撃に対して脆弱です。そのような攻撃の中で最も優れたものは、Itsik Mantin とAdi Shamirによるもので、彼らは、暗号の 2 番目の出力バイトが 1/128 (1/256 ではなく) の確率でゼロに偏っていることを示しました。これは、元の状態の 3 番目のバイトがゼロで、2 番目のバイトが 2 と等しくない場合、2 番目の出力バイトは常にゼロになるという事実によるものです。このような偏りは、256 バイトだけを観察することで検出できます。[ 18 ]
COSICのSouradyuti PaulとBart Preneelは、RC4の最初の2バイトにもバイアスがあることを示した。このバイアスを検出するために必要なサンプル数は2 25バイトである。[ 41 ]
スコット・フルーラーとデビッド・マクグルーも、1ギガバイトの出力が与えられた場合にRC4のキーストリームをランダムストリームから区別する攻撃を示した。[ 42 ]
RC4 PRGA の単一ステップの完全な特性評価は、Riddhipratim Basu、Shirshendu Ganguly、Subhamoy Maitra、および Goutam Paul によって行われました。[ 43 ]すべての順列を考慮すると、出力の分布は i と j が与えられた場合一様ではなく、結果として j に関する情報が常に出力に漏れることを証明しました。
2001年、 Fluhrer、Mantin、Shamirによって、驚くべき新たな発見がなされました。考えられるすべてのRC4キーについて、出力キーストリームの最初の数バイトの統計情報は非常に非ランダムであり、キーに関する情報が漏洩します。ノンスと長期キーを単純に連結してRC4キーを生成すると、このキーで暗号化された多数のメッセージを分析することで、この長期キーを発見できます。[ 44 ]この現象と関連する効果は、802.11無線ネットワークで使用されているWEP（「有線同等プライバシー」）暗号化を破るために利用されました。これにより、802.11市場でWEPに代わる標準ベースの代替手段を求める動きが起こり、IEEE 802.11iの取り組みとWPAにつながりました。[ 45 ]
プロトコルは、キーストリームの最初の部分を破棄することで、この攻撃から防御できます。このような修正されたアルゴリズムは、従来「RC4-drop[ n ]」と呼ばれ、nは破棄されるキーストリームの最初のバイト数です。SCAN のデフォルト値はn = 768バイトですが、保守的な値はn = 3072バイト です。[ 46 ]
Fluhrer、Mantin、Shamirの攻撃はRC4ベースのSSLには適用されません。なぜなら、SSLはRC4で使用する暗号化キーをハッシュ化によって生成するため、異なるSSLセッションは関連性のないキーを持つことになるからです。[ 47 ]
2005年、Andreas KleinはRC4ストリーム暗号の分析を発表し、RC4キーストリームと鍵の間により多くの相関関係があることを示しました。[ 48 ] Erik Tews、Ralf-Philipp Weinmann、およびAndrei Pychkineはこの分析を使用して、128ビットWEPで使用される104ビットRC4を1分未満で解読するツールaircrack-ptwを作成しました。[ 49 ] Fluhrer、Mantin、およびShamirの攻撃では約1000万のメッセージが使用されたのに対し 、aircrack-ptwは50%の確率で40,000フレーム、または95%の確率で85,000フレームで104ビット鍵を解読できます。
RC4暗号の入力と出力の数に関連する組み合わせ問題は、2001年にItsik MantinとAdi Shamirによって初めて提起されました。RC4の典型的な状態にある合計256個の要素のうち、 x個の要素（x ≤ 256）のみが既知である場合（他のすべての要素は空であると仮定できる）、次の256ラウンドで決定論的に生成できる要素の最大数もxになります。この予想は、2004年にSouradyuti PaulとBart Preneelによって正式な証明が与えられ、解決されました。[ 50 ]
2013年、ロンドン大学ロイヤルホロウェイ校の情報セキュリティグループのセキュリティ研究者グループが、わずか234個の暗号化メッセージで有効になる攻撃を報告した。[ 51 ] [ 52 ] [ 53 ]この攻撃は、ほとんどの用途ではまだ実用的ではないが、実用的攻撃に十分近いことから、一部の国家暗号機関がすでにRC4を安全でないものにするより優れた攻撃を持っている可能性があるという憶測につながっている。[ 6 ] 2013年のTLSトラフィックの大部分が、暗号ブロック連鎖を使用するブロック暗号への攻撃を回避するためにRC4を使用していたことを考えると、これらの仮説上のより優れた攻撃が存在する場合、一般的なTLS暗号化は、多くの実用的シナリオでそのような攻撃者に対して安全ではないことになる。[ 6 ]
2015年3月、ロイヤル・ホロウェイ大学の研究者らは、TLSで使用されているRC4で暗号化されたパスワードに対する2 26攻撃の改良を発表した。 [ 54 ]
Black Hat Asia 2015 カンファレンスで、Itsik Mantin は RC4 暗号を使用した SSL に対する別の攻撃を発表しました。[ 55 ] [ 56 ]
2015年、ルーヴェン・カトリック大学のセキュリティ研究者らは、 TLSとWPA-TKIPの両方でRC4に対する新たな攻撃を発表した。[ 57 ] NOMORE（Numerous Occurrence MOnitoring & Recovery Exploit）攻撃と呼ばれるこの攻撃は、実際に実証されたこの種の攻撃としては初めてのものである。TLSに対する攻撃では、75時間以内にセキュアなHTTP Cookieを復号できる 。WPA-TKIPに対する攻撃は1時間以内に完了し、攻撃者は任意のパケットを復号して挿入することができる。
前述のように、RC4 の最も重要な弱点は、鍵スケジュールが不十分なことにあります。出力の最初のバイトは鍵に関する情報を漏らします。これは、出力ストリームの最初の部分を破棄することで修正できます。[ 58 ]これは RC4-drop Nとして知られており、Nは通常 768 や 1024 など 256 の倍数です。
RC4を強化するための試みが数多く行われており、特にSpritz、RC4A、VMPC、RC4 +などが挙げられる。
Souradyuti PaulとBart PreneelはRC4の変種を提案しており、それをRC4Aと呼んでいる。[ 59 ]
RC4Aは、2つの状態配列S1とS2、および2つのインデックスj1とj2を使用します。iがインクリメントされるたびに、2バイトが生成されます。
したがって、アルゴリズムは次のようになります。
すべての演算は256を法として行われます。 i := 0 j1 := 0 j2 := 0 出力生成中: i := i + 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 [ 60 ]とNECのチーム[ 61 ]は、その出力を真のランダムシーケンスから区別する方法を開発している。
可変修正順列合成 (VMPC) は、RC4 の別のバリアントです。[ 62 ]これは RC4 と同様の鍵スケジュールを使用しますが、 j := S[(j + S[i] + key[i mod keylength]) mod 256]を 256 回ではなく 3 × 256 = 768 回繰り返し、オプションで初期ベクトルを組み込むための追加の 768 回繰り返します。出力生成関数は次のように動作します。
すべての演算は256を法として行われます。 i := 0 出力生成中: j := S[j + S[i]] 出力S[S[S[j]] + 1] S[i]とS[j]を交換する （b := S[j]; S[j] := S[i]; S[i] := b） i := i + 1 endwhile
RC4 +は、より複雑な 3 フェーズのキー スケジュール (RC4 の約 3 倍の時間、または RC4-drop512 と同じ) と、より複雑な出力関数を備えた RC4 の改良版であり、各バイト出力に対して S 配列で 4 つの追加ルックアップを実行するため、基本的な RC4 の約 1.7 倍の時間がかかります。[ 64 ]
すべての演算は256を法とします。 <<と>>は左シフトと右シフト、 ⊕は排他的論理和です。出力生成中: i := i + 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 [ 65 ]で発表され、出力バイトを生成するために複数のネストされた呼び出しが必要なため、SpritzはSHA-3などの他のハッシュ関数や、RC4の最もよく知られたハードウェア実装と比較してかなり遅いことが示された。
他のスポンジ関数と同様に、Spritz は暗号学的ハッシュ関数、決定論的乱数ビット生成器 ( DRBG )、認証付き暗号化と関連データ (AEAD) をサポートする暗号化アルゴリズムなどを構築するために使用できます。 [ 14 ]
2016年、BanikとIsobeは、Spritzをランダムノイズから区別できる攻撃を提案した。[ 66 ] 2017年、Banik、Isobe、Moriiは、キーストリームの最初の2バイトの識別情報を削除する簡単な修正を提案し、ソフトウェアのパフォーマンスを大幅に低下させることなく、追加のメモリアクセスを1回だけ必要とした。[ 67 ]
プロトコルに「（オプション）」と記載されている場合、RC4はシステムが設定して使用できる複数の暗号方式のうちの1つです。
用の ChaCha ベースの乱数生成器。
のレガシー arc4random(3) API を ChaCha20 PRF を使用して再実装し、スレッドごとの状態を持つ。
{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)