Re: Shortcut digital signature verification failure
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 expend it's CPU. My 800MHz PIII can do about 2800 512-bit RSA verifies per second. Dan Bernstein has a signature algorithm where verification is significantly faster still [1], and his ideas could probably be used to quickly reject most invalid signatures with even better efficiency. What David left out here is that this should be about 10 times as fast as signing. 20 times for 1024 bit, 30 for 2048 and 60 for 4096 - so the answer is use bigger keys. Note that even using 4096 bit keys my (totally non-optimal debugging build of) OpenSSL can do over 80 verifies a second on a PIII of average speed (and less than two signs). Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 early rejection of repeated bad queries from a source. The rating system would reset the source rating after a pre-defined time, much like anti-congestion mechanisms on the Net. Fast rejection of bogus signatures would help, but not alone. I had already thought of this approach, but wanted to add to it a CPU limit on the client end. Hash cash with a server provided problem seems a good approach there. Cheers - Bill - Bill Frantz | The principal effect of| Periwinkle -- Consulting (408)356-8506 | DMCA/CBDTPA is to | 16345 Englewood Ave. [EMAIL PROTECTED] | prevent fair use. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 that 0 = s^3 - kn n; clearly this can't hurt security, as k can be publicly computed from s. Then the recipient can efficiently verify the validity of the claimed signature (t,k) on m as follows: verify that 0 = s^3 - kn n; then So the signer supplies s and k. And our first step is to verify that 0 = s^3 - kn n. But given that we've computed S = s^3 - kn and it is in this range, isn't it the case that S = s^3 mod n? And so we can test test that H(m) = S = s^3 mod n and that verifies the signature directly. secretly pick a random 31-bit prime p, compute t' = s^3 mod p, n' = n mod p, k' = k mod p, h' = H(m) mod p, and verify that t' - k'n' = h' (mod p). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 proof-of-work entitling the client to have the server verify the accompanying signature. Adam On Thu, Jun 20, 2002 at 11:08:37PM -0700, Bill Frantz 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 processing just to reject the transaction. 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 expend it's CPU. This might result in a better balance between the resources needed by the attacker and those needed by the server. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 a valid request. To extend the idea to signatures, all you really have to do is program the server to create puzzles that will take at least as much computation to solve as it requires to check the signature. And of course it checks the solution to the puzzle (using a single modular-power operation, which is relatively cheap) before it checks the signature itself. Bear On Thu, 20 Jun 2002, Bill Frantz 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 processing just to reject the transaction. 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 expend it's CPU. This might result in a better balance between the resources needed by the attacker and those needed by the server. Cheers - Bill - Bill Frantz | The principal effect of| Periwinkle -- Consulting (408)356-8506 | DMCA/SDMI is to prevent| 16345 Englewood Ave. [EMAIL PROTECTED] | fair use. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 a source. The rating system would reset the source rating after a pre-defined time, much like anti-congestion mechanisms on the Net. Fast rejection of bogus signatures would help, but not alone. Cheers, Ed Gerck Bill Frantz 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 processing just to reject the transaction. 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 expend it's CPU. This might result in a better balance between the resources needed by the attacker and those needed by the server. Cheers - Bill - Bill Frantz | The principal effect of| Periwinkle -- Consulting (408)356-8506 | DMCA/SDMI is to prevent| 16345 Englewood Ave. [EMAIL PROTECTED] | fair use. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Shortcut digital signature verification failure
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 receiving. So normally you would require no hashcash, so the clients don't have to expend CPU cycles. Then as the number of bad signatures increases, you step up the amount of hashcash so that you can continue coping. Interestingly you ought to be able to calculate the amount of hashcash required to keep the flow of bad signatures manageable. Suppose your current hashcash requirement is x, and bad signatures are arriving at twice the speed your crypto accelerator can cope with. Then, assuming that the hashcash calculation is the dominant cost for the attackers, you need to double your requirement to 2x. -- Pete - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Shortcut digital signature verification failure
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 processing just to reject the transaction. 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 expend it's CPU. This might result in a better balance between the resources needed by the attacker and those needed by the server. Neat idea. So neat in fact that RSA Security has a patent on it. :-) Sorry, I don't have the patent number handy. --Lucky - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
