International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Correlation Attack on Full SNOW-V and SNOW-Vi

Authors:
Zhen Shi , PLA SSF Information Engineering University
Chenhui Jin , PLA SSF Information Engineering University
Jiyan Zhang , PLA SSF Information Engineering University
Ting Cui , PLA SSF Information Engineering University
Lin Ding , PLA SSF Information Engineering University
Yu Jin , PLA SSF Information Engineering University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: In this paper, a method for searching correlations between the binary stream of Linear Feedback Shift Register (LFSR) and the keystream of SNOW-V and SNOW-Vi is presented based on the technique of approximation to composite functions. With the aid of the linear relationship between the four taps of LFSR input into Finite State Machine (FSM) at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a series of linear approximation trails with high correlation. By exhausting the intermediate masks, we find a binary linear approximation with a correlation $-2^{-47.76}$. Using such approximation, we propose a correlation attack on SNOW-V with an expected time complexity $2^{246.53}$, a memory complexity $2^{238.77}$ and $2^{237.5}$ keystream words generated by the same key and Initial Vector (IV). For SNOW-Vi, we provide a binary linear approximation with the same correlation and mount a correlation attack with the same complexity as that of SNOW-V. To the best of our knowledge, this is the first known efficient attack on full SNOW-V and SNOW-Vi, which is better than the exhaustive key search. The results indicate that neither SNOW-V nor SNOW-Vi can guarantee the 256-bit security level if we ignore the design constraint that the maximum length of keystream for a single pair of key and IV is less than $2^{64}$.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31829,
  title={A Correlation Attack on Full SNOW-V and SNOW-Vi},
  publisher={Springer-Verlag},
  author={Zhen Shi and Chenhui Jin and Jiyan Zhang and Ting Cui and Lin Ding and Yu Jin},
  year=2022
}