Ledger Donjon CTF 2020 - SMPC Signature

Posted on 21 Nov 2020, 18:30 in WriteUps

Donjon CTF 2020

Ledger is a company selling hardware wallets for cryptocurrencies and Ledger Donjon is the team at Ledger doing security research on Ledger's devices and, more broadly, on the whole ecosystem of hardware wallets.

Ledger Donjon logo

The Donjon CTF 2020 was held in November 2020. During the three weeks of this event, participants were asked to solve challenges in multiple categories related with cryptology and hardware security.

Izy Wallet, CryptoHackers and etbnetbhtr were the three teams on the podium at the end of the CTF. I'm rather proud to finally end up at the 8th place because I was doing this CTF alone where other participants may have worked as teams.

Crypto reminders

Since they are at the core of this challenge, here are reminders on mathematical concepts often used in cryptography. You can jump directly to the challenge solution if you already are familiar with them.

Elliptic curves basics

An elliptic curve is a mathematical object used extensively in modern cryptography. It is defined by an equation of the form \(y^2 = x^3 + ax + b\) (for some fixed parameters \(a\) and \(b\)), which means that every point \((x, y)\) that satisfies this equation lies on the curve. The most common representation of an elliptic curve looks like this:

Elliptic curve over real numbers

But in cryptography, the coordinates \(x\) and \(y\) of the points are not real numbers but instead they are defined as integers modulo some big prime number (for example modulo \(p =2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1\)). Thus, the curve doesn't look like the picture above anymore and the number of points on the curve is no longer infinite: there are at most \(p^2\) points in total. The same elliptic curve for integers modulo 89 looks like this:

Elliptic curve over finite field

Now that we have defined a set of "special" points amongst the \(p^2\) points (namely, those that satisfy the equation of the curve), we want to have a way to combine them: the point addition. A basic property of this addition is that adding a point \(P\) to a point \(Q\) gives a point \(P+Q\) which is also on the curve. Thus, just adding the coordinate is not the right approach in general.

Because we are working with a finite number of points, there is another interesting property. Given a point \(P\), we will denote \([n]P\) the point which is equal to \(P + P + P + \dots\), with \(n\) times the point \(P\). But what happen if you compute \([n]P\) with an increasing value of \(n\)? Imagine a path starting at point \(P\) and jumping from \(P\) to \([2]P\), then to \([3]P\), etc. Since the number of points is finite, we are sure that it will come a time where the path will return to a point already visited: we have found a cycle! In other words, there exists \(n_0\) and \(n_1\) such that \([n_0]P = [n_1]P\). If you choose a point in this cycle and call it \(G\), you can go over every point in the cycle just by adding \(G\) the right number of times. And if you make as much jump as the length of the cycle, you will land on \(G\) again. This structure is called a cyclic subgroup and the length of the cycle is called the order of this group.

In cryptographic applications using an elliptic curve the curve parameters \((a, b)\), a generator \(G\) of a cyclic group and its order \(q\) are given.

ECDSA

ECDSA stands for Elliptic Curve Digital Signature Algorithm. It is a digital signature scheme which purpose is to authenticate some data. A signature should be publicly verifiable and cannot be emitted without the knowledge of some secret.

ECDSA is based on DSA.

Here is an outline of how a DSA signature is computed for a message \(m\) from public parameters \((g, p, q)\), and private key \(x\):

  • First, draw an integer \(k\) uniformly at random in {1 ... q-1}
  • Then compute \(r := \left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q\)
  • Finally compute \(s := \left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q\), with \(H\) a public cryptographic hash function.

The signature is the couple \((r, s)\). One crucial thing is that the value of \(k\) is not public nor it is reused for different messages, else one can trivially compute \(x\) from the value of \(s\), \(r\) and \(m\). To avoid this, the Discrete Logarithm Problem (given \(g\) and \(r\), finding \(k\) such that \(r = \left(g^{k}{\bmod {\,}}p\right)\)) must be computationally hard. But what we will see is that \(k\) must also not have a known prefix (or suffix).

ECDSA is sensibly the same as DSA but it uses arithmetic in a group defined over an elliptic curve which makes the Discrete Logarithm Problem (given \(P\) and \(G\), finding \(k\) such that \(P = [k]G\)) harder than for modular integers.

SMPC

SMPC stands for Secure Multi-Party Computation. In "classical" cryptography, an entity usually computes a function (encryption, signature, ...) on some data before sending it over a potentially untrusted or public channel. Secure Multi-Party Computations have a different setup: now we want a given number (strictly greater than 1) of entities being able to compute together a function on some data while communicating between them using an untrusted channel or at least while not having to trust individually each party.

As we will see, in this challenge the setup is the following: we have 16 entities and we want them to be able to collectively produce a valid ECDSA signature of some data only if at least 5 amongst them agree on doing so.

Shamir's Secret Sharing

One requirement that is often needed in an SMPC setting is to be able to share a secret between a set of \(n\) parties such that \(k \leq n\) shares are needed to reconstruct the secret. One famous scheme achieving this was introduced by Adi Shamir and is thus called Shamir's Secret Sharing.

Shamir's Secret Sharing (SSS) is based on the following properties of polynomials:

  • Given \(k\) points on the plane, there exists a unique polynomial of degree \(k - 1\) or less going through them. It is computationally efficient to reconstruct the polynomial from those points using Lagrange interpolation.
  • Given \(l\) points on the plane, there exists infinitely many polynomials of degree \(d \geq l\) with real coefficients that go through them. For example, if I give you a single point \((x, y)\), you can define infinitely many line that go through this point.

For cryptographic applications, we will not work with real numbers but instead with the usual "integers modulo a big prime number". SSS for \(n\) shares with a threshold of \(k\) (at least \(k\) shares are required to reconstruct the secret) works the following way:

  • Draw uniformly at random a value \(c_0\) that will be the secret shared ;
  • Draw independently and uniformly at random \(k - 1\) coefficients \(c_i\), \(1 \leq i < k\), defining a polynomial \(P := \sum\limits_{i = 0}^{k-1}c_i.X^{i} = c_0 + \sum\limits_{i = 1}^{k - 1}c_i.X^{i}\);
  • For each of the \(n\) participants, choose \(x_i \neq 0\) and compute \(y_i := P(x_i)\), defining a point \((x_i, y_i)\) on the curve of \(P\).

Each point \((x_i, y_i)\) is a share of the secret. Now, to reconstruct the secret \(c_0\) from at least \(k\) shares, one just need to reconstruct the polynomial using Lagrange interpolation thus revealing the value of the constant coefficient \(c_0\), ie. the secret.

An additional property of SSS is used in this challenge and can be stated as follows: given a point \((x, y)\) on the curve of a polynomial \(P\) and a point \((x, y')\) on the curve of a polynomial \(P'\), the point \((x, y + y')\) lies on the curve of \(P + P'\). Thus, given the shares of \(c_0\) and the one of \(c'_0\), respectively \((x_i, y_i)\) and \((x_i, y'_i)\) for \(0 \leq i < n\), the shares \((x_, y_i + y'_i)\) are valid shares of \(c_0 + c'_0\). 1

Lattices

A lattice is yet another mathematical object. It is a structured set of vectors in \(n\) dimension with coordinates in \(\mathbb{R}\) or \(\mathbb{Q}\) where each vector can be represented as an integer linear combination of the vectors of a basis. In two dimension, a lattice will look like this:

Lattice with random basis

The pink vectors together are a basis of the lattice: the pink points can all be reached by adding (or subtracting) an integer number of time the two basis vectors.

In the case, of a random basis as in the picture above, some problems can be harder than for a carefully chosen basis. For example, try to find the right combination of the basis vector to reach a point close to the origin. This is called the Shortest Vector Problem (SVP) and, with the right parameters (more importantly, in higher dimensions), it can be computationally hard to solve.

A non-trivial approach of this problem (and of some other problems on lattices) is to use an algorithm designed in the 1980s by two brothers Arjen and Hendrick Lenstra and by László Lovász. This algorithm is called the LLL algorithm and it is able to find a "better" basis (with shorter and "more orthogonal" vectors) of the lattice studied. In the lattice shown above, the LLL lattice reduction algorithm would lead to the following basis of the same lattice:

Lattice reduced using LLL

Having a basis with shorter vectors may be sufficient to instantly solve an instance of the Shortest Vector Problem or at least of its approximate version.

In fact, this algorithm is so powerful that it can also be used to solve other problems that seem at first unrelated to lattices. For example, with the right reformulation of the problem, LLL can be used to improve the search for a solution of some instance of the Knapsack problem.

SMPC Signature

Now that you know the basics of the concepts used, here is the challenge we were asked to solve during this CTF.

Challenge description

This challenge was the only 500-points challenge in the "Crypto" category. I managed to solve it before everyone else did and at the end of the CTF we were only four participants to have solved it.

Here is the description that is given to us:

# Secure Multiparty Computation ECDSA Signature

Some organisation has been using ECDSA to sign some important data.
In order to avoid the secret key from being compromised, it was split in 16 fragments that were distributed to parties in a way that at least 5 parties need to share their fragments in order to recover the secret key.
Then, the organisation implemented a custom program that is able to sign data if enough parties agree, without requiring anyone to share their secret fragment.
This works thanks to a Secure Multiparty Computation algorithm based on the one used by the Ren Project (https://renproject.io/), which has been specified in https://github.com/renproject/rzl-mpc-specification/tree/33a60237eb5eb3ec617d125f533368683cfca628.

When signing some data, the encrypted packets that are exchanged between the participants are recorded into a log file.
A few days ago, some unknown attacker managed to breach into the network and to exfiltrate one of these log files (smpc_trace.log).
This attacker then managed to recover the secret key, even though he did not have any fragment!
So there is a critical vulnerability in the implementation.
Can you find it and recover the secret key?

When you find the secret key, please use get_flag.py to generate the flag.

As written in this description, we were given (very well-engineered) Python scripts that implements the Secure Multi-Party Computation of an ECDSA signature following the scheme described by Ross Pure and Zian-Loong Wang for Ren.

The scripts are split in three files:

Additionally, we have smpc_trace.log, the log of the communications between the parties while they are signing some data, as well as public_key.pem the corresponding public key. In fact, we will only need the signatures (which are valid ECDSA signatures that can be verified with the public key) to solve the challenge and not the communications between parties.

Challenge solution

Weak generation

As explained, to compute an (EC)DSA signature a value \(k\) must first be drawn. In the case of SMPC protocol used, computation must be done on \(k\), without any set of strictly less than 5 parties being able to retrieve its actual value. To do so, the following two functions are used:

Python Source code
RANDOM_BITS = 64

async def smpc_biased_rng(self) -> int:
    """Implement Biased Random Number Generation algorithm"""
    # Generate random shares for other parties
    coefs = [secrets.randbits(RANDOM_BITS) for _ in range(self.smpc_k)]
    for peer_channel in self.active_channels.values():
        value = 0
        for power, coef in enumerate(coefs):
            value = (value + coef * pow(peer_channel.peer_secret_x, power, SECP256K1_ORDER)) % SECP256K1_ORDER
        peer_channel.send_encrypted(value.to_bytes(32, "big"))

    # Compute my own share
    brng_share = 0
    for power, coef in enumerate(coefs):
        brng_share = (brng_share + coef * pow(self.secret_x, power, SECP256K1_ORDER)) % SECP256K1_ORDER

    # Receive shares from other parties
    for peer_channel in self.active_channels.values():
        share_from_other = int.from_bytes(await peer_channel.recv_exactly_encrypted(32), "big")
        brng_share = (brng_share + share_from_other) % SECP256K1_ORDER
    return brng_share

async def smpc_unbiased_rng(self) -> int:
    """Implement Unbiased Random Number Generation algorithm"""
    coefficients: List[int] = []
    for _ in range(self.smpc_k):
        coefficients.append(await self.smpc_biased_rng())

    for peer_channel in self.active_channels.values():
        value = 0
        for power, c_share in enumerate(coefficients):
            value = (value + c_share * pow(peer_channel.peer_secret_x, power, SECP256K1_ORDER)) % SECP256K1_ORDER
        peer_channel.send_encrypted(value.to_bytes(32, "big"))

    value = 0
    for power, c_share in enumerate(coefficients):
        value = (value + c_share * pow(self.secret_x, power, SECP256K1_ORDER)) % SECP256K1_ORDER

    shares: List[Tuple[int, int]] = [(self.secret_x, value)]
    for peer_channel in self.active_channels.values():
        share_from_other = int.from_bytes(await peer_channel.recv_exactly_encrypted(32), "big")
        shares.append((peer_channel.peer_secret_x, share_from_other))
    return sss_recover(shares)

In short, the random number generator works the following way:

  • First, each party \(i\) draws uniformly at random an integer \(k_i\) between 0 and \(\mathbf{2^{64}}\);
  • Then, each party \(i\) split \(k_i\) into 16 shares \(k_{ij}\) using Shamir's Secret Sharing and send \(k_{ij}\) to party \(j\);
  • Finally, each party \(j\) sum all \(k_{ij}, 0 \leq i < 16\) modulo \(q\) giving \(k'_j\).

With this protocol, and because of the property explained before for addition of shares, each \(k'_j\) is in fact a valid sharing of \(k := \sum\limits_{i=0}^{15}k_i\).

What's wrong with it, you may ask? The problem here is that, in the (EC)DSA protocol, \(k\) need to be drawn uniformly at random between 0 and the public parameter \(q\). In our case, as we have seen in the reminder about elliptic curves, \(q\) is equal to the order of the cyclic group generated by \(G\). Here, each \(k_i\) is taken between 0 and \(2^{64}\) thus the final value is between 0 and \(16\times2^{64}\) but \(q\) is equal to 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 which is almost equal to \(2^{256}\).

Thus, when representing \(k\) as a string of 256 bits, we know that the \(256 - 68 = 188\) most significant bits are always equal to 0.

The actual generation of the secret k is in reality a bit more complex. The function smpc_unbiased_rng is there to ensure that the sharing is uniform. In fact, even if the secret k hidden by the smpc_biased_rng function is uniform (when at least one party is honest), its sharing may not be so in presence of a malicious party. Nonetheless, smpc_unbiased_rng returns to each party a share that, combined, gives the same secret k as the shares returned by the first call to smpc_biased_rng. Thus, it has the same flaw: it is only taken between 0 and \(2^{68}\).

Retrieving \(k\)

We will now explain, without going in depth, how does the attack works from here. For more details, you can check this article by Breitner and Heninger. The fact is that in (EC)DSA when the \(k\) value (often called a "nonce" because it must be used only once) is not taken uniformly at random in all the possible values, it's possible to apply a class of attack based on a lattice representation of this problem. 2

In our case, for each signature, the expression of \(s\) can be seen as a modular equation. In smpc_trace.log we have different signatures, with different \(k\)s. Thus, our problem can be reformulated as a system of modular equations, one for each signature. Since it is underconstrained (one \(k\) and \(x\), the private coefficient, both appear in each equation), there are multiple valid solutions to this system and we can't just solve it using regular linear algebra. But we have another information on the values of the different unknown \(k\)s: they are really really small (between 0 and \(2^{68}\), in a space almost \(2^{188}\) times bigger).

From this system, we can define a basis such that finding a short vector in the corresponding lattice reveals the value of the \(k\)s used in the signature. To find a short vector, one can use a basis reduction algorithm (here, LLL is used). As seen before, retrieving the value of any \(k\) used in a signature allows to trivially compute the value of the private key \(x\).

The following sage script implements the attack.

Sage source code
sigs = [
        (54062599949533570768481067279120692156137985130084718412343598495044602503191, 80258273781253291739780015186361918151947778269292572104553731139027879553195),
        (46636440372569168811229894524106432185563295832262321574877674258238059617431, 8977272425154588925793710437227738821117999974990649929069377419862384005820),
        (74068884789311113136742309388801526049250324413675245755382496712283981371896, 17982769657605846779081087699425464854212768841254947783400266140760783995030),
        (58475174745688464821559250964327220227396868798752664843345796074038422834897, 89431884715541300644903937272937949719237941805574117300891414640647891994920),
        (98043578076750586399470709903610513766338211124602907658119206821627913841500, 112445028488108500100962784117687141454381857344623733333088378612187168744922),
        (82395005897433204978931055291746506752997269161045816011507886723200512100026, 56291365616056427404727637801679616441535767210295140241920585034027340106723),
        (25333331596907371225721277244818880430558974151662471668735022928780748564460, 114174212507189293050312853204891470043637988143606811215137987790002510898167),
        (56379279287411106078729657235205719939168943955619418158508267768661619512720, 21286044287633376792895070090740150626639597426195161585030980651831667468918),
        (92562663951359870693325718224091023702232358482078210417751698609528342229560, 83396695238355405080652003698286117889249538082466672490680430698628826698297),
        (115077453667133708192593320133159106427000900429911482391117737956198883472268, 61954803716787654672003594637510885168388736762329414999234019882698912454253),
        (54283757868525882885292432395869902756458193177943742890994724257603562234017, 50309134197591319426194000488323081306504174758107459258550085528426997329746),
        (86923982590256663932640870400302754752611818949054869030418136370094240788072, 71144264531235528401509417517635534924601963012512603705868726103451152277729),
        (106356952587189171759304600901267533034334483575344418478949097839002627879358, 15867732118535334648324120574033659880265492564705334483840918262545427878263),
        (113739375203345094148908875527844223565193130861372149760286148158877846905244, 29791189851963425314301416295225176557137333663352443264608496946865565782188),
        (34294312228157492146845507742369732503780455513770529151115521692676701820124, 4445696888288574414655495980755136640832813539197692606133647193296381339407),
        (9805902748736649851160384350239571877174912322668932842696690874297449320515, 38084284877728880103949849348914274673829767904419074429386309754512981680633),
        (45308993850912860576355545803549062696208974458007537383008113840894661481997, 8429046633964876270318469609843329482861801502679502734630041690809813642529),
        (5416445189745996189367850454665101452672157867127242003049853307841344260339, 105960517497361609860982953091472832631587498850836222772301687284223008035925),
        (99871896894231400655334045991072295298863680553807224415303492246254586833191, 60283594191894316309833305190430442784065825802168951892472208664697580829229),
        (8615182964837587117248032398408815583263865773124362242686716520644021440360, 76445347489005780668609195383338534109879120813153244616993929950402645306716),
        (90393318059739510992604693985628674001608754220525684766606983316991064956799, 6597040838109456937001021559872823601402321755544981935497078710214879524451),
        (115708170600616589986324676258647194738578249078804381355005154750478563129017, 23012350275019282392531679875818086155594230882910415625003824591097729959248),
        (40403825331325709437727583858602365600368105262385995431646598372030833375332, 61141957613212138324253495931679411476426452876294011803552633076776055396815),
        (92855411678415475066975947788474923892137203572851319752485164318874576976320, 18227868742869528149993149011020450920262942368440802247783874139871319101890),
        (54535018628452763955825218657229562311898963519447416414296551803486436173804, 53937045945598759373020775176098342129703322663986643641701371236512734817638),
        (103775078619250914156616320404752911265673596434768330462180302225888254744673, 34032585906122822446383086468237041482803431717597285274748901319365862536787),
        (40364714872196887053805828796014530764586898029366190080915441972071274620490, 58792569651904763229412787314502485511274570131481518043809543207616936459224),
        (88058655069406618991362900488448620980798245521985935336328289291398774244571, 38560963034459506345233382046345773561183975861080227345112261135653425988966),
        (95730859952110020224025003998637155320994354202749549627266700817515957900247, 47310007269524055851041628222917654906841955121586019759835095617935110413039),
        (40805996824799590981172260885601975334719290169278268334197589374435390969922, 96268399456178515835007019935551900076236742006466378330408309194475217213895),
        (3957924225326779150561851088595158510834100088400177955823739970209707828373, 109495975252942453637215427062371997576063305516671417465303890091719234528140),
        (78328683425586512630038124337234665248532396780994273039088009954116009661330, 17540915173459378803733703342970573492928166898073910825204921371943582114942),
        (68721611633500588357480199283741091275250314420197145582010603462954849410615, 113352581844457058743166557904757142107060700244211587167848592112811359549517),
        (24169585101721687781543881553555589662544226151689981391263582836602714412054, 21389338690444766536440404519296380576226263586174287132811470807041171424037),
        (113359846337210058456180378840522016416223746676488945663690943604028737673016, 15055424317021716988997724696889178743508396410568526963490961752995568406279),
        (34901351094264913369571867241086411310390846525382631823543838735195651431173, 3454142356446136323914773787451023343554459797346941115736366208879406160856),
        (54712474909777804290788470231694820800471704799149841008498537413152697671408, 27149625143300267905624527701629262775299717923288173701712889812408858166507),
        (60711835165132966822847291819711379660076948184506998530032869659622316798662, 93111016192346512100610687132499146335132693527596099593262012919814021026610),
        (35110475686886040882771111036093688016016347113547033450996578058430146098490, 77172909360958085427363468337033939891628013162221852714414955453371909343782),
        (56430372845365447641827580725969245136099934576135001531899870823525971386529, 28903750545184877684522337615126102734132526978042616220548978017192729701134),
        (103733599164992532955818228079764559856989892641220024055078410551725864573826, 108946144156206487386250924545335706322656946331861275568848181504319635879248),
        (55913571825701538009993736158465322697379582656237963797876166663899081823492, 70146150681786017774516419391729508625293647586445605794283683286018052133021)
        ]

h = 49336014789726221425645034889532154763255157700418396653166559400071907231390 # Integer value of SHA256("👋 Hello, world 🌍 🎉")
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Elliptic curve order
B = 2**69 # Known upper bound on the value of k

def attack():
    # First: Construct the basis with the right values
    basis = []
    for i in range(len(sigs)):
        v = [0]*(len(sigs)+2)
        v[i] = q
        basis.append(v)

    vt = [0]*(len(sigs) + 2)
    va = [0]*(len(sigs) + 2)

    vt[-2] = B/q
    va[-1] = B

    i = 0
    for r, s in sigs:
        sinv = pow(s, -1, q)
        t = int(sinv*r)
        a = int(sinv*h)
        vt[i] = t
        va[i] = a

        i += 1
    basis.append(vt)
    basis.append(va)

    # The vector elements are not integer, but rational numbers
    M = Matrix(QQ, basis)

    # Reduce the basis using LLL
    reduced_basis = M.LLL()

    # This vector in the reduced basis is our solution
    # Found by looking at its norm and shape
    sol = reduced_basis[1]

    # Compute the private key x for each signature and verify that they are all equal
    x = [(sigs[i][1]*Mod(k, q) - h)*pow(sigs[i][0], -1, q) for i, k in enumerate(sol[:-2])]
    assert all([xi == x[0] for xi in x])

    return x[0]


if __name__ == "__main__":
    x = attack()
    print("Private coefficient: {}".format(x))

From the private key \(x\), we can use the script get_flag.py given by the authors of the challenge to get the following flag: CTF{weak_RNG_strikes_back_again}.

  1. To see this, just write \(P + P' = \sum\limits_{i=0}^{k-1}c_i.X^{i} + \sum\limits_{i=0}^{k-1}c'_i.X^{i} = c_0 + c'_0 + \sum\limits_{i = 1}^{k-1}(c_i + c'_i).X^{i}\).
  2. In the same article, the authors investigated a real-life example of this attack. They found 5,863 vulnerable signatures linked to 280 distinct keys in the bitcoin ecosystem. These signatures used 64-bit values for \(k\). The likely culprit is a commit in a JavaScript bitcoin library that draws \(k\) from an array of 8 random bytes. It was fixed a month later but vulnerable signatures were emitted until almost one year later.