Cryptology ePrint Archive: Report 2021/1296

Partitioning Oracles from Weak Key Forgeries

Marcel Armour and Carlos Cid

Abstract: In this work, we show how weak key forgeries against polynomial hash based Authenticated Encryption (AE) schemes, such as AES-GCM, can be leveraged to launch partitioning oracle attacks. Partitioning oracle attacks were recently introduced by Len et al. (Usenix'21) as a new class of decryption error oracle which, conceptually, takes a ciphertext as input and outputs whether or not the decryption key belongs to some known subset of keys. Partitioning oracle attacks allow an adversary to query multiple keys simultaneously, leading to practical attacks against low entropy keys (e.g. those derived from passwords).

Weak key forgeries were given a systematic treatment in the work of Procter and Cid (FSE'13), who showed how to construct MAC forgeries that effectively test whether the decryption key is in some (arbitrary) set of target keys. Consequently, it would appear that weak key forgeries naturally lend themselves to constructing partition oracles; we show that this is indeed the case, and discuss some practical applications of such an attack. Our attack applies in settings where AE schemes are used with static session keys, and has the particular advantage that an attacker has full control over the underlying plaintexts, allowing any format checks on underlying plaintexts to be met -- including those designed to mitigate against partitioning oracle attacks.

Prior work demonstrated that key commitment is an important security property of AE schemes, in particular settings. Our results suggest that resistance to weak key forgeries should be considered a related design goal. Lastly, our results reinforce the message that weak passwords should never be used to derive encryption keys.

Category / Keywords: secret-key cryptography / Authenticated Encryption, Partitioning Oracles, Weak Key Forgeries

Original Publication (with minor differences): Cryptology and Network Security 2021

Date: received 27 Sep 2021, last revised 27 Sep 2021

Contact author: marcel armour 2017 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20210927:130500 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]