削除された内容 追加された内容
Claw of Slime (会話 | 投稿記録)
疑似コード: この部分の空行のスペースには意味があるので除去しないでください
m 疑似コード: RFCのURLを公式のものに差し替え
 
(23人の利用者による、間の37版が非表示)
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=httphttps://code.google.com/archive/p/hashclash/ }}</ref>。実際の突破には至っていない<ref>[https://shattered.io ShAttered]</ref>
}}
'''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-1'''は、[[アメリカ国家安全保障局]] (NSA) によって設計され、[[アメリカ国立標準技術研究所]] (NIST) によって[[連邦情報処理標準|FIPS]] PUB 180-4として標準化された[[暗号学的ハッシュ関数]]である。
SHA-1は、160ビット(20バイト)のハッシュ値を生成する。そのハッシュは、[[十六進法]]40桁で表現されることが多い。
 
== 概要 ==
SHAシリーズ全体の俯瞰については[[Secure Hash Algorithm]]の記事を参照のこと。
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「[[Secure Hash Algorithm]]」の略である。SHAには4種類、160ビット(20バイト)ハッリーズが存在し、それぞれ'''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に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された<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年11月には[[マイクロソフト]]が、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>。2014年9月には[[Google]]も2017年までに[[Google Chrome]]においてSHA-1による証明書を受け入れないようにすることを表明した<ref>{{cite web | url=https://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ | title=Intent to Deprecate: SHA-1 certificates | publisher=Google | date=2014-09-03 | accessdate=2014-09-04}}</ref>。Mozillaでも同様に2017年までにSHA-1による証明書を受け入れないようにすることを検討している<ref>{{cite web | url=https://bugzilla.mozilla.org/show_bug.cgi?id=942515 | title=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 | publisher=Mozilla | accessdate=2014-09-04}}</ref><ref>{{cite web | url=https://wiki.mozilla.org/CA:Problematic_Practices#SHA-1_Certificates | title=CA:Problematic Practices - MozillaWiki | publisher=Mozilla | accessdate=2014-09-09}}</ref><ref>{{cite web | url=https://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/ | title=Phasing Out Certificates with SHA-1 based Signature Algorithms <nowiki>|</nowiki> Mozilla Security Blog | publisher=Mozilla | date=2014-09-23 | accessdate=2014-09-24}}</ref>。日本においても、[[CRYPTREC]]が2003年の初版では推奨リストに掲載されていたSHA-1を2013年の改訂において互換性維持のための利用に限定した運用監視リストに移行し<ref>{{Cite web|url=http://www.cryptrec.go.jp/images/cryptrec_ciphers_list_2013.pdf|title=電子政府における調達のために参照すべき暗号のリスト(CRYPTREC暗号リスト)|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>。
以前は、SHA-1はSHAシリーズの中で最も広く用いられていものであり、多くのアプリケーションやプロトコルに採用されていたが、2017年2月には衝突攻撃(強衝突耐性の突破)の成功が現実に示されている。そのため、下記の通りセキュリティの懸念から利用が控えられつつある状況にある。
 
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年11月には[[マイクロソフト]]が、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>。2014年9月には[[Google]]も2017年までに[[Google Chrome]]においてSHA-1による証明書を受け入れないようにすることを表明した<ref>{{cite web | url=https://groups.google.com/a/chromium.org/d/msg/blink-dev/2-R4XziFc7A/i_JipRRJoDQJ | title=Intent to Deprecate: SHA-1 certificates | publisher=Google | date=2014-09-03 | accessdate=2014-09-04}}</ref>。[[Mozilla]]でも同様に2017年までにSHA-1による証明書を受け入れないようにすることを検討している<ref>{{cite web | url=https://bugzilla.mozilla.org/show_bug.cgi?id=942515 | title=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 | publisher=Mozilla | accessdate=2014-09-04}}</ref><ref>{{cite web | url=https://wiki.mozilla.org/CA:Problematic_Practices#SHA-1_Certificates | title=CA:Problematic Practices - MozillaWiki | publisher=Mozilla | accessdate=2014-09-09}}</ref><ref>{{cite web | url=https://blog.mozilla.org/security/2014/09/23/phasing-out-certificates-with-sha-1-based-signature-algorithms/ | title=Phasing Out Certificates with SHA-1 based Signature Algorithms <nowiki>|</nowiki> Mozilla Security Blog | publisher=Mozilla | date=2014-09-23 | accessdate=2014-09-24}}</ref>。日本においても、[[CRYPTREC]]が2003年の初版では推奨リストに掲載されていたSHA-1を2013年の改訂において互換性維持のための利用に限定した運用監視リストに移行し<ref>{{Cite web|url=http://www.cryptrec.go.jp/images/cryptrec_ciphers_list_2013.pdf|title=電子政府における調達のために参照すべき暗号のリスト(CRYPTREC暗号リスト)|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>。
 
日本においても、[[CRYPTREC]]が2003年の初版では推奨リストに掲載されていたSHA-1を2013年の改訂において互換性維持のための利用に限定した運用監視リストに移行し<ref>{{Cite web|和書|url=http://www.cryptrec.go.jp/images/cryptrec_ciphers_list_2013.pdf|title=電子政府における調達のために参照すべき暗号のリスト(CRYPTREC暗号リスト)|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>。
これらを受けて、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 ハッシュ関数 ==
43 ⟶ 49行目:
 
== 用途 ==
 
=== 暗号 ===
{{details|暗号学的ハッシュ関数#用途}}
SHA-1は暗号に関する多くのアプリケーションやプロトコルに用いられている。例としては、[[Transport Layer Security|TLS/SSL]]、[[OpenPGP]]、[[Secure Shell|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を利用すべきである」としている<ref>{{cite web | url=http://csrc.nist.gov/groups/ST/hash/policy_2006.html | title=NIST's March 2006 Policy on Hash Functions | publisher=NIST | date=2006-03-15 |accessdate=2014-01-01}}</ref>。
 
SHA制定の重要な動機は[[Digital Signature Algorithm|Digital Signature Standard]]であった。DSAの仕様には、SHA-1を利用する過程が含まれている。
55 ⟶ 60行目:
 
=== データ完全性 ===
SHA-1ハッシュは[[Git]]、[[Mercurial]]、[[Monotone]]といった[[分散型バージョン管理システム]]においても、バージョンの管理やデータの破損、改竄の検出に用いられている。[[任天堂]]の[[Wii]]においては、起動時にSHA-1による署名を検証しているが、これを回避する手法も開発されている<ref>http://debugmo.de/?p=61 Debugmo.de "For verifiyingverifying 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."</ref>。
 
== 攻撃と認証 ==
ハッシュ長が ''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> の長さはハッシュ関数のブロック長と等しい)。
71 ⟶ 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において、 2<sup>35</sup> の圧縮関数の試行で2ブロックの衝突が発見された。この攻撃では 2<sup>35</sup> の試行しか要しないことから、理論的にアルゴリズムが綻しられものとみなされている<ref>{{cite web
| 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> Their attack was extended further to 73 rounds (of 80) in 。さらに、2010 by 年にはGrechnikov.がこの攻撃を73ラウンドのSHA-1に対応するよう拡張している<ref>{{cite web
| url = http://eprint.iacr.org/2010/413
| title = Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics
91 ⟶ 96行目:
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 [[ランダウの記号|''O'']](2<sup>52</sup>)" は著者によって推定が誤りであることが発見され撤回された<ref>[http://eprint.iacr.org/2009/259 International Association for Cryptologic Research]</ref>。
 
2012年現在、SHA-1対する最も効率的な攻撃Marc Stevensによるものであると攻撃法が報告されている<ref name="Cryptanalysis of MD5 & SHA-1">[http://2012.sharcs.org/slides/stevens.pdf Cryptanalysis of MD5 & SHA-1]</ref>。この攻撃では1つのハッシュを破るためにクラウドサーバからCPUリソースを借り受けるためのコストは277万ドルと見積もられている<ref>[http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html When Will We See Collisions for SHA-1?]</ref>。Stevensは、差分経路攻撃を実装し、この手法をHashClashと呼ばれるプロジェクト<ref>[httphttps://code.google.com/archive/p/hashclash/ HashClash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5]</ref>で開発した。2010年11月8日、StevensはフルバージョンのSHA-1に対して 2<sup>57.5</sup> の圧縮の試行で衝突攻撃に近いものを達成したと主張し、完全な衝突攻撃には 2<sup>61</sup> の試行で可能だと見積もっている。
 
==== 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 ChabaudDifferential andCollisions Joux,in 1998SHA-0]</ref>。ハッシュの衝突は 2<sup>61</sup> の試行で発見された。
 
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<sup>51</sup> の試行で衝突を発見した。
129 ⟶ 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>
169 ⟶ 184行目:
e = h4
<span style="color: green;">''Main loop:''</span><ref>httphttps://www.faqsrfc-editor.org/rfcsrfc/rfc3174.html</ref>
'''for''' i '''from''' 0 '''to''' 79
'''if''' 0 ≤ i ≤ 19 '''then'''
228 ⟶ 243行目:
 
== SHAシリーズの比較 ==
{{SHAシリーズの比較}}<br />
{{Further|Merkle-Damgård construction}}
 
== 実装ライブラリ ==
SHA-1をサポートしているライブラリは以下の通り。
 
* [[Botan]]
{{SHAシリーズの比較}}
* [[:en:Bouncy_Castle_(cryptography)|Bouncy Castle]]
* [[:en:Cryptlib|cryptlib]]
* [[:en:Crypto++|Crypto++]]
* [[:en:Libgcrypt|Libgcrypt]]
* [[:en:Nettle_(cryptographic_library)|Nettle]]
* [[OpenSSL]]
* [[wolfSSL]]
* [[GnuTLS]]
 
== 脚注 ==
257 ⟶ 283行目:
* [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
* RFC{{IETF RFC|3174}} (with sample C implementation)
** [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]]