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).