SHA-1は、アメリカ国家安全保障局 (NSA) によって設計され、アメリカ国立標準技術研究所 (NIST) によってFIPS PUB 180-4として標準化された暗号学的ハッシュ関数である。SHA-1は、160ビット（20バイト）のハッシュ値を生成する。SHAは「Secure Hash Algorithm」の略である。SHAには4種類のシリーズが存在し、それぞれSHA-0、SHA-1、SHA-2、SHA-3と呼ばれる。SHA-1はSHA-0にきわめて類似しており、SHA-0において脆弱性の原因となっていた仕様のエラーを修正したものがSHA-1である。そのためSHA-0はあまり用いられてはいない。一方、SHA-2、SHA-3はSHA-1とは大きく異なる仕様である。SHA-1はSHAシリーズの中で最も広く用いられているものであり、多くのアプリケーションやプロトコルに採用されている。2005年、SHA-1に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された。NISTは、合衆国の政府組織に対して、2010年までにSHA-1からSHA-2へ移行するよう要請した。SHA-2に対する有効な攻撃法はいまだ報告されていないが、その構造はSHA-1に類似したものである。2012年、公募を経て、KeccakがSHA-3として選定された。2013年11月にはマイクロソフトが、2017年までにMicrosoft WindowsのTLS/SSLにおいてSHA-1を利用した証明書を受け入れないようにすることを表明した。2014年9月にはGoogleも2017年までにGoogle ChromeにおいてSHA-1による証明書を受け入れないようにすることを表明した。Mozillaでも同様に2017年までにSHA-1による証明書を受け入れないようにすることを検討している。日本においても、CRYPTRECが2003年の初版では推奨リストに掲載されていたSHA-1を2013年の改訂において互換性維持のための利用に限定した運用監視リストに移行し、総務省および法務省では、政府認証基盤および電子認証登記所（商業登記認証局）においてSHA-1を用いた電子証明書の検証を2015年度まで（特別の事情がある場合は2019年度まで）に終了することとしている。これらを受けて、SHA-1を使っているウェブサイトはSHA-2への移行が予定されており、SHA-2に対応できないソフトや機器によるアクセスは不能になる。特に2009年以前の携帯電話機は一部を除き内蔵ソフト更新が行われないため、ハードウェアの買い替えを余儀なくされる。SHA-1は、マサチューセッツ工科大学のロナルド・リベストがMD4やMD5の設計で用いたものと同様の原理に基づいているが、より保守的な設計となっている。オリジナルの仕様は、1993年にNISTによってFIPS 180 "Secure Hash Standard" として発表された。このバージョンは現在ではしばしば "SHA-0" と呼ばれる。このバージョンは発表からしばらくしてNSAによって撤回され、1995年に改訂版がFIPS PUB 180-1として発表された。これがSHA-1と呼ばれるものであり、SHA-0とは圧縮関数におけるビット演算のローテートが1つ異なるのみである。NSAによれば、これによってSHA-0においてセキュリティを低下させていたフローが修正されたとしているが、NSAはそれ以上の説明や証拠の提示を行わなかった。その後も、SHA-0、SHA-1の双方についてセキュリティ脆弱性の報告がなされている。SHA-1は暗号に関する多くのアプリケーションやプロトコルに用いられている。例としては、TLS/SSL、OpenPGP、SSH、S/MIME、IPsecなどが挙げられる。これらではMD5もよく用いられる（SHA-1とMD5はともにMD4の後継である）。SHA-1とSHA-2は、アメリカ合衆国において機密情報を扱う際に法律によって要求されるハッシュアリゴリズムの一つである。FIPS 180-1では、SHA-1を私的にあるいは商業で用いることも推奨している。SHA-1は合衆国政府での利用はほぼ終了しており、NISTでは「連邦組織は、電子署名、タイムスタンプ、衝突への耐性を必要とするアプリケーションでのSHA-1の利用を可及的速やかに中止すべきである。2010以降はSHA-2を利用すべきである」としている。SHA制定の重要な動機はDigital Signature Standardであった。DSAの仕様には、SHA-1を利用する過程が含まれている。SHAハッシュ関数はブロック暗号であるSHACALの基礎となっている。SHA-1ハッシュはGit、Mercurial、Monotoneといった分散型バージョン管理システムにおいても、バージョンの管理やデータの破損、改竄の検出に用いられている。任天堂のWiiにおいては、起動時にSHA-1による署名を検証しているが、これを回避する手法も開発されている。ハッシュ長が "L" ビットであるハッシュ関数において、与えられた特定のハッシュに対応する元のメッセージを見つけることは、総当たり攻撃では 2 の試行で可能である。これは原像攻撃と呼ばれる。一方、同じハッシュを与える2つの異なるメッセージを見つけることは衝突攻撃と呼ばれ、およそ 1.2 * 2 の試行で可能である。後者の理由により、ハッシュ関数の強度はハッシュ長の半分の鍵長の共通鍵暗号と比較される。これより、SHA-1の強度は80ビットであると考えられてきた。暗号研究者によって、SHA-0については衝突ペアが発見され、SHA-1についても当初想定されていた 2 の試行よりもずっと少ない試行で衝突を発生させうる手法が発見された。そのブロック構造、繰り返し構造と、追加的な最終ステップの欠如により、SHAシリーズは伸長攻撃およびpartial-message collision attacksに対して脆弱である。これらの攻撃法により、formula_1 または formula_2 のような鍵をつけたハッシュだけでメッセージが署名されている場合、攻撃者は、そのメッセージを伸長しハッシュを再計算する（鍵を知ることなしにできる）ことでメッセージを改竄することができる。この攻撃に対するもっとも単純な対処法は、ハッシュ計算を2回行うことである。formula_3（ゼロのみからなるブロック formula_4 の長さはハッシュ関数のブロック長と等しい）。2005年初頭、フィンセント・ライメンとElisabeth Oswaldは80ラウンドから53ラウンドに削減されたSHA-1において 2 より少ない試行において衝突を発見する攻撃を報告した。2005年2月、Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yuによって、フルバージョン（80ラウンド）のSHA-1において 2 より少ない試行で衝突を発見できる攻撃が報告された。総当たり攻撃では 2 の試行を必要とする。2005年8月17日、Xiaoyun Wang、Andrew Yao、Frances Yaoによって改良された攻撃が報告され、必要とする試行は 2 まで削減された。2007年12月18日に、Martin Cochranによってこの結果の詳細が説明、検証された。Christophe De CannièreとChristian Rechbergerは"Finding SHA-1 Characteristics: General Results and Applications,"においてさらに攻撃を改良し、ASIACRYPT 2006においてBest Paper Awardを受賞した。64ラウンドに削減されたSHA-1において、2 の圧縮関数の試行で2ブロックの衝突が発見された。この攻撃では 2 の試行しか要しないことから、理論的に破られたものとみなされている Their attack was extended further to 73 rounds (of 80) in 2010 by Grechnikov.。80ラウンドのSHA-1で実際に衝突を発見するには、膨大な計算機資源が必要とされる。そのため、グラーツ工科大学によってSHA-1での衝突発見のためのBOINCプロジェクトが開始されたが、進展がなかったことから2009年に中止された。CRYPTO 2006のRump SessionにおいてChristian RechbergerとChristophe De Cannièreは、攻撃者が少なくともメッセージの一部を選ぶことができるSHA-1での衝突を発見したと主張した。2008年、Stéphane Manuelによって理論的に 2 to 2 の試行で衝突を発見しうる攻撃法が報告された。しかし、ローカル衝突パスが独立でなく、最も効率の良い衝突ベクトルが既知であったことが明らかとなり、この報告は撤回された。Cameron McDonald、Philip Hawkes、Josef Pieprzykは、Eurocrypt 2009のRump sessionにおいて 2 の試行での衝突攻撃を報告したが、それに伴う論文 "Differential Path for SHA-1 with complexity "O"(2)" は著者によって推定が誤りであることが発見され撤回された。2012年には、Marc Stevensによる攻撃法が報告されている。この攻撃では1つのハッシュを破るためにクラウドサーバからCPUリソースを借り受けるためのコストは277万ドルと見積もられている。Stevensは、差分経路攻撃を実装し、この手法をHashClashと呼ばれるプロジェクトで開発した。2010年11月8日、StevensはフルバージョンのSHA-1に対して 2 の圧縮の試行で衝突攻撃に近いものを達成したと主張し、完全な衝突攻撃には 2 の試行で可能だと見積もっている。2015年10月8日、Marc Stevens、Pierre Karpman、Thomas Peyrinによって2 の試行で可能なSHA-1の圧縮関数に対する衝突攻撃が報告された。この攻撃では攻撃者が初期状態を自由に決定できる必要があるため、内部状態の初期状態を選択することができない完全なSHA-1そのものにおける衝突攻撃の成功を直接に意味するものではないが、SHA-1の安全性に対する懸念となる。特に、これまでに報告されている攻撃法が膨大な計算機資源と資金を必要としていたことに対して、今回の報告は完全なSHA-1に対する実用的な攻撃が可能であることを示したものである。報告者によって、この攻撃法は "The SHAppening" と命名された。この攻撃法は報告者による既知の攻撃法に基づいており、高性能かつコストパフォーマンスに優れたNVIDIAのGPUカードを用いたものである。衝突は計64枚のグラフィックカードからなる16ノードのクラスタによって発見された。報告者によれば、同様の衝突を発見するためにはAmazon EC2で2000米ドル分のGPU時間を購入すれば可能であると見積もられている。また、完全なSHA-1において衝突を発見するためには、EC2において7万5000から12万米ドル程度のGPU時間で可能であると報告者は見積もっており、これは国家規模の情報機関ではなく犯罪組織であれば十分に用意できるレベルである。このため、報告者は一刻も早くSHA-1の使用を中止するよう推奨している。CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への攻撃が報告された。ハッシュの衝突は 2 の試行で発見された。2004年、Eli BihamとChenはほぼ同じSHA-0ハッシュを持つ2つのメッセージを発見した。160ビットのハッシュのうち142ビットが一致していた。彼らは80ラウンドから62サウンドに削減したSHA-0における完全な衝突も発見した。2004年8月12日、Joux、Carribault、Lemuet、Jalbyによって、フルバージョンのSHA-0における衝突が報告された。これはChabaudとJouxによる攻撃を一般化したものであり、256基のItanium 2プロセッサを搭載したスーパーコンピュータで80000 CPU時間を費やすことにより（このコンピュータの全計算能力の13日分である）、 2 の試行で衝突を発見した。2004年8月17日のCRYPTO 2004のRump sessionにおいて、Wang、Feng、Lai、YuによってMD5、SHA-1他いくつかのハッシュ関数に対する攻撃の初期的な結果が報告された。SHA-0への攻撃は 2 の試行が必要であり、これはJouxらによるものより優れたものである。2005年2月、Wang、Yin、Yuによって、 2 の試行でSHA-0の衝突を発見可能であることが報告された。CRYPTO 2004における報告の後、NISTは2010年までにSHA-1の使用を終了し、SHA-2に移行するプランを発表した。FIPSに認定されたすべての関数の実装は、NISTとCommunications Security Establishment Canada (CSEC) によるCryptographic Module Validation Programの認定を申請することが可能である。2013年現在、SHA-1については2000以上の実装が認定されている。SHA-1のハッシュの例を、十六進法およびBase64エンコードにて示す。メッセージをわずかでも変更すれば、得られるハッシュ値は大きく変化する。例えば、上の例で codice_1 を codice_2 に変えると、160ビットのハッシュのうち81ビットが変化する。空の入力に対するハッシュ値は以下の通りである。SHA-1の疑似コードは以下の通りである。hh はメッセージダイジェストであり、十六進法 (base 16) あるいはBase64エンコードで表現される。定数は "nothing up my sleeve number" として選択される。4つのラウンド定数 codice_3 はそれぞれ 2、3、5、10の平方根の 2 倍の値である。状態値のうち codice_4 から codice_5 まではMD5と同じであり、codice_6 は類似したものである。FIPS PUB 180-1によるものの代わりに、下記の式をメインループでの codice_7 の計算に用いることができる。Max Locktyukhin は、32-79ラウンドにおけるをで置換することが可能であることを示した。

出典:wikipedia