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

71–76 of 76 posts

Re: The design of Chacha20

#71

Post by wolf550e »

Gibbon1 wrote: post #68
loup-vaillant wrote: post #67

Earlier quoted context omitted.

> And implementing it with a for loop also leaks. Assuming you're talking about this for loop: for (int i = 0; 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 Then yeah, it leaks. > Longer term worry…

Problem is the optimizer is totally free to implement the 'safe' code snippet using an 'unsafe' early return. According to the standard that would be completely legal.

A compiler that did this optimization would immediately introduce a pragma guaranteed to result in constant time memcmp from some blessed source pattern.

Maintainers of crypto libraries inspect the assembly when upgrading their compilers, test with many compilers and document the versions of compilers they support.

Re: The design of Chacha20

#72

Post by stouset »

loup-vaillant wrote: post #65
stouset wrote: post #57

Earlier quoted context omitted.

Even then, they actually used a tweaked version of ChaCha20 that uses a 96-bit nonce (just barely large enough to be suitable for randomly-generated nonces) and a 32-bit counter (limiting its use to 128GiB for a given nonce). Also, an extension XChaCha20 was recently published which performs an extra 20 rounds to initialize the cipher state, allowing for 192-bit nonces with no corresponding reduction in counter size.…

> an extension XChaCha20 was recently published It has? With test vectors and all? I want that, do you have a link?

I could have sworn I saw a paper on this recently. I may have hallucinated it.

Edit: Shit, considering it further, what I was remembering was the recent paper on BLAKE2X, not XChaCha20.

Re: The design of Chacha20

#73

Post by rstuart4133 »

floodyberry- wrote: post #41
wolf550e wrote: post #13

Earlier quoted context omitted.

AES 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…

Basic 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!)

Basic GNU C implementations don't get auto-vectorised full stop. But with a little bit of effort Chacha20 can be made to vectorise. The implementation in here is vectorised by GNU C:

  https://sourceforge.net/p/pbkdf2/code/ci/default/tree/pbkdf2.c
If "ultra-efficient code" means what could be produced by a programmer highly skilled in some amd64 implementation (intel core2, amd bulldozer, ...) for that implementation then yes I doubt GNU C produces it. But the odds are GNU C's output runs faster than that's guru's code on other amd64 implementations.

Re: The design of Chacha20

#74

Post by floodyberry- »

rstuart4133 wrote: post #73
floodyberry- wrote: post #41

Earlier quoted context omitted.

Basic 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!)

Basic GNU C implementations don't get auto-vectorised full stop. But with a little bit of effort Chacha20 can be made to vectorise. The implementation in here is vectorised by GNU C: https://sourceforge.net/p/pbkdf2/code/ci/default/tree/pbkdf2.c If "ultra-efficient code" means what could be produced by a programmer highly skilled in some amd64 implementation (intel core2, amd bulldozer, ...) for that implementation t…

That Salsa implementation is not being vectorized? Salsa also requires some values to be shuffled around to actually work in SSE registers, djb made a bit of a boo-boo when designing it. Chacha fixes that, so its SIMD implementations are a bit more straightforward.

Re: The design of Chacha20

#75

Post by [deleted] »

tptacek wrote: post #22

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…

[deleted]

Re: The design of Chacha20

#76

Post by [deleted] »

tptacek wrote: post #22

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…

[deleted]
Post reply on HN