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.
@article{ITA_2013__47_2_171_0,
author = {de S\'A, Vin\'\i cius G. P. and Boccardo, Davidson R. and Rust, Luiz Fernando and Machado, Raphael C. S.},
title = {A tight bound for exhaustive key search attacks against Message Authentication Codes},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {47},
year = {2013},
pages = {171-180},
doi = {10.1051/ita/2012025},
mrnumber = {3072316},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2013__47_2_171_0}
}
de SÁ, Vinícius G. P.; Boccardo, Davidson R.; Rust, Luiz Fernando; Machado, Raphael C. S. A tight bound for exhaustive key search attacks against Message Authentication Codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 171-180. doi : 10.1051/ita/2012025. http://gdmltest.u-ga.fr/item/ITA_2013__47_2_171_0/
[1] and , Random oracles are practical : a paradigm for designing efficient protocols. Proc. 1st ACM conference on Computer and communications security (1993) 62-73.
[2] , and , Handbook of Applied Cryptography. CRC Press, USA (1996). | MR 1412797 | Zbl 0868.94001
[3] , Hash functions and MAC algorithms based on block cyphers, in Cryptography and Coding, 6th IMA International Conference. Lect. Notes Comput. Sci. 1355 (1997) 270-282. | Zbl 1083.94520
[4] , , and , Swatt : Software-based attestation for embedded devices, in 2004. IEEE Symposium on Security and Privacy. Los Alamitos, CA (2004) 272.
[5] , , , , and , Pioneer : verifying code integrity and enforcing untampered code execution on legacy systems. SIGOPS Oper. Syst. Rev. 39 (2005) 1-16.
[6] , , , and , Externally verifiable code execution. Commun. ACM 49 (2006) 45-49.
[7] , Reflection as a Mechanism for Software Integrity Verification. ACM Trans. Infor. Syst. Secur. 3 (2000) 51-62.
[8] , Some Observations on the Theory of Cryptographic Hash Functions. Designs Codes Cryptogr. 38 (2006) 259-277. | MR 2197472 | Zbl 1146.94010
[9] , , and , Distributed software-based attestation for node compromise detection in sensor networks, in Proc. of the IEEE Symposium on Reliable Distributed Systems (2007) 219-228.