Probabilistic Related-Key Statistical Saturation Cryptanalysis

Muzhou Li; Nicky Mouha; Ling Sun; Meiqin Wang

Paper 2023/1245

Probabilistic Related-Key Statistical Saturation Cryptanalysis

Muzhou Li, School of Cyber Science and Technology, Shandong University, Qingdao, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Nicky Mouha, Strativia, Largo, MD, USA

Ling Sun, School of Cyber Science and Technology, Shandong University, Qingdao, China, Quan Cheng Shandong Laboratory, Jinan, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China, State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China

Meiqin Wang, School of Cyber Science and Technology, Shandong University, Qingdao, China, Quan Cheng Shandong Laboratory, Jinan, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Abstract

The related-key statistical saturation (RKSS) attack is a cryptanalysis method proposed by Li et al. at FSE 2019. It can be seen as the extension of previous statistical saturation attacks under the related-key setting. The attack takes advantage of a set of plaintexts with some bits fixed, while the other bits take all possible values, and considers the relation between the value distributions of a part of the ciphertext bits generated under related keys. Usually, RKSS distinguishers exploit the property that the value distribution stays invariant under the modification of the key. However, this property can only be deterministically verified if the plaintexts cover all possible values of a selection of bits. In this paper, we propose the probabilistic RKSS cryptanalysis which avoids iterating over all non-fixed plaintext bits by applying a statistical method on top of the original RKSS distinguisher. Compared to the RKSS attack, this newly proposed attack has a significantly lower data complexity and has the potential of attacking more rounds. As an illustration, for reduced-round Piccolo, we obtain the best key recovery attacks (considering both pre- and post-whitening keys) on both versions in terms of the number of rounds. Note that these attacks do not threaten the full-round security of Piccolo.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Minor revision. SAC 2023
Keywords: Related-Key Statistical Saturation Piccolo Statistic
Contact author(s): muzhouli @ mail sdu edu cn
nicky @ mouha be
lingsun @ sdu edu cn
mqwang @ sdu edu cn
History: 2023-08-21: approved; 2023-08-17: received; See all versions
Short URL: https://ia.cr/2023/1245
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1245,
      author = {Muzhou Li and Nicky Mouha and Ling Sun and Meiqin Wang},
      title = {Probabilistic Related-Key Statistical Saturation Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1245},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1245}
}