SHA-1
SHA-1(シャーワン[3][4])は、Secure Hash Algorithmシリーズの
アメリカ | |
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 |
概要
SHAシリーズ
SHA-1は、160ビット(20バイト)のハッシュ
廃止
2005
NISTは2030
SHA-1 ハッシュ関数
A, B, C, D, E:32ビットの
F:
n nだけ
n:
Wt:ラウンドtにおける
Kt:ラウンドtにおける
:addition modulo 232
SHA-1は、
オリジナルの
用途
暗号
SHA-1は
SHA-1とSHA-2は、
SHA
SHAハッシュ
データ完全 性
SHA-1ハッシュはGit、Mercurial、Monotoneといった
攻撃 と認証
ハッシュ
そのブロック
攻撃
2005
2005
2005
Christophe De CannièreとChristian Rechbergerは"Finding SHA-1 Characteristics: General Results and Applications,"[26]においてさらに
CRYPTO 2006のRump SessionにおいてChristian RechbergerとChristophe De Cannièreは、
2008
Cameron McDonald、Philip Hawkes、Josef Pieprzykは、Eurocrypt 2009のRump sessionにおいて 252 の
2012
The SHAppening
2015
この
また、
衝突 例 の発表
2017
SHA-0
CRYPTO 98において、Florent ChabaudとAntoine JouxによってSHA-0への
2004
2004
2004
2005
CRYPTO 2004における
公式 認定
FIPSに
ハッシュ値 の例
SHA-1のハッシュの
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
に
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 はメッセージダイジェストであり、
k
はそれぞれ 2、3、5、10の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
で
SHAシリーズの比較
アルゴリズムとバリエーション | (bits) |
(bits) |
ブロック (bits) |
(bits) |
ラウンド |
ビット |
セキュリティ (bits) |
パフォーマンスの (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 ( |
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 |
24[54] | And, Xor, Rot, Not |
112 128 192 256 |
- | |
SHAKE128 SHAKE256 |
d( d( |
1344 1088 |
d/2と128のいずれか d/2と256のいずれか |
- |
実装 ライブラリ
SHA-1をサポートしているライブラリは
脚注
- ^ Marc Stevens. hashclash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5 .
- ^ ShAttered
- ^ “シャーワン”. NTTPCコミュニケーションズ. 2017
年 9月 30日 閲覧 。 - ^ “SHA-1とは”. IT
用語 辞典 e-words. 2022年 6月 29日 閲覧 。 - ^ a b NIST Retires SHA-1 Cryptographic Algorithm | NIST
- ^ Bruce Schneier (2005
年 2月 18日 ). “Schneier on Security: Cryptanalysis of SHA-1”. 2014年 1月 1日 閲覧 。 - ^ a b “Secure Hashing”. NIST. 2014
年 1月 1日 閲覧 。[1] - ^ “SHA1 Deprecation Policy”. Microsoft (2013
年 11月12日 ). 2014年 1月 1日 閲覧 。 - ^ “Intent to Deprecate: SHA-1 certificates”. Google (2014
年 9月 3日 ). 2014年 9月 4日 閲覧 。 - ^ “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日 閲覧 。 - ^ “CA:Problematic Practices - MozillaWiki”. Mozilla. 2014
年 9月 9日 閲覧 。 - ^ “Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog”. Mozilla (2014
年 9月 23日 ). 2014年 9月 24日 閲覧 。 - ^ “
電子 政府 における調達 のために参照 すべき暗号 のリスト(CRYPTREC暗号 リスト)”.総務 省 及 び経済 産業 省 . 2014年 9月 4日 閲覧 。 - ^ “
政府 機関 の情報 システムにおいて使用 されている暗号 アルゴリズムSHA-1及 びRSA1024に係 る移行 指針 ”.情報 セキュリティ対策 推進 会議 (2012年 10月 26日 ). 2014年 9月 4日 閲覧 。 - ^ えきねっとの
例 - ^ サーバ
証明 書 の切 り替 えによるドコモ ケータイへの影響 について2015年 7月 15日 - ^ auケータイをご
利用 のお客 さまへ、サーバ証明 書 切 り替 えによる影響 について - ^ SoftBank 3G(
携帯 電話 )をご利用 のお客 さまへ サーバ証明 書 切 り替 えによる影響 のご案内 2015年 7月 15日 - ^ “NIST's March 2006 Policy on Hash Functions”. NIST (2006
年 3月 15日 ). 2014年 1月 1日 閲覧 。 - ^ 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."
- ^ Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering, John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
- ^ Cryptology ePrint Archive
- ^ a b Schneier on Security: SHA-1 Broken
- ^ Schneier on Security: New Cryptanalytic Results Against SHA-1
- ^ Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path
- ^ Christophe De Cannière, Christian Rechberger (2006-11-15). Finding SHA-1 Characteristics: General Results and Applications .
- ^ “IAIK Krypto Group – Description of SHA-1 Collision Search Project”. 2009
年 6月 30日 閲覧 。 - ^ “Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics”. 2010
年 7月 24日 閲覧 。 - ^ “SHA-1 Collision Search Graz”. 2014
年 1月 2日 閲覧 。 - ^ SHA-1 hash function under pressure – heise Security
- ^ Crypto 2006 Rump Schedule
- ^ Stéphane Manuel. Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1 2011
年 5月 19日 閲覧 。. - ^ Stéphane Manuel. Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1 2012
年 10月 4日 閲覧 。. the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak - ^ SHA-1 collisions now 2^52
- ^ International Association for Cryptologic Research
- ^ Cryptanalysis of MD5 & SHA-1
- ^ When Will We See Collisions for SHA-1?
- ^ HashClash - Framework for MD5 & SHA-1 Differential Path Construction and Chosen-Prefix Collisions for MD5
- ^ a b c “The SHAppening: freestart collisions for SHA-1”. 2015
年 10月 9日 閲覧 。 - ^ https://shattered.io/ 2017
年 2月 26日 閲覧 。 - ^ a b Announcing the first SHA1 collision Google Security Blog、2017
年 2月 23日 (2017年 2月 26日 閲覧 )。 - ^ The end of SHA-1 on the Public Web Mozilla Security Blog、2017
年 2月 23日 (2017年 2月 26日 閲覧 )。 - ^ Differential Collisions in SHA-0
- ^ Freedom to Tinker » Blog Archive » Report from Crypto 2004
- ^ Sdu.edu.cn, Shandong University
- ^ National Institute of Standards and Technology
- ^ SHS Validation List
- ^ https://www.rfc-editor.org/rfc/rfc3174.html
- ^ Locktyukhin, Max; Farrel, Kathy (2010-03-31), “Improving the Performance of the Secure Hash Algorithm (SHA-1)”, Intel Software Knowledge Base (Intel) 2014
年 1月 1日 閲覧 。 - ^ “Crypto++ 5.6.0 Benchmarks”. 2014
年 1月 1日 閲覧 。 - ^ AMD Opteron 8354 2.2 GHzプロセッサと64ビット
版 Linuxによる計測 [50] - ^ “Announcing the first SHA1 collision”. 2017
年 2月 23日 閲覧 。 - ^ “The Sponge Functions Corner”. 2016
年 1月 28日 閲覧 。 - ^ “The Keccak sponge function family”. 2016
年 1月 28日 閲覧 。
参考 文献
- 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), IACR.org
- Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005, CMU.edu
- Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, Crypto 2005 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
- “Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard”. Federal Register 59 (131): 35317–35318. (1994-07-11) 2007
年 4月 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
関連 項目
外部 リンク
- 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