**tl;dr**

- use hash extension to bypass password check on login.
- use RSA properties to recover $q$ and get $p$ and therefore $N= p*q$.
- sign the message given, and get the flag.

**Challenge Points**: 900

**Challenge Solves**: ~20

## Challenge Description

try to login to this service.

## Initial Analysis

We are provided with an nc service with the following three options

**Sign up****Login****Leave**

a) *Sign up*

This asked us for a username following which a password would be generated

password consisted of three parts each seperated by a `;`

whose sha256 hash was taken

1 | passwd = H(server_token + b';' + user + b';' + proof) |

`server_token`

: random 16 byte string`user`

: username over which the user had control over`proof`

: value of this was initially set to`is_admin=false`

after sign up user would get $username$ , $password$ and $proof$ values

b) *Login*

on Login user would have to input the values of $username$,$password$ and $proof$.

the password value is checked with the hash of secret token and $user$ and $proof$ values which you entered.

if it is correct u move on to next stage

## Login check

the 3 values which you enter on login: $username$, $password$ and $proof$

are used for the first check

1 | if password == H(server_token + b';' + username + b';' + proof): |

here the hash is calulated by using sha256.

And we need `is_admin=true`

in $proof$ but on signup $proof$ is initialised with `is_admin=false`

a) *Intended solution*

the intended way here is to append the data `is_admin=true`

to $proof$ and generate a hash which satisfies this new data. This can be achived by hash extension attack using this tool.

b) *Unintended solution*

Instead of going though with implementation of hash extension there is way more simpler solution to this. If we look at the login part where the 2 if conditions are present we see the second if condition only checks for if the string `is_admin=true`

is present in $proof$. But we see that $proof$ is initialised with `is_admin=false`

in the begining itself.

Also we notice we have control over username and the value assigned to proof in the login function. So the idea here is to initially generate a password that will pass the first if condition and contain the desired proof value.

Since on sign up we do not have acess to proof we use username itself to assign the value of $proof$.

*confusingâ€¦â€¦.*

well the idea is to match the password hash and that proof should contain the desired value. For this to work we use the fact that the hash is calculated by adding the strings together it doesnt matter wherse a string is placed as long as on adding all the strings we get the same final string and hence the same hash.

So in sign up we fill in the desired value of proof in username field itself like so

`username = 'a;is_admin=true'`

so now password hash is:

1 | passwd = H(server_token + b';' + b'a;is_admin=true' + b';' + b'is_admin=false') |

Now on sign up we have control over bothe username and proof fields

So we give **username** as `a`

and **proof** as `is_admin=true;is_admin=false`

1 | passwd = H(server_token + b';' + b'a' + b';' + b'is_admin=true;is_admin=false') |

so the password hash is same as what we get after sign up but this time the desired vaue is there in proof instead of username hence we pass the check

## Signing

to pass this we need to correctly sign this

1 | message_to_sign = b"https://twitter.com/CTFCreators" |

since the server gives us $e$ and $d$ we can easily get the correct signature only problem is we dont have modulus instea we have $pinv \equiv p^{-1} \bmod\ q$

we know this rsa formula $ed = 1 + k*(p-1)(q-1)$ from this we see $k$ will have same bit size as e and so it can be bruteforced hence we can assume we have $\phi(n) = (p-1)(q-1)$

also we have $p^{-1}p \equiv 1\bmod\ q$

writing $\phi(n)$ in terms of $ \bmod\ q$ we get $\phi(n) \equiv -(p-1) \bmod\ q$

from these 2 observatoins we get $1 + pinv*\phi(n) - pinv \equiv 0 \bmod\ q$ ,

after substituting $p$ in the equation.

$i.e$ LHS of the above equation is a multiple of $q$

from ** fermats little theorem** for some $a$ we get $a^{\phi(n)} - 1 \equiv 0 \bmod\ p*q$

so we have another multiple. Taking the gcd of these two will get us the value of $q$ after which we get $p$ and so we have $N = p*q$ and we can easily generate a valid sign for the given message!!