## 3 Results
### The MD5
Depending on the round number, we have the following:  
Figure 2: Dividing MD5 hashing to “simple” problems. The circles denote operations and rectangles indicate integer numbers. 1. \(F_{k}(B,C,D)=F(B,C,D)=(B\wedge C)\vee(!B\wedge D)\quad(k\in 1\dots 16)\);
2. \(F_{k}(B,C,D)=G(B,C,D)=(B\wedge D)\vee(C\wedge!D)\quad(k\in 17\dots 32)\);
3. \(F_{k}(B,C,D)=H(B,C,D)=B\oplus C\oplus D\quad(k\in 33\dots 48)\);
4. \(F_{k}(B,C,D)=I(B,C,D)=C\oplus(B\lor!D)\quad(k\in 49\dots 64)\). The final hash value of the MD5 is compound of \(A_{64},B_{64},C_{64},D_{64}\) blocks. Comparing with the notation from the beginning \((H(x)=y),x\) is divided into \(M_{k}\) blocks, \(y\) is the compound of \(A_{64},B_{64},C_{64},D_{64}\) blocks. More details can be found in [19]. In the Table 2, we specified all nonlinear functions used in MD5. Denote by \(L_{k}(B_{k-1},C_{k-1},D_{k-1},FF_{k},\alpha_{k})=0\) the linear system of equations for nonlinear operations in the \(k\)-th round. This system consists of the linear equation for each bit of \(B_{k-1},C_{k-1},D_{k-1}\) and is chosen from Table 2 in accordance with the hash function round. Here, \(FF_{k}\) is the output number of \(F_{k}(B_{k-1},C_{k-1},D_{k-1})\), and \(\alpha_{k}\) is a vector variable which denotes all ancilla bits. For example, let us consider the 33-rd round and let all the numbers in the blocks be 2 bit for simplicity's sake. In the 33-rd round, \(H(B,C,D)\) is used from Table 2. Then, the linear system \(L_{33}(B_{32},C_{32},D_{32},FF_{33},\alpha_{33})=0\) becomes  
\[L_{33}(B_{32},C_{32},D_{32},FF_{33},\alpha_{33})=0\coloneqq \begin{cases}B_{32, 0}+C_{32,0}+D_{32,0}-FF_{33,0}-2\alpha_{33,0}=0\\ B_{32,1}+C_{32,1}+D_{32,1}-F_{33,1}-2\alpha_{33,1}=0\end{cases}  \tag{40}\]  
For the addition modulo, we use another notation, \(\Sigma(A,B,\dots,D,R,\xi)\), where \(A,B,\dots,D\) are input numbers, \(R\) is the output one and \(\xi\) is a vector variable of all ancilla bits as in the nonlinear function case. Let us write an explicit formula for \(\Sigma\) in the simple case. For example, consider two 2-bit summands, then \(\Sigma\) is as follows:  
\[\Sigma(A,B,R,\xi)=0\coloneqq \begin{cases}A_{0}+B_{0}=R_{0}+2\xi_{0}\\ \xi_{0}+A_{1}+B_{1}=R_{1}+2\xi_{1}\end{cases}  \tag{41}\]  
Using the MD5 round definition and Figure 2, we can write the linear system for one round. Consider the \(k\)-th round:  
\[ \begin{cases}&L_{k}(B_{k-1},C_{k-1},D_{k-1},FF_{k},\alpha_{k})=0\\ &\Sigma\left(FF_{k},A_{k-1},M_{\mu(k)},K_{k},FM_{k},\xi_{k,1}\right)=0\\ &\Sigma(FM_{k}<<s_{k},B_{k-1},B_{k},\xi_{k,2})=0\\ &A_{k}=D_{k-1},C_{k}=B_{k-1},D_{k}=C_{k-1}\end{cases}  \tag{42}\]Combining all of Equation (42), we obtain the MILP for the whole MD5:  
\[\left\{ \begin{array}{l}L_{1}(B_{0},C_{0},D_{0},FF_{1},\alpha_{1})=0\\ \Sigma\left(FF_{1},A_{0},M_{\mu(1)},K_{1},FM_{1},\xi_{1,1}\right)=0\\ \Sigma(FM_{1}<<<s_{1},B_{0},B_{1},\xi_{1,2})=0\\ A_{1}=D_{0},C_{1}=B_{0},D_{1}=C_{0}\\ \ldots\\ L_{k}(B_{k-1},C_{k-1},D_{k-1},FF_{k},\alpha_{k})=0\\ \Sigma\left(FF_{k},A_{k-1},M_{\mu(k)},K_{k},FM_{k},\xi_{k,1}\right)=0\\ \Sigma(FM_{k}<<<s_{k},B_{k-1},B_{k},\xi_{k,2})=0\\ A_{k}=D_{k-1},C_{k}=B_{k-1},D_{k}=C_{k-1}\\ \ldots\\ L_{64}(B_{63},C_{63},D_{63},FF_{64},\alpha_{64})=0\\ \Sigma\left(FF_{64},A_{0},M_{\mu(64)},K_{64},FM_{64},\xi_{64,1}\right)=0\\ \Sigma(FM_{64}<<<<s_{64},B_{63},B_{64},\xi_{64,2})=0\\ A_{64}=D_{63},C_{64}=B_{63},D_{64}=C_{63}\end{array} \right. \tag{43}\]  
with the final hash value \(A_{64},B_{64},C_{64},D_{64}\). Now, we calculate the number of binary variables in the MILP of the MD5 hash function. In the zeroth round, we have \(A_{0},B_{0},C_{0},D_{0}\) and all \(M_{i}(i\in 0\ldots 16)\). They are \((4+16)\cdot 32=640\) bits. Each \(L_{k}\) adds \(F_{k}\) and \(\alpha_{k}\) variables, and \(F_{k}\) in each round consists of 32 bits, whereas the number of bits in \(\alpha_{k}\) depends on a round. From 1 to 32 rounds, \(\alpha_{k}\) has \(3\cdot 32=96\) bits; from 33 to 48, \(\alpha_{k}\) has 32 bits; and from 49 to 64, \(\alpha_{k}\) has 64 bits.