Subject: [TLS] A closer look at ROBOT, BB Attacks, timing attacks in general, and what we can do in TLS

From: Colm MacCárthaigh <[email-masked]>
Date: Thu, 14 Dec 2017 14:20:54 -0800

TLS folks,

A few weeks ago the s2n team got a mail from US CERT asking us to take a
look for any Bleichenbacher attack issues and get to back to them. We
didn't have any issues (thankfully!), but it was a good opportunity for us
to review how we defend against BB and other related attacks.  The notice
was of course based on the excellent work of Hanno Böck, Juraj Soorovsky,
and Craig Young.

Based on the notice, we also went looking in some other code-bases and
implementations we have access to, and did find issues, both classic BB98
style attacks, and small timing side channels. We've worked with vendors
and code owners in each case and fixes are in place, new releases made, and
so on.

Based on our experiences with all of this over the last few weeks, I'd like
to summarize and throw out a few suggestions for making TLS stacks more
defensive and robust against problems of this class. One or two may be even
worth considering as small additions to the forthcoming TLS RFC, and I'd
love to get feedback on that.

*First: the basic specific defense against BB98*
In s2n we went with the boring basic per-the-TLS defense against BB98. We
pre-generate a random PMS:

https://github.com/awslabs/s2n/blob/master/tls/s2n_client_key_exchange.c#L64

then we over-write this PMS only if RSA succeeds:

https://github.com/awslabs/s2n/blob/55a641dc29d17780620c16713854f1c9fd31f7ce/crypto/s2n_rsa.c#L165

since it's important not to leak timing, we use a special
"constant_time_copy_or_dont" routine to do the over-write:

https://github.com/awslabs/s2n/blob/master/utils/s2n_safety.c#L70

we then allow the handshake to proceed, and fail it later:

https://github.com/awslabs/s2n/blob/088240d081953131deefb27a70fa6f728156f0cf/tls/s2n_client_finished.c#L35

So far everything is standard, though we did notice in reviewing some other
implementations that things can be unnecessarily complicated around
handling the first step. I'm including the code links here just as an
example that literally following the RFC guidance is fairly doable, but it
helps a lot to have a constant-time copy-or-not kind of routine to make it
much easier.

*Second: hide all alerts in suspicious error cases*
Next, when the handshake does fail, we do two non-standard things. The
first is that we don't return an alert message, we just close the
connection. This is intentional, and even though it violates the written
standards, we believe it's better to optimize for frustrating attackers and
not leaking information Vs making occasional debugging by TLS experts
easier. I'd be interested in the thoughts of others here.  We did find
other implementations that just close() a connection, and we've never
noticed inter-operability problems. Should we tolerate this in the RFC?

*Third: mask timing side-channels with a massive delay*
The second non-standard thing we do is that in all error cases, s2n behaves
as if something suspicious is going on and in case timing is involved, we
add a random delay. It's well known that random delays are only partially
effective against timing attacks, but we add a very very big one. We wait a
random amount of time between a minimum of 10 seconds, and a maximum of 30
seconds. With the delay being granular to nanoseconds. This puts a delay of
20 seconds on average on every potential attacker measurement (though
obviously they can parallelize) and adds something around 2^60 bits of
entropy to a measurement. The effectiveness of this technique depends on
the size and distribution of the timing channel being leaked, as well the
distribution of measurement latency generally, but suppose the timing leak
is 10 microseconds, then the delay likely increases attacker difficulty by
a factor of probably hundreds of billions.  I'd be interested in thoughts
on this too, as a general recommendation as "something TLS stacks
can/should do is that when there's an error, mask it with a big random
delay".

The main "downside" of this delay is that it can tie up resources - but
we're not as concerned with that. Firstly, an attacker can always cause a
connection to stall for 30 seconds, and even ordinary network conditions
like packet loss can trigger that. That's why we chose 30 seconds as our
upper bound. Second, connections are cheap, especially in
asynchronous/epoll driven models, or any model that isn't one-connection
per process. We prefer to have the defense in depth. It's worth noting that
this protection also helps with other timing attacks, such as Lucky13 (read
https://aws.amazon.com/blogs/security/s2n-and-lucky-13/ for my write up on
how the earlier version of this, with microsecond granularity, wasn't
enough to defeat Lucky13, but still made it millions of times harder for an
attacker) or even AES timing issues.

The remainder of this mail doesn't concern changes that could made in the
TLS draft, but rather just other information that may be useful for
implementors. Sorry if I'm abusing the purpose of the list a little, but
hopefully the last item in particular will make it worth the read.

*Fourth: regression tests*
We noticed that many of implementations we encountered had no regression
tests. In s2n we do have plenty of tests, but actually did not have a
specific regression test against BB. We didn't want to add one until the
Robot attack was public, but are now adding one.

*Fifth: formal constant-time verification*
Regression tests on their own do not defend against timing side channel
regressions, and we noticed in the commit history of some of the code we
reviewed that ones had snuck in over time. For example some non-s2n code we
encountered added some debug logging in the case where the padding is
mismatched, which created a very small timing difference with the cost it
takes to print the logging message. Here I'd like to share two pieces of
work we've been doing over the last year. The first is formal verification
of our code's constant time properties with ctverif and SMACK. Our
integration is at:

https://github.com/awslabs/s2n/tree/master/tests/ctverif

We've been able to instrument our most timing sensitive routines and verify
that they really do use the same number of instructions, regardless of
inputs. The annotations are very readable and easy to deal with and don't
mess up the code base, in fact the code I linked to earlier:

https://github.com/awslabs/s2n/blob/master/utils/s2n_safety.c#L70

is annotated, that's what the S2N_PUBLIC_INPUT macro is for. These
constant-time tests run on every commit and build of s2n, and defend
against regressions in the code and even compiler. For those of you who may
be at RWC2018/HACS, I'd love to show you more if you're interested in
integrating or doing anything similar!

*Sixth: fuzzy constant-time verification for code-balancing*
In building the s2n formal constant-time verification, we noticed that
there are more complicated aspects of TLS processing; such as CBC
verification and BB98 mitigation that need to be in constant-time, but
where the code also spans many functions and even messages. The solutions
here typically are not small routines that are rigorously constant time,
but instead rely on a degree of code-balancing: taking code paths that are
"similar enough" in timing so as not to be measurable.

At first, the reaction against code-balancing can often be finger-wagging,
but our our survey of TLS libraries is that most are using code-balancing
in some capacity. In fact, we can take the OpenSSL LuckyMinus20
vulnerability and regression as evidence that trying to be rigorously
constant time on large complicated algorithms that were not designed to be
constant time can seriously backfire by introducing logic errors in the
very hard-to-follow constant-time adaptations.

Because code-balancing is useful in these cases, and certainly used in many
real world implementations, we wanted to make its effect more measurable,
and more than simply good intentions. Our automated reasoning group (and in
particular Daniel Schwartz-Narbonne and Konstantinos Athanasiou) has built
and integrated a new tool called sidewinder. The PR integrating it into s2n
is here:

https://github.com/awslabs/s2n/pull/664

The great thing about Sidewinder is that it can cope with an analysis over
larger and more inter-related code units, and it can produce bounds for how
much may the execution paths differ by, for both instructions and memory
accesses.I believe it would have prevented some of the regressions we found
in our BB attack focused review of third party code bases over the last few
weeks. It's another tool I'd be excited and happy to share with folks at
RWC/HACS.

-- 
Colm

---

From: Watson Ladd <[email-masked]>
Date: Thu, 14 Dec 2017 14:58:59 -0800

Let's not forget defense 0: migrating away from broken algorithms
(which means turning them off). The fact that we didn't switch MTI
away from RSA encryption in TLS 1.1 after these attacks were
disclosed, or even in TLS 1.2, means that we've got a very long time
before some sites can turn off these algorithms. Given that some
places can't turn off SSL v3, it's not clear we can ever turn off a
widely implemented protocol.

Sincerely,
Watson Ladd

---

From: Colm MacCárthaigh <[email-masked]>
Date: Thu, 14 Dec 2017 16:45:57 -0800

Bringing this back to TLS-WG territory. Deprecating algorithms is hard work
and can take a long time. Having been through MD5, RC4, 3DES, SHA1
deprecations and CBC de-prioritisations, it was a lot of work and network
effects work against rapid changes.

What else could we be doing here? One option might be to say that
implementations should aways maintain at least two active algorithms for
everything, both used with some frequency, and hence both likely to be
optimized, the goal being to be able to turn off one at a moments notice
with no availability or performance impact.

But what would that look like? What would we do now, in advance, to make it
easy to turn off AES? For example.

-- 
Colm

---

From: Hanno Böck <[email-masked]>
Date: Fri, 15 Dec 2017 02:01:16 +0100

On Thu, 14 Dec 2017 16:45:57 -0800
Colm MacCárthaigh <[email-masked]> wrote:

> But what would that look like? What would we do now, in advance, to
> make it easy to turn off AES? For example.

I think this is the wrong way to look at it.

From what I'm aware nobody is really concerned about the security of
AES. I don't think that there's any need to prepare for turning off AES.

The problem with PKCS #1 v1.5 is that it survived so long *after* its
was known that it was bad. I really recommend everyone who wants to
know how protocols go bad to read up on the Bleichenbacher
countermeasures in TLS 1.0, 1.1 and 1.2 - and particularly the last
one. The chapter in 1.2 is a nightmare and I seriously fail to
understand how anyone could have seen that and think it's a good idea
to do that in order to stay compatible with a standard that was already
deprecated at that point.

We know that when this group decided to deprecate both PKCS #1 1.5 and
RSA encryption that there were people trying to lobby against that. I'm
glad that this wasn't successful.

I think the takeaway is just as simple as this: If you know an algorithm
is bad get rid of it and don't try to "rescue" it over into the next
protocol.

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42

---

From: Colm MacCárthaigh <[email-masked]>
Date: Thu, 14 Dec 2017 17:05:37 -0800

> AES. I don't think that there's any need to prepare for turning off AES.

Well, DJB is a notable concerned critic of AES and its safety in some
respects ... but I was using AES as kind of a worst-case scenario since so
many things do depend on it and it's especially hard to leave. I'm not
aware of some ground-breaking cryptanalysis :) But I do think the question
is worth having an answer for. I think we *do* need to prepare for turning
off AES, there's always a chance we might have to.

-- 
Colm

---

From: Yoav Nir <[email-masked]>
Date: Fri, 15 Dec 2017 06:50:50 +0200

> On 15 Dec 2017, at 3:05, Colm MacCárthaigh <[email-masked]> wrote:
> 
> 
> 
> On Thu, Dec 14, 2017 at 5:01 PM, Hanno Böck <[email-masked] <mailto:[email-masked]>> wrote:
> Colm MacCárthaigh <[email-masked] <mailto:[email-masked]>> wrote:
> 
> Well, DJB is a notable concerned critic of AES and its safety in some respects ... but I was using AES as kind of a worst-case scenario since so many things do depend on it and it's especially hard to leave. I'm not aware of some ground-breaking cryptanalysis :) But I do think the question is worth having an answer for. I think we *do* need to prepare for turning off AES, there's always a chance we might have to.

I think that was the point of standardizing ChaCha20-Poly1305.  In fact, that’s what is says in the second paragraph of the introduction in RFC 7539:

https://tools.ietf.org/html/rfc7539#section-1 <https://tools.ietf.org/html/rfc7539#section-1>

Yoav

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 15 Dec 2017 15:19:56 +0100

> glad that this wasn't successful.

RSA PKCS #1 1.5 decryption and signatures are far from deprecated. In fact
the security of TLS 1.3 is heavily tied to these primitives if servers
support TLS 1.2 and RSA (see [0]) alongside TLS 1.3. It would be very nice
if we can only deprecate RSA PKCS#1 1.5 at some point.

regards,
Nikos

[0]. https://github.com/tlswg/tls13-spec/pull/1123

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 16:30:57 +0200

On Thu, Dec 14, 2017 at 05:05:37PM -0800, Colm MacCárthaigh wrote:

> But I do think the question

Even nastier dependency: SHA-2. If that breaks, currently both TLS 1.2
and 1.3 break. There are no alternatives defined.

Yes, sure SHA-2 has taken a lot of cryptoanalysis without serious
trouble (I think one reason for starting SHA-3 process was preceived
weakness in SHA-2, that later turned out not to be the case). 

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 16:46:19 +0200

> widely implemented protocol.

I think the main problem in way of just deleting static RSA code is
those "visibility" folks. Because vast majority of clients that are
not utter garbage for other reasons support PFS with decent key sizes.

(And then there are folks that interpret MTI in insane ways).

-Ilari

---

From: Andrei Popov <[email-masked]>
Date: Fri, 15 Dec 2017 14:57:33 +0000

Here's an attempt to define a SHA-2 alternative: https://tools.ietf.org/html/draft-wconner-blake2sigs-01

Cheers,

Andrei

-----Original Message-----
From: TLS [mailto:[email-masked]] On Behalf Of Ilari Liusvaara
Sent: Friday, December 15, 2017 6:31 AM
To: Colm MacCárthaigh <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] A closer look at ROBOT, BB Attacks, timing attacks in general, and what we can do in TLS

On Thu, Dec 14, 2017 at 05:05:37PM -0800, Colm MacCárthaigh wrote:

> is worth having an answer for. I think we *do* need to prepare for 
> turning off AES, there's always a chance we might have to.

Even nastier dependency: SHA-2. If that breaks, currently both TLS 1.2 and 1.3 break. There are no alternatives defined.

Yes, sure SHA-2 has taken a lot of cryptoanalysis without serious trouble (I think one reason for starting SHA-3 process was preceived weakness in SHA-2, that later turned out not to be the case). 

-Ilari

_______________________________________________
TLS mailing list
[email-masked]
https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=04%7C01%7CAndrei.Popov%40microsoft.com%7C22779f9a38834781928208d543c87f97%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636489450805010503%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwifQ%3D%3D%7C-1&sdata=yVHsF021AGtXGR0DDpm2mV07gsCThPjk%2BGsDm8R4UyE%3D&reserved=0

---

From: Kathleen Moriarty <[email-masked]>
Date: Fri, 15 Dec 2017 11:47:54 -0500

> if we can only deprecate RSA PKCS#1 1.5 at some point.

Is there a reason why a migration to PCKS #1 v2.2 doesn't help for TLS
1.2 and prior? I haven't noticed any discussion on that previously. Is
it just the code base and not those using it being unwilling to
upgrade supporting libraries?

>From RFC8017:

   To avoid implementation weaknesses related to the way errors are
   handled within the decoding operation (see [BLEICHENBACHER] and
   [MANGER]), the encoding and decoding operations for RSAES-OAEP and
   RSAES-PKCS1-v1_5 are embedded in the specifications of the respective
   encryption schemes rather than defined in separate specifications.
   Both encryption schemes are compatible with the corresponding schemes
   in PKCS #1 v2.1.

And, yes, I know deprecation is very hard, but if there's been no
effort, it should be considered as TLS 1.2 isn't going away anytime
soon.

Thanks,
Kathleen
> https://www.ietf.org/mailman/listinfo/tls
>

-- 

Best regards,
Kathleen

---

From: Hanno Böck <[email-masked]>
Date: Fri, 15 Dec 2017 17:57:48 +0100

On Fri, 15 Dec 2017 11:47:54 -0500

> upgrade supporting libraries?

It depends... particularly if we talk about encryption or signatures.

With Bleichenbacher attacks there are plenty of cross-protocol attack
possibilities, this was one of the papers at the TRON workshop:
https://www.nds.rub.de/media/nds/veroeffentlichungen/2015/08/21/Tls13QuicAttacks.pdf

While I believe we certainly can't get rid of PKCS #1 1.5 signatures
any time soon, I think we can get rid of PKCS #1 1.5 encryption (at
least on the server side for HTTPS). The number of legit connections is
really low.

If you run servers please check if you can do that. (I'm also
considering writing an RSA-kex-diediedie RFC when I find time for it.)

-- 
Hanno Böck
https://hboeck.de/

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 19:02:19 +0200

> effort, it should be considered as TLS 1.2 isn't going away anytime

The problem is that handling a decryption fault in TLS 1.2 and prior is
hard. The TLS 1.2 RFC already discusses how to do that.

Basically, if decryption fails, you need to carry on as nothing had
happened, but then cause Finished MAC check to fail. In _constant_
time. Which is not easy, and even if your code looks constant time,
compiler "optimizations" can really ruin your day.

I think there should be a draft which formally deprecates RSA,
recommends the support to be removed (at least from server side)
and updates TLS 1.2 to change the MTI ciphersuite. Of course,
certain ("visibility") folks would scream about that.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 19:46:28 +0200

On Fri, Dec 15, 2017 at 02:57:33PM +0000, Andrei Popov wrote:
> > Even nastier dependency: SHA-2. If that breaks, currently both TLS
> > 1.2 and 1.3 break. There are no alternatives defined.
> 

Also would need TLS ciphersuite codepoints with alternative handshake
hash algorithms.

-Ilari

---

From: Andrei Popov <[email-masked]>
Date: Fri, 15 Dec 2017 18:03:46 +0000

Correct.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Friday, December 15, 2017 9:46 AM
To: Andrei Popov <[email-masked]>
Cc: Colm MacCárthaigh <[email-masked]>; [email-masked]
Subject: Re: [TLS] A closer look at ROBOT, BB Attacks, timing attacks in general, and what we can do in TLS

On Fri, Dec 15, 2017 at 02:57:33PM +0000, Andrei Popov wrote:
> Here's an attempt to define a SHA-2 alternative: 
> https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftools
> .ietf.org%2Fhtml%2Fdraft-wconner-blake2sigs-01&data=04%7C01%7CAndrei.P
> opov%40microsoft.com%7C30de6e3a48024110441608d543e3c8b7%7C72f988bf86f1
> 41af91ab2d7cd011db47%7C1%7C0%7C636489567969040822%7CUnknown%7CTWFpbGZs
> b3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwifQ%3D%3D%7C-1&
> sdata=f72MvX0ydw5WvjkvngbY39sai8v9oOc5ZUYZOQI3XmI%3D&reserved=0

Also would need TLS ciphersuite codepoints with alternative handshake hash algorithms.

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 15 Dec 2017 10:07:16 -0800

I'm not quite following how this helps. It's true that if SHA-256 is
broken, we're in serious trouble, but that's largely because of the fact
that that's what people's certificates have, so clients really can't refuse
to support SHA-256 certificates. So, how does adding new algorithms help?
(That's why I would argue that the existing SHA-384 support doesn't help).

-Ekr

On Fri, Dec 15, 2017 at 9:46 AM, Ilari Liusvaara <[email-masked]>
wrote:

> https://tools.ietf.org/html/draft-wconner-blake2sigs-01
>

---

From: Watson Ladd <[email-masked]>
Date: Fri, 15 Dec 2017 10:12:59 -0800

We can force a rotate of all certs in 90 days, and I don't think most
people will notice.

On Fri, Dec 15, 2017 at 10:07 AM, Eric Rescorla <[email-masked]> wrote:
> I'm not quite following how this helps. It's true that if SHA-256 is broken,
> we're in serious trouble, but that's largely because of the fact that that's
> what people's certificates have, so clients really can't refuse to support
> SHA-256 certificates. So, how does adding new algorithms help? (That's why I
> would argue that the existing SHA-384 support doesn't help).
>
> -Ekr
>
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 20:14:32 +0200

> (That's why I would argue that the existing SHA-384 support doesn't help).

TLS handshake assumes the hash function is strongly collision-
resistant. So if SHA-256/SHA-384 breaks, the handshake hash function
needs to be replaced.

This is separate from certificate signatures. Transitioning this would
be much more nasty than TLS handshake hash, because there is no
backward-compatible way of changing the hash. This is one major reason
why SHA-1 transition took over 10 years (oh, then there is the "fun"
post-quantum transition possibly coming up).

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 15 Dec 2017 10:15:23 -0800

> We can force a rotate of all certs in 90 days, and I don't think most

Unfortunately, there are plenty of longterm certificates with lifetimes >>
90 days.

-Ekr

> broken,

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 15 Dec 2017 10:16:59 -0800

> resistant. So if SHA-256/SHA-384 breaks, the handshake hash function

Yes. In 1.3, you would define new cipher suites with the new hash. But of
course you then have to worry about downgrade if clients jointly support
the weakest hash and it's weak enough.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 20:34:24 +0200

> Unfortunately, there are plenty of longterm certificates with lifetimes >>

Yes, currently the lifetime limit for public certificates is 39 months,
and will be reduced to 825 days (~27 months) effective March 2018.

Then there is backdating to consider. It was seen in both MD5 and SHA-1
deprecations. So maximum certificate lifetime sets limit on how fast
features can be flushed out.

And then there would be enormous amounts of endpoints not supporting
anything better. Those would have to be upgraded.

All in all, a real mess.

-Ilari

---

From: Andrei Popov <[email-masked]>
Date: Fri, 15 Dec 2017 18:41:06 +0000

It's true, the migration will be slow, but IMHO it still makes sense to define and implement an alternative hash.

-----Original Message-----
From: TLS [mailto:[email-masked]] On Behalf Of Ilari Liusvaara
Sent: Friday, December 15, 2017 10:34 AM
To: Eric Rescorla <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] A closer look at ROBOT, BB Attacks, timing attacks in general, and what we can do in TLS

On Fri, Dec 15, 2017 at 10:15:23AM -0800, Eric Rescorla wrote:
> > We can force a rotate of all certs in 90 days, and I don't think 
> > most people will notice.
> >
> 

Yes, currently the lifetime limit for public certificates is 39 months, and will be reduced to 825 days (~27 months) effective March 2018.

Then there is backdating to consider. It was seen in both MD5 and SHA-1 deprecations. So maximum certificate lifetime sets limit on how fast features can be flushed out.

And then there would be enormous amounts of endpoints not supporting anything better. Those would have to be upgraded.

All in all, a real mess.

-Ilari

_______________________________________________
TLS mailing list
[email-masked]
https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=04%7C01%7CAndrei.Popov%40microsoft.com%7C248257e4202549b54e9208d543ea7ff7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636489596817634560%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwifQ%3D%3D%7C-1&sdata=viW%2F6xW3bJoG6SlxgENwp%2BFH8%2Bqnb%2BFynkE4Yxfq%2Bjc%3D&reserved=0

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 20:49:51 +0200

On Fri, Dec 15, 2017 at 06:41:06PM +0000, Andrei Popov wrote:
> It's true, the migration will be slow, but IMHO it still makes sense
> to define and implement an alternative hash.

Agreed. However, on certificates front, we need a method to perform
backward-compatible algorithm transition. Because non-backward-
compatible ones are just too hard. As we have seen _twice_.

On TLS handshake hashes, the transitions are already backward-
compatible. But that does not mean the transition will be easy.

-Ilari

---

From: Tim Hollebeek <[email-masked]>
Date: Fri, 15 Dec 2017 19:14:00 +0000

So, this has been discussed extensively at the CA/Browser forum, for obvious
reasons.

In my mind, it is not so important to identify and define and implement an
alternative hash.

What *is* important is that the protocol and associated software is able to
support a smooth transition period where people are moving from one
algorithm to another.

Ideally, you'd want certificates to be able to have two signatures during
the transition period, in order to support clients who have transitioned and
those who have not.  Unfortunately RFC 5280 is deficient in that regard.
Hosting multiple certificates and switching based on the client is feasible,
but requires some technical wizardry and isn't possible in all situations.

A lot of these transitions are painful because with the way things currently
work, algorithms have to reach near ubiquity before the transition can begin
(the popularity of Windows XP was a huge problem).

The transition will happen at different rates for various industries and use
cases that have different security requirements, so everyone needs to be
able to move at a pace that makes sense for their needs.  It needs to be
carefully coordinated, and yes, transitions will take years.  The current
maximum certificate lifetime is a compromise between the speed at which
changes can be made, and the pain imposed by replacement, which largely
still isn't automated.  I know people are working to improve that, but we
are where we are.

-Tim

> Sent: Friday, December 15, 2017 11:50 AM
> On TLS handshake hashes, the transitions are already backward- compatible.
> But that does not mean the transition will be easy.
> 
> 
> 
> 
> -Ilari
>

---

From: Andrei Popov <[email-masked]>
Date: Fri, 15 Dec 2017 19:25:20 +0000

> those who have not.

> but requires some technical wizardry and isn't possible in all situations.

For my understanding, why is the former (double-signed certs, where either signature is trusted) better than the latter (multiple certs with different algorithms)?
The latter is currently supported by some TLS servers.

Cheers,

Andrei

---

From: Tim Hollebeek <[email-masked]>
Date: Fri, 15 Dec 2017 19:33:44 +0000

Because it's easier for the client to decide what the client understands
than it is for the server to decide what the client understands.  Less
complexity = less failures.  

Note that this is how XP was handled for code signing.  The Authenticode
spec actually made it so if you did things in the right order, XP would only
see the SHA-1 signature, while more recent operating systems would see both
the SHA-1 and SHA-2 signatures, ignore the SHA-1 signature, and use the
SHA-2 signature.  This allowed doubly-signed binaries that worked both on XP
and non-XP systems.  Unfortunately the technical steps to do so weren't
widely publicized, but I know some companies took advantage of it.

However, servers are easier to upgrade than clients, which is why you see
some of the server side support you mention.  I know CloudFlare in
particular helped a lot of people cope with communicating with clients who
had different certificate capabilities.  It isn't a bad thing that both
approaches exist.

-Tim

> From: Andrei Popov [mailto:[email-masked]]
> Sent: Friday, December 15, 2017 12:25 PM
> To: Tim Hollebeek <[email-masked]>; Ilari Liusvaara
> <[email-masked]>
> Cc: [email-masked]
> Subject: RE: [TLS] A closer look at ROBOT, BB Attacks, timing attacks in
> general, and what we can do in TLS
> 
> > Ideally, you'd want certificates to be able to have two signatures
> > during the transition period, in order to support clients who have
> > transitioned and those who have not.
> 
> > Hosting multiple certificates and switching based on the client is
> > feasible, but requires some technical wizardry and isn't possible in all
> situations.
> 
> For my understanding, why is the former (double-signed certs, where either
> signature is trusted) better than the latter (multiple certs with
different
> algorithms)?

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 21:37:32 +0200

> In my mind, it is not so important to identify and define and implement an

Well, I would think that having ready to go backup would cut fair
amount of time from transitions.

It should be noted that the two transitions we have seen had backup
algorithm already (SHA-1 in case of MD5 and SHA-2 in case of SHA-1).

> support a smooth transition period where people are moving from one

Yes, that is what I was referring with "backward-compatible algorithm
transition".
 
> but requires some technical wizardry and isn't possible in all situations.

Yes, there are enormous amount of stacks that have problems with
multiple certificate chains. Ranging from OCSP stapling not working
properly (Nginx+openSSL) to dual-cert not working at all (too many to
list).

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 21:45:17 +0200

On Fri, Dec 15, 2017 at 07:25:20PM +0000, Andrei Popov wrote:
> signature is trusted) better than the latter (multiple certs with different
> algorithms)? The latter is currently supported by some TLS servers.

Because the latter is only supported by some TLS servers.

And even if the TLS server nominally supports multiple certificates,
there may be other issues. E.g., OCSP stapling does not work correctly
with multiple certificates.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 15 Dec 2017 21:55:29 +0200

> had different certificate capabilities.  It isn't a bad thing that both

Also, it should be noted that the past two migrations needed to be
compatible with TLS 1.0 and 1.1, which have much less advanced
signature negotiation than TLS 1.2 (and 1.3).

However, there are enormous amount of very badly configured servers out
there, so it is doubtful how quickly things change.

-Ilari

---

From: [email-masked] (Martin Rex)
Date: Sat, 16 Dec 2017 00:15:32 +0100 (CET)

> widely publicized, but I know some companies took advantage of it.

Now that sounds weird.

If I look at the code signatures on my Windows 7 machine,
e.g.
    C:\windows\ccm\CcmExec.exe

it carries one single digital signature & timestamp _from_Microsoft_ 
created 01-November-2017 and both with sha1RSA.

So it seems some vendors haven't really started migrating away from SHA-1.

-Martin

---

From: [email-masked] (Martin Rex)
Date: Sat, 16 Dec 2017 00:30:06 +0100 (CET)

> signature negotiation than TLS 1.2 (and 1.3).

There is an awfully large installed base of borked TLSv1.2 servers.

If those servers are equipped with a sha256WithRsaEncryption server cert,
the handshake results are:

  - TLSv1.0 for SSLv3 ClientHello w/ client_version = (3,1) 
  - TLSv1.1 for SSLv3 ClientHello w/ client_version = (3,2) 
  - TLSv1.1 for SSL VERSION 2 CLIENT-HELLO offering (3,3)
  - chokes and drops network connection
           for SSLv3 ClientHello w/ client_version = (3,3)

i.e. there exists a serious interop problem for TLSv1.2 with such servers,
but there is no problem interoperating with TLSv1.0 or TLSv1.1

-Martin

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 16 Dec 2017 12:21:28 +0200

> but there is no problem interoperating with TLSv1.0 or TLSv1.1

What I meant is that in TLS 1.2, one could signal the client
transition status, whereas that is not possible in TLS 1.0 and 1.1.

E.g. suppose we need to transition from SHA-2 to SHA-3.

Pre-transition: signature_algorithms=...,ecdsa_secp256r1_sha256,...
In-transition: signature_algorithms=...,ecdsa_secp256r1_sha3256,ecdsa_secp256r1_sha256,...
Post-transition: signature_algorithms=...,ecdsa_secp256r1_sha3256,...

And server with apropriate SHA-3 certificate chain can send it to the
client. The similar works across signature algorithms.

But this is not possible with TLS 1.0 and 1.1 without very nasty hacks.

However, as noted, many servers do not correctly deal with having two
certificates at the same time. Or server owners think it is too
difficult to deal with them. Dual-signature certificates would be
valuable for those cases.

-Ilari

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 20 Dec 2017 15:37:46 +0000

>https://github.com/awslabs/s2n/blob/master/utils/s2n_safety.c#L70

Has anyone actually been able to measure the impact of issues like this?  I
know about papers like "Remote timing attacks are practical" that work with
things like Montgomery modmult, but can much be practically done with a few
instructions here and there, not repeated in a loop like a modmult?

The reason I ask is a combination of two things, firstly I've done timing
measurements on my own code to try and detect differences in behaviour and
couldn't find anything among the general noise of code execution, and secondly
any constant-time code is a tradeoff between readability/auditability and
(near) constant-time operation ("near" because you have no control over what a
compiler will do to optimise your code, so it may not be anywhere near
constant-time once it's in binary form).  Something like
s2n_constant_time_copy_or_dont() is barely passable, but I've seen constant-
time PKCS #1 decoding and similar that's essentially incomprehensible, there's
no way to look at it and see that it's correct.  Even something as simple as:

https://blog.cloudflare.com/yet-another-padding-oracle-in-openssl-cbc-ciphersuites/

had errors, because the constant-time code is so difficult to audit.

>Next, when the handshake does fail, we do two non-standard things. The first
>is that we don't return an alert message, we just close the connection. 

That's actually really annoying, because it implies something other than a TLS
crypto problem, e.g. a misconfigured firewall or who knows what.  I don't know
how diversely-used s2n is, in other words whether you can assume the clients
and servers employed will know how to react to this, but in general use it'll
make getting things working a major pain since it changes the error indicator
from "the TLS handshake failed due to crypto issues" to "something failed
somewhere, probably at the network level".

>as if something suspicious is going on and in case timing is involved, we add
>a random delay. It's well known that random delays are only partially
>seconds. With the delay being granular to nanoseconds. 

I do the same thing, but I use 1s rather than 10 (although I've just bumped
this to 3 in the latest code):

/* Delay by a small random amount, used to dither the results of (failed) 
   crypto operations to make timing attacks harder.
   
   As with anything involving randomness, there's been a lot of smoke and 
   not much light generated over the use of random delays to address timing 
   attacks.  The generic answer is that it doesn't help so there's no point 
   in doing it and everyone should just write constant-time code, another 
   prime example of le mieux est l'ennemi du bien.

   If the arguments ever get beyond abstract theory (theoretical constant-
   time code is better than theoretical random delays), the argument given 
   is usually that we're measuring timing differences in us or ns while the 
   delay functions are typically in ms.  Another argument is that all an 
   attacker has to do is repeat the measurements in order to filter out the 
   delays.

   The counterargument for the former is that if you've got an attacker 
   sitting on your local LAN segment making ns-scale timing measurements on 
   your crypto then you've got bigger things to worry about than side-
   channel attacks (over more distant connections, you can at best get tens 
   to hundreds of us using thousands of measurements, see e.g. 
   "Opportunities and Limits of Remote Timing Attacks" by Crosby, Reid, and 
   Wallach, which also required multiple days of data-gathering beforehand 
   to characterise the network).  In addition in cryptlib's case since all 
   operations go via the kernel, you don't have direct (timing) access to 
   the low-level crypto ops but only get strongly dithered results at that 
   level.

   As a result, while you can still use repeated measurements to eventually
   filter out the dithering, it's now made the attacker's job much, much 
   harder.  Since it's essentially free (it's only invoked if an operation 
   fails), it makes sense to add the delay.

   Another issue is how long to make the delay.  Obviously the longer, the
   better, however if we make it too long then it can end up looking like a
   different problem, e.g. a networking issue rather than a crypto defence,
   which will be a pain to diagnose for users.  3s seems to be a good tradeoff
   between dithering operations and slowing down an attacker while not adding
   an excessive delay that looks like it's caused by something else */

Again, it's for ease of deployment, a 1s (or 3s) delay won't get noticed while
a 10s delay looks like a network problem, and 30s looks like a major issue
somewhere.

>The solutions here typically are not small routines that are rigorously
>constant time, but instead rely on a degree of code-balancing: taking code
>paths that are "similar enough" in timing so as not to be measurable.

Yup, that's what I try and do.

>trying to be rigorously constant time on large complicated algorithms that
>were not designed to be constant time can seriously backfire by introducing
>logic errors in the very hard-to-follow constant-time adaptations.

You don't even need large complicated algorithms, you can create logic errors
in a few lines of code, as your cited example shows.  That's why I prefer
obvious correctness (or probably-correctness :-) and defences in other places.

Peter.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 20 Dec 2017 23:50:44 +0200

On Wed, Dec 20, 2017 at 03:37:46PM +0000, Peter Gutmann wrote:

> no way to look at it and see that it's correct. 

Just for fun I tried to implement decoding raw decrypted PKCS#1 encoded
RSA premaster secret and then checking the finished MAC. In way not
vulernable to ROBOT.

I started with code already implementing (EC)DHE key derivation and
finished check. It was like 25-30 (depends on how one counts) lines of
(not very hairy) code to implement, including modifications to existing
code. And this was without any fancy libraries (including random number
generation). Of course, just removing static RSA is much easier way
of eliminate ROBOT.

I never hooked it up to TLS proper, because that would have been
hundreds of lines of code at the very least. Plus, the code is not
up to my quality standards to publish, even as a hack (ocassionally
absolutely incredible things make to "production").

-Ilari