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_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
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
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
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
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
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
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]
