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.
Mots-clés : cryptography, message authentication code, asymptotic analysis
@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},
pages = {171--180},
publisher = {EDP-Sciences},
volume = {47},
number = {2},
year = {2013},
doi = {10.1051/ita/2012025},
mrnumber = {3072316},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2012025/}
}
TY - JOUR AU - de SÁ, Vinícius G. P. AU - Boccardo, Davidson R. AU - Rust, Luiz Fernando AU - Machado, Raphael C. S. TI - A tight bound for exhaustive key search attacks against Message Authentication Codes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 171 EP - 180 VL - 47 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2012025/ DO - 10.1051/ita/2012025 LA - en ID - ITA_2013__47_2_171_0 ER -
%0 Journal Article %A de SÁ, Vinícius G. P. %A Boccardo, Davidson R. %A Rust, Luiz Fernando %A Machado, Raphael C. S. %T A tight bound for exhaustive key search attacks against Message Authentication Codes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 171-180 %V 47 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2012025/ %R 10.1051/ita/2012025 %G en %F 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) no. 2, pp. 171-180. doi : 10.1051/ita/2012025. http://www.numdam.org/articles/10.1051/ita/2012025/
[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 | Zbl
[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
[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 | Zbl
[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.
Cité par Sources :
