Internal differential cryptanalysis is introduced by Peyrin (Improved differential attacks for ECHO and Grøstl. In: Rabin T (ed) Advances in cryptology—CRYPTO 2010. LNCS, vol 6223. Springer, Berlin, pp 370–392, 2010. doi:10.1007/978-3-642-14623-7_20). It is generalized and firstly applied to collision attacks of round-reduced Keccak by Dinur et al. (Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials. In: Moriai S (ed) Fast software encryption. FSE 2013. LNCS, vol 8424. Springer, Berlin, pp 219–240, 2013. doi:10.1007/978-3-662-43933-3_12). Recently, internal differential cryptanalysis is further improved by Zhang et al., which brings better collision attacks. Inspired by their works, we propose a new technique named internal differential structure which is a framework of preimage attacks on round-reduced Keccak. The technique internal differential structure is a combination of two parts. The first part is a reversed characteristic from a fixed internal difference backward to the starting state with symmetric capacity. As for the second part, the internal difference keeps linear after 1.5 rounds until the last <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_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>, which can be restricted to match the output digest. With this simple but useful technique, we obtain the preimage attacks of 5-round Keccak-224/256 with complexity <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{204.0}/2^{230.0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mn>204.0</mn> </mrow> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mrow> <mn>230.0</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> and the complexity of 4-round Keccak-224/256 can be decreased to <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{157.5}/2^{173.5}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mn>157.5</mn> </mrow> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mrow> <mn>173.5</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. If <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{98.0}/2^{114.2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mn>98.0</mn> </mrow> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mrow> <mn>114.2</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> memory is provided, the complexity of 4-round Keccak-224/256 can be further decreased to <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{144.4}/2^{160.4}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mn>144.4</mn> </mrow> </msup> <mo stretchy="false">/</mo> <msup> <mn>2</mn> <mrow> <mn>160.4</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. Besides, this technique can be applied to 4-round Keccak[r = 240, c = 160, <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell =80$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>=</mo> <mn>80</mn> </mrow> </math></EquationSource> </InlineEquation>] (start round index <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$ir=5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mi>r</mi> <mo>=</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>) with complexity around <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="30" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{58.7}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mn>58.7</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> and 2-round Keccak[r = 40, c = 160, <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell =80$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>=</mo> <mn>80</mn> </mrow> </math></EquationSource> </InlineEquation>] (start round index <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$ir=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mi>r</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>) with complexity around <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1655_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="30" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{49.0}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mn>49.0</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>, resulting new solutions to Keccak preimage contest.

Internal differential structure: preimage attacks on up to 5-round Keccak

期刊论文
发表日期：

2025年6月6日

查看全文

Xiaoen Lin,
Le He,
Zhengrong Lu,
Yantian Shen,
Chongxu Ren,
Hongbo Yu

摘要

Internal differential cryptanalysis is introduced by Peyrin (Improved differential attacks for ECHO and Grøstl. In: Rabin T (ed) Advances in cryptology—CRYPTO 2010. LNCS, vol 6223. Springer, Berlin, pp 370–392, 2010. doi:10.1007/978-3-642-14623-7_20). It is generalized and firstly applied to collision attacks of round-reduced Keccak by Dinur et al. (Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials. In: Moriai S (ed) Fast software encryption. FSE 2013. LNCS, vol 8424. Springer, Berlin, pp 219–240, 2013. doi:10.1007/978-3-662-43933-3_12). Recently, internal differential cryptanalysis is further improved by Zhang et al., which brings better collision attacks. Inspired by their works, we propose a new technique named internal differential structure which is a framework of preimage attacks on round-reduced Keccak. The technique internal differential structure is a combination of two parts. The first part is a reversed characteristic from a fixed internal difference backward to the starting state with symmetric capacity. As for the second part, the internal difference keeps linear after 1.5 rounds until the last $\chi $ $χ$ , which can be restricted to match the output digest. With this simple but useful technique, we obtain the preimage attacks of 5-round Keccak-224/256 with complexity $2^{204.0}/2^{230.0}$ $2^{204.0} / 2^{230.0}$ and the complexity of 4-round Keccak-224/256 can be decreased to $2^{157.5}/2^{173.5}$ $2^{157.5} / 2^{173.5}$ . If $2^{98.0}/2^{114.2}$ $2^{98.0} / 2^{114.2}$ memory is provided, the complexity of 4-round Keccak-224/256 can be further decreased to $2^{144.4}/2^{160.4}$ $2^{144.4} / 2^{160.4}$ . Besides, this technique can be applied to 4-round Keccak[r = 240, c = 160, $\ell =80$ $ℓ = 80$ ] (start round index $ir=5$ $i r = 5$ ) with complexity around $2^{58.7}$ $2^{58.7}$ and 2-round Keccak[r = 40, c = 160, $\ell =80$ $ℓ = 80$ ] (start round index $ir=3$ $i r = 3$ ) with complexity around $2^{49.0}$ $2^{49.0}$ , resulting new solutions to Keccak preimage contest.