1993-03-02 - Re: A novel (?) return address idea

Header Data

From: gnu (John Gilmore)
To: cypherpunks@toad.com, gnu
Message Hash: b35016291396cba07bef6c160488ad3fdce6046a0d4f2f74f8087b17bdb545e8
Message ID: <9303021838.AA29102@toad.com>
Reply To: <9303021603.AA09007@mango>
UTC Datetime: 1993-03-02 18:38:20 UTC
Raw Date: Tue, 2 Mar 93 10:38:20 PST

Raw message

From: gnu (John Gilmore)
Date: Tue, 2 Mar 93 10:38:20 PST
To: cypherpunks@toad.com, gnu
Subject: Re: A novel (?) return address idea
In-Reply-To: <9303021603.AA09007@mango>
Message-ID: <9303021838.AA29102@toad.com>
MIME-Version: 1.0
Content-Type: text/plain

There seems to me to be a serious problem with the "novel return
address" idea.  The information that ties together multiple anonymous
messages from the same person is out in the world, encrypted by a
single key in a conventional cipher.

If that single key is compromised, everyone's identity is exposed. (Or,
at least, the correlation among all messages sent by that individual, 
even if their legal or email name is not revealed).

Furthermore, breaking the key will be possible by sending test-probes
and doing exhaustive search.  E.g. if you add 128 bits of salt,
someone can send five or ten messages to themself through the
remailer, and accumulate ten encrypted addresses that are known to be
for the same sender.  When decrypted, these keys will have maybe a 16-
or 32-bit "return address ID" and 128 bits of salt.  The attacker can
then search the key space for keys that include large numbers of
identical bits when decrypting those ten keys.  This search is easily
amenable to parallelization, fast hardware also exists to do it, and
it may be possible to find improved algorithms to use the knowledge of
identical plaintext bits to speed up the search process.

The idea also suffers from the dossier problem -- all the information
about return addresses will exist in a single place (at the remailer
site) where it's tempting for a government (or other adversary of
privacy) to try for it.

Keep thinking, folks!  We aren't there yet...