Subject: Re: namedroppers, continued

From: [email-masked]
Date: Sat, 07 Dec 2002 15:07:59 -0800 (PST)

> In message <[email-masked]>, Dean An
> derson writes:
> >This seems clever, however, it will also take significant computational
> >effort to verify the computational effort was actually done. Even if a
> >class of functions are found that are "easier" to verify than to compute,
> >they will no doubt still take up a significant fraction of time.

> In fact, that's the easy part.  You could demand that the sender
> compute 1,000,000 HMACs of the text, the envelope, the time of day, and
> a counter.  The verifier could check 100 randomly-chosen ones -- if any
> fail, there's a forgery.  (Well, you probably wouldn't want those
> values, since 1,000,000 HMACs would be a lot of data to transmit.  But
> you get the general idea.)

The exmaple given in the Microsoft paper was square roots in a finite field.
These are computationally difficult to compute (lots of multiplication mod p)
but easy to check (single multiplication mod p).

I'm sure there are other examples -- finding candidate functions of this
sort is *much* easier than finding, say, a public key algorithm.

				Ned

---

From: Dean Anderson <[email-masked]>
Date: Sun, 8 Dec 2002 12:39:23 -0500 (EST)

To make them do all the work, and you do little to verify, you need a lot
of things done independently, so that a random sample can be selected that
is much smaller than the work they had to do. This will get bulky.  The
less they send, the larger the fraction of work you have to do in relation
to theirs.  And of course, you have to do the same amount of work on your
outgoing messages as they do.

The result is that it costs you much more than it costs the spammer.
(since you have to do the work for both sending and receiving, and the
spammer only has to do the work for sending.

This would not result in a reduction of spam, as a percent of total mail.
If everyone used this, it might (at best or worst) reduce the total mail
sent, since the billions of legitimate messages sent each day would
require significantly more work to send.

Further, it would open one up to a denial of service type attack where
garbage is sent, and you have to do the work to check the (invalid)
signature, thereby wasting your cpu resources.

Essentially, this shoots oneself in the foot. Or perhaps the CPU.

		--Dean

On Sat, 7 Dec 2002, Steven M. Bellovin wrote:

> 		--Steve Bellovin, http://www.research.att.com/~smb (me)
> 		http://www.wilyhacker.com ("Firewalls" book)
>
>
>
> --
> to unsubscribe send a message to [email-masked] with
> the word 'unsubscribe' in a single line as the message text body.
> archive: <http://ops.ietf.org/lists/namedroppers/>
>

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>