[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: freehaven@freehaven.net*Subject*: [freehaven-dev] Re: request for comments on Mixnet Reputations paper*From*: David Hopwood <hopwood@zetnet.co.uk>*Date*: Tue, 12 Dec 2000 11:16:43 +0000*CC*: adam@homeport.org, adam@cypherspace.org, jfr@zeroknowledge.com, daw@cs.berkeley.edu, dm@cs.nyu.edu, asmith@theory.lcs.mit.edu, anna@theory.lcs.mit.edu, jbash@zeroknowledge.com, golem@mit.edu, freehaven-dev@freehaven.net*Delivery-Date*: Tue, 12 Dec 2000 06:20:44 -0500*References*: <20001210060112.F31162@belegost.mit.edu>*Reply-To*: freehaven-dev@freehaven.net*Sender*: owner-freehaven-dev@freehaven.net

-----BEGIN PGP SIGNED MESSAGE----- [sorry to anyone who receives this more than once] Roger Dingledine wrote: > We (Michael Freedman, David Molnar, and I) have been writing a submission > for the Info Hiding Workshop (http://chacs.nrl.navy.mil/IHW2001/), > and we'd be interested to have you take a look and give us your > reactions. I give the abstract below, and the paper itself is available > from http://freehaven.net/doc/mix-acc/mix-acc.ps (or .tex). Our submission > deadline is Dec 12 (Tuesday). # One common way to prevent raters from cheating is to design some means of # verifying transactions. In many systems, transaction verification is done # by having both parties exchange signed digital receipts, or by performing # the transaction publically. We extend the latter notion to develop a mix # design in which all messages in the MIXnet are publicly known. That is, # MIX nodes publish their input and output messages. This information is # exactly what would be seen anyway by a passive adversary with complete # network access. We retain unlinkability between message sender and # recipient due to the batching and reordering that each MIX performs # internally. This seems like a very strong assumption to be making about the security of the mix-net. It is possible to send messages between mixes using secure channels (which would be quite desirable in order to turn potential passive attacks into attacks that require compromising some nodes), so the assumption that a global passive adversary would see all messages anyway is not necessarily correct for all mix-net protocols. # This idea was originally due to Chaum in [4]. The reason we obtain # anonymity is because the messages coming into the MIX are encrypted. The # MIX decrypts them and sends out the decryptions, which are themselves # encrypted messages (except for the last hop). If we have a semantically # secure cryptosystem, then an adversary has only negligible probability of # determining which incoming message corresponds to which outgoing message. Semantic security is definitely not sufficient to protect against an active attacker. For example, I've been working on a class of attacks that I'll call "marking" attacks, where an active adversary changes a message in such a way that it can be identified later in the route. Although Mixmaster and many other mix-net protocols have message integrity checks, they do not cover the whole message (which is quite difficult to do because of the random padding to a fixed length). By making a change to a specific part of the message, the adversary can ensure that it is only be detected as invalid n hops later, where n is determined by the adversary. If the adversary also controls that later node (and possibly even if he does not - see below), then he can identify the message. In particular if the message is marked before the first node, and identified at the last node, the whole path is compromised. It may also be possible to perform this attack even when the last node is not controlled by the adversary. Suppose that a node always has the same number of output messages as input messages in a given time period. In that case it can be detected whether the node has dropped a message, because the number of output messages will be one less than expected. This attack can also be extended to the case where (inputs - outputs) is random but varies only by a small amount. Publishing the inputs and outputs potentially aids this attack (as well as traffic analysis and probably other attacks), because it makes any adversary into a global passive adversary, i.e. there is no need to eavesdrop on the inputs and outputs of the last node, or know which node this is in advance. It is possible to prevent marking attacks by making sure that a change to the ciphertext is always detected by the next hop. This is quite complicated, and requires the use of deterministic rather than random padding to a fixed length. I've been working on a mix-net protocol that does this, as a refinement of Babel (it also has some nice features like supporting reply messages that are as secure against replay attacks as outgoing messages, which I don't think any other protocol does). # However, we should keep in mind that traffic analysis research is still # in its infancy, and it may be that hiding even the information that a # passive adversary would see is crucial to real anonymity for remailer # networks; see Section 5.8 for more consideration of this point. # In general, a system to verify transactions should provide verification # of both successful and failed transactions. However, due to the # pseudonymous nature of a mixnet, successful transactions can easily be # spoofed (via pseudospoofing, as described in Section 5.5) and thus do # not provide an accurate metric for MIX reliability. If the mix-net supports reply blocks then it can also support receipts, which allow successful message transmissions to be verified by the sender. This does not allow the sender (Alice) to prove to anyone else that the message was or was not sent correctly, and it doesn't allow Alice to determine precisely which mix on the path failed. However, Alice could potentially send more messages, with paths that cross the previous path, to determine how reliable each of those mixes is. Also, it is still possible for reviewers/scorers to test reliability, either for real messages or for dummy messages that a reviewer sends to itself. These will be indistinguishable from real messages if the network is working as intended, so they will be no more or less reliable than real messages on average. I.e. sections 5.5 to 5.7 of the paper apply even when inputs and outputs are not published. Another possibility is for Alice to be able to request information about whether a message she sent that failed to arrive was received by each mix on the path. Call a mix "dishonest" if *either* it lies in response to one of these requests, or it dropped a message. If all of the mixes on the path say they did receive the message, then the last mix is dishonest. Otherwise, let i be the index of the first mix that says it did not receive the message; then either N_{i-1} or N_i or both are dishonest. This is not as good as being able to blame a particular mix, but it does not require publishing messages. We can enforce that only Alice can obtain this information (so that it is still hidden from passive attackers attempting to do traffic analysis, etc.) by having Alice prove to the mix, over a secure channel, that she knows a value that was included in the relevant onion layer. If so then the answer is sent back over the same secure channel. Unfortunately even when Alice knows that either N_{i-1} or N_i is dishonest, she can't prove it to anyone else. # In our notation, we will explicitly include the random value used in # the encryption, so E_1(M, r) means the encryption of message M and # random value r under the public key of N_1. # [footnote] Note that while E_1(M) is a random variable ranging over # all the possible encryptions of M, E_1(M, r) is a particular string. This should be E_1(r, M), to be consistent with the notation in the rest of the paper. # This section describes the protocol for sending a message from Alice # to Bob, using our mixnet design with verifiable failures. # 1. Alice chooses a recipient Bob. # 2. Alice chooses k MIX nodes N_1, ..., N_k to form a "MIX path". # 3. Alice picks k + 1 random padding values r1, r2, ..., rk, rbob. # 4. Alice creates an initial packet P, defined as # P = E_1(r1, 2, E_2(r2, 3, ... E_k(rk, Bob, E_Bob(rbob, M)) ...)) It would be slightly clearer to use P = E_1(r1, I_2, E_2(r2, I_3, ... where I_j is the identity or name of node N_j. # We now define ciphertext collision resistance in a manner similar to # hash functions. Call a public key cryptosystem weakly ciphertext # collision resistant if it is infeasible for a probabilistic # polynomialtime adversary, given a target ciphertext C, to produce a # public key pk, message M, and random padding value r such that # C = E_pk(r, M). A public key cryptosystem is then strongly ciphertext # collision resistant if it is infeasible for a polynomialtime # adversary to produce any collision whatsoever, not necessarily a # targeted one. Somewhat surprisingly, common cryptosystems are not # ciphertext collision resistant. Actually they are in the sense required. Definition: a "public key encryption scheme with unambiguous decryption" is a public key encryption scheme (G, E, D) where G : Coins -> PubKey x PrivKey (G is probabilistic) E : PubKey x Seed x PT -> CT D : PrivKey x CT -> PT \union {INVALID} such that for all (pk, sk) = G(coins), there is a *one-to-many* relation R_pk : PT x CT -> {0,1}, and a set ValidCT_pk, defined by R_pk(M, C) = 1, if \exists r \in Seed s.t. E(pk, r, M) = C = 0, otherwise ValidCT_pk = { C \in CT : \exists M s.t. R_pk(M, C) = 1 } such that D(sk, C) = the unique M s.t. R_pk(M, C) = 1, if C \in ValidCT_pk, = INVALID, otherwise. A ciphertext in ValidCT_pk is called a "valid ciphertext for pk". E is supposed to be used by choosing a seed at random from the set Seed for each message. (To visualise this, draw a diagram with each plaintext in PT mapping to a collection of ciphertexts in CT, so that all the collections in CT are disjoint. All the remaining points in CT decrypt to INVALID.) RSA-OAEP, DHAES, and almost all other PK encryption schemes have unambiguous decryption. The only example I can immediately think of that doesn't is the Rabin encryption scheme (which is one reason why it isn't commonly used). # Call a public key cryptosystem fixedkey strongly ciphertext collision # resistant if for a fixed public key pk, it is infeasible for a # probabilistic polynomial time adversary to find a tuple # (M, r, M0, r0) such that E_pk(r, M) = E_pk(r0, M0) and M != M0 or # r != r0. The "fixedkey" here means that we restrict ourselves to # ciphertext collisions only over a single fixed key. This is not really the right property; we do not need to care about collisions where r != r0 but M = M0. Call a public key cryptosystem fixedkey ciphertext collision-free if for a fixed public key pk generated by G, there does not exist a tuple (M, r, M0, r0) such that E_pk(r, M) = E_pk(r0, M0) and M != M0. Because R_pk is one-to-many, there cannot be ciphertext collisions for different messages under a given public key generated by G, so all encryption schemes with unambiguous decryption are fixed-key ciphertext collision-free, and this is sufficient for the proofs. About the Elgamal example (reference 34), David Wagner wrote: > David A Molnar wrote: > > Suppose I have a message M and a "target" ciphertext C = E_PK(M,r) for > > some randomized public key encryption and padding scheme E_PK with > > padding value r. How difficult is it to find a different M',r' such that > > E_PK(M',r') = C ? > > For El Gamal, it is trivial. If C = E(M) and C' = E(M'), then > C*C' = E(M*M'), so generate C' = E(1) [a random encryption of "1"], > and then multiply C by C'. The ciphertext in Elgamal is (g^r, M*g^xr), where r is the random seed and x is the private key. I think David Wagner is talking about the second part of the ciphertext; it is not possible to find a fixed-key collision (i.e. with M' != M) for the whole ciphertext, because that would mean that decryption was ambiguous. It is certainly possible to find collisions with r' != r and M' = M; for Elgamal, r' = r + ord(g) is a collision in that sense. But this is completely harmless for the delivery failure proof: exhibiting *any* r and M such that E(pk, r, M) = C proves that C \in ValidCT_pk, and therefore D_sk(C) = M. [Collisions for different keys are not really relevant, because the key of the node that is being accused of failure can be assumed to be known to any verifier. We can also assume that this key is valid (i.e. was generated by G) and secure, because the node chose it, and has no incentive to generate an invalid or insecure key. This is important because unambiguous decryption does not necessarily hold for invalid keys.] # OAEP(m, r) = m0^k1 XOR G(r) || r XOR H(m0^k1 XOR G(r)) Note that the version of OAEP that has been standardised (in IEEE Std 1363-2000 and PKCS #1 v2.0) and is now commonly used, is OAEP(r, M, P) = DB XOR G(r) || r XOR H(DB XOR G(r)) where DB = h(P) || 0^k || 1 || M P = encoding parameters (often zero length). [In fact when G and H are constructed using "MGF1" with the hash function h, as specified in the above standards, then RSA-OAEP could be proven fixed-key strongly ciphertext collision resistant assuming only that h is collision resistant, i.e. without using the random oracle model - but this is academic because fixed-key strong ciphertext collision resistance isn't required.] Next problem: the proofs of Goals 2 and 3 are flawed (although they can be fixed). In the proof of Goal 3, the string that Alice presents is called D_k(foo), when it is not known to be of that form. In fact there's another minor mistake here - the decryption of foo would include (k+1) - but the main point I want to make is that foo is not known a priori to be a valid ciphertext, and the D_k(foo) notation makes an implicit assumption that foo can be validly decrypted. Also the verifier cannot compute the function D_k, so cannot check directly that this value is equal to D_k(foo) (checking by re-encryption is not the same thing). Suppose, then, that Alice presents rk, I_{k+1}, and bar, such that E_k(rk, I_{k+1}, bar) = foo. The proof would then continue as follows: If N_k finds that foo is not a valid ciphertext for pk, then it would ignore the packet. But if Alice can provide any plaintext that encrypts to foo under N_k's public key, then foo must have been a valid ciphertext for pk. So D_k(foo) != INVALID. Since we are using an encryption scheme with unambiguous decryption and since N_k's public key can be assumed to be valid, E_k(rk, I_{k+1}, bar) = foo implies that D_k(foo) = (I_{k+1}, bar). Thus N_k can obtain (I_{k+1}, bar) from foo. If such an entry was on the ledger (who wrote it there is irrelevant), and N_k did not later post "To N_{k+1}: bar" to the ledger, then N_k really did fail. Alice's claim is therefore true. Therefore, we satisfy Goal 3. Goal 2 gave me a real headache, until I realised that it is not necessary. The proof of Goal 3 already shows that no-one can exhibit (rk, I_{k+1}, bar) showing that N_k dropped a message which is valid up to and including the N_k layer, unless N_k actually dropped it. So it is sufficient to merge Goal 2 and Goal 3 into: # Goal 2, Reject false claims: Any participant (including Alice) # cannot claim that node N_j failed to pass on a well-formed message # sent by Alice to N_{j+1} (and possibly onward from there to Bob), # unless it really did fail to send such a message. Saying "a well-formed message sent by Alice to N_{j+1}", instead of "a well-formed message sent by Alice to Bob", is important because the protocol does not prove whether the parts of the message encrypted to N_{j+1}, ... Bob are well-formed or not. In fact we do not care whether those parts are well-formed: if Alice shows that N_j failed to pass on a message to N_{j+1}, but the later parts of the message were ill-formed, then N_j has still failed. Similarly, we don't care about how the message to N_j got onto the ledger; it is considered well-formed iff the layer encrypted to N_j's public key is correct. So the whole proof for the merged Goal 2 (which addresses soundness, not completeness) can be written as: False claims are rejected Sketch We wish to show that any participant cannot claim that node N_j failed to pass on a well-formed message sent by Alice to N_{j+1}, unless it really did fail to send such a message. Without loss of generality we will assume that the prover is also Alice (this allows the prover to use information that only Alice has, e.g. the random seed values). - If Alice posted a real message P which includes N_j as normal, then a well-behaving, honest N_j will have forwarded it on and produced an intermediate message. Any verifier will see this intermediate message when Alice claims N_j failed and disbelieve Alice. By assumption, Alice cannot delete the intermediate message from the ledger, so N_j is protected from such a false claim. - In order for Alice to claim that N_j failed to pass on her message as above, Alice would need: - an entry "To N_j: foo" present on the ledger, - knowledge of some string bar, seed rj, and destination N_{j+1}, such that E_j(rj, I_{j+1}, bar) = foo. If N_j finds that foo is not a valid ciphertext for pk, then it would ignore the packet. But if Alice can provide any plaintext (I_{j+1}, bar) that encrypts to foo under N_j's public key, then foo must have been a valid ciphertext for pk. So D_j(foo) is not INVALID. Since we are using an encryption scheme with unambiguous decryption, E_j(rj, I_{j+1}, bar) = foo implies that D_j(foo) = (I_{j+1}, bar). (We can assume that N_j's public key is validly generated, because it is chosen by N_j, who would have no incentive to generate an invalid key.) Thus N_j can obtain (I_{j+1}, bar) from foo. If such an entry was on the ledger (who wrote it there is irrelevant), and N_j did not later post "To N_{j+1}: bar" to the ledger, then N_j really did fail. Alice's claim is therefore true. Therefore, we satisfy Goal 2. Note that this also covers the case where Alice attempts to send N_j ill-formed messages, since (I_{j+1}, bar) is not ill-formed, and we have proven that when Alice's claim is accepted, N_j must have received a message with that as the plaintext. Any other messages that N_j may have received are irrelevant. It is also necessary to show that the cryptosystem remains secure when random seeds are published, but this is true because the seeds are only published by someone who encrypts to the public key, and does not know the private key. In that case, revealing the seed can only affect the secrecy of the specific message encrypted under that seed (which is revealed anyway at the same time). I think that was all :-) Good luck with the deadline. - -- David Hopwood <hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOjYIYzkCAxeYt5gVAQHWhwgAzkexIAP8KRh1qEzCxtSNpSR9TCcp+mgX ho6CiVDcoHJP9VniM4hPIkMaKu4Mlj3BpZw2DyWesyKIV0Tu9zNMrMrj+G7Cm7Ks 3PyTeJhCwSIMITWR9Q96ZWsv2dHk4d+wpwhcqBKDcZ+QImt0Mme5LOZIoiKKdNGv Bbs+wrzqr2poYh0gmbirEqUDWGTtAViy22bBulhS2DoeBjnOOpjtKd2Z9xx90xp6 U4HVFz+lytVofjnkQNHnN1IH6ImKNQDsw+kLS1tGK/v2HsXE6YNAaLKyXxaLR9n8 ByzoavQAZCFguHF6QoxVXNEW9mgHb7uJHNzYMKDuCVli96/72Pnjfg== =GsBA -----END PGP SIGNATURE-----

**Follow-Ups**:**[freehaven-dev] Re: request for comments on Mixnet Reputations paper***From:*David Wagner <daw@cs.berkeley.edu>

**Re: [freehaven-dev] Re: request for comments on Mixnet Reputations paper***From:*David Hopwood <hopwood@zetnet.co.uk>

- Prev by Date:
**[freehaven-dev] (FWD) request for comments on Mixnet Reputations paper** - Next by Date:
**[freehaven-dev] Re: request for comments on Mixnet Reputations paper** - Prev by thread:
**[freehaven-dev] (FWD) request for comments on Mixnet Reputations paper** - Next by thread:
**[freehaven-dev] Re: request for comments on Mixnet Reputations paper** - Index(es):