Re: associating a key with a permutation for a hash
- From: Bob Jenkins <bob_jenkins@xxxxxxxxxxxxxxxx>
- Date: Sat, 26 Jul 2008 17:32:41 -0700 (PDT)
On Jul 26, 4:20 pm, Bob Jenkins <bob_jenk...@xxxxxxxxxxxxxxxx> wrote:
On Jul 26, 10:58 am, Bob Jenkins <bob_jenk...@xxxxxxxxxxxxxxxx> wrote:
I'm looking at building a cryptographic hash starting with a weak
bijective function f.
Most attacks rely on differentials. If you can attack a structure
with n rounds of f, that comes down to finding n separate
differentials where you get to choose the input of just one of them.
(Unless you can find differentials that map to themselves, say ff(x+d)
= ff(x)+d, like Fluhrer's attack on Mercy. I'll assume that f has
been screened for differentials like that.)
One question is how big should n be. I'll make a stab in the dark: if
every one-bit differential usually affects every bit forward by at
least 25% after x rounds and backwards by at least 25% after y rounds,
then n = 2(x*y) is a good guess. I think I've seen 1.5 rather than 2
used in practice.
Another question is, given that n=30 rounds of f is enough, how do you
combine data blocks with the permutation to build a hash? How do you
associate a key with the permutation?
One approach chooses m=10 (some m that divides n evenly). Do n/m=3
rounds of the permutation, then do a combine. Combine every block m
times, 2n/m=6 rounds apart, which is every other combine. That means
you've got 2m-1=19 blocks you're keeping track of, and you combine m
blocks every n/m rounds. A combine XORs all m blocks to the internal
state. To prevent the XORs from extracting the same information from
the blocks every time, rotate the blocks by different amounts every
time they're combined, say by (i choose 2)%16 for the ith combine of a
block. The key can be XORed in too, unrotated, every combine.
Leading blocks at startup can be all zero, and trailing blocks can all
be set to the total data length.
A block B will be combined m times, forming m-1 gaps of 2n/m, that's n
+n(m-2)/m rounds to exploit deltas in B. A block B followed by a
block C will form m (B,C) pairs with gaps of length n/m. That's m*(n/
m)=n rounds to exploit deltas in B and C. The block rotates prevent
the same differential from being used every time. There's also m-1
(C,B) pairs with gaps of n/m, but also a leading B and a trailing C
with gaps of n/m each. That's n/m + (m-1)(n/m) + n/m = n + n/m rounds
to exploit deltas in (C,B) pairs.
Is this actually enough? This combines a new block every n/m rounds,
which is much less than the n rounds required for security. It's even
less than the n/4 rounds required for avalanche. I've got a work-in-
progress hash that implements this,http://burtleburtle.net/bob/crypto/nisthash6.c
. I havent' screened that for differentials that map to themselves
yet.
It's not enough. Suppose you take consecutive data blocks A,B,C,D and
complement them. You'll get the first (A,B) pair (n/m rounds) and
last (C,D) pair (n/m round), but in between A^C and B^D will cancel
out the complement. That's 2n/m rounds to find differentials for,
well short of n.
The fix to this, well, the trick, is to combine the blocks
nonlinearly. Sometimes combining f(B) instead of B. That f counts
towards the n rounds, but only once no matter how many times f(B) is
used.
.
- References:
- associating a key with a permutation for a hash
- From: Bob Jenkins
- Re: associating a key with a permutation for a hash
- From: Bob Jenkins
- associating a key with a permutation for a hash
- Prev by Date: Re: associating a key with a permutation for a hash
- Next by Date: Re: associating a key with a permutation for a hash
- Previous by thread: Re: associating a key with a permutation for a hash
- Next by thread: Re: associating a key with a permutation for a hash
- Index(es):
Relevant Pages
|
