Subject: [multipathtcp] Hash Chain Security Solution

From: "Ford, Alan" <[email-masked]>
Date: Tue, 7 Dec 2010 09:38:07 -0000

Folks,

We have been looking at another possible security solution for MPTCP,
based around Hash Chains. This mail summarises some early thoughts on
this topic, although there are still many open issues and thoughts would
be most welcome. We hope this could be one topic for discussion in next
week's security-focused interim.

A hash chain is a mechanism for authenticating endpoints without any
need for exchanging keying material. Essentially, a hash chain is a list
of hashes based on an initial random seed, S:
H[0] = H(S); H[1] = H(H[0]); H[2] = H(H[1]); ...; H[n] = H(H[n-1])

One entity can identify itself by giving H[n]. The hashes are
non-reversible, so no observer could know that H[n-1] precedes H[n] in
the chain. So, when the hash chain owner needs to authenticate itself to
a peer, it will send H[n-1]. The receiver can then hash this and get
H[n], and it knows the sender is the same as originally sent H[n]. Once
a hash chain entry has been used, it is never used again for
authentication, to prevent replay attacks. This can be used to
authenticate MPTCP control messages, most notably MP_JOIN, to join a
subflow to an existing MPTCP connection.

Whatever mechanism for authentication is used, we still need a way for
additional subflows (with MP_JOIN) to identify which connection they
belong to, so the Hash Chain is not enough for the SYN handshake. In the
following proposal, we use the same Key/Token mechanism as for the
current (-02) draft proposal, in addition to the hash chain.

A proposal for the message exchange is as follows:

         Host A                                     Host B
------------------------                   ------------------------
Address A1    Address A2                   Address B1    Address B2
----------    ----------                   ----------    ----------
    |             |                            |             |
    |     SYN + MP_CAPABLE(Key-A, H-A[n])      |             |
    |----------------------------------------->|             |
    |<-----------------------------------------|             |
    |    SYN/ACK + MP_CAPABLE(Key-B, H-B[n])   |             |
    |             |                            |             |
    |             |                            |             |
    |             |     SYN + MP_JOIN(Token-B, H-A[n-1])     |
    |             |----------------------------------------->|
    |             |<-----------------------------------------|
    |             |   SYN/ACK + MP_JOIN(Token-A, H-B[n-1])   |
    |             |                            |             |
    |             | HMAC(K=(K-A+K-B), M=(H-A[n-1]+H-B[n-1])) |
    |             |----------------------------------------->|
    |             |<-----------------------------------------|
    |             | HMAC(K=(K-B+K-A), M=(H-B[n-1]+H-A[n-1])) |
    |             |                            |             |

The key points of this message exchange are as follows:

Token-A = Hash(IDSN-A); IDSN-A = Hash(Key-A)
Token-B = Hash(IDSN-B); IDSN-B = Hash(Key-B)
H-A[n] = nth entry in A's hash chain

On connection initiation, each end host will generate a hash chain
unique for this connection. The length of the chain is up to the
generating host, and it is seeded on a random number.

On each new control message (MP_JOIN, and probably REMOVE_ADDR and
ADD_ADDR), the previous entry in the chain will be sent as an
authentication token. The receiver will hash the received hash and see
if it matches the entry it has last seen. If it does not, it will try
hashing it a few more times (in case some entries had got lost). We can
retransmit the same hash chain entry on a retransmission of a packet,
but it must only ever be used for one control message (if it fails, we
move on in the hash chain).

On a MP_JOIN handshake, once the token and hash-chains entry have been
verified, a HMAC is also exchanged in the first two payload packets.
This is very similar to the HMAC in the current (-02 draft) proposal,
with the key based on the keys exchanged in the first handshake, and the
message is based on fresh information - the hash chain entries that have
just been exchanged. This provides additional verification of the
validity of the peer.

The reason for doing this HMAC exchange would be the potential threat
from passive listeners who are able to break into a connection by
finding out the hash chain entry on a SYN/MP_JOIN while preventing this
reaching the destination (e.g. through a DoS attack).

* The use of hash chains ensures that seeing the first SYN/MP_CAPABLE
exchange is not enough to break into a connection.
* The use of HMAC ensures that the peer will also have seen the first
SYN/MP_CAPABLE exchange.

We will also need a new TCP option - let's call it MP_KEY - that can be
used to refresh the hash chain if the connection runs out of entries. An
easy way of doing this is just to have a message containing both the
final entry of the first hash chain and H[n] of the new chain.

There remain plenty of open questions with this proposal:

* Do we need the HMAC exchange?

* I think we will struggle with more than 64 bits for a hash chain entry
due to limited option space. A hash truncated to 64-bits is probably the
maximum we can manage. (RFC2104 recommends no less than 80 bits of
SHA-1, but we really don't want MP_JOIN and MP_CAPABLE to be longer than
128 bits.)

* Do we need to signal the length of the hash chain and/or the index of
the chain when we send the entry? I don't think we need this, but it may
make determining where we are in the chain in the event of errors
easier. (Otherwise chains would need a window of validity, and if
searching for X entries does not find a valid entry, give up.)

* Can we design the initial SYN exchange to be stateless from the
server's end? (At the moment, a server will need to generate a hash
chain and store it - this is relatively expensive from both processing
and especially state.) (We could deliver the hash chain entry on the
first non-SYN packet in each direction, but that gives a (very small)
window of opportunity for an attacker to insert its own hash.)

And finally, is it appropriate?! Thoughts very much welcome!

Regards,
Alan

---

From: Marshall Eubanks <[email-masked]>
Date: Tue, 7 Dec 2010 08:45:52 -0500

On Dec 7, 2010, at 4:38 AM, Ford, Alan wrote:

> authentication, to prevent replay attacks.

This sounds very similar to the multicast TELSA idea - see

http://tools.ietf.org/id/draft-ietf-msec-tesla-intro-04.txt 

http://www.securemulticast.org/msec-bof-5-Perrig-tesla-ietf-bofPDF.PDF

In TELSA the hash chain was called a "one-way chain," and the basic idea was to authenticate a multicast stream to multiple
receivers (instead of authenticating multiple paths to the same receiver). TESLA used a public key scheme to set up the initial 
trust relationship, and the one-way chain was used to maintain that relationship and to verify symmetric keys. There
are differences (TELSA is concerned with encryption, and thus maintaining trust in keys), but also, it seems to me,
a fair number of similarities. 

Is timing the only way that replays are detected ? That seems dangerous in a multi-path setting, and is the real point behind TESLA. 

If I get two messages within N milliseconds, both claiming to be legit and both containing the
same H[n-1], always picking the first message will fail at times if N < or ~ the RTT; an attacker can
easily generate such messages if they are located topologically close to the actual source. 

The TELSA idea was to 

- send H[n] and a MAC of the message using H[n-1] (not yet revealed)

- wait long enough that every possible receiver would have received that message 

- then reveal H[n-1], allowing the previous message to be authenticated. H[n-1] is authenticated by verifying that H[H[n-1]] = H[n]

In this case, a TESLA like idea could protect against
replay attacks. Say that there is a trusted path, and it was used to communicate H[n].

A new path could send H[n] and a MAC of the message using H[n-1]. Then, after a suitable delay, any path sends H[n-1] and a MAC of the message using H[n-2].

The receiver can

- verify that H[n] = H[H[n-1]] and
- verify that the MAC of the old message with H[n-1] checks out. 

That way, a replay attacker could not send a proper MAC, as they would not know H[n-1] until it was too late. 

Of course, as with TESLA, this would rely on loose clock synchronization between sender and receiver. 

> This can be used to

Are DOS attacks an issue (i.e., could an attacker force the issuance of more messages) ? That would exhaust the chain. 

Regards
Marshall

> _______________________________________________
> multipathtcp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/multipathtcp
>

---

From: "Ford, Alan" <[email-masked]>
Date: Wed, 8 Dec 2010 11:27:33 -0000

Hi Marshall, all,

Thanks for the comments. There are certainly interesting similarities
between the proposals; some thoughts inline...

> Is timing the only way that replays are detected ? That seems
dangerous in a
> multi-path setting, and is the real point behind TESLA.
> 
> If I get two messages within N milliseconds, both claiming to be legit
and
> both containing the
> same H[n-1], always picking the first message will fail at times if N
< or ~
> the RTT; an attacker can
> easily generate such messages if they are located topologically close
to the
> actual source.

Indeed, this is a clear threat. The idea we had for a partial solution
to this was to use the HMAC, keyed on the "Key" exchanged in the
original MPTCP connection initiation (MP_CAPABLE). This is still
vulnerable to a racing attacker if he had seen this initial exchange,
however. Whether this is a threat we need to cope with is another issue,
however.

> - wait long enough that every possible receiver would have received
that
> message
> 
> - then reveal H[n-1], allowing the previous message to be
authenticated. H[n-
> 1] is authenticated by verifying that H[H[n-1]] = H[n]
> 
> A new path could send H[n] and a MAC of the message using H[n-1].
Then, after
> a suitable delay, any path sends H[n-1] and a MAC of the message using
H[n-
> 2].
> That way, a replay attacker could not send a proper MAC, as they would
not
> know H[n-1] until it was too late.

It sounds as if this would remove the threat we have against a listener
picking up the HMAC Key from the initial MPTCP connection
initialisation, at the cost of more hash entries used. A simple message
exchange for this is below; unfortunately, this seems to require a
six(!)-way handshake. I wonder if we can make it any shorter?

         Host A                                     Host B
------------------------                   ------------------------
Address A1    Address A2                   Address B1    Address B2
----------    ----------                   ----------    ----------
    |             |                            |             |
    |     SYN + MP_CAPABLE(Key-A, H-A[n])      |             |
    |----------------------------------------->|             |
    |<-----------------------------------------|             |
    |    SYN/ACK + MP_CAPABLE(Key-B, H-B[n])   |             |
    |             |                            |             |
    |             |                            |             |
    |             |     SYN + MP_JOIN(Token-B, H-A[n-1])     |
    |             |----------------------------------------->|
    |             |<-----------------------------------------|
    |             |   SYN/ACK + MP_JOIN(Token-A, H-B[n-1])   |
    |             |                            |             |
    |             |  HMAC(K=H-A[n-2], M=(H-A[n-1]+H-B[n-1])) |
    |             |----------------------------------------->|
    |             |<-----------------------------------------|
    |             |  HMAC(K=H-B[n-2], M=(H-B[n-1]+H-A[n-1])) |
    |             |                            |             |
    |             |         ACK + MP_VERIFY(H-A[n-2])        |
    |             |----------------------------------------->|
    |             |<-----------------------------------------|
    |             |         ACK + MP_VERIFY(H-B[n-2])        |
    |             |                            |             |

This exchange proves that Host A was actually the owner of the hash
chain - an attacker would not be able to produce H-A[n-2] in the third
part of the handshake. Unfortunately, this really is an inconveniently
long and expensive handshake (although, the MP_VERIFY can probably be
used along with application data).

> Are DOS attacks an issue (i.e., could an attacker force the issuance
of more
> messages) ? That would exhaust the chain.

I don't think this is an issue for us - a host would not use an entry
from its hash chain without the peer first providing a valid entry from
its chain.

Regards,
Alan

---

From: Javier Diez <[email-masked]>
Date: Wed, 8 Dec 2010 13:31:02 +0100

Hello Alan, all,

As you know, Marcelo and I were working around the idea of providing a MPTCP
security solution based on Hash Chains.

The idea is, as you said, to protect the MP_JOIN messages by introducing an
element of the hash chain that must be replied with another of the peer, as
a way to perform source authentication. Of course, having the anchors (Hn)
been exchanged during the initial 3WH, in order to later could verify
whether the received hash values belongs to the chain.

This idea is based on WIMP-F proposal by Ylitalo (
http://tools.ietf.org/html/draft-ylitalo-multi6-wimp-01), which in turn is
based on TESLA. We also proposed an interactive exchange mechanism of the
hash chain values. Since we don't consider lost entries (reusing until
succeed), hashing several times would determine that an attack has occurred.
This poses a constraint, since various paths cannot be arranged
simultaneously, but sequentially. Besides, we were thinking on a fixed
length chain.

The problem was that, unlike WIMP-F and TESLA that provide not only source
authentication but also integrity protection of the messages, we couldn´t
manage to do so with the new address that is intended to be joined the
connection, since due to NAT traversal considerations the original address
could be modified and it would be impposible to differentiate from a
tampering attack. Therefore, a MitM attacker could modify the new address by
replacing it with its own address, even an off-path one and the attack would
be undetectable.

As you mention, another outstanding issue is the need for the
server from keeping stateless until the connection is established. To do so,
some kind of non-obvious syn-cookie solution would be required, including of
course the exchanged hash chain material.

Regards,
Javier Diez.

---

From: "Ford, Alan" <[email-masked]>
Date: Wed, 8 Dec 2010 13:41:40 -0000

Hi again all,

Following up my own mail, but having thought about this more I don't
think we need the HMAC and this could in fact be achieved with a four
way handshake just using the hash chain...

         Host A                                     Host B
    |             |            MP_VERIFY(H-A[n-2])           |
    |             |            MP_VERIFY(H-B[n-2])           |
    |             |                            |             |

> used along with application data).

This is still the case - once the TCP subflow has been established, the
exchange of the previous hash chain entry then acts as proof that the
end host is the same as sent the SYN (so an attacker couldn't just steal
the hash chain entry and take over immediately).

There are still possible attacks on this - e.g. an attacker who could
race both ends could possibly hijack the connection, but that's almost a
MITM then, and probably outside of scope for our threats.

Might this be a suitable solution?

Regards,
Alan

---

From: Javier Diez <[email-masked]>
Date: Wed, 8 Dec 2010 20:00:56 +0100

Hello,

I wonder why you need the MP_VERIFY part. I mean, the exchange of Hn-1 hash
values in both directions already acts in itself as a proof that the host
that is trying to add the new address is the same as the one that
established the connecction. In fact, Host B doesn't reply with its SYN+ACK
(and conveying its hash value) until it checks the received hash
value (H-A[n-1]) is the following in the peer's chain.

Just the owner of the hash chain can add new subflows. Therefore, for an
attacker the key part is to steal the anchors of the legitimate peers during
the establishment (or better, to replace them with its own chain), not to
send two consecutive hash values once he has stolen the legitimate anchor
... I guess this wouldn't be a problem.

Regards,
Javier Diez.

---

From: "Ford, Alan" <[email-masked]>
Date: Thu, 9 Dec 2010 00:44:19 -0000

Hi Javier,

The purpose of the second hash chain entry is to protect against the
threat Marshall identified in his earlier mail, i.e. one where an
attacker can passively listen to the SYN with the valid hash chain
entry, steal this entry, and race (and beat) the valid SYN to the
endpoint. In other words, it is theoretically possible or a passive
listener to become an active attacker, without needing to be an on-path
attacker on the original subflow. This is suboptimal.

By forcing the host to also reveal the next hash chain entry (what I had
termed MP_VERIFY) after the SYN exchange, we ensure that the peer to
which we've set up the subflow genuinely is the owner of the hash chain,
and not someone who just listened to the hash and re-sent it. It would
not be possible (as far as I can see) for an attacker to break into this
connection once the subflow has been set up and verified, with two hash
chain entries.

I'm not necessarily saying this is the correct solution to the problem;
but it seems to be a potential solution.

Regards,

Alan

From: Javier Diez [mailto:[email-masked]] 
Sent: 08 December 2010 19:01
To: Ford, Alan
Cc: Marshall Eubanks; [email-masked]
Subject: Re: [multipathtcp] Hash Chain Security Solution

Hello,

I wonder why you need the MP_VERIFY part. I mean, the exchange of Hn-1
hash values in both directions already acts in itself as a proof that
the host that is trying to add the new address is the same as the one
that established the connecction. In fact, Host B doesn't reply with its
SYN+ACK (and conveying its hash value) until it checks the received hash
value (H-A[n-1]) is the following in the peer's chain. 

Just the owner of the hash chain can add new subflows. Therefore, for an
attacker the key part is to steal the anchors of the legitimate peers
during the establishment (or better, to replace them with its own
chain), not to send two consecutive hash values once he has stolen the
legitimate anchor ... I guess this wouldn't be a problem.

Regards,

Javier Diez. 

Hi again all,

        Host A                                     Host B

Regards,
Alan

---

From: Javier Diez <[email-masked]>
Date: Thu, 9 Dec 2010 10:22:37 +0100

Hi Alan, all,

AFAICT the threath identified by Marshall applies to a loose-time
synchronized approach between a sender and the receivers like TESLA, but I
think it is not a concern in an interactive exchange of hash chain values
approach between two hosts. The exchange in itself acts as an event as time
does in the other approach.

If I undestand the scenario correctly, the problem here is not the race
condition, but the fact that an attacker is located as an MitM during the
initiation of a new subflow (provided that it wasn´t present during the
establishment of the connection). For an attacker could listen the valid
hash entry, it is required that this attacker is placed MitM. An if so, this
MitM could re-send the hash value, as you said, but not just beating the
legitimate host in a potential race, but impersonating it, and then the
interesting thing would be to tampering the new address intended to add the
new subflow with the attacker's one.

I cannot see how sending two consecutive entries could protect this attack,
since the attacker is able to keep for a while as an MitM and forward both
entries in both directions (acting as a kind of middlebox, you know), as
simple as if it were just one. Moreover, if the MitM had various addresses,
it could use another one (not on-path) in the new sublfow, becoming this
attack in an off-path one (or kind of time-shifted one), I think ...

Regards,
Javier Diez.

On Thu, Dec 9, 2010 at 1:44 AM, Ford, Alan <[email-masked]> wrote:

>  Hi Javier,
>
>
>
> The purpose of the second hash chain entry is to protect against the threat
> Marshall identified in his earlier mail, i.e. one where an attacker can
> passively listen to the SYN with the valid hash chain entry, steal this
> entry, and race (and beat) the valid SYN to the endpoint. In other words, it
> is theoretically possible or a passive listener to become an active
> attacker, without needing to be an on-path attacker on the original subflow.
> This is suboptimal.
>
>
>
> termed MP_VERIFY) after the SYN exchange, we ensure that the peer to which
> we’ve set up the subflow genuinely is the owner of the hash chain, and not
> someone who just listened to the hash and re-sent it. It would not be
> possible (as far as I can see) for an attacker to break into this connection
> once the subflow has been set up and verified, with two hash chain entries.
>
>
>
> I’m not necessarily saying this is the correct solution to the problem; but
> it seems to be *a* potential solution.
>
>
>
> Regards,
>
> Alan
>
>
>
> *From:* Javier Diez [mailto:[email-masked]]
> *Sent:* 08 December 2010 19:01
> *To:* Ford, Alan
> *Cc:* Marshall Eubanks; [email-masked]
> *Subject:* Re: [multipathtcp] Hash Chain Security Solution
>
>
>
> Hello,
>
>
>

---

From: "Ford, Alan" <[email-masked]>
Date: Thu, 9 Dec 2010 09:48:22 -0000

The issue with this threat is that the attacker does not need to be a MitM. By MitM, I mean an active attacker, i.e. one who can read and change packets. This threat applies also to passive attackers, i.e. one who can just listen. A common scenario for a passive attacker would be open wireless LAN.

If the only authentication on the SYN was a single hash entry, a passive attacker could listen to this but stop it from getting to the receiver, or delay it by DoS, or just use a faster link that means the attacker can race and beat the genuine SYN to the receiver with its own SYN, authenticated with the genuine hash entry. It then is able to set up a new subflow, and the genuine SYN will be ignored if it arrives later.

In other words, the use of a single hash chain entry could allow an attacker to upgrade himself from a passive attacker to an active attacker by opening a subflow. This is the threat we first tried to get around with the HMAC in my initial hash chain mail, but now I think can be solved better and easier with the second hash entry.

The use of the second hash entry verifies that the person with which the new subflow has been set up is the owner of the hash chain. Since this second entry would only be revealed on a successful connection setup, it could not be used by a passive attacker since he would have to sniff both hash entries, but could only get the second one if the genuine peer had undertaken the SYN exchange (by which point the hash chain entry has been used and the attacker would not be able to replay it). I hope this makes sense now? I would try drawing a diagram, but it's a bit tricky to show the time dimension in it.

I'm not saying we have to protect against this, but this would seem a reasonably plausible approach if we wanted to.

Regards,

Alan

From: Javier Diez [mailto:[email-masked]] 
Sent: 09 December 2010 09:23
To: Ford, Alan
Cc: Marshall Eubanks; [email-masked]
Subject: Re: [multipathtcp] Hash Chain Security Solution

Hi Alan, all,

AFAICT the threath identified by Marshall applies to a loose-time synchronized approach between a sender and the receivers like TESLA, but I think it is not a concern in an interactive exchange of hash chain values approach between two hosts. The exchange in itself acts as an event as time does in the other approach.

If I undestand the scenario correctly, the problem here is not the race condition, but the fact that an attacker is located as an MitM during the initiation of a new subflow (provided that it wasn´t present during the establishment of the connection). For an attacker could listen the valid hash entry, it is required that this attacker is placed MitM. An if so, this MitM could re-send the hash value, as you said, but not just beating the legitimate host in a potential race, but impersonating it, and then the interesting thing would be to tampering the new address intended to add the new subflow with the attacker's one.

I cannot see how sending two consecutive entries could protect this attack, since the attacker is able to keep for a while as an MitM and forward both entries in both directions (acting as a kind of middlebox, you know), as simple as if it were just one. Moreover, if the MitM had various addresses, it could use another one (not on-path) in the new sublfow, becoming this attack in an off-path one (or kind of time-shifted one), I think ...

Regards,
Javier Diez.

Hi Javier,

The purpose of the second hash chain entry is to protect against the threat Marshall identified in his earlier mail, i.e. one where an attacker can passively listen to the SYN with the valid hash chain entry, steal this entry, and race (and beat) the valid SYN to the endpoint. In other words, it is theoretically possible or a passive listener to become an active attacker, without needing to be an on-path attacker on the original subflow. This is suboptimal.

By forcing the host to also reveal the next hash chain entry (what I had termed MP_VERIFY) after the SYN exchange, we ensure that the peer to which we've set up the subflow genuinely is the owner of the hash chain, and not someone who just listened to the hash and re-sent it. It would not be possible (as far as I can see) for an attacker to break into this connection once the subflow has been set up and verified, with two hash chain entries.

I'm not necessarily saying this is the correct solution to the problem; but it seems to be a potential solution.

Regards,

Alan

Hello,

I wonder why you need the MP_VERIFY part. I mean, the exchange of Hn-1 hash values in both directions already acts in itself as a proof that the host that is trying to add the new address is the same as the one that established the connecction. In fact, Host B doesn't reply with its SYN+ACK (and conveying its hash value) until it checks the received hash value (H-A[n-1]) is the following in the peer's chain. 

Just the owner of the hash chain can add new subflows. Therefore, for an attacker the key part is to steal the anchors of the legitimate peers during the establishment (or better, to replace them with its own chain), not to send two consecutive hash values once he has stolen the legitimate anchor ... I guess this wouldn't be a problem.

Regards,

Javier Diez. 

Hi again all,

        Host A                                     Host B

Regards,
Alan

---

From: Javier Diez <[email-masked]>
Date: Thu, 9 Dec 2010 14:58:33 +0100

Ok. I understand now the reduced scenario covered. I wonder whether the
overhead introduced by adding two more messages for all the subflows is
worth it "just" to couple with passive attackers.

Regards,
Javier Díez.

On Thu, Dec 9, 2010 at 10:48 AM, Ford, Alan <[email-masked]> wrote:

>  The issue with this threat is that the attacker *does not* need to be a
> MitM. By MitM, I mean an *active *attacker, i.e. one who can read and
> change packets. This threat applies also to *passive* attackers, i.e. one
> who can just listen. A common scenario for a passive attacker would be open
> wireless LAN.
>
>
>
> If the only authentication on the SYN was a single hash entry, a passive
> attacker could listen to this but stop it from getting to the receiver, or
> delay it by DoS, or just use a faster link that means the attacker can race
> and beat the genuine SYN to the receiver with its own SYN, authenticated
> with the genuine hash entry. It then is able to set up a new subflow, and
> the genuine SYN will be ignored if it arrives later.
>
>
>
> In other words, the use of a single hash chain entry could allow an
> attacker to upgrade himself from a passive attacker to an active attacker by
> opening a subflow. This is the threat we first tried to get around with the
> HMAC in my initial hash chain mail, but now I think can be solved better and
> easier with the second hash entry.
>
>
>
> The use of the second hash entry verifies that the person with which the
> new subflow has been set up is the owner of the hash chain. Since this
> second entry would only be revealed on a successful connection setup, it
> could not be used by a passive attacker since he would have to sniff both
> hash entries, but could only get the second one if the genuine peer had
> undertaken the SYN exchange (by which point the hash chain entry has been
> used and the attacker would not be able to replay it). I hope this makes
> sense now? I would try drawing a diagram, but it’s a bit tricky to show the
> time dimension in it.
>
>
>
> I’m not saying we have to protect against this, but this would seem a
> reasonably plausible approach if we wanted to.
>
>
>
> Regards,
>
> Alan
>
>
>
> *Sent:* 09 December 2010 09:23
>
> *To:* Ford, Alan

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 12 Dec 2010 03:00:47 -0800

Hello Alan,  I might miss some points, but I have several questions on this.

1:  if token B is stolen, can an attacker produce many SYN packets
with random hash to consume Host A's CPU?
2: Can't we do like this?

     SYN + MP_JOIN(Token-B)    -->
           <--- SYN/ACK + MP_JOIN(Token-A)
     MP_VERIFY(H-A[n-1])    -->
           <--  MP_VERIFY(H-B[n-1])

3: If a MP_KEY message is peeked, the mptcp session can be messed up
at any time. But, is this acceptable?

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: Christoph Paasch <[email-masked]>
Date: Sun, 12 Dec 2010 12:50:36 +0100

Hi,

a solution to the attack of point 1 might be to use a subflow identifier SID 
for each hash-chain so that a specific hash-chain can only be used for the 
establishment of one single subflow.

If a peer opens a new subflow with the SID, both parts only accept this SID to 
be used on this subflow (same addresses/ports).

With this, we can protect against your attack described in point 1, because as 
soon as A receives a SYN with a SID1 and a wrong hash-value, A does not accept 
any SYN's with SID1 and will send out an RM_SID to the original peer.

The advantage of using a SID is that the hash-chains are very short. Thus, we 
will reduce the computation time necessary to "prepare" for the establishment 
of one subflow. It is also much easier to stay synchronized, because a peer 
should not accept a certain hash-value twice.
E.g., the establishment of one subflow fails and an attacker reuses the 
sniffed hash-values. With a SID this is only possible if the attacker can 
sniff and spoof.

The SID should also be integrated in your idea of point 2. Because otherwise 
it is still possible for an attacker to hijack a session without spoofing, if 
he manages to sniff the MP_VERIFY and sends his MP_VERIFY faster than the 
original peer.

Regards,
Christoph

---

From: "Ford, Alan" <[email-masked]>
Date: Sun, 12 Dec 2010 23:03:05 -0000

Hi Yoshifumi,

To answer your points...

1. Yes, there is the potential of such an attack. A server will, on every valid token, try hashing the hash a number of times to see if it is valid for the connection. The impact of this attack will be influenced by the size of the hash window (i.e. how many times a host will try before giving up). An alternative could be to signal an index into the hash chain (but this is costly in terms of option space, and a false value could still encourage unnecessary processing).

However, I feel that the proof of knowledge of token does provide a sufficient level of protection against opportunistic DoS attacks such as this. A more general point is that it would be highly desirable to find a way of allowing a server to operate statelessly (and with minimal processor overhead) on the first (MP_CAPABLE) SYN.

2. That would not provide sufficient protection against the attack described. This is because the Token is repeatable information, whereas hash chain entries are not. The two-hash-entry proposal works, I believe, because the subflow is established in two stages, and the second can only follow the first once the first is complete and not repeatable. With only the token as protection for the SYN, an attacker could hypothetically snoop this, use it itself, and race (and win) with the MP_VERIFY.

3. I have used MP_KEY to refer to extending the hash chain. If you mean the same here, then no, there is no threat - this is no different to someone seeing the MP_CAPABLE handshake - the final entry of a hash chain is useless to an attacker since the previous entry (which is used for the next authentication) is still kept secret.

Regards,
Alan

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Yoshifumi Nishida
> Sent: 12 December 2010 11:01
> To: Ford, Alan
> Cc: [email-masked]

---

From: "Ford, Alan" <[email-masked]>
Date: Sun, 12 Dec 2010 23:06:07 -0000

Hi Christoph,

This sounds interesting... Could you explain a bit more about your
proposal? How would the hosts agree on a SID and chain before the
establishment of a subflow? (And, come to think of it, how would they
know that a setup has failed and know to remove the validity of the
information?). What are the message exchanges involved?

Thanks,
Alan

> From: Christoph Paasch [mailto:[email-masked]]
> Sent: 12 December 2010 11:51
> To: [email-masked]
> Cc: Yoshifumi Nishida; Ford, Alan
> If a peer opens a new subflow with the SID, both parts only accept
this SID
> to
> With this, we can protect against your attack described in point 1,
because
> as
> soon as A receives a SYN with a SID1 and a wrong hash-value, A does
not
> accept
> > Hello Alan,  I might miss some points, but I have several questions
on
> > this.

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 12 Dec 2010 18:23:27 -0800

Hi Alan,
Thanks for your response.

> However, I feel that the proof of knowledge of token does provide a sufficient level of protection against opportunistic DoS attacks such as this. A more general point is that it would be highly de…

hmm. if I somehow steal the token, I would send huge number of SYNs
with this token from spoofed address.
If we calculate the hash after syn, I think we can mitigate this to
some extent.

> 2. That would not provide sufficient protection against the attack described. This is because the Token is repeatable information, whereas hash chain entries are not. The two-hash-entry proposal wo…

if we can wait a certain amount of time after MP_JOIN received to see
any more MP_JOIN hasn't come, i think it might be OK.
Also, this seems to be a bit tricky case. To me, the issue in 1 looks
more serious than this.

> 3. I have used MP_KEY to refer to extending the hash chain. If you mean the same here, then no, there is no threat - this is no different to someone seeing the MP_CAPABLE handshake - the final entr…

I see. So, a potential risk is an attacker might be able to find
proper H[n-1] from H[n] if there's plenty of time since he/she can
know which hash function is used from the spec and it's not a keyed
function. But, I think it will be acceptable.

Thanks,
--
Yoshifumi Nishida
[email-masked]

---

From: Christoph Paasch <[email-masked]>
Date: Mon, 13 Dec 2010 21:41:56 +0100

Hi Alan,

I think of a protocol like the following.

The initial subflow has been established with just TokenA and TokenB 
exchanged. As soon as a host wants to open another subflow he needs to 
exchange hash-chains and SID:

MP_CHAIN (SID, Ha[n])
------------------->

MP_CHAIN (SID, Hb[n])
<-------------------

The SID is unique for this mptcp-session.

The host should start this exchange only when he is really intending to open 
up a new subflow very soon. From an implementation point-of-view this is nice, 
because we will reduce the computation-overhead, as we are not generating a 
hash-chain (or a key) at the initial subflow.

If the host B does not want to open a new subflow, he just reponds with an 
RM_SID message. Both hosts need to agree on the fact that they want to open a 
new subflow.

The subflow handshake works like the following:

  SYN + MP_CAPABLE (TokenB, SID, Ha[n-1])
------------------------------------------>
		Upon reception of this message, the server verifies that the TokenB 	
		and SID are valid and then checks the hash-chain. If everything is 
		fine, he associates the source addr/port of the SYN to the SID. He 
		won't accept any SYN's with the same SID anymore coming from another 	
		addr/port.

		If Ha[n-1] is not correct (we are under attack), the server will not 
		accept anymore this SID and sends a RM_SID to the peer.

  SYN/ACK + TokenB + Hb[n-1]
<-----------------------------------------

  ACK + Ha[n-2]
----------------------------------------->
		This third message is necessary, because an attacker might send a
		sniffed SYN faster than the original peer. (already described in a 	
		previous mail here in this list)

The SID/hash-chains can only be used once for one addr/port-pair. As soon as A 
has sended its SYN, and this SYN does not gets an answer (due to 
firewalls,...) he should send a RM_SID as soon as the subflow-establishment 
times out.
Also B should have a timer on the SID, to better protect against a time-
shifted attack, where an attacker has a lot of time to make an exhaustive 
search and find Ha[n-2].

As soon as the subflow-establishment of a flow fails, the SID isn't anymore 
valid and thus the RM_SID needs to be sended.

The advantages of this solution are:
* The initial handshake is very lightweight, which is usefull, as most TCP-
flows are rather short, and it is not always desired to open a new subflow.
* Both hosts need to agree to open a new subflow. Thus, no one can force it's 
peer to calculate a hash-chain.
* The hash-chains are very short. H(H(x)) should be enough. Thus we limit the 
computation overhead.

A problem that still needs to be solved:
MP_CHAIN and RM_SID should be protected against spoofing. We might do some 
kind of "validation" over another subflow to ensure that the host really 
requested the MP_CHAIN or RM_SID. If only one subflow is present and an 
attacker can spoof this address, the session has been hijacked anyway even for 
regular TCP.

Regards,
Christoph

On Monday, December 13, 2010 wrote Ford, Alan:
> > a solution to the attack of point 1 might be to use a subflow
> 
> identifier SID
> 
> > for each hash-chain so that a specific hash-chain can only be used for
> 
> the
> 
> > The advantage of using a SID is that the hash-chains are very short.
> 
> Thus, we
> 
> > will reduce the computation time necessary to "prepare" for the
> 
> establishment
> 
> > of one subflow. It is also much easier to stay synchronized, because a
> 
> peer
> 
> > E.g., the establishment of one subflow fails and an attacker reuses
> 
> the
> 
> > sniffed hash-values. With a SID this is only possible if the attacker
> 
> can
> 
> > sniff and spoof.
> > 
> > The SID should also be integrated in your idea of point 2. Because
> 
> otherwise
> 
> > it is still possible for an attacker to hijack a session without
> 
> spoofing, if
> 
> > he manages to sniff the MP_VERIFY and sends his MP_VERIFY faster than
> 
> the
> 
> > original peer.
> > 
> > 
> > Regards,
> > Christoph
> > 
> > > > Following up my own mail, but having thought about this more I
> 
> don't
> 
> > > > think we need the HMAC and this could in fact be achieved with a
> 
> four
> 
> > > > ------------------------
> ------------------------
> > > > Address A1    Address A2                   Address B1    Address
> 
> B2
> 
> > > > ----------    ----------                   ----------
> 
> ----------
> 
> > > >    |
> > > >    |
> > > >    |    
> > > >    |             |
> > > >    |             |
> > > >    |             |   
> > > >    |             |
> > > >    |             |
> > > >> This exchange proves that Host A was actually the owner of the
> 
> hash
> 
> > > >> chain - an attacker would not be able to produce H-A[n-2] in the
> 
> third
> 
> > > >> part of the handshake. Unfortunately, this really is an
> 
> inconveniently
> 
> > > >> long and expensive handshake (although, the MP_VERIFY can
> 
> probably be
> 
> > > > This is still the case - once the TCP subflow has been
> 
> established, the
> 
> > > > exchange of the previous hash chain entry then acts as proof that
> 
> the
> 
> > > > end host is the same as sent the SYN (so an attacker couldn't just
> 
> steal
> 
> > > > There are still possible attacks on this - e.g. an attacker who
> 
> could
> 
> > > > race both ends could possibly hijack the connection, but that's
> 
> almost a
> 

--
Christoph Paasch

Research Assistant
IP Networking Lab --- http://inl.info.ucl.ac.be
MultiPath TCP --- http://inl.info.ucl.ac.be/mptcp
Université Catholique de Louvain

www.rollerbulls.be
--

---

From: Christoph Paasch <[email-masked]>
Date: Tue, 14 Dec 2010 11:47:49 +0100

Hi all,

some more details on how to protect against a spoofed MP_CHAIN:

On Monday, December 13, 2010 wrote Christoph Paasch:
> attacker can spoof this address, the session has been hijacked anyway even
> for regular TCP.
For clarity, here again the MP_CHAIN-exchange:

MP_CHAIN_1 SID + Ha[n]
--------------------------->

MP_CHAIN_2 SID + Hb[n] + Ha[n]
<---------------------------
I added now the Ha[n] to protect against an attacker that sniffes the 
MP_CHAIN_1 and then spoofes an MP_CHAIN_1 with the same SID.

We enfore that the receiver of an MP_CHAIN_1-message should reply with its 
MP_CHAIN_2 on *all* subflows.
With this, we protect against spoofing, because if the original peer receives 
an MP_CHAIN_2 with an SID/Ha[n] that he did not request in an MP_CHAIN_1-
message, we send out an RM_SID.

As the MP_CHAIN_2 is broadcasted on all subflows, it is important to see, what 
happens when there is only one subflow. Then, the attacker might spoof an 
MP_CHAIN_1, however B will still reply with an MP_CHAIN_2 and A will see that 
it did not request this SID/Ha[n] and can thus send out again an RM_SID.

The RM_SID can also be spoofed. However, it is not absolutly necessary to 
protect against this, because our goal is to not be worse than TCP. Spoofed 
RM_SID just prevent new subflows to be established, and thus mptcp behaves 
like regular TCP.

Another advantage of this solution is, that when we receive an MP_CHAIN_2 with 
the wrong SID/Ha[n], we know that we are under attack and it might be wise to 
close this mptcp-session.

Regards,
Christoph

--
Christoph Paasch

Research Assistant

www.rollerbulls.be
--

---

From: "Ford, Alan" <[email-masked]>
Date: Tue, 14 Dec 2010 11:28:12 -0000

Hi Christoph,

Since reading your earlier mail, I too have been thinking about this anti-spoofing issue, and the solution as a whole.

In your proposal, it is now the sending data back on all subflows that is the key security feature, to allow the alleged initiator to say "hey that wasn't me!". Do we need hash chains at all in this case? Or would it be perfectly feasible to implement the same level of security with a random token sent along with any MP_JOIN that is echoed (and ACKed again) on every subflow to allow both endpoints to agree. (Not sure if this is as secure, though - there is potential for stealing tokens I guess - so maybe a second token would have to be echoed on the new subflow on setup).

(Also you typically don't want to close all subflows if the connection appears under attack - that would make an easy DoS attack!)

The trouble with this - and indeed the SID-based proposal in general - is that it does not permit the use of MPTCP to support break-before-make changes of address. It is felt desirable that MPTCP will support session continuity over a short break in connectivity, as TCP does today - and with MPTCP we have the potential to support a change in address over this break too.

In order to support this, we need a hash chain already in place (we cannot predict when it will be needed). But to have a long-life hash chain in place, we need to ensure it cannot be injected by an attacker. Which means it needs to be done at the start of the connection. And so we come round in a circle!

However, it has been pointed out that in many cases it is only the original connection initiator that actually needs to worry about this. (Although it is possible for either endpoint to trigger a subflow setup, most MPTCP use cases have the initiator making new subflow connections even if that means responding to an ADD_ADDR from the peer.) I wonder if there is some way of building a hybrid solution where the client has the expense of calculating a long hash chain at the start, but the server can make do with a short chain, on-demand, as you suggest. It would not cover all bases, but would make this a lot less expensive from the server side.

Regards,
Alan

> Sent: 14 December 2010 10:48
> Cc: Ford, Alan

---

From: Mark Handley <[email-masked]>
Date: Tue, 14 Dec 2010 22:53:54 +0000

> way handshake just using the hash chain...

Apologies for having to drop out of the call today a little early.

Just for completeness, I'll re-state why MP_VERIFY doesn't really work.

Recall that the problem was that an attacker might passively eavesdrop
the SYN+MP_JOIN and regenerate a SYN+MP_JOIN from an address he owns
using the same value of H-A[n-1].  If he can beat the original MP_JOIN
his hijack is successful.  This might be achieved pretty
deterministically if he's got (say) WiFi and 3G, and manages to build
a large queue on the WiFi uplink (which is often over DSL), observes
MP_JOIN over WiFi, and then generates his own MP_JOIN over 3G.

Now, to defeat the MP_VERIFY, all the attacker needs to do is spoof
the SYN/ACK from the server to the legit client using the value of
H-B[n-1] from the SYN/ACK he received when he won the race.  The legit
client will then generate an MP_VERIFY containing H-A[n-1], which the
attacker can observe, generate his own MP_VERIFY,  and win the race
again.  In fact he may not even need to race the second time if the
server ignores the MP_VERIFY from the legit client.

So my conclusion is that if the attacker has access to any address on
the Internet that can spoof a packet, MP_VERIFY adds no additional
security.

 - Mark