<p>Near collision attacks and fast near collision attacks on stream ciphers are controversial attack methods in the field of cryptography in recent years, and their attack results are based on reduced experimental observations and derivation of birthday collision theory. Due to the large-scale internal state of the stream cipher, it is difficult to conduct experiments on all internal states. This article systematically summarizes the principles of near collision attacks and fast near collision attacks, and conducts a complete near collision attack experiment on the nonlinear output function used in the Grain v1 cipher. It is found that there are significant deviations in the keystream output differences for only partial near collisions, while for other non-near collisions, the corresponding keystream output difference also has a large deviation. Combining the theories of derivative of Boolean functions, we find that the effectiveness of near collision attacks is correlated to the distribution of the derivative of the Boolean function the cipher used. At the same time, we provide a more accurate near collision attack method for the Grain v1 stream cipher. Furthermore, we present an indepth analysis of the attack presented at ACNS 2023. The results of this article have a memory and data complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$2^{79}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>79</mn> </msup> </math></EquationSource> </InlineEquation>, a online time complexity of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$2^{69.3}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mn>69.3</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>, and a success probability of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$2^{-16.97}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mo>-</mo> <mn>16.97</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>.</p>

Some observations of near collision attacks on grain v1

期刊论文
出版模式：

开放获取
发表日期：

2026年3月6日

查看全文

Shaoyu Du,
Weiping Gu,
Bin Zhang

摘要

Near collision attacks and fast near collision attacks on stream ciphers are controversial attack methods in the field of cryptography in recent years, and their attack results are based on reduced experimental observations and derivation of birthday collision theory. Due to the large-scale internal state of the stream cipher, it is difficult to conduct experiments on all internal states. This article systematically summarizes the principles of near collision attacks and fast near collision attacks, and conducts a complete near collision attack experiment on the nonlinear output function used in the Grain v1 cipher. It is found that there are significant deviations in the keystream output differences for only partial near collisions, while for other non-near collisions, the corresponding keystream output difference also has a large deviation. Combining the theories of derivative of Boolean functions, we find that the effectiveness of near collision attacks is correlated to the distribution of the derivative of the Boolean function the cipher used. At the same time, we provide a more accurate near collision attack method for the Grain v1 stream cipher. Furthermore, we present an indepth analysis of the attack presented at ACNS 2023. The results of this article have a memory and data complexity of $2^{79}$ $2^{79}$ , a online time complexity of $2^{69.3}$ $2^{69.3}$ , and a success probability of $2^{-16.97}$ $2^{- 16.97}$ .