lemma

Let $m_1,m_2$ be the 96-byte messages $\begin{aligned} m_1&=(p_1,0,0,0\mid p_2,0,0,0\mid 0,0,0,0),\\ m_2&=(p_1+2^{8},0,0,0\mid p_2-2^{9}-2^{24},0,0,0\mid 2^{8},0,0,0), \end{aligned}$ (four little-endian 64-bit lanes per packet, arithmetic mod $2^{64}$), with $p_1=-I_{00}$ and $p_2=c_2-I_{00}$, $c_2=\mathtt{b3000100}$. Let $K=(K_0,K_1,K_2,K_3)$ be a HighwayHash key with $\operatorname{hi}(K_0)=\mathtt{dbe6d5d5}=\operatorname{hi}(I_{00})$ (condition (1)), $\operatorname{lo}(K_0)$ and $K_1$ uniform on $\{0,1\}^{96}$ and $K_2,K_3$ arbitrary. Let $\mathcal C$ be the event that the full 1024-bit HighwayHash state after the three packets of $m_1$ equals the state after the three packets of $m_2$ (so every suffix and every output width collides). Then $\Pr[\mathcal C]\;\ge\;\Pr[E_2]\;=\;\frac{235\cdot 239}{2^{40}}\;=\;\frac{56165}{2^{40}}\;=\;2^{-24.2226\ldots},$ where $E_2$ is the event $\operatorname{lo}(v_1[0])-\operatorname{hi}(v_0[0])\equiv 2^{8}\pmod{2^{32}}$ evaluated at the lane-0 $\mathit{mul}_0$ multiplication of packet 2 (the two operands of that multiplication). Consequently, over a uniformly random 256-bit key, $\Pr[\mathcal C]\;\ge\;2^{-32}\cdot\frac{235\cdot 239}{2^{40}}\;=\;\frac{56165}{2^{72}}\;=\;2^{-56.2226\ldots},$ and $\Pr[E_2\mid(1)]$ exceeds the value $2^{-32}$ of a uniformly distributed 32-bit difference by the exact factor $56165/256=219.4=2^{7.78}$.

Proof. 0. The round function on lanes 0,1. $\mathrm{Update}(p)$ first applies, lane by lane, $v_1\mathrel{+}=\mathit{mul}_0+p$; $\mathit{mul}_0\mathrel{\oplus}=\operatorname{lo}(v_1)\cdot\operatorname{hi}(v_0)$; $v_0\mathrel{+}=\mathit{mul}_1$; $\mathit{mul}_1\mathrel{\oplus}=\operatorname{lo}(v_0)\cdot\operatorname{hi}(v_1)$, and then, writing $A=v_1[0]$, $B=v_1[1]$, $v_0[0]\mathrel{+}=Z_0(A,B)$, $v_0[1]\mathrel{+}=Z_1(A,B)$, and afterwards with $A=v_0[0]$, $B=v_0[1]$ (the updated values) $v_1[0]\mathrel{+}=Z_0(A,B)$, $v_1[1]\mathrel{+}=Z_1(A,B)$, where (bytes $0,\dots,7$) $\begin{aligned} Z_0(A,B)&=(A[3],B[4],A[2],A[5],B[6],A[1],B[7],A[0]),\\ Z_1(A,B)&=(B[3],A[4],B[2],B[5],B[1],A[6],B[0],A[7]). \end{aligned}$ Lanes 2,3 are processed identically among themselves and never touch lanes 0,1 before the finalization permutation, so $K_2,K_3$ are irrelevant for $\mathcal C$ (they enter both states identically).

1. The state after packet 1 of $m_1$. Write $k=\operatorname{lo}(K_0)$, $a=\mathtt{fe4cce2f}\oplus k$, $b=\mathtt{3bd39e10}\oplus k$ (so $b=a\oplus\mathtt{c59f503f}$; in particular $b[1]=a[1]\oplus\mathtt{50}$, $b[0]=a[0]\oplus\mathtt{3f}$). Reset gives $v_0[0]=(0,a)$, $v_1[0]=(b,\mathtt{10e82046})$, $\mathit{mul}_0=\mathit{init}_0$, $\mathit{mul}_1=\mathit{init}_1$. In packet 1, $v_1[0]\mathrel{+}=I_{00}+p_1=0$; the product $\operatorname{lo}(v_1[0])\cdot\operatorname{hi}(v_0[0])$ is $0$ because $\operatorname{hi}(v_0[0])=0$ under condition (1), so $\mathit{mul}_0[0]=I_{00}$ is unchanged; then $V_0:=v_0[0]=a+I_{10}$ and $\mathit{mul}_1[0]=I_{10}\oplus\operatorname{lo}(V_0)\cdot b$. In lane 1, $W_1:=v_1[1]=(I_{11}\oplus\operatorname{rot}_{32}(K_1))+I_{01}$ and $W_0:=v_0[1]=(I_{01}\oplus K_1)+I_{11}$ (the lane-1 multipliers do not matter below). The two zipper steps then give $\begin{aligned} U_0&:=v_0[0]=V_0+Z_0\big((b,\mathtt{10e82046}),W_1\big),\\ U_1&:=v_0[1]=W_0+Z_1\big((b,\mathtt{10e82046}),W_1\big),\\ T&:=v_1[0]=(b,\mathtt{10e82046})+Z_0(U_0,U_1). \end{aligned}$ Here $Z_0((b,\mathtt{10e82046}),W_1)=(\mathtt{10},W_1[4],\mathtt{e8},b[1],W_1[6],\mathtt{20},W_1[7],\mathtt{46})$. Put $Z_c:=b[1]2^{24}+\mathtt{e8}\cdot2^{16}+W_1[4]2^{8}+\mathtt{10}$ (its low half) and $\gamma:=\Big\lfloor\frac{a+\mathtt{cb0ef593}+Z_c}{2^{32}}\Big\rfloor\in\{0,1,2\}, \qquad \operatorname{lo}(U_0)=(a+\mathtt{cb0ef593}+Z_c)\bmod 2^{32}.$ Then $h:=\operatorname{hi}(U_0)=\mathtt{81d3be10}+W_1[7]\,2^{16}+W_1[6]+\gamma \pmod{2^{32}},$ so $h_0=(\mathtt{10}+W_1[6]+\gamma)\bmod 256$ with carry $e_0=[\mathtt{10}+W_1[6]+\gamma\ge256]$, $h_1=\mathtt{be}+e_0\in\{\mathtt{be},\mathtt{bf}\}$, $h_2=(\mathtt{d3}+W_1[7])\bmod256$ with carry $e_2$, and $h_3=\mathtt{81}+e_2\in\{\mathtt{81},\mathtt{82}\}$. In particular $U_0[5]=h_1\ne\mathtt{ff},\qquad h<2^{32}-2^{8}.$ Finally $\operatorname{lo}(T)=\mathtt{10e82046}+Q\pmod{2^{32}}$ with $Q:=(h_1,U_0[2],U_1[4],U_0[3])$, since $\operatorname{lo}(Z_0(U_0,U_1))=(U_0[5],U_0[2],U_1[4],U_0[3])$.

2. The difference trail: $E_2\Rightarrow\mathcal C$. Track $m_2$ against $m_1$; all differences are modular in $2^{64}$. Packet 1. $v_1[0]$ differs by $+2^{8}$; its low half is the constant $\mathtt{10e82046}$, so the difference sits in byte 1 ($\mathtt{20}\to\mathtt{21}$) and $\operatorname{hi}(v_1[0])=b$ is unchanged; both multiplications of lane 0 use only $\operatorname{hi}(v_0[0])=0$, $\operatorname{lo}(V_0)$ and $\operatorname{hi}(v_1[0])$, so all multipliers are equal. $Z_0(v_1[0],W_1)$ has byte 5 $=v_1[0][1]$, hence differs by exactly $2^{40}$, while $Z_1$ reads bytes $4,6,7$ of $v_1[0]$ and is unchanged: $v_0[0]$ differs by $2^{40}$, $v_0[1]$ is equal. By [eq:hbounds], $U_0[5]=h_1\le\mathtt{bf}$, so $U_0+2^{40}$ differs from $U_0$ in byte 5 only ($h_1\to h_1+1$); therefore $Z_0(U_0,U_1)$ (byte 3 $=U_0[5]$) differs by exactly $2^{24}$ and $Z_1(U_0,U_1)$ (bytes $4,6,7$ of $U_0$) is unchanged. After packet 1: $v_0[0]$ differs by $2^{40}$, $v_1[0]$ by $2^{8}+2^{24}$, everything else is equal. Packet 2. $v_1[0]\mathrel{+}=I_{00}+p_2=c_2$ in both runs, so $v_1[0]=T+c_2$ resp. $T+c_2+2^{8}+2^{24}-2^{9}-2^{24}=T+c_2-2^{8}$: the difference is $-2^{8}$. With $x:=\operatorname{lo}(T+c_2)$ and $h=\operatorname{hi}(U_0)$ the two lane-0 $\mathit{mul}_0$ products are $x\cdot h$ and $\big((x-2^{8})\bmod 2^{32}\big)\cdot\big((h+2^{8})\bmod 2^{32}\big)$, products of 32-bit integers. If neither operand wraps, the second is $xh+2^{8}(x-h-2^{8})$, equal to $xh$ iff $x-h=2^{8}$; if exactly one wraps the second product exceeds or falls short of $xh$ by at least $2^{8}(2^{32}-2^{8})-2^{16}>0$, so they differ; if both wrap ($x<2^{8}$, $h\ge2^{32}-2^{8}$) they are equal iff $x=h+2^{8}-2^{32}$. In all cases: the products coincide iff $x-h\equiv 2^{8}\pmod{2^{32}}$, i.e. iff $E_2$. Assume $E_2$. By [eq:hbounds] $h<2^{32}-2^{8}$, hence $x=h+2^{8}$ as integers, $x\ge2^{8}$ and $x[1]=h_1+1\in\{\mathtt{bf},\mathtt{c0}\}$. Thus $v_1[0]-2^{8}$ differs from $v_1[0]$ in byte 1 only: $\operatorname{hi}(v_1[0])$ is equal (so the $\mathit{mul}_1$ products coincide, $\operatorname{lo}(v_0[0])$ being equal), and after $v_0[0]\mathrel{+}=\mathit{mul}_1[0]$ the term $Z_0(v_1[0],v_1[1])$ differs by exactly $-2^{40}$ while $Z_1$ is unchanged. Hence $v_0[0]$ becomes equal ($+2^{40}-2^{40}$), $v_0[1]$ is equal, the second zipper adds equal words, and after packet 2 the only difference is $v_1[0]$: $-2^{8}$. Packet 3. $v_1[0]\mathrel{+}=\mathit{mul}_0[0]+p_3$ with $p_3=0$ resp. $2^{8}$ cancels it; the states are identical from here on. So $E_2\Rightarrow\mathcal C$ and $\Pr[\mathcal C]\ge\Pr[E_2]$.

3. $E_2$ as a system of byte equations. $E_2$ reads $\operatorname{lo}(T)-h\equiv 2^{8}-c_2\equiv\mathtt{4d000000}$, i.e. $Q-h\equiv\mathtt{4d000000}-\mathtt{10e82046}=\mathtt{3c17dfba}\pmod{2^{32}}$. Subtracting byte by byte with borrows $g_0,g_1,g_2\in\{0,1\}$: $\begin{aligned} U_0[3]-h_0&=\mathtt{ba}-256g_0, & U_1[4]-h_1-g_0&=\mathtt{df}-256g_1,\\ U_0[2]-h_2-g_1&=\mathtt{17}-256g_2, & h_1-h_3-g_2&\equiv\mathtt{3c}\pmod{256}. \end{aligned}$ Since $h_1+g_0+\mathtt{df}\ge\mathtt{be}+\mathtt{df}>255$, $g_1=1$; so $g_2=[h_2\ge\mathtt{e8}]$. The last equation is $\mathtt{3d}+e_0-e_2-g_2\equiv\mathtt{3c}$, i.e. $e_0+1=e_2+g_2$. If $e_2=1$ then $h_2=W_1[7]-\mathtt{2d}\le\mathtt{d2}$ and $g_2=0$; so $e_2+g_2\le1$, forcing $e_0=0$ and $e_2+g_2=1$, which (checking $e_2=0$: $g_2=[W_1[7]\ge\mathtt{15}]$) is exactly $W_1[7]\ge\mathtt{15}$. Hence $E_2$ is equivalent to the conjunction of $\begin{aligned} &\text{(iv$'$)}\quad \mathtt{10}+W_1[6]+\gamma\le255\ \ (e_0=0)\quad\text{and}\quad W_1[7]\ge\mathtt{15};\\ &\text{(i)}\quad U_0[3]\equiv h_0+\mathtt{ba}=\mathtt{ca}+W_1[6]+\gamma\pmod{256},\qquad g_0=[h_0\ge\mathtt{46}];\\ &\text{(iii)}\quad U_0[2]\equiv h_2+\mathtt{18}\equiv\mathtt{eb}+W_1[7]\pmod{256};\\ &\text{(ii)}\quad U_1[4]\equiv h_1+g_0+\mathtt{df}\equiv\mathtt{9d}+g_0\pmod{256}. \end{aligned}$ (The side condition $U_0[5]\ne\mathtt{ff}$ used in step 2 holds unconditionally by [eq:hbounds].)

4. The key-1 side: condition (ii) costs exactly $2^{-8}$. Write $K_1=(K_{1h},K_{1l})$. Then $W_1=(\mathrm{hi},\mathrm{lo})$ with $\operatorname{lo}(W_1)=(\mathtt{b5f18a8c}\oplus K_{1h})+\mathtt{299f31d0}\bmod2^{32}$, carry $c_1=[\operatorname{lo}(W_1)<\mathtt{299f31d0}]$, and $\operatorname{hi}(W_1)=(\mathtt{c0acf169}\oplus K_{1l})+\mathtt{a4093822}+c_1\bmod 2^{32}$; $\operatorname{lo}(W_0)=(\mathtt{299f31d0}\oplus K_{1l})+\mathtt{b5f18a8c}\bmod2^{32}$ with carry $c_0$, and $\operatorname{hi}(W_0)[0]=(\mathtt{22}\oplus K_{1h}[0])+\mathtt{69}+c_0\bmod256$. Since $Z_1((b,\cdot),W_1)=(W_1[3],b[0],W_1[2],W_1[5],W_1[1],b[2],W_1[0],b[3])$, $\begin{aligned} U_1[4]&=\big((\mathtt{22}\oplus K_{1h}[0])+\mathtt{69}+c_0+W_1[1]+c'\big)\bmod256,\\ c'&=\big[\operatorname{lo}(W_0)+W_1[5]2^{24}+W_1[2]2^{16}+b[0]2^{8}+W_1[3]\ge2^{32}\big]. \end{aligned}$ The map $K_{1h}\mapsto\operatorname{lo}(W_1)=:(w_3,w_2,w_1,w_0)$ is a bijection of 32-bit words, and $K_{1h}[0]=((w_0-\mathtt{d0})\bmod256)\oplus\mathtt{8c}$, so $\varphi(w_0):=\mathtt{22}\oplus K_{1h}[0] =((w_0-\mathtt{d0})\bmod256)\oplus\mathtt{ae}$ is a bijection of bytes, and (ii) becomes $\varphi(w_0)\equiv t'-w_1\pmod{256},\qquad t':=\mathtt{34}+g_0-c_0-c'\in[\mathtt{32},\mathtt{35}].$ Fix $a$, $K_{1l}$ and $(w_3,w_2,w_1)$. If $(w_3,w_2,w_1)\ne(\mathtt{29},\mathtt{9f},\mathtt{31})$ then $c_1$, hence $\operatorname{hi}(W_1)$, $c_0$, $c'$, $g_0$ and the truth of (i),(iii),(iv$'$), do not depend on $w_0$, and [eq:pad] has exactly one solution $w_0$. For the exceptional triple, $c_1=[w_0<\mathtt{d0}]$; but for either value of $c_1$ the unique solution of [eq:pad] is $w_0=((t'-\mathtt{31})\oplus\mathtt{ae})+\mathtt{d0}\bmod256\in\{\mathtt{7a},\mathtt{7c},\mathtt{7d},\mathtt{7f}\}$, which is $<\mathtt{d0}$; so no $w_0\ge\mathtt{d0}$ satisfies (ii), and exactly one $w_0<\mathtt{d0}$ does, with $c_1=1$. In every case the number of $w_0$ satisfying (ii) is $[\text{(i),(iii),(iv$'$) hold for } \operatorname{hi}(W_1)(K_{1l},c_1)]$ with $c_1$ a function of $(w_3,w_2,w_1)$ alone (equal to $1$ on the exceptional triple). For fixed $(w_3,w_2,w_1)$ the map $K_{1l}\mapsto\operatorname{hi}(W_1)=(w_7,w_6,w_5,w_4)$ is a bijection, and (i),(iii),(iv$'$) involve $\operatorname{hi}(W_1)$ only through $w_4=W_1[4]$, $w_6$, $w_7$. Therefore $\begin{gathered} \#\{(k,K_1)\in\{0,1\}^{96}: E_2\}=2^{24}\cdot 2^{8}\cdot M,\\ M:=\#\{(a,w_4,w_6,w_7)\in\{0,1\}^{56}:\ \text{(i),(iii),(iv$'$)}\}. \end{gathered}$

5. $M=2^{24}\cdot235\cdot239$. Fix $a[0],a[1],w_4$ and $w_7\ge\mathtt{15}$ ($235$ values). Let $S:=\mathtt{cb0ef593}+Z_c=(\mathtt{cb}+b[1])2^{24}+\mathtt{f6f5a3}+w_4 2^{8}$ (an integer $<2^{33}$; note $\mathtt{f6f5a3}+\mathtt{ff00}<2^{24}$), $\sigma:=\lfloor S/2^{32}\rfloor=[b[1]\ge\mathtt{35}]$, $s:=S\bmod2^{32}$, so $s[3]=(\mathtt{cb}+b[1])\bmod256$ and $s[2]=\mathtt{f6}+[w_4\ge\mathtt{0b}]$. Let $X:=a[3]\,256+a[2]$, $\kappa:=\lfloor(a[1]256+a[0]+s[1]256+s[0])/2^{16}\rfloor$ and $Y:=s[3]256+s[2]+\kappa$; then $Y[0]=s[2]+\kappa\le\mathtt{f8}$, $Y[1]=s[3]$, and by [eq:gamma] $(U_0[3],U_0[2])=(X+Y)\bmod2^{16},\qquad \gamma=\sigma+[X+Y\ge2^{16}].$ Condition (iii) fixes $X\bmod256$: $X=X_0+256j$, $j=0,\dots,255$, with $X_0\equiv r_2-Y$, $r_2:=(\mathtt{eb}+w_7)\bmod256$. Put $q:=\lfloor(Y+X_0)/256\rfloor=Y[1]+[r_2<Y[0]]$ and $u:=q+j$; then $U_0[3]=u\bmod256$ and $\gamma=\sigma+[u\ge256]$. For each $j$, condition (i) determines $w_6\equiv U_0[3]-\mathtt{ca}-\gamma$ uniquely, and (iv$'$) holds iff $w_6\le\mathtt{ef}-\gamma$, i.e. iff $(u-\gamma)\bmod256\notin[\mathtt{ba}-\gamma,\mathtt{c9}]$, i.e. iff $u\notin[\mathtt{ba},\mathtt{c9}+\sigma]\cup[\mathtt{1ba},\mathtt{1ca}+\sigma].$ The window $\{q,\dots,q+255\}$ meets the first interval in $\max(0,\mathtt{c9}+\sigma-\max(q,\mathtt{ba})+1)$ points and the second in $\max(0,\min(q-1,\mathtt{ca}+\sigma)-\mathtt{b9})$ points, which sum to $16+\sigma$ for $q\le\mathtt{ca}+\sigma$ and to $17+\sigma$ for $q\ge\mathtt{cb}+\sigma$. Hence the number of admissible $(a[2],a[3],w_6)$ is $240-\sigma-[q\ge\mathtt{cb}+\sigma]$. If $\sigma=0$ then $b[1]\le\mathtt{34}$, $Y[1]=\mathtt{cb}+b[1]\ge\mathtt{cb}$, so $q\ge\mathtt{cb}$ and the count is $239$; if $\sigma=1$ then $Y[1]=b[1]-\mathtt{35}\le\mathtt{ca}$, so $q\le\mathtt{cb}<\mathtt{cc}$ and the count is again $239$. Summing over the $256^3$ choices of $(a[0],a[1],w_4)$ and the $235$ values of $w_7$ gives $M=2^{24}\cdot235\cdot239$, and by [eq:N] $\Pr[E_2\mid(1)]=\frac{2^{32}\cdot2^{24}\cdot235\cdot239}{2^{96}}=\frac{235\cdot239}{2^{40}}.$ Multiplying by the exact probability $2^{-32}$ of condition (1) (a 32-bit equation on $\operatorname{hi}(K_0)$, independent of the other 224 bits) gives the bound over uniform keys. The comparison factor is $(235\cdot239/2^{40})/2^{-32}=56165/256$. ◻

The two factors are transparent: $235/256$ is the probability that the byte $W_1[7]$ (a uniform byte of the key-1 word after one addition) is at least $\mathtt{15}$, so that the top byte of the difference $\operatorname{lo}(T)-h$ equals $\mathtt{4d}$ rather than $\mathtt{4c}$; $239/256$ is the probability that the byte $W_1[6]$ together with the carry $\gamma$ does not overflow $h_0$ ($e_0=0$): once the constants are accounted for, exactly $17$ of the $256$ values are excluded, whatever the key. The trail thus pays the three "uniform” byte equations (i),(ii),(iii) at exactly $2^{-8}$ each and the fourth byte at $235\cdot239/2^{16}=0.857$ instead of $2^{-8}$; that is the whole gain of the tuned constant $c_2$ over a uniform difference: $2^{7.78}$.