Hagai Bar-El

Information Security Analyst

HBAREL.COM

Interlock protocol and MITM

Message # 1

Date: Wed, 2 Nov 2005
From: Jeff K
To: practicalsecurity at hbarel.com
Subject: [PracticalSecurity] Interlock protocol and MITM

Hi all,
I am designing a secure client-server application. I just had a look at the Interlock protocol that presumably prevents man-in-the-middle attacks in key exchanges. It looks so perfect but I don't recall ever seeing it at work anywhere.
Does anyone here have any thoughts on this? Was it proven vulnerable?
Are there any higher-level protocols using this?
/JK

Message # 2

Date: Wed, 2 Nov 2005
From: "Cuellar, Jorge"
To: "Jeff K" ,
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

Hi Jeff,
yes, it is vulnerable. Take a look at
http://www.cs.columbia.edu/~smb/papers/interlock.pdf http://en.wikipedia.org/wiki/Interlock_Protocol
What are the requirements in your system?
Do you want an unauthenticated key exchange, or an authenticated one?
Why you do not use IKEv2 or something of that type?
Best,
Jorge

-----Original Message-----
From: PracticalSecurity-bounces at hbarel.com
[mailto:PracticalSecurity-bounces at hbarel.com] On Behalf Of Jeff K
Sent: Wednesday, November 02, 2005 10:37 AM
To: practicalsecurity at hbarel.com
Subject: [PracticalSecurity] Interlock protocol and MITM
Hi all,
I am designing a secure client-server application. I just had
a look at the Interlock protocol that presumably prevents
man-in-the-middle attacks in key exchanges. It looks so
(snip)

Message # 3

Date: Wed, 2 Nov 2005
From: Sarad AV
To: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

hi,
Yes, the Interlock Protocol is insecure.In classical cryptography, we cannot setup up a provably secure communication channel between two authentic communicating parties when there is a
man-in-the-middle without a previously shared secret.In practice I am not sure what the level of risk involved actually is.
Sarad.
--- "Cuellar, Jorge" wrote:

Hi Jeff,
yes, it is vulnerable. Take a look at
http://www.cs.columbia.edu/~smb/papers/interlock.pdf
http://en.wikipedia.org/wiki/Interlock_Protocol
What are the requirements in your system?
Do you want an unauthenticated key exchange, or an
authenticated one?
Why you do not use IKEv2 or something of that type?
Best,
Jorge

Jorge R Cuellar Tel: +49 89 636
47 585
Jorge.Cuellar at siemens.com

Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com

Message # 4

Date: Wed, 02 Nov 2005
To: Jeff K
From: Greg Rose
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

At 11:37 2005-11-02 +0200, Jeff K wrote:

Hi all,
I am designing a secure client-server application. I just had a look
at the Interlock protocol that presumably prevents man-in-the-middle
attacks in key exchanges. It looks so perfect but I don't recall ever
seeing it at work anywhere.
Does anyone here have any thoughts on this? Was it proven vulnerable?
Are there any higher-level protocols using this?

I analysed the protocol at one point. Its big failure is that if it detects a man-in-the-middle, you must assume that the secret was burned, and fall back to a more secure method of re-provisioning a new secret. In some ways this is a big deal; it makes a very severe denial-of-service attack extremely easy. In other ways, it isn't, because the attacker can get nothing except the denial-of-service, so they are unlikely to bother, and then it works very well...
Greg.
Greg Rose INTERNET: ggr at qualcomm.com Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drive http://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C

Message # 5

Date: Sat, 5 Nov 2005
From: Jeff K
To: "Cuellar, Jorge"
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

Hi Jorge,
On 11/2/05, Cuellar, Jorge wrote:

Hi Jeff,
yes, it is vulnerable. Take a look at
http://www.cs.columbia.edu/~smb/papers/interlock.pdf
http://en.wikipedia.org/wiki/Interlock_Protocol
What are the requirements in your system?
Do you want an unauthenticated key exchange, or an authenticated one?
Why you do not use IKEv2 or something of that type?
Best,
Jorge
Jorge R Cuellar Tel: +49 89 636 47 585
Jorge.Cuellar at siemens.com

Thanks a lot! I will read this with a lot of interest.
What I need is basically an unauthenticated channel over which I want to provision credentials. How to establish trust when there is no authentication is a different issue, but my first desire was a tunnel between two still-unauthenticated ends. I tend to believe, at this point, that this is not possible. In order to assure no MITMs you need some credentials in place...
Thanks!
/JK

Message # 6

Date: Thu, 10 Nov 2005
From: "Cuellar, Jorge"
To: "Hagai Bar-El" , "Sarad AV" ,
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

Hi Hagai,

Generally put, there is no way to establish a MITM-free link
without a pre-shared secret. And, if a pre-shared secret is
available, as Jorge noted, one can deploy IKE-like protocols.
Is this assertion incorrect?

It is not precise: you need some kind of "trusted information" but this trusted information does not have to be a pre-shared secret.
There must be some secret involved (the party to be authenticated knows some secret) but this secret may be related to public or to shared information.
It may be the knowledge that the corresponding party indeed "owns" a certain public key ("own" means here that this other party is the only one that is able to access the corresponding private key, besides perhaps very trusted third parties that will not perform MITM and will not disclose sensitive information).
For instance you may use an identity-based public key system, in which there is a public algorithm to obtain the public key out of the public name of the entity.
But without any trusted information known by A, relating to a secret known by B (and trusted parties), it is impossible to construct a one-sided secure channel, in the sense that from the point of view of A there is no MITM (A is assured, he is talking to B). (To construct a two sided secure channel, you need also the other way around). Of course, one particular case is when A also knows the secret of B (and both are trusted not to disclose sensitive information).

I agree with the vulnerability of the protocol. Yet, I am not
convinced that the alternative that is offered in chapter IV
is as bad as it is described to be.

I agree.
There is another way of constructing "secure" channels out of nothing, but hoping that some initial information has not been tampered with.
For instance, A creates a pair (p,P) of public and private keys, just for this communication ("purpose-built keys") and sends (A,P) to B.
If this communication went right, B can use P to communicate securely with A. See
http://www.ietf.org/internet-drafts/draft-bradner-pbk-frame-06.txt
There are similar methods around.
But if A does not know that B has a secret (i.e.: something that he only knows or he can access, except trusted parties and A) he can not be assured that he is talking to B.
Best,
Jorge

-----Original Message-----
From: Hagai Bar-El [mailto:info at hbarel.com]
Sent: Thursday, November 10, 2005 10:08 AM
To: Sarad AV; Cuellar, Jorge; Jeff K
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM
Hi Sarad,
At 02/11/05 16:00, Sarad AV wrote:

hi,
Yes, the Interlock Protocol is insecure.In classical

cryptography, we

cannot setup up a provably secure communication channel between two
authentic communicating parties when there is a man-in-the-middle
without a previously shared secret.In practice I am not sure

what the

level of risk involved actually is.
Sarad.

To the best of my knowledge, this is indeed the case.
Generally put, there is no way to establish a MITM-free link
without a pre-shared secret. And, if a pre-shared secret is
(snip)

Message # 7

Date: Thu, 10 Nov 2005
To: Sarad AV , Jorge Cuellar ,Jeff K
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Interlock protocol and MITM
Cc: practicalsecurity at hbarel.com

Hi Sarad,
At 02/11/05 16:00, Sarad AV wrote:

hi,
Yes, the Interlock Protocol is insecure.In classical
cryptography, we cannot setup up a provably secure
communication channel between two authentic
communicating parties when there is a
man-in-the-middle without a previously shared
secret.In practice I am not sure what the level of
risk involved actually is.
Sarad.

To the best of my knowledge, this is indeed the case. Generally put, there is no way to establish a MITM-free link without a pre-shared secret. And, if a pre-shared secret is available, as Jorge noted, one can deploy IKE-like protocols. Is this assertion incorrect?
If the assertion is correct, Jeff does not have a way of obtaining what he wants, which is to FIRST to have a MITM-free channel, and LATER to use it for provisioning.
Now per the paper Jorge sent a link to (about the vulnerability of Interlock):

--- "Cuellar, Jorge"
wrote:

Hi Jeff,
yes, it is vulnerable. Take a look at
http://www.cs.columbia.edu/~smb/papers/interlock.pdf

I saw this paper once, but was happy to read it again.
I agree with the vulnerability of the protocol. Yet, I am not convinced that the alternative that is offered in chapter IV is as bad as it is described to be. I agree that broken encrypted messages cannot contain values that are not known to both parties. However, nonces, time-stamps, etc. can easily be integrated along with a plain-text version on the same message without hampering security - they are assumed to be well-known anyway. I see nothing wrong with specifying the time-stamp or nonce in the clear, concatenated to the message that holds the ciphertext fragment. With regards to the limitation of hashed passwords (that a half-password cannot be verified because passwords are stored as hashes), I believe this can easily be resolved by storing two hashes, one for the first part and one for the second part, or one for the first part and one for the entire password. This should work.
On the other hand, I see a bigger problem with this alternative, which is not stated in the paper, but which was implied by Greg Rose on this list, which is that once an attack succeeds - the secret is burned. I am not sure Greg referred to the alternative in chapter IV, but I think it can apply here equally well:
Once an attack succeeds, the attacker (Z) cannot complete the protocol, but he does know one half of the password of the other side (say, of A). So, he can use this half to get the entire password of the other side (B) when running the protocol in the other direction, if the other side (B) is the one to send the first message. If the other side (B) cannot be made to send the first message, the attacker can send the half he knows (of A's password) to trigger B to send his first part, and then go back to the original direction to convince A to give it all after presenting B's first part. Of course, this behavior will ring all bells in the world, but who cares...
I guess all this sends us back to Jorge's point: Given there is a shared secret, who not use IKE?...
Hagai.

Message # 8

Date: Thu, 10 Nov 2005
From: "Cuellar, Jorge"
To: "Hagai Bar-El"
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

Hi Hagai,

I agree that instead of a shared secret the parties can use a
trusted piece of information held by one side, that is securely
1-to-1 related to a secret information held by the other, and
vice versa.

This is true. Note that A does not have to know that "A" knows the secret, but only that the person he wants to talk knows the secret.

In a sense, the requirements to assure MITM-protection are very close
(identical?) to the requirements for knowing who you are talking to
(at least to the level of a linked pseudonym). This leads us back to
the obvious understanding that MITM protection cannot be established
while anonymity is in place.

Yes, it is possible to have "authorization without authentication" and to establish trust even under some degree of anonymity, but this is at least a linked pseudonym.

There is another way of constructing "secure" channels out

of nothing,

but hoping that some initial information has not been tampered with.
For instance, A creates a pair (p,P) of public and private keys, just
for this communication ("purpose-built keys") and sends (A,P) to B.
If this communication went right, B can use P to communicate
securely with A. See
http://www.ietf.org/internet-drafts/draft-bradner-pbk-frame-06.txt

I haven't seen the document yet, but how does B know that Z hasn't
replaced P by P'?

He does not: if Z has replaced P by P' in the initial communication, the assumptions of the protocol are not met. (They were stated in "If this communication went right, "). Only if the first exchange was not tampered with, there is no MITM.

Does A sign P with a private key for which B has
the public counterpart pre-provisioned?

This is one possibility.
Best,
Jorge

Message # 9

Date: Thu, 10 Nov 2005
To: "Cuellar, Jorge"
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Interlock protocol and MITM
Cc: practicalsecurity at hbarel.com

Hi Jorge,
At 10/11/05 13:35, Cuellar, Jorge wrote:

Generally put, there is no way to establish a MITM-free link
without a pre-shared secret. And, if a pre-shared secret is
available, as Jorge noted, one can deploy IKE-like protocols.
Is this assertion incorrect?

It is not precise: you need some kind of "trusted information"
but this trusted information does not have to be a pre-shared secret.
There must be some secret involved (the party to be authenticated
knows some secret) but this secret may be related to public
or to shared information.
It may be the knowledge that the corresponding party indeed "owns"
a certain public key ("own" means here that this other party is
the only one that is able to access the corresponding private key,
(snip)

Right, I agree. I phrased my general assertion too quickly without relating to PKI-style solutions that may be as secure as symmetric ones. I agree that instead of a shared secret the parties can use a trusted piece of information held by one side, that is securely 1-to-1 related to a secret information held by the other, and vice versa.
In a sense, the requirements to assure MITM-protection are very close (identical?) to the requirements for knowing who you are talking to (at least to the level of a linked pseudonym). This leads us back to the obvious understanding that MITM protection cannot be established while anonymity is in place.

There is another way of constructing "secure" channels out of nothing,
but hoping that some initial information has not been tampered with.
For instance, A creates a pair (p,P) of public and private keys, just
for this communication ("purpose-built keys") and sends (A,P) to B.
If this communication went right, B can use P to communicate
securely with A. See
http://www.ietf.org/internet-drafts/draft-bradner-pbk-frame-06.txt

I haven't seen the document yet, but how does B know that Z hasn't replaced P by P'? Does A sign P with a private key for which B has the public counterpart pre-provisioned?
Hagai.

Message # 10

From: pgut001 at cs.auckland.ac.nz (Peter Gutmann)
To: info at hbarel.com, jeffko12 at gmail.com, jorge.cuellar at siemens.com,
Date: Mon, 14 Nov 2005
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

"Cuellar, Jorge" writes:

Generally put, there is no way to establish a MITM-free link
without a pre-shared secret. And, if a pre-shared secret is
available, as Jorge noted, one can deploy IKE-like protocols.
Is this assertion incorrect?

It is not precise: you need some kind of "trusted information" but this
trusted information does not have to be a pre-shared secret. There must be
some secret involved (the party to be authenticated knows some secret) but
this secret may be related to public or to shared information.

The information doesn't even have to be secret. Some voice crypto protocols are authenticated purely by using the voice of the speaker, which isn't secret at all. The strength lies in the fact that performing a real-time speech MITM is hard.
Peter.

Message # 11

Date: Sun, 13 Nov 2005
From: "Cuellar, Jorge"
To: "Peter Gutmann" , ,
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Interlock protocol and MITM

Peter Gutmann writes:

Generally put, there is no way to establish a MITM-free

link without

a pre-shared secret. And, if a pre-shared secret is available, as
Jorge noted, one can deploy IKE-like protocols.
Is this assertion incorrect?

It is not precise: you need some kind of "trusted information" but
this trusted information does not have to be a pre-shared

secret. There

must be some secret involved (the party to be authenticated

knows some

secret) but this secret may be related to public or to

shared information.
The information doesn't even have to be secret. Some voice
crypto protocols are authenticated purely by using the voice
of the speaker, which isn't secret at all. The strength lies
in the fact that performing a real-time speech MITM is hard.

This is true. I was using the term "secret" to represent some "trusted information" or "trusted resource" to which only the party to be authenticated (say "A") has access to.
It may be a key, a procedure, etc. In the case you describe it is the procedure for say responding a question on real time with a certain voice profile. This procedure is "secret" in the sense that only A should be able to access the procedure.
Jorge