Paper 2019/424

Preimage Security of KNOT-Hash

Raghvendra Rohit

Abstract

KNOT is a Round 1 submission of the ongoing NIST lightweight cryptography project. In this short note, we show that the preimage security of KNOT-Hash instances with squeezing rate half the state size is lower than the claimed security. Our attack exploits the non-randomness properties of the KNOT Sbox which reduce the preimage complexities. In particular, if $2n$ is the squeezing rate then the preimage security is approximately $(\text{logtextsubscript{2}}(\frac{3}{4}){)}^{-n}\times 2^{\frac{3n}{4}}\times (\text{logtextsubscript{2}}(3){)}^{\frac{n}{2}}$. For $n=64$, 96 and 128, the former bound translates to $2^{125.28}$, $2^{187.92}$ and $2^{250.57}$, respectively.

Note: Thanks to the KNOT designers for pointing out the inconsistencies in Step 1 and Step 2 of the attack (Section 3). The time complexities indeed exceed the claimed security level and hence the mentioned attack does not work in the current scenario.