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.

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

## 2 comments

## 2 pings

From where have you got the value of e (65537)?

Author

That’s the exponent which is used almost always. But to be sure you could check that it is valid by checking pow(gd, e, n) == g.

[…] http://mslc.ctf.su/wp/plaidctf-2016-radioactive-crypto-275/ […]

[…] Then it may be that the server flips some single bit of the secret exponent sometimes. There was a similar challenge already at this year’s Plaid CTF, but there we didn’t get enough […]