On the existence of related-key oracles in cryptosystems based on block ciphers

The notion of a related-key attack (RKA) was formally introduced by Biham in 1993. It is essentially more of an attack model rather than a specific type of attack in that it considers what sort of oracles are available to the attacker. In this case, the attacker has access to related-key (RK) oracles, i.e. he is able to have encryptions performed on plaintexts of his choice, keyed by two or more unknown but related keys. The feasibility of this attack model is at times debated mainly because the assumption that an attacker would have access to RK oracles may be too strong to really exist in practice. Hence, attacks on block ciphers in this RKA model have commonly not been regarded on the same level of significance of those not requiring RK oracles. A good example is the AES. It is generally accepted that the best known attack is a non-RKA by Gilbert and Minier in 2000, although it applies to less rounds compared to the best known RKA on AES by Biham et al. that applies to more rounds. It is our aim in this paper to show how RK oracles exist in various block cipher based cryptosystems. The gist is to think outside the box, i.e. to note that a block cipher is often an underlying primitive within a larger cryptographic construct, thus it is only natural to evaluate the block cipher security in this setting and not as a standalone primitive. In doing so, we formally introduce the notion of related-key multiplicative differentials, and related-key compositionally differentials. We also consider the existence of RK oracles in PGV-type hash functions, message authentication codes, recent authenticated encryption modes and cases of key-exchange protocols not previously mentioned in literature.