On Thu, 11 May 2000, Wei Dai wrote:
> David Molnar Wrote:
> > Anyway, recipient-hiding is most obviously useful when public bulletin
> > boards are involved. I'm not so sure it's useful between remailers, since
> > the underlying transport protocol will tend to reveal the ID of the next
> > hop anyway...but it strikes me as something to have as a hedge against
> > future clever attacks I can't think of.
OK, I thought of something else. Please let me know if this makes sense :
Consider the situation where we want to use a cypherpunk-remailer reply
block R to send a message M to someone. Let's denote the hops inside the
reply block by H_1, H_2, H_3 ... H_n. The sender can't look inside the
reply block, and so only knows H_1.
He concatenates R and M, then encrypts this with the public key of H_1
and sends that on to H_1. Then H_1 decrypts the reply block,
learns the identity of H_2, sends the message on, and so on.
Is M available for inspection by H_1? If so, then it seems that if M
reveals the identity of the intended recipient, then H_1 (and all the
other hops) can learn the identity of the recipient. Normally we would
try to prevent this by encrypting M with the public key of the recipient
-- but if the cryptosystem is not recipient-hiding, this will potentially
reveal the recipient's identity, not hide it. Modulo purposely
encrypting with somebody else's public key and other subtrefuge, anyway.
Normally, this would not be a problem because M would be a layered
encryption, but in this case since the identities of H_2 -- H_n are not
known to the sender, how does he encrypt the message for them?
Now H_1 knows both sender and recipient, which makes the other hops
irrelevant. Even if the sender is another remailer (as would happen
if the sender is smart and chains through remailers to send to H_1),
now every hop in the chain can learn the destination and have some
idea as to where it is in the chain.
Am I missing something which causes this to fail?
>
> If a number of mixes share a broadcast channel, recipient-hiding might be
> very useful for reducing the number of "good" mixes in a chain needed to
> achieve complete mixing. For efficiency, it would be desirable to have a
> recipient-hiding encryption scheme that allows easy screening of
> ciphertexts that can be decrypted by a given private key. Is this
> possible? All of the schemes you listed seem to require trial decryptions
> of every ciphertext.
>
I don't know anything cute, unfortunately. :-\
The most straightforward hack I know is to encrypt a known "magic number"
with the same key as the message. Prepend the encrypted magic number to
the encrypted message. Now we only need to trial decrypt the encrypted
magic number ; choose it to be long enough that the chance of the wrong
key making it decrypt to the correct value, but short enough to minimize
the cost of decryption. Screening such a message now requires only trial
decrypting the magic number...although it must be noted that someone could
easily encrypt the number with a different key than the message itself
and so mount a kind of denial of service attack.
Thanks,
-David Molnar
