A practical distinguisher on the full Skyscraper permutation

Antoine Bak

Paper 2025/102

A practical distinguisher on the full Skyscraper permutation

Antoine Bak, French Institute for Research in Computer Science and Automation, Direction Générale de l'Armement

Abstract

Skyscraper is a cryptographic permutation published in TCHES 2025, optimized for use in proof systems such as PlonK. This primitive is based on a 10-round Feistel network combining $x^{2}$ monomials and lookup-based functions to achieve competitive plain performances and efficiency in proof systems supporting lookups. In terms of security, the $x^{2}$ monomials are supposed to provide security against statistical attacks, while lookups are supposed to provide security against algebraic attacks. In this note, we show that this primitive has a much lower security margin than expected. Using a rebound attack, we find practical truncated differentials on the full permutation. As a corollary, we also find a practical collision attack on the compression function based on a 9-round Skyscraper permutation, which significantly reduces the security margin of the primitive. All of these attacks have been implemented and work in practice.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Skyscraper split-and-lookup rebound attack cryptanalysis
Contact author(s): antoine bak @ inria fr
History: 2025-01-23: approved; 2025-01-22: received; See all versions
Short URL: https://ia.cr/2025/102
License: CC BY

BibTeX

@misc{cryptoeprint:2025/102,
      author = {Antoine Bak},
      title = {A practical distinguisher on the full Skyscraper permutation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/102},
      year = {2025},
      url = {https://eprint.iacr.org/2025/102}
}