Rating:

# __X-MAS CTF 2018__
## _Santa's list_

## Information
**Category:** | **Points:** | **Writeup Author**
--- | --- | ---
Crypto | 286 | MiKHalyCH

**Description:**

> Santa's database got corrupted and now he doesn't know who was nice anymore... Can you help him find out if Galf was nice?
>
>Server: nc 199.247.6.180 16001
>
>[santas_list.zip](src/santas_list.zip)
>
>Author: SoulTaku

## Solution
Every connection creates new `rsa = RSA.generate(1024)`. `N` is 1024 bits length (that is unknown), `e = 0x10001`.

We can encrypt everything. But our message would be added to `used` list (that contains flag from start).

Also we can decrypt everything, which result isn't devisible by elements of `used`. So we can't decrypt `flag` as it is.

Let's define `ct = E(flag) = (flag ** e) % N`.

And we need to undestand some RSA properties:
```py
D(ct**k) =
= (ct**k)**d % N =
= (ct**d)**k % N =
= (ct**d % N)**k % N =
= ((flag**e)**d % N)**k % N =
= (flag**(e**d) % N)**k % N =
= (flag % N)**k % N =
= flag**k % N
```

```py
D(ct*(i**e)) =
= ct*(i**e)**d % N =
= (flag**e)*(i**e)**d % N =
= ((flag*i)**e)**d % N =
= (flag*i)*(e**d) % N =
= flag*i % N
```

Firstly we need to find `N`. I notice that `flag**2 < N < flag**3`. It was the good idea to calculate `N`:

```py
while True:
<create new session>
m1 = D(ct**3)
m2 = D(ct**3 * 2**e)
if 2*m1 != m2:
N = 2*m1 - m2
break
```
How it works?
```py
(2*m1 != m2) % N => 2*m1 = m2 + N => N = 2*m1 - m2
```

Now we can encrypt messages by client side. How to find the flag? From fact that we can decrypt, I thought about Oracle Attack and found an interesting question about [RSA Least Significant Bit Padding Oracle](https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack) on crypto.stackexchange.com.

Let's define bounds at the start of algorithm:
```py
LowerBound = 0
UpperBound = N
```
In this attack we are trying to bring closer the bounds to our secret message.

At the first try we will send to decrypt `ct*(2**e)` and recieve `m' = m*2 % N -> m*2 = m' + k*N`.

* If `m'` is even, then `m*2 < N`. We need to reduce `UB`.
* If `m'` is odd, then `m*2 > N`. We need to increase `LB`.

We need to do this `log_2(N)` times increasing the multiplier twice each step.

To reduce the final bounds' size of `flag`, I've used `flag**2` and `iroot` then.

This is my interpretation of RSA LSB PO:
```py
l = log_2(N)
LB, UB = 0, N

for i in range(1, l):
ct = (pow(ct, 2) * pow(2, i*e, N)) % N
m = D(ct)
if m is None or not (m % 2):
UB = (UB + LB)//2
else:
LB = (UB + LB)//2

flag = iroot(UB, 2)
```

My final solution is [here](solver.py)! And it works well!

___________
## _Santa's list 2.0_

## Information
**Category:** | **Points:** | **Writeup Author**
--- | --- | ---
Crypto | 328 | MiKHalyCH, a1exdandy

**Description:**
>Santa's MechaGnomes caught up to some intense traffic on their servers so they decided to modify santa's database server to be DDoS-proof but it still is corrupted, find out if Galf was nice or not but try not to DDoS the server.
>
>Server: nc 199.247.6.180 16002
>
>[list_2.py](src/list_2.py)
>
>Author: SoulTaku

## Solution
This task looks same, but we can encrypt/decrypt just 5 times per one connection.

We know that we can calculate `N` just in 2 requests. 3 left for flag RSA LSB PO. But this attack works only if we use same `N`. This time we need to create new solution!

My idea was simple. If we can find `k`: `flag**(k-1) < N` and `flag**k > N` then we can calculate `flag`:
```py
flag * 2**k % N = m' % N
flag * 2**k = m' + N
flag = (m' + N) // 2**k
```

To find `k` faster we can use `flag**2` and then take square root of it.

Here is my [solution](solver_2.py) for second task.

## P.S.
_SoulTaku_ said that there is solution that uses only 2 requests to server. And _a1exdandy_ found an intersting [idea](solver_2_fast.py) for it.

Firstly he collects 2 pairs of `(flag**3, N)`:
```py
ns = []
m3s = []

while len(ns) < 2:
<create new session>
m1 = D(ct**3)
m2 = D(ct**3 * 2**e)
if 2*m1 != m2:
N = 2*m1 - m2
ns.append(N)
m3s.append(m1)
```

At the second step he uses [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to the real value of `flag**3` without modulus.

Original writeup (https://github.com/VoidHack/write-ups/tree/master/X-MAS%20CTF%202018/crypto/Santa's%20list#santas-list-20).