A TIGHT BOUND FOR EXHAUSTIVE KEY SEARCH ATTACKS AGAINST MESSAGE AUTHENTICATION CODES

作者：de Sa Vinicius G P^*; Boccardo Davidson R; Rust Luiz Fernando; Machado Raphael C S

来源：RAIRO - Theoretical Informatics and Applications, 2013, 47(2): 171-180.

DOI：10.1051/ita/2012025

• Cryptography
• Message Authentication Code
• asymptotic analysis

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.

• 出版日期2013-4