TU Darmstadt / ULB / TUbiblio

On the Related-Key Attack Security of Authenticated Encryption Schemes

Faust, Sebastian ; Krämer, Juliane ; Orlt, Maximilian ; Struck, Patrick (2022)
On the Related-Key Attack Security of Authenticated Encryption Schemes.
13th Conference on Security and Cryptography for Networks. Amalfi, Italy (12.-14.09.2022)
doi: 10.1007/978-3-031-14791-3_16
Conference or Workshop Item, Bibliographie

Abstract

Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT’03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was later extended to cover other primitives such as signatures and public key encryption schemes, but until now, a comprehensive formal security analysis of authenticated encryption schemes with associated data (AEAD) in the RKA setting has been missing. The main contribution of our work is to close this gap for the relevant class of nonce-based AEAD schemes.

To this end, we revisit the common approach to construct AEAD from encryption and message authentication. We extend the traditional security notion of AEAD to the RKA setting and consider an adversary that can tamper with the key Ke and Km of the underlying encryption and MAC, respectively. We study two security models. In our weak setting, we require that tampering will change both Ke and Km, while in our strong setting, tampering can be arbitrary, i.e., only one key might be affected. We then study the security of the standard composition methods by analysing the nonce-based AEAD schemes N1 (Encrypt-and-MAC), N2 (Encrypt-then-MAC), and N3 (MAC-then-Encrypt) due to Namprempre, Rogaway, and Shrimpton (EUROCRYPT’03). We show that these schemes are weakly RKA secure, while they can be broken under a strong related-key attack. Finally, based on the N3 construction, we give a novel AEAD scheme that achieves our stronger notion.

Item Type: Conference or Workshop Item
Erschienen: 2022
Creators: Faust, Sebastian ; Krämer, Juliane ; Orlt, Maximilian ; Struck, Patrick
Type of entry: Bibliographie
Title: On the Related-Key Attack Security of Authenticated Encryption Schemes
Language: English
Date: 5 September 2022
Publisher: Springer
Book Title: Security and Cryptography for Networks
Series: Lecture Notes in Computer Science
Series Volume: 13409
Event Title: 13th Conference on Security and Cryptography for Networks
Event Location: Amalfi, Italy
Event Dates: 12.-14.09.2022
DOI: 10.1007/978-3-031-14791-3_16
URL / URN: https://link.springer.com/chapter/10.1007/978-3-031-14791-3_...
Abstract:

Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT’03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was later extended to cover other primitives such as signatures and public key encryption schemes, but until now, a comprehensive formal security analysis of authenticated encryption schemes with associated data (AEAD) in the RKA setting has been missing. The main contribution of our work is to close this gap for the relevant class of nonce-based AEAD schemes.

To this end, we revisit the common approach to construct AEAD from encryption and message authentication. We extend the traditional security notion of AEAD to the RKA setting and consider an adversary that can tamper with the key Ke and Km of the underlying encryption and MAC, respectively. We study two security models. In our weak setting, we require that tampering will change both Ke and Km, while in our strong setting, tampering can be arbitrary, i.e., only one key might be affected. We then study the security of the standard composition methods by analysing the nonce-based AEAD schemes N1 (Encrypt-and-MAC), N2 (Encrypt-then-MAC), and N3 (MAC-then-Encrypt) due to Namprempre, Rogaway, and Shrimpton (EUROCRYPT’03). We show that these schemes are weakly RKA secure, while they can be broken under a strong related-key attack. Finally, based on the N3 construction, we give a novel AEAD scheme that achieves our stronger notion.

Uncontrolled Keywords: Primitives, P1, Solutions, S7
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Angewandte Kryptographie
20 Department of Computer Science > Cryptography and Complexity Theory
20 Department of Computer Science > QPC - Quantum and Physical attack resistant Cryptography
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Date Deposited: 21 Mar 2023 09:04
Last Modified: 17 Jul 2023 10:02
PPN: 50974771X
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details