Shmoocon 2011 Crypto Pack Solved! And Pairings And SAGE!

I'm happy to announce a thorough and impressive solution to all the Shmoocon 2011 cryptography challenges by crackmes.de denizen Dcoder.

Not long after Dcoder's solve, user ged_ posted valid serials for his name, but sadly never supplied an explanation of his methods.

Like stated previously, the choice of python and the simplicity of the first few challenges were intended to entice contenders into actually doing the challenges. The 4'th and 5'th challenge were to inject some new material into the keygenme problem space and that's what I'll discuss here.

Challenge 4 is a large rational function calculating the "multiply-by-m" map of a point on an elliptic curve. Formulas exist to add and double points, so it's sensible that they may be composed to derive formulas for multiplication by a given coefficient. This is just a giant formula for multiplying by 13. No way could you take care of the algebra by hand: I used SAGE's EllipticCurve function multiplication_by_m() which Dcoder independently used when he suggests recreating the map for verification. A guessing game wasn't intended: the degree of the polynomial being 169 (13²) is a clue. Blackboxing the function is even feasible.

Challenge 5 is the BLS short signature scheme using pairings on elliptic curves. Pairings are freaking magic and here I'll try to explain why. We'll have the typical mapping from an elliptic curve group (where the group operation is written as addition and thus repeated operations are written as multiplication) to the multiplicative group of an extension field (where repeated operations are written as exponentiation). Thus we write the bilinear property as:

e(aP, bQ) = e(P,Q)^ab

So the map doesn't care if you first multiply the points and then ask for output, or if you ask for the output and then exponentiate the result. Why is a mapping with this property useful?

Recall the computational DH problem (CDH) by thinking of the eavesdropper's perspective of an DH key exchange. Eve views P, aP, and bP, but cannot compute the shared secret abP. But if Eve were handed the shared secret among a thousand other random group elements, could she discern abP from the decoys? This is called the decision DH problem (DDH) and is solvable if the group is equipped with a pairing. How? Given (P, aP, bP, abP) Eve tests e(P, abP) = e(aP, bP) = e(P,P)^ab.

Now look at it from a public-key standpoint. Suppose I publish E=<G>, xG but keep x secret. You could challenge my claim of knowing x by asking me to multiply it on a new point P. I'd return xP, just not x. You'd then have (G, xG, P, xP) and could verify e(G, xP) = e(xG, P) = e(G,P)^x.

If this isn't magic enough, think now how you can operate on e(G,P)^x without knowing x. The pairing kind of exposes the x for involvement in future computations without explicitly revealing its value. Three-party key agreement is the clearest use of this property. When the three parties {A,B,C} compute respectively {e(bG,cG)^a, e(aG,cG)^b, e(aG,bG)^c}, everybody arrives at e(G,G)^abc, yet each party knows only the value of their own {a,b,c}.

The BLS signature scheme is is exactly the same as the first example with DDH above, except that the challenge point P is the message mapped to a point, and the xP is renamed the signature S. Verifying the signature is verifying the tuple (G, xG, P, S).

There are a few pairings now, but the Weil pairing is seemed like the "hello world" of pairings and still it was very difficult to get working. I owe mostly to Ben Lynn for writing his thesis in a clear, explanatory fashion and not being too "math leet" to include worked examples. Also, I had a bug when evaluating points on lines that went through infinity and couldn't have figured it out without David Hanson's Weil pairing implementation in SAGE.

Producing curve parameters is an entirely separate problem. The paper on BN (Barreto, Naehrig) curves had an algorithm that wasn't too difficult to type out and test. Here's the implementation in SAGE. Finally crypto5 can be constructed:

sage: [E,g1] = search_embed_12(64)
Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 9524793152874449521
(1 : 4577206343548535956 : 1)
sage: r = E.order()
sage: is_prime(r)
True

As expected from the BN curve algorithm, we have a prime order curve. This means that r=#E and every point is in the r-torsion E[r]. This r-torsion's definition is a subgroup whose elements' orders divide r, but here every elements' order is exactly r. Call this group by a new name G1 = <g1> to detach it from E since we'll be moving E over larger fields.

Over increasingly extended fields, #E grows, fast. Not until extension 12 (the embedding degree) does the group E(F_p¹²) contain E[r²].

sage: E=EllipticCurve(GF(9524793152874449521^12,'a'),[0,0,0,0,13])
sage: E.order()
557527939388338455999335177184553128648411435525495183120877629267756649506692825601416365268161565197227820626524244139422343537066988585815195692298420149498809296111861768128843274828063908967761768686256781963953791177011200

That's a lot of points! E[r²] is the direct product of G1 and some other r-sized subgroup in E we'll call G2. To find G2, we take a random point and multiply by #E/r².

sage: g2=E.random_point() * Integer(E.order()/r^2)
sage: g2.order()
9524793149788155121
sage: g2
(28930072329430674*a^11 + 3476916985694553167*a^10 + 7416446501236864153*a^9 + 1546806533803993509*a^8 + 9258625410126221791*a^7 + 3946459769382694037*a^6 + 9082757750092742366*a^5 + 4925994372571715422*a^4 + 9356115311475410715*a^3 + 3239246275650681784*a^2 + 2530023797852594208*a + 2582477270547956977 : 4569041207989982512*a^11 + 392122047555439583*a^10 + 53398003196643395*a^9 + 2471082114350274565*a^8 + 3769727620341931341*a^7 + 2253879482993753613*a^6 + 7323759157123465679*a^5 + 1956558743620835276*a^4 + 1065433853209237195*a^3 + 8009494946720473686*a^2 + 8874621118513866374*a + 544373368025887171 : 1)

We see that g2 is not in G1 and its order is the prime r so G2 = <g2>. Now, g1 and g2 together form a sort of basis by which all of E[r²] can be generated; every element in E[r²] can be written as a*g1 + b*g2 where a,b from Z_r.

We'll have the pairing map G1 x G2 -> F_p¹². The input groups must be different, otherwise the points will be linearly dependent and the pairing will become degenerate. G1's members' coordinates have a nice compact representation of a single ground field element while each of G2's members's coordinates require 12 ground field elements. The public key P should then live in G2 while the signature S lives in G1. Choose private key x and compute:

sage: x = 1223334444333221111
sage: P = g2*x
sage: P
(9234041514029458289*a^11 + 7779915664763212307*a^10 + 6346523241154805362*a^9 + 5513000999900352828*a^8 + 7183243026634094341*a^7 + 6887819078187130363*a^6 + 5522347192587339249*a^5 + 832499822664426562*a^4 + 1305341026780126317*a^3 + 5936146128578535690*a^2 + 474243480778556212*a + 6400173802196845754 : 4965553112357672903*a^11 + 3816268899954016796*a^10 + 359467867455554913*a^9 + 212427926173001815*a^8 + 5152204995298522178*a^7 + 915090504523216963*a^6 + 8111126461946895687*a^5 + 318194623178172360*a^4 + 8053089739653482422*a^3 + 171210160812342620*a^2 + 6985863117841018225*a + 122495515023342804 : 1)

To convert a message (the user name input to the crackme) to a point in G1, we just convert the name to a number and multiply generator g1. Suppose the name converts to 123456, then the signature is simply:

sage: M = 123456*g1
sage: M
(5525487180627916384 : 8968938521026939071 : 1)
sage: S = x*M
sage: S
(7298443986699715260 : 507887173084537875 : 1)

You can store just one of the coordinates and a bit to distinguish candidate roots when solving the other coordinate. Despite sections in the BN paper specifically aimed at helping the reader compress points by solving cube roots, I failed to understand and implement this in time and the crackme had to be supplied with both coordinates :( You can hardly call this a short signature. Anyways, verifying the signature now is verifying the DH tuple (g2, P, M, S) = (g2, x*g2, 123456g1, 123456x*g1). We compare e(x*g2, M) with e(g2, 123456x*g1) and hopefully get e(g2,g1)^123456x:

sage: g2.weil_pairing(S,r)
3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371
sage: P.weil_pairing(M,r)
3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371
sage: g2.weil_pairing(g1,r) ^ (123456*x)
3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371

All the same result! Sanity check passed! Here's an attempt to diagram the entire process. Please don't trust this for correctness:

To forge signatures... well that's the cracker's job. Read Dcoder's solution to learn how, along with quick ways to destroy the other challenges. Thanks and congratulations again to him, a clear champion among keygenners!

http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/solution/dcoder