PDA

View Full Version : Attacking DSA


Pyrae
April 25th, 2003, 11:18
Hi there,
I've got some (plenty to be honest ) questions regarding DSA-based protection schemes,
where p (1024 bit), g, y, and q (160 bit) are known.

1. Forging
In some earlier thread someone mentioned that forging a valid
signature might have been possible in a similar case.
What does "forging" in this context mean?
Is it trying to brute-force x by trying values below q or is it
something about more sophisticated cryptanalysis?

2. Solving the DLP
Is solving the DLP in such cases feasible or will the sun burn out
prior to a getting a result?
If it is, which algos would be most promising (Pollard-Rho, Index-Calculus)?
Are there any public sources (might be maple, mathematica etc. aswell)
for those (it's no fun spending a month writing the whole stuff yourself
just for probably achieving no result ) or are the gurus keeping that code for themselves?

'nuff questions for now and thanks for reading,
Pyrae

mike
April 27th, 2003, 17:40
"Forging a signature" means pretty much the same thing it does with normal signatures: that someone other than the holder of the private key generates a message that appears to have been signed by the private key. The method of forging depends entirely on the context, and is usually infeasible, especially for the size of numbers you're talking about. (Else what would be the point of the crypto in the first place?)

"Solving the DLP" isn't something you do just once (unless you find a new algorithm for it that will make you rich & famous). You need to solve it for each instance you're trying to attack. The time it takes to solve depends on the size of the parameters. You can solve the DLP mod 5 in your head But here, p would have to be a prime with a special form in order to use any of the known attacks.

And yes, the sun would burn out first...

I'll refer you to Woodmann's searching thread for finding packages that do this stuff.

You'll learn a lot more if you implement it yourself, though. To get you started, here's a link:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/phexam.html

Index calculus usually runs faster than Pollig-Hellman. Here's a link:
http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/silverman.ps.zip

Pyrae
April 28th, 2003, 21:14
Thanks very much, Mike!
Sorry for not having informed myself a bit more before asking some of these
(pretty naive, looking at them now) questions...
I read up some stuff in the HAC meanwhile and found that in my particular case
none of the seven attacks mentioned - except index calculus perhaps, which I
have not been able to check until now - seems to be usable.
Guess next month's project will be to implement index calculus with some decent algo
for finding relations (hoping my school math is up to the task)...
Anyway, one last naive question:
Can one possibly choose (i.e. patch in) different p,g and x which would lead to the same
public key y and make your own generated signatures pass the verification algo?
And, of course, thanks for the links, especially the first one
(actually I found some pretty good explanation on index calculus in my native language).

Back to the books,
Pyrae

mike
April 28th, 2003, 22:30
Yeah, sure, you can patch it no problem most of the time. In fact, usually, they do something like
Code:

input name, serial
hash it with sha to get x'
compute y'=g^x' mod p
compare y,y'
je goodkey
messagebox (bad key!)
ret
goodkey:
messagebox (yay!)
...

And you just change je to jne. Unless they're using DLP for encryption (ElGamal), then patching will knock it dead--it's only good for preventing keygens.

Can you give any more details of how the DLP is used in your context?

Pyrae
April 29th, 2003, 01:12
Yes, of course.
Basically it's the classical DSA verification procedure.
The registration name is first hashed using a modified SHA-1.
The serial is a composite of 2 160 bit integers (r and s).

The following computation is done:

w=(2nd160bitofserial ^ -1) mod q
u1=(namehash * w) mod q
u2=(1st160bitofserial * w) mod q
v=((g^u1 * y^u2) mod p) mod q

If v=1st160bitofserial (i.e. 'r') you're a good guy.
(p is 1024 bit, q is 160 bit)

The problem is that the public key y is crippled inside the target and is for certain reasons near to intractable (see PM for details).
Actually I didn't mean a jz/jnz kind of patch, as this is for the same reasons not applicable. My hope was, that modifying only the p, y, g and/or q parameters, which are easily exchangable in the code, might be some way to tackle this target. But now I guess, this can't be a solution as only y is called the "public key" in the literature.
I'm not sure, whether it would be a wise choice to post the exact parameters here, so I sent you a PM with some details...

Thanks again,
Pyrae



/edit: Oops, just saw that your inbox is full. The PM will be sent immediately when your account is reachable again...

Pyrae

mike
April 29th, 2003, 03:58
Try setting p=q. Then you only have to solve discrete log mod q, which is doable.

mike
April 29th, 2003, 04:16
Another way that isn't guaranteed to work but which makes everything easier if it does:

set g=1
then
v=((g^u1 * y^u2)mod p)mod q
=((1*y^u2)mod p)mod q
=(y^u2 mod p) mod q

Then start trying different numbers for p to see if you can get
r = y^u2 mod p
If you can't, try to find p such that
r+q = y^u2 mod p
and then
r+2q = y^u2 mod p

Pyrae
April 29th, 2003, 04:26
Wow, I realize again, you're eating this for breakfast.
As soon as I wake up, I'll immediately try your suggestions. But for now my mind is urging me to go to bed (about 40 hours without sleep until now)...

P.S. The PM has now been sent...


Thanks No. 4,
Pyrae

Pyrae
April 29th, 2003, 11:42
Phew, can't get this out of my head.
As for the 1st method, I told maple to do some number crunching (it's already eating up half of my ram).
The second way is what gives me a hard time.
Doesn't r always turn out to be 1, if you're setting g=1?
What should I choose for u2 in the final equation?
Isn't this actually dependent on s and therefore on x?
Should x=1 and k=1 be used for that?
Sorry, if I didn't get the point, but this one really gives me a headache...

Nearly wiser than before,
Pyrae

mike
April 30th, 2003, 03:29
What method in mathematica? ECM to factor q-1?

I assumed r is first 160-bit hash, s is second. If so, r isn't always going to be 1. Put in whatever serial you want, find r,s, and calculate u1 and u2 from it.

Here's another one, probably even faster.
set p to a prime r<p<=q

Then to make it work we need
v=r=(g^u1 * y^u2)mod p
r * y^(-u2) = g^u1 mod p
g = u1th root of (r * y^(-u2)) mod p

Since it's easy (Mathematica will do it for you) to take roots mod primes, then if there's a solution we can find a value for g (as above) that will satisfy the equation directly. If there's no solution, we can still play with it; set p to any prime between r and q and try again.

Of course, all this assumes you can tweak any value except y.

mike
April 30th, 2003, 03:31
Oops! I mean maple, not mathematica.

mike
April 30th, 2003, 03:34
Is the final comparison between v and r done mod anything, or is it a direct equality check?

Pyrae
April 30th, 2003, 16:01
Quote:

What method in mathematica? ECM to factor q-1?

Actually, I told Maple to solve mlog(y, g, q), but realized that this probably isn't the way to do it, as the calculation still lasts.
Well, factoring q-1 using lenstra or pollard was a matter of seconds, but of what use is this?
Seems I didn't get the point again...

Quote:

I assumed r is first 160-bit hash, s is second. If so, r isn't always going to be 1. Put in whatever serial you want, find r,s, and calculate u1 and u2 from it.

Erm, r is the first part of the serial and s is the second, so there
actually isn't anything to put in besides the registration name and the two signature parameters r and s.

Quote:

Is the final comparison between v and r done mod anything, or is it a direct equality check?

The latter. It's actually a simple string comparison.

Quote:

Here's another one, probably even faster.

Thanks, gonna try it immediately.
Didn't think, that there are so many ways to accomplish this...


But there's also a little success I had.
Using your second suggestion of making g=1, and setting k=1 and x=1 myself, it solves to the following:

r = (g ^ k mod p) mod q
=(1^1 mod p) mod q
=1

s=(k^-1 * (namehash + xr)) mod q
=1 * (namehash + 1) mod q
= namehash + 1 (for namehash+1 < q)

Then using any p with y^((namehash+1)^-1 mod q) mod p = 1 makes the verification work.



Btw, does Mathematica implement better algorithms for factoring and discrete logs than Maple (at least you seem t like it better )?


Slowly becoming smarter,
Pyrae

mike
April 30th, 2003, 18:09
Great! Yeah, when there's only one constraint and (r,s,g,p,q) five parameters, you can play with it in a lot of different ways. I understood that r and s were outputs of SHA-1 when I made my suggestions, rather than some power of g.

Good on ya' for figuring out how to do it!

Factoring modulus-1 is the first step in pohlig-hellman. If you only changed p=q, then you could have solved the discrete log problem that way.

mike
April 30th, 2003, 18:14
Oh, and no preference between maple & mathematica, it's just that I happen to have the latter and not the former.