[keygenme] Alive

[HMX0101]

Alive

Just another crypto keygenme and delphi ****.

Only valid solution is a keygen.

Luck,

HMX0101 // 10-04-2011

alivekgme-hmx.rar

[Saduff]

Is this ElGamal Signature Scheme? It looks like it.

Anyway, attempting to solve DLP to get the private key

gives me: "Can't solve that sh*t!"

Never solved ElGamal (or DLP) before, so I'm a newbie in that area.

I've identified all the FGInt calls and stuff and know what it's doing,

but don't know how to reverse it.

First thought was to generate first 2 parts of serial randomly and

then solve 9F76B9617C4B04782B89 ^ X mod E50D80BB9284DF3F23D3 = Y to

get the 3rd part, where X is the 3rd part of serial and Y is calculated

based on 1st and 2nd part of serial and name. But solving DLP every time is unfeasible.

-- EDIT --

Been trying to get the private key by solving the DLP (using another DLP solver)

for 3 hours now and still nothing. I must be doing something wrong.

Guess I'm not the only one having difficulties with this one, considering it's still unsolved.

-- EDIT --

If this is indeed ElGamal, then am I correct with the following?

Y = G ^ X mod P, where G,P,Y are public keys and X is the private key.

Y = E17D4BC428ED77A25829

G = 9F76B9617C4B04782B89

P = E50D80BB9284DF3F23D3

Edited June 1, 2011 by Saduff

[HMX0101]

You're correct, those are the values for P,G,Y.

About the DLP solving time, I would recommend you to use a solver based on Index Calculus method.

[Saduff]

Thanks, I found a calculator that solved the DLP in 0.5 seconds.

Now let's see if I can keygen this thing.

-- EDIT --

Now I don't understand what the 3rd part of the serial (last 20 chars) has to be.

I think that the first 2 parts of the serial are the signature (r, s).

The 3rd part of the serial is used only here: G ^ serial[3] mod P, so I thought that

it has to be MD5(name), but that can't be, since MD5 is 32 chars long.

So I tried using MD5(name) mod P as the 3rd part of the serial, but that didn't work.

Edited June 1, 2011 by Saduff

[HMX0101]

The third part of the serial is part of the signature.

Difficulty of the challenge is to find out what the third part should be

[Soul]

Thanks for the keygenme!

I hope my keygen works well.

keygen.rar

Edited June 11, 2011 by Soul

[HMX0101]

Nice work Soul, ATM you're the only one that solved it

And I don't know why if Its so simple

[rdbnhoax]

Thanks, I found a calculator that solved the DLP in 0.5 seconds.

Now let's see if I can keygen this thing.

Care to share that tool, or give me/us a link for it?

I have been looking for a dlp solver using the index calculus method for a while now.

Maybe I'm just a bad googler

- rdbnhoax

[Saduff]

I used Magma Calculator:

http://magma.maths.usyd.edu.au/calc/

Used this script:

p := 1081671008419063856571347;
K := GF(p);
g := K ! 753046344671602713045897;
y := K ! 1064843761188532526405673;
x := Log(g, y);
x;

Don't know if it uses the index calculus method, but it solved the DLP very fast, while other solvers failed.

[rdbnhoax]

Thank you Saduff

- rdbnhoax

[qpt^J]

yeah, really nice scheme

thanks to KKR, for informing me, that it's a special signature scheme, so could be solved more effective way, rather than runtime DLP solving for each signature. So I wrote the equation with pen and got the result

for those, who are interested how to get signing algorithm without searching for some common schemes:

maybe I'll solve this kgm soon, once i get bored.

Edited July 6, 2011 by qpt^J

[KKR_WE_RULE]

I got freak'd out by the serial decoding algo

May be if I get bored some time, I'll touch it again

way to go qpt do it !!

[KKR_WE_RULE]

Okie.. I got bored & I touched it again.. This time I recoded ya Serial Decoding stuff in Delphi.

Here it is.

http://pastebin.com/Gqyw9DLz

Accoriding to my logic.. It should be reversed as Under, but it isn't working.

http://pastebin.com/Tw30Vtqv

Any 1 else having this prob ?

Edited July 13, 2011 by KKR_WE_RULE

[qpt^J]

cool kgm really thx kkr for that hint

Keygen.rar

[HMX0101]

Nice job mate, wasn't that hard, huh?

Btw, my intention was to use 'FUN' as first 3 chars... I didn't thought about other possible words

[qpt^J]

for me, it was hard, yeah

especially that Lexicographical order part, because there wasnt any good explaination about it on inet, only by guessing i found how it works

and found that 'KEY' part by guessing too

[KKR_WE_RULE]

That transformation part kick'd my *** Real thanx goes to Dcoder__. I couldn't identify the algo there.

Ok.. now it can be made public.. Its BWT De_Transform() that used there. Need to use BWT_Transform() to reverse it

@qpt^J : Great work as always Congratz

@HMX : I'll still write a soln, coz last time I tried I had some probs with the BWT_Transform(). It was hard for me.. but I have gotta admit, it taught me a great deal of stuff. Thanx a bunch

[SmilingWolf]

I'm years late as always D:

I'm including the modified ElGamal signature's paper, my notes (in italian, sorry), the (probable) original Delphi BWT source used in the KeygenMe, a sorta equivalent implementation in Python found on the net and most importantly my keygen in Python. Uses Z3Py to retrieve the first three letters of the serial
Also included a version with the precalculated string in case you don't want to install and configure Z3Py. The other dependencies are standard Python 2.7 modules.

EDIT: finally added to my KGCollection. Relevant sources: BWT, keygen.

Alive.7z

Edited June 13, 2016 by SmilingWolf