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

61–70 of 76 posts

Re: The design of Chacha20

#61

Post by nullc »

Gibbon1 wrote: post #59
cesarb wrote: post #25

Earlier quoted context omitted.

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

'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.

> '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...)

Re: The design of Chacha20

#62

Post by tptacek »

nullc wrote: post #60
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…

> Both are so fast that the speed difference is not particularly important, Without hardware support timing attack resistant AES is not so fast. (and then there is the adventure of many motherboards shipping with hardware AES disabled in the bios...)

Without hardware support AES isn't competitive with Salsa20 anyways.

Re: The design of Chacha20

#63

Post by koverstreet »

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

But ChaCha is simple enough that even implementing it in assembly with AVX or whatever isn't all that hard.

Re: The design of Chacha20

#64

Post by [deleted] »

asdaksdhksajd wrote: post #54

the 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]

[deleted]

Re: The design of Chacha20

#65

Post by loup-vaillant »

stouset wrote: post #57
the8472 wrote: post #29

Earlier quoted context omitted.

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

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?

Re: The design of Chacha20

#67

Post by loup-vaillant »

Gibbon1 wrote: post #59
cesarb wrote: post #25

Earlier quoted context omitted.

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

'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.

> 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 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.

Re: The design of Chacha20

#68

Post by Gibbon1 »

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

Earlier quoted context omitted.

'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.

> 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.

Re: The design of Chacha20

#69

Post by j_s »

JoachimS wrote: post #7

Fwiw, 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

Interesting to see the changelog with a bunch of improvements in September after silence for nearly 2 years.

Re: The design of Chacha20

#70

Post by loup-vaillant »

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.

Correct. It can. I was just explaining why I think it won't anyway.
Post reply on HN