Re: Re-rolled Salsa20 function

From: xmath (xmath.news_at_gmail.com)
Date: 09/26/05 

Date: 26 Sep 2005 10:34:34 -0700

D. J. Bernstein wrote:
> More interesting possibilities would break the traditional chaining
> structure. Applying Salsa20 to each message block in parallel produces
> an output string that seems hard to control and thus easy to compress.
> For example, it seems difficult to find collisions in the 64-byte string
> Salsa20(m0,c) ^ Salsa20(m1,c^1), where m0, m1 are 48-byte message blocks
> and c is a 16-byte constant. Similarly, it seems difficult to find
> collisions in the 64-byte string
>
> Salsa20(Salsa20(m0,c) ^ Salsa20(m1,c^1))
> ^ Salsa20(Salsa20(m2,c) ^ Salsa20(m3,c^1) ^ 1)
>
> where m0, m1, m2, m3 are 48-byte message blocks. The general idea is to
> start from the string m0,c,m1,c,m2,c,... and then hash, in parallel,
> each 128-byte block b0,b1 to Salsa20(b0) ^ Salsa20(b1^1). The final
> 64-byte output can be fed through Salsa20 again and truncated to 32
> bytes, producing a 256-bit hash with one Salsa20 invocation for each 32
> message bytes.

hm, so say the message is split into 48-byte chunks, each formatted
into 64-bit blocks by inserting constants into the diagonal, and I call
those blocks m0, m1, m2, etc.

define F(x) = Salsa20(Salsa20(x))
define C(x,y) = Salsa20(x) ^ Salsa20(y^1)

then if the number of blocks is a power of two, you get:
F(m0)
F(C(m0,m1))
F(C(C(m0,m1),C(m2,m3)))
F(C(C(C(m0,m1),C(m2,m3)),C(C(m4,m5),C(m6,m7))))

that's 2^(n+1) invocations of Salsa20 for every 2^n 48-byte message
blocks, which is one Salsa20 invocation for every 24 message bytes.

so I'm not sure where you get the "one Salsa20 invocation for each 32
message bytes"... did I misunderstand your scheme?

I'd also estimate some might find it somewhat annoying that you need
O(log(k)) memory for hashing a length-k message.

how about plain
Salsa20(m0) ^ Salsa20(m1^1) ^ Salsa20(m2^2) ^ .. ^ Salsa20(mk^k)

this gives one Salsa20 per 48 bytes. As long as k < 2^32, the three
untouched words of the constant should still provide sufficient
protection or not?

or more conservatively, apply Salsa20 on 32-byte message blocks, with
constant *and* separate nonce (block-counter), and XOR those all
together. giving one Salsa20 per 32 bytes.

 -xmath

Relevant Pages

  • Re: Re-rolled Salsa20 function
    ... it's safe to build a compression function in ... Either approach produces a conservative hash ... Applying Salsa20 to each message block in parallel produces ... it seems difficult to find collisions in the 64-byte string ...
    (sci.crypt)
  • Re: Cryptographic Hash function
    ... always produces a fixed length string as output. ... mean that the output string will always be longer than the ... The hash function generally does not care about the length ... So yes, collisions are bound to be a mathematical possibility, ...
    (sci.crypt)
Loading