Paper 2021/1345

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

Subhadeep Banik, Khashayar Barooti, 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
Contact author(s)
subhadeep banik @ epfl ch
khashayar barooti @ epfl ch
serge vaudenay @ epfl ch
hailun yan @ epfl ch
History
2021-11-22: revised
2021-10-07: received
See all versions
Short URL
https://ia.cr/2021/1345
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1345,
      author = {Subhadeep Banik and Khashayar Barooti and Serge Vaudenay and Hailun Yan},
      title = {New Attacks on {LowMC} instances with a Single Plaintext/Ciphertext pair},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1345},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1345}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.