## 3 Results
### The MD5  
In this subsection, we consider converting a pre-image attack on hash functions into an optimization problem. The hash functions, \(H(x)\), possesses two features:  
1. For any \(x\) number, there is easy to compute \(H(x)\). 2. For any \(y\) number, there is hard to find \(x\) such that \(H(x)=y\). The pre-image attack tries to break the second feature. There is a paper in which researchers tried to commit this attack [15]. They used local collision, partial fixing and other classical cryptography techniques. The final complexity in the mentioned paper is \(2^{123.4}\). Unfortunately, this is not practical at all. Another approach based on the SAT for the MD-family hash functions was considered in Refs. [16; 17]. In these papers, they used an idea similar to what we use in this work, but they converted the pre-image attack to the SAT problem as we convert it into the MILP problems. In Ref. [16], they successfully committed an attack on the MD4 with 39 rounds under [PERSON]'s conditions [18]. Here, we develop an efficient technique to obtain the solution. Namely, we divide the MD5 hash function into simple operations, which we can easily convert to the MILP or QUBO (Figure 2). Each circle depicts an operation; the white rectangle is a 32 bit number. At a first step, we note that all round functions make the same operations, except a nonlinear function. Therefore, the MILP or QUBO will appear in the similar way. Taking a closer look at the round function, we notice that it consists of the following types of operations: the nonlinear function, addition modulo and shift. Nonlinear functions are used in the MD5 to act on 32 bit numbers separately, and thus, we can find the MILP/QUBO representation for each bit separately. Table 2 gives all nonlinear functions in the MD5 and the respective linear equations for them. The addition modulo is considered in Section 3.1. For implementing a shift operation (left or right bit rotation), one should just rename the corresponding variables. Let us consider the linear system \(\vec{\Phi}(\vec{x},\vec{y})=\vec{b}\), where \(\vec{x}\) and \(\vec{y}\) are vectors of variables, and \(\vec{b}\) is a fixed vector of parameters. We need to add a shift operation to \(\vec{x}\) and to leave \(\vec{y}\) unchanged. We denote by \(\vec{x}\,^{\prime}\) the \"shifted\" \(\vec{x}\). By definition, \(\vec{x}=(x_{1},x_{2},\ldots,x_{N})\), then \(\vec{x}\,^{\prime}=(x_{s+1},x_{s+2},\ldots,x_{N},x_{1},x_{2},\ldots,x_{s})\) in the case of right rotation \((x^{\prime}=x>>s)\) and \(\vec{x}\,^{\prime}=(x_{N-s},x_{N-s+1},\ldots,x_{N},x_{1},x_{2},\ldots,x_{N-s-1})\) in the case of left rotation \((x^{\prime}=x<<s)\). So, the new linear system (after shift) is just the system of simple equations (\"reindexing\") \(\vec{\Phi}^{\prime}(\vec{x},\vec{y})=\vec{b}\Leftrightarrow\vec{\Phi}(\vec{ x}\,^{\prime},\vec{y})=\vec{b}\). After converting all types of operations in the MILP, we are ready to build it for the whole MD5. Before doing that though, let us shortly revise the definition of MD5. The hash function transforms the 512 bit input message into the hash value. The given message divides into 16 pieces of 32 bit numbers, \(M_{i}(i\in 0\ldots 15)\). In addition, the MD5 has four 32-bit constants, which we define as \(A_{0},B_{0},C_{0},D_{0}\), respectively. The calculating of the hash value consists of rounds. The MD5 has 64 rounds. In each round, we calculate some intermediate hash value as follows:  
\[ \begin{split} A_{k}&=D_{k-1},B_{k}=\Big{(}F_{k}(B_{k- 1},C_{k-1},D_{k-1})+A_{k-1}+M_{\mu(k)}+K_{k}\Big{)}<<s_{k}+B_{k-1},\\ C_{k}&=B_{k-1},D_{k}=C_{k-1}\end{split}  \tag{39}\]  
where \(k\in 1\ldots 64\) is the number of rounds, \(K_{k}\) and \(s_{k}\) are given constant numbers, and \(\mu(k)\) are as follows:  
1. \(\mu(k)=k-1\quad(k\in 1\ldots 16)\);
2. \(\mu(k)=5k-4(\text{mod }16)\quad(k\in 17\ldots 32)\);
3. \(\mu(k)=3k+2(\text{mod }16)\quad(k\in 33\ldots 48)\);
4. \(\mu(k)=7k-7(\text{mod }16)\quad(k\in 49\ldots 64)\). Here \(F_{k}\) is one of the nonlinear round functions.