Jump to content
Tuts 4 You

[KeygenMe] KeygenMe


Nooby
Go to solution Solved by xSRTsect,

Recommended Posts

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 by Nooby
  • Like 1
Link to comment
Share on other sites

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


 


fdbztd.jpg


Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by Nooby
Link to comment
Share on other sites

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.


  • Like 1
Link to comment
Share on other sites

@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.


Link to comment
Share on other sites

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


 


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 by Nooby
Link to comment
Share on other sites

are you absolutely sure about this line:


 


0044A392     68 03000100                      PUSH 10003

 

Are you positive it is not 0x10001?

Link to comment
Share on other sites

@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.

Link to comment
Share on other sites

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).


Link to comment
Share on other sites

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 by Nooby
Link to comment
Share on other sites

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


Link to comment
Share on other sites

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 by Nooby
Link to comment
Share on other sites

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


Link to comment
Share on other sites

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 by Nooby
Link to comment
Share on other sites

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.

  • Like 1
Link to comment
Share on other sites

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?


Link to comment
Share on other sites

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 by Nooby
Link to comment
Share on other sites

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 by xSRTsect
Link to comment
Share on other sites

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).

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...