# A tight bound for exhaustive key search attacks against Message Authentication Codes

Vinícius G. P. de SÁ; Davidson R. Boccardo; Luiz Fernando Rust; Raphael C. S. Machado

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

- Volume: 47, Issue: 2, page 171-180
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topde SÁ, Vinícius G. P., et al. "A tight bound for exhaustive key search attacks against Message Authentication Codes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.2 (2013): 171-180. <http://eudml.org/doc/273064>.

@article{deSÁ2013,

abstract = {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.},

author = {de SÁ, Vinícius G. P., Boccardo, Davidson R., Rust, Luiz Fernando, Machado, Raphael C. S.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {cryptography; message authentication code; asymptotic analysis},

language = {eng},

number = {2},

pages = {171-180},

publisher = {EDP-Sciences},

title = {A tight bound for exhaustive key search attacks against Message Authentication Codes},

url = {http://eudml.org/doc/273064},

volume = {47},

year = {2013},

}

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

PB - EDP-Sciences

VL - 47

IS - 2

SP - 171

EP - 180

AB - 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.

LA - eng

KW - cryptography; message authentication code; asymptotic analysis

UR - http://eudml.org/doc/273064

ER -

## References

top- [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). Zbl0868.94001MR1412797
- [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. Zbl1083.94520
- [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. ACM49 (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. Zbl1146.94010MR2197472
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.