Mitigate TCCR hash security drop by rekeying AES #341
Description
The TCCR hash, which we currently use for garbling and which is based on a fixed-key AES cipher, is known to suffer a security degradation that grows with the number of AND gates garbled. Specifically, its effective security level decreases by approximately log₂ (n) bits when n AND gates are garbled under the same key.
The attack requires the evaluator (acting as the adversary) to precompute a look-up table for a particular TCCR instantiation with a specific AES key.
To mitigate this, I propose periodic rekeying of the AES cipher to limit the security loss. For example, if we rekey after every one million (≈ 2²⁰) garbled AND gates, the effective security level would be approximately 128 − 20 = 108 bits, which should be sufficient for many practical applications.
The attack is given in https://eprint.iacr.org/2019/1168 Figure 4:
