
November 1st, 2001, 14:23
#1
TMG keygenme #3
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 RipeMD160 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
I promise that I have read the FAQ and tried to use the Search to answer my question.

November 1st, 2001, 18:15
#2
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.

November 1st, 2001, 20:15
#3
hi goat
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
I promise that I have read the FAQ and tried to use the Search to answer my question.

November 2nd, 2001, 09:38
#4
TMG Keygenme #3
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
I promise that I have read the FAQ and tried to use the Search to answer my question.

November 5th, 2001, 13:58
#5
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 p1 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 p1: 2, 232D4D, 2DE7A0949A5
tE!, perhaps you could shine some light on my problems, I'd really appreciate your help.
goatass
I promise that I have read the FAQ and tried to use the Search to answer my question.

November 5th, 2001, 16:05
#6
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 (p1)
//a = g^k mod p
//b = k^1 (m  x*a) mod (p1)
decr(p,1,p);
copy(p,p2);
copy(p,p3);
// x2=xa mod p1
multiply(x,a,x2);
divide(x2,p2,x3); //z=x2/p1 p2(3rd param)=remainder
//copy(p2,x2);
// x3=Mx2
subtract(m2,x2,x3);
divide(x3,p2,x2);
// x3=k*b mod (p1)
// m=b/k mod p1 ( 1/k (mod p1) first, then b*1/k (mod p1) )
// Serial part 2
xgcd(k2,p,k2,k2,k2); //eXtended Greater Common Divisor (1/k (mod p1))
multiply(x3,k2,x2); // (1/k (mod p1) * x3 mod (p1)
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
I promise that I have read the FAQ and tried to use the Search to answer my question.

November 5th, 2001, 19:11
#7
At first glace I see you don't check to make sure k is relatively prime to p1. Considering p1 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

November 6th, 2001, 14:28
#8
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 (P1)
K
RegCode = {a, b}
regards
McCodEMaN
I promise that I have read the FAQ and tried to use the Search to answer my question.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules
Bookmarks