Shortcut digital signature verification failure

[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 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 majordomo at wasabisystems.com