-----Original Message-----
From: asrg-admin(_at_)ietf(_dot_)org [mailto:asrg-admin(_at_)ietf(_dot_)org]
On
Behalf Of Scott A Crosby
Sent: Friday, 21 March 2003 08:38
To: David Finnie
Cc: hparry(_at_)andrew(_dot_)cmu(_dot_)edu; asrg(_at_)ietf(_dot_)org
Subject: [Asrg] Re: Stamping
On Fri, 21 Mar 2003 23:21:32 +1100, David Finnie
<David(_dot_)Finnie(_at_)platypuspartners(_dot_)com> writes:
Scott,
I don't like that, but how about some notion of stamping? Each
message recieved must include a valid stamp. Stamps are
only usable
once.
This is an interesting idea. I have some questions for you
about your
proposal:
Can you please describe more fully your concept of a "partial hash
collision", and "sufficient number of bits". I think I
understand that
the first 64 bits of the stamp is input to MD5, and also that the
recipient's email address is input to MD5. If we let "x" be
the number
of bits in "sufficient number of bits", are you saying that:
The sender gets 32 bits, called HashNonce from the recipient
through a stamp-missing bounce. Then then wish to compute the
64 bit quantity XXX, such that:
N=(HashNonce || XXX)
and
MD5(N)[0:x-1] = MD5(recipient email)[0:x-1]
N is now a valid stamp. The reason I use HashNonce there is
to allow a recipient to eventually time out old used stamps
to reduce storage needs for already used stamps. I would
expect it to change yearly.
MD5(stamp[0:63])[0:x-1] = MD5(recipient email)[0:x-1]
MD5(stamp[0:63])[128-y:127] = MD5(recipient email)[128-y:127]
This does not matter, what matters is the number of bits that
are forced to be matched. IE, x=20 in your first example is
as equally hard problem as y=20 in the second.
or perhaps that it is up to the receiver to determine which
bits match
? And presumably "x" is worked out by the recipient when it
does it's
calculation to produce some stamps ? Or are you suggesting
that "x" be
a fixed quantity for this protocol ?
$x$ is a fixed quantity, say 32, such that computing such an
XXX requires a signifigant amount of work. Benchmarking, it
looks like 1ghz machine can do 5 million/second MD5's, so for
$x$=32, this means about 15 minutes/stamp, but will go down
with increasing computing power. I want it to be this long,
because nominally, this cost is only payed once between a
pair of participants. Generally, anyone you've sent email to
won't have to burn this CPU time to reply.
MD5 may not be the best function however; anyone have any
idea how greatly can be greatly sped up using hardware? (And
for what cost?)
Forgive my ignorance, but I'm not familiar with working
with partial
hashes, and I don't know of any gotchas. My main concerns would be:
say for a particular recipient email address, could the MD5 hash it
produces severely limit the maximum value of "x" that can
be used for
a partial match against hashes of 64 bit quantities ? Given
the good
randomness of MD5, I would guess probably not, but it is worth
investigating (if you haven't already). My reasoning is
that if that
were the case, then some unfortunate recipients may be easy targets
for spamming because it would be easier to "guess" the
first 64 bits
of their stamp.
Assuming that MD5 is a random function of its inputs, $x=32$
means that the probability of successfully forging a stamp is
one in 4 billion.
Are you proposing that the stamp-control protocol piggy-back within
SMTP ? My main reason for asking is that for a sender to acquire a
Undecided. There are four sets of data that need to be kept:
1. Canceled/Used stamps.
2. Outstanding stamps (that were sent in response to a request)
3. HashNonce
4. Unused stamps
IMHO, #1, #2 may be kept by the user or the ISP. #3 should be
kept by the ISP, so that first-time senders can learn the
currently valid HashNonce with paying a user-agent to ISP
trip instead of = paying a full user-agent user-agent round
trip. So, if #3 is not kept by the ISP, email latency could
require two round trips.
#4 is who keeps track of which stamps are unused for a
particular recipient. If this is kept by the ISP, how does
the ISP avoid paying the time for a partial hash collision.
stamp from a receiver, the request really needs to somehow
end up at
the mail server for the receiver (so that the database of
valid stamps
can be checked when a mail message containing a stamp is
received). I
think it would make sense for it to piggy back within SMTP.
I'm not entirely certain, and leave this to others.
I am also assuming that a stamp cannot be verified as
belonging to, or
not belonging to, a particular recipient, except by the recipient
itself. (I say this because one of the options is for the
recipient to
create totally random stamps.) Is this correct ?
There are two notions of stamp: Random nonces created by a
recipient, and partial hash collisions. In the first case,
identification can come from the fact that all nonces are
fresh. In the second case, identification may come from the HashNonce.
There is no identification attached to a stamp, except for
the knowledge that the probability of someone successfully
forging one is extremely small. If I create stamp
*EMovyZQWSXggt1uV*, I can be assured that nobody will guess
it, I can also keep track of who I origionally sent it to. I
also keep track when its been used.
So, when a stamp is recieved, it is
1. If a nonce, looked up in the hash table of all unused stamps. If
yes, accept, if no, bounce.
2. If a partial-hash stamp, the HashNonce is looked up in the hash
table of all currently accepted HashNonce's. If its not there,
bounce. Then the the partial hash collision is checked. If invalid,
bounce. Finally, the stamp is checked in the used-stamps
hashtable. If there, bounce, if not accept.
Scott
_______________________________________________
Asrg mailing list
Asrg(_at_)ietf(_dot_)org
https://www1.ietf.org/mailman/listinfo/asrg