10 ms·
The design of Chacha20
- vog 10y agoThe author seems to favor XChaCha20 over ChaCha20, even though XChaCha20 is not part of any formal standard or any widely know paper. [1] It would be interesting to know what DJB (the author of ChaCha20) thinks about XChaCha20 and related variants. [1] http://crypto.stackexchange.com/a/34605 http://crypto.stackexchange.com/a/34605
- marcosdumay 10y agoWell, NaCl (DJB's encryption library) uses XChaCha20, doesn't it? Edit: Nope, it's XSalsa20.
- panic 10y agoNaCl provides Salsa20 and XSalsa20 (https://nacl.cr.yp.to/stream.html https://nacl.cr.yp.to/stream.html). libsodium adds ChaCha20 (https://download.libsodium.org/doc/advanced/chacha20.html https://download.libsodium.org/doc/advanced/chacha20.html) but not XChaCha20.
- CiPHPerCoder 10y agoThat's coming soon: https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_aead/xchacha20poly1305/sodium/aead_xchacha20poly1305.c https://github.com/jedisct1/libsodium/blob/master/src/libsod...
- asdaksdhksajd 10y agough, an extra ietf variant that pads the remaining 64-bit from the nonce to fit 96 bit thats incompatible with all the implementations out there... :-( why can't we get our shit together...
- JoachimS 10y agoNaCl supports several secret key encryption algorithms: http://nacl.cr.yp.to/stream.html http://nacl.cr.yp.to/stream.html aes-128 in counter mode, Salsa20 with 8, 12 and 20 rounds and XSalsa with 20 rounds. Som other implementations of NaCl/Sodium have restricted the different algs. TweekNaCl only supports XSalsa20 and Salsa20.
- loup-vaillant 10y agoI took some liberty here, but this is a straightforward derivation of XSalsa20. I trust XChacha20 just as strongly as I trust Chacha20. The same cannot be said about my implementation however. I haven't found test vectors for XChacha20, so for now I have to rely on code review (only my own eyes so far) to ascertain its correctness. Not ideal. Also I don't favour XChacha20 over Chacha20, because it is slightly slower to initialise. If a 64-bit nonce is enough, I'll use Chacha20. Maybe I should make this clear in my article.
- riffraff 10y ago> [re magic "expand 32-byte k" string] And it's readable ASCII text, so you can be pretty sure there's no back door in there. I am not sure this matters? I mean, facebook managed to get a reasonably nice .onion routing id (facebookcorewwwi.onion) by bruteforcing stuff right? I can imagine bruteforcing the "backdoor key space" to find something that looks good, am I insane?
- cwmma 10y agoIf backdoored constants are easy enough to find that you are able to find them AND they are appropriate English phrases then the cipher itself is likely broken doubly so as the origional version of chacha had 2 key sizes 16-byte and 32-byte and each used the applicable constant, so in this case you would have had to have found 2 matching back doored constants. That being said you aren't crazy this is what the nsa was accused of doing with elliptical curves though they had started with inexplicable random seeds.
- vog 10y agoI was wondering about this, too. To put even more paranoia at the table: Readable ASCII means that every byte is in a certain range. For example, bit 7 is 0 for every byte. Maybe this allone enables a backdoor. That is, the mere fact that this is readable ASCII could enable a backdoor. Who knows?
- loup-vaillant 10y agoThis theory probably contradicts the usage of block cipher in counter mode. With them, the input block is usually full of zeros. This constraint has strengthened ciphers in the past. DJB wrote somewhere that some block cipher were broken in CBC mode (all the bock can be controlled by the attacker), while CTR mode was still safe (many bits forced to zero).
- tptacek 10y agoNo, it does not. You're taking this notion of constrained values out of context. ASCII strings in crypto constructions are very common; for instance, they provide domain isolation in hash constructions (where you have a single hash function applied to inputs of different sensitivity, and want to mint multiple logically unrelated hash functions from the one you have). They're also common in versions. The ASCII we're looking at here is conceptually a hash input. It's not a part of the design of the hash core itself.
- JoachimS 10y agoFwiw, here is a HW-implementation of ChaCha. It is very fast due to the big block and four parallel quarterrounds. https://github.com/secworks/chacha https://github.com/secworks/chacha
- j_s 10y agoInteresting to see the changelog with a bunch of improvements in September after silence for nearly 2 years.
- vog 10y agoHow does ChaCha20 compare to the established AES standard? Is it stronger? weaker? faster? slower? easier to implement correctly? harder to implement correctly? better for some other reason? worse for some other reason?
- cwmma 10y agoIt's main claimed benefits are that it is resistant to side channel timing attacks, simpler (easier to implement correctly) and faster. all things being equal, in practice AES is often implemented in hardware which gives it an advantage.
- wolf550e 10y agoAES is hard to implement on a general purpose computer in a way that is both fast and doesn't leak through cache timing attacks. The safe way to use AES is by using a hardware implementation, like modern x86 and some ARM CPUs. The best software implementations use bitslicing and SSE, but are still slow. The best I saw is an Emilia Kasper and Peter Schwabe paper[1] from 2009 on bitsliced AES-GCM has 21.99 cycles/byte performance for constant-time implementation authenticated AES-GCM. For comparison, Intel shows[2] 0.77 cycles/byte for same with a hardware implementation, albeit on a newer CPU. Chacha is fast on modern general purpose CPUs without the need for a hardware implementation of chacha. One reason it's fast is that it was designed so that a normal compiler can generate machine code from regular-looking C code in such a way that it uses vector (wide) registers and uses independent operations to use as many operations in the CPU in parallel in the same clock cycle, without requiring an assembly wizard to do that. Intel can afford assembly wizards (i.e. Shay Gueron), other people can't. Modern TLS stacks prefer AES when running on a CPU that has AES hardware and fallback to chacha otherwise. They of course fallback to either a slow or an insecure implementation of AES if the other side doesn't support chacha. 1 - https://eprint.iacr.org/2009/129 https://eprint.iacr.org/2009/129 2 - https://software.intel.com/en-us/articles/improving-openssl-performance#_Toc416943489 https://software.intel.com/en-us/articles/improving-openssl-...
- floodyberry- 10y agoBasic Chacha C implementations do not get auto-vectorized down to ultra-efficient code. The most efficient implementations are intrinsic/assembler that process 4 (SSE2/AVX/NEON) or 8 (AVX2) Chacha20 blocks at once. This is due to layout of variables and operations being designed for efficient SIMD use and the blocks being independent of each other. (Shay's Chacha20 implementation is also not the fastest!)
- overcast 10y agoI thought this was for Chacha the site, and I'm equally bewildered that service is still running after twelve years!
- tptacek 10y agoThis is solid but might miss the forest for the trees. If you want to understand Chacha/Salsa, the best way to start is that it's an ARX-based hash function, keyed, running in counter mode. ARX stands for addition, rotation, and XOR, which are the three operations ARX designs are composed of. Addition is nonlinear in the context of ARX, which eliminates the need for S-boxes (or complex alternatives to S-boxes) and makes it easier to build constant time crypto. You can make any function out of just A, R, and X (technically, any function out of A and R, but less efficiently). A good place to start understanding why you want rotation and nonlinearity is the Wikipedia page for SP Networks: https://en.wikipedia.org/wiki/Substitution-permutation_network https://en.wikipedia.org/wiki/Substitution-permutation_netwo... Another good bit of background is the old idea of iterated ciphers (round functions run repeatedly, rather than one giant cipher function), and the slightly more modern idea that it's better to have a very simple round function you repeat a lot than a complicated round function you run fewer times. When you get this you can start grokking design decisions in terms of how many rounds they shave off your design to achieve the same security (which also might get you back to why you have X in addition to A and R). The Salsa20 core is a very simple hash function designed to be fast and flexible for multiple constructions. Bernstein designed the stream cipher we all know based on it, and also Rumba20, which is a more tradition collision-resistant cryptographic hash. Designing ciphers out of hash functions has been a research interest of Bernstein's since the 1990s, when hash functions were approved for export but ciphers not. A keyed hash (also: PRF) is a hash function that takes a secret key input. In a general-purpose hash like SHA3, you provide the key along with the rest of the input by simple concatenation. Fun true fact: in SHA-2 and hashes before that, it was unsafe to do this, which is why we have the HMAC construction, which SHA-3 and Blake2 obsolete. At any rate, Salsa20 takes the key as a special parameter and encodes it into a block. Counter mode is conventionally a method for turning a block cipher into a stream cipher. In 2017 its widely seen as the most important and primary way you should use block ciphers (if you're not using an AEAD, most of which are built on counter mode in some way). Counter mode is super simple: you encrypt a counter of some sort and XOR the resulting block with your plaintext. To decrypt, you do the same thing. A really good place to start learning about Salsa20 (and thus Chacha20) is Bernstein's design paper, which is extremely readable and easy to skim: https://cr.yp.to/snuffle/design.pdf https://cr.yp.to/snuffle/design.pdf
- zeveb 10y agoa += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7; I'm curious: could a C compiler look at the quarter-round function above and determine that a+b (or the other terms) might overflow a 32-bit integer, and thus invoke undefined behaviour to eliminate the loop entirely?
- cesarb 10y agoIn C, unsigned overflow is defined as wrapping, and all these numbers are unsigned. It's signed overflow that's undefined in C.
- Gibbon1 10y ago'Safe for for now' Notable I think the NaCl crypto library implements a compare as follows uint32_t diff_bits = 0; diff_bits |= x[0] ^ y[0]; ... diff_bits |= x[31] ^ y[31]; return (1 & ((diff_bits - 1) >> 8)) - 1; This because memcmp() leaks timing information. And implementing it with a for loop also leaks. Longer term worry is the optimizer will figure the above out as well.
- nullc 10y ago> 'Safe for for now' No, unconditionally safe. The C standard exactly defines unsigned overflow while specifically leaving signed overflow undefined. (Pedantically timing is always a crapshoot in C, a compiler only need produce the same results as the abstract machine. It could freely take all your secret data and modulate it into the timing and be conforming. -- but considering that intel/amd won't make timing promises about the instructions themselves...)
- loup-vaillant 10y ago> And implementing it with a for loop also leaks. Assuming you're talking about this for loop: for (int i = 0; i < 32; i++) // safe branch diff_bits |= x[i] ^ y[i]; then no, it doesn't leak, because the result of the resulting conditional branch doesn't depend on a secret. The only reason NaCl unrolls that loop is because neeed moar speeed. If you were talking about the early return straightforward for loop: for (int i = 0; i < 32; i++) // safe branch if (x[i] != y[i]) // timing leak... return -1; // ...magnified Then yeah, it leaks. > Longer term worry is the optimizer will figure the above out as well. It may, but even compiler implementers realise the value of constant time code. Replacing this code with an early return doesn't just require very sophisticated optimisations, it never happens outside of a crypto library. There is little incentive for compiler writers to do this.
- jean- 10y agoIf you enjoyed the style of this article, I would also recommend you have a look at the brilliant explanation of Earley parsing by the same author: http://loup-vaillant.fr/tutorials/earley-parsing/ http://loup-vaillant.fr/tutorials/earley-parsing/
- frankenbagel 10y agoThere have also been some good AES vs ChaCha performance tests: 1) Speedify's AES vs ChaCha in VPN: http://speedify.com/blog/a-new-kind-of-vpn/ http://speedify.com/blog/a-new-kind-of-vpn/ 2) Cloudflare's AES vs ChaCha in browser: https://blog.cloudflare.com/do-the-chacha-better-mobile-performance-with-cryptography/ https://blog.cloudflare.com/do-the-chacha-better-mobile-perf...
- ayetwyer 10y agoIf you are looking for a professional Hacker that specialized in school grade change… contact me ASAP, I do several School grades hack everyday. My jobs are secured and without trace. I have worked for students in Asia, America, Europe,Africa and Australia. I ALSO do Facebook Hacking, Whatsapp Hacking, Instagram, Mobile Hacking, Increase credit score, removal of name from criminal record, removal of links from website. Recover Your email passwords, Hack into Bank/Company web site, etc
- asdaksdhksajd 10y agothe nonce and counter state words seem to be swapped in the 3rd figure of the "A much bigger nonce: XChacha20" section: block'[ 0]: "expa" block'[ 8]: kcolb[12] block'[ 1]: "nd 3" block'[ 9]: kcolb[13] block'[ 2]: "2-by" block'[10]: kcolb[14] block'[ 3]: "te k" block'[11]: kcolb[15] block'[ 4]: kcolb[0] block'[12]: nonce[4] <--- block'[ 5]: kcolb[1] block'[13]: nonce[5] <--- block'[ 6]: kcolb[2] block'[14]: counter[0] <--- block'[ 7]: kcolb[3] block'[15]: counter[1] <---
- loup-vaillant 10y agoCorrected, thanks.
- asdaksdhksajd 10y agothe page didnt change for me yet, caches?
- loup-vaillant 10y agoCrap, I thought you were referring to another figure, which had the same error. Correcting now.
- deleted 10y ago[deleted]