Loading article…
| セキュアハッシュアルゴリズム | |
|---|---|
| コンセプト | |
| ハッシュ関数、SHA、DSA | |
| 主な基準 | |
| SHA-0、SHA-1、SHA-2、SHA-3 | |
| 一般的な | |
|---|---|
| デザイナー | 国家安全保障局 |
| 初版 | 1993 (SHA-0)、 1995 (SHA-1) |
| シリーズ | ( SHA-0 )、SHA-1、SHA-2、SHA-3 |
| 認証 | FIPS PUB 180-4、CRYPTREC (監視) |
| 暗号の詳細 | |
| ダイジェストサイズ | 160ビット |
| ブロックサイズ | 512 ビット |
| 構造 | メルクル・ダムガルド建設 |
| ラウンド | 80 |
| 最高の公開暗号解読 | |
| 2011年にマーク・スティーブンスが行った攻撃では、2 60.3から 2 65.3 の操作の複雑さでハッシュ衝突が発生する可能性があります。[1]最初の公開衝突は2017年2月23日に発表されました。[2] SHA-1は長さ拡張攻撃を受けやすいです。 | |
暗号学において、SHA-1（セキュアハッシュアルゴリズム1）は、入力を受け取り、メッセージダイジェストと呼ばれる160ビット（20バイト）のハッシュ値（通常40桁の16進数で表現される）を生成するハッシュ関数である。これは米国国家安全保障局によって設計され、米国連邦情報処理標準である。[3]このアルゴリズムは暗号的に破られたことがあるが[4] [5] [6] [ 7] [8] [9] [10]、現在でも広く使用されている。
2005年以来、SHA-1は資金力のある敵に対して安全ではないと考えられてきました。[11] 2010年の時点で、多くの組織がその置き換えを推奨しています。[12] [10] [ 13] NISTは2011年にSHA-1の使用を正式に非推奨とし、2013年にはデジタル署名での使用を禁止し、2030年までに段階的に廃止すると宣言しました。[14] 2020年の時点で[アップデート]、 SHA-1に対する選択プレフィックス攻撃は実用的です。[6] [8]そのため、できるだけ早く製品からSHA-1を削除し、代わりにSHA-2またはSHA-3を使用することをお勧めします。デジタル署名にSHA-1が使用されている場合は、SHA-1の置き換えが急務です。
すべての主要なウェブブラウザベンダーは、2017年にSHA-1 SSL証明書の受け入れを停止しました。 [15] [9] [4] 2017年2月、CWIアムステルダムとGoogleは、SHA-1に対する衝突攻撃を実行し、同じSHA-1ハッシュを生成する2つの異なるPDFファイルを公開したことを発表しました。[16] [2]ただし、SHA-1はHMACに対して依然として安全です。[17]
マイクロソフトは2020年8月3日にWindows UpdateでのSHA-1コード署名のサポートを終了しました[18] 。これにより、 Windows 2000からVistaまでのWindowsや、Windows 2000 ServerからServer 2003までのWindows Serverバージョンなど、SHA-2に更新されていないWindowsのバージョンの更新サーバーも事実上終了しました。
発達
- A、B、C、D、E は状態の32 ビットワードです。
- F は変化する非線形関数です。
- はn桁左ビット回転を表します。
- n は操作ごとに異なります。
- W t はラウンドtの拡張メッセージワードです。
- K t はラウンドtのラウンド定数です。
2 32を法とする加算を表します。
SHA-1 は、MITのRonald L. RivestがMD2、MD4、およびMD5メッセージ ダイジェスト アルゴリズムの設計で使用した原理と同様の原理に基づいてメッセージ ダイジェストを生成しますが、より大きなハッシュ値 (128 ビットに対して 160 ビット) を生成します。
SHA-1は、米国政府のキャップストーンプロジェクトの一環として開発されました。[19]アルゴリズムの元の仕様は、1993年に米国政府標準化機関NIST（国立標準技術研究所）によってセキュアハッシュ標準、FIPS PUB 180というタイトルで公開されました。 [20] [21]このバージョンは現在、 SHA-0と呼ばれることが多いです。これは公開後まもなくNSAによって撤回され、1995年にFIPS PUB 180-1で公開され、一般的にSHA-1と呼ばれる改訂版に置き換えられました。SHA-1とSHA-0の違いは、圧縮機能のメッセージスケジュールにおけるビット単位のローテーションが1つだけあることです。NSAによると、これは暗号のセキュリティを低下させた元のアルゴリズムの欠陥を修正するために行われたとのことですが、それ以上の説明はされていません。[22] [23]公開されている技術では、2017年のSHA-1よりも前に、2004年にSHA-0の侵害が実証されています（「攻撃」を参照）。
アプリケーション
暗号化
SHA-1 は、 TLSやSSL、PGP、SSH、S/MIME、IPsecなど、広く使用されているセキュリティ アプリケーションやプロトコルの一部です。これらのアプリケーションはMD5も使用できます。MD5 と SHA-1 はどちらもMD4から派生したものです。
SHA-1 と SHA-2 は、機密扱いされていない機密情報を保護するために、他の暗号化アルゴリズムやプロトコル内での使用を含む、米国政府の特定のアプリケーションで使用することが法律で義務付けられているハッシュ アルゴリズムです。FIPS PUB 180-1 では、民間および商業組織による SHA-1 の採用と使用も推奨されています。SHA-1 はほとんどの政府用途から廃止されつつあります。米国国立標準技術研究所は、「連邦政府機関は、衝突耐性を必要とするアプリケーションでの SHA-1 の使用を可能な限り速やかに中止し、 2010 年以降はこれらのアプリケーションでSHA-2ファミリーのハッシュ関数を使用する必要があります」と述べています[24]。ただし、これは後に緩和され、古いデジタル署名とタイムスタンプの検証に SHA-1 を使用できるようになりました[24] 。
セキュア ハッシュ アルゴリズムが公開された主な動機は、それが組み込まれている デジタル署名標準でした。
SHA ハッシュ関数は、 SHACAL ブロック暗号の基礎として使用されています。
データの整合性
Git、Mercurial、Monotoneなどのリビジョン管理システムは、セキュリティのためではなく、リビジョンを識別し、偶発的な破損によってデータが変更されていないことを確認するために SHA-1 を使用します。Linus Torvalds は2007 年に Git について次のように述べています。
- ディスク破損や DRAM 破損など、何らかの問題があれば、Git はそれを検知します。これは「検知されるかどうか」という問題ではなく、保証です。悪意を持って攻撃する人がいることはあり得ます。しかし、彼らは成功しません。[...] 誰も SHA-1 を破ることができていませんが、重要なのは、Git に関する限り、SHA-1 はセキュリティ機能ではないということです。これは純粋に一貫性チェックです。セキュリティ部分は別の場所にあるため、多くの人は、Git が SHA-1 を使用し、SHA-1 は暗号的に安全なものに使用されているので、これは非常に重要なセキュリティ機能であると考えています。これはセキュリティとはまったく関係がなく、単に入手できる最高のハッシュです。...
- データを Git に保存しておけば、5 年後、つまりハードディスクから DVD や新しいテクノロジーに変換されてコピーされた後でも、取り出されたデータが保存したデータとまったく同じであることを 5 年後に確認できるという事実を信頼できます。 [...]
- 私がカーネルを気にしている理由の1つは、 BitKeeperサイトの1つに侵入があり、カーネルのソースコードリポジトリを破壊しようとした人がいることです。[25]
しかし、Gitは、衝突が発生した場合にオブジェクトの最も古いバージョンを常に保持することを優先し、攻撃者が密かにファイルを上書きするのを防ぐため、セキュリティ機能としてSHA-1の2番目のプリイメージ耐性を必要としません。 [26]既知の攻撃（2020年現在）も2番目のプリイメージ耐性を破ることはできません。[27]
暗号解読と検証
Lがメッセージ ダイジェストのビット数であるハッシュ関数の場合、与えられたメッセージ ダイジェストに対応するメッセージを見つけることは、約 2 L 回の評価でブルート フォース検索を使用して常に実行できます。これは原像攻撃と呼ばれ、 Lと特定のコンピューティング環境に応じて実用的である場合とそうでない場合があります。ただし、同じメッセージ ダイジェストを生成する 2 つの異なるメッセージを見つけることで構成される衝突では、誕生日攻撃を使用して平均で約1.2 × 2 L /2 回の評価のみが必要です。したがって、ハッシュ関数の強度は通常、メッセージ ダイジェストの長さの半分の対称暗号と比較されます。160 ビットのメッセージ ダイジェストを持つ SHA-1 は、当初 80 ビットの強度を持つと考えられていました。
パスワード ストレージなどの暗号ハッシュを使用するアプリケーションの一部は、衝突攻撃による影響が最小限に抑えられます。特定のアカウントで機能するパスワードを作成するには、原像攻撃と、元のパスワードのハッシュへのアクセスが必要ですが、これは簡単な場合もあれば、そうでない場合もあります。パスワードの暗号化を元に戻す (たとえば、他の場所にあるユーザーのアカウントに対して試すためのパスワードを取得する) ことは、この攻撃では不可能です。ただし、安全なパスワード ハッシュであっても、弱いパスワードに対するブルート フォース攻撃を防ぐことはできません。パスワード クラッキングを参照してください 。
文書署名の場合、攻撃者は既存の文書から署名を偽造するだけでは不十分です。攻撃者は、無害な文書と有害な文書のペアを作成し、秘密鍵の所有者に無害な文書に署名してもらう必要があります。これが可能な状況は実際にあります。2008年末までは、MD5衝突を使用して偽造SSL証明書を作成することができました。[28]
アルゴリズムのブロックと反復構造、および追加の最終ステップの欠如により、すべてのSHA関数（SHA-3を除く）[29]は、長さ拡張攻撃と部分メッセージ衝突攻撃に対して脆弱です。 [30]これらの攻撃により、攻撃者はメッセージを拡張し、キーを知らなくてもハッシュを再計算することで、キー付きハッシュ（ SHA( key || message ) 、 SHA ( message || key )ではなく）のみで署名されたメッセージを偽造できます。これらの攻撃を防ぐための簡単な改善方法は、ハッシュを2回行うことです。SHA d ( message ) = SHA(SHA(0 b || message )) （0 bの長さ、つまりゼロブロックは、ハッシュ関数のブロックサイズに等しくなります）。
0 ハッシュ
CRYPTO 98では、フランスの研究者であるフロラン・シャボーとアントワーヌ・ジュがSHA-0に対する攻撃を発表しました。衝突は複雑度2 61で発見され、同じサイズの理想的なハッシュ関数の衝突数2 80よりも少ないことがわかりました。[31]
2004年、ビハムとチェンはSHA-0のニアコリジョン（ハッシュ値がほぼ同じになる2つのメッセージ）を発見した。この場合、160ビットのうち142ビットが等しい。彼らはまた、SHA-0の完全なコリジョンが80ラウンドのうち62ラウンドに減少したことを発見した。[32]
その後、2004 年 8 月 12 日に、Joux、Carribault、Lemuet、Jalby によって完全な SHA-0 アルゴリズムの衝突が発表されました。これは、Chabaud と Joux の攻撃の一般化を使用して行われました。衝突の発見は複雑度 2 51で、 256 個のItanium 2プロセッサを搭載したスーパーコンピュータで約 80,000 プロセッサ時間(コンピュータを 13 日間フルタイムで使用した場合と同等) を要しました。
2004年8月17日、CRYPTO 2004のRumpセッションで、Wang、Feng、Lai、YuらがMD5、SHA-0、その他のハッシュ関数に対する攻撃に関する予備的な結果を発表しました。SHA-0に対する攻撃の複雑さは240で、 Jouxらによる攻撃よりも大幅に優れています。 [33] [34]
2005年2月、 Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yuによる攻撃が発表され、 239回の演算でSHA-0の衝突を発見することができた。[5] [35]
2008年にブーメラン攻撃を適用した別の攻撃では、衝突を見つける複雑さが2 33.6にまで低下し、2008年の平均的なPCでは1時間かかると推定されました。[36]
SHA-0の結果を踏まえて、一部の専門家[誰? ]は、新しい暗号システムでのSHA-1の使用計画を再検討すべきだと提案した。CRYPTO 2004の結果が公表された後、NISTは2010年までにSHA-1の使用を段階的に廃止し、SHA-2の変種を採用する計画を発表した。[37]
攻撃
2005年初頭、ヴィンセント・ライメンとエリザベス・オズワルドは、 SHA-1の縮小版（80ラウンドのうち53ラウンド）に対する攻撃を公開した。この攻撃では、280回未満の計算量で衝突を検出することができる。[38]
2005年2月、Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yuによる攻撃が発表されました。[5]この攻撃では、SHA-1のフルバージョンで衝突を見つけることができますが、必要な操作は2 69回未満です。（ブルートフォース検索では2 80回の操作が必要です。）
著者らは次のように書いている。「特に、我々の分析は、SHA-0 に対するオリジナルの差分攻撃、SHA-0 に対するニアコリジョン攻撃、マルチブロックコリジョン技術、および MD5 に対するコリジョンサーチ攻撃で使用されるメッセージ変更技術に基づいている。これらの強力な分析技術がなければ、SHA-1 を破ることは不可能だっただろう。」[39]著者らは、2 33回のハッシュ操作で見つかった 58 ラウンドの SHA-1 の衝突を提示した。完全な攻撃の説明を含む論文は、2005 年 8 月の CRYPTO カンファレンスで発表された。
インタビューで、Yinは「大まかに言えば、次の2つの弱点を悪用します。1つは、ファイルの前処理手順が十分に複雑ではないことです。もう1つは、最初の20ラウンドの特定の数学演算に予期しないセキュリティ上の問題があることです。」と述べています。[40]
2005年8月17日、CRYPTO 2005 Rumpセッションで、 Xiaoyun Wang、Andrew Yao、Frances Yaoの代理により、SHA-1攻撃の改良が発表され、SHA-1での衝突を見つけるために必要な複雑性が2 63にまで低下しました。[7] 2007年12月18日、この結果の詳細がMartin Cochranによって説明され、検証されました。[41]
Christophe De Cannière と Christian Rechberger は、SHA-1 に対する攻撃をさらに改良した「SHA-1 特性の発見: 一般的な結果と応用」[42] を発表し、 ASIACRYPT 2006で最優秀論文賞を受賞した。64 ラウンドの SHA-1 に対する 2 ブロックの衝突が発表されたが、これは 2 35 回の圧縮関数評価を伴う最適化されていない方法を使用して発見された。この攻撃には約 2 35回の評価に相当するものが必要であるため、これは理論上の大きなブレークスルーであると考えられている。 [ 43]彼らの攻撃は、2010 年にGrechnikovによってさらに 73 ラウンド (80ラウンド中)に拡張された。[44] ただし、ハッシュ関数の 80 ラウンドすべてで実際の衝突を見つけるには、膨大な量のコンピュータ時間が必要である。この取り組みは進展がなかったため2009年5月12日に中止された。[45]
CRYPTO 2006のRumpセッションで、Christian RechbergerとChristophe De Cannièreは、攻撃者がメッセージの少なくとも一部を選択できるようにするSHA-1の衝突攻撃を発見したと主張した。[46] [47]
2008年、ステファン・マニュエルによる攻撃手法では、ハッシュ衝突の理論的な複雑度は2 51～ 2 57演算と推定された。[48]しかし、後に彼は、局所衝突経路が実際には独立していないことを発見し、最終的に最も効率的な衝突ベクトルとしてこの研究以前にすでに知られていた衝突ベクトルを引用して、その主張を撤回した。[49]
キャメロン・マクドナルド、フィリップ・ホークス、ヨゼフ・ピエプジクは、Eurocrypt 2009のランプセッションで、複雑度が2 52であるハッシュ衝突攻撃を発表しました。 [50]しかし、付随する論文「複雑度O（2 52 ）のSHA-1の差分パス」は、著者らの推定が間違っていたことが発覚したため撤回されました。[51]
SHA-1に対する攻撃の1つは、Marc Stevens [52]によるもので、クラウドサーバーからCPUパワーを借りて1つのハッシュ値を破るのに277万ドル（2012年）のコストがかかると推定されています。[53] Stevensはこの攻撃をHashClash [54]というプロジェクトで開発し、差分パス攻撃を実装しました。 2010年11月8日、彼は完全なSHA-1に対して、推定複雑度が2 57.5 SHA-1圧縮に相当する、完全に機能するニアコリジョン攻撃を行ったと主張しました。彼はこの攻撃が複雑度が約2 61の完全な衝突にまで拡張できると推定しました。
シェイピング
2015 年 10 月 8 日、Marc Stevens、Pierre Karpman、Thomas Peyrin は、SHA-1 の圧縮関数に対するフリースタート衝突攻撃を発表しました。この攻撃では、2 57 回の SHA-1 評価のみが必要です。これは、完全な SHA-1 ハッシュ関数に対する衝突 (攻撃者が初期の内部状態を自由に選択できない) に直接つながるわけではありませんが、SHA-1 のセキュリティ上の主張を弱めます。特に、完全な SHA-1 に対する攻撃が実証されたのはこれが初めてでした。以前の攻撃はすべて、作成者が実行するにはコストが高すぎました。作成者は、 SHA-1暗号解読におけるこの重要なブレークスルーをSHAppeningと名付けました。[10]
この方法は、彼らの以前の研究と、JouxとPeyrinによる補助パス（またはブーメラン）高速化技術、およびNvidiaの高性能でコスト効率の高いGPUカードに基づいています。衝突は、合計64枚のグラフィックカードを備えた16ノードのクラスターで発見されました。著者らは、 EC2で2,000ドルのGPU時間を購入することで同様の衝突を発見できると推定しました。[10]
著者らは、論文発表時点でSHA-1の完全な衝突を生成するのに十分なEC2 CPU/GPU時間をレンタルするコストは75,000ドルから120,000ドルの間であると推定しており、これは国家情報機関は言うまでもなく犯罪組織の予算内で十分であると指摘した。そのため、著者らはSHA-1をできるだけ早く廃止することを推奨した。[10]
SHAttered – 初めての公の衝突
2017年2月23日、CWI（Centrum Wiskunde & Informatica）とGoogleはSHAttered攻撃を発表しました。この攻撃では、約263.1回のSHA-1評価で同じSHA-1ハッシュを持つ2つの異なるPDFファイルを生成しました。この攻撃は、誕生日攻撃によるSHA-1衝突のブルートフォース攻撃よりも約10万倍高速で、誕生日攻撃では280回のSHA-1評価が必要と推定されました。この攻撃には「6,500年間の単一CPU計算と110年間の単一GPU計算に相当する処理能力」が必要でした。[2]
誕生日ニアコリジョン攻撃 – 最初の実用的な選択プレフィックス攻撃
2019 年 4 月 24 日、Eurocrypt 2019 で発表された Gaëtan Leurent と Thomas Peyrin の論文では、Davies–Meyerブロック暗号に基づくMerkle–Damgårdのようなダイジェスト関数における、これまで最良とされていた選択プレフィックス攻撃の強化について説明しました。これらの改善により、この方法では、約 2 68 回の SHA-1 評価で選択プレフィックスの衝突を検出できます。これは、以前の攻撃の 2 77.1 回の評価 (ただし、選択されたプレフィックスは使用されておらず、検出された衝突はほぼランダムであったため、ほとんどの標的型攻撃には実用的ではありませんでした) [1 ]よりも約10 億倍高速であり (また、悪意のあるコードや署名付き証明書内の偽造 ID などのプレフィックスを選択できるため、多くの標的型攻撃に使用できるようになりました) 、また、約 10 万ドルのクラウド処理を必要とする、リソースの豊富な攻撃者にとっては実用的なほど高速です。この方法はMD5関数の選択プレフィックス衝突を見つけることもできますが、複雑さは2 46.3で、理論レベル（2 39 ）では以前の最良の方法を超えませんが、潜在的には実用的なレベル（≤2 49 ）です。[55]この攻撃には500 GB以上のメモリが必要です。
2020年1月5日、著者らは「shambles」と呼ばれる改良された攻撃を発表しました。[8]この論文では、複雑さが2の63.4である選択プレフィックス衝突攻撃を実証しており、発表時点では生成された衝突ごとに45,000米ドルのコストがかかります。
公式認証
FIPS 承認のすべてのセキュリティ機能の実装は、米国国立標準技術研究所(NIST) と通信保安局(CSE)が共同で運営するCMVP プログラムを通じて正式に検証できます。非公式の検証については、多数のテスト ベクトルを生成するパッケージが NIST サイトからダウンロードできますが、その結果得られる検証は、特定のアプリケーションで法律で義務付けられている正式な CMVP 検証に代わるものではありません。
2013 年 12 月現在[アップデート]、SHA-1 の検証済み実装は 2000 を超えており、そのうち 14 はビット長が 8 の倍数ではないメッセージを処理できます ( Wayback Machineの 2011-08-23 アーカイブされた SHS 検証リストを参照)。
例と擬似コード
ハッシュの例
これらは、16 進数およびBase64バイナリからASCIIテキストへのエンコードでのSHA-1メッセージ ダイジェストの例です。
SHA1("The quick brown fox jumps over the lazy dog")
メッセージに小さな変更を加えただけでも、雪崩効果により、多くのビットが変化する可能性が高くなります。たとえば、dogを に変更するとcog、160 ビットのうち 81 ビットの値が異なるハッシュが生成されます。
SHA1("The quick brown fox jumps over the lazy cog")
長さゼロの文字列のハッシュは次のとおりです。
SHA1("")
SHA-1 疑似コード
SHA-1 アルゴリズムの 疑似コードは次のとおりです。
注 1: すべての変数は符号なし 32 ビット量であり、計算時に 2 32を法としてラップされます。ただし、 メッセージ長 ml は 64 ビット量であり、 メッセージ ダイジェスト hh は 160 ビット量です。注 2: この疑似コード内のすべての定数は ビッグ エンディアンです。 各ワード内では、最上位バイトは左端のバイト位置に格納されます。 変数を初期化します: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 ml = ビット単位のメッセージの長さ (常に文字のビット数の倍数)。 前処理: メッセージの長さが 8 ビットの倍数の場合は、たとえば 0x80 を追加して、メッセージにビット '1' を追加します。 0 ≤ k < 512 ビットの '0' を追加し、結果として得られるメッセージの長さ（ビット単位） は-64 ≡ 448 (mod 512) と一致する。 元のメッセージの長さ（ビット単位）ml を 64 ビットのビッグエンディアン整数として追加します。 したがって、合計の長さは 512 ビットの倍数になります。 メッセージを連続する 512 ビットのチャンクで処理します。 メッセージを512ビットのチャンクに分割する 各チャンクごとに チャンクを16個の32ビットビッグエンディアンワードw[i]に分割する（0 ≤ i ≤ 15） メッセージスケジュール: 16 個の 32 ビットワードを 80 個の 32 ビットワードに拡張します。i は16 から79 までです。注 3: SHA-0 は、この左回転がない点で異なります。w [i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 このチャンクのハッシュ値を初期化します: α = h0 b = h1 ｃ = h2 d = h3 え = h4 メインループ: [3] [56] i0から79 の場合、 0≤i≤19の場合、 f = (bかつc)または(( not b)かつd) 0x5A827999 です それ以外の場合20 ≤ i ≤ 39 f = b xor c xor d 0x6ED9EBA1 の続きを読む それ以外の場合、 40 ≤ i ≤ 59 f = (bとc)または(bとd)または(cとd) k = 0x8F1BBCDC それ以外の場合、 60 ≤ i ≤ 79 f = b xor c xor d 0xCA62C1D6 のコード temp = (a左回転5) + f + e + k + w[i] 電子 = d d = c c = b左回転30 b = a a = 温度 このチャンクのハッシュをこれまでの結果に追加します。 h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e 最終的なハッシュ値（ビッグエンディアン）を160ビットの数値として生成します。hh = (h0 leftshift 128)または(h1 leftshift 96)または(h2 leftshift 64)または(h3 leftshift 32)またはh4
数字hhはメッセージ ダイジェストであり、16 進数 (基数 16) で記述できます。
アルゴリズムで使用される選択された定数値は、私の袖の数字ではないと想定されました。
- 4 つのラウンド定数は、2、3、5、10 の平方根の
k2 30倍です。ただし、0 ビットと 1 ビットの比率が均等になるように、最も近い奇数に丸められるのではなく、最も近い整数に誤って丸められました。また、10 の平方根 (素数ではない) を選択すると、2 と 5 の選択された他の 2 つの素数の平方根の共通因数になり、連続するラウンドで算術特性が使用できる可能性があり、一部のビットの衝突の検出に対するアルゴリズムの強度が低下します。 h0からまでの最初の 4 つの開始値はh3MD5 アルゴリズムと同じであり、5 番目 ( の場合h4) も同様です。ただし、これらは、マルチブロック差分攻撃で使用可能な、一部のビットでの衝突の可能性を推測するための最初の数回のラウンドの反転に対する耐性については適切に検証されていません。
示されている元の FIPS PUB 180-1 の定式化の代わりに、次の同等の式を使用してf上記のメイン ループで計算することもできます。
cとdのビット単位の選択。 bによって制御されます。 (0 ≤ i ≤ 19): f = d xor (b and (c xor d)) (選択肢 1) (0 ≤ i ≤ 19): f = (b and c)または(( not b) and d) (選択肢 2) (0 ≤ i ≤ 19): f = (b and c) xor (( not b) and d) (選択肢 3) (0 ≤ i ≤ 19): f = vec_sel(d, c, b) (選択肢 4) [プレモ08] ビット単位の多数決関数。 (40 ≤ i ≤ 59): f = (bおよびc)または(dおよび(bまたはc)) (選択肢 1) (40 ≤ i ≤ 59): f = (bおよびc)または(dおよび(b xor c)) (選択肢 2) (40 ≤ i ≤ 59): f = (bおよびc) xor (dおよび(b xor c)) (選択肢 3) (40 ≤ i ≤ 59): f = (bおよびc) xor (bおよびd) xor (cおよびd) (選択肢 4) (40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d) (選択肢 5)
また、第32～79ラウンドでは次の計算が行われることも 示されました[57] 。
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16])左回転1
次のように置き換えることができます:
w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32])左回転2
この変換により、すべてのオペランドが 64 ビットに揃えられ、 の依存性がなくなるためw[i]、x86 SSEw[i-3]命令のようなベクトル長 4 の効率的な SIMD 実装が可能になります。
SHA関数の比較
以下の表では、内部状態は、データ ブロックの各圧縮後の「内部ハッシュ サム」を意味します。
実装
以下は SHA-1 をサポートする暗号化ライブラリのリストです。
ハードウェア アクセラレーションは、次のプロセッサ拡張機能によって提供されます。
- Intel SHA 拡張機能: 一部の Intel および AMD x86 プロセッサで利用できます。
- VIA パッドロック
- IBM z/Architecture : 2003年からMessage-Security-Assist Extensionの一部として利用可能[63]
衝突対策
SHAtteredの後に、マーク・スティーブンスとダン・シュモウは「sha1collisiondetection」（SHA-1CD）を公開した。これは衝突攻撃を検出し、検出された場合にハッシュ出力を変更するSHA-1の変種である。誤検出率は2 −90である。[64] SHA-1CDは2017年3月からGitHubで使用され、2017年5月のバージョン2.13.0からgitで使用されている。 [65]
参照
WikifunctionsにはSHA-1 関数があります。
注記
- ^ ab Stevens, Marc (2012 年 6 月 19 日). ハッシュ関数とその応用に対する攻撃(PDF) (博士論文).ライデン大学. hdl :1887/19093. ISBN 9789461913173. OCLC 795702954.
- ^ abc スティーブンス、マーク;エリー・バーシュシュタイン;カルプマン、ピエール。アルベルティーニ、アンジェ。マルコフ、ヤリク (2017)。ジョナサン・カッツ;シャチャム、ホヴァフ (編)。完全な SHA-1 の最初の衝突(PDF)。暗号学の進歩 – CRYPTO 2017。コンピューター サイエンスの講義ノート。 Vol. 10401.スプリンガー。 570–596ページ。土井：10.1007/978-3-319-63688-7_19。ISBN 9783319636870. 2018年5月15日時点のオリジナル（PDF）よりアーカイブ。2017年2月23日閲覧。
- Marc Stevens、Elie Bursztein、Pierre Karpman、Ange Albertini、Yarik Markov、Alex Petit Bianco、Clement Baisse (2017 年 2 月 23 日)。「初の SHA1 衝突のお知らせ」。Googleセキュリティ ブログ。
- ^ ab 「Secure Hash Standard (SHS)」（PDF）。米国国立標準技術研究所。2015年。doi：10.6028/NIST.FIPS.180-4。連邦情報処理標準出版物180-4。2020年1月7日時点のオリジナル（PDF）からアーカイブ。 2019年9月23日閲覧。
- ^ ab 「パブリック Web での SHA-1 の終了」。Mozillaセキュリティ ブログ。2017 年 2 月 23 日。2019 年 5 月 29 日閲覧。
- ^ abc 「SHA-1 の破壊 - シュナイアーのセキュリティに関する見解」www.schneier.com。
- ^ ab 「一般的なデジタルセキュリティアルゴリズムに重大な欠陥が発見される」。南洋理工大学、シンガポール。2020年1月24日。
- ^ ab 「SHA-1 に対する新たな暗号解析結果 - Schneier on Security」www.schneier.com。
- ^ abc Leurent, Gaëtan; Peyrin, Thomas (2020-01-05). 「SHA-1 は Shambles First の選択プレフィックス衝突であり、SHA-1 と PGP Web of Trust への応用」(PDF)。Cryptology ePrint Archive、レポート 2020/014。
- ^ ab 「Google は 2017 年 1 月 1 日までに Chrome から SHA-1 暗号化を削除します」。VentureBeat。2015年 12 月 18 日。2019 年 5 月 29 日閲覧。
- ^ abcde スティーブンス、マーク;カルプマン、ピエール。ペイリン、トーマス。 「SHAppening: SHA-1 のフリースタート衝突」。2015 年 10 月 9 日に取得。
- ^ Schneier, Bruce (2005 年 2 月 18 日)。「Schneier on Security: Cryptanalysis of SHA-1」。
- ^ 「NIST.gov – Computer Security Division – Computer Security Resource Center」。2011年6月25日時点のオリジナルよりアーカイブ。2019年1月5日閲覧。
- ^ Schneier, Bruce (2015 年 10 月 8 日)。「SHA-1 フリースタート衝突」。Schneier on Security。
- ^ 「NIST、SHA-1暗号化アルゴリズムを廃止」（プレスリリース）。NIST。2022年12月15日。
- ^ Goodin, Dan (2016-05-04). 「Microsoft は今後 4 か月以内に SHA1 証明書のサポートを終了予定」Ars Technica . 2019 年 5 月 29 日閲覧。
- ^ 「CWI、Google、業界セキュリティ標準 SHA-1 の初の衝突を発表」 。2017年 2 月 23 日閲覧。
- ^ Barker, Elaine (2020 年 5 月).鍵管理に関する推奨事項: パート 1 – 一般事項、表 3 (技術レポート)。NIST。p. 56. doi : 10.6028/NIST.SP.800-57pt1r5。
- ^ 「SHA-1 Windows コンテンツは 2020 年 8 月 3 日に廃止されます」。techcommunity.microsoft.com。2024年2 月 28 日閲覧。
- ^ 「Capstone に関する RSA FAQ」。
- ^ Selvarani, R.; Aswatha, Kumar; TV Suresh, Kumar (2012). Proceedings of International Conference on Advances in Computing. Springer Science & Business Media. p. 551. ISBN 978-81-322-0740-5。
- ^ セキュアハッシュ標準、連邦情報処理標準出版物 FIPS PUB 180、国立標準技術研究所、1993 年 5 月 11 日
- ^ Kramer, Samuel (1994 年 7 月 11 日)。「連邦情報処理標準 (FIPS) 180、セキュア ハッシュ標準の改訂案」連邦官報。
- ^ fgrieu. 「SHA-0 ハッシュ アルゴリズムの説明はどこにありますか?」。Cryptography Stack Exchange。
- ^ ab コンピュータセキュリティ部門、情報技術研究所 (2017-01-04)。「ハッシュ関数に関するNISTポリシー – ハッシュ関数」。CSRC、NIST 。 2023年8月27日閲覧。
- ^ 「Tech Talk: Linus Torvalds on git」YouTube 。 2013年11月13日閲覧。
- ^ Torvalds, Linus. 「Re: sha-256 について考え始めているか?」marc.info . 2016 年5 月 30 日閲覧。
- ^ Walfield, Neal H. (2020). 「openpgp: ハッシュアルゴリズムのセキュリティ要件を Policy::signature に渡す」. gitlab.com/sequoia-pgp .– レンダリングされたドキュメントの「背景」セクションを参照してください
- ^ アレクサンダー・ソティロフ;マーク・スティーブンス。アッペルバウム、ジェイコブ。レンストラ、アリジェン。モルナー、デイビッド。オスヴィック、ダグ・アーン。デ・ウェガー、ベンネ（2008年12月30日）。 「今日有害と考えられる MD5: 不正な CA 証明書の作成」。2009 年3 月 29 日に取得。
- ^ 「Keccak の強み - 設計とセキュリティ」。Keccakスポンジ関数ファミリー。Keccak チーム。2015年9 月 20 日閲覧。SHA
-1 や SHA-2 とは異なり、Keccak には長さ拡張の弱点がないため、HMAC ネスト構造は必要ありません。代わりに、メッセージの先頭にキーを追加するだけで MAC 計算を実行できます。
- ^ 「Schneier on Security: Cryptography Engineering」www.schneier.com . 2023年8月27日閲覧。
- ^ シャボー、フィレンツェ;ジュー、アントワーヌ（1998年10月3日）。 「SHA-0 の差分衝突」。 Krawczyk、Hugo (編)。暗号学の進歩 – CRYPTO '98。コンピューターサイエンスの講義ノート。 Vol. 1462. スプリンガー。 56–71ページ。土井：10.1007/BFb0055720。ISBN 978-3-540-64892-5– Springer Link経由。
- ^ Biham, Eli; Chen, Rafi. 「SHA-0 のニアコリジョン」(PDF)。
- ^ 「Report from Crypto 2004」。2004年8月21日時点のオリジナルよりアーカイブ。2004年8月23日閲覧。
- ^ Grieu, Francois (2004 年 8 月 18 日)。「Re: 暗号残党セッションからの最新情報はありますか?」。ニュースグループ: sci.crypt。イベントは 05:06:02 +0200 に発生。Usenet : fgrieu-05A994.05060218082004@individual.net。
- ^ SHA-0 に対する効率的な衝突探索攻撃、 Wayback Machineに 2005-09-10 アーカイブ、山東大学
- ^ Manuel, Stéphane; Peyrin, Thomas (2008-02-11). SHA-0 での 1 時間以内の衝突(PDF) . Fast Software Encryption 2008. Lecture Notes in Computer Science. Vol. 5086. pp. 16–35. doi : 10.1007/978-3-540-71039-4_2 . ISBN 978-3-540-71038-7。
- ^ 「NIST による最近の暗号解読攻撃と SHA-1 によって提供される継続的なセキュリティに関する簡単なコメント」 2017 年 8 月 23 日。 2022 年 3 月 16 日閲覧。
- ^ Rijmen, Vincent; Oswald, Elisabeth (2005). 「SHA-1 のアップデート」. Cryptology ePrint Archive .
- ^ SHA1 に対する衝突探索攻撃、2005-02-19 に Wayback Machineにアーカイブ、マサチューセッツ工科大学
- ^ Lemos, Robert. 「セキュリティの穴を埋める」ZDNet。
- ^ Cochran, Martin (2007). 「Wang et al. 263 SHA-1 差分パスに関する注記」Cryptology ePrint Archive。
- ^ De Cannière, Christophe; Rechberger, Christian (2006-11-15). 「SHA-1 特性の検出: 一般的な結果とアプリケーション」。暗号学の進歩 - ASIACRYPT 2006。 コンピュータ サイエンスの講義ノート。 Vol. 4284。 pp. 1–20。doi :10.1007/11935230_1。ISBN 978-3-540-49475-1。
- ^ 「IAIK Krypto Group — SHA-1 衝突検索プロジェクトの説明」。2013 年 1 月 15 日時点のオリジナルよりアーカイブ。2009年 6 月 30 日閲覧。
- ^ 「72 ステップおよび 73 ステップ SHA-1 の衝突: 特性法の改善」。2010 年 7 月 24 日閲覧。
- ^ 「SHA-1 Collision Search Graz」。2009年2月25日時点のオリジナルよりアーカイブ。2009年6月30日閲覧。
- ^ "heise online – IT-News、Nachrichten und Hintergründe".ハイセオンライン。 2023年8月27日。
- ^ 「Crypto 2006 Rump Schedule」。www.iacr.org。
- ^ Manuel, Stéphane. 「SHA-1 に対する衝突攻撃に対する妨害ベクトルの分類と生成」(PDF)。Cryptology ePrint Archive 。 2011 年 5 月 19 日閲覧。
- ^ マヌエル、ステファン (2011)。「SHA-1 に対する衝突攻撃に対する妨害ベクトルの分類と生成」。設計、コード、暗号化。59 (1–3): 247–263。doi : 10.1007 /s10623-010-9458-9。S2CID 47179704 。 最も効率的な妨害ベクトルは、JutlaとPatthakによって最初に報告されたCodeword2である。
- ^ 「SHA-1 衝突数は現在 2^52」(PDF)。
- ^ McDonald, Cameron; Hawkes, Philip; Pieprzyk, Josef (2009). 「複雑度O(252)のSHA-1の差分パス」Cryptology ePrint Archive。（撤回）
- ^ 「MD5とSHA-1の暗号解析」（PDF）。
- ^ 「SHA-1 の衝突はいつ起こるのか? – Schneier on Security」www.schneier.com。
- ^ 「Google Code アーカイブ – Google Code プロジェクト ホスティング用の長期ストレージ」。code.google.com。
- ^ Leurent, Gaëtan; Peyrin, Thomas (2019). 「衝突から選択されたプレフィックスの衝突への応用 - 完全な SHA-1 へ」(PDF)。 Yuval Ishai、Vincent Rijmen (編)。 暗号学の進歩 - EUROCRYPT 2019 (PDF)。 38 回目の国際暗号技術の理論と応用に関する年次会議、ドイツ、ダルムシュタット、2019 年 5 月 19 ～ 23 日。 コンピュータ サイエンスの講義ノート。 Vol. 11478。 Springer。 pp. 527 ～ 555。doi :10.1007/978-3-030-17659-4_18。ISBN 978-3-030-17658-7.S2CID 153311244 。
- ^ 「RFC 3174 - US セキュアハッシュアルゴリズム 1 (SHA1) (RFC3174)」。www.faqs.org。
- ^ Locktyukhin, Max (2010-03-31)、「セキュア ハッシュ アルゴリズム (SHA-1) のパフォーマンスの向上」、Intel Software Knowledge Base 、2010-04-02取得
- ^ 「測定表」bench.cr.yp.to .
- ^ Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). MD5 に対する高速衝突攻撃(PDF) . Cryptology ePrint Archive (技術レポート). IACR .
- ^ Stevens, Marc ; Bursztein, Elie ; Karpman, Pierre ; Albertini, Ange ; Markov, Yarik. 完全な SHA-1 の最初の衝突(PDF) (技術レポート)。Google Research。
- Marc Stevens、Elie Bursztein、Pierre Karpman、Ange Albertini、Yarik Markov、Alex Petit Bianco、Clement Baisse (2017 年 2 月 23 日)。「初の SHA1 衝突のお知らせ」。Googleセキュリティ ブログ。
- ^ 切り捨てがない場合、衝突耐性に関係なく、ハッシュ関数の完全な内部状態がわかります。出力が切り捨てられている場合、ハッシュ関数を再開する前に、状態の削除された部分を検索して見つける必要があり、攻撃を続行できるようになります。
- ^ 「Keccakスポンジ関数ファミリー」。2016年1月27日閲覧。
- ^ IBM z/Architecture Principles of Operation、発行番号 SA22-7832。第 7 章の KIMD および KLMD 命令を参照してください。
- ^ Stevens, Marc (2017). 「cr-marcstevens/sha1collisiondetection: ファイル内の SHA-1 衝突を検出するためのライブラリとコマンドラインツール」
- ^ King, Jeff (2017 年 5 月 10 日)。「Git 2.13 がリリースされました」。GitHub ブログ。
参考文献
- Eli Biham、Rafi Chen、「SHA-0 のニアコリジョン」、Cryptology ePrint Archive、レポート 2004/146、2004 年 (CRYPTO 2004 に掲載)、IACR.org
- Xiaoyun Wang、Hongbo Yu、Yiqun Lisa ying、SHA-0 に対する効率的な衝突探索攻撃、暗号 2005
- Xiaoyun Wang、Yiqun Lisa ying、Hongbo Yu、完全な SHA-1 の衝突の発見、暗号 2005
- アンリ・ギルバート、ヘレナ・ハンシュー：SHA-256 と Sisters のセキュリティ分析。2003年暗号分野選択：pp175～193
- 暗号ハッシュの図解ガイド
- 「連邦情報処理標準 (FIPS) 180、セキュアハッシュ標準の改訂案」連邦官報59 ( 131): 35317–35318。1994-07-11。2007-04-26閲覧。[永久リンク切れ ]
- A. Cilardo、L. Esposito、A. Veniero、A. Mazzeo、V. Beltran、E. Ayugadé、「暗号ハッシュ関数の脆弱性を分析するための CellBE ベースの HPC アプリケーション」、高性能コンピューティングおよび通信国際会議、2010 年 8 月
外部リンク
- CSRC 暗号化ツールキット –セキュアハッシュ標準の公式NISTサイト
- FIPS 180-4: セキュアハッシュ標準 (SHS)
- RFC 3174 (サンプル C 実装付き)
- SHA-1への攻撃に関するYiqun Lisa Yin氏へのインタビュー
- SHA-1 に対する成功した攻撃の説明 (3 ページ、2006 年)
- 暗号研究 – ハッシュ衝突に関するQ&A
- SHA-1 に関する講義 (1 時間 18 分) YouTubeのChristof Paar によるアーカイブ (2017 年 4 月 24 日、Wayback Machineより)