International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Human-readable Proof of the Related-Key Security of AES-128

Authors:
Khoongming Khoo , DSO National Laboratories
Eugene Lee , Raffles Institution
Thomas Peyrin , School of Physical and Mathematical Sciences, ; School of Computer Science and Engineering, ; Temasek Laboratories, Nanyang Technological University
Siang Meng Sim , Nanyang Technological University
Download:
DOI: 10.13154/tosc.v2017.i2.59-83
URL: https://tosc.iacr.org/index.php/ToSC/article/view/638
Search ePrint
Search Google
Abstract: The related-key model is now considered an important scenario for block cipher security and many schemes were broken in this model, even AES-192 and AES-256. Recently were introduced efficient computer-based search tools that can produce the best possible related-key truncated differential paths for AES. However, one has to trust the implementation of these tools and they do not provide any meaningful information on how to design a good key schedule, which remains a challenge for the community as of today. We provide in this article the first human-readable proof on the minimal number of active Sboxes in the related-key model for AES-128, without any help from a computer. More precisely, we show that any related-key differential path for AES-128 will respectively contain at least 0, 1, 3 and 9 active Sboxes for 1, 2, 3 and 4 rounds. Our proof is tight, not trivial, and actually exhibits for the first time the interplay between the key state and the internal state of an AES-like block cipher with an AES-like key schedule. As application example, we leverage our proofs to propose a new key schedule, that is not only faster (a simple permutation on the byte positions) but also ensures a higher number of active Sboxes than AES-128’s key schedule. We believe this is an important step towards a good understanding of efficient and secure key schedule designs.
BibTeX
@article{tosc-2017-28477,
  title={Human-readable Proof of the Related-Key Security of AES-128},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2017, Issue 2},
  pages={59-83},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/638},
  doi={10.13154/tosc.v2017.i2.59-83},
  author={Khoongming Khoo and Eugene Lee and Thomas Peyrin and Siang Meng Sim},
  year=2017
}