Distinguishing and key recovery attacks on the reduced-round SNOW-V and SNOW-Vi

摘要

This paper presents distinguishing and key recovery attacks on the reduced-round SNOW-V and SNOW-Vi, which are stream ciphers proposed for standard encryption schemes for the 5G mobile communication system. First, we construct a Mixed-Integer Linear Programming (MILP) model to search for integral characteristics using the division property, and find the best integral distinguisher in the 3-, 4-, 5-round SNOW-V, and 5 round SNOW-Vi with time complexities of 2(8), 2(16), 2(48), and 2(16), respectively. Next, we construct a bit-level MILP model to efficiently search for differential characteristics, and find the best differential characteristics in the 3-and 4-round versions. These characteristics lead to the 3-round differential distinguishers for SNOW-V and SNOW-Vi with time complexities of 2(17) and 2(12) and the 4-round differential distinguishers for SNOW-V and SNOW-Vi with time complexities of 2(97) and 2(39), respectively. Then, we consider single-bit and dual-bit differential cryptanalysis, which is inspired by the existing study on Salsa and ChaCha. By carefully choosing the IV values and differences, we can construct practical bit-wise differential distinguishers for the 4-round SNOW-V, 4-, and 5-round SNOW-Vi with time complexities of 2(4.466), 2(1.000), and 2(14.670), respectively. Finally, we improve the existing differential attack based on probabilistic neutral bits, which is also inspired by the existing study on Salsa and ChaCha. As a result, we present the best key recovery attack on the 4-round SNOW-V and SNOW-Vi with time complexities of 2(153.97) and 2(233.99 )and data complexities of 2(26.96 )and 2(19.19), respectively. Consequently, we significantly improve the existing best key recovery attack in the initialization phase by the designers.