Analyzing Multi-key Security Degradation
The multi-key, or multi-user, setting challenges cryptographic algorithms to maintain high levels of security when used with many different keys, by many different users. Its significance lies in the fact that in the real world, cryptography is rarely use
- PDF / 639,605 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 200 Views
3
imec-COSIC, KU Leuven, Leuven, Belgium [email protected] 2 Department of Computer Science, University of California, Davis, One Shields Ave, Davis, CA 95616, USA Digital Security Group, Radboud University, Nijmegen, The Netherlands [email protected] 4 CWI, Amsterdam, The Netherlands 5 Information Security Group, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK [email protected]
Abstract. The multi-key, or multi-user, setting challenges cryptographic algorithms to maintain high levels of security when used with many different keys, by many different users. Its significance lies in the fact that in the real world, cryptography is rarely used with a single key in isolation. A folklore result, proved by Bellare, Boldyreva, and Micali for public-key encryption in EUROCRYPT 2000, states that the success probability in attacking any one of many independently keyed algorithms can be bounded by the success probability of attacking a single instance of the algorithm, multiplied by the number of keys present. Although sufficient for settings in which not many keys are used, once cryptographic algorithms are used on an internet-wide scale, as is the case with TLS, the effect of multiplying by the number of keys can drastically erode security claims. We establish a sufficient condition on cryptographic schemes and security games under which multi-key degradation is avoided. As illustrative examples, we discuss how AES and GCM behave in the multikey setting, and prove that GCM, as a mode, does not have multi-key degradation. Our analysis allows limits on the amount of data that can be processed per key by GCM to be significantly increased. This leads directly to improved security for GCM as deployed in TLS on the Internet today. Keywords: Multi-key · Multi-user · Multi-oracle · AES · GCM · TLS · Weak keys
1
Introduction
A crucial aspect to analyzing cryptographic algorithms is modeling real-world settings. These models should not only accurately reflect the limits imposed by the environments and the security properties desired, but they should also c International Association for Cryptologic Research 2017 T. Takagi and T. Peyrin (Eds.): ASIACRYPT 2017, Part II, LNCS 10625, pp. 575–605, 2017. https://doi.org/10.1007/978-3-319-70697-9_20
576
A. Luykx et al.
produce meaningful ways to estimate how security deteriorates with use. In particular, in practice, algorithms are fixed, and hence so are key sizes, block sizes, groups, and various other parameters. Therefore it is important to be able to compute adversarial success probabilities relative to their resources as precisely as possible. For example, block ciphers have traditionally been analyzed in a setting where adversaries are given access to the encryption and decryption oracles keyed with a value chosen uniformly at random, unknown to the adversary. For many purposes using a block cipher which is secure in this model is sufficient, barring easy access to side channel information. Estimates for adversarial success are obtained by analyzing
Data Loading...
