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.

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.

DOI : 10.1051/ita/2012025
Classification : 94A60
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2012025/

[1] M. Bellare and P. Rogaway, Random oracles are practical : a paradigm for designing efficient protocols. Proc. 1st ACM conference on Computer and communications security (1993) 62-73.

[2] A. Menezes, P. Van Oorschot and S. Vanstone, Handbook of Applied Cryptography. CRC Press, USA (1996). | MR | Zbl

[3] B. Preneel, 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] A. Seshadri, A. Perrig, L. Van Doorn and P. Khosla, Swatt : Software-based attestation for embedded devices, in 2004. IEEE Symposium on Security and Privacy. Los Alamitos, CA (2004) 272.

[5] A. Seshadri, M. Luk, E. Shi, A. Perrig, L. Van Doorn and P. Khosla, Pioneer : verifying code integrity and enforcing untampered code execution on legacy systems. SIGOPS Oper. Syst. Rev. 39 (2005) 1-16.

[6] A. Seshadri, M. Luk, A. Perrig, L. Van Doorn and P. Khosla, Externally verifiable code execution. Commun. ACM 49 (2006) 45-49.

[7] D. Spinellis, Reflection as a Mechanism for Software Integrity Verification. ACM Trans. Infor. Syst. Secur. 3 (2000) 51-62.

[8] D.R. Stinson, Some Observations on the Theory of Cryptographic Hash Functions. Designs Codes Cryptogr. 38 (2006) 259-277. | MR | Zbl

[9] Y. Yang, X. Wang, S. Zhu and G. Cao, 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 :