International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Subhadeep Banik , Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Khashayar Barooti , Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Serge Vaudenay , Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Hailun Yan , Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Download:
DOI: 10.1007/978-3-030-92062-3_11
Search ePrint
Search Google
Conference: ASIACRYPT 2021
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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31428,
  title={New Attacks on LowMC instances with a Single Plaintext/Ciphertext pair},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92062-3_11},
  author={Subhadeep Banik and Khashayar Barooti and Serge Vaudenay and Hailun Yan},
  year=2021
}