International Journal of Research and Innovation in Applied Science (IJRIAS) | Volume VII, Issue VIII, July 2022 | ISSN 2454–6194
Pre-image attack of the MD5 hash function by proportional logic
Aboubakar Nkouankou*1,2, Fotso Clarice1,2, Wadoufey Abel2,3, René Ndoundam1
1Department of Computer Science, Faculty of Science, University of Yaoundé I, Cameroon
2National Institute of Cartography, Cameroon
3Department of Computer Science, Faculty of Science, University of Ngaoundéré, Cameroon
*Corresponding Author
Abstract: Hash functions are important cryptographic primitives that map arbitrary length messages to fixed length message summaries such that: it is easy to compute the digest given a message, while invert the hash process (for example, finding a message that maps a summary of a specific message) is difficult. An attack against a hash function is an algorithm that nevertheless manages to invert the hash process. Hash functions are used in authentication, digital signature, and key exchange systems. The most widely used hash function in many applications is the Message Digest-5 (MD5) algorithm. In this paper we study the current state of the technique of realization of the preimage attack of MD5 using solver SAT, we try improvements in the process of encoding and resolution. An important part of our work is to use the methods of propositional logic to model the attack problem and to determine which heuristic leads to the best resolution. Our most important result is a new encoding of the addition to several operands which considerably reduce the time required for the SAT solvers to find a solution to coding’s previously known.
Keywords: Hash function, MD5, Logic cryptanalysis, preimage, SAT – Solver.
I.INTRODUCTION
Ahash function is a function taking as input variable-size digital data and returning as output a character string of fixed and predetermined size. These functions are very useful especially in the field of databases. Indeed, they make it possible to handle very large structures while maintaining an acceptable speed with regard to the search for elements. In this article we only consider a subclass of hash functions: cryptographic hash functions (more particularly the MD5 function [10, 11]). This function, which is very different from the symmetric/asymmetric encryption functions [1], mainly performs two roles: data integrity and authentication .
The preimage search resistance of this function constitutes an important security criterion for a hashing algorithm. In other words, for a given hash Y, the attacker should not be able to find a vector X called preimage such that MD5(X) = Y (unless calculating the set of possible hashes, that is i.e. 2128). Using brute force, we can simply compute the hash value of all messages in turn until we find one that hashes to the correct value. However, this process will take longer than the lifetime of the universe. The challenge lies in effectively finding such a message. Several attack techniques [23] have emerged but have not been able to undermine the robustness of this function and its resistance to preimage is evaluated at a complexity of 2122.97 [8]. It is becoming urgent to change the approach, which is why we are turning to the logical approach, motivated by the performance and success of SAT solvers [0, 2, 12].