HITCON CTF 2019 Quals - Lost Key Again (crypto)

The challenge has the following code:

def read_key():
    key_file = open("key")
    n,e,d = map(int,key_file.readlines()[:3])
    return n,e,d

def calc(n,p,input):
    data = "X: "+input
    num = bytes_to_long(data)
    res = pow(num,p,n)
    return long_to_bytes(res).encode('hex')

def read_flag():
    flag = open('flag').read()
    assert len(flag) >= 50
    assert len(flag) <= 60
    prefix = os.urandom(68)
    return prefix+flag

n,e,d = read_key()
flag =  calc(n,e,read_flag())
print 'Here is the flag!', flag
for i in xrange(100):
    m = raw_input('give me your X value: ')
    try:
        m = m.decode('hex')[:15]
        print calc(n,e,m)
    except:
        print 'no'
        exit(0)

We can encrypt messages of length up to 15 bytes, prepended by $T=$ "X: "=0x583a20. The challenge only provides encryption oracle, therefore knowing $e$ and $n$ should allow to decrypt, i.e. they must be weak in some way. This already hints about some guessing, but first we need to recover $n$ and/or $e$.

Typically, to recover the modulus, when $e$ is unknown, we use multiplicativity of RSA:

$$ a^e \times b^e \equiv (a \times b)^e \pmod{n}.$$

If we compute the values on the left and on the right, they will differ by a multiple of $n$. After collecting a few of them, we recover $n$ using the GCD.

Here, due to restrictions (3-byte padding and small size), we can not find values $a,b$ such that $a,b,ab$ all have correct padding "X: ".

However, the key is to notice that we are not required to obtain one enc() on the righthand side: we can use any nontrivial relations. Let's find some!

Let $pad_t(x) := 256^tT + x$. We want to find relations of the form

$$ pad_{t_1}(x_1)^{e_1} pad_{t_2}(x_2)^{e_2} \ldots = pad_{t_1'}(x_1')^{e_1'} pad_{t_2'}(x_2')^{e_2'} \ldots, $$

where all $t_i$ should be at most 15, all $x_i \le 256^{t_i}$, and all $e_i$ must be small (since we will compute the expressions on both sides in integers). How can we find them? Let's map the problem to a linear one!

One approach is to consider logarithms: taking logarithm of the equation leads to a linear equation. However, logarithms in real numbers have precision issues, which are hard to tackle with. Instead, we can make logarithms base each prime to produce a vector of integers. Equivalently, we obtain multiple linear equations.

This approach is similar to the index calculus method and some sieving methods. First, we choose a factor base $B$ made of small primes up to a chosen limit and look for values that split completely in $B$ and have correct padding $pad_t$. Note that this is doable only because we can choose small numbers $pad_t(x)$, which have high chance to split in a small factor base.

In [1]:
from __future__ import print_function, division
from sage.all import *
from Crypto.Util.number import *
from sock import Sock
class Stop(Exception): _render_traceback_ = lambda self: None
In [2]:
T = 0x583a20 # "X: "

Experimentally, we can find that all 53 primes below 250 make a good factorbase. Our goal is to find $53 + \epsilon$ messages that split in $B$, where $\epsilon$ is the minimum kernel dimension that we would like. The larger the kernel is, the more relations will be there, and higher chance to find small ones.

In [3]:
# factorbase
B = set(primes(250))
# number of required relations
# more extra -> larger kernel -> smaller relations!
N = len(B) + 50

def facb(v):
    res = []
    for p in B:
        e = 0
        while v % p == 0:
            e += 1
            v //= p
        res.append((p, e))
    if v == 1: return res
In [4]:
sources = []
vecs = []
for t in range(1, 100):
    if len(sources) >= N: break
    for x in range(0, 256**t-1):
        if len(sources) >= N: break
        v = 256**t * T + x
        fac = facb(v)
        if fac:
            ps = {p for p, e in fac}
            vecs.append([e for p, e in fac])
            sources.append((t, x))
            print("%3d-th/%d B-smooth number: t=%2d x=%7d factors: %r" % (len(sources), N, t, x, factor(v)))
print("Done", len(sources))
  1-th/103 B-smooth number: t= 1 x=     16 factors: 2^4 * 41 * 109 * 127 * 163
  2-th/103 B-smooth number: t= 1 x=     60 factors: 2^2 * 7^2 * 17 * 19 * 103 * 227
  3-th/103 B-smooth number: t= 1 x=    179 factors: 3^2 * 7 * 17 * 61 * 139 * 163
  4-th/103 B-smooth number: t= 2 x=   2128 factors: 2^4 * 11 * 31 * 41 * 67 * 131 * 193
  5-th/103 B-smooth number: t= 2 x=   3551 factors: 3^4 * 7^2 * 61 * 83 * 109 * 173
  6-th/103 B-smooth number: t= 2 x=   4096 factors: 2^12 * 41 * 109 * 127 * 163
  7-th/103 B-smooth number: t= 2 x=   5216 factors: 2^5 * 3^2 * 13^3 * 29 * 107 * 193
  8-th/103 B-smooth number: t= 2 x=   7738 factors: 2 * 11^2 * 13 * 47 * 103 * 139 * 179
  9-th/103 B-smooth number: t= 2 x=   8222 factors: 2 * 3^3 * 5^2 * 11^3 * 23 * 53 * 173
 10-th/103 B-smooth number: t= 2 x=   9522 factors: 2 * 5^3 * 7 * 71 * 113 * 137 * 197
 11-th/103 B-smooth number: t= 2 x=  14342 factors: 2 * 3^2 * 5 * 13^2 * 31 * 73 * 101 * 109
 12-th/103 B-smooth number: t= 2 x=  15059 factors: 3 * 7 * 53 * 67 * 113 * 193 * 233
 13-th/103 B-smooth number: t= 2 x=  15360 factors: 2^10 * 7^2 * 17 * 19 * 103 * 227
 14-th/103 B-smooth number: t= 2 x=  18496 factors: 2^6 * 7^2 * 11 * 31 * 37 * 61 * 157
 15-th/103 B-smooth number: t= 2 x=  19112 factors: 2^3 * 3^2 * 5 * 7 * 11^2 * 47 * 137 * 193
 16-th/103 B-smooth number: t= 2 x=  19882 factors: 2 * 5 * 7 * 11 * 17^2 * 19^2 * 53 * 89
 17-th/103 B-smooth number: t= 2 x=  23195 factors: 3 * 13 * 23^3 * 37 * 113 * 191
 18-th/103 B-smooth number: t= 2 x=  24212 factors: 2^2 * 3 * 5 * 43^2 * 113 * 167 * 181
 19-th/103 B-smooth number: t= 2 x=  26060 factors: 2^2 * 3^2 * 31 * 61 * 151 * 191 * 193
 20-th/103 B-smooth number: t= 2 x=  29687 factors: 3^3 * 5 * 31 * 47 * 53 * 163 * 223
 21-th/103 B-smooth number: t= 2 x=  29888 factors: 2^6 * 3 * 23 * 43 * 59 * 149 * 227
 22-th/103 B-smooth number: t= 2 x=  30256 factors: 2^4 * 7^2 * 19 * 23 * 73 * 109 * 139
 23-th/103 B-smooth number: t= 2 x=  31187 factors: 3 * 5 * 7^2 * 17 * 19 * 37 * 179 * 241
 24-th/103 B-smooth number: t= 2 x=  35766 factors: 2 * 11 * 13 * 19^2 * 97 * 157 * 241
 25-th/103 B-smooth number: t= 2 x=  36032 factors: 2^6 * 3^6 * 5 * 17 * 19 * 47 * 107
 26-th/103 B-smooth number: t= 2 x=  42800 factors: 2^4 * 3^2 * 7^2 * 29 * 31^2 * 41 * 47
 27-th/103 B-smooth number: t= 2 x=  44753 factors: 3^3 * 7 * 11 * 17 * 19 * 31 * 109 * 167
 28-th/103 B-smooth number: t= 2 x=  45824 factors: 2^8 * 3^2 * 7 * 17 * 61 * 139 * 163
 29-th/103 B-smooth number: t= 2 x=  46048 factors: 2^5 * 7 * 29^2 * 89 * 97 * 233
 30-th/103 B-smooth number: t= 2 x=  49637 factors: 3 * 5 * 11 * 13 * 71 * 97 * 113 * 227
 31-th/103 B-smooth number: t= 2 x=  50612 factors: 2^2 * 3^7 * 5 * 7 * 13 * 31 * 37 * 83
 32-th/103 B-smooth number: t= 2 x=  51536 factors: 2^4 * 3 * 7 * 17 * 19 * 79 * 193 * 229
 33-th/103 B-smooth number: t= 2 x=  51947 factors: 3 * 5^2 * 11 * 43^3 * 53 * 109
 34-th/103 B-smooth number: t= 2 x=  52106 factors: 2 * 3^2 * 19 * 23 * 47 * 53 * 83 * 233
 35-th/103 B-smooth number: t= 2 x=  55393 factors: 7^5 * 19 * 67 * 89 * 199
 36-th/103 B-smooth number: t= 2 x=  56039 factors: 3^4 * 11 * 19 * 23 * 79 * 97 * 127
 37-th/103 B-smooth number: t= 2 x=  60284 factors: 2^2 * 3 * 13 * 31 * 47 * 67 * 149 * 167
 38-th/103 B-smooth number: t= 2 x=  62519 factors: 3^5 * 7 * 101 * 113 * 131 * 149
 39-th/103 B-smooth number: t= 2 x=  62897 factors: 3^3 * 5^4 * 7 * 13 * 29 * 67 * 127
 40-th/103 B-smooth number: t= 2 x=  65144 factors: 2^3 * 3 * 7^2 * 53 * 137 * 199 * 223
 41-th/103 B-smooth number: t= 3 x=   3732 factors: 2^2 * 5^2 * 7^3 * 13 * 17 * 29 * 41 * 47 * 229
 42-th/103 B-smooth number: t= 3 x=  12062 factors: 2 * 3^5 * 5 * 7^2 * 17^2 * 23^2 * 73^2
 43-th/103 B-smooth number: t= 3 x=  47230 factors: 2 * 7 * 13 * 19 * 89 * 107 * 113 * 131 * 199
 44-th/103 B-smooth number: t= 3 x=  92327 factors: 3 * 5 * 11 * 13 * 29 * 37 * 47 * 61^2 * 241
 45-th/103 B-smooth number: t= 3 x= 118496 factors: 2^5 * 3^5 * 11^2 * 13^2 * 61 * 73 * 137
 46-th/103 B-smooth number: t= 3 x= 135227 factors: 3^2 * 5 * 7 * 11 * 13^2 * 17 * 23 * 31 * 79 * 173
 47-th/103 B-smooth number: t= 3 x= 148773 factors: 13 * 97 * 101 * 107 * 137 * 223 * 233
 48-th/103 B-smooth number: t= 3 x= 167357 factors: 3^2 * 5^2 * 7 * 17 * 61 * 67^2 * 101 * 131
 49-th/103 B-smooth number: t= 3 x= 226307 factors: 3^4 * 5^2 * 11^2 * 23^2 * 29 * 131 * 197
 50-th/103 B-smooth number: t= 3 x= 247850 factors: 2 * 3 * 7^2 * 31 * 47 * 71 * 103 * 173 * 179
 51-th/103 B-smooth number: t= 3 x= 253436 factors: 2^2 * 3 * 7^3 * 13 * 43 * 53 * 59 * 97 * 139
 52-th/103 B-smooth number: t= 3 x= 289264 factors: 2^4 * 13 * 17 * 53 * 101 * 107 * 211 * 227
 53-th/103 B-smooth number: t= 3 x= 296982 factors: 2 * 5^2 * 11 * 17 * 61^2 * 71 * 173 * 227
 54-th/103 B-smooth number: t= 3 x= 334844 factors: 2^2 * 3 * 11^2 * 23 * 53^3 * 109 * 179
 55-th/103 B-smooth number: t= 3 x= 348687 factors: 5 * 13 * 29 * 103^2 * 109 * 191 * 233
 56-th/103 B-smooth number: t= 3 x= 405532 factors: 2^2 * 5^2 * 7^2 * 19 * 37 * 41 * 73 * 97^2
 57-th/103 B-smooth number: t= 3 x= 500696 factors: 2^3 * 3 * 13 * 37^2 * 83 * 107^2 * 239
 58-th/103 B-smooth number: t= 3 x= 502308 factors: 2^2 * 11^3 * 13 * 17 * 47 * 61 * 149 * 193
 59-th/103 B-smooth number: t= 3 x= 529907 factors: 3 * 5^2 * 11 * 13 * 23 * 107 * 137 * 139 * 193
 60-th/103 B-smooth number: t= 3 x= 530856 factors: 2^3 * 13^2 * 19 * 61 * 71 * 89 * 97 * 101
 61-th/103 B-smooth number: t= 3 x= 544768 factors: 2^12 * 11 * 31 * 41 * 67 * 131 * 193
 62-th/103 B-smooth number: t= 3 x= 578000 factors: 2^4 * 3^2 * 23 * 31^2 * 43 * 67 * 71 * 149
 63-th/103 B-smooth number: t= 3 x= 630007 factors: 5^3 * 11 * 13 * 41 * 47 * 73 * 173 * 223
 64-th/103 B-smooth number: t= 3 x= 642184 factors: 2^3 * 11^2 * 17 * 37 * 41 * 71 * 229 * 239
 65-th/103 B-smooth number: t= 3 x= 662930 factors: 2 * 3 * 11 * 41 * 73 * 131 * 139 * 149 * 181
 66-th/103 B-smooth number: t= 3 x= 674328 factors: 2^3 * 29 * 41 * 47 * 61 * 139 * 157 * 163
 67-th/103 B-smooth number: t= 3 x= 674876 factors: 2^2 * 3^2 * 11 * 19 * 23 * 79 * 181 * 197 * 199
 68-th/103 B-smooth number: t= 3 x= 720337 factors: 5 * 89 * 137 * 139 * 211 * 227 * 239
 69-th/103 B-smooth number: t= 3 x= 736417 factors: 5 * 19 * 29 * 79 * 107 * 113 * 191 * 193
 70-th/103 B-smooth number: t= 3 x= 793144 factors: 2^3 * 13^2 * 17 * 37 * 47 * 97 * 131 * 191
 71-th/103 B-smooth number: t= 3 x= 841240 factors: 2^3 * 7^2 * 11 * 19 * 163 * 173 * 199 * 211
 72-th/103 B-smooth number: t= 3 x= 844166 factors: 2 * 3^2 * 7 * 11 * 19 * 31 * 97 * 107^3
 73-th/103 B-smooth number: t= 3 x= 909056 factors: 2^8 * 3^4 * 7^2 * 61 * 83 * 109 * 173
 74-th/103 B-smooth number: t= 3 x=1004870 factors: 2 * 3^2 * 29 * 31 * 41 * 53 * 89 * 139 * 223
 75-th/103 B-smooth number: t= 3 x=1033607 factors: 3^3 * 5^2 * 7 * 23 * 31 * 37 * 71 * 97 * 113
 76-th/103 B-smooth number: t= 3 x=1048576 factors: 2^20 * 41 * 109 * 127 * 163
 77-th/103 B-smooth number: t= 3 x=1081632 factors: 2^5 * 5^5 * 113 * 179 * 199 * 241
 78-th/103 B-smooth number: t= 3 x=1081991 factors: 3^6 * 7 * 13 * 17 * 41 * 61 * 163 * 211
 79-th/103 B-smooth number: t= 3 x=1108199 factors: 3^2 * 7 * 11 * 13 * 37 * 89 * 109 * 131 * 229
 80-th/103 B-smooth number: t= 3 x=1111880 factors: 2^3 * 3^8 * 29 * 41 * 73 * 107 * 199
 81-th/103 B-smooth number: t= 3 x=1190435 factors: 3 * 7 * 11^3 * 47^2 * 89 * 127 * 139
 82-th/103 B-smooth number: t= 3 x=1262921 factors: 3 * 157 * 163 * 167 * 193 * 197 * 199
 83-th/103 B-smooth number: t= 3 x=1280964 factors: 2^2 * 41 * 43 * 67 * 79 * 109 * 113 * 211
 84-th/103 B-smooth number: t= 3 x=1335296 factors: 2^13 * 3^2 * 13^3 * 29 * 107 * 193
 85-th/103 B-smooth number: t= 3 x=1341632 factors: 2^6 * 3^2 * 5^4 * 17 * 37 * 53 * 59 * 137
 86-th/103 B-smooth number: t= 3 x=1352359 factors: 7^2 * 17 * 19^2 * 83 * 109 * 181 * 197
 87-th/103 B-smooth number: t= 3 x=1366210 factors: 2 * 13 * 19 * 23 * 29 * 89 * 149^3
 88-th/103 B-smooth number: t= 3 x=1407564 factors: 2^2 * 11 * 23^2 * 29 * 53 * 71 * 181 * 211
 89-th/103 B-smooth number: t= 3 x=1412228 factors: 2^2 * 3^6 * 11^2 * 19 * 37 * 47 * 53 * 157
 90-th/103 B-smooth number: t= 3 x=1424320 factors: 2^6 * 13 * 17 * 71 * 73 * 83 * 107 * 149
 91-th/103 B-smooth number: t= 3 x=1431275 factors: 3 * 13 * 31 * 107 * 109 * 181 * 191 * 199
 92-th/103 B-smooth number: t= 3 x=1468832 factors: 2^5 * 3 * 5^2 * 7^2 * 13 * 53 * 67 * 107 * 167
 93-th/103 B-smooth number: t= 3 x=1518636 factors: 2^2 * 17 * 47 * 73 * 101 * 137 * 151 * 199
 94-th/103 B-smooth number: t= 3 x=1530920 factors: 2^3 * 3^3 * 13 * 79 * 113 * 157^3
 95-th/103 B-smooth number: t= 3 x=1629907 factors: 5^2 * 11^2 * 29 * 79 * 241^3
 96-th/103 B-smooth number: t= 3 x=1646382 factors: 2 * 5^3 * 47 * 53 * 67 * 89 * 151 * 173
 97-th/103 B-smooth number: t= 3 x=1684132 factors: 2^2 * 5^4 * 43 * 137 * 151 * 181 * 241
 98-th/103 B-smooth number: t= 3 x=1728280 factors: 2^3 * 7 * 11^2 * 17 * 127 * 149 * 191 * 233
 99-th/103 B-smooth number: t= 3 x=1771841 factors: 3^3 * 7 * 19^3 * 31 * 83 * 127 * 229
100-th/103 B-smooth number: t= 3 x=1817859 factors: 7^4 * 19 * 37 * 41^2 * 179 * 191
101-th/103 B-smooth number: t= 3 x=1837964 factors: 2^2 * 3^7 * 17^2 * 31 * 61 * 103 * 197
102-th/103 B-smooth number: t= 3 x=1897317 factors: 5 * 11^2 * 19 * 41 * 61 * 127 * 163^2
103-th/103 B-smooth number: t= 3 x=1942904 factors: 2^3 * 3^2 * 29 * 71 * 83 * 173 * 199 * 229
Done 103

In a few seconds we have found 103 $B$-smooth messages! We are looking for relations between them, let's look at the kernel. Furthermore, we are interested in small relations, since we will compute the corresponding values in integers. Let's apply LLL to the kernel first:

In [5]:
ml = matrix(ZZ, vecs).left_kernel().matrix().LLL()
ml[0]
Out[5]:
(0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Wow, a very small relation indeed! What does it correspond to?

In [6]:
p = 1
for i, c in enumerate(ml[0]):
    if c:
        t, x = sources[i]
        p *= (256**t*T + x)**c
        print("pad(t=%d,x=%d)^%d *" % (t, x, c))
print("= %d" % p)        
pad(t=2,x=2128)^-1 *
pad(t=2,x=3551)^1 *
pad(t=3,x=544768)^1 *
pad(t=3,x=909056)^-1 *
= 1

Ouch, fractions? We can not invert since we don't know $n$... But we don't need to! We simply move the negative power to the righthand side and get the relation that we want:

$$ pad_2(3551)pad_3(544768) = pad_2(2128)pad_3(909056). $$

Let's now collect a few smallest relations:

In [7]:
rels = []
for row in ml[:7]:
    rel = []
    for i, c in enumerate(row):
        t, x = sources[i]
        v = 256**t*T + x
        v = v**abs(c)
        if c:
            rel.append((c, t, x))
    print(
        " * ".join("pad(t=%d,x=%d)^%d" % (r[1], r[2], r[0]) for r in rel if r[0] > 0),
        "=",
        " * ".join("pad(t=%d,x=%d)^%d" % (r[1], r[2], -r[0]) for r in rel if r[0] < 0),
    )
    print(
        " * ".join(repr(long_to_bytes(256**r[1]*T+r[2])) + "^%d" % r[0] for r in rel if r[0] > 0),
        "=",
        " * ".join(repr(long_to_bytes(256**r[1]*T+r[2])) + "^%d" % (-r[0]) for r in rel if r[0] < 0),
    )
    print()
    rels.append(rel)
pad(t=2,x=3551)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=4096)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1048576)^1
'X: \x10\x00'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \x10\x00\x00'^1

pad(t=2,x=5216)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1335296)^1
'X: \x14`'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \x14`\x00'^1

pad(t=2,x=2128)^1 * pad(t=2,x=15360)^1 = pad(t=1,x=60)^1 * pad(t=3,x=544768)^1
'X: \x08P'^1 * 'X: <\x00'^1 = 'X: <'^1 * 'X: \x08P\x00'^1

pad(t=2,x=3551)^1 * pad(t=2,x=4096)^1 = pad(t=1,x=16)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \x10\x00'^1 = 'X: \x10'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=3551)^1 * pad(t=2,x=45824)^1 = pad(t=1,x=179)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \xb3\x00'^1 = 'X: \xb3'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=14342)^1 * pad(t=2,x=15360)^1 * pad(t=2,x=19112)^1 * pad(t=2,x=19882)^1 * pad(t=2,x=49637)^1 * pad(t=2,x=60284)^1 * pad(t=3,x=334844)^1 * pad(t=3,x=500696)^1 * pad(t=3,x=544768)^1 * pad(t=3,x=674328)^1 * pad(t=3,x=841240)^1 * pad(t=3,x=1081991)^1 * pad(t=3,x=1190435)^1 * pad(t=3,x=1728280)^1 = pad(t=2,x=7738)^1 * pad(t=2,x=8222)^1 * pad(t=2,x=15059)^1 * pad(t=2,x=42800)^1 * pad(t=2,x=44753)^1 * pad(t=2,x=55393)^1 * pad(t=3,x=289264)^1 * pad(t=3,x=502308)^1 * pad(t=3,x=720337)^1 * pad(t=3,x=793144)^1 * pad(t=3,x=1048576)^1 * pad(t=3,x=1412228)^1 * pad(t=3,x=1424320)^1 * pad(t=3,x=1897317)^1
'X: 8\x06'^1 * 'X: <\x00'^1 * 'X: J\xa8'^1 * 'X: M\xaa'^1 * 'X: \xc1\xe5'^1 * 'X: \xeb|'^1 * 'X: \x05\x1b\xfc'^1 * 'X: \x07\xa3\xd8'^1 * 'X: \x08P\x00'^1 * 'X: \nJ\x18'^1 * 'X: \x0c\xd6\x18'^1 * 'X: \x10\x82\x87'^1 * 'X: \x12*#'^1 * 'X: \x1a_\x18'^1 = 'X: \x1e:'^1 * 'X:  \x1e'^1 * 'X: :\xd3'^1 * 'X: \xa70'^1 * 'X: \xae\xd1'^1 * 'X: \xd8a'^1 * 'X: \x04i\xf0'^1 * 'X: \x07\xaa$'^1 * 'X: \n\xfd\xd1'^1 * 'X: \x0c\x1a8'^1 * 'X: \x10\x00\x00'^1 * 'X: \x15\x8c\x84'^1 * 'X: \x15\xbb\xc0'^1 * 'X: \x1c\xf3e'^1

The first 6 relations are very short and should be enough to recover $n$! The others are of course still usable if needed: they have a reasonable amount of terms and small powers.

In [8]:
cache = {}
def query(x, t):
    if (x, t) not in cache:
        f.read_until(b"X value:")
        assert x < 256**t
        assert x < 256**15
        bx = long_to_bytes(x) if x else ""
        bx = "\x00" * (t - len(bx)) + bx
        f.send_line(bx.encode("hex"))
        cache[x, t] = int(f.read_line().strip(), 16)
    return cache[x, t]
In [9]:
f = Sock("3.115.26.78 31337")
f.read_until("flag! ")
encflag = bytes_to_long(f.read_line().strip().decode("hex"))
n = 0
for rel in rels[:6]:
    print("rel", rel)
    vl = vr = 1
    for c, t, x in rel:
        v = query(x, t)
        if c < 0:
            vr *= v**(-c)
        else:
            vl *= v**c
    n = gcd(n, vl - vr)
f.close()
print()
print("n =", n)
rel [(-1, 2, 2128), (1, 2, 3551), (1, 3, 544768), (-1, 3, 909056)]
rel [(-1, 2, 2128), (1, 2, 4096), (1, 3, 544768), (-1, 3, 1048576)]
rel [(-1, 2, 2128), (1, 2, 5216), (1, 3, 544768), (-1, 3, 1335296)]
rel [(-1, 1, 60), (1, 2, 2128), (1, 2, 15360), (-1, 3, 544768)]
rel [(-1, 1, 16), (1, 2, 3551), (1, 2, 4096), (-1, 3, 909056)]
rel [(-1, 1, 179), (1, 2, 3551), (1, 2, 45824), (-1, 3, 909056)]

n = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157

Now comes the guessing part: we recovered $n$, so what? Even if we recover $e$ (may be it's small?) we only have the encryption oracle...

After trying basic factorization attacks on $n$, we can find that Pollard's $p-1$ works: $p-1$ is smooth for at some prime factor of $n$:

In [10]:
p = 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159
q = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523
assert n == p * q
print(factor(p-1))
2 * 269 * 1013 * 1997 * 2293 * 5477 * 6521 * 8521 * 9029 * 13729 * 15511 * 16333 * 18119 * 19963 * 24329 * 25589 * 26561 * 37889 * 38231 * 38557 * 38851 * 47881 * 49477 * 49547 * 49549 * 59009 * 63149 * 64067 * 66733 * 67807 * 70139 * 76543 * 78277 * 85621 * 85991 * 88289

This allows us to recover the public exponent too, since we can apply Pohlig-Hellman's discrete logarithm method. Sage can do it for us transparently:

In [11]:
f = Sock("3.115.26.78 31337")
msg0 = T
enc0 = query(0, 0)
f.close()
F = GF(p)
e = F(enc0).log(F(msg0))
assert pow(msg0, e, n) == enc0
e
Out[11]:
375469807216214245
In [12]:
d = inverse_mod(e, n - p - q + 1)
long_to_bytes(pow(encflag, d, n))
Out[12]:
'X: \xb2J\xb4\x82\xb6\x042!\x15\xce$\xf83\xd6\xd6nF?\x1an\xd6\xd0\xbc\xed<O>\xee\x97*"g\x14\xa6\xf0k%\xd6\xfa\xf4`\x8a{\x05\x12\x86\xfe\x1f!\xb2\xb3\x16\xbfa\x04:^~\x1bjc4\xb2\x04\xeb\xfe\x9ayhitcon{@@@[email protected]@@}\n'

Aftermath

After the CTF my colleague told me a very simple way to find $n$. In fact, it is basically the same as the 6 relations that I used, but I didn't realize their trivial structure, for example:

'X: \r\xdf'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \r\xdf\x00'^1

Clearly, there are arbitrary two messages and their copies padded by a null bytes!

Since we can append a null byte to any message, we obtain encryptions of $m$ and $256m$, and if we repeat for another message $m'$, we get:

$$m^e \times (256m')^e = (m')^e \times (256m)^e. $$

Since we obtain reduced modulo $n$ encryptions, the products are likely to be separated by a nonzero multiple of $n$, and $n$ can thus be recovered using a couple of $gcd$.