Re: Shortcut digital signature verification failure

2002-06-23 Thread Ben Laurie
David Wagner wrote: Bill Frantz wrote: If there is a digital signature algorithm which has the property that most invalid signatures can be detected with a small amount of processing, then I can force the attacker to start expending his CPU to present signatures which will cause my server to

Re: Shortcut digital signature verification failure

2002-06-22 Thread Bill Frantz
At 2:18 PM -0400 6/21/02, Ed Gerck wrote: A DoS would not pitch one client against one server. A distributed attack using several clients could overcome any single server advantage. A scalable strategy would be a queue system for distributing load to a pool of servers and a rating system for

Re: Shortcut digital signature verification failure

2002-06-22 Thread Nomen Nescio
David Wagner describes a trick from Dan Bernstein to speed up RSA signature verification with e = 3: One of the nicest ideas from his work is easy to describe. In plain RSA, s is a valid signature on m if H(m) = s^3 (mod n). Now suppose we ask the signer to also supply an integer k such

Re: Shortcut digital signature verification failure

2002-06-21 Thread Adam Back
Doesn't a standard digital signature plus hashcash / client puzzles achieve this effect? The hashcash could be used to make the client to consume more cpu than the server. The hashcash collision wouldn't particularly have to be related to the signature, as the collision would just act as a

Re: Shortcut digital signature verification failure

2002-06-21 Thread bear
It's already been thunk of. check the literature on hash cash. Basically, the idea is that the server presents a little puzzle that requires linear computation on the client's side. (same algorithm as minsky used for his time-lock). The client has to present the solution of the puzzle with

Re: Shortcut digital signature verification failure

2002-06-21 Thread Ed Gerck
A DoS would not pitch one client against one server. A distributed attack using several clients could overcome any single server advantage. A scalable strategy would be a queue system for distributing load to a pool of servers and a rating system for early rejection of repeated bad queries from

Re: Shortcut digital signature verification failure

2002-06-21 Thread Pete Chown
Ed Gerck wrote: A scalable strategy would be a queue system for distributing load to a pool of servers and a rating system for early rejection of repeated bad queries from a source. You could also vary the amount of hashcash required depending on the number of bad signatures you are

RE: Shortcut digital signature verification failure

2002-06-21 Thread Lucky Green
Bill wrote: I have been thinking about how to limit denial of service attacks on a server which will have to verify signatures on certain transactions. It seems that an attacker can just send random (or even not so random) data for the signature and force the server to perform extensive