Does Salsa20 protect integrity?

Question

I was reading about the differences between block ciphers and stream ciphers. One thing that hit me was that stream ciphers like RC4 tend to be susceptible to bit-flipping attacks, in which flipping a bit in the ciphertext can predictably change the plaintext, allowing an attacker who knows the plaintext to change it in any way he/she wants, while in secure block ciphers, an attacker cannot flip a bit in the ciphertext and predictably change the block of plaintext.

How does Salsa20, being a widely used and secure stream cipher, protect against these attacks, if it does at all? If it doesn't, how does Salsa20-Poly1305 protect integrity of known plaintext?

Answer 1

Salsa20 alone does not protect integrity.

Poly1305 protects integrity, as it is a Message Authentication Code (MAC). A MAC takes a secret key and a message, and outputs an authentication tag. Any change to the message will cause the resulting tag to not match. Only someone with the key can generate the tag, which means that an attacker shouldn't be able to flip bits undetected.

At a very high level, Poly1305 takes a message and a two-part key and turns it into a very big polynomial (modulo a large prime).

$MAC=(m_{1}r^{n}+m_{2}r^{n-1}\ldots+m_{n}r^{1}+k)\mod p$, where $m_1$, $m_2$, etc, are blocks of the message and r & k are the key.

In the case of Poly1305 the prime p is $2^{130}-5$.

To encode a message $M$ into blocks you take 16 bytes from the message, append a 1 byte to the end, then treat the 17 bytes as a little-endian number (this process ensures that trailing zeroes are detected).

There are also some restrictions on how $r$ is chosen.

The end result is very difficult to compute by an attacker not knowing r and k, even if they know the plaintext of the message.

Loup Valliant has a good explanation with a bit more detail on how Poly1305 actually works.1 And of course DJB's paper provides even more detail, though it's harder to understand.2