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

Abstract AEGIS is one of the authenticated encryption with associated data designs selected for the final portfolio of the CAESAR competition. It combines the AES round function and simple Boolean operations to update its large state and extract a keystream to achieve an excellent software performance. The AEGIS family consists of AEGIS-128, AEGIS-256 and AEGIS-128L, which use 5, 6 and 8 parallel AES round functions to process 128, 128 and 256 bits message block per step with slightly different output functions separately. Surprisingly, very few cryptanalytic results on AEGIS have been published so far. This paper presents the first guess-and-determine attacks on AEGIS family. Firstly, we propose a new observation on the structure of AEGIS that the relations of fixed variables remain in the outputs at consecutive steps under some conditions on the AND operations, and the vectorial bitwise AND operation is biased, which is able to derive the additional variables added directly. Secondly, we add several techniques, such as divide and conquer on byte-based columns, reduction by meet in the middle and simplification through constraints on variables, for each AEGIS member. Finally, we conduct guess-and-determine attacks on AEGIS-128, AEGIS-256 and AEGIS-128L and result in a complexity of $2^{309}$, $2^{437}$ and $2^{384}$ to $2^{416}$, respectively. Although neither attack threatens the practical security of AEGIS, it has great significance to evaluate the resistance of such structure compared with their large internal state exploited of 640, 768 and 1024 bits. It is also the first internal state recovery attack on AEGIS without nonce reusing, while only distinguishing attacks on AEGIS exist up to now.