Topic: From Asymptotic Proofs to Network-Adversary Attacks against Secure Encryption Schemes
July 23, 2009
Dr Virgil Gligor
The asymptotic approach to proving security properties of encryption schemes assigns no vulnerability significance to the use of non-tight reductions. However, we introduce the notion of a "network adversary" and show that, while it is indistinguishable from an ordinary adversary in the asymptotic approach, it achieves decidedly non-negligible advantage in attacking provable security properties in practice; e.g., the "existential key recovery" and "multi-key hiding" properties of IND$-CPA secure symmetric-key schemes whenever these schemes are implemented with standard block ciphers. The network adversary amplifies its advantage quadratically by increasing the amount of commercially-available computational resources used only linearly, while the unit cost of the dominant resource (storage) continues to drop by 37–50% per year. We also show that symmetric encryption schemes whose security properties are obtained by non-tight reduction proofs cannot be implemented with certain standard block-cipher sizes (i.e., two-key 3DES) and retain those properties in network applications that use shared group keys. Finally, we show that "existential key recovery" and "(universal) key recovery" security properties are not equivalent. In practice this means that, while all standard encryption schemes (modes) are secure against "key recovery" attacks, some fail to provide the "existential key recovery" and "multi-key hiding" properties. We identify schemes that satisfy these properties, and suggest that similar analyses be conducted for other primitives (e.g., MACs and authenticated encryption schemes) whose properties are obtained by non-tight reductions.
Back