PlaidCTF 2016 – Radioactive (Crypto 275)

We just got this fancy new cryptographic device and it seems to work great… for the most part. But sometimes the values it gives me are wrong. Maybe you could take a look for me.

radioactive.tar.bz2

Summary: fault attack on RSA signature (not RSA-CRT)

Inside we have three files: flag.enc, log.gz and README. Here’s the README:

So I have this key signing service, but it's next to this big.. glowy thing.
If I ask it to sign the same thing twice, I sometimes get different results!
 
I don't think I have a bug in my code.. all I do is
 d = radioactive_storage.load("d")
 n = radioactive_storage.load("n")
 g = int(raw_input())
 return pow(g, d, n), n
 
I attached a log of what I mean, maybe it will help you diagnose the issue.

We can interpret it like this: $d$ or $n$ may be corrupted before the computations, but the computations themselves are correct. Note that there is no separaion on $p$ and $q$ here, hence the well known fault attacks on RSA-CRT will not work here. That is, taking a few gcd‘s won’t do the job.

The flag.enc file obviously contains an encrypted flag and log.gz contains 1500 triples of the form (sent $g$, retrieved $g^d \mod{n}$, retrieved $n$).

How can we exploit corruption of $d$? Assume that we know that the fault consists in flipping some bit of $d$, resulting in $d’$. Then we know that $g^{d’} = g^{d’\pm 2^k}=g^{2^k}g^d$. We can check this for all $k$ less than size of $N$. If we find that $d’ = d + 2^k$, then we know that $d$ had zero bit in position $k$, otherwise there will be more changes due to carry propagation. Similarly, if we see that $d’ = d – 2^k$, then we know that $k$’th bit is $1$, otherwise carry would touch more than one bit. But this way requires assumption about bit flipping faults and we can recover only ~50 bits of $d$ from different positions. If we had an access to the faulty oracle, then we could recover all the bits in such way. But from the given log we don’t have enough triples.

Then, how can we exploit corruption of $n$? Consider an edge case – what if we learn $g^d \mod{p}$ for some small prime $p$? We can compute the discrete logarithm modulo $p$ and recover $d \mod ord_p(g)$. That is, we gain some information about $d$.

Obviously, it is very unprobable that $n$ is corrupted into a small prime. But it is very possible that corrupted $n$ has a small prime factor! Thus, we can try to factor out small primes from the corrupted modulos and recover lots of information about $d$.

And then we can join all this information using Chinese Remainder Theorem to obtain $d \mod{lcm(m_1,m_2,\ldots)}$, where $m_1,m_2,\ldots$ are the previous modulos (orders of respective $g$). Let’s see how much we can get. Here’s a Sage script:

ps = list(primes(10**7))
 
f = open("slog")  # sort -u log >slog
 
N = 128252385158999798650478619915390348219127455402754689089261593737448863301830850674971570556378141585421543279992130969111964989833589473502693007444433776166136517668072138209463294411651789727827877583581930984842125108249744730094086909309185568218796494490149921734990907802684240383885623446995532878367
E = 0x10001
 
curd = 0
curmod = 1
while True:
    l = f.readline().strip()
    if not l:
        break
    g, gd, n = map(int, l.split(", "))
    if n == N:
        continue
    for p in ps:
        if n % p:
            continue
        mod = 1
        while n % p == 0:
            n //= p
            mod *= p
 
        # lazy to handle other cases
        if gcd(g, mod) != 1:
            continue
 
        z = Zmod(mod)
        newmod = z(g).multiplicative_order()
        newrem = discrete_log(z(gd), z(g))
        print "%d mod %d" % (newrem, newmod)
        curd = crt([curd, newrem], [curmod, newmod])
        curmod = lcm(curmod, newmod)
 
print "Finished", "mod size", curmod.nbits()

In 30 seconds we get 582-bit modulus (let’s call it $M$)! Recall that size of $n$ is 1024 bits. There exists an attack which allows to factor $n$ when quarter of the bits of $d$ is known and we have even more than a half! Actually, we can make a quite simple attack.

Consider the equation $ed – k(n – p – q + 1) = 1$. We can reduce it modulo $M$ and use the knowledge of $d \mod {M}$. Also note that $k$ is less than $e = 65537$, therefore we can check all candidates for $k$! As a result, we can recover the value of $p+q$ modulo $M$, but since $M$ is larger than 513 bits, that value will be equal to $p+q$ without any reductions. Then we can solve a simple quadratic equation over integers to recover $p$ and $q$. Here’s the script:

N = 128252385158999798650478619915390348219127455402754689089261593737448863301830850674971570556378141585421543279992130969111964989833589473502693007444433776166136517668072138209463294411651789727827877583581930984842125108249744730094086909309185568218796494490149921734990907802684240383885623446995532878367
E = 0x10001
 
drem = 111548247099426273389948507953833349793581006224434222496170188807812542432248571343054254439167042364761271083138602731106930981638865930562124831007293288177676704938822593
dmod = 10274028805726112705913850295896303264348652981631836133118572817617200621634370718771916760166640218221053248064436048608818372150752407015086987656246659129922719605007864000
 
for k in xrange(1, E):
    if k % 1000 == 0:
        print k
    kpq = (k * (N + 1) - E*drem + 1) % dmod
    g = gcd(k, dmod)
    if kpq % g:
        continue
    k /= g
    kpq /= g
    mod = int(dmod / g)
 
    k = int(k)
    pq_sum = (kpq * inverse_mod(k, mod)) % mod
 
    # solve p^2 - pq_sum*p + N = 0
    b = -pq_sum
    c = N
    dsc = b**2 - 4*c
    sqrtD = int(sqrt(dsc))
    if sqrtD**2 != dsc:
        continue
 
    p = (-b + sqrtD) / 2
    p = int(p)
    if N % p == 0:
        print "Factored:"
        print p
        print N / p
        print
        break

And in 40 seconds we get $k = 22408$ and factorization of $n$.

Then we decrypt the flag.enc: its_okay_luckily_bits_never_flip_in_the_real_world.