### Zero Knowledge Identity Proofs

I'm reading about zero knowledge identity proofs and 'The Mafia Fraud' in Applied Cryptography. Has no one found a way to perform an identity proof such that you can prove who you are to a specific person? In the example in the book Alice proves who she is to Bob who transmits to Carol, and Carol proves that she is Alice to Dave. I'm curious what the problem is with creating a proof that Alice is Alice such that only Bob can be assured that she is Alice so that Carol can't use the proof to identify who she is to Dave. -- Groove On Dude Michael Conlen Obfuscated Networking [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

On Sun, 24 Jun 2001, Michael Conlen wrote: > I'm reading about zero knowledge identity proofs and 'The Mafia Fraud' in > Applied Cryptography. Has no one found a way to perform an identity proof > such that you can prove who you are to a specific person? In the example in > the book Alice proves who she is to Bob who transmits to Carol, and Carol > proves that she is Alice to Dave. I'm curious what the problem is with > creating a proof that Alice is Alice such that only Bob can be assured that > she is Alice so that Carol can't use the proof to identify who she is to > Dave. THe proofs that you are requesting for have been standard tools in cryptography for many years - they are usually known as identification schemes. The best known scheme (and most elegant IMHO) is the Schnorr identification scheme. See http://www.tml.hut.fi/~helger/crypto/link/identification/ for a (noncomplete) collection of links. Helger - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

I think this is a case for additional protective mechanisms to extend the protocol semantics (there is nothing in the protocol prohibiting the verifier to perform a verification on behalf of a third party, which is the vulnerability exploited in the Mafia Fraud attack). This 'challenge-relay' can easily be defeated if the verifier (in the Mafia Fraud case that's Bob and Dave) is required to digitally sign their challenges. If challenges are signed then Alice will only proceed with the rest of the protocol run if the challenge indeed comes from Bob; Carol can still pass Dave's challenges to Bob but Alice will refuse to perform the protocol run having noticed that the challenges do not come from Bob. The optimised versions of the Feige-Fiat-Shamir and Guillou-Quisquater protocols make signing easier since they employ a vector of challenges to perform multiple accreditations- in order to avoid multiple messages. Regards, Dimitrios Petropoulos > I'm reading about zero knowledge identity proofs and 'The Mafia Fraud' in > Applied Cryptography. Has no one found a way to perform an identity proof > such that you can prove who you are to a specific person? In the example in > the book Alice proves who she is to Bob who transmits to Carol, and Carol > proves that she is Alice to Dave. I'm curious what the problem is with > creating a proof that Alice is Alice such that only Bob can be assured that > she is Alice so that Carol can't use the proof to identify who she is to > Dave. > > -- > Groove On Dude > Michael Conlen > Obfuscated Networking > [EMAIL PROTECTED] > - Visit our Internet site at http://www.reuters.com Any views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Reuters Ltd. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

I'm not hep to the identification scheme literature, but I'll just a note that in Dimitrios's scheme, Alice can't just sign the challenge, but must also include Dave's signature in her signature. That is, Alice must sign all of {S_dave(challenge), challenge}, not just the challenge by itself. And Dave has to verify that both the challenge and his signature were signed by Alice. Otherwise, Bob could just masquerade Dave's challenge. Marc [EMAIL PROTECTED] wrote: > > I think this is a case for additional protective mechanisms to extend the > protocol semantics (there is nothing in the protocol prohibiting the > verifier to perform a verification on behalf of a third party, which is > the vulnerability exploited in the Mafia Fraud attack). This > 'challenge-relay' can easily be defeated if the verifier (in the Mafia > Fraud case that's Bob and Dave) is required to digitally sign their > challenges. If challenges are signed then Alice will only proceed with > the rest of the protocol run if the challenge indeed comes from Bob; > Carol can still pass Dave's challenges to Bob but Alice will refuse to > perform the protocol run having noticed that the challenges do not come > from Bob. The optimised versions of the Feige-Fiat-Shamir and Guillou- > Quisquater protocols make signing easier since they employ a vector of > challenges to perform multiple accreditations- in order to avoid > multiple messages. > > Regards, > Dimitrios Petropoulos - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

Interestingly enough, I don't think this is the case because the objective is to prevent Alice from acting on Dave's challenges. The confusion may also have arisen because of my use of terms. In this email I'll use 'signing' to mean creation of proof of origin (and classic digital signature algorithms like RSA will suffice). When an entity is trying to prove their identity I'll refer to it as 'acting on' or 'transforming' a challenge. I'll try to clarify: Alice does not need to 'sign' any challenge since she is the 'prover', i.e. the entity that needs to prove the truthfulness and genuineness of her identity to Bob, who is the 'verifier' and therefore the entity producing the challenges. In the course of proving her identity to Bob using a zero knowledge proof of identity, Alice will accept a number of challenges from Bob (the number of which Bob has to decide depending on his perception of risk; each iteration reduces the likelihood of successful impersonation by half), perform some transformations and return the result to Bob who will verify the transformations. In this scheme, Alice can fall victim to Bob and Carol working together to defraud both Alice and Dave (the Mafia Fraud example), whereby Carol masquerades as Alice to Dave and relays Dave's challenges -through Bob- to Alice, who will perform the transformations believing she is proving her identity to Bob (when in fact she is proving it to Dave). Digital signatures (e.g. RSA) on the challenge vectors (along with sensible additional information like prover & verifier identities, timestamps/nonces, etc. to prevent other attacks on the message semantics) would prevent the Mafia Fraud attack since -in this example- Alice would only perform the protocol run if the challenge vector is signed by Bob, whereas Dave will send challenge vectors carrying his signature to Carol (which can no longer relay them to Alice). I cannot see why Alice would have to transform both the challenge and the signature on it (this, incidentally, would mean that you cannot use signatures with message recovery). Apologies if there's something in Marc's email that I have misunderstood; grateful if I could have it pointed out to me. Regards, Dimitrios Petropoulos > I'm not hep to the identification scheme literature, but I'll just a note > that in Dimitrios's scheme, Alice can't just sign the challenge, but must > also include Dave's signature in her signature. That is, Alice must sign all > of {S_dave(challenge), challenge}, not just the challenge by itself. And > Dave has to verify that both the challenge and his signature were signed by > Alice. Otherwise, Bob could just masquerade Dave's challenge. > > Marc > > > [EMAIL PROTECTED] wrote: > > > > I think this is a case for additional protective mechanisms to extend the > > protocol semantics (there is nothing in the protocol prohibiting the > > verifier to perform a verification on behalf of a third party, which is > > the vulnerability exploited in the Mafia Fraud attack). This > > 'challenge-relay' can easily be defeated if the verifier (in the Mafia > > Fraud case that's Bob and Dave) is required to digitally sign their > > challenges. If challenges are signed then Alice will only proceed with > > the rest of the protocol run if the challenge indeed comes from Bob; > > Carol can still pass Dave's challenges to Bob but Alice will refuse to > > perform the protocol run having noticed that the challenges do not come > > from Bob. The optimised versions of the Feige-Fiat-Shamir and Guillou- > > Quisquater protocols make signing easier since they employ a vector of > > challenges to perform multiple accreditations- in order to avoid > > multiple messages. > > > > Regards, > > Dimitrios Petropoulos > > > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to > [EMAIL PROTECTED] - Visit our Internet site at http://www.reuters.com Any views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Reuters Ltd. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

Following up on my previous post (netiquette? what's that?) one further clarification (and summary of my thoughts): the heart of the Mafia Fraud attack lies -I think- in that the challenge messages provide no proof of origin (who created them) nor of intended recipient (who were they intended for). A simple extension of the challenge message to include this information, protected with a simple digital signature scheme, is -in my opinion- enough to overcome the problem. Regards, Dimitrios Petropoulos - Visit our Internet site at http://www.reuters.com Any views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Reuters Ltd. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

Well, I can't be sure that I'm not misunderstanding something either. For the most part, I agree with Dimitrios that challenges with proof of origin are part of the solution to Mafia Fraud attacks. My main point is that I don't think simply signing the challenge is enough. Let me try to restate things symbolically. Nominally, in the naive case, Dave would present Alice with a challenge, X, and Alice would transform & return the challenge: X'. This, as we know, is vulnerable to the Mafia Fraud. What I believe Dimitrios is proposing is for Dave to present both the challenge and a signature on the challenge: {X, S_dave(X)}. Then, Alice would verify that the signature corresponds to the person she thinks she's talking to, and if so she can return the transformed challenge X'. I'm essentially contending that Dave needs to verify that Alice did indeed see the challenge & signature he presented. Consider Mafia Fraud against the above scenario. Dave presents {X, S_dave(X)} to Carol, who forwards it to Bob. Now, Bob can re-sign the challenge himself, and present {X, S_bob(X)} to Alice. Alice will happily verify that the challenge comes from Bob, and return X' to Bob, who then passes it to Carol & then on to Dave. The fraud is successful, because Dave can't tell that Alice saw Bob's signature on the challenge and not his own. So the X' that Alice computes must be a function f(X, S_dave(X)) on both the challenge and the signature. (If, in the naive case, X'=S_alice(X), then to truly prevent the fraud we need X'=S_alice(X,S_dave(X)).) Now the fraud fails because Alice would compute X'=f(X, S_bob(X)), and so Dave (not Alice) would detect the fraud. So it's not enough for Dave to simply sign the challenge & for Alice to verify that signature. Alice must prove to Dave that she saw his signature and not somebody else's. BTW, without giving it any thought, I believe this scheme is safe against replay attacks (because Dave generates a new challenge every time). Does anybody have any thoughts about that? Marc - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero Knowledge Identity Proofs

I now strongly believe that Marc and I are actually talking about the same thing, only we're doing it using different words: Marc talks about Alice providing evidence that she has seen Dave's signature on the challenge whereas I talk about the challenge vector being accompanied by information identifying the originator and the intended recipient, bound/protected via a classical digital signature... In both cases the ultimate goal is the same: Alice is provided with guarantees that the challenge was intended for her and was produced by the person she thinks she is proving her identity to. Essentially in any challenge-response based entity authentication protocol the following must always hold: Consider an authentication protocol where two entities, A and B, exchange the following messages: A -> B(M1) A <- B(M2) A -> B(M3) A <- B(M4) ... In the above diagram A starts the protocol by sending message M1 to B. B replies by sending message M2 to A, etc. It is assumed that each party sends message Mi only after having successfully received (and verified wherever the protocol makes possible) message Mi-1. After completion of the protocol A would like to be sure that : 1. M2, M4, etc. were indeed sent by B 2. M2, M4, etc. were 'fresh' messages, i.e. not replays of older messages 3. M2, M4, etc. were intended for A and not for any other recipient 4. M2, M4, etc. were sent by B as a response to A's M1, M3, etc. (the above protect respectively against masquerading, replay, reflection and interleaving attacks) Similarly for B: 1. M1, M3, etc. were indeed sent by A 2. M1, M3, etc. were 'fresh' messages, i.e. not replays of older messages 3. M1, M3, etc. were intended for B and not for any other recipient 4. M3, M5, etc. were sent by A as a response to B's M2, M4, etc. When developing authentication protocols the above requirements are usually fulfilled as follows: (1) via the use of secrets, (2) via the use of time-variant parameters (3) by using originator or intended recipient identifiers (4) by including in Mi information that could only have originated from Mi-1. The zero knowledge identity proofs can be considered, in my opinion, as low level primitives on top of which strong entity authentication protocols can be built. On their own (without the extensions discussed above) they will always be vulnerable to a number of attacks. Regarding whether the uniqueness of the challenge vector can protect against replay attacks, I guess this depends on the length of the challenge vector. If 10 bits are used this makes the likelihood of successful impersonation by an imposter quite small (2^-10, i.e. 0.00098) but also the number of different vectors is quite small (2^10, i.e. 1024), therefore after 1024 protocol runs you cannot tell whether the responder is sending a fresh reply or whether they are replaying something they intercepted earlier... In such cases maybe other freshness methods should be used (e.g. timestamps, nonces, etc.). Regards, Dimitrios Petropoulos On 27/06/2001 00:00:26 Marc Branchaud wrote: > Well, I can't be sure that I'm not misunderstanding something either. For > the most part, I agree with Dimitrios that challenges with proof of origin > are part of the solution to Mafia Fraud attacks. My main point is that I > don't think simply signing the challenge is enough. > > Let me try to restate things symbolically. Nominally, in the naive case, > Dave would present Alice with a challenge, X, and Alice would transform & > return the challenge: X'. This, as we know, is vulnerable to the Mafia > Fraud. > > What I believe Dimitrios is proposing is for Dave to present both the > challenge and a signature on the challenge: {X, S_dave(X)}. Then, Alice > would verify that the signature corresponds to the person she thinks she's > talking to, and if so she can return the transformed challenge X'. > > I'm essentially contending that Dave needs to verify that Alice did indeed > see the challenge & signature he presented. Consider Mafia Fraud against the > above scenario. Dave presents {X, S_dave(X)} to Carol, who forwards it to > Bob. Now, Bob can re-sign the challenge himself, and present {X, S_bob(X)} > to Alice. Alice will happily verify that the challenge comes from Bob, and > return X' to Bob, who then passes it to Carol & then on to Dave. The fraud > is successful, because Dave can't tell that Alice saw Bob's signature on the > challenge and not his own. > > So the X' that Alice computes must be a function f(X, S_dave(X)) on both the > challenge and the signature. (If, in the naive case, X'=S_alice(X), then to > truly prevent the fraud we need X'=S_alice(X,S_dave(X)).) Now the fraud > fails because Alice would compute X'=f(X, S_