Subject: Re: [TLS] While we're patching

From: Peter Gutmann <[email-masked]>
Date: Fri, 6 Mar 2015 04:20:46 +0000

Watson Ladd <[email-masked]> writes:

>Consider https://www.smacktls.com/. It's clear that the implementors of TLS 
>libraries attempt to minimize codesize by sharing code between various 
>exchanges but in doing so often mis-implement the state machine. As we 
>decide to further complicate, not simplify, the state machine in TLS 1.3, 
>we should strongly consider making the description of the state machine 
>more formal, and simplifying the flows: mo' code, mo' problems.

The problem isn't that the state machine is too complex, it's that there's
a state machine at all.  The SSL/TLS message flow is so clearly a ladder
diagram that I've never understood how anyone could implement it as a state
machine.  I never even tried to make my implementation a state machine,
which would be why SKIP-TLS just bounced off it.  Look at any security
text that talks about TLS and it's always represented as a ladder diagram.
Heck, even the TLS RFC itself uses ladder diagrams to represent the
mesage flow:

    Client                                               Server

      ClientHello                  -------->
                                                      ServerHello
                                                     Certificate*
                                               ServerKeyExchange*
                                              CertificateRequest*
                                   <--------      ServerHelloDone
      Certificate*
      ClientKeyExchange
      CertificateVerify*
      [ChangeCipherSpec]
      Finished                     -------->
                                               [ChangeCipherSpec]
                                   <--------             Finished
      Application Data             <------->     Application Data

So the way to fix things isn't to do anything to the state machine, it's
to document the protocol for what it actually is, a ladder diagram.

Peter.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 5 Mar 2015 20:36:38 -0800

> to document the protocol for what it actually is, a ladder diagram.

Just to clarify:

Did you test SKIP-TLS against your implementation? Because it's not
clear from the paper that IRINA did.

Regardless of whether we call this a ladder diagram or state machine,
the issue is that optional messages are actually required depending on
what ciphersuite was selected. I don't see how this requirement goes
away if a ladder diagram is used. (What is a ladder diagram anway? How
does one implement it without writing a state machine?)  In
particular, accepting a Server Key Exchange when the negotiated cipher
doesn't require one is exactly the FREAK attack: unless you condition
accepting the Server Key Exchange on the selected cipher suite somehow
you have the problem.

Sincerely,
Watson Ladd

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

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Adam Langley <[email-masked]>
Date: Thu, 5 Mar 2015 21:12:37 -0800

On Thu, Mar 5, 2015 at 8:36 PM, Watson Ladd <[email-masked]> wrote:
> does one implement it without writing a state machine?)

I'm also not quite sure that I understand what Peter meant, but it
seems that his thinking might be similar to mine:

TLS's messages should have encompassed entire flows, except where
switching cipherspecs requires splitting them. I.e. the ServerHello,
Certificate, SKX etc should all have been one message.

It's possible to implement it like this, but the presentation in the
RFC has very often lead to software designs that involve a state
machine. After processing each handshake message, all the state is
serialised back into structures, the next message is read and the
state machine is run again, at which point it needs to pull the state
back out of structures.

The constant marshaling of state is hard and makes the code hard to
understand. This has lead to numerous bugs in stacks that I'm aware
off (most of which don't have names).

Rather, if the whole flow were available at once then the code could
be very much simpler. (And it is available if one structures the code
like that but, again, the RFC style leads implementators in the wrong
direction.)

(This is why QUIC's handshake has one message per flow, except when
starting encryption requires two.)

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Fri, 6 Mar 2015 07:00:27 +0100

> clear from the paper that IRINA did.

Hi,

We were surprised by the number of TLS implementations out there, and didn’t have the
resources to test them all. We mainly looked at a few open source implementations, but
the pattern of attacks we found should be more general.

Our plan is to release our FlexTLS recipes for our client/server tests (SKIP+FREAK)
so everyone can test their implementations. For clients, we will probably provide
a test server to try out.

When looking at a number of implementations, we roughly saw the following patterns.
I am going to use the word state machine in the following, but you can read it as “protocol engine”
or “top-level client/server function”:

- Branching on state vs. branching on incoming message
  Some libraries look at the current state first and then require the incoming message to
  have a certain shape. These generally do better (have fewer bugs) than implementations
  that look at the incoming message and then try to fit them with the current protocol state. 

- Same or different state machines for client and server
  Libraries that use the same state machine for client and server have to jump through
  lots of hoops to discover what state they are in, and this leads to bugs and crashes.

- Interleaving CCS vs Handshake vs Application Data
  Libraries that treat CCS just as a handshake message tend not to forget it.
  Those that treat CCS specially forget to check it was received, or when it was received.
  Similar problems lurk in the interleaving of Application Data and handshake messages.

The informal observations above (of course, it is possible to code TLS correctly in all these styles!)
go against software engineering principles a bit. For example, they suggest that we shouldn’t share 
code for processing the “Certificate” message between client and server.
They also suggest that we shouldn’t cleanly separate the Record layer’s ContentType-based 
dispatch from the Handshake state-machine.

Perhaps most significantly, they suggest that in TLS, both peers should at all times know
exactly what type of message to expect next. Perhaps this is what is meant by a ladder diagram?
When a server receives a ClientHello, it should know the full shape of the upcoming handshake,
and the same goes for a client after the ServerHello. 

Best,
Karthik

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 6 Mar 2015 16:09:25 +0200

> Certificate, SKX etc should all have been one message.

Looking at TLS 1.3 flows, the unencrypted flights should all fit into
one record each (as long as neither endpoint is doing anything
ridiculous). In fact, in most cases those should fit even into
one IP packet each (doesn't really matter for TLS, since TCP hides
the IP packet boundaries).

The encrypted flights might not fit into TLS record, because both
contain certificate chains, which can be quite large.

Also, if one wants to ensure proper sequencing on state level (and
I consider it dangerous not to), the handshake can't actually restart
(the initial and post-restart states are distinct).

> like that but, again, the RFC style leads implementators in the wrong

Also, it occurs to me that there is duplication between ciphersuite
and message types.

Except for some optional messages (like EncryptedExtensions and
CertificateRequest), the sequence of messages is determined by
ciphersuite. Thus most message type info is duplicated information,
which is infamous source of (security) bugs.

Also, there is possiblity of omitted messages. E.g. omit Certificate
or include Certificate but omit Certificate Verify. The problem is
that neither is really optional, those two are dependent on the
ciphersuite (except for resume).

I recently tried to construct state machine model for TLS 1.3.
I discovered that CertificateRequest adds many new states (this
is because of the way it changes messages and rekeying behaviour).

On high level, the TLS 1.3 1RTT/2RTT flow looks pretty decent
to me (although there are problems).

Since 0RTT flow seems pretty much handwaving as of currently, I
can't say anything about it, except note that getting that kind
of thing right might be pretty difficult.

The simplicity is not measured with the simplest implmentation that
works, it is measured with the simplest implementation that is
_secure_. And having large gap between the two is extremely bad,
since it guarantees security holes in practice.

Bugs that result in things failing visibly in operation (incorrect
key derivations, deadlocks, etc...) tend to be fixed MUCH faster
than bugs that result in things failing insecure in invisible
ways.

Also, it is not just TLS protocol and TLS implementation security
bugs... There are also bugs from misuse of TLS (which can be
pretty subtle).

-Ilari

---

From: Andrei Popov <[email-masked]>
Date: Fri, 6 Mar 2015 17:24:53 +0000

Exactly how the code is structured in a particular implementation may be a factor, but I think bigger issues that lead to bugs like this are:

1.       Protocol complexity: multiple message flows are possible, depending on negotiated parameters. Unfortunately, this will get even worse with TLS 1.3 support added to existing implementations.

2.       The fact that implementations tend to disable weak crypto by default, but keep the code around forever. Had we removed EXPORT cipher code years ago, we wouldn't have the issue now.

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Karthikeyan Bhargavan
Sent: Thursday, March 5, 2015 10:00 PM
To: Watson Ladd
Cc: <[email-masked]>
Subject: Re: [TLS] While we're patching

Hi,

We were surprised by the number of TLS implementations out there, and didn't have the
resources to test them all. We mainly looked at a few open source implementations, but
the pattern of attacks we found should be more general.

When looking at a number of implementations, we roughly saw the following patterns.
I am going to use the word state machine in the following, but you can read it as "protocol engine"
or "top-level client/server function":

The informal observations above (of course, it is possible to code TLS correctly in all these styles!)
go against software engineering principles a bit. For example, they suggest that we shouldn't share
code for processing the "Certificate" message between client and server.
They also suggest that we shouldn't cleanly separate the Record layer's ContentType-based
dispatch from the Handshake state-machine.

Best,
Karthik

Sincerely,
Watson Ladd

Peter.
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls

_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls

---

From: Michael StJohns <[email-masked]>
Date: Fri, 06 Mar 2015 12:38:34 -0500

> accepting the Server Key Exchange on the selected cipher suite somehow

I think there are actually 6 state machines running for TLS as far as I 
can tell: client and server version each of parameter negotiation, key 
negotiation and authentication.

And there are many variants on these based on how many older versions of 
TLS you support.

Peter's comment that this is a ladder diagram is really a distinction 
without a difference.  (And I think Adam's note about serialization is 
really a good explanation of the ladder diagram). The ladder diagram 
*might* correctly describe the time order of the messages (e.g. with no 
exceptions and a well behaved server); the state diagram - if done 
properly - should give you insight into what those messages actually 
mean and why they're important at this time and for this recipient.    
Mostly its possible to convert one of these to another - albeit with 
occasional information loss.

In my own protocol designs I used to use the UML based state diagram 
almost exclusively, but it fails miserably when trying to diagram 
exceptions.  I've started to use UML to describe the normal path as an 
overview, but I've transition to using SDL (Z.100 series - sigh) for 
anything more complex than a state diagram for a traffic light. UML is 
transition based - SDL is state based.  The SDL state machine can be 
decomposed down to a single diagram per state each of which describes 
possible transitions from that state and allows the use of If/then/else 
and case logic to mix in other variables besides simple message or timer 
based transitions.   The other nice thing is there are equivalent 
graphic and text representations.

In any event, we've got the ladder diagrams and I don't think they're 
going away anytime soon.  Until the RFCs can incorporate better diagrams 
than ASCII art, I think moving to a state diagram is off the table.

Mike

---

From: Ronald del Rosario <[email-masked]>
Date: Fri, 6 Mar 2015 17:57:54 +0000

===

2.       The fact that implementations tend to disable weak crypto by default, but keep the code around forever. Had we removed EXPORT cipher code years ago, we wouldn’t have the issue now. +1

Cheers,

Andrei

===

My thoughts exactly.

Ron

From: Andrei Popov <[email-masked]<mailto:[email-masked]>>
Date: Friday, March 6, 2015 at 9:24 AM
To: Karthikeyan Bhargavan <[email-masked]<mailto:[email-masked]>>, Watson Ladd <[email-masked]<mailto:[email-masked]>>
Cc: "<[email-masked]<mailto:[email-masked]>>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [TLS] While we're patching

2.       The fact that implementations tend to disable weak crypto by default, but keep the code around forever. Had we removed EXPORT cipher code years ago, we wouldn’t have the issue now.

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Karthikeyan Bhargavan
Sent: Thursday, March 5, 2015 10:00 PM
To: Watson Ladd
Cc: <[email-masked]<mailto:[email-masked]>>
Subject: Re: [TLS] While we're patching

Hi,

Best,
Karthik

Sincerely,
Watson Ladd

Peter.

________________________________

CONFIDENTIALITY NOTICE: This e-mail and any files attached may contain confidential information of Five9 and/or its affiliated entities. Access by the intended recipient only is authorized. Any liability arising from any party acting, or refraining from acting, on any information contained in this e-mail is hereby excluded. If you are not the intended recipient, please notify the sender immediately, destroy the original transmission and its attachments and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Copyright in this e-mail and any attachments belongs to Five9 and/or its affiliated entities.

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 6 Mar 2015 10:12:12 -0800

On Mar 6, 2015, at 9:38 AM, Michael StJohns <[email-masked]> wrote:
> Until the RFCs can incorporate better diagrams than ASCII art, I think moving to a state diagram is off the table.

If a WG wants to have non-ASCII art for things like better diagrams, they can do so *today* with external references. This has already been done by at least one other WG. I can describe this more fully if needed, but if the WG thinks that one of our documents would be significantly better with real art instead of ASCII art, just do it.

--Paul Hoffman

---

From: Joseph Salowey <[email-masked]>
Date: Fri, 6 Mar 2015 10:55:00 -0800

On Fri, Mar 6, 2015 at 10:12 AM, Paul Hoffman <[email-masked]> wrote:

> > Until the RFCs can incorporate better diagrams than ASCII art, I think
> moving to a state diagram is off the table.
>
> If a WG wants to have non-ASCII art for things like better diagrams, they
> can do so *today* with external references. This has already been done by
> at least one other WG. I can describe this more fully if needed, but if the
> WG thinks that one of our documents would be significantly better with real
> art instead of ASCII art, just do it.
>
>
[Joe] +1

There are several examples of this including an EAP state mahttp://
tools.ietf.org/pdf/rfc4137.pdf.  ASCII format should not stand in the way
of providing better documentation for analysis.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 6 Mar 2015 11:11:45 -0800

A state machine can always be specified by a set of states and transition
functions. That can be done in text. Notice how TCP does this, with an
ASCII art result worthy of the Pope's ceiling.

Part of the issue is that the TLS spec splits all sorts of details off into
extensions in very undisciplined ways. Many of the bugs result from hooking
into the state machine in ways that original authors didn't expect, and not
being explicit about forbidden transitions. The gap between spec and code
is too large.

Sincerely,
Watson Ladd