MR.HAANDI's WeakDSA
| Download weakdsa_keygenme.zip, 8 kb (password: crackmes.de) Browse contents of weakdsa_keygenme.zip This is a non-standard DSA implementation containing a very specific weakness. Spot it and use some math.
Difficulty: 5 - Professional problem to solve | RatingVotes: 5 View profile of MR.HAANDI » |
Solutions
Solution by pk__, published 26. jun, 2012; download (24 kb), password: crackmes.de or browse.
pk__ has rated this crackme as quite nice.
Solution by Dcoder, published 25. jun, 2012; download (1301 kb), password: crackmes.de or browse.
Dcoder has rated this crackme as quite nice.
Discussion and comments
| pk__ 19. Jun 2012 | id: 175001982597854 fp: KZgBH4kwVK34U5lhPyZ+R1814RomwY1c4x6pfG8oNVjWl2c8wM3t3VnorR/aoFeGhPa74R6294AURw== sig: KZgBH4kwVK34U5lhPyZ+R1814RomwY1c4x6pfG8oNVjWl2c8wM3t3VnorR/aoFeGhPa74R6294AUR8mF y8aLK7kBBtE9ys19mfb/Z3fekWi2/2z9xcIadi7RXrLZBRjrYKesSVdOBgwmClk+RlxXnVUYIadT6N5u IXJcl7ZtURs= |
|---|---|
| pk__ 26. Jun 2012 | My solution was based on the birthday paradox. The expected number of iterations with that method is ~2^24 (not counting precalc, which is also 2^24). |
| andrewl.us Moderator 27. Jun 2012 | cool work guys |
| kilobyte.asm 27. Jun 2012 | umm hold on wait, there's no tutorial in pk__'s solution? |
| pk__ 28. Jun 2012 | @kilobyte: sorry, forgot to add it. the problem in crackme is: H(x) - 6 topmost bytes of md5(x) || - concatenation id - id fp - fingerprint serial - encoded pair (r,s) for DSA h = H(id)||fp dsa equation checked by the crackme: w = s^-1 mod q v = g^hw * y^rw mod p mod q r == v If we can control "h", then it's easy to generate a valid sig: r = (y*g)^k = g^xk+k (k random) w = r^-1 * k h = r indeed: y^rw = g^xrw = g^xk, since rw = r*r^-1*k = k g^hw = g^k, since hw=rw=k so: g^hw * y^rw = g^k*g^xk = g^xk+k and this is equal to r. the problem is we can't "easily" control whole hash, since 6 bytes of it come from md5(id). we need to find a collision, by generating random r=g^k and random id and checking if 6 topmost bytes of md5(id) match 6 topmost bytes of "r". If so, we set the fingerprint to fill the rest of h, so that H(id)||fp == r. By birthday paradox, we expect to find a collision after ~sqrt(2^48) = 2^24 iterations. |
| kilobyte.asm 30. Jun 2012 | cheers mate. Hopefully sometime in the near future I'll be able to understand all of that :P |
You may leave your comment, thoughts and discuss this crackme with other reversers here.
Acting childish will not be tolerated.
HTML and such will be left as-is, so don't try.