1
$\begingroup$

Given the Keccak-f[1600] permutation I am interested in the following property: What bits in the output are influenced by what bits of the input? That is, if I change for example say the second bit of the input, what bits of the output are influenced by this?

Put another way: Assume I have the first 256 bits of the output of the Keccak function. Then, because Keccak-f[1600] is bijective, there are only 1600-256 preimages that can still map to an output with the "right" first 256 bits. Is there a way to estimate how many bits are the same across all 1600-256 remaining values?

$\endgroup$
1
  • $\begingroup$ The first question is the avalanche property that we want from hash functions. $\endgroup$
    – kelalaka
    Dec 21, 2021 at 22:59

1 Answer 1

1
$\begingroup$

What bits in the output are influenced by what bits of the input? That is, if I change for example say the second bit of the input, what bits of the output are influenced by this?

To the best of our knowledge, all output bits are a complex function of all input bits. Flipping any specific input bit (say, the second one) can potentially flip any output bit.

Assume I have the first 256 bits of the output of the Keccak function. Then, because Keccak-f[1600] is bijective, there are only 1600-256 preimages that can still map to an output with the "right" first 256 bits

Actually, you miscomputed; there are $2^{1600-256}$ preimages, that is:

383984923062992702193107238768305990575971314802788874095145673202075995393018055488645297669674812185833211621938100469973519720714697045576788566898683254440275883795786334484525778054071087861396060398229434719927672395650215231472663143090071728679350725089418264731278276442800414037787428461842409521168393903855600900323733353159466811689332335765898192891862061280747855198528180896166938113212416

preimages. That's a tad more than 1600-256 = 1344...

$\endgroup$
2
  • $\begingroup$ Aeh yes, right, thanks! You mentioned that "Flipping any specific input bit (say, the second one) can potentially flip any output bit.". Now, assume we know 1599 bits of the output. Then there are only 2 potential preimages that could lead to this output in the Keccak-f, function, right? Is it really guaranteed that those preimages are always different in every bit? $\endgroup$ Dec 21, 2021 at 23:11
  • $\begingroup$ @cryptobeginner: obviously, with only 2 preimages, some of the output bits (likely about half) will be consistent between the 2 postimages. However, if you change one of the 1599 fixed bits, the bits that remain the same between those two modified postimages are likely to change... $\endgroup$
    – poncho
    Dec 22, 2021 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.