[KeygenMe] KeygenMe

[Nooby]

Goal:
Write a keygen to calculate "Answer" to any given valid inputs in a reasonable amount of time.
 
Specs:
UPX packed
No obfuscation or VM
No patch detection
“Request" data is randomized
 
Appendix:
Name: Tuts4You
Request: A799CB8D37C11F8052AA59674A0E89957205F69BE447F887306A02934F4863652C418D6B268070B4B95C500B89FD89D13612D0A9961E0FA39CD033A094F015B5E0FB48BFA37D25834496AD4D68E4FA097D0454303545C89CCBD9898D96021CA8480F06414D8BD28A194C5786EA167BACBD19E259E803EBBB6C74D7367E4615873FD8CA2654055E564DFA145C1A62FAC9DE5D156709F6B6067B014C9DF4D7C7A32E7012B84859AF9A3232EF531904045F272ABBE063D75336B516226049BEAD28Scoring(100 points total):
Patching - 10 points
Calculate "Answer" to one pair of input of your choice - 10 points
Calculate "Answer" to the given input in Appendix - 20 points(first poster)
Calculate "Answer" to each pair of inputs within 6 months - 20 points
Calculate "Answer" to each pair of inputs within 3 months - 20 points
Calculate "Answer" to each pair of inputs within 5 seconds - 20 points

 

Hint:

Some math skills needed to solve the problem.

Your method and/or implementation of one or two steps of the calculation is the key to achieve higher score.

 

Update:

Added some sanity checks on input.

Cleaned up some unnecessary variables.

 

More hint:

Factoring is the way to go and guaranteed practical. 

 

Enjoy!

KeygenMe.zip

Edited May 5, 2014 by Nooby

[simple]

i'll take quick 10 points, just a couple of lines of anti patch/debug could make it take a lot longer though. thx for challenge plz continue posting them

 

[GIV]

Answer must be 80h characters.

CPU Disasm

Address   Hex dump          Command                                  Comments

0044A38A  |.  3D 80000000   CMP EAX,80

0044A38F  |.  0F85 E4000000 JNE 0044A479

And a patch here:

CPU Disasm

Address   Hex dump          Command                                  Comments

0044A441  |. /75 0B         JNE SHORT 0044A44E

0044A443  |. |68 F8304500   PUSH 004530F8                            ; ASCII "Correct!"

0044A448  |. |EB 09         JMP SHORT 0044A453

I get 10 points.

[SReg]

Always interesting look at patches (je->jmp or nop) in [KeygenMe] topic!

wtf? =)

[simple]

for sure keygenning is harder than cracking from a reversers view, but from a dev's view it's easy to make something 'unkeygenable', plenty of these, but to make a program uncrackable is a real app security challenge for the dev.

 

for me personally i will probably never use some crazy random maths like that common in keygenme on a real world coding project so i dont bother, but i respect if u do

[Nooby]

Technically there is no way to stop patching if there exists a correct code path, regardless of algorithms you use.

 

Why I'm making this KeygenMe is because there are some good point of interests that someday you might find useful.

 

There is no custom modified algorithm madness here, I use standard SHA-512 and MPIR library only.

 

To be more precise, if you indeed wish to skip the out-of-compiler code RE part, the difficulty of this KeygenMe is not reduced by providing you the source code and I do have a convincing solution in hand.

Edited May 1, 2014 by Nooby

[Nooby]

any progress?

[xSRTsect]

Okay, so here it goes, a fast solution:

 

for name: Zuma

Request-crap: A75806364AD552910B533EA5FD479CEE1906641C217A904BFD0036E250C9E1FB2B098C9B6005917EEBCC48DDB661FE5305D774F58D3BE547B3DC38F2B71F59199371689AB195B3D7566E48342EFADC1BD791743B9FC72D05023D85E63D3EAE1F9113C0E8C2CBE205CE9CD6D45E01B33E688F62FD6C32A3E34EBB7B27E13E150748CE9E76A27F5D09AE6656F1706E3FA94D6D91AB984CE7E97AB2672280BBB83055474622F4C40734EDBF10FB70EB84C7AF2BB93CE3FA17AE56C647EFB2114204

 

Serial: 14209A19034DF50D5E984732B73F3A27AA0D0002DE1A974B429D55D8788A9744DB3E03313D2EB5B5D404A54E8BD2013788B9D8AE2EE91D1364F5997E003AF213

 

Ofc I did not break your RSA-511. I'll writte a keygen ASAP, and a tutorial if requested. Otherwise just the kg. You were good with the mpir.

[Nooby]

@xSRTSECT

Grats, you have 20 points(assuming 10 points of patching).

 

Note that if RSA isn't broken, the keygen will not work for any given input, thus will not score more.

 

Keep it up and your tutorial to self-keygenning is welcomed.

[xSRTsect]

No but dont worry my kg will work for any input

[Nooby]

In that case you should be able to provide an answer to the given input in Appendix, that will grant you another 20 points.

 

It is of course keygenable by design, and not by trival factoring to earn a high score, I'm just making sure you are on the right track.

Edited May 7, 2014 by Nooby

[xSRTsect]

are you absolutely sure about this line:

 

0044A392     68 03000100                      PUSH 10003

 

Are you positive it is not 0x10001?

[Nooby]

@xSRTsect

I'm absolutely sure about the values, otherwise your previous answer would be incorrect. Maybe it does require solving the RSA, one way or the other.

[xSRTsect]

Dude this is whats up: It is possible to extract the inverse of 0x10001. I dont see a way to extract the inverse of 0x10003. Neither do I see a way to extract Phi(N).

[Nooby]

Good job doing so far, the rest is just math. You can calculate what you need by the following:

d = e^(-1) mod phi(N)

we know de = 1 mod phi(N) so de - 1 = 0 mod phi(N)

so de-1 is a multiple of phi(N)

Given any multiple of phi(N) it is possible to factor N. I'll leave the proof and implementation open.

The original RSA paper http://people.csail.mit.edu/rivest/Rsapaper.pdf mentioned a method in reference 6, which you can find at http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf

Edited May 11, 2014 by Nooby

[xSRTsect]

Nooby I understand what you are saying. But extracting a quadric root of 1 mod N? That is expansive

[Nooby]

In fact, the purpose of the second paper solves the quadric root in a quasilinear time.

Here goes my proof:

let prime x be 1 < x < N, we have

x^(de-1) = x^0 = 1 mod N (Euler's theorem)

because prime p and q are odd, phi(N) = (p-1)(q-1) is divisible by 4

let g = phi(N)/4

y = x^g = x^((de-1)/4) mod N

y^4 = x^((de-1)/4)*4) = x^(de-1) = 1 mod N

y^4-1 = (y-1)(y^3+y^2+y+1) = 0 mod N

we can easily calculate (y-1) which is a multiply of some value in {1, p, q, N}.

pick different x until we find a quartic root with gcd(y-1, N), which is either p or q, a prime factor of N.

now that we have prime factors of N, d = modinv(e, phi(N)), and the value of e is free of your choice.

Edited May 11, 2014 by Nooby

[xSRTsect]

Well nooby I had no clue it would be possible to break RSA just by knowing a multiple of Phi( N). I am going to read those papers, and if it is true, then I am gladly thankfull for this challenge and I will finish my keygen,

 

 

Best Regards,

 

sb

[Nooby]

Ok sure, the phi(N) factoration method is known to the designers of RSA, just its mathematical proof is about primality tests.

Addition to my previous proof:

y^4 = x^((de-1)/4)*4) = x^(de-1) = 1 mod N <-- why?

since (de-1) is a multiple of phi(N),

x^(de-1) = x^a(phi(N)) = x^a = 1 mod N (Euler's theorem again)

BTW, there is another gotcha in this KeygenMe. In the RNG attack I wish your solution has a computational complexity of O(1), otherwise it will not fit in the time limit.

Edited May 11, 2014 by Nooby

[xSRTsect]

No - my rng attack is O(1048576)

[Nooby]

It will take too long. If you read this paper, https://eprint.iacr.org/2012/064.pdf, although they did not menthon their methods, but considering their number of inputs you might ring a bell. I'm able to reproduce their test on the current PGP keychain in the matter of seconds.

[xSRTsect]

Ok. I have checked those two papers you adviced, very disappointing seems basic stuff. And I can't find any references about theory that shows how to recover p,q if a multiple of Phi(N) is known. That seems hard to do without knowing anything else in advance. What is missing here?

[Nooby]

Fair enough, nobody cares about those theories anyways.

Here is the algorithm:

Calculate (de-1) which is a multiple of phi(N)

Since 4 is a square of 2, divide (de-1) by 2 until we have an a*phi(N) that gcd(a*phi(N), 4) = 1

Choose any number x that 1<x<N (just use small primes, let's skip some composite madness) and calculate y = modexp(x, a*phi(N), N)

Since y^4 = (y-1)(y^3+y^2+y+1) is a multiple of N, (y-1) can be some multiple of {1, p, q, N}, gcd((y-1), N) and we have a 50% chance of getting a prime factor, if not, choose a different x

Edited May 15, 2014 by Nooby

[xSRTsect]

yesssssssssssssssssssss... now I see it, great work.

 

I was forgetting that you dont need to root 1, because you already have it from x^aPhi(N)/4

Edited May 15, 2014 by xSRTsect

[Nooby]

this is the counter proof of RSA transform, and was used to test primality of p & q back in the days(last step you'll get other factors if p or q is not prime).