From Single-Key to Multi Sample Clauses

From Single-Key to Multi key The security models described earlier for block ciphers and modes gave the adversaries access to encryption and decryption oracles operating under a single key. However, in practice cryptographic algorithms are used by many different users, each potentially with many different keys. For example, AES-GCM is now widely used in TLS to protect web traffic via HTTPS,1 and is currently used by millions, or perhaps billions, of users daily. Hence it is important to understand what happens to security in the so-called multi-key setting, where adversaries are successful if they compromise the security of one out of many users, meaning their winning condition is a disjunction of single key winning conditions. For block ciphers the picture changes both quantitatively and qualitatively. Whereas in the single-key setting, the best attacks against AES do not improve with increased data complexity, in the multi-key setting they do, as depicted in Fig. 1a. As observed first by Xxxxx [14], and later refined as a time-memory-data trade-off by Xxxxxxxx, Xxxxxxxxxxxx, and Xxxxxx [15], one can take advantage of the fact that recovering a key out of a large group of keys is much easier than targeting one key. The same observation can be applied to any deterministic symmetric-key algorithm, as is done for MACs by Xxxxxxxxxx, Xxxxxxx, and Xxxxxx [21]. More generally, a folklore result guarantees that the attack success proba- bility increases by at most a factor μ when moving from the single-key to the multi-key setting with μ keys. In the case of key recovery against AES, the fact 1 The latest figures from the ICSI Certificate Notary (xxxxx://xxxxxx.xxxx.xxxxxxxx. edu/) suggest that more than 70% of all TLS connections use AES-GCM. · that this increase is necessary can be illustrated with an actual attack. For the mode GCM, a security bound involving a factor μ is easily established using a hybrid argument, meaning that the adversarial success probability is bounded by roughly μ σ2/2128. Bellare and Xxxxxxxx [11] were the first to formalize authenticated encryption in the multi-key setting and to analyze countermea- sures against multi-key attacks in the context of TLS 1.3. Their work simi- larly establishes bounds containing a μ-factor. This leads to a significant secu- rity degradation when there are many GCM instances present, as illustrated in Fig. 1b. Unfortunately, this is exactly the situation faced in large-scale deploy- ments of AES-GCM such as TLS. · Unlike block c...