The Security of “One-Block-to-Many” Modes of Operation

In this paper, we investigate the security, in the Luby-Rackoff secu-rity paradigm, of blockcipher modes of operation allowing to expand a one-block input into a longer t-block output under the control of a secret key K. Such “one-block-to-many ” modes of operation are of frequent use in cryptology. They can be used for stream cipher encryption purposes, and for authentication and key distribution purposes in contexts such as mobile communications. We show that although the expansion functions resulting from modes of operation of blockciphers such as the counter mode or the output feedback mode are not pseudorandom, slight modi-fications of these two modes provide pseudorandom expansion functions. The main result of this paper is a detailed proof, in the Luby-Rackoff se-curity model, that the expansion function used in the construction of the third generation mobile (UMTS) example authentication and key agree-ment algorithm MILENAGE is pseudorandom. 1