Geodesic
Inverting 29-step MD5 compression function via SAT
Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 36-40

Voir la notice de l'article provenant de la source Math-Net.Ru

The cryptographic hash function MD5 was proposed in 1992. Its key component is a 64-step compression function. The compression function is still preimage resistant, that is why its step-reduced versions are usually investigated in this context. In 2007, the 26-step version of the MD5 compression function was inverted via SAT. In 2012, 27- and 28-step versions were inverted via SAT as well. In the paper, an approach to forming 32 intermediate inversion problems between two subsequent steps of the MD5 compression function is proposed. SAT encodings of such problems were constructed between 28 and 29 steps. Several simplest problems were leveraged for tuning a modern SAT solver. As a result, the 29-step version of the MD5 compression function was inverted for the first time.
Keywords: cryptographic hash function, logical cryptanalysis, SAT.
Mots-clés : MD5, algebraic cryptanalysis 
@article{PDMA_2023_16_a9,
     author = {O. S. Zaikin},
     title = {Inverting 29-step {MD5} compression function via {SAT}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {36--40},
     publisher = {mathdoc},
     number = {16},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2023_16_a9/}
}
TY  - JOUR
AU  - O. S. Zaikin
TI  - Inverting 29-step MD5 compression function via SAT
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2023
SP  - 36
EP  - 40
IS  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2023_16_a9/
LA  - ru
ID  - PDMA_2023_16_a9
ER  - 
%0 Journal Article
%A O. S. Zaikin
%T Inverting 29-step MD5 compression function via SAT
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2023
%P 36-40
%N 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2023_16_a9/
%G ru
%F PDMA_2023_16_a9
O. S. Zaikin. Inverting 29-step MD5 compression function via SAT. Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 36-40. http://geodesic.mathdoc.fr/item/PDMA_2023_16_a9/