Cryptology ePrint Archive: Report 2021/1345

New Attacks on LowMC instances with a Single Plaintext/Ciphertext pair

Subhadeep Banik and Khashayar Barooti and Serge Vaudenay and Hailun Yan

Abstract: Cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is a mathematically challenging problem. This is because the attacker is unable to employ most of the standard techniques in symmetric cryptography like linear and differential cryptanalysis. This scenario is particularly relevant while arguing the security of the \picnic digital signature scheme in which the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. In the paper by Banik et al. (IACR ToSC 2020:4), the authors used a linearization technique of the LowMC S-box to mount attacks on some instances of the block cipher. In this paper, we first make a more precise complexity analysis of the linearization attack. Then, we show how to perform a 2-stage MITM attack on LowMC. The first stage reduces the key candidates corresponding to a fraction of key bits of the master key. The second MITM stage between this reduced candidate set and the remaining fraction of key bits successfully recovers the master key. We show that the combined computational complexity of both these stages is significantly lower than those reported in the ToSC paper by Banik et al.

Category / Keywords: secret-key cryptography /

Original Publication (with minor differences): IACR-ASIACRYPT-2021

Date: received 6 Oct 2021, last revised 22 Nov 2021

Contact author: subhadeep banik at epfl ch, khashayar barooti at epfl ch, serge vaudenay at epfl ch, hailun yan at epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20211122:130205 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]