Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-12T08:59:01.487Z Has data issue: false hasContentIssue false
  • English
  • Français

A tight bound for exhaustive key search attacks against MessageAuthentication Codes

Published online by Cambridge University Press:  06 November 2012

Vinícius G.P. de SÁ,
Davidson R. Boccardo,
Luiz Fernando Rust and
Raphael C.S. Machado
Vinícius G.P. de SÁ
Affiliation:
Depto. de Ciência da Computação, Univ. Federal do Rio de Janeiro, Brazil. vigusmao@dcc.ufrj.br
Davidson R. Boccardo
Affiliation:
Inmetro, National Institute of Metrology, Quality and Technology, Brazil; drboccardo@inmetro.gov.br; lfrust@inmetro.gov.br; rcmachado@inmetro.gov.br
Luiz Fernando Rust
Affiliation:
Inmetro, National Institute of Metrology, Quality and Technology, Brazil; drboccardo@inmetro.gov.br; lfrust@inmetro.gov.br; rcmachado@inmetro.gov.br
Raphael C.S. Machado
Affiliation:
Depto. de Ciência da Computação, Univ. Federal do Rio de Janeiro, Brazil. vigusmao@dcc.ufrj.brInmetro, National Institute of Metrology, Quality and Technology, Brazil; drboccardo@inmetro.gov.br; lfrust@inmetro.gov.br; rcmachado@inmetro.gov.br

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A Message Authentication Code (MAC) is a function that takes a message and a key asparameters and outputs an authentication of the message. MAC are used to guarantee thelegitimacy of messages exchanged through a network, since generating a correctauthentication requires the knowledge of the key defined secretly by trusted parties.However, an attacker with access to a sufficiently large number of message/authenticationpairs may use a brute force algorithm to infer the secret key: from a set containinginitially all possible key candidates, subsequently remove those that yield an incorrectauthentication, proceeding this way for each intercepted message/authentication pair untila single key remains. In this paper, we determine an exact formula for the expected numberof message/authentication pairs that must be used before such form of attack issuccessful, along with an asymptotical bound that is both simple and tight. We conclude byillustrating a modern application where this bound comes in handy, namely the estimationof security levels in reflection-based verification of software integrity.

Keywords

CryptographyMessage Authentication Codeasymptotic analysis

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 47 , Issue 2 , April 2013, pp. 171 - 180
Copyright
© EDP Sciences 2012

References

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.
A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography. CRC Press, USA (1996).
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. CrossRef
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.
Seshadri, A., Luk, M., Shi, E., Perrig, A., van Doorn, L. and Khosla, P., Pioneer : verifying code integrity and enforcing untampered code execution on legacy systems. SIGOPS Oper. Syst. Rev. 39 (2005) 1–16. Google Scholar
Seshadri, A., Luk, M., Perrig, A., van Doorn, L. and Khosla, P., Externally verifiable code execution. Commun. ACM 49 (2006) 45–49. Google Scholar
Spinellis, D., Reflection as a Mechanism for Software Integrity Verification. ACM Trans. Infor. Syst. Secur. 3 (2000) 51–62. Google Scholar
Stinson, D.R., Some Observations on the Theory of Cryptographic Hash Functions. Designs Codes Cryptogr. 38 (2006) 259–277. Google Scholar
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.