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

de 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 -