SHA-1

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

テンプレート:Infobox Encryption method

SHA-1は、アメリカ国家安全保障局 (NSA) によって設計され、アメリカ国立標準技術研究所 (NIST) によってFIPS PUB 180-4として標準化された暗号学的ハッシュ関数である。

SHA-1は、160ビット（20バイト）のハッシュ値を生成する。そのハッシュは、十六進法40桁で表現されることが多い。

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に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された[1]。NISTは、合衆国の政府組織に対して、2010までにSHA-1からSHA-2へ移行するよう要請した[2]。SHA-2に対する有効な攻撃法はいまだ報告されていないが、その構造はSHA-1に類似したものである。2012年、公募を経て、KeccakがSHA-3として選定された[2]。2013年、マイクロソフトは、2017年までにMicrosoft WindowsのTLS/SSLにおいてSHA-1を利用した証明書を受け入れないようにすることを表明した[3]。日本のCRYPTRECにおいても、2003年の初版ではSHA-1は推奨リストに掲載されていたが、2013年の改訂では互換性維持のための利用に限定した運用監視リストに移行された。

SHA-1 ハッシュ関数

ファイル:SHA-1.svg
SHA-1 圧縮関数の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シリーズの比較

テンプレート:Further

テンプレート:SHAシリーズの比較

用途

暗号

テンプレート:Details 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を利用すべきである」としている[4]。

SHA制定の重要な動機はDigital Signature Standardであった。DSAの仕様には、SHA-1を利用する過程が含まれている。

SHAハッシュ関数はブロック暗号であるSHACALの基礎となっている。

データ完全性

SHA-1ハッシュはGit、Mercurial、Monotoneといった分散型バージョン管理システムにおいても、バージョンの管理やデータの破損、改竄の検出に用いられている。任天堂のWiiにおいては、起動時にSHA-1による署名を検証しているが、これを回避する手法も開発されている[5]。

攻撃と認証

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

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

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

攻撃

2005年初頭、Vincent RijmenとElisabeth Oswaldは80ラウンドから53ラウンドに削減されたSHA-1において 280 より少ない試行において衝突を発見する攻撃を報告した[7]。

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

2005年8月17日、Xiaoyun Wang、Andrew Yao、Frances Yaoによって改良された攻撃が報告され、必要とする試行は 263 まで削減された[9]。2007年12月18日に、Martin Cochranによってこの結果の詳細が説明、検証された[10]。

Christophe De CannièreとChristian Rechbergerは"Finding SHA-1 Characteristics: General Results and Applications,"[11]においてさらに攻撃を改良し、ASIACRYPT 2006においてBest Paper Awardを受賞した。64ラウンドに削減されたSHA-1において、 235 の圧縮関数の試行で2ブロックの衝突が発見された。この攻撃では 235 の試行しか要しないことから、理論的にアルゴリズムが破綻したとみなされている[12] Their attack was extended further to 73 rounds (of 80) in 2010 by Grechnikov.[13]。80ラウンドのSHA-1で実際に衝突を発見するには、膨大な計算機資源が必要とされる。そのため、グラーツ工科大学によってSHA-1での衝突発見のためのBOINCプロジェクトが開始されたが、進展がなかったことから2009年に中止された[14]。

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

2008年、Stéphane Manuelによって理論的に 251 to 257 の試行で衝突を発見しうる攻撃法が報告された[17]。しかし、ローカル衝突パスが独立でなく、最も効率の良い衝突ベクトルが既知であったことが明らかとなり、この報告は撤回された[18]。

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

2012年現在、SHA-1に対する最も効率的な攻撃はMarc Stevensによるものであるとされる[21]。この攻撃では1つのハッシュを破るためにクラウドサーバからCPUリソースを借り受けるためのコストは277万ドルと見積もられている[22]。Stevensは、差分経路攻撃を実装し、この手法をHashClashと呼ばれるプロジェクト[23]で開発した。2010年11月8日、StevensはフルバージョンのSHA-1に対して 257.5 の圧縮の試行で衝突攻撃に近いものを達成したと主張し、完全な衝突攻撃には 261 の試行で可能だと見積もっている。

SHA-0

CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への攻撃が報告された[24]。ハッシュの衝突は 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らによるものより優れたものである[25]。

2005年2月、Wang、Yin、Yuによって、 239 の試行でSHA-0の衝突を発見可能であることが報告された[8][26]。

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

公式認定

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

ハッシュ値の例

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:[29]
    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

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

関連項目

脚注

テンプレート:Reflist

参考文献

テンプレート:Refbegin

テンプレート:Refend

外部リンク

テンプレート:Cryptography navbox
  1. ↑ テンプレート:Cite web
  2. ↑ 2.0 2.1 テンプレート:Cite web[1]
  3. ↑ テンプレート:Cite web
  4. ↑ テンプレート:Cite web
  5. ↑ http://debugmo.de/?p=61 Debugmo.de "For verifiying 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."
  6. ↑ Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering, John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  7. ↑ Cryptology ePrint Archive
  8. ↑ 8.0 8.1 Schneier on Security: SHA-1 Broken
  9. ↑ Schneier on Security: New Cryptanalytic Results Against SHA-1
  10. ↑ Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path
  11. ↑ テンプレート:Cite journal
  12. ↑ テンプレート:Cite web
  13. ↑ テンプレート:Cite web
  14. ↑ テンプレート:Cite web
  15. ↑ SHA-1 hash function under pressure – heise Security
  16. ↑ Crypto 2006 Rump Schedule
  17. ↑ テンプレート:Cite journal
  18. ↑ テンプレート:Cite journal the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak
  19. ↑ SHA-1 collisions now 2^52
  20. ↑ International Association for Cryptologic Research
  21. ↑ Cryptanalysis of MD5 & SHA-1
  22. ↑ When Will We See Collisions for SHA-1?
  23. ↑ HashClash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5
  24. ↑ [http://fchabaud.free.fr/English/Publications/sha.pdf Chabaud and Joux, 1998
  25. ↑ Freedom to Tinker » Blog Archive » Report from Crypto 2004
  26. ↑ テンプレート:Zh icon Sdu.edu.cn, Shandong University
  27. ↑ National Institute of Standards and Technology
  28. ↑ SHS Validation List
  29. ↑ http://www.faqs.org/rfcs/rfc3174.html
  30. ↑ テンプレート:Citation
「http://wikippe.e-do-match.com/index.php?title=SHA-1&oldid=220438」から取得