PNB Based Differential Cryptanalysis of Salsa20 and ChaCha

Nasratullah GHAFOORI; Atsuko MIYAJI; Ryoma ITO; Shotaro MIYASHITA

doi:10.1587/transinf.2022ICP0015

PNB Based Differential Cryptanalysis of Salsa20 and ChaCha

Nasratullah GHAFOORI, Atsuko MIYAJI, Ryoma ITO, Shotaro MIYASHITA

Full Text Views

0

Cite this

Summary :

This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2^241.62 and data complexity of 2^31.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2^254.011 and data complexity of 2^51.81.

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.9 pp.1407-1422

Publication Date: 2023/09/01

Publicized: 2023/07/13

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022ICP0015

Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)

Category

Authors

Nasratullah GHAFOORI
  Osaka University
Atsuko MIYAJI
  Osaka University
Ryoma ITO
  National Institute of Information and Communications Technology
Shotaro MIYASHITA
  Osaka University

Keyword

stream cipher, Salsa20, ChaCha, differential cryptanalysis, PNBs

Cite this

Copy

Nasratullah GHAFOORI, Atsuko MIYAJI, Ryoma ITO, Shotaro MIYASHITA, "PNB Based Differential Cryptanalysis of Salsa20 and ChaCha" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 9, pp. 1407-1422, September 2023, doi: 10.1587/transinf.2022ICP0015.
Abstract: This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2^241.62 and data complexity of 2^31.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2^254.011 and data complexity of 2^51.81.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022ICP0015/_p

Copy

@ARTICLE{e106-d_9_1407,
author={Nasratullah GHAFOORI, Atsuko MIYAJI, Ryoma ITO, Shotaro MIYASHITA, },
journal={IEICE TRANSACTIONS on Information},
title={PNB Based Differential Cryptanalysis of Salsa20 and ChaCha},
year={2023},
volume={E106-D},
number={9},
pages={1407-1422},
abstract={This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2^241.62 and data complexity of 2^31.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2^254.011 and data complexity of 2^51.81.},
keywords={},
doi={10.1587/transinf.2022ICP0015},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - PNB Based Differential Cryptanalysis of Salsa20 and ChaCha
T2 - IEICE TRANSACTIONS on Information
SP - 1407
EP - 1422
AU - Nasratullah GHAFOORI
AU - Atsuko MIYAJI
AU - Ryoma ITO
AU - Shotaro MIYASHITA
PY - 2023
DO - 10.1587/transinf.2022ICP0015
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2023
AB - This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2^241.62 and data complexity of 2^31.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2^254.011 and data complexity of 2^51.81.
ER -