## waRSAw, inCTF 2019

## Description

Just another conventional RSA attack, isn't it?

The challenge provides an "encrypt.py" source code that contains an RSA LSB decrypt oracle.
However, the particularity is that that you can query only one bit per connection and the challenge will send a
different encrypted flag, and n value at each connection.

Let's first see how a simple LSB RSA oracles works:

## Multiplying by powers of 2 modulo N

This is what happends the simple cases of 2 and 4:

When you multiply by 2:

| Input Range | Output before mod N | Parity after mod N |
|--------------|-----------------------------|--------------------------------------------------------------------------------------|
| 0 - 0.5N | 0 - N | Even, because we multiplied by a power of 2, and the modulo N did nothing |
| 0.5N - N | N - 2N | Odd, because we multiplied by a power of 2, and subtract N once (and N is odd) |

When you multiply by 4:

| Input Range | Output before mod N | Parity after mod N |
|--------------|-----------------------------|--------------------------------------------------------------------------------------|
| 0 - 0.25N | 0 - N | Even, because we multiplied by a power of 2, and the modulo N did nothing |
| 0.25N - 0.5N | N - 2N | Odd, because we multiplied by a power of 2, and subtract N once (and N is odd) |
| 0.5N - 0.75N | 2N - 3N | Even, because we multiplied by a power of 2, and subtract N twice (and N is odd) |
| 0.75 - N | 3 - 4N | Odd, because we multiplied by a power of 2, and subtract N tree times (and N is odd) |

**General Case**
Now we can see, that in the general case when multiplying by $2^k$, we split [0,N] into $2^k$ equal size intervals labeled $I_{0}$ ... $I_{2^k-1}$
* if the result is even, the input was from an evenly labeled interval $I_{2i}$
* if the result is odd, the input was from an oddly labeled interval $I_{2i+1}$

In a normal LSB oracle for RSA, when N stays constant, it is easy solve the challenge by dicotomy.
At each step, we pick a larger power of two, and determine if the value is in $I_{2i}$ or $I_{2i+1}$

## RSA LSB oracle where N changes

Now, when N changes at every step, if you know that the input is in the interval [l, u], we can always pick a value $2^k$ such that two successive intervals $I_{2i}$ and $I_{2i+1}$ (build like explained before) fully cover [l,u] and have their joining point (h) in [l,u].

* If the result is even, we conclude that the input was in $I_{2i}$ and we set u = h
* If the result is odd, we conclude that the input was in $I_{2i+1}$ and we set l = h

We just start with [l, u ] = [0, 2**2048], and apply the rule until we find the solution.

## Source Code

The source code we used to solve the challenge is the following:

from socket import create_connection
import re

e = 65537

def get_power(n, l_know, u_know):
    l = 0
    u = n
    for i in range(2048):
        h = (l + u) // 2
        if l_know <= h <= u_know:
            return (i, h)
        if h < l_know: 
            l = h
        else:
            u = h

def hexencode(i):
    res = hex(i)[2:]
    if len(res) % 2:
        return "0" + res
    return res

def step(l, u):
    conn = create_connection(("18.217.237.201", 3197))
    def recv(l):
        return conn.recv(l)
    def send(data):
        conn.send(data)
    def recv_until(end=b"\n"):
        res = recv(1)
        while res[-len(end):] != end:
            c = recv(1)
            if not c:
                return res
            res += c
        return res
    def readline():
        return recv_until(b"\n")
    # Receive flagenc and modulus
    readline() 
    flagencline = readline()
    flagenc = int(re.search(b":  ([0-9a-h]+)", flagencline).group(1), 16)
    modulusline = readline()
    n = int(re.search(b":  ([0-9a-h]+)", modulusline).group(1))
    
    # Choose decrypt
    recv_until(b'choice: ')
    send(b"2\n")
    recv_until(b': ')
    # Pick the power of 2 to multiply flagenc by
    i, h  = get_power(n, l, u)
    print (i)
    # Send the value
    v = flagenc * pow(2**(i+1), e, n)
    send(hexencode(v).encode() + b"\n")
    resultline = readline()
    response = int(re.search(b":  ([0-1]+)", resultline).group(1))
    # Adjust upper and lower bound
    if response == 0:
        u = h
    else:
        l = h 
    return l, u

if __name__ == '__main__':
    l = 0
    u = 2**2048
    
    for a in range(2048):
        print (a, len(str(l)), len(str(u)), l, u)
        l, u = step( l, u)