SHA-1

SHA-1

一般
設計者	アメリカ国家安全保障局
初版発行日	1993 (SHA-0), 1995 (SHA-1)
シリーズ	(SHA-0), SHA-1, SHA-2, SHA-3
認証	FIPS PUB 180-4, CRYPTREC（運用監視）
詳細
ダイジェスト長	160 bits
構造	Merkle-Damgård construction
ラウンド数	80
最良の暗号解読法
2011年にMarc Stevensによって261回の試行で理論上、強衝突耐性を突破。

SHA-1（シャーワン）は、Secure Hash Algorithmシリーズの暗号学的ハッシュ関数で、SHAの最初のバージョンであるSHA-0の弱点を修正したものである。National Security Agency（NSA）によって設計され、National Institute of Standards and Technology（NIST）によってFederal Information Processing Standard（FIPS） PUB 180-4として標準化されている。NISTは2030年12月31日に仕様を廃止予定。

概要

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年以前の携帯電話機は一部を除き内蔵ソフト更新が行われないため、ハードウェアの買い替えを余儀なくされる。

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

SHA-1 ハッシュ関数

SHA-1 圧縮関数の1回分の繰り返し
A, B, C, D, E：32ビットの状態ワード
F：非線形関数
_n nだけ左ローテート
n：操作ごとに変化
W_t：ラウンドtにおける拡張メッセージワード
K_t:ラウンドtにおける定数
：addition modulo 2³²

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^L の試行で可能である。これは原像攻撃と呼ばれる。一方、同じハッシュを与える2つの異なるメッセージを見つけることは衝突攻撃と呼ばれ、およそ 1.2 * 2^{L / 2} の試行で可能である。後者の理由により、ハッシュ関数の強度はハッシュ長の半分の鍵長の共通鍵暗号と比較される。これより、SHA-1の強度は80ビットであると考えられてきた。

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

そのブロック構造、繰り返し構造と、追加的な最終ステップの欠如により、SHAシリーズは伸長攻撃およびpartial-message collision attacksに対して脆弱である。これらの攻撃法により、${\mathit {SHA}}({\mathit {message}}\,||\,{\mathit {key}})$ または ${\mathit {SHA}}({\mathit {key}}\,||\,{\mathit {message}})$ のような鍵をつけたハッシュだけでメッセージが署名されている場合、攻撃者は、そのメッセージを伸長しハッシュを再計算する（鍵を知ることなしにできる）ことでメッセージを改竄することができる。この攻撃に対するもっとも単純な対処法は、ハッシュ計算を2回行うことである。${\mathit {SHA_{d}}}({\mathit {message}})={\mathit {SHA}}({\mathit {SHA}}(0^{b}\,||\,{\mathit {message}}))$（ゼロのみからなるブロック $0^{b}$ の長さはハッシュ関数のブロック長と等しい）。

攻撃

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³⁵ の試行しか要しないことから、理論的に破られたものとみなされている。さらに、2010年にはGrechnikovがこの攻撃を73ラウンドのSHA-1に対応するよう拡張している。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^57.5 の圧縮の試行で衝突攻撃に近いものを達成したと主張し、完全な衝突攻撃には 2⁶¹ の試行で可能だと見積もっている。

The SHAppening

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の使用を中止するよう推奨している。

衝突例の発表

2017年2月23日、Googleは「SHAttered」と題して、2つのPDFファイルのSHA-1ハッシュを一致させることに成功したと発表した。衝突するハッシュの算出には、922京回のハッシュ計算（110台のGPUで1年かかる計算）が必要であるとしている。これを受けて、Mozilla Firefoxでも発表翌日の2月24日に、既存のバージョンについてもSHA-1証明書を無効化している。

SHA-0

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エンコードにて示す。

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:
    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の平方根の 2³⁰ 倍の値である。状態値のうち 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シリーズの比較

暗号学的ハッシュ関数の比較

アルゴリズムとバリエーション		出力長 (bits)	内部状態長 (bits)	ブロック長 (bits)	最大メッセージ長 (bits)	ラウンド数	ビット演算	セキュリティ強度 (bits)	パフォーマンスの例 (MiB/s)
MD5		128	128 (4 × 32)	512	264 − 1	64	And, Xor, Rot, Add (mod 232), Or	<64（強衝突）	335
SHA-0		160	160 (5 × 32)	512	264 − 1	80	And, Xor, Rot, Add (mod 232), Or	<80（強衝突）	-
SHA-1		160	160 (5 × 32)	512	264 − 1	80		<63 (衝突発見)	192
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	264 − 1	64	And, Xor, Rot, Add (mod 232), Or, Shr	112 128	139
	SHA-384 SHA-512 SHA-512/224 SHA-512/256	384 512 224 256	512 (8 × 64)	1024	2128 − 1	80	And, Xor, Rot, Add (mod 264), Or, Shr	192 256 112 128	154
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	制限なし	24	And, Xor, Rot, Not	112 128 192 256	-
	SHAKE128 SHAKE256	d（可変長） d（可変長）		1344 1088				d/2と128のいずれか小さい方 d/2と256のいずれか小さい方	-

実装ライブラリ

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
• “Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard”. Federal Register 59 (131): 35317–35318. (1994-07-11). http://frwebgate1.access.gpo.gov/cgi-bin/waisgate.cgi?WAISdocID=5963452267+0+0+0&WAISaction=retrieve 2007年4月26日閲覧。. 
• 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
• RFC 3174 (with sample C implementation)
  • SHA-1 (US Secure Hash Algorithm 1 (SHA1))（IPAによる日本語訳）
• NIST Retires SHA-1 Cryptographic Algorithm