Generic Internal State Recovery on Strengthened HMAC: n-bit Secure HMAC Requires Key in All Blocks
Summary :
HMAC is the most widely used hash based MAC scheme. Recently, several generic attacks have been presented against HMAC with a complexity between 2n/2 and 2n, where n is the output size of an underlying hash function. In this paper, we investigate the security of strengthened HMAC instantiated with a Merkle-Damgård hash function in which the key is used to process underlying compression functions. With such a modification, the attacker is unable to precompute the property of the compression function offline, and thus previous generic attacks are prevented. In this paper, we show that keying the compression function in all blocks is necessary to prevent a generic internal state recovery attack with a complexity less than 2n. In other words, only with a single keyless compression function, the internal state is recovered faster than 2n. To validate the claim, we present a generic attack against the strengthened HMAC instantiated with a Merkle-Damgård hash function in which only one block is keyless, thus pre-computable offline. Our attack uses the previous generic attack by Naito et al. as a base. We improve it so that the attack can be applied only with a single keyless compression function while the attack complexity remains unchanged from the previous work.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.1 pp.22-30
- Publication Date
- 2016/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.22
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yu SASAKI, Lei WANG, "Generic Internal State Recovery on Strengthened HMAC: n-bit Secure HMAC Requires Key in All Blocks" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 1, pp. 22-30, January 2016, doi: 10.1587/transfun.E99.A.22.
Abstract: HMAC is the most widely used hash based MAC scheme. Recently, several generic attacks have been presented against HMAC with a complexity between 2n/2 and 2n, where n is the output size of an underlying hash function. In this paper, we investigate the security of strengthened HMAC instantiated with a Merkle-Damgård hash function in which the key is used to process underlying compression functions. With such a modification, the attacker is unable to precompute the property of the compression function offline, and thus previous generic attacks are prevented. In this paper, we show that keying the compression function in all blocks is necessary to prevent a generic internal state recovery attack with a complexity less than 2n. In other words, only with a single keyless compression function, the internal state is recovered faster than 2n. To validate the claim, we present a generic attack against the strengthened HMAC instantiated with a Merkle-Damgård hash function in which only one block is keyless, thus pre-computable offline. Our attack uses the previous generic attack by Naito et al. as a base. We improve it so that the attack can be applied only with a single keyless compression function while the attack complexity remains unchanged from the previous work.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.22/_p
Copy
@ARTICLE{e99-a_1_22,
author={Yu SASAKI, Lei WANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generic Internal State Recovery on Strengthened HMAC: n-bit Secure HMAC Requires Key in All Blocks},
year={2016},
volume={E99-A},
number={1},
pages={22-30},
abstract={HMAC is the most widely used hash based MAC scheme. Recently, several generic attacks have been presented against HMAC with a complexity between 2n/2 and 2n, where n is the output size of an underlying hash function. In this paper, we investigate the security of strengthened HMAC instantiated with a Merkle-Damgård hash function in which the key is used to process underlying compression functions. With such a modification, the attacker is unable to precompute the property of the compression function offline, and thus previous generic attacks are prevented. In this paper, we show that keying the compression function in all blocks is necessary to prevent a generic internal state recovery attack with a complexity less than 2n. In other words, only with a single keyless compression function, the internal state is recovered faster than 2n. To validate the claim, we present a generic attack against the strengthened HMAC instantiated with a Merkle-Damgård hash function in which only one block is keyless, thus pre-computable offline. Our attack uses the previous generic attack by Naito et al. as a base. We improve it so that the attack can be applied only with a single keyless compression function while the attack complexity remains unchanged from the previous work.},
keywords={},
doi={10.1587/transfun.E99.A.22},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Generic Internal State Recovery on Strengthened HMAC: n-bit Secure HMAC Requires Key in All Blocks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 22
EP - 30
AU - Yu SASAKI
AU - Lei WANG
PY - 2016
DO - 10.1587/transfun.E99.A.22
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2016
AB - HMAC is the most widely used hash based MAC scheme. Recently, several generic attacks have been presented against HMAC with a complexity between 2n/2 and 2n, where n is the output size of an underlying hash function. In this paper, we investigate the security of strengthened HMAC instantiated with a Merkle-Damgård hash function in which the key is used to process underlying compression functions. With such a modification, the attacker is unable to precompute the property of the compression function offline, and thus previous generic attacks are prevented. In this paper, we show that keying the compression function in all blocks is necessary to prevent a generic internal state recovery attack with a complexity less than 2n. In other words, only with a single keyless compression function, the internal state is recovered faster than 2n. To validate the claim, we present a generic attack against the strengthened HMAC instantiated with a Merkle-Damgård hash function in which only one block is keyless, thus pre-computable offline. Our attack uses the previous generic attack by Naito et al. as a base. We improve it so that the attack can be applied only with a single keyless compression function while the attack complexity remains unchanged from the previous work.
ER -
English
