「SHA-1」の版間の差分
削除された内容 追加された内容
伸長攻撃の説明が間違っていたので訂正 |
m →疑似コード: RFCのURLを公式のものに差し替え |
||
| (27人の利用者による、間の48版が非表示) | |||
1行目:
{{Infobox Encryption method
| name = SHA-1
| image =
| caption =
<!-- General -->
| designers = [[アメリカ国家安全保障局]]
| publish date = 1993 (SHA-0),<br /> 1995 (SHA-1)
| series = (SHA-0), SHA-1, [[SHA-2]], [[SHA-3]]
| derived from =
| derived to =
| related to =
| certification = [[連邦情報処理標準|FIPS]] PUB 180-4, [[CRYPTREC]]（運用監視）
<!-- Detail -->
15行目:
| structure = [[Merkle-Damgård construction]]
| rounds = 80
| cryptanalysis = 2011年にMarc Stevensによって2<sup>61</sup>回の試行で理論上、強衝突耐性を突破<ref>{{Cite journal |author=Marc Stevens|title=hashclash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5 |url=
}}
'''SHA-1'''（シャーワン<ref>{{Cite web|和書|url=http://www.nttpc.co.jp/yougo/シャーワン.html|title=シャーワン|publisher=[[NTTPCコミュニケーションズ]]|accessdate=2017-09-30}}</ref><ref>{{Cite web|和書|url=https://e-words.jp/w/SHA-1.html|title=SHA-1とは|publisher=IT用語辞典 e-words|accessdate=2022-06-29}}</ref>）は、[[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日に仕様を廃止予定<ref name="名前なし">[https://www.nist.gov/news-events/news/2022/12/nist-retires-sha-1-cryptographic-algorithm NIST Retires SHA-1 Cryptographic Algorithm | NIST]</ref>。
== 概要 ==
SHAシリーズ全体の俯瞰については[[Secure Hash Algorithm]]の記事を参照のこと。
SHA-1は、160ビット（20バイト）のハッシュ値を生成する。
=== 廃止 ===
以前は、SHA-1はSHAシリーズの中で最も広く用いられてい
2005年、SHA-1に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された<ref>{{cite web | url=http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html | title=Schneier on Security: Cryptanalysis of SHA-1 | author=Bruce Schneier |date=2005-02-18 | accessdate=2014-01-01}}</ref>。NISTは、合衆国の政府組織に対して、2010年までにSHA-1からSHA-2へ移行するよう要請した<ref name="NIST_secure_hashing">{{cite web | url=http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html | title=Secure Hashing | publisher=NIST |accessdate=2014-01-01}}[http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html]</ref>。SHA-2に対する有効な攻撃法はいまだ報告されていないが、その構造はSHA-1に類似したものである。2012年、公募を経て、Keccakが[[SHA-3]]として選定された<ref name="NIST_secure_hashing"/>。2013年
▲SHA-1はSHAシリーズの中で最も広く用いられているものであり、多くのアプリケーションやプロトコルに採用されている。
日本においても、[[CRYPTREC]]が2003年の初版では推奨リストに掲載されていたSHA-1を2013年の改訂において互換性維持のための利用に限定した運用監視リストに移行し<ref>{{Cite web|和書|url=http://www.cryptrec.go.jp/images/cryptrec_ciphers_list_2013.pdf|title=電子政府における調達のために参照すべき暗号のリスト（ＣＲＹＰＴＲＥＣ暗号リスト）|publisher=総務省及び経済産業省|accessdate=2014-09-04}}</ref>、[[総務省]]および[[法務省]]では、[[政府認証基盤]]および[[電子認証登記所]]（商業登記認証局）においてSHA-1を用いた電子証明書の検証を2015年度まで（特別の事情がある場合は2019年度まで）に終了することとしている<ref>{{Cite web|和書| url=http://www.nisc.go.jp/active/general/pdf/angou_ikoushishin.pdf | title=政府機関の情報システムにおいて使用されている暗号アルゴリズムSHA-1及びRSA1024に係る移行指針 | publisher=情報セキュリティ対策推進会議 | date=2012-10-26 | accessdate=2014-09-04}}</ref>。
▲2005年、SHA-1に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された<ref>{{cite web | url=http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html | title=Schneier on Security: Cryptanalysis of SHA-1 | author=Bruce Schneier |date=2005-02-18 | accessdate=2014-01-01}}</ref>。NISTは、合衆国の政府組織に対して、2010までにSHA-1からSHA-2へ移行するよう要請した<ref name="NIST_secure_hashing">{{cite web | url=http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html | title=Secure Hashing | publisher=NIST |accessdate=2014-01-01}}[http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html]</ref>。SHA-2に対する有効な攻撃法はいまだ報告されていないが、その構造はSHA-1に類似したものである。2012年、公募を経て、Keccakが[[SHA-3]]として選定された<ref name="NIST_secure_hashing"/>。2013年、[[マイクロソフト]]は、2017年までに[[Microsoft Windows]]の[[Transport Layer Security|TLS/SSL]]においてSHA-1を利用した証明書を受け入れないようにすることを表明した<ref>{{cite web | url=http://blogs.technet.com/b/pki/archive/2013/11/12/sha1-deprecation-policy.aspx | title=SHA1 Deprecation Policy | publisher=Microsoft | date=2013-11-12 | accessdate=2014-01-01}}</ref>。日本の[[CRYPTREC]]においても、2003年の初版ではSHA-1は推奨リストに掲載されていたが、2013年の改訂では互換性維持のための利用に限定した運用監視リストに移行された。
これらを受けて、SHA-1を使っている[[ウェブサイト]]はSHA-2への移行が予定されており、SHA-2に対応できないソフトや機器によるアクセスは不能になる<ref>[https://www.eki-net.com/top/oshirase/20160121/security_information.html えきねっとの例]</ref>。特に2009年以前の携帯電話機は一部を除き内蔵ソフト更新が行われないため、ハードウェアの買い替えを余儀なくされる<ref>[https://www.nttdocomo.co.jp/info/notice/pages/150715_00.html サーバ証明書の切り替えによるドコモ ケータイへの影響について]2015年7月15日</ref><ref>[http://www.kddi.com/important-news/20150715/ auケータイをご利用のお客さまへ、サーバ証明書切り替えによる影響について]</ref><ref>[http://www.softbank.jp/mobile/info/personal/news/support/20150715a/ SoftBank 3G（携帯電話）をご利用のお客さまへ サーバ証明書切り替えによる影響のご案内]2015年7月15日</ref>。
NISTは2030年12月31日に仕様を廃止する予定で、それ以降は米国政府はSHA-1を使用している商品を購入しない予定<ref name="名前なし"/>。
== SHA-1 ハッシュ関数 ==
41 ⟶ 47行目:
オリジナルの仕様は、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シリーズの比較 ==▼
{{SHAシリーズの比較}}▼
== 用途 ==
=== 暗号 ===
{{details|暗号学的ハッシュ関数#用途}}
SHA-1は暗号に関する多くのアプリケーションやプロトコルに用いられている。例としては、[[Transport Layer Security|TLS/SSL]]、[[OpenPGP]]、[[Secure Shell|SSH]]、[[S/MIME]]、[[IPsec]]などが挙げられる。これらでは[[MD5]]もよく用いられる（SHA-1とMD5はともにMD4の後継である）。
SHA-1とSHA-2は、アメリカ合衆国において機密情報を扱う際に法律によって要求されるハッシュア
SHA制定の重要な動機は[[Digital Signature Algorithm|Digital Signature Standard]]であった。DSAの仕様には、SHA-1を利用する過程が含まれている。
62 ⟶ 60行目:
=== データ完全性 ===
SHA-1ハッシュは[[Git]]、[[Mercurial]]、[[Monotone]]といった[[分散型バージョン管理システム]]においても、バージョンの管理やデータの破損、改竄の検出に用いられている。[[任天堂]]の[[Wii]]においては、起動時にSHA-1による署名を検証しているが、これを回避する手法も開発されている<ref>http://debugmo.de/?p=61 Debugmo.de "For
== 攻撃と認証 ==
ハッシュ長が ''L'' ビットであるハッシュ関数において、与えられた特定のハッシュに対応する元のメッセージを見つけることは、[[総当たり攻撃]]では 2<sup>''L''</sup> の試行で可能である。これは[[原像攻撃]]と呼ばれる。一方、同じハッシュを与える2つの異なるメッセージを見つけることは[[誕生日攻撃|衝突攻撃]]と呼ばれ、およそ 1.2 * 2<sup>''L'' / 2</sup> の試行で可能である。後者の理由により、ハッシュ関数の強度はハッシュ長の半分の鍵長の共通鍵暗号と比較される。これより、SHA-1の強度は80ビットであると考えられてきた。
暗号研究者によって、SHA-0については衝突ペアが発見され、SHA-1についても当初想定されていた 2<sup>80</sup> の試行よりもずっと少ない試行で衝突を発生させうる
そのブロック構造、繰り返し構造と、追加的な最終ステップの欠如により、SHAシリーズは[[伸長攻撃]]およびpartial-message collision attacksに対して脆弱である<ref>[http://www.schneier.com/book-ce.html Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering], John Wiley & Sons, 2010. ISBN 978-0-470-47424-2</ref>。これらの攻撃法により、<math>\mathit{SHA}(\mathit{message}\, || \,\mathit{key})</math> または <math>\mathit{SHA}(\mathit{key}\, || \,\mathit{message})</math> のような鍵をつけたハッシュだけでメッセージが署名されている場合、攻撃者は、そのメッセージを伸長しハッシュを再計算する（鍵を知ることなしにできる）ことでメッセージを改竄することができる。この攻撃に対するもっとも単純な対処法は、ハッシュ計算を2回行うことである。<math>\mathit{SHA_d}(\mathit{message}) = \mathit{SHA}(\mathit{SHA}(0^b\, || \,\mathit{message}))</math>（ゼロのみからなるブロック <math>0^b</math> の長さはハッシュ関数のブロック長と等しい）。
=== 攻撃 ===
2005年初頭、
2005年2月、Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yuによって、フルバージョン（80ラウンド）のSHA-1において 2<sup>69</sup> より少ない試行で衝突を発見できる攻撃が報告された<ref name="autogenerated1" />。総当たり攻撃では 2<sup>80</sup> の試行を必要とする。
78 ⟶ 76行目:
2005年8月17日、Xiaoyun Wang、Andrew Yao、Frances Yaoによって改良された攻撃が報告され、必要とする試行は 2<sup>63</sup> まで削減された<ref>[http://www.schneier.com/blog/archives/2005/08/new_cryptanalyt.html Schneier on Security: New Cryptanalytic Results Against SHA-1<!-- Bot generated title -->]</ref>。2007年12月18日に、Martin Cochranによってこの結果の詳細が説明、検証された<ref>[http://eprint.iacr.org/2007/474 Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path]</ref>。
Christophe De CannièreとChristian Rechbergerは"Finding SHA-1 Characteristics: General Results and Applications,"<ref>{{Cite journal |author=Christophe De Cannière, Christian Rechberger |date=2006-11-15 |title=Finding SHA-1 Characteristics: General Results and Applications |url=http://www.springerlink.com/content/q42205u702p5604u/ }}</ref>においてさらに攻撃を改良し、ASIACRYPT 2006においてBest Paper Awardを受賞した。64ラウンドに削減されたSHA-1において、
| url = http://www.iaik.tugraz.at/content/research/krypto/sha1/SHA1Collision_Description.php
| title = IAIK Krypto Group – Description of SHA-1 Collision Search Project
| accessdate = 2009-06-30
}}</ref>
| url = http://eprint.iacr.org/2010/413
| title = Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics
96 ⟶ 94行目:
2008年、Stéphane Manuelによって理論的に 2<sup>51</sup> to 2<sup>57</sup> の試行で衝突を発見しうる攻撃法が報告された<ref>{{Cite journal | author=Stéphane Manuel | title=Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1 |url=http://eprint.iacr.org/2008/469.pdf | accessdate = 2011-05-19 }}</ref>。しかし、ローカル衝突パスが独立でなく、最も効率の良い衝突ベクトルが既知であったことが明らかとなり、この報告は撤回された<ref>{{Cite journal | author=Stéphane Manuel | title=Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1 |url=http://www.springerlink.com/content/u320751102001580/ | accessdate = 2012-10-04 }} ''the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak''</ref>。
Cameron McDonald、Philip Hawkes、Josef Pieprzykは、Eurocrypt 2009のRump sessionにおいて 2<sup>52</sup> の試行での衝突攻撃を報告したが<ref>[http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf SHA-1 collisions now 2^52 ]</ref>、それに伴う論文 "Differential Path for SHA-1 with complexity [[
2012年
==== The SHAppening ====
2015年10月8日、Marc Stevens、Pierre Karpman、Thomas Peyrinによって2<sup>57</sup> の試行で可能なSHA-1の圧縮関数に対する衝突攻撃が報告された。この攻撃では攻撃者が初期状態を自由に決定できる必要があるため、内部状態の初期状態を選択することができない完全なSHA-1そのものにおける衝突攻撃の成功を直接に意味するものではないが、SHA-1の安全性に対する懸念となる。特に、これまでに報告されている攻撃法が膨大な計算機資源と資金を必要としていたことに対して、今回の報告は完全なSHA-1に対する実用的な攻撃が可能であることを示したものである。報告者によって、この攻撃法は ''The SHAppening'' と命名された<ref name="shappening" />。
この攻撃法は報告者による既知の攻撃法に基づいており、高性能かつコストパフォーマンスに優れた[[NVIDIA]]のGPUカードを用いたものである。衝突は計64枚のグラフィックカードからなる16ノードのクラスタによって発見された。報告者によれば、同様の衝突を発見するためには[[Amazon Elastic Compute Cloud|Amazon EC2]]で2000米ドル分のGPU時間を購入すれば可能であると見積もられている<ref name="shappening" />。
また、完全なSHA-1において衝突を発見するためには、EC2において7万5000から12万米ドル程度のGPU時間で可能であると報告者は見積もっている。これは、国家規模の[[情報機関]]などにとどまらず、一般的な犯罪組織でさえ用意できるレベルと言える。このため、報告者は一刻も早くSHA-1の使用を中止するよう推奨している<ref name="shappening">{{cite web |url=https://sites.google.com/site/itstheshappening/ |title=The SHAppening: freestart collisions for SHA-1 |accessdate=2015-10-09 |first1=Marc |last1=Stevens1 |first2=Pierre |last2=Karpman |first3=Thomas |last3=Peyrin}}</ref>。
==== 衝突例の発表 ====
[[2017年]]2月23日、Googleは「SHAttered」と題して<ref>[https://shattered.io/ https://shattered.io/] 2017年2月26日閲覧。</ref>、2つのPDFファイルのSHA-1ハッシュを一致させることに成功したと発表した<ref name="google20170223">[https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html Announcing the first SHA1 collision] Google Security Blog、2017年2月23日（2017年2月26日閲覧）。</ref>。衝突するハッシュの算出には、922京回のハッシュ計算（110台のGPUで1年かかる計算）が必要であるとしている<ref name="google20170223" />。これを受けて、[[Mozilla Firefox]]でも発表翌日の2月24日に、既存のバージョンについてもSHA-1証明書を無効化している<ref>[https://blog.mozilla.org/security/2017/02/23/the-end-of-sha-1-on-the-public-web/ The end of SHA-1 on the Public Web] Mozilla Security Blog、2017年2月23日（2017年2月26日閲覧）。</ref>。
=== SHA-0 ===
CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への攻撃が報告された<ref>[http://fchabaud.free.fr/English/Publications/sha.pdf
2004年、Eli BihamとChenはほぼ同じSHA-0ハッシュを持つ2つのメッセージを発見した。160ビットのハッシュのうち142ビットが一致していた。彼らは80ラウンドから62
2004年8月12日、Joux、Carribault、Lemuet、Jalbyによって、フルバージョンのSHA-0における衝突が報告された。これはChabaudとJouxによる攻撃を一般化したものであり、256基の[[Itanium 2]]プロセッサを搭載した[[スーパーコンピュータ]]で80000 CPU時間を費やすことにより（このコンピュータの全計算能力の13日分である）、 2<sup>51</sup> の試行で衝突を発見した。
136 ⟶ 144行目:
== 疑似コード ==
SHA-1
<span style="color: green;">''Note 1: All variables are unsigned 32 bits and wrap modulo 2<sup>32</sup> when calculating, except''</span>
155 ⟶ 163行目:
<span style="color: green;">''Pre-processing:''</span>
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 [[modular arithmetic|congruent]] to 448 (mod 512)
176 ⟶ 184行目:
e = h4
<span style="color: green;">''Main loop:''</span><ref>
'''for''' i '''from''' 0 '''to''' 79
'''if''' 0 ≤ i ≤ 19 '''then'''
185 ⟶ 193行目:
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
200 ⟶ 208行目:
<span style="color: green;">''Add this chunk's hash to result so far:''</span>
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
234 ⟶ 242行目:
で置換することが可能であることを示した<ref>{{Citation |first1=Max |last1=Locktyukhin |first2=Kathy |last2=Farrel |url=http://software.intel.com/en-us/articles/improving-the-performance-of-the-secure-hash-algorithm-1/ |title=Improving the Performance of the Secure Hash Algorithm (SHA-1) |journal=Intel Software Knowledge Base |publisher=Intel |date=2010-03-31 |accessdate=2014-01-01}}</ref>。
▲== SHAシリーズの比較 ==
== 関連項目 ==▼
▲{{SHAシリーズの比較}}<br />
* [[タイムスタンプ]]▼
* [[衝突 (計算機科学)]]▼
== 実装ライブラリ ==
SHA-1をサポートしているライブラリは以下の通り。
* [[:en:Bouncy_Castle_(cryptography)|Bouncy Castle]]
* [[:en:Cryptlib|cryptlib]]
* [[:en:Crypto++|Crypto++]]
* [[:en:Libgcrypt|Libgcrypt]]
* [[:en:Nettle_(cryptographic_library)|Nettle]]
* [[OpenSSL]]
* [[
* [[
▲* [[sha1sum]]
== 脚注 ==
256 ⟶ 272行目:
* 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
{{refend}}
▲== 関連項目 ==
* [[Secure Hash Algorithm]]
* [[sha1sum]]
* [[RIPEMD-160]]
▲* [[タイムスタンプ]]
▲* [[衝突 (計算機科学)]]
== 外部リンク ==
* [http://csrc.nist.gov/CryptoToolkit/tkhash.html CSRC Cryptographic Toolkit] – Official [[National Institute of Standards and Technology|NIST]] site for the Secure Hash Standard
* [http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf FIPS 180-4: Secure Hash Standard (SHS)] ([[Portable Document Format|PDF]], 1.7 MB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), March 2012
*
** [https://www.nic.ad.jp/ja/tech/ipa/RFC3174JA.html SHA-1 (US Secure Hash Algorithm 1 (SHA1))]（[[情報処理推進機構|IPA]]による日本語訳）
* [https://www.nist.gov/news-events/news/2022/12/nist-retires-sha-1-cryptographic-algorithm NIST Retires SHA-1 Cryptographic Algorithm]
{{Cryptography navbox|hash}}
[[Category:RFC|3174]]
| |||