Talk:Salsa20

From Wikipedia, the free encyclopedia

Contents 1 An-Ping 2 prf description 3 An-Ping redux 4 Differential Cryptanalysis of Sala20/8

[edit] An-Ping

There's a conflict between accuracy and NPOV in how we present An-Ping's "analysis", and I'd be interested in ideas on how to resolve it. An-Ping's "analysis" is indeed garbage, and anyone sufficiently expert who reads his paper will be able to verify that (in so far as they're able to get through his impenetrable language). But because we have to take an NPOV stance, we'll give those who come to Wikipedia the impression that there's some sort of big unresolved question mark over Salsa20, when all there is is one nutter talking nonsense. There must be a fair way we can present the verifiable facts so as not to leave people with this misapprehension. — ciphergoth 10:06, 8 October 2005 (UTC)

I think the way around this sort of thing is to emphasise that noone has accepted his claims, and that experts have expressed criticism or skepticism about the claims. I tweaked a couple of words, and I think it gives the right sort of impression now, but still keeps an NPOV. — Matt Crypto 11:13, 8 October 2005 (UTC)

[edit] prf description

I don't think the description of salsa20 as a prf is quite correct. Its indistinguishability depends on some assumptions about the input distribution, e.g. that the key is random and the hash function input comes from the expansion function. Maybe the individual functions salsa20_{k,v}(n) could be described as prf's on n, i.e. k is a parameter selecting from a family of functions, not a function input. Bernstein has mentioned that you can't use salsa20 as a general purpose 512 bit hash function. Phr

A PRF is not a function; it's a keyed family of functions. For Salsa20 that family is not exactly what you specify; it's Salsa20_k(v, i). Otherwise it would not be claiming any security against an attacker who knows the nonce, which wouldn't be much use. As it is, it claims security against chosen-nonce attacks, a very important class of attacks that break lots of eSTREAM candidates. To me the sentence

a pseudorandom function based on 32-bit addition, bitwise addition (XOR) and rotation operations, which maps a 256-bit key, a 64-bit nonce, and a 64-bit stream position to a 512-bit output

implies that the PRF is Salsa20_k(v, i) but perhaps it could be made clearer? — ciphergoth 09:00, 19 February 2006 (UTC)

Yes it could be clearer. I thought a PRF was a single function (like an HMAC instance with a fixed but unknown key) that can't be distinguished from a random function, so HMAC is a family of PRF's, AES is a family of PRP's, etc. Maybe I've got the definition mixed up. I've been wanting to write articles describing PRF and PRP, so I better check that. Phr 06:26, 20 February 2006 (UTC)

[edit] An-Ping redux

I've removed An-Ping's attacks from here. There has to come a point where someone's commentary on a thing is not notable enough to go in the article on that thing. I will restore them if even one cryptographer who has been published in an IACR journal is prepared to publically say that they think there is some worthwhile substance to those papers. — ciphergoth 05:55, 7 September 2006 (UTC)

[edit] Differential Cryptanalysis of Sala20/8

http://sasc.crypto.rub.de/files/sasc2007_039.pdf says:

In this example, the computational complexity becomes approximately 2²⁵⁵

(= 2²⁴⁵× 2¹⁰ × 2 × 4/8) times of Salsa20/8 encryption and it is lower than 2²⁵⁶

of exhaustive key search.

5 Conclusion

This paper presented a cryptanalysis of the Salsa20 stream cipher proposed

in 2005. We discovered a significant differential probability bias in the Salsa20

round 4 internal state, yielded by assigning single bit differences to the initial

vector which may be freely chosen by an attacker.

Further more, we have used this bias to attack Salsa20/r (5 ≤ r ≤ 8). Using

our method, Salsa20/7 with a 128-bit secret key and Salsa20/8 with a 256-bit

secret key were broken using less computational complexity than required for

an exhaustive key search. The amount of data needed for both cryptanalyses

is theoretically 2^11.37 keystream pairs. Our method of attack uses a new technique

of approximating polynomials of addition, and succeeds in the reducing

the computational complexity compared to previous methods.

Finally, Bernstein proposed Salsa20/8 and Salsa20/12 as models paying consideration

to implementation, but faced with our attack the security of Salsa20/8

is insufficient, and even considering implementation, a model of at least 12 rounds

should be used. However, the attack in this paper does not directly threaten the

security of the full-round Salsa20/20 specification, although caution is still required

regarding the issue of whether there is a sufficient margin of safety. —Preceding unsigned comment added by 71.41.210.146 (talk) 15:00, 13 December 2007 (UTC)