Related-key attacks against Salsa20 and ChaCha

Question

From the Salsa20 security document, DJB states that he doesn't care about related key attacks:

The standard solutions to all the standard cryptographic problems—encryption, authentication, etc.—are protocols that do not allow related-key attacks on the underlying primitives. I see no evidence that we can save time by violating this condition. The reader might guess that Salsa20 is highly resistant to related-key attacks; but I simply don't care.

Emphasis mine. The only related-key attack I know of is against Salsa20/7 and requires 2²¹⁷ operations using 2²⁴ pairs of keystream blocks from two sets of keystream. I can't find any attacks on ChaCha. The linked paper cites a discussion from the eSTREAM forums which argues the attacks are irrelevant.

What is the state of Salsa20 and ChaCha security against related key attacks? What can be said about their design that would make them resistant to such attacks? How does ChaCha compare to Salsa20?

Answer 1

Perhaps the best evidence for the related-key security of Salsa20 is in the Rumba compression function proposed by the author: $$ \mathrm{Rumba}(m_1, m_2, m_3, m_4) = f_1(m_1) \oplus f_2(m_2) \oplus f_3(m_3) \oplus f_4(m_4)\,, $$ where $f_i$ is Salsa20 with a different initial constant for each variant, and each $m_i$ is 384-bit wide. Clearly, for the author to believe this construction would be secure it would require believing the permutation is secure against Salsa20 attackers who also control the key.

This belief was tested in the "New Features of Latin Dances" paper, which found collisions for 3 rounds in time $2^{79}$—much faster than generic methods. But 3 is a long way from 20, and so there does not seem to be much to fear.

Later, in an early version of a paper introducing SMT solvers to the differential cryptanalysis of ARX, Mouha and Preneel argued that there are no strong differential characteristics for 15 rounds of Salsa20, even in the related-key model. However, there are some subtle issues here, and this should be considered evidence but not proof that Salsa20 is immune to differential cryptanalysis.