RAIRO-Theor. Inf. Appl.
Volume 47, Number 2, April-June 2013
|Page(s)||171 - 180|
|Published online||06 November 2012|
A tight bound for exhaustive key search attacks against Message Authentication Codes
Depto. de Ciência da Computação, Univ. Federal do Rio de
2 Inmetro, National Institute of Metrology, Quality and Technology, Brazil
firstname.lastname@example.org; email@example.com; firstname.lastname@example.org
Accepted: 3 September 2012
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.
Mathematics Subject Classification: 94A60
Key words: Cryptography / Message Authentication Code / asymptotic analysis
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.