SHA-1
安全なハッシュアルゴリズム
概念
ハッシュ関数、SHA、DSA
主な基準
SHA-0、SHA-1、SHA-2、SHA-3
SHA-1
一般的な
デザイナー国家安全保障局
初版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は長さ拡張攻撃を受けやすい傾向があります。
Wikifunctions にはSHA-1 関数があります。

暗号学において、SHA-1（セキュアハッシュアルゴリズム1）は、入力を受け取り、160ビット（20バイト）のハッシュ値（メッセージダイジェストと呼ばれる）を生成するハッシュ関数です。これは通常、40桁の16進数で表されます。これは米国国家安全保障局によって設計され、米国連邦情報処理標準（ FIPS）です。[ 3 ]このアルゴリズムは暗号的に解読されていますが[ 4 ] [ 5] [6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] 、現在でも広く使用されています。

2005年以来、SHA-1は資金力のある敵に対して安全であるとは考えられておらず、[ 11 ] 2010年の時点で多くの組織がSHA-1の置き換えを推奨しています。[ 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 2000 ServerからServer 2003までのWindows Serverバージョンなど、SHA-2に更新されていないWindowsのバージョンの更新サーバーも事実上終了しました。

発達

SHA-1 圧縮関数内の 1 つの反復:
  • A、B、C、D、E は状態の32 ビットワードです。
  • Fは変化する非線形関数です。
  • ⁠ ⁠ は⋘n{\displaystyle \lll_{n}}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はほとんどの政府機関での使用から廃止されつつあります。米国国立標準技術研究所（NIST）は、「連邦政府機関は、衝突耐性を必要とするアプリケーションでの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はセキュリティ機能ですらないということです。SHA-1は純粋に整合性チェックのためのものです。セキュリティ部分は別の部分にあるため、多くの人は、GitがSHA-1を使用し、SHA-1は暗号的に安全なものに使用されているので、「なるほど、これは強力なセキュリティ機能だ」と考えがちです。しかし、SHA-1はセキュリティとは全く関係がなく、単に入手できる最高のハッシュ値に過ぎないのです。...
データを Git に保存しておけば、5 年後、つまりハードディスクから DVD や新しいテクノロジーに変換してコピーした後でも、取り出したデータが保存したデータとまったく同じであることを確認できると保証します。[...]
私がカーネルを気にしている理由の一つは、 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( 0b || message )) （ 0b 、つまりゼロブロックの長さは、ハッシュ関数のブロックサイズに等しいです）。

SHA-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プロセッサを搭載したスーパーコンピュータで約8万プロセッサ時間（コンピュータの13日間のフルタイム使用に相当）を要しました。

2004年8月17日、CRYPTO 2004のランプセッションにおいて、Wang、Feng、Lai、Yuらは、MD5、SHA-0、その他のハッシュ関数に対する攻撃に関する予備的な結果を発表しました。SHA-0に対する彼らの攻撃の複雑度は2の40乗であり、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は「Finding SHA-1 Characteristics: General Results and Applications」 [ 42 ]でSHA-1への攻撃をさらに改良し、ASIACRYPT 2006でBest Paper Awardを受賞した。64ラウンドのSHA-1で2ブロックの衝突が発見され、最適化されていない手法で2の35回の圧縮関数評価を行った。この攻撃には約2の35回の評価に相当するものが必要であるため、理論的に大きな飛躍が見られた。[ 43 ]彼らの攻撃は、2010年にGrechnikovによってさらに73ラウンド（80ラウンド中）に拡張された。[ 44 ]しかし、ハッシュ関数の全80ラウンドで実際の衝突を見つけるには、膨大な量の計算時間が必要となる。この目的のため、グラーツ工科大学の主催により、ボランティアコンピューティングプラットフォームBOINCを使用したSHA-1の衝突探索が2007年8月8日に開始された。この取り組みは進展がなかったため2009年5月12日に中止された。[ 45 ]

CRYPTO 2006のランプセッションで、クリスチャン・レッヒベルガーとクリストフ・ドゥ・カニエールは、攻撃者がメッセージの少なくとも一部を選択できるSHA-1の衝突攻撃を発見したと主張した。[ 46 ] [ 47 ]

2008年、ステファン・マニュエルによる攻撃手法では、ハッシュ衝突の理論的複雑度は2の51乗から2の57乗と推定された。[ 48 ]しかし、後に彼は局所的な衝突経路が実際には独立していないことを発見し、最終的に最も効率的な衝突ベクトルとしてこの研究以前に知られていた衝突ベクトルを引用してその主張を撤回した。[ 49 ]

キャメロン・マクドナルド、フィリップ・ホークス、ヨゼフ・ピエプジクは、Eurocrypt 2009のランプセッションで、2.52の複雑度を主張するハッシュ衝突攻撃を発表しました。 [ 50 ]しかし、付随論文「複雑度O（2.52 ）のSHA-1の差分パス」は、著者らの推定が誤っていたことが発覚したため撤回されました。[ 51 ]

SHA-1に対する攻撃の一つに、Marc Stevens氏による攻撃[ 52 ]があります。この攻撃では、クラウドサーバーからCPUパワーを借りてハッシュ値1つを解読するのに、推定コスト277万ドル（2012年）かかりました。[ 53 ] Stevens氏はこの攻撃をHashClashというプロジェクトで開発し、[ 54 ]差分パス攻撃を実装しました。2010年11月8日、彼はSHA-1の完全圧縮に対して、推定複雑度が2の57.5倍に相当する、完全に機能するニアコリジョン攻撃を成功させたと主張しました。彼はこの攻撃が複雑度が約2の61倍の完全衝突にまで拡張できると推定しました。

SHAppening

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による補助パス（ブーメラン）高速化手法と高性能GPUカードの使用に基づいている。衝突は、合計64枚のグラフィックカードを搭載した16ノードのクラスタで発見された。著者らは、EC2で2,000ドル分のGPU時間を購入することで同様の衝突を発見できると推定した。[ 10 ]

著者らは、SHA-1の完全な衝突を生成するのに十分なEC2 CPU/GPU時間をレンタルするコストは、本稿の発表時点で7万5千ドルから12万ドルと推定しており、これは国家情報機関はもちろんのこと、犯罪組織の予算内でも十分に賄える金額だと指摘した。そのため、著者らはSHA-1を可能な限り速やかに廃止することを推奨した。[ 10 ]

SHAttered – 初めての公の場での衝突

2017年2月23日、CWI（Centrum Wiskunde & Informatica）とGoogleはSHAttered攻撃を発表しました。この攻撃では、約2 63.1回のSHA-1評価で、同じSHA-1ハッシュを持つ2つの異なるPDFファイルを生成しました。この攻撃は、誕生日攻撃によるSHA-1衝突の総当たり攻撃（推定2 80回のSHA-1評価が必要）よりも約10万倍高速です。この攻撃には、「単一CPU計算の6,500年分、単一GPU計算の110年分に相当する処理能力」が必要でした。[ 2 ]

誕生日ニアコリジョン攻撃 – 最初の実用的な選択プレフィックス攻撃

2019年4月24日、Gaëtan LeurentとThomas PeyrinによってEurocrypt 2019で発表された論文では、Davies–Meyerブロック暗号に基づくMerkle–Damgårdのようなダイジェスト関数における、これまで最善とされていた選択プレフィックス攻撃の強化について説明しました。これらの改善により、この手法では、約2 68 回のSHA-1評価で選択プレフィックスの衝突を検出できます。これは、以前の攻撃の2 77.1 回の評価（ただし、選択されたプレフィックスは使用されておらず、検出された衝突はほぼランダムであったため、ほとんどの標的型攻撃には実用的ではありませんでした） [ 1 ]よりも約550倍高速であり（また、悪意のあるコードや署名付き証明書内の偽造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 の検証済みの実装は 2,000 を超えており、そのうち 14 はビット長が 8 の倍数ではないメッセージを処理できます ( Wayback Machineの 2011-08-23アーカイブされたSHS 検証リスト を参照)。

例と擬似コード

ハッシュの例

これらは、 16 進数およびBase64バイナリからASCIIテキストへのエンコードでのSHA-1メッセージ ダイジェストの例です。

  • SHA1("The quick brown fox jumps over the lazy dog")
    • 出力された16進数:2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
    • Base64バイナリをASCIIテキストエンコードで出力しました:L9ThxnotKPzthJ7hu3bnORuT6xI=

メッセージに小さな変更を加えるだけでも、雪崩効果により、圧倒的な確率で多くのビットが変化します。例えば、dogを に変更するとcog、160ビットのうち81ビットの値が異なるハッシュが生成されます。

  • SHA1("The quick brown fox jumps over the lazy cog")
    • 出力された16進数:de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
    • Base64バイナリをASCIIテキストエンコードで出力しました:3p8sf9JeGzr60+haC9F9mxANtLM=

長さゼロの文字列のハッシュは次のとおりです。

  • SHA1("")
    • 出力された16進数:da39a3ee5e6b4b0d3255bfef95601890afd80709
    • Base64バイナリをASCIIテキストエンコードで出力しました:2jmj7l5rSw0yVb/vlWAYkK/YBwk=

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 このチャンクのハッシュ値を初期化します。 a = h0 b = h1 c = h2 d = h3 e = h4 メインループ: [ 3 ] [ 56 ] iが0から79 の場合、 0 ≤ i ≤ 19の場合、f = (bかつc)または(( b以外)かつd) k = 0x5A827999 そうでなければ20≤i≤39の場合 f = b xor c xor d k = 0x6ED9EBA1 そうでなければ40≤i≤59の場合 f = (bとc)または(bとd)または(cとd) k = 0x8F1BBCDC そうでなければ60≤i≤79の場合 f = b xor c xor d k = 0xCA62C1D6 temp = (a左回転5) + f + e + k + w[i] e = 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左シフト128)または(h1左シフト96)または(h2左シフト64)または(h3左シフト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関数の比較
アルゴリズムと変種 出力サイズ（ビット） 内部状態サイズ（ビット） ブロックサイズ（ビット） ラウンド オペレーション セキュリティ（ビット） Skylakeでのパフォーマンス（中央値cpb）[ 58 ]初版
長いメッセージ 8バイト
MD5（参考）128128 (4 × 32)5124 （各ラウンドで 16回の演算）And、Xor、Or、Rot、Add（mod 2 32）≤ 18 （衝突が見つかった）[ 59 ]4.9955.001992
SHA-0160160 (5 × 32)51280And、Xor、Or、Rot、Add（mod 2 32）< 34 (衝突が見つかりました)≈ SHA-1≈ SHA-11993
SHA-1< 63 (衝突が見つかりました) [ 60 ]3.4752.001995
SHA-2SHA-224 SHA-256224 256256 (8 × 32)51264And、Xor、Or、Rot、Shr、Add (mod 2 32 )112 1287.62 7.6384.50 85.252004 2001
SHA-384384512 (8 × 64)102480And、Xor、Or、Rot、Shr、Add (mod 2 64 )1925.12135.752001
SHA-5125122565.06135.502001
SHA-512/224 SHA-512/256224 256112 128≈ SHA-384≈ SHA-3842012
SHA-3SHA3​​-224 SHA3-256 SHA3-384 SHA3-512224 256 384 5121600 （5×5×64）1152 1088 832 57624 [ 61 ]そして、Xor、Rot、Not112 128 192 2568.12 8.59 11.06 15.88154.25 155.50 164.00 164.002015
シェイク128シェイク256d（任意）d（任意）1344 1088分( d /2, 128)分( d /2, 256)7.08 8.59155.25 155.50

実装

以下は SHA-1 をサポートする暗号化ライブラリのリストです。

ハードウェア アクセラレーションは、次のプロセッサ拡張機能によって提供されます。

衝突対策

SHAtteredの発表を受けて、Marc StevensとDan Shumowは「sha1collisiondetection」（SHA-1CD）を公開しました。これはSHA-1の派生版で、衝突攻撃を検出し、検出時にハッシュ出力を変更します。誤検出率は2 -90です。[ 63 ] SHA-1CDは、 GitHubでは2017年3月から、gitでは2017年5月のバージョン2.13.0から使用されています。[ 64 ]

参照

注記

  1. ^ a b Stevens, Marc (2012年6月19日).ハッシュ関数とその応用に対する攻撃(PDF) (博士論文).ライデン大学. hdl : 1887/19093 . ISBN 9789461913173. OCLC  795702954 .
  2. ^ a b c Stevens, Marc ; Bursztein, Elie ; Karpman, Pierre ; Albertini, Ange ; Markov, Yarik (2017). Katz, Jonathan ; Shacham, Hovav (編). The First Collision for Full SHA-1 (PDF) . Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science . Vol. 10401. Springer . pp.  570– 596. doi : 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セキュリティブログ。
  3. ^ a b「セキュアハッシュ標準（SHS）」（PDF）。米国国立標準技術研究所（NIST）。2015年。doi：10.6028/NIST.FIPS.180-4 。連邦情報処理標準出版物180-4。 2020年1月7日時点のオリジナル（PDF）からアーカイブ。 2019年9月23日閲覧。
  4. ^ a b「パブリックWebにおけるSHA-1の終了」 Mozillaセキュリティブログ2017年2月23日。 2019年5月29日閲覧。
  5. ^ a b c「SHA-1の脆弱性 - シュナイアー氏のセキュリティに関する見解」 www.schneier.com 2005年2月15日
  6. ^ a b「一般的なデジタルセキュリティアルゴリズムに重大な欠陥が発見される」南洋理工大学、シンガポール。2020年1月24日。
  7. ^ a b「SHA-1に対する新たな暗号解析結果 - シュナイアーのセキュリティに関する見解」 www.schneier.com 2005年8月17日。
  8. ^ a b c Leurent, Gaëtan; Peyrin, Thomas (2020年1月5日). 「SHA-1はShambles First Chosen-Prefix Collision on SHA-1とPGP Web of Trustへの応用」(PDF) . Cryptology ePrint Archive, Report 2020/014 .
  9. ^ a b「Googleは2017年1月1日までにChromeのSHA-1暗号化を廃止する」VentureBeat . 2015年12月18日. 2019年5月29日時点のオリジナルよりアーカイブ。 2019年5月29日閲覧。
  10. ^ a b c d e Stevens, Marc; Karpman, Pierre; Peyrin, Thomas. 「The SHAppening: freestart collisions for SHA-1」 . 2015年10月9日閲覧。
  11. ^ Schneier, Bruce (2005年2月18日). 「Schneier on Security: Cryptanalysis of SHA-1」 .
  12. ^ 「NIST.gov – コンピュータセキュリティ部門 – コンピュータセキュリティリソースセンター」 。 2011年6月25日時点のオリジナルよりアーカイブ。2019年1月5日閲覧。
  13. ^ Schneier, Bruce (2015年10月8日). 「SHA-1フリースタート衝突」 . Schneier on Security .
  14. ^ 「NIST、SHA-1暗号化アルゴリズムを廃止」（プレスリリース）。NIST。2022年12月15日。
  15. ^ Goodin, Dan (2016年5月4日). 「Microsoft、今後4ヶ月以内にSHA1証明書のサポートを終了へ」 Ars Technica . 2019年5月29日閲覧。
  16. ^ 「CWIとGoogle、業界セキュリティ標準SHA-1の初の衝突を発表」。2017年2月23日閲覧。
  17. ^ Barker, Elaine (2020年5月).鍵管理に関する推奨事項：パート1 – 一般事項、表3（技術レポート）. NIST. p. 56. doi : 10.6028/NIST.SP.800-57pt1r5 .
  18. ^ 「SHA-1 Windowsコンテンツは2020年8月3日に廃止されます」。techcommunity.microsoft.com 。2024年2月28日閲覧。
  19. ^ 「Capstone に関する RSA FAQ」。
  20. ^ 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。
  21. ^セキュアハッシュ標準、連邦情報処理標準出版物 FIPS PUB 180、米国国立標準技術研究所、1993年5月11日
  22. ^ Kramer, Samuel (1994年7月11日). 「連邦情報処理規格（FIPS）180、セキュアハッシュ規格の改訂案」連邦官報.
  23. ^ fgrieu. 「SHA-0ハッシュアルゴリズムの説明はどこにありますか？」 Cryptography Stack Exchange .
  24. ^ a bコンピュータセキュリティ部門、情報技術研究所 (2017年1月4日). 「ハッシュ関数に関するNISTポリシー – ハッシュ関数」 . CSRC, NIST . 2023年8月27日閲覧。
  25. ^ 「Tech Talk: Linus Torvalds on git」YouTube 2007年5月14日. 2013年11月13日閲覧。
  26. ^ Torvalds, Linus. 「Re: sha-256について考え始めているか？」 marc.info . 2016年5月30日閲覧。
  27. ^ Walfield, Neal H. (2020). 「openpgp: ハッシュアルゴリズムのセキュリティ要件をPolicy::signatureに渡す」 . gitlab.com/sequoia-pgp .–レンダリングされたドキュメントの「背景」セクションを参照してください
  28. ^アレクサンダー・ソティロフ;マーク・スティーブンス。アッペルバウム、ジェイコブ。レンストラ、アリジェン。モルナー、デイビッド。オスヴィック、ダグ・アーン。デ・ウェガー、ベンネ（2008年12月30日）。「今日有害と考えられる MD5: 不正な CA 証明書の作成」。2009 年3 月 29 日に取得。
  29. ^ 「Keccakの強み - 設計とセキュリティ」 . Keccakスポンジ関数ファミリー. Keccakチーム. 2015年9月20日閲覧。SHA -1やSHA-2とは異なり、Keccakには長さ拡張の弱点がないため、HMACネスト構造は必要ありません。その代わりに、メッセージの先頭に鍵を追加するだけでMAC計算を実行できます。
  30. ^ 「Schneier on Security: Cryptography Engineering」www.schneier.com . 2023年8月27日閲覧。
  31. ^シャボー、フィレンツェ;ジュー、アントワーヌ（1998年10月3日）。「SHA-0 の差分衝突」。 Krawczyk、Hugo (編)。暗号学の進歩 – CRYPTO '98。コンピューターサイエンスの講義ノート。 Vol. 1462. スプリンガー。ページ 56–71。土井: 10.1007/BFb0055720。ISBN 978-3-540-64892-5– Springer Link経由。
  32. ^ Biham, Eli; Chen, Rafi. 「SHA-0のニアコリジョン」（PDF）。
  33. ^ 「Report from Crypto 2004」。2004年8月21日時点のオリジナルよりアーカイブ。2004年8月23日閲覧。
  34. ^ Grieu, Francois (2004年8月18日). 「Re: 暗号残党会合からの速報は？」.ニュースグループ:  sci.crypt . イベント発生時刻: 05:06:02 +0200. Usenet: fgrieu-05A994.05060218082004@individual.net . 
  35. ^ SHA-0に対する効率的な衝突探索攻撃、Wayback Machineに2005年9月10日アーカイブ、山東大学
  36. ^マヌエル、ステファン、ペラン、トーマス (2008-02-11). SHA-0における1時間以内の衝突(PDF) . 高速ソフトウェア暗号化 2008. コンピュータサイエンス講義ノート. 第5086巻. pp.  16– 35. doi : 10.1007/978-3-540-71039-4_2 . ISBN 978-3-540-71038-7。
  37. ^ 「NISTによる最近の暗号解読攻撃とSHA-1が提供する継続的なセキュリティに関する簡潔なコメント」 2017年8月23日。 2022年3月16日閲覧。
  38. ^ Rijmen, Vincent; Oswald, Elisabeth (2005). 「SHA-1のアップデート」 . Cryptology ePrint Archive .
  39. ^ SHA1に対する衝突探索攻撃Archived 2005-02-19 at the Wayback Machine , Massachusetts Institute of Technology
  40. ^レモス、ロバート。「セキュリティホールの修正」ZDNet。
  41. ^ Cochran, Martin (2007). 「Wang et al. 2 63 SHA-1 差分パスに関する注記」 . Cryptology ePrint Archive .
  42. ^ De Cannière, Christophe; Rechberger, Christian (2006-11-15). 「SHA-1特性の検出：一般的な結果と応用」. Advances in Cryptology – ASIACRYPT 2006 . Lecture Notes in Computer Science. Vol. 4284. pp.  1– 20. doi : 10.1007/11935230_1 . ISBN 978-3-540-49475-1。
  43. ^ 「IAIK Krypto Group – SHA-1 Collision Search Project の説明」 。 2013年1月15日時点のオリジナルよりアーカイブ。2009年6月30日閲覧。
  44. ^ 「72段階および73段階SHA-1の衝突：特性法の改良」 。 2010年7月24日閲覧。
  45. ^ 「SHA-1 Collision Search Graz」 2009年2月25日時点のオリジナルよりアーカイブ。 2009年6月30日閲覧。
  46. ^ "heise online – IT-News、Nachrichten und Hintergründe" .ハイセオンライン。 2023年8月27日。
  47. ^ 「Crypto 2006 Rump Schedule」www.iacr.org。
  48. ^マヌエル、ステファン. 「SHA-1に対する衝突攻撃のための妨害ベクトルの分類と生成」(PDF) . Cryptology ePrint Archive . 2011年5月19日閲覧。
  49. ^マヌエル、ステファン (2011). 「SHA-1に対する衝突攻撃のための撹乱ベクトルの分類と生成」. Designs, Codes and Cryptography . 59 ( 1–3 ): 247– 263. doi : 10.1007/s10623-010-9458-9 . S2CID 47179704 . 最も効率的な撹乱ベクトルは、JutlaとPatthakによって最初に報告されたCodeword2である。
  50. ^ 「SHA-1 の衝突は現在 2^52 です」(PDF)。
  51. ^ McDonald, Cameron; Hawkes, Philip; Pieprzyk, Josef (2009). 「複雑度O( 252 )のSHA-1の差分パス」 . Cryptology ePrint Archive .（撤回）
  52. ^ 「MD5とSHA-1の暗号解析」(PDF)。
  53. ^ 「SHA-1の衝突はいつ起こるのか？ - Schneierのセキュリティに関する見解」 www.schneier.com 2012年10月5日
  54. ^ 「Google Code アーカイブ – Google Code プロジェクト ホスティング用の長期ストレージ」 . code.google.com .
  55. ^ Leurent, Gaëtan; Peyrin, Thomas (2019). 「衝突から選択プレフィックス衝突への応用：完全なSHA-1へ」(PDF) . Yuval Ishai, Vincent Rijmen (編). Advances in Cryptology – EUROCRYPT 2019 (PDF) . 第38回暗号技術の理論と応用に関する国際会議、ドイツ、ダルムシュタット、2019年5月19日～23日. Lecture Notes in Computer Science. Vol. 11478. Springer. pp.  527– 555. doi : 10.1007/978-3-030-17659-4_18 . ISBN 978-3-030-17658-7. S2CID  153311244 .
  56. ^ 「RFC 3174 - USセキュアハッシュアルゴリズム1（SHA1）（RFC3174）」。www.faqs.org。
  57. ^ Locktyukhin, Max (2010-03-31)、「セキュアハッシュアルゴリズム（SHA-1）のパフォーマンスの向上」、Intelソフトウェアナレッジベース、2010年4月2日取得
  58. ^ 「測定表」 . bench.cr.yp.to .
  59. ^ Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). MD5に対する高速衝突攻撃(PDF) . Cryptology ePrint Archive (技術レポート). IACR .
  60. ^ 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セキュリティブログ。
  61. ^ 「Keccakスポンジ関数ファミリー」 。 2016年1月27日閲覧。
  62. ^ IBM z/Architecture Principles of Operation、発行番号SA22-7832。第7章のKIMD命令とKLMD命令を参照してください。
  63. ^ Stevens, Marc (2017). 「cr-marcstevens/sha1collisiondetection: ファイル内のSHA-1衝突を検出するためのライブラリとコマンドラインツール」 . GitHub .
  64. ^ King, Jeff (2017年5月10日). 「Git 2.13がリリースされました」 . GitHubブログ.

参考文献

「 https://en.wikipedia.org/w/index.php?title=SHA-1&oldid=1334212456」から取得