Subject: [Trans] STAR & CT coexistence

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Mon, 6 Nov 2017 21:30:44 +0000

Hi everybody,

Context

We are working on STAR [1], an ACME extension to allow a name owner to obtain a string of short-lived certificates that are automatically renewed by the issuing CA.

Using STAR, the name owner controls the lifetime of the renewal process, which can continue for as long as initially agreed, or prematurely come to a halt due to, e.g., a key compromise.

STAR removes the dependency on the revocation infrastructure, while at the same time automating (and minimizing) the interaction of the certificate owner with her RA/CA.

So far so good.

STAR + CT

Obviously, we’d want STAR to work well with Certificate Transparency.

However, it looks like this might not be as easy as we want it to be because of the increase of the ingestion rate and consequent implications on log structure, implementation, rotation, monitoring, etc.

What we were thinking, though – and this is where we’d need your help, since none of us is a CT expert – is that a STAR certificate, except in the degenerate case where users requests a very low number of renewals, can be thought of as a single “usual” certificate that is made of a collection of same short-lived certificates that differ only for their (sliding) validity windows.

If so, it seems (at least theoretically) possible to treat all of them as a single entity from a CT log perspective?

A fall back: the “Certificate Transparency with Privacy” proposal

In case the above hypothesis doesn’t hold true:

A few weeks ago, we got in touch with Eran because of his recent PETS paper in which he sketches a mechanism for dealing with short-lived certs in the context of CT (section 4 of [2]).

Unfortunately, he told us that he wasn’t working on CT anymore and therefore he would not progress those ideas further.  Would any of you be interested in taking over from him and maybe bring it to standardization?

Cheers, thanks very much,

[1] https://datatracker.ietf.org/doc/draft-ietf-acme-star/

[2] https://petsymposium.org/2017/papers/issue4/paper69-2017-4-source.pdf

PS: At least two of us will be in Singapore: if any of you would like to have a f2f discussion, we’d be more than happy to.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Nov 2017 14:36:32 -0800

On Mon, Nov 6, 2017 at 1:30 PM, Fossati, Thomas (Nokia - GB/Cambridge,
UK) <[email-masked]> wrote:
> Hi everybody,
>
>
>
> Context
>
> We are working on STAR [1], an ACME extension to allow a name owner to
> obtain a string of short-lived certificates that are automatically renewed
> by the issuing CA.
>
> Using STAR, the name owner controls the lifetime of the renewal process,
> which can continue for as long as initially agreed, or prematurely come to a
> halt due to, e.g., a key compromise.
>
> STAR removes the dependency on the revocation infrastructure, while at the
> same time automating (and minimizing) the interaction of the certificate
> owner with her RA/CA.
>
> So far so good.
>
>
>
> STAR + CT
>
> However, it looks like this might not be as easy as we want it to be because
> of the increase of the ingestion rate and consequent implications on log
> structure, implementation, rotation, monitoring, etc.
>
> What we were thinking, though – and this is where we’d need your help, since
> none of us is a CT expert – is that a STAR certificate, except in the
> degenerate case where users requests a very low number of renewals, can be
> thought of as a single “usual” certificate that is made of a collection of
> same short-lived certificates that differ only for their (sliding) validity
> windows.

We also have work in TLS on short term credentials that can be issued
by people with the private keys of certificates. Could this be
shoehorned to solve the problems STAR solves without requiring lots of
CT entries?

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

---

From: Melinda Shore <[email-masked]>
Date: Mon, 6 Nov 2017 20:09:54 -0900

The question of how to log short-lived certificates is something
that's been coming up more frequently recently, and it's
independent (mostly) of the issuance mechanism.  I think we've
got time to discuss it during the session at IETF 100, and
it would be helpful if there's a specific proposal to use as
a starting point.  Will the folks working on this be
at the meeting?

Melinda

---

From: Eran Messeri <[email-masked]>
Date: Tue, 7 Nov 2017 16:54:04 -0800

One way for a single SCT to be valid for multiple certificates is to omit
the fields that change from the data covered by the SCT's signature.
For short-lived certificates this would (likely) be the serial number,
notBefore and notAfter dates.

This means there's no need to re-request an SCT each time a new short-lived
certificate is minted, and the SCT covers all key fields in the
certificate's TBSCertificate structure (Subject Alternative Names, key,
etc).
The drawback is that without a serial number (1) it is not possible to
verify CAs don't violate the unique serial number requirement (effectively
reducing auditing capabilities) (2) mis-issued certificates can't be
revoked using the usual means.

Note that such a mechanism cannot be implemented either using 6962 or
6962-bis: Both documents mandate that the SCT covers all fields in the
TBSCertificate (at least). But, if the design was changed to exclude some
fields, it seems to me that this solution would otherwise be compatible
with the rest of the CT protocol.

On Mon, Nov 6, 2017 at 9:09 PM, Melinda Shore <[email-masked]>
wrote:

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

---

From: Jeremy Rowley <[email-masked]>
Date: Wed, 8 Nov 2017 01:24:08 +0000

We are interested in this. Clint Wilson will be there and happy to help on
both sides (as a log operator interested in logging certs through STAR and as 
a CA
interested in implementing STAR).

-----Original Message-----
From: Trans [mailto:[email-masked]] On Behalf Of Melinda Shore
Sent: Monday, November 6, 2017 10:10 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [Trans] STAR & CT coexistence

The question of how to log short-lived certificates is something that's been
coming up more frequently recently, and it's independent (mostly) of the
issuance mechanism.  I think we've got time to discuss it during the session
at IETF 100, and it would be helpful if there's a specific proposal to use as
a starting point.  Will the folks working on this be at the meeting?

Melinda

---

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Wed, 8 Nov 2017 10:00:08 +0000

Hi Melinda,

On 07/11/2017, 05:09, "Melinda Shore" <[email-masked]> wrote:
> that's been coming up more frequently recently, and it's independent
> (mostly) of the issuance mechanism.  I think we've got time to discuss
> it during the session at IETF 100, and it would be helpful if there's
> a specific proposal to use as a starting point.  Will the folks
> working on this be at the meeting?

Great, thanks.

We don't have any specific proposal at this point in time, but if we can
have a small slot in the agenda (say 10m) we could present the general
problem and our current thinking WRT the STAR and CT coexistence?

Ideally, that would trigger the relevant conversation where you folks
tell us if and how this can be solved :-)

Cheers

---

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Wed, 8 Nov 2017 10:04:28 +0000

Hi Eran,

Thanks (again) for your insight.

Do you think we’d need a 6962-ter to accommodate STAR?  Or could we specify a different SCT format and processing rules for STAR-like certificates in the framework defined by 6962-bis?

Cheers

On 08/11/2017, 00:54, "Eran Messeri" <[email-masked]<mailto:[email-masked]>> wrote:

One way for a single SCT to be valid for multiple certificates is to omit the fields that change from the data covered by the SCT's signature.
For short-lived certificates this would (likely) be the serial number, notBefore and notAfter dates.

This means there's no need to re-request an SCT each time a new short-lived certificate is minted, and the SCT covers all key fields in the certificate's TBSCertificate structure (Subject Alternative Names, key,  etc).
The drawback is that without a serial number (1) it is not possible to verify CAs don't violate the unique serial number requirement (effectively reducing auditing capabilities) (2) mis-issued certificates can't be revoked using the usual means.

Note that such a mechanism cannot be implemented either using 6962 or 6962-bis: Both documents mandate that the SCT covers all fields in the TBSCertificate (at least). But, if the design was changed to exclude some fields, it seems to me that this solution would otherwise be compatible with the rest of the CT protocol.

On Mon, Nov 6, 2017 at 9:09 PM, Melinda Shore <[email-masked]<mailto:[email-masked]>> wrote:

Melinda

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

---

From: Al Cutter <[email-masked]>
Date: Wed, 8 Nov 2017 14:59:43 +0000

Hi,

I'm a fan of short-lived certs, but I'm not particularly keen on the idea
of not logging publicly rooted certs - the point of CT is the
discoverability of misissuance after all, and it does seem that having an
SCT which could refer to a whole set of "similar" yet unlogged certs is not
a great idea, e.g. a scenario where the key is compromised by an entity
which can coerce the CA into issuing more "non-logged" certs to cover any
period the proud new owner of the key material would like.

I'll point out that there does seem to be an underlying premise here that
it's simply not possible to log all these short-lived certs, have we
considered whether that's actually the case?
Back of the envelope: currently, the global issuance rate of certs is < 10
per second on average [90d average growth of Pilot is actually < 5/s]. The
overwhelming majority of certificates come from Let's Encrypt, and
currently all have a lifetime of 90 days.  If we're talking about reducing
that cert lifetime to 24h then we're looking at 90x increase, so let's call
it 1k/s.

Even if we're assuming that every cert must be logged to every Log I think
that's achievable by the Trillian-based logs, and I'll coyly mention that
I'm aware of one other Log implementation which I'm led to believe is more
than capable of sustaining that level of throughput.  Were that not the
case, it's also not hard to imagine schemes for spreading this load around
if need be (e.g. sharding by modulo of cert hash etc., "smart"
load-balancing CT proxies, etc. etc.)

Log growth to very large sizes can be already be addressed by schemes such
as Chrome's Temporal Log Policy which allow Operators to define their Log
life-cycle, and CAs, UAs, Monitors, and any other interested entity to
build-in support for that life-cycle ahead of time.

There might be other concerns of scale elsewhere, but I'm not sure that
it's in the logging.

Cheers,
Al.

On Wed, Nov 8, 2017 at 10:04 AM, Fossati, Thomas (Nokia - GB/Cambridge, UK)
<[email-masked]> wrote:

> Do you think we’d need a 6962-ter to accommodate STAR?  Or could we
> specify a different SCT format and processing rules for STAR-like
> certificates in the framework defined by 6962-bis?
>
>
>
> Cheers
>
>
>
> On 08/11/2017, 00:54, "Eran Messeri" <[email-masked]> wrote:
>
>
>
> This means there's no need to re-request an SCT each time a new
> short-lived certificate is minted, and the SCT covers all key fields in the

---

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Wed, 8 Nov 2017 23:28:08 +0000

Hi Al,

On 08/11/2017, 14:59, "Al Cutter" <[email-masked]> wrote:
> I'm a fan of short-lived certs, but I'm not particularly keen on the
> idea of not logging publicly rooted certs - the point of CT is the
> discoverability of misissuance after all, and it does seem that having
> an SCT which could refer to a whole set of "similar" yet unlogged
> certs is not a great idea, e.g. a scenario where the key is
> compromised by an entity which can coerce the CA into issuing more
> "non-logged" certs to cover any period the proud new owner of the key
> material would like.

A STAR certificate is not open ended.  Its overall validity is bounded
by the recurrent-start-date and recurrent-end-date attributes that are
negotiated at the time the ACME order is made.

It is my impression that both recurrent-start-date and
recurrent-end-date should go in the SCT to provide semantics equivalent
to the notBefore/notAfter attributes of "regular" certificates.

If so, in the key compromise & CA coercion scenario that you are
describing, the attacker would not be able to convince the CA to issue
other short-term certificates than those which are already lined up
- up to recurrent-end-date - while also confusing CT.

Coercion would only result in ignoring any attempt from the user to
terminate the STAR order, similarly to the CA coerced to avoid updating
revocation information on key compromise with a "regular" certificate.

Am I missing something? (Probably so...)

> I'll point out that there does seem to be an underlying premise here
> that it's simply not possible to log all these short-lived certs, have
> we considered whether that's actually the case?  Back of the envelope:
> currently, the global issuance rate of certs is < 10 per second on
> average [90d average growth of Pilot is actually < 5/s]. The
> currently all have a lifetime of 90 days.  If we're talking about
> reducing that cert lifetime to 24h then we're looking at 90x increase,
> so let's call it 1k/s.
> 
> Even if we're assuming that every cert must be logged to every Log I
> think that's achievable by the Trillian-based logs, and I'll coyly
> mention that I'm aware of one other Log implementation which I'm led
> to believe is more than capable of sustaining that level of
> throughput.  Were that not the case, it's also not hard to imagine
> schemes for spreading this load around if need be (e.g. sharding by
> modulo of cert hash etc., "smart" load-balancing CT proxies, etc.
> etc.)
> 
> Log growth to very large sizes can be already be addressed by schemes
> such as Chrome's Temporal Log Policy which allow Operators to define
> their Log life-cycle, and CAs, UAs, Monitors, and any other interested
> entity to build-in support for that life-cycle ahead of time.
> 
> There might be other concerns of scale elsewhere, but I'm not sure
> that it's in the logging.

Very interesting.

Cheers

---

From: Rob Stradling <[email-masked]>
Date: Thu, 9 Nov 2017 21:56:21 +0000

On 08/11/17 00:54, Eran Messeri wrote:
> One way for a single SCT to be valid for multiple certificates is to 
> omit the fields that change from the data covered by the SCT's signature.
> short-lived certificate is minted, and the SCT covers all key fields in 
> the certificate's TBSCertificate structure (Subject Alternative Names, 
> key,  etc).
> > The drawback is that without a serial number

Hi Eran.  Just thinking about the problem space here...

> (1) it is not possible to 
> verify CAs don't violate the unique serial number requirement 
> (effectively reducing auditing capabilities)

One way to mitigate this would be to require the use of a deterministic 
serial number scheme (i.e., where the serial number is calculated from 
the rest of the TBSCertificate just before the cert is signed).

> (2) mis-issued certificates can't be revoked using the usual means.

The "usual means" of revocation (CRL and OCSP) "don't work" anyway. 
That is, many of today's TLS clients no longer use these mechanisms.

Alternative revocation mechanisms could be invented that revoke groups 
of certs (e.g., perhaps by SHA-256(SubjectPublicKeyInfo), or by 
SHA-256(SharedSCT), etc, instead of by serial number).

> TBSCertificate (at least). But, if the design was changed to exclude 
> some fields, it seems to me that this solution would otherwise be 
> compatible with the rest of the CT protocol.

How about defining an SCT extension that, when present, indicates that 
the SCT's signature doesn't cover serial number, notBefore and notAfter?

>     [email-masked] <mailto:[email-masked]>
>     <https://www.ietf.org/mailman/listinfo/trans>
> 
> 
> 
> 

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online
Office Tel: +44.(0)1274.730505
Office Fax: +44.(0)1274.730909
www.comodo.com

COMODO CA Limited, Registered in England No. 04058690
Registered Office:
   3rd Floor, 26 Office Village, Exchange Quay,
   Trafford Road, Salford, Manchester M5 3EQ

This e-mail and any files transmitted with it are confidential and 
intended solely for the use of the individual or entity to whom they are 
addressed.  If you have received this email in error please notify the 
sender by replying to the e-mail containing this attachment. Replies to 
this email may be monitored by COMODO for operational or business 
reasons. Whilst every endeavour is taken to ensure that e-mails are free 
from viruses, no liability can be accepted and the recipient is 
requested to use their own virus checking software.

---

From: Bryan Ford <[email-masked]>
Date: Sat, 11 Nov 2017 12:44:29 +0100

On Nov 8, 2017, at 3:59 PM, Al Cutter <[email-masked]> wrote:
> I'm a fan of short-lived certs, but I'm not particularly keen on the idea of not logging publicly rooted certs - the point of CT is the discoverability of misissuance after all, and it does seem that having an SCT which could refer to a whole set of "similar" yet unlogged certs is not a great idea, e.g. a scenario where the key is compromised by an entity which can coerce the CA into issuing more "non-logged" certs to cover any period the proud new owner of the key material would like.

100% agreed on this point.  Short-term certs are good, and they all should - and can - be publicly logged to ensure transparency.  To whatever extent this capacity issue is a problem in the current CT design, this is a problem with CT that needs to be fixed.

The SkipChain structure for cryptographically-traversable, collectively-signed blockchains, detailed in our CHAINIAC work that I just mentioned (https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/nikitin <https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/nikitin>), may be of use here.  The SkipChain structure is designed to support groups of collective signers whose public keys may change quite rapidly, while ensuring that any client or validator can “catch up” with its peers’ state quickly and efficiently no matter how far behind in time they may be.

For example, SkipChains were designed to support permissionless blockchains such as Bitcoin or ByzCoin (https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias <https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias>), where the the collective signing group is defined by a window of recent proof-of-work miners that may change very 10 minutes.  The SkipChain structure enables new or long-offline light clients or full nodes to catch up with the state of the blockchain from any recent collectively-signed snapshot, without everyone having to store the entire blockchain history.  In practice we expect some subset of validators well-provisioned with storage would still store the entire history, but that becomes optional rather than mandatory.

Note that I’m definitely not suggesting that CT would want proof-of-work; just bringing this up as an example “torture test” for frequently-changing keys/certificates that the SkipChain structure is designed and already demonstrated to support efficiently.  The property that SkipChains allow nodes (e.g., log servers, CAs, and/or clients) to prune their storage of rapidly-changing logs more aggressively seems like the property most likely of potential valid here.

But in any case, how exactly SkipChains would best fit into CT and/or STAR is of course an open question for discussion, which I’m happy to participate in if there’s interest.

Bryan

---

From: Watson Ladd <[email-masked]>
Date: Sat, 11 Nov 2017 17:40:49 -0800

On Sat, Nov 11, 2017 at 3:44 AM, Bryan Ford <[email-masked]> wrote:
> I'm a fan of short-lived certs, but I'm not particularly keen on the idea of
> not logging publicly rooted certs - the point of CT is the discoverability
> of misissuance after all, and it does seem that having an SCT which could
> refer to a whole set of "similar" yet unlogged certs is not a great idea,
> e.g. a scenario where the key is compromised by an entity which can coerce
> the CA into issuing more "non-logged" certs to cover any period the proud
> new owner of the key material would like.
>
>
> 100% agreed on this point.  Short-term certs are good, and they all should -
> and can - be publicly logged to ensure transparency.  To whatever extent
> this capacity issue is a problem in the current CT design, this is a problem
> with CT that needs to be fixed.

What are the problems we are trying to solve with short-term certs and
can we come up with a way to solve them that doesn't have the
implications for CT of the current proposal?
TLS delegated credentials seem to do what we want, but maybe I don't
understand the problem well enough. Pruning chains of expired certs
has implications for misbehavior detection.

Sincerely,
Watson

---

From: "Fossati, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Sun, 12 Nov 2017 02:22:45 +0000

Hi Watson,

On 12/11/2017, 09:40, "Watson Ladd" <[email-masked]> wrote:
> > > I'm a fan of short-lived certs, but I'm not particularly keen on
> > > the idea of not logging publicly rooted certs - the point of CT is
> > > the discoverability of misissuance after all, and it does seem
> > > that having an SCT which could refer to a whole set of "similar"
> > > yet unlogged certs is not a great idea, e.g. a scenario where the
> > > key is compromised by an entity which can coerce the CA into
> > > issuing more "non-logged" certs to cover any period the proud new
> > > owner of the key material would like.
> >
> > 100% agreed on this point.  Short-term certs are good, and they all
> > should - and can - be publicly logged to ensure transparency.  To
> > whatever extent this capacity issue is a problem in the current CT
> > design, this is a problem with CT that needs to be fixed.
> 

Al was pointing out that maybe the 100x increase in ingestion (worst
case, assuming every cert becomes a STAR cert) would not be the end of
the world.  And even if it were, there might be scalability strategies
that might mitigate/fix it?

> understand the problem well enough.

The main issue with DC is that until all the clients have upgraded their
TLS stack (and even then, they must decide to opt-in DC), server side
you need to maintain a LURK-box fall-back, which is neither cheap nor
scalable.  Sadly, the upgrade cycles of a STB or a CPE is completely
different from that of modern browsers.  Short-term certs from that
point of view, just work out of the box.

(See also the discussion on the TLS mailing list at the time the call for
adoption of DC was made [1].)

Cheers

[1] https://www.ietf.org/mail-archive/web/tls/current/msg24098.html

---

From: Ben Laurie <[email-masked]>
Date: Mon, 13 Nov 2017 14:21:20 +0000

On 12 November 2017 at 01:40, Watson Ladd <[email-masked]> wrote:

> idea of
> should -

The problem is revocation (or the lack of it).

We actually know how to solve transparency for revocation, and what's more
Trillian provides the necessary infrastructure, so I'm not entirely sure
why we'd want to make the job of checking for misissued certs 100x more
expensive rather than just making revocation work properly (which
presumably could use the same underlying mechanism to determine revocation
status).

---

From: "Dr. Pala" <[email-masked]>
Date: Tue, 14 Nov 2017 09:17:13 +0800

On 11/13/17 10:21 PM, Ben Laurie wrote:
> [...]
> We actually know how to solve transparency for revocation, and what's 
> more Trillian provides the necessary infrastructure, so I'm not 
> entirely sure why we'd want to make the job of checking for misissued 
> certs 100x more expensive rather than just making revocation work 
> properly (which presumably could use the same underlying mechanism to 
> determine revocation status).
+1

Cheers,
Max

-- 
Best Regards,
Massimiliano Pala, Ph.D.
OpenCA Labs Director
OpenCA Logo