Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU
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 sta...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-06-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/9718 |
| _version_ | 1818471171719430144 |
|---|---|
| author | Muzhou Li Nicky Mouha Ling Sun Meiqin Wang |
| author_facet | Muzhou Li Nicky Mouha Ling Sun Meiqin Wang |
| author_sort | Muzhou Li |
| collection | DOAJ |
| description |
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.
|
| first_indexed | 2024-04-13T21:47:08Z |
| format | Article |
| id | doaj.art-639d1b59cdf24c10bf4bd24a39f04233 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-04-13T21:47:08Z |
| publishDate | 2022-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-639d1b59cdf24c10bf4bd24a39f042332022-12-22T02:28:32ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-06-012022210.46586/tosc.v2022.i2.161-200Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBUMuzhou Li0Nicky Mouha1Ling Sun2Meiqin Wang3Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaStrativia, Largo, MD, USAKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey 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 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. https://tosc.iacr.org/index.php/ToSC/article/view/9718Matsui’s Algorithm 1Linear HullTinyJAMBU |
| spellingShingle | Muzhou Li Nicky Mouha Ling Sun Meiqin Wang Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU IACR Transactions on Symmetric Cryptology Matsui’s Algorithm 1 Linear Hull TinyJAMBU |
| title | Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU |
| title_full | Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU |
| title_fullStr | Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU |
| title_full_unstemmed | Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU |
| title_short | Revisiting the Extension of Matsui’s Algorithm 1 to Linear Hulls: Application to TinyJAMBU |
| title_sort | revisiting the extension of matsui s algorithm 1 to linear hulls application to tinyjambu |
| topic | Matsui’s Algorithm 1 Linear Hull TinyJAMBU |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/9718 |
| work_keys_str_mv | AT muzhouli revisitingtheextensionofmatsuisalgorithm1tolinearhullsapplicationtotinyjambu AT nickymouha revisitingtheextensionofmatsuisalgorithm1tolinearhullsapplicationtotinyjambu AT lingsun revisitingtheextensionofmatsuisalgorithm1tolinearhullsapplicationtotinyjambu AT meiqinwang revisitingtheextensionofmatsuisalgorithm1tolinearhullsapplicationtotinyjambu |