<p>Keccak, the cryptographic hash function at the core of the SHA-3 standard, offers enhanced security and efficiency for data integrity and authentication. Qin et al. (EUROCRYPT 2023) first introduced a Meet-in-the-Middle (MitM) preimage attack on Keccak using a Mixed-Integer Linear Programming (MILP) model. In this paper, we further analyze Keccak’s security against this MitM preimage attack. In Qin’s work, the model relied only on the digest portion of Keccak’s output to find match points, though the digest represents only part of the full output. Our improved MILP model expands on this by incorporating both the digest and additional selected bits from the remaining output of Keccak. Additionally, we exploit the properties of the<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation> operation to optimize the model further. This new model increases the number of match points in MitM attacks and effectively reduces time complexity. Applying it to Keccak-384 and Keccak-512, we achieve the best-known results for 4-round Keccak-512, with a time complexity of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{502.8}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mn>502.8</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> and memory complexity of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{79}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>79</mn> </msup> </math></EquationSource> </InlineEquation>. Moreover, We present the first MitM preimage attack on weak digests for Keccak-384 and Keccak-512, where “weak digests” refers to digests that are more vulnerable to efficient attacks compared to others. For 4-round Keccak-512, the attack has a time complexity of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{491} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>491</mn> </msup> </math></EquationSource> </InlineEquation> and memory complexity of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{68} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>68</mn> </msup> </math></EquationSource> </InlineEquation>. Since we fix the values of 57 bits in the digest, this attack is effective for <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{455} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>455</mn> </msup> </math></EquationSource> </InlineEquation> digests. For 4-round Keccak-384, it achieves a time complexity of <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{376.1} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mn>376.1</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> and memory complexity of <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{73} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>73</mn> </msup> </math></EquationSource> </InlineEquation>. Since we fix the values of 12 bits in the digest, this attack is effective for <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1703_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">$ 2^{372} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>372</mn> </msup> </math></EquationSource> </InlineEquation> digests.</p>

Exploiting output bits and the $\chi $ operation in MitM preimage attacks on Keccak

期刊论文
发表日期：

2025年8月7日

查看全文

Tianling Weng,
Gaoli Wang,
Keting Jia,
Xiaoyang Dong,
Siwei Sun,
Tingting Cui

摘要

Keccak, the cryptographic hash function at the core of the SHA-3 standard, offers enhanced security and efficiency for data integrity and authentication. Qin et al. (EUROCRYPT 2023) first introduced a Meet-in-the-Middle (MitM) preimage attack on Keccak using a Mixed-Integer Linear Programming (MILP) model. In this paper, we further analyze Keccak’s security against this MitM preimage attack. In Qin’s work, the model relied only on the digest portion of Keccak’s output to find match points, though the digest represents only part of the full output. Our improved MILP model expands on this by incorporating both the digest and additional selected bits from the remaining output of Keccak. Additionally, we exploit the properties of the $\chi $ $χ$ operation to optimize the model further. This new model increases the number of match points in MitM attacks and effectively reduces time complexity. Applying it to Keccak-384 and Keccak-512, we achieve the best-known results for 4-round Keccak-512, with a time complexity of $2^{502.8}$ $2^{502.8}$ and memory complexity of $2^{79}$ $2^{79}$ . Moreover, We present the first MitM preimage attack on weak digests for Keccak-384 and Keccak-512, where “weak digests” refers to digests that are more vulnerable to efficient attacks compared to others. For 4-round Keccak-512, the attack has a time complexity of $ 2^{491} $ $2^{491}$ and memory complexity of $ 2^{68} $ $2^{68}$ . Since we fix the values of 57 bits in the digest, this attack is effective for $ 2^{455} $ $2^{455}$ digests. For 4-round Keccak-384, it achieves a time complexity of $ 2^{376.1} $ $2^{376.1}$ and memory complexity of $ 2^{73} $ $2^{73}$ . Since we fix the values of 12 bits in the digest, this attack is effective for $ 2^{372} $ $2^{372}$ digests.

Exploiting output bits and the \(\chi \) operation in MitM preimage attacks on Keccak

摘要