SHA-2

SHA-2は、Secure Hash Algorithmシリーズの暗号学的ハッシュ関数で、SHA-1の改良版である。アメリカ国家安全保障局によって設計され、2001年にアメリカ国立標準技術研究所によって連邦情報処理標準 PUB 180-4として標準化された。

1. 概要
-----

SHA-2には、前身のSHA-1から多くの改良が加えられている。それ以前のハッシュ関数は出力が固定長で強度もその長さによって決まる値に固定されていたが、SHA-2はSHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256の6つのバリエーションを持ち、ハッシュ長は224、256、384、512ビットのいずれかである。

SHA-256とSHA-512は、それぞれ32ビット、64ビットのワード長から計算されるハッシュ関数である。シフト量と追加定数が異なるが、構造自体は本質的に同一であり、ラウンド数のみが異なる。SHA-224とSHA-384は、それぞれSHA-256とSHA-512を単純に切り詰めたバージョンであり、初期値のみが異なる。SHA-512/224とSHA-512/256は、SHA-256ではなくSHA-512を切り詰めたバージョンである。SHA-2シリーズは US によってカバーされているが、アメリカ合衆国は、この特許をロイヤリティフリーで開放している。

2004年にMD5とSHA-0の強衝突耐性が突破され、翌2005年にはSHA-1の突破方法が発表された。以降も攻撃法の研究が進む、といった事態が起きたため、急遽NIST主導で新たな構造を持つアルゴリズムのSHA-3の公募が2007年から5年かけて進められた。公募後、3年の検証を経て、2015年8月にSHA-2の次のスタンダードとしてSHA-3が制定された。SHA-2にはSHA-1と類似する点もあるものの、後述するように当時憂慮されたような事態にはなっていない。

2014年1月現在、SHA-1に有効な攻撃をSHA-2に拡張することは達成されていない。原像攻撃ではSHA-256にて52ラウンドまで、SHA-512にて57ラウンドまで、衝突攻撃ではSHA-256の46ラウンドまでが最良の攻撃法である。

SHA-2は、日本のCRYPTRECおよびヨーロッパのNESSIEにおいて、推奨暗号として採用されている。

2. ハッシュ関数の標準化
-------------

FIPS PUB 180-2において、3つのハッシュ関数がSHAシリーズに追加された。これらは出力されるハッシュ長のビット数からそれぞれSHA-256、SHA-384、SHA-512と呼ばれ、SHA-2と総称される。

アルゴリズムは2001年のFIPS PUB 180-2の草稿にて発表され、レビューやコメントが寄せられた。2002年8月、FIPS PUB 180-2は新たな標準 "Secure Hash Standard" として認定され、1995年に制定されたFIPS PUB 180-1を置き換えた。FIPS PUB 180-2には、180-1で規定されたSHA-1も含まれている。

2004年2月、FIPS PUB 180-2のChange Noticeとして、鍵を2つ用いるトリプルDESの鍵長に合うように定義されたSHA-224が追加された。2008年10月、FIPS PUB 180-3が制定されたが、これはSHA-224をChange Noticeから標準自体に取り込むほかには本質的な変化はなかった。この更新は、ハッシュ関数のセキュリティ情報の更新と、これらSHA-2をSpecial Publications 800-107および800-57において使用することを推奨するためのものであった。詳細なテストデータとハッシュの例が標準から除去され、別文書とされた。

2011年1月、NISTはSP800-131Aを発表した。これは、連邦政府組織におけるセキュリティ強度の下限について、それまでの80ビットの使用を2013年末までに限定し、それ以降は112ビットを下限とするものである。

2012年3月、FIPS PUB 180-4が制定され、SHA-512を切り詰めたバージョンとしてSHA-512/224とSHA-512/256が追加された。また、入力データのパディングをハッシュ計算の前に行なうこととしていた制限が撤廃され、リアルタイムでの音声や映像などにおけるハッシュ計算をコンテンツ生成と同時に行うことが可能となった。最終ブロックのパディングのみは、引き続きハッシュ出力の前に行なうこととされている。

2012年7月、NISTは暗号鍵管理に関するガイドラインであるSP800-57を改訂した。これは、2007年版において112ビット未満の電子署名の生成を2010年末までとしていたものを2013年までに変更するものである。2012年8月にはSP800-107にも同様の変更がなされた。

NISTは2012年に、かねてからコンペティションを進行させていたSHA-3の選出を行った。コンペティションの趣旨によりSHA-3はSHA-2とは類似しないものになっている。

3. 用途
-----

SHA-2ハッシュ関数は、TLS/SSL、OpenPGP、SSH、S/MIME、IPsec、Bitcoinといった広く使われているアプリケーションやプロトコルで利用されている。SHA-256は、Debian GNU/Linuxのソフトウェアパッケージの認証や、DKIMにおけるメッセージ署名標準として利用されている。SHA-512は、ルワンダ国際戦犯法廷におけるビデオアーカイブの認証に用いられている。SHA-256およびSHA-512は、DNSSECでの利用が提唱されている。UnixやLinuxのベンダーでは、パスワードの安全なハッシュ法としてSHA-256やSHA-512への移行を始めている。

SHA-1とSHA-2は、アメリカ合衆国において機密情報を扱う際に法律によって要求されるハッシュアルゴリズムの一つである。FIPS 180-1では、SHA-1を私的にあるいは商業で用いることも推奨している。SHA-1は合衆国政府での利用はほぼ終了しており、NISTでは「連邦組織は、電子署名、タイムスタンプ、衝突への耐性を必要とするアプリケーションでのSHA-1の利用を可及的速やかに中止すべきである。2010以降はSHA-2を利用すべきである」としている。

SHA-2はセキュリティ的にSHA-1より優れているものの、SHA-1ほど広くは用いられていない。その理由として、Microsoft Windows XPのSP2以前がSHA-2をサポートしていないことや、SHA-1において実際の衝突が発見されていなかったために緊迫感に欠けたことが挙げられる。ただし後者については、2017年に2月23日にGoogleとオランダの研究機関CWI Instituteが共同で2つの異なるファイルから同じSHA-1ハッシュ値を生成する衝突に成功した。

また、Windows XPのサポート終了などの背景から、公的機関でのSHA-1の使用を原則的に終了する動きがあり、民間のウェブサイトでもSHA-2へ移行するケースが出始めた。

4. 攻撃と認証
--------

ハッシュ長が //L// ビットであるハッシュ関数において、与えられた特定のハッシュに対応する元のメッセージを見つけることは、総当たり攻撃では 2//L// の試行で可能である。これは原像攻撃と呼ばれる。一方、同じハッシュを与える2つの異なるメッセージを見つけることは衝突攻撃と呼ばれ、およそ 2//L// / 2 の試行で可能である。

SHA-3選定におけるハッシュ関数の解析への興味の増加によって、SHA-2への新しい攻撃が報告されている。最良の攻撃法を下のテーブルに示す。現時点では衝突攻撃のみが現実的な可能性を有しているが、フルバージョンのSHA-2に対する攻撃は成功していない。 Fast Software Encryption 2012において、ソニーの研究者によって、SHA-256で52ラウンドまで、SHA-512で57ラウンドまでbiclique疑似原像攻撃に基づく疑似衝突攻撃が可能であることが報告された。



4.1. 公的認証
---------

FIPSに認定されたすべての関数の実装は、NISTとCommunications Security Establishment Canada によるCryptographic Module Validation Programの認定を申請することが可能である。2013年現在、SHA-256については1300以上、SHA-512については900以上の実装が認定されている。

5. ハッシュ値の例
----------

空の入力に対するハッシュ値：SHA224 0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42fSHA256 0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855SHA384 0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95bSHA512 0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3eSHA512/224 0x 6ed0dd02806fa89e25de060c19d3ac86cabb87d6a0ddd05c333b84f4SHA512/256 0x c672b8d1ef56ed28ab87c3622c5114069bdd3ad7b8f9737498d0c01ecef0967a

入力メッセージのわずかな違いも、出力されるハッシュ値に大きな変化を及ぼす。例えば、メッセージの最後にピリオドを加えた場合：SHA224 0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525SHA224 0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c

6. 疑似コード
--------

SHA-256アルゴリズムの疑似コードは以下の通りである。

//Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 232////Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63////Note 3: The compression function uses 8 working variables, a through h////Note 4: Big-endian convention is used when expressing the constants in this pseudocode,////and when parsing message block data from bytes to words, for example,////the first word of the input message "abc" after padding is 0x61626380//

//Initialize hash values://: h0 := 0x6a09e667 h1 := 0xbb67ae85 h2 := 0x3c6ef372 h3 := 0xa54ff53a h4 := 0x510e527f h5 := 0x9b05688c h6 := 0x1f83d9ab h7 := 0x5be0cd19

//Initialize array of round constants://: k[0..63] := 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

//Pre-processing:// append the bit '1' to the message append k bits '0', where k is the minimum number >= 0 such that the resulting message length  is 448. append length of message , in //bits//, as 64-bit big-endian integer 

//Process the message in successive 512-bit chunks:// break message into 512-bit chunksfor each chunk create a 64-entry message schedule array w[0..63] of 32-bit words//// copy chunk into first 16 words w[0..15] of the message schedule array

//Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array://for i from 16 to 63 s0 :=  xor  xor  s1 :=  xor  xor  w[i] := w[i-16] + s0 + w[i-7] + s1

//Initialize working variables to current hash value:// a := h0 b := h1 c := h2 d := h3 e := h4 f := h5 g := h6 h := h7

//Compression function main loop://for i from 0 to 63 S1 :=  xor  xor  ch :=  xor  and g) temp1 := h + S1 + ch + k[i] + w[i] S0 :=  xor  xor  maj :=  xor  xor  temp2 := S0 + maj

h := g g := f f := e e := d + temp1 d := c c := b b := a a := temp1 + temp2

//Add the compressed chunk to the current hash value:// h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e h5 := h5 + f h6 := h6 + g h7 := h7 + h

//Produce the final hash value :// digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

ch および maj の計算は、SHA-1と同様の手法により最適化できる。

SHA-224は本質的にSHA-256と同じであるが、以下の点が異なる。

初期値 h0 から h7 が異なる
h7 を除去することで出力が得られるSHA-224 initial hash values : h[0..7] := 0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4

SHA-512の構造は本質的にSHA-256と同じであるが、以下の点が異なる。

メッセージが512ビットごとではなく1024ビットごとのチャンクに分けられる
初期値とラウンド定数が64ビットに拡張されている
ラウンド数が64から80に変更されている
メッセージ配列wは64個の32ビットワードではなく、80個の64ビットワードを持つ
メッセージ配列wを拡張するためのループは16～63ではなく16～79
ラウンド定数が最初の80個の素数 2..409 に基づいている
演算に用いられるワード長が64ビットである
末尾に追加されるメッセージ長が128ビットのビッグエンディアンである
シフトとローテートの数が異なるSHA-512 initial hash values :

h[0..7] := 0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179

SHA-512 round constants:

k[0..79] := [ 0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694, 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70, 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b, 0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8, 0x19a4c116b8d2d0c8,
0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3, 0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec, 0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b, 0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817]

SHA-512 Sum & Sigma:

S0 :=  xor  xor  S1 :=  xor  xor 

s0 :=  xor  xor  s1 :=  xor  xor 

SHA-384は本質的にSHA-512と同じであるが、以下の点が異なる。

初期値 h0 から h7 が異なる
h6 および h7 を除去することで出力が得られるSHA-384 initial hash values :

h[0..7] := 0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939, 0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4

SHA-512///t//は本質的にSHA-512と同じであるが、以下の点が異なる。

初期値 h0 から h7 は //SHA-512/t IV generation function// によって与えられる
h0 から h7 の //t// ビット目までで切り詰めることで出力が得られる
//t// が384となることは認められていない
//t// が224および256であるものが認定されている

7. SHAシリーズの比較
-------------

'x86' と表記されたパフォーマンス値は64ビットのプロセッサで32ビットのコードを実行したもの、'x86-64' と表記されたパフォーマンス値は64ビットのプロセッサで64ビットのコードを実行したものである。SHA-256は32ビット計算向けに設計されているが、64ビットプロセッサ向けの最適化の恩恵を受けている。SHA-512の32ビット環境での実装は、64ビット環境でのものと比較すると有意に遅くなっている。これら2つのアルゴリズムの変種のパフォーマンスは、これらと同等である。MD5およびSHA-1の最適な実装の実効速度は4.5 - 6 Cycles/Byteである。このテストはイリノイ大学シカゴ校のhydra8システムおよびhydra9システムによるものである。

8. 実装ライブラリ
----------

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

Botan
libsodium
LibreSSL
OpenSSL
GnuTLS
wolfSSL

9. 脚注
-----

10. 参考文献
--------

Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193

11. 関連項目
--------

タイムスタンプ
HMAC
Hashcash
sha1sum  commands
scrypt

12. 外部リンク
---------

[1] from NIST
[2] – Draft for proposed SHS 
[3] – Proposed SHS 
[4] – Official NIST site for the Secure Hash Standard
[5]  – Current version of the Secure Hash Standard , March 2012
[6] from the NESSIE project
[7] from NIST site
[8] SHA-3 competition
3874}}: A 224-bit One-way Hash Function: SHA-224.
6234}}: US Secure Hash Algorithms SHA and SHA-based HMAC and HKDF. Contains sample C implementation.
[9]