What is so special about chacha20 stream cipher along with poly1305 for message authentication codes?

Question

I am currently trying to dissect the low level cryptography protocols of the lightning network and I realize that in many places chacha20 is being used. I tried reading about it in the Wikipedia Article there it says:

This gives Salsa20 and ChaCha the unusual advantage that the user can efficiently seek to any position in the key stream in constant time. Salsa20 offers speeds of around 4–14 cycles per byte in software on modern x86 processors, and reasonable hardware performance. It is not patented, and Bernstein has written several public domain implementations optimized for common architectures.

While I see the later parts about not being patented and optimzed for many architectures is nice I don't get the first sentence of the Quote. What does it mean that one can efficiently seek to any position in the key stream in constant time?

Answer 1

What is so special about chacha20 stream cipher along with poly1305 for message authentication codes?

There is nothing special about the combination. It's just a combination of two constructions (ChaCha20 for the stream cipher, Poly1305 for MAC) that are designed with similar goals in mind:

• Easy to write a correct implementation in software
• Optimized for performance of software implementations running on general purpose hardware. This is in contrast to many cryptographic primitives which are optimized for hardware implementation, but are suboptimal in software. This is mainly due to the use of integer addition operations in ChaCha20.
• 128-bit security level.

Furthermore the key derivation is informally standardized, allowing using a single key for both encryption and authentication. Having real-world constructions (for example OpenSSH) use this constructions gives confidence about security.

What does it mean that one can efficiently seek to any position in the key stream in constant time?

Assume you're given n GiB of incoming encrypted data, but for some reason you're only interested in the last 1 MiB. With some ciphers, you'd need to do O(n) work to "skip" the first n GiB. ChaCha20, like most stream ciphers, permits decrypting any one MiB with same amount of work regardless of its position - essentially deriving the cipher output for arbitrary positions (aligned to a 64 byte boundary at least) with as much work as decoding sequentially.