Zero Knowledge Identity Proofs

[Dimitrios.Petropoulos at reuters.com]

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




-----------------------------------------------------------------
        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 majordomo at wasabisystems.com