Snuffle 2005: the Salsa20 encryption function (original) (raw)

Snuffle 2005 D. J. Bernstein
Hash functions and ciphers Salsa20 specification; Salsa20 design
Salsa20 speed; Salsa20 software
Salsa20 security
Salsa20 prizes
Salsa20 formalities

Salsa20 diffusion
Salsa20 approval

The Salsa20 encryption function, also known as Snuffle 2005, uses theSalsa20 coreto encrypt data.

Salsa20 specification; Salsa20 design

The following paper explains how Salsa20 works:

• [salsafamily]15pp.(PDF)D. J. Bernstein. The Salsa20 family of stream ciphers. Document ID: 31364286077dcdff8e4509f9ff3139ad. URL: https://cr.yp.to/papers.html#salsafamily. Date: 2007.12.25.

The original Salsa20 documentation split this information into two documents (including many extra examples in the specification):

• Salsa20 specification. This document contains the complete definition of the Salsa20 core, the Salsa20 expansion function, and the Salsa20 encryption function.
• Salsa20 design. This document discusses the Salsa20 design, explaining why this particular encryption function is better than other encryption functions.

The following paper defines XSalsa20, a variant of Salsa20 with a longer nonce, and proves that XSalsa20 is secure if Salsa20 is secure:

• [xsalsa]14pp.(PDF)D. J. Bernstein. Extending the Salsa20 nonce. Document ID: c4b172305ff16e1429a48d9434d50e8a. URL: https://cr.yp.to/papers.html#xsalsa. Date: 2011.02.04. Supersedes:(PDF)2008.11.28.

Salsa20 speed; Salsa20 software

There are two documents analyzing Salsa20 performance:

• Salsa20 speed. This document discusses a range of benchmarks relevant to cryptographic speed; estimates Salsa20's performance on those benchmarks; and explains, at a lower level, techniques to achieve this performance. This document is somewhat out of date: it does not reflect some speedups achieved by the current Salsa20 software.
• Salsa20/8 and Salsa20/12. This document proposes reduced-round (8-round and 12-round) variants of Salsa20; presents detailed software benchmarks comparing Salsa20/8 to ABC version 2, 10-round AES, Dragon, HC-256, LEX, NLS, Phelix, Py, Py6, Rabbit, RC4, SNOW, SOSEMANUK, and TRIVIUM; and discusses Salsa20 from a hardware perspective.

There are several Salsa20 implementations:

• test, an initial test implementation. This consists of ecrypt-config.h,ecrypt-machine.h,ecrypt-portable.h, andecrypt-sync.hfrom the ECRYPT Stream Cipher Project;ecrypt.c, which encrypts and decrypts; andbigtest.c, which tries various Salsa20 encryptions and prints occasional checksums of the results, starting with e2d22467015c0ffb0adc5fac0ee88ccf8d467a7f07ab53d4efeac8da47fd833e.
• ref, a reference implementation that fits into the eSTREAM performance-testing framework:salsa20.c,Makefile,ecrypt-sync.h.
• regs:salsa20.c,Makefile,ecrypt-sync.h. Similar to salsa20/refbut uses separate temporary variables instead of a temporary array.
• merged:salsa20.c,Makefile,ecrypt-sync.h. Similar to salsa20/regsbut inlines the Salsa20 core.
• x86-1, specific to the Pentium, Athlon, and other x86 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• x86-2, specific to the Pentium, Athlon, and other x86 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• x86-3, specific to the Pentium, Athlon, and other x86 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Similar to x86-2 but organizes the stack differently.
• x86-pm, specific to the Pentium, Athlon, and other x86 chips:salsa20.s,Makefile,ecrypt-sync.h.
• x86-athlon, specific to the Pentium, Athlon, and other x86 chips:salsa20.s,Makefile,ecrypt-sync.h. Similar to x86-3 but pads instructions to 16-byte boundaries.
• x86-mmx, specific to the Pentium Pro and other CPUs with MMX registers:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Uses some MMX registers as substitutes for stack positions.
• x86-xmm, specific to the Pentium 4 and other CPUs with SSE2 instructions:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• x86-xmm2, specific to the Pentium 4 and other CPUs with SSE2 instructions:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Selects different SSE2 instructions.
• x86-xmm4, specific to the Pentium 4 and other CPUs with SSE2 instructions:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Handles four blocks in parallel. Based on code by Wei Dai.
• x86-xmm5, specific to the Pentium 4 and other CPUs with SSE2 instructions:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Some additional instruction scheduling.
• amd64-1, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• amd64-2, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• amd64-3, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• amd64-xmm, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h.
• amd64-xmm2, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Selects different SSE2 instructions.
• amd64-xmm5, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Handles four blocks in parallel. Translation of x86-xmm5.
• amd64-xmm6, specific to the Athlon 64, Core 2 Duo, and other AMD64 chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Some additional instruction scheduling.
• ppc-altivec, specific to the PowerPC G4 and other CPUs with AltiVec instructions:salsa20.c,Makefile,ecrypt-sync.h. Based on code by Matthijs van Duin.
• sparc, specific to the UltraSPARC and other 64-bit SPARC chips:salsa20.q,salsa20.s,Makefile,ecrypt-sync.h. Some older implementations, limited to the Salsa20 core and not including stream generation, appear on theSalsa20-core speed page.

ECRYPT's test framework reports the following speeds for encrypting a 576-byte packet (or a long stream) with a 256-bit key:

AVR speeds: At the SASC 2007 workshop, Gordon Meiser reported a Salsa20 implementation for an 8MHz ATmega8 taking 292 cycles/byte and using 1514 bytes of flash memory. For comparison, Meiser reported an AES implementation for an 8MHz ATmega16 taking 786 cycles/byte and using 6664 bytes of flash memory.

ARM speeds: At the SASC 2007 workshop, Cedric Lauradoux reported a Salsa20 implementation for a 200MHz ARM920T taking 69 cycles/byte and using just 868 bytes of code. For comparison, Lauradoux reported an AES implementation taking 101 cycles/byte with 15920 bytes of code.

FPGA speeds: At the SASC 2007 workshop, Marcin Rogawski reported an unrolled-double-round Salsa20 implementation using 3510 logic elements on a Altera Cyclone EP1C20F324C6 (130nm process). The implementation is estimated to drain 450.14 mW at 30MHz and produce 1280 Mbps. For comparison, Rogawski reported an AES implementation using 5053 logic elements; the implementation is estimated to drain 1191.01 mW at 105MHz and produce 611 Mbps.

At the IEEE CCECE 2007 workshop, Yan and Heys reported a "compact" Salsa20 implementation using 194 CLB slices and 4 Block RAMs on a Xilinx 2V250fg256. The implementation is estimated to produce 38 Mbps.

ASIC speeds: At the SASC 2007 workshop, Tim Good reported an unrolled-double-round Salsa20 implementation for a 130nm ASIC, with area estimated as 18626 gate equivalents and speed estimated as 668 Mbps at 35.2 MHz. It's quite clear to me that these speeds are highly suboptimal; I look forward to seeing better Salsa20 ASIC implementations. For comparison, Good reported an AES implementation with area estimated as 5398 gate equivalents and speed estimated as 311 Mbps at 131.2 MHz.

At the IEEE CCECE 2007 workshop, Yan and Heys reported three Salsa20 implementations for a 180nm ASIC: a "compact" implementation with area estimated as 14100 gate equivalents and speed estimated as 71.2 Mbps, a "basic" implementation with area estimated as 23408 gate equivalents and speed estimated as 255 Mbps, and a "fast" implementation with area estimated as 470000 gate equivalents and speed estimated as 4800 Mbps.

Other languages: Larry Bugbee has implemented a Python wrapper for Salsa20:https://www.seanet.com/~bugbee/crypto/salsa20/.

Salsa20 security

I have several documents discussing the security of Salsa20:

• Salsa20 security. This document states the Salsa20 security conjectures and explains why the security conjectures are reasonable.
• Notes on the Salsa20 key size. This document discusses my recommendation to use 256-bit keys.
• Disproof of Li An-Ping's claims regarding Salsa20. This document illustrates the importance of computer verification of cryptanalytic claims.
• Response to "On the Salsa20 core function". This document illustrates the importance of Salsa20's diagonal constants.
• Response to "Slid pairs in Salsa20 and Trivium". This document illustrates the fact that "attacks" more expensive than brute force aren't useful.
• [bruteforce]10pp.(PDF) (PS) (DVI)D. J. Bernstein. Understanding brute force. Document ID: 73e92f5b71793b498288efe81fe55dee. URL: https://cr.yp.to/papers.html#bruteforce. Date: 2005.04.25.
  This paper is not specific to Salsa20. It discusses the tremendous power of a parallel brute-force key-search machine, and corrects several related errors in the literature. See also the Salsa20 diffusion page.

Cryptanalysts are strongly encouraged

• to generalize their attacks from 32-bit words to w-bit words for every w in {2,4,6,8,...,32};
• to generalize their attacks from 20 rounds to r rounds for every r in {2,4,6,8,...,20};
• to state the success probability of the attack for all pairs (w,r);
• to state the time taken by the attack for all pairs (w,r);
• to state the price of the attack machine (memory, etc.) for all pairs (w,r); and
• to publish software verifying these statements for as many pairs (w,r) as possible. Every attack should be fast when w and r are small; and there is no excuse for failing to have a computer verify that a fast attack works.

Independent cryptanalysis:

• 2005.10: Crowleyreported
  • a 2^165-operation attack on Salsa20/5.
    The attack works forwards from a small known input difference to a biased bit 3 rounds later, and works 2 rounds backwards from an output after guessing 160 relevant key bits.
• 2006.12: Fischer, Meier, Berbain, Biasse, and Robshawreported
  • a 2^177-operation attack on Salsa20/6 and
  • a much faster attack on Salsa20/5, clearly breaking Salsa20/5.
    The Salsa20/6 attack works forwards from a small known input difference to a biased bit 4 rounds later, and works 2 rounds backwards from an output after guessing 160 relevant key bits.
• 2007.01:Tsunoo, Saito, Kubo, Suzaki, and Nakashimareported
  • a 2^184-operation attack on Salsa20/7 and
  • a much faster attack on Salsa20/6, clearly breaking Salsa20/6.
    The Salsa20/7 attack works forwards from a small known input difference to a biased bit 4 rounds later, and works 3 rounds backwards from an output after guessing 171 highly relevant key bits.
• 2007.12: Aumasson, Fischer, Khazaei, Meier, and Rechbergerreported
  • a 2^249-operation attack on Salsa20/8,
  • a 2^248-operation attack on ChaCha7,
  • a 2^153-operation attack on Salsa20/7, and
  • a 2^139-operation attack on ChaCha6.
    The Salsa20/8 attack works forwards from a small known input difference to a biased bit 4 rounds later, and works 4 rounds backwards from an output after guessing 228 extremely relevant key bits. (See alsoFischer's thesis, 2008.04.)
• 2012.11:Shi, Zhang, Feng, and Wureported
  • a 2^250-operation attack on Salsa20/8 (while saying that the previous attack takes 2^251 operations),
  • a 2^246.5-operation attack on ChaCha7,
  • a 2^148-operation attack on Salsa20/7 (while saying that the previous attack takes 2^151 operations), and
  • a 2^136-operation attack on ChaCha6.
• 2015.03: Maitra, Paul, and Meierreported
  • a 2^247.2-operation attack on Salsa20/8.
• 2015.07: Maitrareported
  • a 2^245.5-operation attack on Salsa20/8 and
  • a 2^239-operation attack on ChaCha7.
• 2016.10: Choudhuri and Maitrareported
  • a 2^244-operation attack on Salsa20/8,
  • a 2^233-operation attack on ChaCha7,
  • a 2^137-operation attack on Salsa20/7,
  • a 2^127.5-operation attack on ChaCha6, and
  • a 2^32-operation attack on Salsa20/6.
• 2017.08: Dey and Sarkarreported
  • a 2^243.67-operation attack on Salsa20/8, and
  • a 2^235.22-operation attack on ChaCha7.
• 2019.06: Dey, Roy, and Sarkarreported
  • a 2^243.23-operation attack on Salsa20/8, and
  • a 2^234.78-operation attack on ChaCha7.
• 2020.02: Dey and Sarkaranalyzed correlations appearing in existing attacks.
• 2020.03: Coutinho and Souza Netoreported
  • a 2^102-operation (2^56 data) attack on ChaCha6,
  • a 2^75-operation (2^75 data) attack on ChaCha6, and
  • a 2^231.9-operation (2^50 data) attack on ChaCha7.
• 2020.06: Beierle, Leander, and Todoreported
  • a 2^77.4-operation (2^58 data) attack on ChaCha6, and
  • a 2^230.86-operation (2^48.83 data) attack on ChaCha7.
• 2021.03: Coutinho and Souza Netoreported
  • a 2^51-operation (2^51 data) attack on ChaCha6,
  • a 2^228.51-operation (2^80.51 data) attack on ChaCha7, and
  • a 2^218-operation (2^218 data) attack on ChaCha7.
• 2021.08: Dey, Dey, Sarkar, and Meierre-analyzed the 2021.03 attack and concluded that it is
  • a 2^232.83-operation (2^84.78 data) attack on ChaCha7.
• 2021.10: Dey and Sarkaranalyzed distinguishing probabilities appearing in existing attacks.
• 2021.11: Miyashita, Ito, and Miyajireported
  • a 2^231.63-operation (2^49.58 data) attack on ChaCha7,
  • a 2^255.62-operation (2^37.49 data) attack on 7.25 rounds, and
  • a 2^244.22-operation (2^69.14 data) attack on 7.25 rounds.
• 2022.05: Dey, Garai, Sarkar, and Sharmareported
  • a 2^81.58-operation (2^43.59 data) attack on ChaCha6 with a 128-bit key,
  • a 2^123.04-operation (2^66.94 data) attack on 6.5 rounds with a 128-bit key, and
  • a 2^221.95-operation (2^90.20 data) attack on ChaCha7.
• 2022.06: Niu, Sun, Liu, and Lireported an improved differential-linear distinguisher for 4 rounds of ChaCha.
• 2022.12: Coutinho, Passos, Grados, de Mendonça, Timóteo, and Borgesreported
  • a 2^214-operation differential-linear attack on ChaCha7,
  • a 2^215.62-operation differential-linear attack on Salsa20/8, and
  • a 2^217.62-operation (2^113.14 data) attack on Salsa20/8.
• 2023.02: Dey, Garai, and Maitrareported
  • a 2^99.48-operation attack on ChaCha6,
    and said that previous attacks on 6 rounds from 2008, 2012, 2016, 2016, 2016, 2020, 2020 used 2^147, 2^139, 2^159, 2^161, 2^166, 2^210, 2^212 operations (to search for probabilistic neutral bits) rather than the reported 2^139, 2^136, 2^131.40, 2^129.53, 2^127.5, 2^102.2, 2^104.68 operations.
• 2023.04: Dey, Garai, Sarkar, and Sharmareoprted
  • a 2^121.40-operation attack on 6.5 rounds of ChaCha,
  • a 2^218.95-operation attack on ChaCha7, and
  • a 2^244.85-operation attack on 7.5 rounds.
• 2023.06: Bellini, Gerault, Grados, Makarim, and Peyrinreported
  • a 2^206.8-operation (2^110.81 data) differential-linear attack on ChaCha7.
• 2023.07: Wang, Liu, Hou, and Linreported
  • a 2^75.7-operation attack (2^73.7 data) on ChaCha6,
  • a 2^216.9-operation attack (2^68.9 data) on ChaCha7,
  • a 2^210.3-operation attack (2^103.3 data) on ChaCha7,
  • a 2^244.9-operation attack (2^104.9 data) on parts of 7.5 rounds, and
  • a 2^242.9-operation attack (2^125.8 data) on parts of 7.5 rounds.
• 2024.03: Sharma and Deyestimated key-recovery probabilities for various earlier attacks.
• 2024.05: Deyreported
  • a 2^71.0-operation attack (2^41.6 data) on ChaCha6,
  • a 2^192.89-operation attack (2^93.79 data) on ChaCha7,
  • a 2^228.24-operation attack (2^100.90 data) on 7.25 rounds, and
  • a 2^255.24-operation attack (2^32.64 data) on 7.5 rounds.
• 2024.06: Xu, Xu, Tan, and Qireported
  • a 2^189.7-operation attack (2^102.63 data) on ChaCha7, and
  • a 2^223.9-operation attack (2^100.8 data) on parts of 7.5 rounds.
• 2024.08: Dey, Leander, and Sharmareported
  • a 2^102.82-operation attack (2^28.77 data) on Salsa20/7 with a 128-bit key,
  • a 2^124.22-operation attack (2^23.06 data) on 7.5 rounds with a 128-bit key, and
  • a 2^240.62-operation attack (2^27.56 data) on Salsa20/8.
• 2025.02: Wang, Ding, Li, Wan, and Husaid that some previous attacks on ChaCha7 are slower than had been reported.
• 2025.02: Dey, Maitra, Sarkar, and Sharmareported
  • a 2^98.25-operation attack (2^86.67 data) on Salsa20/7 with a 128-bit key,
  • a 2^111.47-operation attack (2^94.16 data) on 7.5 rounds with a 128-bit key,
  • a 2^186.01-operation attack (2^99.73 data) on Salsa20/8, and
  • a 2^245.84-operation attack (2^99.47 data) on 8.5 rounds,
    and said that a previous attack on 8 rounds uses more than the reported 2^217 operations.
• 2025.03: Sharma, Dey, Sarkar, and Maitrareported
  • a 2^178.12-operation attack (2^101.9 data) on ChaCha7,
  • a 2^212.43-operation attack (2^100.56 data) on 7.25 rounds, and
  • a 2^253.23-operation attack (2^34.47 data) on 7.5 rounds,
    and said that the 2023.06 attack on 7 rounds needs more data than is available (and thus fails).
• 2025.03: Flórez-Gutiérrez and Todoreported
  • a 2^57.4-operation attack (2^55.7 data) on ChaCha6,
  • a 2^61.4-operation attack (2^51.0 data) on ChaCha6,
  • a 2^148.2-operation attack (2^127.7 data) on ChaCha7,
  • a 2^154.2-operation attack (2^102.9 data) on ChaCha7, and
  • a 2^250.2-operation attack (2^127.1 data) on 7.5 rounds.

Salsa20 prizes

In May 2005 I announced that, at the end of 2005, I would award a $1000 prize for the public Salsa20 cryptanalysis that I considered most interesting. I didn't make any promises regarding what I'd find interesting, but I posted the following guidelines:

• Breaking larger r's wins bonus points. ``Breaking'' is defined by being faster than brute force_for the same cost of cryptanalytic hardware_.
• Extra speed wins bonus points.
• Early publication wins bonus points. Don't hold back!
• New ideas win bonus points. I awarded the prize to Paul Crowley for his paper ``Truncated differential cryptanalysis of five rounds of Salsa20.''

Salsa20 formalities

My submission of Salsa20 to theECRYPT Stream Cipher project (eSTREAM)included the following formalities:

• Salsa20 cover sheet.
• Salsa20 robustness statement.
• Salsa20 intellectual-property statement.
• CD packing list.