noobpwnftw's KeygenMe
| Download KeygenMe.zip, 234 kb (password: crackmes.de) Browse contents of KeygenMe.zip Goal:
Difficulty: 5 - Professional problem to solve | RatingWaiting for at least 3 votes View profile of noobpwnftw » |
Solutions
Solution by redoC, published 01. jul, 2014; download (1488 kb), password: crackmes.de or browse.
redoC has not rated this crackme yet.
Discussion and comments
| redoC 16. May 2014 | What version of MPIR is used? |
|---|---|
| noobpwnftw Author 16. May 2014 | MPIR 2.2.1, the last version that supports vc9. |
| redoC 18. May 2014 | exponent 0x10003 is intended? |
| noobpwnftw Author 18. May 2014 | Yes, 0x10003 is chosen on purpose. |
| redoC 19. May 2014 | Is here anyone good in RSA crypto mathematics? Here is full algo. I have no idea how to solve it... bigNamehash = SHA512 (Name) bigNamehash &= 0x0FFFF... // high 4-bits zeroed, this can be clue? ========================= 0044A5EF_Button_Request: p = gen. random 256-bit prime q = gen. random 256-bit prime N = p * q F = (p-1) * (q-1) D = gmpz_invert (0x10001, F) // private key D ^= bigNameHash // xor big1 = gen. random 256-bit prime big2 = gen. random 256-bit prime big3 = big1 * big2 // required condition: D < big3 big4 = pow (D, 0x10001) mod big3 szRequestNumber = ToHexString (N, big3, big4) // concatenation of three 512-bit numbers ========================= 0044A332_Button_Check(): good_boy if: bigNamehash = pow (bigAnswer, 0x10003) mod N // 0x10003 is not error ========================= ...so we have these numbers N, big3, big4, bigNamehash and we should construct number bigAnswer |
| Encrypto 21. May 2014 | mmm I gave this a quick overview, however I only found relevant material in regards to GnuPG's implementation of choosing e, and in the potential weaknesses involved in exposing a (32) bit factor of (p-1)*(q-1). I would be very interested in seeing a solution, as I do not have much time to dedicate towards this myself :( |
| noobpwnftw Author 27. May 2014 | alright. so as the analysis by redoC, there are 2 rsa moduli involved, D^hash is encrypted by big3, result is big4. In order to retrieve D you need to factor big3, then use D to factor N, calculate another D with 0x10003 and encrypt namehash, then you have good boy answer. all conditions and high bit masks are used to fulfil 1<plain<N for rsa to work. |
| redoC 28. May 2014 | Factoring 512-bit number is not possible within 5 seconds. Give us more hints. Different generation of big2 plays a role? |
| noobpwnftw Author 29. May 2014 | Yes, big2 is preditable. |
| s3Rious 10. Jun 2014 | Great job redoC! :) |
| noobpwnftw Author 11. Jun 2014 | For redoC's solution, I think it is better to use a table for big2 as the RNG is reseeded in every loop with the value of rand(), there can only be RAND_MAX possible values. By doing so the solution can be physically independent from the KGM, rather than a side-channel attack. |
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.