Subject: [Cfrg] tcp-md5 "strength"

From: Stephen Farrell <[email-masked]>
Date: Thu, 29 Sep 2016 13:14:57 +0100

Hiya,

I was just asked for an estimate for how much effort
it might be to break tcp-md5 [1] and whether (and for
whom:-) that might be practical, for any interesting
kind of break.

If anyone has answers or estimates handy, that'd be
appreciated.

Cheers,
S.

PS: Yes, I know tcp-md5 is pretty to very crappy,
sadly, it's still used and hard to displace :-(

[1] https://tools.ietf.org/html/rfc2385

---

From: Greg Rose <[email-masked]>
Date: Thu, 29 Sep 2016 07:05:02 -0700

> On Sep 29, 2016, at 5:14 , Stephen Farrell <[email-masked]> wrote:

Appending the shared key to the end of the data to be hashed, as a message digest, is not considered to be safe with any hash function. That's why HMAC was developed. In the face of MD5 being not target collision resistant, I'd say this is a large security vulnerability. Practically speaking, the effort might depend on the length of the messages being transmitted, and their internal format, and I don't know enough about BGP to say for sure. If the messages are multiple blocks, with fairly flexible content in them, there's software out there that can produce messages with the same validation data in seconds.

I do understand that designing a replacement, particularly one without downgrade attacks applicable, is hard, and deploying it will be even harder, but wow, this is BGP! It's a bit important to the functioning of the Interwebs.

Greg.

Phone:  +1 619 890 8236 
GPG/PGP:  1081A37C  232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 29 Sep 2016 20:23:18 +0100

Hiya,

On 29/09/16 15:05, Greg Rose wrote:
> this is BGP! It's a bit important to the functioning of the Interwebs.

Yeah. Two things:-

1. TCP-AO [1] was defined to improve this situation but has seen
no deployment. So merely defining the obvious replacement in 2010
wasn't sufficient to move things along here.

2. It's not just BGP, other (e.g. MPLS-related) protocols re-use
what's available on the relevant kit and are still doing so [2]
(note [2] is not a new protocol but is a protocol being advanced
on the IETF standards track).

Hence my asking - I think there may be a chance to try (yet again)
to convince folks to implement and deploy something better, but as
part of that it'd be great to have an up-to-date and precise view
on just how bad the currently deployed thing (TCP-MD5) really is.
(And hey, if someone spends effort on this, they might get a nice
publication about BGP;-)

Ta,
S.

[1] https://tools.ietf.org/html/rfc5925
[2] https://datatracker.ietf.org/doc/draft-ietf-pals-rfc4447bis/

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Thu, 29 Sep 2016 20:18:34 +0000

Hi Stephen,

>If anyone has answers or estimates handy, that'd be

There are several different types of attacks that are possible on TCP-MD5:

1) attacks on the "secret-suffix MAC” used in that construction: (see Preneel and Van Oorschot, "MD-x MAC and building fast MACs from hash functions", Advances in Cryptology Crypto '95 Proceedings).  The attacker needs to find two messages M, M’ that hash to the same value, then they can substitute one message for the other, when it appears on the wire.  Applying this attack to TCP-MD5 is not exactly straightforward, because the attacker doesn’t have a chosen-message oracle, but it probably feasible with O(2^64) operations.   A good variant would be for the attacker to create a large set of (message, hash) pairs, then observe the victim traffic until a collision occurs between that set and the hash of the messages on the wire.

2) replay attacks, or session-splicing attacks.   These are especially successful if the attacker goes active and forces a reset of the TCP session, in which case about 256 resets are typically needed to create the window overlap needed to make an attack possible.

3) offline dictionary attacks, which will work whenever the key is predictable.

#1 would be the most interesting to study, #2 is probably the easiest to pull off, and #3 is the stealthiest.  

Don’t use TCP-MD5!

best

David