Salsa20 hashing
in [Cryptography]
|
Prev: How long to trust 3DES
Next: M.peg biss key finder
From: xmath on 27 Sep 2006 09:08 How about splitting the padded message into 48-byte blocks, combining them with fixed diagonal constants into salsa20 inputs m_1, m_2, .. m_k and doing: h_0 = IV h_1 = F(h_0) + Salsa20(m_1) h_2 = F(h_1) + Salsa20(m_2) ... h_k = F(h_{k-1}) + Salsa20(m_k) Where F is Salsa20/8 without final addition (a "random" bijection). This appears to avoid all attacks so far, and keeps the diagonal out of the attacker's hands. Performance is even slightly better because the faster F more than compensates for the smaller message blocks. Another variation would be h_i = F(h_{i-1}) + Salsa20(m_i XOR h_{i-1}) which would further interfere with any "parallel" attack (like generalized birthday). It would however also interfere with parallel evaluation of the hash. More thoughts? - xmath
From: D. J. Bernstein on 27 Sep 2006 13:45 On 2006-09-27, xmath <xmath.news(a)gmail.com> wrote: > How about splitting the padded message into 48-byte blocks, combining > them with fixed diagonal constants into salsa20 inputs m_1, m_2, .. m_k That's a fairly strong start. The outputs such as Salsa20(m_1) are very hard to control. But it's not as strong as including a position in each input; the attacker can permute or copy output blocks. > and doing: > h_0 = IV > h_1 = F(h_0) + Salsa20(m_1) > h_2 = F(h_1) + Salsa20(m_2) > .. > h_k = F(h_{k-1}) + Salsa20(m_k) > Where F is Salsa20/8 without final addition (a "random" bijection). Some people will complain that the compression function has collisions (although this doesn't necessarily imply collisions in the whole hash): any h,m,m' have F(h) + Salsa20(m) = F(h') + Salsa20(m') where h' is computed as F^(-1)(F(h) + Salsa20(m) - Salsa20(m')). Why biject? Anyway, the standard way to analyze collision resistance of a mode is to prove that a global collision implies a much simpler local collision. Every safe mode I've seen allows this type of proof. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago
From: xmath on 27 Sep 2006 16:51 D. J. Bernstein wrote: > On 2006-09-27, xmath <xmath.news(a)gmail.com> wrote: > > How about splitting the padded message into 48-byte blocks, combining > > them with fixed diagonal constants into salsa20 inputs m_1, m_2, .. m_k > > That's a fairly strong start. The outputs such as Salsa20(m_1) are very > hard to control. But it's not as strong as including a position in each > input; the attacker can permute or copy output blocks. Yea, I had already realized it was a good idea to have the first two diagonal words fixed, and the other two words as a 64-bit value of the number of bytes hashed so far (i * 48 for all but the last block, total size for last block). Another advantage is that you then only need to zero-pad the message, nothing fancier. > Why biject? Somewhat simpler code, assures F is collision-free which could save some headache in proving things about the overall hash. I think it might also better preserve the entropy of the early message blocks of a long message? > Anyway, the standard way to analyze collision resistance of a mode is to > prove that a global collision implies a much simpler local collision. I'm trying but it's not particularly simple. Certainly it requires more from H than simple collision-resistance, like given a non-zero w it should be hard to find m and m' such that H(m) - H(m') = w. I'll spend some more thought on it tomorrow, see how it goes. - xmath
From: Scott Contini on 27 Sep 2006 20:06 xmath wrote: > 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 Just a few comments: According to my colleague who knows all this foundations of cryptographry stuff, there is no known construction which converts a one-way function into a collision resistant hash function. I'd also warn you to be careful about attempting to do it with Salsa20: Salsa20 has at least one obvious fixed point (all 0's), which is ominous. Also, the well known hash functions use compression functions. Salsa20 does not compress: the output size is the same as the input. I haven't looked at your construction with two independent one-way functions, but it would be advisable to have some type of security reduction. Constructions that are entirely heuristic are often broken very quickly. Scott
From: D. J. Bernstein on 27 Sep 2006 21:00
Scott Contini <the_great_contini(a)yahoo.com> wrote: > Salsa20 does not compress: the output size is the same as the input. Correct. But there are many safe ways to build a reasonably fast compression function from Salsa20. For example, here's Rumba20: compress a 1536-bit string partitioned as (m_1,m_2,m_3,m_4) to the 512-bit string Salsa20(c_1,m_1) + Salsa20(c_2,m_2) + Salsa20(c_3,m_3) + Salsa20(c_4,m_4) where each c_i is a new standard 128-bit constant placed on the diagonal and chosen as discussed in ``Salsa20 security,'' Section 4, ``Notes on the diagonal constants.'' Feed the final 512-bit output through Salsa20 again; truncate to 256 bits; you have a SHA-256 replacement. ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago |