__Original writeup:__ <https://github.com/kyos-public/ctf-writeups/blob/main/insomnihack-2024/Pedersen.md>

# The Challenge

The goal was to find a collision in the Pedersen hash function (i.e., find distinct inputs that yield the same output).

We had access to a running version of the code (a hashing oracle), as indicated in the `README.md`:

```Markdown
You do not need to go to the CERN to have collisions, simply using Pedersen hash should do the trick.

`nc pedersen-log.insomnihack.ch 25192`

Test locally: `cargo run -r`
```

The implementation (in Rust) of the hash function was provided. All the interesting bits were in the `main.rs` file:

```Rust
use starknet_curve::{curve_params, AffinePoint, ProjectivePoint};
use starknet_ff::FieldElement;
use std::ops::AddAssign;
use std::ops::Mul;
use std::time::Duration;
use std::thread::sleep;

mod private;

const SHIFT_POINT: ProjectivePoint = ProjectivePoint::from_affine_point(&curve_params::SHIFT_POINT);
const PEDERSEN_P0: ProjectivePoint = ProjectivePoint::from_affine_point(&curve_params::PEDERSEN_P0);
const PEDERSEN_P2: ProjectivePoint = ProjectivePoint::from_affine_point(&curve_params::PEDERSEN_P2);

fn perdersen_hash(x: &FieldElement, y: &FieldElement) -> FieldElement {
let c1: [bool; 16] = private::C1;
let c2: [bool; 16] = private::C2;

let const_p0 = PEDERSEN_P0.clone();
let const_p1 = const_p0.mul(&c1;;
let const_p2 = PEDERSEN_P2.clone();
let const_p3 = const_p0.mul(&c2;;

// Compute hash of two field elements
let x = x.to_bits_le();
let y = y.to_bits_le();

let mut acc = SHIFT_POINT;

acc.add_assign(&const_p0.mul(&x[..248]));
acc.add_assign(&const_p1.mul(&x[248..252]));
acc.add_assign(&const_p2.mul(&y[..248]));
acc.add_assign(&const_p3.mul(&y[248..252]));

// Convert to affine
let result = AffinePoint::from(&acc;;

// Return x-coordinate
result.x
}

fn get_number() -> FieldElement {
let mut line = String::new();
let _ = std::io::stdin().read_line(&mut line).unwrap();
// Remove new line
line.pop();
let in_number = FieldElement::from_dec_str(&line).unwrap_or_else(|_| {
println!("Error: bad number");
std::process::exit(1)
});
in_number
}

fn main() {
println!("Welcome in the Large Pedersen Collider\n");
sleep(Duration::from_millis(500));
println!("Enter the first number to hash:");
let a1 = get_number();
println!("Enter the second number to hash:");
let b1 = get_number();
let h1 = perdersen_hash(&a1, &b1;;
println!("Hash is {}", h1);

println!("Enter the first number to hash:");
let a2 = get_number();
println!("Enter the second number to hash:");
let b2 = get_number();

if a1 == a2 && b1 == b2 {
println!("Input must be different.");
std::process::exit(1);
}

let h2 = perdersen_hash(&a2, &b2;;
println!("Hash is {}", h2);

if h1 != h2 {
println!("No collision.");
} else {
println!("Collision found, congrats here is the flag {}", private::FLAG);
}
}
```

So we can almost run the code locally, but the `private` module is missing. Looking at the rest of the code, we can infer that the private module contains the flag and two mysterious constants: `C1` and `C2`, which we can initialize arbitrarily for now:

```Rust
mod private {
pub const FLAG: &str = "INS{this_is_the_flag}";
pub const C1: [bool; 16] = [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false];
pub const C2: [bool; 16] = [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false];
}
```

We then see in the main function that we actually need two numbers to compute one hash value. We must therefore find four numbers `a1`, `b1`, `a2`, `b2`, such that `(a1 == a2 && b1 == b2)` is false, but `perdersen_hash(&a1, &b1) == perdersen_hash(&a2, &b2)`.

A first important observation here is that `b1` can be equal to `b2`, as long as `a1` is different from `a2`.

# The Theory

There are two non-standard imports: `starknet_curve` and `starknet_ff`, which are both part of the `starknet-rs` library: <https://github.com/xJonathanLEI/starknet-rs>.

The documentation tells us how the Pedersen hash function is supposed to be implemented: <https://docs.starkware.co/starkex/crypto/pedersen-hash-function.html>.

Normally, $H$ is a Pedersen hash on two field elements, $(a, b)$ represented as 252-bit integers, defined as follows (after some renaming to keep the math consistent with the code):

$$ H(a, b) = [S + a_\textit{low} \cdot P_0 + a_\textit{high} \cdot P_1 + b_\textit{low} \cdot P_2 + b_\textit{high} \cdot P_3]_x $$

where

- $a_\textit{low}$ is the 248 low bits of $a$ (same for $b$);
- $a_\textit{high}$ is the 4 high bits of $a$ (same for $b$);
- $[P]_x$ denotes the $x$ coordinate of an elliptic-curve point $P$;
- $S$, $P_0$, $P_1$, $P_2$, $P_3$, are constant points on the elliptic curve, derived from the decimal digits of $\pi$.

But looking at the challenge's implementation, we see that the constant points are actually related:

- $P_1 = P_0 \cdot C_1$
- $P_3 = P_2 \cdot C_2$

Given the above equations, we can rewrite the hash function as follows:

$$ H(a, b) = [S + (a_\textit{low} + a_\textit{high} \cdot C_1) \cdot P0 + (b_\textit{low} + b_\textit{high} \cdot C_2) \cdot P2]_x $$

Since we've established that we can keep $b$ constant, let's find a pair $a$ and $a'$ such that

$$ a_\textit{low} + a_\textit{high} \cdot C_1 = a_\textit{low}' + a_\textit{high}' \cdot C_1 $$

Given the linear nature of these equations, there is a range of solutions. If $a_\textit{low}$ is increased by some $\delta$, then $a_\textit{high}$ can be decreased by $\delta/C_1$ to keep the term $(a_\textit{low} + a_\textit{high} \cdot C_1) \cdot P0$ unchanged.

A straightforward solution is to pick $\delta = C_1$, which implies that if we increase $a_\textit{low}$ by $C_1$ and decrease $a_\textit{high}$ by 1, we have a collision.

# The Practice

Now in theory we know how to find a collision, but we don't actually know `C1` and `C2`. Since they are just 16 bits long, let's bruteforce them! Or at least one of them... As we don't need different values for `b1` and `b2`, we can leave them at 0 and thus `C2` is not needed. You could bruteforce `C1` with a piece of code that looks like this:

```Rust
// Try all possible values of c1
for i in 0..(1 << 16) {
let mut c1 = [false; 16];
for j in 0..16 {
c1[j] = (i >> j) & 1 == 1;
}

let const_p0 = PEDERSEN_P0.clone();
let const_p1 = const_p0.mul(&c1;;
let const_p2 = PEDERSEN_P2.clone();
let const_p3 = const_p0.mul(&c2;;

let x = x.to_bits_le();
let y = y.to_bits_le();

let mut acc = SHIFT_POINT;

acc.add_assign(&const_p0.mul(&x[..248]));
acc.add_assign(&const_p1.mul(&x[248..252]));
acc.add_assign(&const_p2.mul(&y[..248]));
acc.add_assign(&const_p3.mul(&y[248..252]));

let result = AffinePoint::from(&acc;;

// Check if the result is the expected hash
if result.x == FieldElement::from_dec_str("3476785985550489048013103508376451426135678067229015498654828033707313899675").unwrap() {
// Convert c1 to decimal
let mut c1_dec = 0;
for j in 0..16 {
c1_dec |= (c1[j] as u16) << j;
}
println!("Bruteforce successful, c1 = {}", c1_dec);
break;
}
}
```

For this to work, we need to query the hashing oracle with $a_\textit{high} \ne 0$ (otherwise `C1` does not play any role in the computation of the final result) and $b_\textit{high} = 0$. For example, we could set the first number to $2^{248} = 452312848583266388373324160190187140051835877600158453279131187530910662656$ and the second number to $0$, and obtain a hash value of $3476785985550489048013103508376451426135678067229015498654828033707313899675$.

We then find by bruteforce that $C_1 = 24103$.

# The Solution

Now that we have everything we need, the final solution is:

```
Enter the first number to hash: 452312848583266388373324160190187140051835877600158453279131187530910662656
Enter the second number to hash: 0
Hash is: 3476785985550489048013103508376451426135678067229015498654828033707313899675

Enter the first number to hash: 24103
Enter the second number to hash: 0
Hash is: 3476785985550489048013103508376451426135678067229015498654828033707313899675
```

This works because we start with $a_\textit{low} = 0$ and $a_\textit{high} = 1$ (i.e., $2^{248}$), and then we increase $a_\textit{low}$ by $C_1$ and decrease $a_\textit{high}$ by $1$ to obtain 24103.

Submitting such a collision to `nc pedersen-log.insomnihack.ch 25192` gives us the `INS{...}` flag (which we forgot to save, sorry).