Cryptology ePrint Archive: Report 2019/1000

Security of Symmetric Primitives against Key-Correlated Attacks

Aisling Connolly and Pooya Farshim and Georg Fuchsbauer

Abstract: We study the security of symmetric primitives against key-correlated attacks (KCA), whereby an adversary can arbitrarily correlate keys, messages, and ciphertexts. Security against KCA is required whenever a primitive should securely encrypt key-dependent data, even when it is used under related keys. KCA is a strengthening of the previously considered notions of related-key attack (RKA) and key-dependent message (KDM) security. This strengthening is strict, as we show that 2-round Even–Mansour fails to be KCA secure even though it is both RKA and KDM secure. We provide feasibility results in the ideal-cipher model for KCAs and show that 3-round Even–Mansour is KCA secure under key offsets in the random-permutation model. We also give a natural transformation that converts any authenticated encryption scheme to a KCA-secure one in the random-oracle model. Conceptually, our results allow for a unified treatment of RKA and KDM security in idealized models of computation.

Category / Keywords: secret-key cryptography / Key-correlated attack, related-key attack, key-dependent-message attack, ideal-cipher model, random-oracle model, authenticated encryption, xkcd.

Original Publication (in the same form): IACR-FSE-2019

Date: received 3 Sep 2019

Contact author: aisling connolly at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20190905:072712 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]