Hey everyone, I am working on TMG's keygenme #3 and I got stuck at when I couldn't make any valid keys. I studied the Elgamal signature algorithm and the RipeMD-160 used and I figured the RipeMD part and the ElGamal stuff but it never makes valid keys. I think my problem comes when I try to reduce the generator of the group. Did anyone check it out at all or could help me out with ElGamal. Math isn't my strong side but that's why I'm asking for help

If someone is interested in this I can post my commented IDA file and my source code for the keygen that I made (in C++).

p.s. I'm not doing this to join TMG so save your flames.

thanks
goatass

Hey goatass!

Find me on irc and I'll see what I can do to help you out. I worked on this one a while back and still have my notes.

goatass it uses md5 not ripemd160, this might answer as to why
your keys are invalid. Also just follow the miracl library to see what each function call does or figure it out manually. Once done use the solving method found in index.c in miracl library should do the trick. Heya Kythen btw. -Sab

Hey Kythen and Sab, what's going on with you two, long time no talk.

Sab, the reason why I thought it was using RipeMD is because it used it in Keygenme #2 and I recognized the init functions and the hash loops and in my keygen I implemented RipeMD and hashed my username and it gave me the same exact hash value as the keygenme gave me when I traced it hashing the same username.
Maybe it is MD5, I ripped out the hashing loops and put them in my keygen that's why I'm getting the correct hash but I have in my head that it's RipeMD for some stupid reason.

I think I'm missing something with the Number Theory part of things.


Thanks alot guys, hopefully we can get this thing figured out so we can move to Keygenme #4 which looks very interesting

goatass

some more help please.....

When I try to solve the DLP using tE!'s dlp util from his SecureCRT source codes on his web site, I can never get the correct X. I tried rearranging the factors of my p-1 since he mentioned in there that their order matters but I never get the correct X since when it does the verification of y=g^x mod p the y that is generated doesn't match the one I used to solve the DLP.

Prime, P = C9D94F46D0984F43
Genrator of a group, G = 4B45042B684BCBD1
public key, Y = 91D4D6EF46B05C78
private key, X = 1AA4EF ??? not sure

verification = 3A29A50EA6C6DD99 doesn't match Y from above.

factors of p-1: 2, 232D4D, 2DE7A0949A5

tE!, perhaps you could shine some light on my problems, I'd really appreciate your help.

goatass

I'm a retard, I figured out why I get wrong X values, my array of prime factors was one unit too small so it skipped the last factor. Fixing that I get X = 6C18DA28FDD8FEF1 but now when I use it in my keygen it generates wrong signatures.

My keygen goes like this (mainly tE!'s code):

/* create m from hashed name */

mip->IOBASE=256;
mip->INPLEN=16;

cinstr(m,RipeMD);

mip->IOBASE=16;
x1=mirvar(0);
cinstr(x1,EG_1);
power(m,3,x1,m2); //m2=m^3 mod x1
mirkill(x1);


mip->INPLEN=0;
/* Input Bignumbers */
cinstr(p,EG_p);
cinstr(g,EG_g);
cinstr(x,EG_x);
cinstr(y,EG_y);

//--------------------------------------------------
// generate a random K
decr(p,1,p);
bigrand(p,k);

incr(p,1,p);
copy(k,k2);
copy(k,k3);


/* a=g^k mod p -> Serial part 1 */
powmod(g,k,p,a);
copy(a,a2);

//-------------------------------------------------
//M = (x*a + k*b) mod (p-1)
//a = g^k mod p
//b = k^-1 (m - x*a) mod (p-1)

decr(p,1,p);
copy(p,p2);
copy(p,p3);

// x2=xa mod p-1
multiply(x,a,x2);
divide(x2,p2,x3); //z=x2/p-1 p2(3rd param)=remainder
//copy(p2,x2);

// x3=M-x2
subtract(m2,x2,x3);
divide(x3,p2,x2);

// x3=k*b mod (p-1)
// m=b/k mod p-1 ( 1/k (mod p-1) first, then b*1/k (mod p-1) )
// Serial part 2

xgcd(k2,p,k2,k2,k2); //eXtended Greater Common Divisor (1/k (mod p-1))
multiply(x3,k2,x2); // (1/k (mod p-1) * x3 mod (p-1)
divide(x2,p3,x3);
copy(x2,b);

//-------------------------------------------------


cotstr(a2, szR1);
cotstr(b, szR2);

// strcat szR1 and szR2 and print to screen
//--------------------------------------------------------------------------------

/* y^a*a^b mod p = g^M mod p */


/* Verify serial */
incr(p,1,p);
powmod(y,a2,p,d); //d = 91D4D6EF46B05C78 ^ serial1 mod p
powmod(a2,b,p,c); //c = serial1 ^ serial2 mod p
mad(c,d,d,p,p,m); //m = c * d mod p
cotstr(m, szM);
SetDlgItemTextA(hDlg, EDIT_VERC, szM);

/* Verify name */
powmod(g,m2,p,m);
cotstr(m, szM);
SetDlgItemTextA(hDlg, EDIT_VERN, szM);

The results from the above two verifications don't match and they should, and that's where I'm lost.....

goatass

At first glace I see you don't check to make sure k is relatively prime to p-1. Considering p-1 is even, you have less than a 50/50 chance of getting a relatively prime random number. That'll put a damper on your ElGamal stuff any day
There may be other problems of course, but i'll have to sit and look it over more carefully.

Cheers!
Kythen

Greetings goatass!

Look at this algorithm:


UserName - text line
Hash = HashMD5 (UserName);
m = Hash ^ 3 mod hp
a = G ^ K mod P
m - X * a
b =----mod (P-1)
K
RegCode = {a, b}


regards
McCodEMaN