Distinguishers on Double-Branch Compression Function and Applications to Round-Reduced RIPEMD-128 and RIPEMD-160

Yu SASAKI; Lei WANG

doi:10.1587/transfun.E97.A.177

Distinguishers on Double-Branch Compression Function and Applications to Round-Reduced RIPEMD-128 and RIPEMD-160

Yu SASAKI, Lei WANG

Full Text Views

0

Share
Cite this

Summary :

This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 2³⁵ and 2³⁶, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2¹⁰¹ and 2¹⁵⁸, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.1 pp.177-190

Publication Date: 2014/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.177

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Based Cryptography

Authors

Yu SASAKI
NTT Corporation
Lei WANG
Nanyang Technological University

Keyword

RIPEMD-128, RIPEMD-160, double-branch structure, 2-dimension sum, q-multi-second-order collision

Cite this

Copy

Yu SASAKI, Lei WANG, "Distinguishers on Double-Branch Compression Function and Applications to Round-Reduced RIPEMD-128 and RIPEMD-160" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 1, pp. 177-190, January 2014, doi: 10.1587/transfun.E97.A.177.
Abstract: This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 2³⁵ and 2³⁶, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2¹⁰¹ and 2¹⁵⁸, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.177/_p

Copy

@ARTICLE{e97-a_1_177,
author={Yu SASAKI, Lei WANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Distinguishers on Double-Branch Compression Function and Applications to Round-Reduced RIPEMD-128 and RIPEMD-160},
year={2014},
volume={E97-A},
number={1},
pages={177-190},
abstract={This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 2³⁵ and 2³⁶, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2¹⁰¹ and 2¹⁵⁸, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.},
keywords={},
doi={10.1587/transfun.E97.A.177},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Distinguishers on Double-Branch Compression Function and Applications to Round-Reduced RIPEMD-128 and RIPEMD-160
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 177
EP - 190
AU - Yu SASAKI
AU - Lei WANG
PY - 2014
DO - 10.1587/transfun.E97.A.177
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2014
AB - This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 2³⁵ and 2³⁶, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2¹⁰¹ and 2¹⁵⁸, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.
ER -