SHA-1

概要 
SHAシリーズ全体の俯瞰についてはSecure Hash Algorithmの記事を参照のこと。

SHA-1は、160ビット（20バイト）のハッシュ値を生成する。SHA-1はSHA-0にきわめて類似しており、SHA-0において脆弱性の原因となっていた仕様のエラーを修正したものがSHA-1であるため、SHA-0は基本的に全く用いられない。

 廃止 
以前は、SHA-1はSHAシリーズの中で最も広く用いられていたものであり、多くのアプリケーションやプロトコルに採用されていたが、2017年2月には衝突攻撃（強衝突耐性の突破）の成功が現実に示されている。そのため、下記の通りセキュリティの懸念から利用が控えられつつある状況にある。

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年以前の携帯電話機は一部を除き内蔵ソフト更新が行われないため、ハードウェアの買い替えを余儀なくされるサーバ証明書の切り替えによるドコモ ケータイへの影響について2015年7月15日auケータイをご利用のお客さまへ、サーバ証明書切り替えによる影響についてSoftBank 3G（携帯電話）をご利用のお客さまへ サーバ証明書切り替えによる影響のご案内2015年7月15日。

NISTは2030年12月31日に仕様を廃止する予定で、それ以降は米国政府はSHA-1を使用している商品を購入しない予定。

 SHA-1 ハッシュ関数 
A, B, C, D, E：32ビットの状態ワード
F：非線形関数
左シフトn nだけ左ローテート
n：操作ごとに変化
Wt：ラウンドtにおける拡張メッセージワード
Kt:ラウンドtにおける定数
Addition：addition modulo 232

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による署名を検証しているが、これを回避する手法も開発されているhttp://debugmo.de/?p=61 Debugmo.de "For verifying the hash (which is the only thing they verify in the signature), they have chosen to use a function (strncmp) which stops on the first nullbyte – with a positive result. Out of the 160 bits of the SHA1-hash, up to 152 bits are thrown away."。

 攻撃と認証 
ハッシュ長が L ビットであるハッシュ関数において、与えられた特定のハッシュに対応する元のメッセージを見つけることは、総当たり攻撃では 2L の試行で可能である。これは原像攻撃と呼ばれる。一方、同じハッシュを与える2つの異なるメッセージを見つけることは衝突攻撃と呼ばれ、およそ 1.2 * 2L / 2 の試行で可能である。後者の理由により、ハッシュ関数の強度はハッシュ長の半分の鍵長の共通鍵暗号と比較される。これより、SHA-1の強度は80ビットであると考えられてきた。

暗号研究者によって、SHA-0については衝突ペアが発見され、SHA-1についても当初想定されていた 280 の試行よりもずっと少ない試行で衝突を発生させうる手法が発見された。

そのブロック構造、繰り返し構造と、追加的な最終ステップの欠如により、SHAシリーズは伸長攻撃およびpartial-message collision attacksに対して脆弱であるNiels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering, John Wiley & Sons, 2010. ISBN 978-0-470-47424-2。これらの攻撃法により、 または  のような鍵をつけたハッシュだけでメッセージが署名されている場合、攻撃者は、そのメッセージを伸長しハッシュを再計算する（鍵を知ることなしにできる）ことでメッセージを改竄することができる。この攻撃に対するもっとも単純な対処法は、ハッシュ計算を2回行うことである。（ゼロのみからなるブロック  の長さはハッシュ関数のブロック長と等しい）。

 攻撃 
2005年初頭、フィンセント・ライメンとElisabeth Oswaldは80ラウンドから53ラウンドに削減されたSHA-1において 280 より少ない試行において衝突を発見する攻撃を報告したCryptology ePrint Archive。

2005年2月、Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yuによって、フルバージョン（80ラウンド）のSHA-1において 269 より少ない試行で衝突を発見できる攻撃が報告された。総当たり攻撃では 280 の試行を必要とする。

2005年8月17日、Xiaoyun Wang、Andrew Yao、Frances Yaoによって改良された攻撃が報告され、必要とする試行は 263 まで削減されたSchneier on Security: New Cryptanalytic Results Against SHA-1。2007年12月18日に、Martin Cochranによってこの結果の詳細が説明、検証されたNotes on the Wang et al. $2^{63}$ SHA-1 Differential Path。

Christophe De CannièreとChristian Rechbergerは"Finding SHA-1 Characteristics: General Results and Applications,"においてさらに攻撃を改良し、ASIACRYPT 2006においてBest Paper Awardを受賞した。64ラウンドに削減されたSHA-1において、235 の圧縮関数の試行で2ブロックの衝突が発見された。この攻撃では 235 の試行しか要しないことから、理論的に破られたものとみなされている。さらに、2010年にはGrechnikovがこの攻撃を73ラウンドのSHA-1に対応するよう拡張している。80ラウンドのSHA-1で実際に衝突を発見するには、膨大な計算機資源が必要とされる。そのため、グラーツ工科大学によってSHA-1での衝突発見のためのBOINCプロジェクトが開始されたが、進展がなかったことから2009年に中止された。

CRYPTO 2006のRump SessionにおいてChristian RechbergerとChristophe De Cannièreは、攻撃者が少なくともメッセージの一部を選ぶことができるSHA-1での衝突を発見したと主張したSHA-1 hash function under pressure – heise SecurityCrypto 2006 Rump Schedule。

2008年、Stéphane Manuelによって理論的に 251 to 257 の試行で衝突を発見しうる攻撃法が報告された。しかし、ローカル衝突パスが独立でなく、最も効率の良い衝突ベクトルが既知であったことが明らかとなり、この報告は撤回された the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak。

Cameron McDonald、Philip Hawkes、Josef Pieprzykは、Eurocrypt 2009のRump sessionにおいて 252 の試行での衝突攻撃を報告したがSHA-1 collisions now 2^52 、それに伴う論文 "Differential Path for SHA-1 with complexity O(252)" は著者によって推定が誤りであることが発見され撤回されたInternational Association for Cryptologic Research。

2012年には、Marc Stevensによる攻撃法が報告されているCryptanalysis of MD5 & SHA-1。この攻撃では1つのハッシュを破るためにクラウドサーバからCPUリソースを借り受けるためのコストは277万ドルと見積もられているWhen Will We See Collisions for SHA-1?。Stevensは、差分経路攻撃を実装し、この手法をHashClashと呼ばれるプロジェクトHashClash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5で開発した。2010年11月8日、StevensはフルバージョンのSHA-1に対して 257.5 の圧縮の試行で衝突攻撃に近いものを達成したと主張し、完全な衝突攻撃には 261 の試行で可能だと見積もっている。

 The SHAppening 
2015年10月8日、Marc Stevens、Pierre Karpman、Thomas Peyrinによって257 の試行で可能な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の使用を中止するよう推奨している。

 衝突例の発表 
2017年2月23日、Googleは「SHAttered」と題してhttps://shattered.io/ 2017年2月26日閲覧。、2つのPDFファイルのSHA-1ハッシュを一致させることに成功したと発表したAnnouncing the first SHA1 collision Google Security Blog、2017年2月23日（2017年2月26日閲覧）。。衝突するハッシュの算出には、922京回のハッシュ計算（110台のGPUで1年かかる計算）が必要であるとしている。これを受けて、Mozilla Firefoxでも発表翌日の2月24日に、既存のバージョンについてもSHA-1証明書を無効化しているThe end of SHA-1 on the Public Web Mozilla Security Blog、2017年2月23日（2017年2月26日閲覧）。。

 SHA-0 
CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への攻撃が報告されたDifferential Collisions in SHA-0。ハッシュの衝突は 261 の試行で発見された。

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日分である）、 251 の試行で衝突を発見した。

2004年8月17日のCRYPTO 2004のRump sessionにおいて、Wang、Feng、Lai、YuによってMD5、SHA-1他いくつかのハッシュ関数に対する攻撃の初期的な結果が報告された。SHA-0への攻撃は 240 の試行が必要であり、これはJouxらによるものより優れたものであるFreedom to Tinker » Blog Archive » Report from Crypto 2004。

2005年2月、Wang、Yin、Yuによって、 239 の試行でSHA-0の衝突を発見可能であることが報告されたSchneier on Security: SHA-1 Broken Sdu.edu.cn, Shandong University。

CRYPTO 2004における報告の後、NISTは2010年までにSHA-1の使用を終了し、SHA-2に移行するプランを発表したNational Institute of Standards and Technology。

 公式認定 
FIPSに認定されたすべての関数の実装は、NISTとCommunications Security Establishment Canada (CSEC) によるCryptographic Module Validation Programの認定を申請することが可能である。2013年現在、SHA-1については2000以上の実装が認定されているSHS Validation List。

 ハッシュ値の例 
SHA-1のハッシュの例を、十六進法およびBase64エンコードにて示す。

 SHA1("The quick brown fox jumps over the lazy dog")
 gives hexidecimal: 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12
 gives Base64 binary to ASCII text encoding: L9ThxnotKPzthJ7hu3bnORuT6xI=

メッセージをわずかでも変更すれば、得られるハッシュ値は大きく変化する。例えば、上の例で dog を cog に変えると、160ビットのハッシュのうち81ビットが変化する。

 SHA1("The quick brown fox jumps over the lazy cog")
 gives hexidecimal: de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3
 gives Base64 binary to ASCII text encoding: 3p8sf9JeGzr60+haC9F9mxANtLM=

空の入力に対するハッシュ値は以下の通りである。

 SHA1("")
 gives hexidecimal: da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709
 gives Base64 binary to ASCII text encoding: 2jmj7l5rSw0yVb/vlWAYkK/YBwk=

 疑似コード 
SHA-1の疑似コードは以下の通りである。

 Note 1: All variables are unsigned 32 bits and wrap modulo 232 when calculating, except
         ml the message length which is 64 bits, and
         hh the message digest which is 160 bits.
 Note 2: All constants in this pseudo code are in big endian.
         Within each word, the most significant byte is stored in the leftmost byte position

 Initialize variables:

 h0 = 0x67452301
 h1 = 0xEFCDAB89
 h2 = 0x98BADCFE
 h3 = 0x10325476
 h4 = 0xC3D2E1F0

 ml = message length in bits (always a multiple of the number of bits in a character).

 Pre-processing:
 append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits.
 append 0 ≤ k < 512 bits '0', so that the resulting message length (in bits)
    is congruent to 448 (mod 512)
 append ml, as a 64-bit big-endian integer. So now the message length is a multiple of 512 bits.

 Process the message in successive 512-bit chunks:
 break message into 512-bit chunks
 for each chunk
     break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

     Extend the sixteen 32-bit words into eighty 32-bit words:
     for i from 16 to 79
         w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

     Initialize hash value for this chunk:
     a = h0
     b = h1
     c = h2
     d = h3
     e = h4

     Main loop:https://www.rfc-editor.org/rfc/rfc3174.html
     for i from 0 to 79
         if 0 ≤ i ≤ 19 then
             f = (b and c) or ((not b) and d)
             k = 0x5A827999
         else if 20 ≤ i ≤ 39
             f = b xor c xor d
             k = 0x6ED9EBA1
         else if 40 ≤ i ≤ 59
             f = (b and c) or (b and d) or (c and d)
             k = 0x8F1BBCDC
         else if 60 ≤ i ≤ 79
             f = b xor c xor d
             k = 0xCA62C1D6

         temp = (a leftrotate 5) + f + e + k + w[i]
         e = d
         d = c
         c = b leftrotate 30
         b = a
         a = temp

     Add this chunk's hash to result so far:
     h0 = h0 + a
     h1 = h1 + b
     h2 = h2 + c
     h3 = h3 + d
     h4 = h4 + e

 Produce the final hash value (big-endian) as a 160 bit number:
 hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

hh はメッセージダイジェストであり、十六進法 (base 16) あるいはBase64エンコードで表現される。

定数は "nothing up my sleeve number" として選択される。4つのラウンド定数 k はそれぞれ 2、3、5、10の平方根の 230 倍の値である。状態値のうち h0 から h3 まではMD5と同じであり、h4 は類似したものである。

FIPS PUB 180-1によるものの代わりに、下記の式をメインループでの f の計算に用いることができる。

 (0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (alternative 1)
 (0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (alternative 2)
 (0  ≤ i ≤ 19): f = (b and c) + ((not b) and d)            (alternative 3)
 (0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       (alternative 4)

 (40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (alternative 1)
 (40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (alternative 2)
 (40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c))          (alternative 3)
 (40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (alternative 4)

Max Locktyukhin は、32-79ラウンドにおける

 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

を

 w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) leftrotate 2

で置換することが可能であることを示した。

 SHAシリーズの比較 

 実装ライブラリ 
SHA-1をサポートしているライブラリは以下の通り。

 Botan
 Bouncy Castle
 cryptlib
 Crypto++
 Libgcrypt
 Nettle
 OpenSSL
 wolfSSL
 GnuTLS

 脚注 

 参考文献 

 Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71
 Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (appeared on CRYPTO 2004), IACR.org
 Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005, CMU.edu
 Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto 2005 MIT.edu
 Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193
http://www.unixwiz.net/techtips/iguide-crypto-hashes.html

 A. Cilardo, L. Esposito, A. Veniero, A. Mazzeo, V. Beltran, E. Ayugadé, A CellBE-based HPC application for the analysis of vulnerabilities in cryptographic hash functions, High Performance Computing and Communication international conference, August 2010

 関連項目 
 Secure Hash Algorithm
 sha1sum
 RIPEMD-160
 タイムスタンプ
 衝突 (計算機科学)

 外部リンク 
 CSRC Cryptographic Toolkit – Official NIST site for the Secure Hash Standard
 FIPS 180-4: Secure Hash Standard (SHS) (PDF, 1.7 MB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), March 2012
  (with sample C implementation)
 SHA-1 (US Secure Hash Algorithm 1 (SHA1))（IPAによる日本語訳）
 NIST Retires SHA-1 Cryptographic Algorithm

3174