SAT-Based Analysis of Related-Key Impossible Distinguishers on Piccolo and (Tweakable) TWINE

Lightweight block ciphers have gained attention in recent years due to the increasing demand for sensor nodes, RFID tags, and various applications. In such a situation, lightweight block ciphers Piccolo and TWINE have been proposed. Both Piccolo and TWINE are designed based on the Generalized Feistel Structure. However, it is crucial to address the potential vulnerability of these structures to the impossible differential attack. Therefore, detailed security evaluations against this attack are essential. This paper focuses on conducting bit-level evaluations of Piccolo and TWINE against related-key impossible differential attacks by leveraging SAT-aided approaches. We search for the longest distinguishers under the condition that the Hamming weight of the active bits of the input, which includes plaintext and master key differences, and output differences is set to 1, respectively. Additionally, for Tweakable TWINE, we search for the longest distinguishers under the related-tweak and related-tweak-key settings. The result for Piccolo with a 128-bit key, we identify the longest 16-round distinguishers for the first time. In addition, we also demonstrate the ability to extend these distinguishers to 17 rounds by taking into account the cancellation of the round key and plaintext difference. Regarding evaluations of TWINE with a 128-bit key, we search for the first time and reveal the distinguishers up to 19 rounds. For the search for Tweakable TWINE, we evaluate under the related-tweak-key setting for the first time and reveal the distinguishers up to 18 rounds for 80-bit key and 19 rounds for 128-bit key.