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

"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

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

Yeah, sure, you can patch it no problem most of the time. In fact, usually, they do something like

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?

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

Try setting p=q. Then you only have to solve discrete log mod q, which is doable.

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

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

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

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.

Oops! I mean maple, not mathematica.

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

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


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.


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


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

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.

Oh, and no preference between maple & mathematica, it's just that I happen to have the latter and not the former.