# salsa20 is invertible, useless in CTR mode?

I'm reading the salsa20 spec (sorry for the newbie question, i'm really a newbie here). Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

1. If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?
2. As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?
3. Isn't it easier to design a robust hash than a robust cipher?
• How exactly do you use salsa20 in block cipher CTR mode? Salsa20 is not a block cipher, it is a stream cipher. – mikeazo Sep 16 '14 at 13:20
• @mikeazo, Salsa20 runs the "Salsa20 hash function" in "CTR mode". The terminology there is a bit confusing, especially as "hash function" doesn't mean cryptographic hash, so it's no wonder if the question isn't exactly correctly stated. – otus Sep 16 '14 at 13:29
• yup, sorry for the confusion. One said : What is well understood can be clearly expressed :) It's not well understood yet. Both answer were perfect, I picked one. Thank you very much – yota Sep 16 '14 at 13:49
• @mikeazo More of an aside: While it’s indeed a stream cipher, there are some pages that add to the confusion by hinting at the fact that “Salsa20/r resembles the operation of a block cipher in counter mode.” (source: ecrypt.eu.org, emphasis mine). – e-sushi Sep 16 '14 at 14:32

## 2 Answers

Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

The Salsa20 quarterround, and thus rowround, columnround and doubleround are invertible. However, the whole Salsa20 core is not because the initial state is added to the state after iterating the rounds (cf. page 6 in the spec).

1. If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?

If the whole cipher core was invertible, then a known plaintext attack would reveal the key. So not being invertible is a requirement, somewhere along the line.

1. As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?

This is correct. See, for example this question.

1. Isn't it easier to design a robust hash than a robust cipher?

Maybe, but block ciphers are usually much faster than a hash function in CTR mode. Hash functions are optimized to consume data, not output it. Stream ciphers, OTOH, are occasionally even faster, like you can see if you compare Salsa20 and AES in software implementations.

## How does Salsa20 work?

1. The basic building block of salsa20 is a fixed 512 bit permutation. This is similar to a block cipher with a fixed and publicly know key (or a zero bit key if you prefer). Since it has no key input, you can't use it with block cipher modes of operation.

2. The next step in Salsa20 is a feed-forward by adding the input into the output, turning it into an unkeyed hash function/one-way-function.

If $P(x)$ is a permutation and thus reversible, $P(x)\oplus x$ is one way.

This is the standard way for turning a reversible function into an irreversible one, and is often used to build compression functions.

3. The input of this 512 bit function gets divided into several parts: A 256 bit key, an 8 byte stream identifier (IV) an 8 byte counter and 16 bytes of fixed padding. Note that the padding is necessary to remove certain symmetries from the raw hash function.

This turns the unkeyed hash into a keyed one, formally a PRF (pseudo random function)

4. Finally to produce a long output Salsa20 calls the core function with a different counter for each 512 bit block. This is very similar to the CTR mode used with block ciphers.

## To address your questions:

2) As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?

A generalized counter mode can be used with any PRF, which is the formalization of a keyed hash.

Building a PRF from an unkeyed hash is easy in practice and secure for most hashes we use, such as SHA-2 or SHA-3. Theoretically it's tricky and probably needs the random oracle assumption.

1) If I use Salsa20 in block cipher CTR mode, this property does not seems mandatory to me, am I right?

If you interpret Salsa20 as a 512 bit block cipher it's clearly not secure, since it has a zero bit key and undesirable symmetries on top of that. So you can't use it in CTR mode as it's defined for block ciphers.

On the other hand, the Salsa20 function as described in Step 3 above is believed to be a PRF, and Step 4 is a kind of counter mode, so in a way you're always using Salsa20 in CTR mode.

3) Isn't it easier to design a robust hash than a robust cipher?

Pretty much all hashes we use are built from a permutation, keyed (aka block cipher) or unkeyed. The key idea is that the irreversible operation is where collisions happen, so we want only a single one of those and it should be as far as possible from what the attacker controls.

So I don't think it's easier to build a hash than a permutation or block cipher. In some ways it's harder, since we often request collision resistance from hashes, whereas ciphers are generally used with random keys the attacker has no control over.

• I'm not sure to understand how block cipher CTR is (or not) alike salsa20 stream cipher. Looking at the spec, and at en.wikipedia.org/wiki/… I can not spot the differences, neither why you can't use "salsa20 in CTR mode as it's defined for block ciphers". Isn't the salsa20 initial state precisely made of the key, and a CTR index (+ nonce) ? – yota Sep 18 '14 at 11:45