| 词条 | Salsa20 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 释义 |
|name = Salsa20 |image = |caption = The Salsa quarter-round function. Four parallel copies make a round. |designers = Daniel J. Bernstein |publish date = 2007 (designed 2005)[1] |series = |derived from = |derived to = ChaCha |related to = Rumba20 |certification = eSTREAM portfolio |key size = 128 or 256 bits |security claim = |state size = 512 bits |structure = ARX |rounds = 20 |speed = 3.91 cpb on an Intel Core 2 Duo[1] |cryptanalysis = 2008 cryptanalysis breaks 8 out of 20 rounds to recover the 256-bit secret key in 2251 operations, using 231 keystream pairs.[2] }}Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Because the two ciphers are very similar, this article will occasionally discuss them together. Salsa20, the original cipher, was designed in 2005, then later submitted to eSTREAM by Daniel J. Bernstein. ChaCha is a modification of Salsa20 published by Bernstein in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.[3] Both ciphers are built on a pseudorandom function based on add-rotate-xor (ARX) operations — 32-bit addition, bitwise addition (XOR) and rotation operations. The core function maps a 256-bit key, a 64-bit nonce, and a 64-bit counter to a 512-bit block of the key stream (a Salsa version with a 128-bit key also exists). This gives Salsa20 and ChaCha the unusual advantage that the user can efficiently seek to any position in the key stream in constant time. Salsa20 offers speeds of around 4–14 cycles per byte in software on modern x86 processors,[4] and reasonable hardware performance. It is not patented, and Bernstein has written several public domain implementations optimized for common architectures.[5] StructureInternally, the cipher uses bitwise addition ⊕ (exclusive OR), 32-bit addition mod 232 ⊞, and constant-distance rotation operations (<<<) on an internal state of sixteen 32-bit words. Using only add-rotate-xor operations avoids the possibility of timing attacks in software implementations. The internal state is made of sixteen 32-bit words arranged as a 4x4 matrix.
The initial state is made up of 8 words of key, 2 words of stream position, 2 words of nonce (essentially additional stream position bits), and 4 fixed words:
The constant words spell "expand 32-byte k" in ASCII (i.e. the 4 words are "expa", "nd 3", "2-by", and "te k"). This is an example of a nothing up my sleeve number. The core operation in Salsa20 is the quarter-round b ^= (a + d) <<< 7; c ^= (b + a) <<< 9; d ^= (c + b) <<< 13; a ^= (d + c) <<< 18; Odd-numbered rounds apply // Odd round QR( 0, 4, 8, 12) // column 1 QR( 5, 9, 13, 1) // column 2 QR(10, 14, 2, 6) // column 3 QR(15, 3, 7, 11) // column 4 // Even round QR( 0, 1, 2, 3) // row 1 QR( 5, 6, 7, 4) // row 2 QR(10, 11, 8, 9) // row 3 QR(15, 12, 13, 14) // row 4 An implementation in C/C++ appears below.
b ^= ROTL(a + d, 7), \\ c ^= ROTL(b + a, 9), \\ d ^= ROTL(c + b,13), \\ a ^= ROTL(d + c,18))
void salsa20_block(uint32_t out[16], uint32_t const in[16]) {int i; uint32_t x[16]; for (i = 0; i < 16; ++i) x[i] = in[i]; // 10 loops × 2 rounds/loop = 20 rounds for (i = 0; i < ROUNDS; i += 2) { // Odd round QR(x[ 0], x[ 4], x[ 8], x[12]); // column 1 QR(x[ 5], x[ 9], x[13], x[ 1]); // column 2 QR(x[10], x[14], x[ 2], x[ 6]); // column 3 QR(x[15], x[ 3], x[ 7], x[11]); // column 4 // Even round QR(x[ 0], x[ 1], x[ 2], x[ 3]); // row 1 QR(x[ 5], x[ 6], x[ 7], x[ 4]); // row 2 QR(x[10], x[11], x[ 8], x[ 9]); // row 3 QR(x[15], x[12], x[13], x[14]); // row 4 } for (i = 0; i < 16; ++i) out[i] = x[i] + in[i]; } In the last line, the mixed array is added, word by word, to the original array to obtain its 64-byte key stream block. This is important because the mixing rounds on their own are invertible. In other words, applying the reverse operations would produce the original 4×4 matrix, including the key. Adding the mixed array to the original makes it impossible to recover the input. (This same technique is widely used in hash functions from MD4 through SHA-2.) Salsa20 performs 20 rounds of mixing on its input.[6] However, reduced round variants Salsa20/8 and Salsa20/12 using 8 and 12 rounds respectively have also been introduced. These variants were introduced to complement the original Salsa20, not to replace it, and perform even better[7] in the eSTREAM benchmarks than Salsa20, though with a correspondingly lower security margin. XSalsa20 with 192-bit nonceIn 2008, Bernstein proposed a variant of Salsa20 with 192-bit nonces called XSalsa20.[8][9] XSalsa20 is provably secure if Salsa20 is secure, but is more suitable for applications where longer nonces are desired. XSalsa20 feeds the key and the first 128 bits of the nonce into one block of Salsa20 (without the final addition, which may either be omitted, or subtracted after a standard Salsa20 block), and uses 256 bits of the output as the key for standard Salsa20 using the last 64 bits of the nonce and the stream position. Specifically, the 256 bits of output used are those corresponding to the non-secret portions of the input: indexes 0, 5, 10, 15, 6, 7, 8 and 9. eSTREAM selection of Salsa20Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the eSTREAM project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 2.[10] Salsa20 had previously been selected as Phase 2 Focus design for Profile 1 (software) and as a Phase 2 design for Profile 2 (hardware) by the eSTREAM project,[11] but was not advanced to Phase 3 for Profile 2 because eSTREAM felt that it was probably not a good candidate for extremely resource constrained hardware environments.[12] Cryptanalysis of Salsa20{{As of|2015}}, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[2] breaks 8 of the 12 or 20 rounds.In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2165, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".[13] This attack, and all subsequent attacks are based on truncated differential cryptanalysis. In 2006, Fischer, Meier, Berbain, Biasse, and Robshaw reported an attack on Salsa20/6 with estimated time complexity of 2177, and a related-key attack on Salsa20/7 with estimated time complexity of 2217.[14] In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in 2255 operations, using 211.37 keystream pairs.[15] However, this attack does not seem to be competitive with the brute force attack. In 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberger reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2153, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2251. This attack makes use of the new concept of probabilistic neutral key bits for probabilistic detection of a truncated differential. The attack can be adapted to break Salsa20/7 with a 128-bit key.[2] In 2012, the attack by Aumasson et al. was improved by Shi et al. against Salsa20/7 (128-bit key) to a time complexity of 2109 and Salsa20/8 (256-bit key) to 2250.[16] In 2013, Mouha and Preneel published a proof[17] that 15 rounds of Salsa20 was 128-bit secure against differential cryptanalysis. (Specifically, it has no differential characteristic with higher probability than 2−130, so differential cryptanalysis would be more difficult than 128-bit key exhaustion.) ChaCha variant{{Infobox encryption method|name = ChaCha |image = |caption = The ChaCha quarter-round function. Four parallel copies make a round. |designers = Daniel J. Bernstein |publish date = 2008 |series = |derived from = Salsa20 |derived to = |related to = Rumba20 |certification = |key size = 128 or 256 bits |security claim = |state size = 512 bits |structure = ARX |rounds = 20 |speed = 3.95 cpb on an Intel Core 2 Duo{{r|ChaCha|p=2}} |cryptanalysis = }} In 2008, Bernstein published the closely related "ChaCha" family of ciphers, which aim to increase the diffusion per round while achieving the same or slightly better performance.[18] The Aumasson et al. paper also attacks ChaCha, achieving one round fewer: for 256 bits ChaCha6 with complexity 2139 and ChaCha7 with complexity 2248. 128 bits ChaCha6 within 2107, but claims that the attack fails to break 128 bits ChaCha7.[2] Like Salsa20, ChaCha's initial state includes a 128-bit constant, a 256-bit key, a 64-bit counter, and a 64-bit nonce, arranged as a 4×4 matrix of 32-bit words. But ChaCha re-arranges some of the words in the initial state:
The constant is the same as Salsa20 ("expand 32-byte k"). ChaCha replaces the Salsa20 quarter-round a += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7; Notice that this version updates each word twice, while Salsa20's quarter round updates each word only once. In addition, the ChaCha quarter-round diffuses changes more quickly. In average, after changing 1 input bit the Salsa20 quarter-round will change 8 output bits while the ChaCha one will change 12.5 output bits.{{r|ChaCha}} Note also that the ChaCha quarter round has the same number of adds, xors, and bit rotates as the Salsa20 quarter-round, but the fact that two of the rotates are multiples of 8 allows for a small optimization on some architectures including x86.[19] Additionally, the input formatting has been rearranged to support an efficient SSE implementation optimization discovered for Salsa20. Rather than alternating rounds down columns and across rows, they are performed down columns and along diagonals.{{r|ChaCha|p=4}} Like Salsa20, ChaCha arranges the sixteen 32-bit words in a 4x4 matrix. If we index the matrix elements from 0 to 15
Then a double round in ChaCha is // Odd round QR(0, 4, 8, 12) // 1st column QR(1, 5, 9, 13) // 2nd column QR(2, 6, 10, 14) // 3rd column QR(3, 7, 11, 15) // 4th column // Even round QR(0, 5, 10, 15) // diagonal 1 (main diagonal) QR(1, 6, 11, 12) // diagonal 2 QR(2, 7, 8, 13) // diagonal 3 QR(3, 4, 9, 14) // diagonal 4 ChaCha20 uses 10 iterations of the double round.[20] An implementation in C/C++ appears below.
a += b, d ^= a, d = ROTL(d,16), \\ c += d, b ^= c, b = ROTL(b,12), \\ a += b, d ^= a, d = ROTL(d, 8), \\ c += d, b ^= c, b = ROTL(b, 7))
void chacha_block(uint32_t out[16], uint32_t const in[16]) {int i; uint32_t x[16]; for (i = 0; i < 16; ++i) x[i] = in[i]; // 10 loops × 2 rounds/loop = 20 rounds for (i = 0; i < ROUNDS; i += 2) { // Odd round QR(x[0], x[4], x[ 8], x[12]); // column 0 QR(x[1], x[5], x[ 9], x[13]); // column 1 QR(x[2], x[6], x[10], x[14]); // column 2 QR(x[3], x[7], x[11], x[15]); // column 3 // Even round QR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal) QR(x[1], x[6], x[11], x[12]); // diagonal 2 QR(x[2], x[7], x[ 8], x[13]); // diagonal 3 QR(x[3], x[4], x[ 9], x[14]); // diagonal 4 } for (i = 0; i < 16; ++i) out[i] = x[i] + in[i]; } ChaCha is the basis of the BLAKE hash function, a finalist in the NIST hash function competition, and BLAKE2 successor tuned for even higher speed. It also defines a variant using sixteen 64-bit words (1024 bits of state), with correspondingly adjusted rotation constants. XChaChaAlthough not announced by Bernstein, the security proof of XSalsa20 extends straightforwardly to an analogous "XChaCha" cipher. Use the key and the first 128 bits of the nonce (in input words 12 through 15) to form a ChaCha input block, then perform the block operation (omitting the final addition). Output words 0–3 and 12–15 (those words corresponding to non-key words of the input) then form the key used for ordinary ChaCha (with the last 64 bits of nonce and 64 bits of block counter). ChaCha20 adoptionGoogle has selected ChaCha20 along with Bernstein's Poly1305 message authentication code as a replacement for RC4 in TLS, which is used for Internet security.[21] Google's implementation secures https (TLS/SSL) traffic between the Chrome browser on Android phones and Google's websites.[22]Shortly after Google's adoption for TLS, both the ChaCha20 and Poly1305 algorithms were also used for a new chacha20-poly1305@openssh.com cipher in OpenSSH.[23][24] Subsequently, this made it possible for OpenSSH to avoid any dependency on OpenSSL, via a compile-time option.[25] ChaCha20 is also used for the arc4random random number generator in FreeBSD[26], OpenBSD[27], and NetBSD[28] operating systems, instead of the broken RC4, and in DragonFly BSD[29] for the CSPRNG subroutine of the kernel.[30][31] Starting from version 4.8, the Linux kernel uses the ChaCha20 algorithm to generate data for the nonblocking /dev/urandom device.[32][33][34] An implementation reference for ChaCha20 has been published in {{IETF RFC|7539}}. The IETF's implementation modified Bernstein's published algorithm by changing 64-bit nonce and 64-bit block counter to 96-bit nonce and 32-bit block counter,[35] The name was not changed when the algorithm was modified, as it is cryptographically insignificant (both form what a cryptographer would recognize as a 128-bit nonce), but the interface change could be a source of confusion for developers. Because of the reduced block counter, the maximum message length that can be safely encrypted by the IETF's variant is 232 blocks of 64 bytes (256 GiB). For applications where this is not enough, such as file or disk encryption, {{IETF RFC|7539}} proposes using the original algorithm with 64-bit nonce. Use of ChaCha20 in IKE and IPsec have been proposed for standardization in {{IETF RFC|7634}}. Proposed standardization of its use in TLS is published as {{IETF RFC|7905}}. ChaCha20 is used by the WireGuard VPN protocol (exclusively).[36] See also
Notes1. ^{{cite web | url=https://cr.yp.to/snuffle.html#speed | title=Salsa 20 speed; Salsa20 software | author=Daniel J. Bernstein | date=2013-05-16}} 2. ^1 2 3 {{cite journal | title=New Features of Latin Dances | authors=Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger | url=https://eprint.iacr.org/2007/472.pdf | date=2008-03-14}} 3. ^{{Citation| title=ChaCha, a variant of Salsa20| date=28 January 2008| url=https://cr.yp.to/chacha/chacha-20080128.pdf| first=Daniel| last=Bernstein| authorlink=Daniel J. Bernstein| accessdate=2018-06-03}} 4. ^{{cite web| url=https://cr.yp.to/snuffle.html| title=Snuffle 2005: the Salsa20 encryption function| author=Daniel J. Bernstein| date=2013-05-16}} 5. ^{{cite web| url=https://cr.yp.to/salsa20/speed.html| title=Salsa20: Software speed| date=2007-05-11}} 6. ^1 {{cite journal| title=The Salsa20 family of stream ciphers| author=Daniel J. Bernstein| url=https://cr.yp.to/snuffle/salsafamily-20071225.pdf| date=2007-12-24}} 7. ^Since the majority of the work consists of performing the repeated rounds, the number of rounds is inversely proportional to the performance. That is, halving the number of rounds roughly doubles the performance. Reduced-round variants are thus appreciably faster. 8. ^{{cite web| title=Extending the Salsa20 nonce| author=Daniel J. Bernstein| url=https://cr.yp.to/snuffle/xsalsa-20110204.pdf| accessdate=2017-08-22}} 9. ^{{cite web| url=http://www.ecrypt.eu.org/stream/e2-salsa20.html| title=Salsa20/12 ECRYPT II Page| accessdate=2017-08-22}} 10. ^{{cite web| url=http://www.ecrypt.eu.org/stream/endofphase2.html| title=The eSTREAM Project: End of Phase 2| publisher=eSTREAM| date=2008-04-29}} 11. ^{{cite web| url=http://www.ecrypt.eu.org/stream/endofphase1.html| title=eSTREAM PHASE 3: End of Phase 1| author=Hongjun Wu| publisher=eSTREAM| date=2007-03-30}} 12. ^{{cite web| url=http://www.ecrypt.eu.org/stream/PhaseIIreport.pdf| title=eSTREAM: Short Report on the End of the Second Phase| publisher=eSTREAM| date=2007-03-26}} 13. ^{{cite web| url=http://www.ciphergoth.org/crypto/salsa20/| title=Truncated differential cryptanalysis of five rounds of Salsa20| author=Paul Crowley| date=2006-02-09}} 14. ^{{cite book| title=Non-randomness in eSTREAM Candidates Salsa20 and TSC-4| authors= Simon Fischer, Willi Meier, Côme Berbain, Jean-François Biasse , M. J. B. Robshaw| date=2006| journal=Indocrypt 2006| volume= 4329| pages= 2–16| doi=10.1007/11941378_2| series= Lecture Notes in Computer Science| isbn= 978-3-540-49767-7| citeseerx= 10.1.1.121.7248}} 15. ^{{cite journal| title=Differential Cryptanalysis of Salsa20/8| authors=Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima| url=http://www.ecrypt.eu.org/stream/papersdir/2007/010.pdf| date=2007-01-02}} 16. ^{{cite book| title=Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha| authors=Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu| date=2012| journal=ICISC'12 Proceedings of the 15th International Conference on Information Security and Cryptology| volume=7839| pages=337–351| isbn=978-3-642-37681-8| doi=10.1007/978-3-642-37682-5_24| series=Lecture Notes in Computer Science}} 17. ^{{cite journal| title=Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20| author1=Nicky Mouha| author2=Bart Preneel| date=2013| url=https://eprint.iacr.org/2013/328.pdf}} 18. ^{{cite web| url=https://cr.yp.to/chacha.html| title=The ChaCha family of stream ciphers| author=Daniel J. Bernstein| date=2008-04-25}} 19. ^{{Citation| title=Faster ChaCha implementations for Intel processors| url=https://eden.dei.uc.pt/~sneves/chacha/chacha.html| first=Samuel| last=Neves| date=2009-10-07| quote=two of these constants are multiples of 8; this allows for a 1 instruction rotation in Core2 and later Intel CPUs using the pshufb instruction| accessdate=2016-09-07}} 20. ^{{cite web| url=https://datatracker.ietf.org/doc/rfc7539/| title=ChaCha20 and Poly1305 for IETF Protocols: RFC 7539| authors=Y. Nir (Check Point), A. Langley (Google Inc.)| date=May 2015}} 21. ^{{cite web| url=https://tools.ietf.org/html/draft-ietf-tls-chacha20-poly1305-04| title=ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS)| authors=A. Langley, W. Chang, N. Mavrogiannopoulos, J. Strombergson, S. Josefsson| date=2015-12-16| work=Internet Draft}} 22. ^{{cite web| url=https://www.infosecurity-magazine.com/news/google-swaps-out-crypto-ciphers-in-openssl/| title=Google Swaps Out Crypto Ciphers in OpenSSL| date=2014-04-25| publisher=InfoSecurity| archiveurl=https://web.archive.org/web/20181107124824/www.infosecurity-magazine.com/news/google-swaps-out-crypto-ciphers-in-openssl/| archivedate=2018-11-07}} 23. ^{{cite web| url=http://bxr.su/OpenBSD/usr.bin/ssh/PROTOCOL.chacha20poly1305| title=ssh/PROTOCOL.chacha20poly1305| first=Damien| last=Miller| website=Super User's BSD Cross Reference: PROTOCOL.chacha20poly1305| date=2016-05-03| accessdate=2016-09-07}} 24. ^{{cite web| url=https://it.slashdot.org/story/13/12/11/173213/openssh-has-a-new-cipher-chacha20-poly1305-from-dj-bernstein| title=OpenSSH Has a New Cipher — Chacha20-poly1305 — from D.J. Bernstein| first=Constantine A.| last=Murenin| editor=Unknown Lamer| date=2013-12-11| publisher=Slashdot| accessdate=2016-09-07}} 25. ^{{cite web| url=https://it.slashdot.org/story/14/04/30/1822209/openssh-no-longer-has-to-depend-on-openssl| title=OpenSSH No Longer Has To Depend On OpenSSL| first=Constantine A.| last=Murenin| editor=Soulskill| date=2014-04-30| publisher=Slashdot| accessdate=2016-09-07}} 26. ^{{cite web| url=https://svnweb.freebsd.org/base?view=revision&revision=r317015| title=Revision 317015| date=2017-04-16| quote=Replace the RC4 algorithm for generating in-kernel secure random numbers with Chacha20| accessdate=2018-03-16}} 27. ^{{cite web| url=http://bxr.su/OpenBSD/lib/libc/crypt/arc4random.c| title=libc/crypt/arc4random.c| website=Super User's BSD Cross Reference: arc4random.c| editor=guenther (Philip Guenther)| date=2015-09-13| quote=ChaCha based random number generator for OpenBSD.| accessdate=2016-09-07}} 28. ^{{cite web| url=http://bxr.su/NetBSD/lib/libc/gen/arc4random.c| title=libc/gen/arc4random.c| website=Super User's BSD Cross Reference: arc4random.c| editor=riastradh (Taylor Campbell)| date=2016-03-25| quote=Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state.| accessdate=2016-09-07}} 29. ^{{cite web| url=http://bxr.su/DragonFly/sys/kern/subr_csprng.c| title=kern/subr_csprng.c| website=Super User's BSD Cross Reference: subr_csprng.c| date=2015-11-04| quote= chacha_encrypt_bytes| accessdate=2016-09-07}}30. ^{{cite web| url=https://ianix.com/pub/chacha-deployment.html| title=ChaCha Usage & Deployment| date=2016-09-07| accessdate=2016-09-07}} 31. ^{{cite web| url=http://netbsd.gw.com/cgi-bin/man-cgi?arc4random++NetBSD-current| title=arc4random(3)| work=NetBSD Manual Pages| date=2014-11-16| accessdate=2016-09-07}} 32. ^{{cite web| url=https://lwn.net/Articles/686033/| title=Replacing /dev/urandom| website=Linux Weekly News| author=Corbet, Jonathan| accessdate=2016-09-20}} 33. ^{{cite web| url=https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=818e607b57c94ade9824dad63a96c2ea6b21baf3| title=Merge tag 'random_for_linus' of git.kernel.org/pub/scm/linux/kernel/git/tytso/random| website=Linux kernel source tree| quote=random: replace non-blocking pool with a Chacha20-based CRNG| accessdate=2016-09-20}} 34. ^{{cite web| url=https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.8-dev-random| title=/dev/random Seeing Improvements For Linux 4.8| date=2016-07-25| author=Michael Larabel| publisher=Phoronix| accessdate=2016-10-03}} 35. ^{{cite web| url=https://www.ietf.org/proceedings/89/slides/slides-89-cfrg-1.pdf| title=ChaCha20 and Poly1305 for IETF protocols| quote=Changes from regular ChaCha. The nonce: block sequence number split was changed from 64:64 to 96:32| accessdate=2017-08-07}} 36. ^{{cite web |title=Protocol and Cryptography |url=https://www.wireguard.com/protocol/ |website=WireGuard |publisher=Jason A. Donenfeld |accessdate=4 July 2018}} References{{reflist|30em}}External links
3 : Internet Standards|Stream ciphers|Public-domain software with source code |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 随便看 |
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。