Quantum Cryptanalysis of OTR and OPP: Attacks on Confidentiality, and Key-Recovery

In this paper, we analyze the security of authenticated encryption modes OTR (Minematsu, Eurocrypt 2014) and OPP (Granger et al., Eurocrypt 2016) in a setting where an adversary is allowed to make encryption queries in quantum superposition. Starting with OTR – or more technically, AES-OTR, a third-round CAESAR candidate – we extend prior quantum attacks on the mode’s unforgeability in the literature to provide the first attacks breaking confidentiality, i.e., IND-qCPA security, of AES-OTR in different settings depending on how the associated data is processed. On a technical level, one of our IND-qCPA attacks involves querying the quantum encryption oracle on a superposition of data with unequal length; to the best of our knowledge, such an attack has never been modelled before in the (post-)quantum cryptographic literature, and we hence believe our technique is of independent interest. Coming to OPP, we present the first key-recovery attack against the scheme which uses only a single quantum encryption query.