A tight bound for exhaustive key search attacks against Message Authentication Codes

¹ Depto. de Ciência da Computação, Univ. Federal do Rio de Janeiro, Brazil
vigusmao@dcc.ufrj.br
² Inmetro, National Institute of Metrology, Quality and Technology, Brazil
drboccardo@inmetro.gov.br; lfrust@inmetro.gov.br; rcmachado@inmetro.gov.br

Received: 22 March 2012
Accepted: 3 September 2012

Abstract

A Message Authentication Code (MAC) is a function that takes a message and a key as parameters and outputs an authentication of the message. MAC are used to guarantee the legitimacy of messages exchanged through a network, since generating a correct authentication requires the knowledge of the key defined secretly by trusted parties. However, an attacker with access to a sufficiently large number of message/authentication pairs may use a brute force algorithm to infer the secret key: from a set containing initially all possible key candidates, subsequently remove those that yield an incorrect authentication, proceeding this way for each intercepted message/authentication pair until a single key remains. In this paper, we determine an exact formula for the expected number of message/authentication pairs that must be used before such form of attack is successful, along with an asymptotical bound that is both simple and tight. We conclude by illustrating a modern application where this bound comes in handy, namely the estimation of security levels in reflection-based verification of software integrity.