What input bits are revealed when revealing the first 256 bits of the output Keccak-f permutation?

cryptobeginner

4/21/23, 10:51 PM

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?

0 + 0

sha-3

keccak

kelalaka

4/21/23, 10:59 PM

The first question is the avalanche property that we want from hash functions.

Score:1

Crypto

poncho

4/21/23, 11:00 PM

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...

0 + 0

cryptobeginner

4/21/23, 11:11 PM

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?

poncho

4/22/23, 3:41 PM

@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...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What input bits are revealed when revealing the first 256 bits of the output Keccak-f permutation?

TH: บิตอินพุตใดที่เปิดเผยเมื่อเปิดเผย 256 บิตแรกของการเรียงสับเปลี่ยนเอาต์พุต Keccak-f

RO: Ce biți de intrare sunt dezvăluiți la dezvăluirea primilor 256 de biți ai permutației Keccak-f de ieșire?

RU: Какие входные биты обнаруживаются при раскрытии первых 256 бит выходной перестановки Keccak-f?

VI: Những bit đầu vào nào được tiết lộ khi tiết lộ 256 bit đầu tiên của hoán vị Keccak-f đầu ra?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.