Paper 2024/722

Ultrametric integral cryptanalysis

Tim Beyne, KU Leuven
Michiel Verbauwhede, KU Leuven
Abstract

A systematic method to analyze \emph{divisibility properties} is proposed. In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs). From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis. The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Geometric approachIntegral cryptanalysisDivision property
Contact author(s)
tim beyne @ esat kuleuven be
michiel verbauwhede @ esat kuleuven be
History
2024-05-11: approved
2024-05-10: received
See all versions
Short URL
https://ia.cr/2024/722
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/722,
      author = {Tim Beyne and Michiel Verbauwhede},
      title = {Ultrametric integral cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2024/722},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/722}},
      url = {https://eprint.iacr.org/2024/722}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.