Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The design of Chacha20

loup-vaillant.fr

Post reply on HN
Print view View original

21–30 of 76 posts

Re: The design of Chacha20

#21

Post by sp332 »

riffraff wrote: post #5

> [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?

They did throw >100,000,000 CPU-hours at it https://news.ycombinator.com/item?id=11550922 , but they still got extremely lucky to find such a good address. https://news.ycombinator.com/item?id=8538390 It's not usually that easy.

Re: The design of Chacha20

#22

Post by tptacek »

This 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_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

Re: The design of Chacha20

#23

Post by zeveb » 

    a += b;  d ^= a;  d
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?

Re: The design of Chacha20

#24

Post by tptacek »

TillE wrote: post #15
vog wrote: post #8

How 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?

AES is a block cipher, Salsa/ChaCha are streams. This makes them very useful for, say, file encryption with random access.

There's virtually no difference in utility, since pretty much the only thing we ever do with a block cipher is adapt it to encrypt streams --- this is true conceptually even when we're not literally turning the block cipher into a PRF with something like CTR mode.

Re: The design of Chacha20

#25

Post by cesarb »

zeveb wrote: post #23

a += b; d ^= a; d 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?

In C, unsigned overflow is defined as wrapping, and all these numbers are unsigned. It's signed overflow that's undefined in C.

Re: The design of Chacha20

#26

Post by tptacek »

vog wrote: post #8

How 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?

Chacha/Salsa is:

* Intrinsically simpler than AES

* Easier to implement

* As an ARX design, doesn't need S-boxes, and so doesn't leave a cache footprint

* Has free key setup

AES is:

* A global standard

* Available in hardware on most platforms (extremely important)

* A conventional block cipher for which a bunch of modes (in particular: wide-block and AEAD) are already defined

But unlike Salsa, AES:

* Has relatively complicated key schedule (you have to expand its key input to a series of per-round keys, which imposes a cost when you switch keys)

* Relies on S-boxes for security and so must carefully avoid microarchitectural side channels

* Is much harder to implement

* Is not a native stream cipher, so requires an adapter (usually: GCM mode) to use safely.

AES is usually faster on modern systems because it's implemented directly in silicon. Salsa is usually the fastest pure-software option. Both are so fast that the speed difference is not particularly important, but most systems will prefer AES when hardware support is present.

Salsa is almost certainly the better choice for new designs just because of its simplicity. It's harder to screw up Salsa20 or its derivatives than it is to screw up AES (it is very easy to screw up AES), and its performance is more than satisfactory.

Re: The design of Chacha20

#27

Post by tc »

riffraff wrote: post #5

> [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?

It doesn't really matter. The key thing is that the constant bytes prevent a symmetry from forming in the block. So it matters that the string does aid such symmetry. Making it a text string is just a flourish helpful to us humans. It makes it easier to see the lack of symmetry and trivially answers the question, "why those bytes?"

Re: The design of Chacha20

#28

Post by the8472 »

TillE wrote: post #15
vog wrote: post #8

How 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?

AES is a block cipher, Salsa/ChaCha are streams. This makes them very useful for, say, file encryption with random access.

Under the hood chacha is a block cipher too. It just happens to have counter mode baked in, which turns it into a stream cipher.

Re: The design of Chacha20

#29

Post by the8472 »

tptacek wrote: post #26
vog wrote: post #8

How 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?

Chacha/Salsa is: * Intrinsically simpler than AES * Easier to implement * As an ARX design, doesn't need S-boxes, and so doesn't leave a cache footprint * Has free key setup AES is: * A global standard * Available in hardware on most platforms (extremely important) * A conventional block cipher for which a bunch of modes (in particular: wide-block and AEAD) are already defined But unlike Salsa, AES: * Has relatively…

> * A global standard

ChaCha is standard enough to make it into TLS and IPSec

Re: The design of Chacha20

#30

Post by tptacek »

the8472 wrote: post #29
tptacek wrote: post #26

Earlier quoted context omitted.

Chacha/Salsa is: * Intrinsically simpler than AES * Easier to implement * As an ARX design, doesn't need S-boxes, and so doesn't leave a cache footprint * Has free key setup AES is: * A global standard * Available in hardware on most platforms (extremely important) * A conventional block cipher for which a bunch of modes (in particular: wide-block and AEAD) are already defined But unlike Salsa, AES: * Has relatively…

> * A global standard ChaCha is standard enough to make it into TLS and IPSec

Yes, but that's true of all sorts of things that aren't really global standards. Don't get me wrong: you should use Salsa ciphers. I'm just trying to provide the most honest possible accounting.
Post reply on HN