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

Zhen Shi, Chenhui Jin, Jiyan Zhang, Ting Cui, Lin Ding, and Yu Jin

##### 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 attack on full SNOW-V and SNOW-Vi, which is better than the exhaustive key search with respect to time complexity. 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}$.

Available format(s)
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
SNOW-VSNOW-ViCryptanalysisLinear Approxima- tionAutomatic SearchCorrelation Attack.
Contact author(s)
shizhenieu @ 126 com
jinchenhui @ 126 com
xdzhangjiyan @ 126 com
cuiting_1209 @ 126 com
dinglin_cipher @ 163 com
jinyu0801 @ foxmail com
History
2022-02-09: revised
See all versions
Short URL
https://ia.cr/2021/1047

CC BY

BibTeX

@misc{cryptoeprint:2021/1047,
author = {Zhen Shi and Chenhui Jin and Jiyan Zhang and Ting Cui and Lin Ding and Yu Jin},
title = {A Correlation Attack on Full SNOW-V and SNOW-Vi},
howpublished = {Cryptology ePrint Archive, Paper 2021/1047},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1047}},
url = {https://eprint.iacr.org/2021/1047}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.