Re: Slightly faster checking for encrypted messages to me

[Bill Stewart <stewarts@ix.netcom.com>]

At 10:31 AM 9/5/95 -0800, Doug Barnes wrote to Hal and us:

>If two entities want to communicate via a message pool,
>without worrying about traffic analysis, but don't want
>the overhead of trying to decrypt every headerless
>message to the pool, then they can do the following:
>
>1) In a "headered" message, one of the entities (A) sends
>   a collection of large random numbers to be used as return
>   markers, encrypted with the public key of the desired
>   correspondent (B).
>
>2) B can then respond to A with an essentially headerless
>   message prefixed with one of the numbers send by A.
>   This initial message should contain a list of similar
>   numbers for B, that A can use to send messages to B.

There's a way to get this without sending as much data -
using a relative of S/Key (probably not affected by S/Key patent.)
A sends B two random numbers, thing1 and thing2.
B's headers include a prefix of
        n, hash( thing2, hash^n(thing1) )
where hash^n is n rounds of hash, e.g. MD4 or MD5.
Thing2 can possibly be a well-known string instead.  
Assuming there's no special relationship between thing2 and 
the hash function, it should be hard to derive 
        hash( thing2, hash^n(thing1) ) 
from 
        hash( thing2, hash^(n-1)(thing1) )
presumably as hard as inverting the hash.  
(Brute-force is an option if thing1 is not chosen well, 
involving a few hundred hashes on a few million popular wimpy passwords,
but S/Key suffers from the same weakness.)

Including n in the header is a mild message-correlation risk, 
though messages don't have to be sent with consecutive n's 
(at a cost of more runs of hash per message.)  This lets you recover
easily from lost messages.  There's also the mild risk that the
thing1 and thing2 keys need to be stored, though Doug's method
also suffers from that.

It is also possible to use S/Key itself - the original message
from B to A contains Xn = hash^n(key) and maybe n.  
The next message contains Xn-1 = hash^(n-1)(key), which A checks by 
hashing it and looking in his table of messageids for Xn.
A can recover from small numbers of lost messages by hashing a few times.
(Since you're not using it for authentication, is it covered by
the S/Key patent?)

This method has the weakness that Traffic Analysts can also
correlate messages by hashing the fields and comparing with previous.
One workaround is to for B to also send A the keys for some simple
encryption method E such as "Ek = m xor k" and use Xn = Ek(hash^n(key)).
This requires A to perform an xor and a hash for each correspondent
(B, C, D, ...), but is probably secure enough.  Alternatively,
since the numbers are fairly short, you can use "Ek = m^k mod p",
but that's starting to look like work :-).



#---
#                                Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---