DigestiveV2

DigestiveV2

Points	Solves
423	23

Description

I only like upper case try to change my mind !

Overview

ECDSA with sussy hash function:

def pub_hash(m):
     return (bytes_to_long(m.encode())%O)>>60 

We have to find the username for $m_1$ and $m_2$ (all of the character has to be in ascii range) which look like this:

m1 = '{"username": "...", "admin": "false"}'
m2 = '{"username": "...", "admin": "truee"}'

where $h(m_1) = h(m_2)$ and $m_1 \neq m_2$ ($h$ is the sussy baka hash function)

Solution

Turn out we just have to find $long(name_1) \equiv long(name_2) \pmod{O}$ since the postfix is irrelevant due to >> 60

This can be transform into a lattice problem as follow:

Let’s denote $name_{1, i}$ and $name_{2, i}$ as the $ith$ character of $name_1$ and $name_2$ from left to right (I also assume $len(name_1) = len(name_2)$ to make thing easier)

Notice that $long(name_1) \equiv long(name_2) \pmod{O} \Rightarrow long(name_1) - long(name_2) - kO = 0$ $\Rightarrow$ $\sum_{i=1}^{n}256^{\pi_i}(name_{1,i} - name_{2, i}) - kO = 0$ for some k $\in Z$ ($256^{\pi_i}$ is the postition of $character_i$ in the string $m$)

Now let’s consider a lattice generated by the rows of the following $(n+1) \times (n+1)$ matrix where $len(name_1) = len(name_2) = n$

\[\begin{aligned} M = \left(\begin{array}{cc} 256^{n-1+l} & 1 & 0 & \dots & 0 \\ 256^{n-2+l} & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 256^l & 0 & 0 & \dots & 1 \\ O & 0 & 0 & \dots & 0 \end{array}\right) \end{aligned}\]

where l = len('", "admin": "false"}') (the postfix)

Notice that the vector $(0, name_{1, 1} - name_{2, 1}, \dots, name_{1, n}- name_{2, n}, -k)$ is a short vector in this lattice so we can use LLL to find all the $name_{1, i} - name_{2, i}$ $\Rightarrow$ We have found $name_2$

1