(Translated by https://www.hiragana.jp/)
SHA-1 - Wikipedia
Wikipedia

SHA-1

暗号あんごう学がく的てきハッシュ関数かんすう

SHA-1（シャーワン[3][4]）は、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日にちに仕様しようを廃止はいし予定よてい[5]。

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回かいの試行しこうで理論りろん上じょう、強つよ衝突しょうとつ耐たい性せいを突破とっぱ[1][2]。

概要がいよう

編集へんしゅう

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に対たいする攻撃こうげき法ほうが発見はっけんされ、将来しょうらい的てきな利用りように十分じゅうぶんな安全あんぜん性せいを有ゆうしていないことが示唆しさされた[6]。NISTは、合衆国がっしゅうこくの政府せいふ組織そしきに対たいして、2010年ねんまでにSHA-1からSHA-2へ移行いこうするよう要請ようせいした[7]。SHA-2に対たいする有効ゆうこうな攻撃こうげき法ほうはいまだ報告ほうこくされていないが、その構造こうぞうはSHA-1に類似るいじしたものである。2012年ねん、公募こうぼを経へて、KeccakがSHA-3として選定せんていされた[7]。2013年ねん11月にはマイクロソフトが、2017年ねんまでにMicrosoft WindowsのTLS/SSLにおいてSHA-1を利用りようした証明しょうめい書しょを受うけ入いれないようにすることを表明ひょうめいした[8]。2014年ねん9月がつにはGoogleも2017年ねんまでにGoogle ChromeにおいてSHA-1による証明しょうめい書しょを受うけ入いれないようにすることを表明ひょうめいした[9]。Mozillaでも同様どうように2017年ねんまでにSHA-1による証明しょうめい書しょを受うけ入いれないようにすることを検討けんとうしている[10][11][12]。

日本にっぽんにおいても、CRYPTRECが2003年ねんの初版しょはんでは推奨すいしょうリストに掲載けいさいされていたSHA-1を2013年ねんの改訂かいていにおいて互換ごかん性せい維持いじのための利用りように限定げんていした運用うんよう監視かんしリストに移行いこうし[13]、総務そうむ省しょうおよび法務省ほうむしょうでは、政府せいふ認証にんしょう基盤きばんおよび電子でんし認証にんしょう登記とうき所しょ（商業しょうぎょう登記とうき認証にんしょう局きょく）においてSHA-1を用もちいた電子でんし証明しょうめい書しょの検証けんしょうを2015年度ねんどまで（特別とくべつの事情じじょうがある場合ばあいは2019年度ねんどまで）に終了しゅうりょうすることとしている[14]。 これらを受うけて、SHA-1を使つかっているウェブサイトはSHA-2への移行いこうが予定よていされており、SHA-2に対応たいおうできないソフトや機器ききによるアクセスは不能ふのうになる[15]。特とくに2009年ねん以前いぜんの携帯けいたい電話機でんわきは一部いちぶを除のぞき内蔵ないぞうソフト更新こうしんが行おこなわれないため、ハードウェアの買かい替かえを余儀よぎなくされる[16][17][18]。

NISTは2030年ねん12月31日にちに仕様しようを廃止はいしする予定よていで、それ以降いこうは米国べいこく政府せいふはSHA-1を使用しようしている商品しょうひんを購入こうにゅうしない予定よてい[5]。

SHA-1 ハッシュ関数かんすう

編集へんしゅう
 
SHA-1 圧縮あっしゅく関数かんすうの1回分かいぶんの繰くり返かえし
A, B, C, D, E：32ビットの状態じょうたいワード
F：非線形ひせんけい関数かんすう
 n nだけ左ひだりローテート
n：操作そうさごとに変化へんか
Wt：ラウンドtにおける拡張かくちょうメッセージワード
Kt:ラウンドtにおける定数ていすう
 ：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を利用りようすべきである」としている[19]。

SHA制定せいていの重要じゅうような動機どうきはDigital Signature Standardであった。DSAの仕様しようには、SHA-1を利用りようする過程かていが含ふくまれている。

SHAハッシュ関数かんすうはブロック暗号あんごうであるSHACALの基礎きそとなっている。

データ完全かんぜん性せい

編集へんしゅう

SHA-1ハッシュはGit、Mercurial、Monotoneといった分散ぶんさん型がたバージョン管理かんりシステムにおいても、バージョンの管理かんりやデータの破損はそん、改竄かいざんの検出けんしゅつに用もちいられている。任天堂にんてんどうのWiiにおいては、起動きどう時じにSHA-1による署名しょめいを検証けんしょうしているが、これを回避かいひする手法しゅほうも開発かいはつされている[20]。

攻撃こうげきと認証にんしょう

編集へんしゅう

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

暗号あんごう研究けんきゅう者しゃによって、SHA-0については衝突しょうとつペアが発見はっけんされ、SHA-1についても当初とうしょ想定そうていされていた 280 の試行しこうよりもずっと少すくない試行しこうで衝突しょうとつを発生はっせいさせうる手法しゅほうが発見はっけんされた。

そのブロック構造こうぞう、繰くり返かえし構造こうぞうと、追加ついか的てきな最終さいしゅうステップの欠如けつじょにより、SHAシリーズは伸長しんちょう攻撃こうげきおよびpartial-message collision attacksに対たいして脆弱ぜいじゃくである[21]。これらの攻撃こうげき法ほうにより、  または   のような鍵かぎをつけたハッシュだけでメッセージが署名しょめいされている場合ばあい、攻撃こうげき者しゃは、そのメッセージを伸長しんちょうしハッシュを再さい計算けいさんする（鍵かぎを知しることなしにできる）ことでメッセージを改竄かいざんすることができる。この攻撃こうげきに対たいするもっとも単純たんじゅんな対処たいしょ法ほうは、ハッシュ計算けいさんを2回かい行おこなうことである。 （ゼロのみからなるブロック   の長ながさはハッシュ関数かんすうのブロック長ちょうと等ひとしい）。

攻撃こうげき

編集へんしゅう

2005年ねん初頭しょとう、フィンセント・ライメンとElisabeth Oswaldは80ラウンドから53ラウンドに削減さくげんされたSHA-1において 280 より少すくない試行しこうにおいて衝突しょうとつを発見はっけんする攻撃こうげきを報告ほうこくした[22]。

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

2005年ねん8月がつ17日にち、Xiaoyun Wang、Andrew Yao、Frances Yaoによって改良かいりょうされた攻撃こうげきが報告ほうこくされ、必要ひつようとする試行しこうは 263 まで削減さくげんされた[24]。2007年ねん12月18日にちに、Martin Cochranによってこの結果けっかの詳細しょうさいが説明せつめい、検証けんしょうされた[25]。

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

CRYPTO 2006のRump SessionにおいてChristian RechbergerとChristophe De Cannièreは、攻撃こうげき者しゃが少すくなくともメッセージの一部いちぶを選えらぶことができるSHA-1での衝突しょうとつを発見はっけんしたと主張しゅちょうした[30][31]。

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

Cameron McDonald、Philip Hawkes、Josef Pieprzykは、Eurocrypt 2009のRump sessionにおいて 252 の試行しこうでの衝突しょうとつ攻撃こうげきを報告ほうこくしたが[34]、それに伴ともなう論文ろんぶん "Differential Path for SHA-1 with complexity O(252)" は著者ちょしゃによって推定すいていが誤あやまりであることが発見はっけんされ撤回てっかいされた[35]。

2012年ねんには、Marc Stevensによる攻撃こうげき法ほうが報告ほうこくされている[36]。この攻撃こうげきでは1つのハッシュを破やぶるためにクラウドサーバからCPUリソースを借かり受うけるためのコストは277万まんドルと見積みつもられている[37]。Stevensは、差分さぶん経路けいろ攻撃こうげきを実装じっそうし、この手法しゅほうをHashClashと呼よばれるプロジェクト[38]で開発かいはつした。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 と命名めいめいされた[39]。

この攻撃こうげき法ほうは報告ほうこく者しゃによる既知きちの攻撃こうげき法ほうに基もとづいており、高性能こうせいのうかつコストパフォーマンスに優すぐれたNVIDIAのGPUカードを用もちいたものである。衝突しょうとつは計けい64枚まいのグラフィックカードからなる16ノードのクラスタによって発見はっけんされた。報告ほうこく者しゃによれば、同様どうようの衝突しょうとつを発見はっけんするためにはAmazon EC2で2000米あめりかドル分ぶんのGPU時間じかんを購入こうにゅうすれば可能かのうであると見積みつもられている[39]。

また、完全かんぜんなSHA-1において衝突しょうとつを発見はっけんするためには、EC2において7万まん5000から12万まん米あめりかドル程度ていどのGPU時間じかんで可能かのうであると報告ほうこく者しゃは見積みつもっている。これは、国家こっか規模きぼの情報じょうほう機関きかんなどにとどまらず、一般いっぱん的てきな犯罪はんざい組織そしきでさえ用意よういできるレベルと言いえる。このため、報告ほうこく者しゃは一刻いっこくも早はやくSHA-1の使用しようを中止ちゅうしするよう推奨すいしょうしている[39]。

衝突しょうとつ例れいの発表はっぴょう

編集へんしゅう

2017年ねん2月がつ23日にち、Googleは「SHAttered」と題だいして[40]、2つのPDFファイルのSHA-1ハッシュを一致いっちさせることに成功せいこうしたと発表はっぴょうした[41]。衝突しょうとつするハッシュの算出さんしゅつには、922京きょう回かいのハッシュ計算けいさん（110台だいのGPUで1年ねんかかる計算けいさん）が必要ひつようであるとしている[41]。これを受うけて、Mozilla Firefoxでも発表はっぴょう翌日よくじつの2月がつ24日にちに、既存きそんのバージョンについてもSHA-1証明しょうめい書しょを無効むこう化かしている[42]。

SHA-0

編集へんしゅう

CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への攻撃こうげきが報告ほうこくされた[43]。ハッシュの衝突しょうとつは 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らによるものより優すぐれたものである[44]。

2005年ねん2月がつ、Wang、Yin、Yuによって、 239 の試行しこうでSHA-0の衝突しょうとつを発見はっけん可能かのうであることが報告ほうこくされた[23][45]。

CRYPTO 2004における報告ほうこくの後のち、NISTは2010年ねんまでにSHA-1の使用しようを終了しゅうりょうし、SHA-2に移行いこうするプランを発表はっぴょうした[46]。

公式こうしき認定にんてい

編集へんしゅう

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

ハッシュ値ちの例れい

編集へんしゅう

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

で置換ちかんすることが可能かのうであることを示しめした[49]。

SHAシリーズの比較ひかく

編集へんしゅう
暗号あんごう学がく的てきハッシュ関数かんすうの比較ひかく [編集へんしゅう]
アルゴリズムとバリエーション 出力しゅつりょく長ちょう
(bits) 		内部ないぶ状態じょうたい長ちょう
(bits) 		ブロック長ちょう
(bits) 		最大さいだいメッセージ長ちょう
(bits) 		ラウンド数すう ビット演算えんざん セキュリティ強度きょうど
(bits) 		パフォーマンスの例れい[51]
(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
(衝突しょうとつ発見はっけん[52])		 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		 制限せいげんなし[53] 24[54] And, Xor, Rot,
Not		 112
128
192
256		 -
SHAKE128
SHAKE256		 d（可変長かへんちょう）
d（可変長かへんちょう）		 1344
1088		 d/2と128のいずれか小ちいさい方ほう
d/2と256のいずれか小ちいさい方ほう		 -


実装じっそうライブラリ

編集へんしゅう

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

脚注きゃくちゅう

編集へんしゅう
  1. ^ Marc Stevens. hashclash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5. https://code.google.com/archive/p/hashclash. 
  2. ^ ShAttered
  3. ^ “シャーワン”. NTTPCコミュニケーションズ. 2017年ねん9月がつ30日にち閲覧えつらん。
  4. ^ “SHA-1とは”. IT用語ようご辞典じてん e-words. 2022年ねん6月がつ29日にち閲覧えつらん。
  5. ^ a b NIST Retires SHA-1 Cryptographic Algorithm | NIST
  6. ^ Bruce Schneier (2005年ねん2月がつ18日にち). “Schneier on Security: Cryptanalysis of SHA-1”. 2014年ねん1月がつ1日にち閲覧えつらん。
  7. ^ a b “Secure Hashing”. NIST. 2014年ねん1月がつ1日にち閲覧えつらん。[1]
  8. ^ “SHA1 Deprecation Policy”. Microsoft (2013年ねん11月12日にち). 2014年ねん1月がつ1日にち閲覧えつらん。
  9. ^ “Intent to Deprecate: SHA-1 certificates”. Google (2014年ねん9月がつ3日にち). 2014年ねん9月がつ4日にち閲覧えつらん。
  10. ^ “Bug 942515 - stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01”. Mozilla. 2014年ねん9月がつ4日にち閲覧えつらん。
  11. ^ “CA:Problematic Practices - MozillaWiki”. Mozilla. 2014年ねん9月がつ9日にち閲覧えつらん。
  12. ^ “Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog”. Mozilla (2014年ねん9月がつ23日にち). 2014年ねん9月がつ24日にち閲覧えつらん。
  13. ^ “電子でんし政府せいふにおける調達ちょうたつのために参照さんしょうすべき暗号あんごうのリスト（ＣＲＹＰＴＲＥＣ暗号あんごうリスト）”. 総務そうむ省しょう及および経済けいざい産業さんぎょう省しょう. 2014年ねん9月がつ4日にち閲覧えつらん。
  14. ^ “政府せいふ機関きかんの情報じょうほうシステムにおいて使用しようされている暗号あんごうアルゴリズムSHA-1及およびRSA1024に係かかる移行いこう指針ししん”. 情報じょうほうセキュリティ対策たいさく推進すいしん会議かいぎ (2012年ねん10月がつ26日にち). 2014年ねん9月がつ4日にち閲覧えつらん。
  15. ^ えきねっとの例れい
  16. ^ サーバ証明しょうめい書しょの切きり替かえによるドコモ ケータイへの影響えいきょうについて2015年ねん7月がつ15日にち
  17. ^ auケータイをご利用りようのお客きゃくさまへ、サーバ証明しょうめい書しょ切きり替かえによる影響えいきょうについて
  18. ^ SoftBank 3G（携帯けいたい電話でんわ）をご利用りようのお客きゃくさまへ サーバ証明しょうめい書しょ切きり替かえによる影響えいきょうのご案内あんない2015年ねん7月がつ15日にち
  19. ^ “NIST's March 2006 Policy on Hash Functions”. NIST (2006年ねん3月がつ15日にち). 2014年ねん1月がつ1日にち閲覧えつらん。
  20. ^ 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."
  21. ^ Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering, John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  22. ^ Cryptology ePrint Archive
  23. ^ a b Schneier on Security: SHA-1 Broken
  24. ^ Schneier on Security: New Cryptanalytic Results Against SHA-1
  25. ^ Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path
  26. ^ Christophe De Cannière, Christian Rechberger (2006-11-15). Finding SHA-1 Characteristics: General Results and Applications. http://www.springerlink.com/content/q42205u702p5604u/. 
  27. ^ “IAIK Krypto Group – Description of SHA-1 Collision Search Project”. 2009年ねん6月がつ30日にち閲覧えつらん。
  28. ^ “Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics”. 2010年ねん7月がつ24日にち閲覧えつらん。
  29. ^ “SHA-1 Collision Search Graz”. 2014年ねん1月がつ2日にち閲覧えつらん。
  30. ^ SHA-1 hash function under pressure – heise Security
  31. ^ Crypto 2006 Rump Schedule
  32. ^ Stéphane Manuel. Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1. http://eprint.iacr.org/2008/469.pdf 2011年ねん5月がつ19日にち閲覧えつらん。. 
  33. ^ Stéphane Manuel. Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1. http://www.springerlink.com/content/u320751102001580/ 2012年ねん10月がつ4日にち閲覧えつらん。.  the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak
  34. ^ SHA-1 collisions now 2^52
  35. ^ International Association for Cryptologic Research
  36. ^ Cryptanalysis of MD5 & SHA-1
  37. ^ When Will We See Collisions for SHA-1?
  38. ^ HashClash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5
  39. ^ a b c “The SHAppening: freestart collisions for SHA-1”. 2015年ねん10月がつ9日にち閲覧えつらん。
  40. ^ https://shattered.io/ 2017年ねん2月がつ26日にち閲覧えつらん。
  41. ^ a b Announcing the first SHA1 collision Google Security Blog、2017年ねん2月がつ23日にち（2017年ねん2月がつ26日にち閲覧えつらん）。
  42. ^ The end of SHA-1 on the Public Web Mozilla Security Blog、2017年ねん2月がつ23日にち（2017年ねん2月がつ26日にち閲覧えつらん）。
  43. ^ Differential Collisions in SHA-0
  44. ^ Freedom to Tinker » Blog Archive » Report from Crypto 2004
  45. ^ （中国ちゅうごく語ご） Sdu.edu.cn, Shandong University
  46. ^ National Institute of Standards and Technology
  47. ^ SHS Validation List
  48. ^ https://www.rfc-editor.org/rfc/rfc3174.html
  49. ^ Locktyukhin, Max; Farrel, Kathy (2010-03-31), “Improving the Performance of the Secure Hash Algorithm (SHA-1)”, Intel Software Knowledge Base (Intel), http://software.intel.com/en-us/articles/improving-the-performance-of-the-secure-hash-algorithm-1/ 2014年ねん1月がつ1日にち閲覧えつらん。 
  50. ^ “Crypto++ 5.6.0 Benchmarks”. 2014年ねん1月がつ1日にち閲覧えつらん。
  51. ^ AMD Opteron 8354 2.2 GHzプロセッサと64ビット版ばんLinuxによる計測けいそく[50]
  52. ^ “Announcing the first SHA1 collision”. 2017年ねん2月がつ23日にち閲覧えつらん。
  53. ^ “The Sponge Functions Corner”. 2016年ねん1月がつ28日にち閲覧えつらん。
  54. ^ “The Keccak sponge function family”. 2016年ねん1月がつ28日にち閲覧えつらん。

参考さんこう文献ぶんけん

編集へんしゅう

関連かんれん項目こうもく

編集へんしゅう

外部がいぶリンク

編集へんしゅう
  • 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)
  • NIST Retires SHA-1 Cryptographic Algorithm
「https://ja.wikipedia.org/w/index.php?title=SHA-1&oldid=101463775」から取得しゅとく