Paper 2011/015

Exponential attacks on 6-round Luby-Rackoff and on 5-round Lai-Massey

Jean-Philippe Aumasson

Abstract

The random oracle model and the ideal cipher model were proven equivalent after Coron et al. (CRYPTO 08) showed that six Feistel rounds are indifferentiable from an ideal cipher. This result, however, does not imply the inexistence of superpolynomial-time attacks outperforming generic (exponential-time) attacks. The finding of such attacks was left open by Coron et al., and is of utmost importance to evaluate the security of concrete fixed-parameters systems, as deployed in practice, for which the superpolynomial guarantee is an insufficient security argument. In addressing this issue, this paper proposes an exponential attack on six Feistel rounds, thus showing that at least seven rounds are necessary for optimal security guarantees. We then consider the Lai-Massey construction, as used in the block ciphers IDEA and FOX, for which we present an efficient attack on four rounds and an exponential attack on five. As a consequence, at least five Lai-Massey rounds are necessary to achieve indifferentiability in the general model.

Note: To be revised with respect to recent results (http://arxiv.org/abs/1011.1264) showing errors in the Coron et al. CRYPTO 08 proof.