SHA-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 -->
| digest size    = 160 bits
| 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=https://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シリーズ全体の俯瞰については[[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に対する攻撃法が発見され、将来的な利用に十分な安全性を有していないことが示唆された<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=電子政府における調達のために参照すべき暗号のリスト（ＣＲＹＰＴＲＥＣ暗号リスト）|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.docomo.ne.jp/info/notice/pages/150715_00.html サーバ証明書の切り替えによるドコモ ケータイへの影響について]2015年7月15日</ref><ref>[https://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 ハッシュ関数 ==
[[File:SHA-1.svg|thumbnail|right|300px|SHA-1 圧縮関数の1回分の繰り返し<br>
A, B, C, D, E：32ビットの状態ワード<br>
''F''：非線形関数<br>
[[File:lll.png|左シフト]]<sub>''n''</sub> ''n''だけ左ローテート<br>
''n''：操作ごとに変化<br>
W<sub>t</sub>：ラウンドtにおける拡張メッセージワード<br>
K<sub>t</sub>:ラウンドtにおける定数<br>
[[Image:Boxplus.png|Addition]]：addition modulo 2<sup>32</sup>]]

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の双方についてセキュリティ脆弱性の報告がなされている。

== 用途 ==
=== 暗号 ===
{{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を利用する過程が含まれている。

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

=== データ完全性 ===
SHA-1ハッシュは[[Git]]、[[Mercurial]]、[[Monotone]]といった[[分散型バージョン管理システム]]においても、バージョンの管理やデータの破損、改竄の検出に用いられている。[[任天堂]]の[[Wii]]においては、起動時にSHA-1による署名を検証しているが、これを回避する手法も開発されている<ref>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."</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> の長さはハッシュ関数のブロック長と等しい）。

=== 攻撃 ===
2005年初頭、[[フィンセント・ライメン]]とElisabeth Oswaldは80ラウンドから53ラウンドに削減されたSHA-1において 2<sup>80</sup> より少ない試行において衝突を発見する攻撃を報告した<ref>[http://eprint.iacr.org/2005/010 Cryptology ePrint Archive<!-- Bot generated title -->]</ref>。

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

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>。さらに、2010年には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
 | accessdate = 2010-07-24
}}</ref>。80ラウンドのSHA-1で実際に衝突を発見するには、膨大な計算機資源が必要とされる。そのため、[[グラーツ工科大学]]によってSHA-1での衝突発見のための[[BOINC]]プロジェクトが開始されたが、進展がなかったことから2009年に中止された<ref>{{cite web
 | url = http://boinc.iaik.tugraz.at/sha1_coll_search/
 | title = SHA-1 Collision Search Graz
 | accessdate = 2014-01-02
}}</ref>。

CRYPTO 2006のRump SessionにおいてChristian RechbergerとChristophe De Cannièreは、攻撃者が少なくともメッセージの一部を選ぶことができるSHA-1での衝突を発見したと主張した<ref>[http://www.heise-online.co.uk/security/SHA-1-hash-function-under-pressure--/news/77244 SHA-1 hash function under pressure – heise Security<!-- Bot generated title -->]</ref><ref>[http://www.iacr.org/conferences/crypto2006/rumpsched.html Crypto 2006 Rump Schedule<!-- Bot generated title -->]</ref>。

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 [[ランダウの記号|''O'']](2<sup>52</sup>)" は著者によって推定が誤りであることが発見され撤回された<ref>[http://eprint.iacr.org/2009/259 International Association for Cryptologic Research]</ref>。

2012年には、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>[https://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 Differential Collisions in SHA-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> の試行で衝突を発見した。

2004年8月17日のCRYPTO 2004のRump sessionにおいて、Wang、Feng、Lai、Yuによって[[MD5]]、SHA-1他いくつかのハッシュ関数に対する攻撃の初期的な結果が報告された。SHA-0への攻撃は 2<sup>40</sup> の試行が必要であり、これはJouxらによるものより優れたものである<ref>[http://www.freedom-to-tinker.com/archives/000664.html Freedom to Tinker » Blog Archive » Report from Crypto 2004<!-- Bot generated title -->]</ref>。

2005年2月、Wang、Yin、Yuによって、 2<sup>39</sup> の試行でSHA-0の衝突を発見可能であることが報告された<ref name="autogenerated1">[http://www.schneier.com/blog/archives/2005/02/sha1_broken.html Schneier on Security: SHA-1 Broken<!-- Bot generated title -->]</ref><ref>{{zh icon}} [http://www.infosec.sdu.edu.cn/paper/sha0-crypto-author-new.pdf Sdu.edu.cn], [[Shandong University]]</ref>。

CRYPTO 2004における報告の後、NISTは2010年までにSHA-1の使用を終了し、SHA-2に移行するプランを発表した<ref>[http://csrc.nist.gov/groups/ST/toolkit/documents/shs/hash_standards_comments.pdf National Institute of Standards and Technology]</ref>。

=== 公式認定 ===
FIPSに認定されたすべての関数の実装は、NISTとCommunications Security Establishment Canada (CSEC) によるCryptographic Module Validation Programの認定を申請することが可能である。2013年現在、SHA-1については2000以上の実装が認定されている<ref>[http://csrc.nist.gov/groups/STM/cavp/documents/shs/shaval.htm SHS Validation List]</ref>。

== ハッシュ値の例 ==
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=

メッセージをわずかでも変更すれば、得られるハッシュ値は大きく変化する。例えば、上の例で <code>dog</code> を <code>cog</code> に変えると、160ビットのハッシュのうち81ビットが変化する。

 SHA1("The quick brown fox jumps over the lazy '''c'''og")
 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の[[疑似コード]]は以下の通りである。

 <span style="color: green;">''Note 1: All variables are unsigned 32 bits and wrap modulo 2<sup>32</sup> when calculating, except''</span>
         <span style="color: green;">''ml the message length which is 64 bits, and''</span>
         <span style="color: green;">''hh the message digest which is 160 bits.''</span>
 <span style="color: green;">''Note 2: All constants in this pseudo code are in [[endianness|big endian]].''</span>
         <span style="color: green;">''Within each word, the most significant byte is stored in the leftmost byte position''</span>
 
 <span style="color: green;">''Initialize variables:''</span>
 
 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).
 
 <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 &lt; 512 bits '0', so that the resulting message length (in ''bits'')
    is [[modular arithmetic|congruent]] to 448 (mod 512)
 append ml, as a 64-bit [[Endianness|big-endian]] integer. So now the message length is a multiple of 512 bits.
 
 <span style="color: green;">''Process the message in successive 512-bit chunks:''</span>
 break message into 512-bit chunks
 '''for''' each chunk
     break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
 
     <span style="color: green;">''Extend the sixteen 32-bit words into eighty 32-bit words:''</span>
     '''for''' i '''from''' 16 to 79
         w[i] = (w[i-3] '''xor''' w[i-8] '''xor''' w[i-14] '''xor''' w[i-16]) '''[[Circular shift|leftrotate]]''' 1
 
     <span style="color: green;">''Initialize hash value for this chunk:''</span>
     a = h0
     b = h1
     c = h2
     d = h3
     e = h4
 
     <span style="color: green;">''Main loop:''</span><ref>https://www.rfc-editor.org/rfc/rfc3174.html</ref>
     '''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
 
     <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
     h4 = h4 + e
 
 <span style="color:green;">''Produce the final hash value (big-endian) as a 160 bit number:''</span>
 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つのラウンド定数 <code>k</code> はそれぞれ 2、3、5、10の平方根の 2<sup>30</sup> 倍の値である。状態値のうち <code>h0</code> から <code>h3</code> まではMD5と同じであり、<code>h4</code> は類似したものである。

FIPS PUB 180-1によるものの代わりに、下記の式をメインループでの <code>f</code> の計算に用いることができる。

 (0  ≤ i ≤ 19): f = d '''xor''' (b '''and''' (c '''xor''' d))                <span style="color: green;">''(alternative 1)''</span>
 (0  ≤ i ≤ 19): f = (b '''and''' c) '''xor''' (('''not''' b) '''and''' d)          <span style="color: green;">''(alternative 2)''</span>
 (0  ≤ i ≤ 19): f = (b '''and''' c) + (('''not''' b) '''and''' d)            <span style="color: green;">''(alternative 3)''</span>
 (0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       <span style="color: green;">''(alternative 4)''</span>
 &nbsp;
 (40 ≤ i ≤ 59): f = (b '''and''' c) '''or''' (d '''and''' (b '''or''' c))          <span style="color: green;">''(alternative 1)''</span>
 (40 ≤ i ≤ 59): f = (b '''and''' c) '''or''' (d '''and''' (b '''xor''' c))         <span style="color: green;">''(alternative 2)''</span>
 (40 ≤ i ≤ 59): f = (b '''and''' c) + (d '''and''' (b '''xor''' c))          <span style="color: green;">''(alternative 3)''</span>
 (40 ≤ i ≤ 59): f = (b '''and''' c) '''xor''' (b '''and''' d) '''xor''' (c '''and''' d)  <span style="color: green;">''(alternative 4)''</span>

Max Locktyukhin は、32-79ラウンドにおける

 w[i] = (w[i-3] '''xor''' w[i-8] '''xor''' w[i-14] '''xor''' w[i-16]) '''[[Circular shift|leftrotate]]''' 1

を

 w[i] = (w[i-6] '''xor''' w[i-16] '''xor''' w[i-28] '''xor''' w[i-32]) '''[[Circular shift|leftrotate]]''' 2

で置換することが可能であることを示した<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をサポートしているライブラリは以下の通り。

* [[Botan]]
* [[:en:Bouncy_Castle_(cryptography)|Bouncy Castle]]
* [[:en:Cryptlib|cryptlib]]
* [[:en:Crypto++|Crypto++]]
* [[:en:Libgcrypt|Libgcrypt]]
* [[:en:Nettle_(cryptographic_library)|Nettle]]
* [[OpenSSL]]
* [[wolfSSL]]
* [[GnuTLS]]

== 脚注 ==
{{reflist|}}

== 参考文献 ==
{{refbegin}}
* Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. [[CRYPTO]] 1998. pp56–71
* [[Eli Biham]], Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (appeared on CRYPTO 2004), [http://eprint.iacr.org/2004/146/ IACR.org]
* [[Xiaoyun Wang]], Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005, [http://www.cs.cmu.edu/~dbrumley/srg/spring06/sha-0.pdf CMU.edu]
* [[Xiaoyun Wang]], Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto 2005 [http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf MIT.edu]
* [[Henri Gilbert]], [[Helena Handschuh]]: Security Analysis of SHA-256 and Sisters. [[Selected Areas in Cryptography]] 2003: pp175–193
*http://www.unixwiz.net/techtips/iguide-crypto-hashes.html
* {{cite journal|title=Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard|journal=Federal Register|date=1994-07-11|first=|last=|coauthors=|volume=59|issue=131|pages=35317–35318|id= |url=http://frwebgate1.access.gpo.gov/cgi-bin/waisgate.cgi?WAISdocID=5963452267+0+0+0&WAISaction=retrieve|format=|accessdate=2007-04-26}}
* 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
* {{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]]