Shortcut digital signature verification failure

[David Wagner]

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.

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
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).  This requires a few reductions and multiplications modulo
a 31-bit number, and thus is faster than verifying the RSA signature
directly (the latter requires a few reductions and multiplications
modulo a 512-bit number).  Moreover, if the prime is chosen randomly,
the probability that an adversary can forge a signature that passes
this screening test is something like 2^-26 or so.  In short, invalid
signatures can be detected quickly with very high probability.

[1] D. J. Bernstein. ``A secure public-key signature system with extremely
fast verification.''  http://cr.yp.to/papers.html#sigs

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com