Shortcut digital signature verification failure

[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 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.
>frantz at pwpconsult.com | fair use.              | Los Gatos, CA 95032, USA
>
>
>
>---------------------------------------------------------------------
>The Cryptography Mailing List
>Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
>


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