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.