The idea of this crackme is a challenge: to generate a single ECDSA signature for two different messages (computed from the username). The cracker gets free choice of the public key QA and the randomized parameter k.
Two messages, one signature? It's impossible right?
Well after many lonely mornings in front of the glow, it really is possible!
The spoiler is that in the ECDSA signature verification computations, only the x-coordinate of the computed point is checked. For each x-coordinate on a curve over Fp, there are two y-coordinates (two distinct points total, inverses of one another for point arithmetic on the curve). Here is a good example from Certicom's ECC Java applet:
Given some point k*G, where k is an integer and point G is the generator, you don't have to do anything difficult like the ECDLP to find -(k*G). One of the six generators is G=(17,10). Calculating 1*G, 2*G, ... this generator produces:
(17,10), (16,15), (15,03), (09,18), (21,17), (01,18), (11,10), (18,13), (20,04), (13,05), (19,22), (00,00), (19,01), (13,18), (20,19), (18,10), (11,13), (01,05), (21,06), (09,05), (15,20), (16,08), (17,13), (inf)
The inverse points are mirrored around the (0,0) point in the middle of the sequence. We can put this symmetry into a simple formula:
k * G = -((N-k) * G)
Where N is the order of the generator. Like in the above picture, P and Q are inverses. But suppose we didn't know this beforehand, and only knew that P=14*G. We could discover Q by calculating (24-14)*G = 10*G = Q.
Ok so we can find the two inverse points easily in terms of a coefficient and a generator point. Now just try to get the two separate messages to have these two separate points as signatures. See my solution for more detail.
It is mentioned in WiteG's comment that it has been keygenned by jB before, a known keygenning master. If I find the time I will his solution and maybe add some more comments.
No comments:
Post a Comment
thanks for commenting!