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

^{2}) 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(a

**P**, b

**Q**) = 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**, a

**P**, and b

**P**, but cannot compute the shared secret ab

**P**. But if Eve were handed the shared secret among a thousand other random group elements, could she discern ab

**P**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**, a

**P**, b

**P**, ab

**P**) Eve tests e(

**P**, ab

**P**) = e(a

**P**, b

**P**) = e(

**P**,

**P**)

^{ab}.

Now look at it from a public-key standpoint. Suppose I publish

**E**=<

**G**>, x

**G**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 x

**P**, just not x. You'd then have (

**G**, x

**G**,

**P**, x

**P**) and could verify e(

**G**, x

**P**) = e(x

**G**,

**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(b

**G**,c

**G**)

^{a}, e(a

**G**,c

**G**)

^{b}, e(a

**G**,b

**G**)

^{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 x

**P**is renamed the signature

**S**. Verifying the signature is verifying the tuple (

**G**, x

**G**,

**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)As expected from the BN curve algorithm, we have a prime order curve. This means that r=#

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

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

*E***g1**> to detach it from

**since we'll be moving**

*E***over larger fields.**

*E*Over increasingly extended fields, #

**grows, fast. Not until extension 12 (the embedding degree) does the group**

*E***(F**

*E*_{p12}) contain

**[r**

*E*^{2}].

sage: E=EllipticCurve(GF(9524793152874449521^12,'a'),[0,0,0,0,13])That's a lot of points!

sage: E.order()

557527939388338455999335177184553128648411435525495183120877629267756649506692825601416365268161565197227820626524244139422343537066988585815195692298420149498809296111861768128843274828063908967761768686256781963953791177011200

**[r**

*E*^{2}] is the direct product of

**G1**and some other r-sized subgroup in

**. To find G2, we take a random point and multiply by #**

*E*we'll call G2**/r**

*E*^{2}.

sage: g2=E.random_point() * Integer(E.order()/r^2)We see that

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)

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

**[r**

*E*^{2}] can be generated; every element in

**[r**

*E*^{2}] can be written as a*

**g1**+ b*

**g2**where a,b from Z

_{r}.

We'll have the pairing map G1 x G2 -> F

_{p12}. 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 = 1223334444333221111To 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

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)

**g1**. Suppose the name converts to 123456, then the signature is simply:

sage: M = 123456*g1You 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 (

sage: M

(5525487180627916384 : 8968938521026939071 : 1)

sage: S = x*M

sage: S

(7298443986699715260 : 507887173084537875 : 1)

**g2**,

**P**,

**M**,

**S**) = (

**g2**, x*

**g2**, 123456

**g1**, 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)All the same result! Sanity check passed! Here's an attempt to diagram the entire process. Please don't trust this for correctness:

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

dcoder is teh man.

ReplyDeletewhy i need a quick serial I send him the binary, he loads it up in IDA and tells me a valid serial.

he's like a human keygen ;)

actually NOT joking, true story.

HolyShit!!!, It took me sometime to understand Elliptic Curves & I cant say that I understand all its mathematical properties even now & this pairing stuff just went tangent to my head :p

ReplyDeleteI tried reading it up, but after 15 mins I had a bad headache :p (True Story) :D

btw excellent work Dcoder__ & Andrewl :)

br

KKR

Hey Bro,

ReplyDeleteWhat happened to crakmes.de?

--Obnoxious