International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU

Authors:
Muzhou Li , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China
Nicky Mouha , Strativia, Largo, MD, USA
Ling Sun , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China
Meiqin Wang , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China; Quan Cheng Shandong Laboratory, Jinan, China
Download:
DOI: 10.46586/tosc.v2022.i2.161-200
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9718
Search ePrint
Search Google
Abstract: At EUROCRYPT ’93, Matsui introduced linear cryptanalysis. Both Matsui’s Algorithm 1 and 2 use a linear approximation involving certain state bits. Algorithm 2 requires partial encryptions or decryptions to obtain these state bits after guessing extra key bits. For ciphers where only part of the state can be obtained, like some stream ciphers and authenticated encryption schemes, Algorithm 2 will not work efficiently since it is hard to implement partial encryptions or decryptions. In this case, Algorithm 1 is a good choice since it only involves these state bits, and one bit of key information can be recovered using a single linear approximation trail. However, when there are several strong trails containing the same state bits, known as the linear hull effect, recovering key bits with Algorithm 1 is infeasible. To overcome this, Röck and Nyberg extended Matsui’s Algorithm 1 to linear hulls. However, Röck and Nyberg found that their theoretical estimates are quite pessimistic for low success probabilities and too optimistic for high success probabilities. To deal with this, we construct new statistical models where the theoretical success probabilities are in a good accordance with experimental ones, so that we provide the first accurate analysis of the extension of Matsui’s Algorithm 1 to linear hulls. To illustrate the usefulness of our new models, we apply them to one of the ten finalists of the NIST Lightweight Cryptography (LWC) Standardization project: TinyJAMBU. We provide the first cryptanalysis under the nonce-respecting setting on the full TinyJAMBU v1 and the round-reduced TinyJAMBU v2, where partial key bits are recovered. Our results do not violate the security claims made by the designers.
BibTeX
@article{tosc-2022-32084,
  title={Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={161-200},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9718},
  doi={10.46586/tosc.v2022.i2.161-200},
  author={Muzhou Li and Nicky Mouha and Ling Sun and Meiqin Wang},
  year=2022
}