Salsa20 hashing
in [Cryptography]
|
Prev: How long to trust 3DES
Next: M.peg biss key finder
From: xmath on 26 Sep 2006 15:15 I've been playing a bit with the thought of building a hash out of Salsa20, for applications that already use it and don't want another primitive... Does anyone see an obvious problem with this particular mode of turning Salsa20 (or any other one-way function where the input size equals the output size) into a collision-resistant hash function on arbitrary-size messages: Pad and split the message into 64-byte blocks m_1 .. m_k, then: h_0 = IV h_1 = Salsa20(h_0 + Salsa20(m_1)) h_2 = Salsa20(h_1 + Salsa20(m_2)) h_3 = Salsa20(h_2 + Salsa20(m_3)) .... h_k = Salsa20(h_{k-1} + Salsa20(m_k)) With h_k as the hash output. (By using the same per-word addition as Salsa20 uses to add in the original input you can save a temporary 16-word array in the implementation.) I feel a little uncomfortable about allowing the attacker to fully control the input to Salsa20, however if the IV is chosen properly then none of the ways (known to me) in which Salsa20 deviates from a perfect random function are of any utility. In comparison, the "obvious" chaining mode (32 message bytes, 32 chaining bytes) only allows the attacker to have precise control over half the input, but she also only needs to find a collision in half the output. Because of that, simple chaining obviously allows a collision to be found in about 2^128 operations, while for the mode above I see no obvious attack faster than about 2^256 operations. Performance of the two modes is about the same. On my G4 (PPC 7447A), around 8 cycles/byte. Any thoughts? Also, what about the reduced-round versions, Salsa20/8 and /12 ? - xmath
From: D. J. Bernstein on 26 Sep 2006 17:15 On 2006-09-26, xmath <xmath.news(a)gmail.com> wrote: > Does anyone see an obvious problem with this particular mode Yes. The diagonal constants in Salsa20 are important. There are many other sensible choices of constants, but the constants should never be replaced by attacker-controlled variables. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago
From: xmath on 26 Sep 2006 20:24 D. J. Bernstein wrote: > Yes. The diagonal constants in Salsa20 are important. There are many > other sensible choices of constants, but the constants should never be > replaced by attacker-controlled variables. I know about the diagonal rotate issue, but I don't see how it can help the attacker. If he rotates a message block m_i then Salsa20(m_i) rotates along, but for this to propagate in a useful way to h_i, she also needs h_{i-1} to be rotated in the same way, which not only requires m_{i-1} to be rotated as well, but also h_{i-2} etc until she hits h_0 (the IV) which quite stubbornly refuses to rotate :-) Also, even if the attacker could do this successfully, while it would be an ugly property I don't see it violating collision-resistance. Or can more evil be done if the diagonal is attacker-controlled? - xmath
From: Scott Contini on 27 Sep 2006 02:26 xmath wrote: > I've been playing a bit with the thought of building a hash out of > Salsa20, for applications that already use it and don't want another > primitive... > > Does anyone see an obvious problem with this particular mode of turning > Salsa20 (or any other one-way function where the input size equals the > output size) into a collision-resistant hash function on arbitrary-size > messages: > > Pad and split the message into 64-byte blocks m_1 .. m_k, then: > > h_0 = IV > h_1 = Salsa20(h_0 + Salsa20(m_1)) > h_2 = Salsa20(h_1 + Salsa20(m_2)) > h_3 = Salsa20(h_2 + Salsa20(m_3)) > ... > h_k = Salsa20(h_{k-1} + Salsa20(m_k)) > > With h_k as the hash output. (By using the same per-word addition as > Salsa20 uses to add in the original input you can save a temporary > 16-word array in the implementation.) I think you can get a collision as follows (please check, I sometimes make stupid mistakes). Let m1 and m1' be anything, with m1 != m1'. Then take m2 = h_0 + f(m1') and m2' = h_0 + f(m1) , where you use f = Salsa20. If this is right, then your construction is bad, the attack does not depend upon the underlying "hash function". Scott
From: xmath on 27 Sep 2006 07:54
Scott Contini wrote: > I think you can get a collision as follows Whoops. :-) I suppose this could be prevented by taking h_i = F(h_{i-1} + H(m_i)) or h_i = F(h_{i-1}) + H(m_i) where F and H are independent one-way functions? actually I think F doesn't even need to be one-way or anything, just stir things enough to avoid a generalized birthday attack. Hmm... I need to think a bit more about this clearly... - xmath |