On the Full MAC Security of a Double-Piped Mode of Operation |
|
Kan Yasuda |
|
|
This paper shows a new mode of operation which, by iterating a compression function,
yields a highly secure message authentication code. Using the new construction, we are
able to exceed substantially the security limit due to the birthday paradox, which was
imposed on previous message authentication codes. The paper makes a significant
contribution from both practical and academic perspectives.
A message authentication code, widely used in the Internet and other IT applications, is asymmetric-key technique to protect integrity and authenticity of data. Naturally weexpect a high level of security from a message authentication code. However, previous constructions of a message authentication code suffered from security degradation due to the birthday paradox. Here, by the “security degradation” we mean, for example, that the security of a message authentication code becomes (not 128-bit but) only 64-bit even if the construction iterates a compression function having a 128-bit output size.
A compression function is in a way a unit, or a “small” function, that has fixed input and output sizes. We can process virtually all data having arbitrary lengths by iterating a compression function. A mode of operation precisely specifies how to iterate a compression function.
In 1999 An and Bellare made an attempt to prove the “original” security (i.e.unforgeability) of a message authentication code based on the unforgeability of the underlying compression function. Though ideal from the theoretical viewpoint, this security framework did not attract many following researches, because it was rather difficult to carry out proof analyses in the framework as compared to other methods (such as those assuming pseudo-randomness). In particular, it was considered to be hard to exceed the birthday paradox limit in the security framework.
The paper succeeds in proving security beyond the birthday paradox limit by first modifying the so-called double-pipe mode of operation and then applying to the modified construction a novel relation between the birthday paradox and unforgeability which the paper discovers. Therefore, now we can construct a 128-bit secure (in the sense of unforgeability) message authentication code using an unforgeable compression function having a 128-bit output size. Thus, we think highly of the paper in terms of its practical and theoretical contents.
