Subject: Re: [Trans] Call for adoption, draft-linus-trans-gossip-ct

From: Bryan Ford <[email-masked]>
Date: Thu, 6 Aug 2015 11:17:19 +0200

Sorry for the slow followup, I wasn’t able to keep up with the lists since the IETF meeting...

> On Jul 24, 2015, at 1:09 PM, Ben Laurie <[email-masked]> wrote:
> On Thu, 23 Jul 2015 at 23:27 Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:
>> From: Melinda Shore <[email-masked] <mailto:[email-masked]>>
>> Subject: [Trans] Call for adoption, draft-linus-trans-gossip-ct
>> Date: July 23, 2015 at 2:03:24 PM GMT+2
>> To: "[email-masked] <mailto:[email-masked]>" <[email-masked] <mailto:[email-masked]>>
> 
>> 
>> Hi, all:
>> 
>> This is a call for adoption of
>> http://datatracker.ietf.org/doc/draft-linus-trans-gossip-ct/ <http://datatracker.ietf.org/doc/draft-linus-trans-gossip-ct/>
>> as a working group deliverable.  The call closes on August 6.
> 
> 
> While the draft represents a fine start at defining a gossip mechanism, I would like to express serious reservations about the draft’s basic premise that a gossip mechanism is the best approach - or even an adequate approach - “to detect misbehavior by CT logs”, to quote the draft’s self-stated purpose.  As such, I have serious reservations about the WG adopting the draft, not because there’s anything wrong with the content of the draft per se but because gossip is simply not the right approach.
> 
> First, the gossip approach creates severe privacy problems, which are already well-discussed so I won’t reiterate them.
> 
> Actually, I think you need to reiterate them, since we think that gossip as proposed does _not_ create privacy problems.

It creates new privacy problems by requiring the client (browser user) to “opt out” of web browsing privacy in order to gain any security benefit.  Either the user hands over all his browsing history to a remote “trusted auditor”, thereby opting out of privacy; or else the user remains fully vulnerable to the same kind of (potentially extended) MITM attacks that motivated CT in the first place.
 
> Second, the gossip approach can’t ensure that privacy-sensitive Web clients (who can’t or don’t want to reveal their whole browsing history to a Trusted Auditor) will ever actually be able “to detect misbehavior by CT logs”, if for example the misbehaving log’s private key is controlled by a MITM attacker between the Web client and the website the client thinks he is visiting.
> 
> The intent of CT is not to enable clients to detect such behaviour - rather, it is to enable the system as a whole to detect it.

Could you explain how “the system as a whole” detects such misbehavior in the case of the state/ISP-level MITM attacker scenario?  

As I see it, if the client/browser doesn’t opt-out of privacy by gossiping his browsing history with a trusted auditor, then the client’s *only* connection to the rest of the world, i.e., “the system as a whole”, is through the “web server”, which may well be the same kind of MITM attackers that have been known to subvert the CA system.  The client never gets to communicate to the rest of the system - i.e., the legitimate CT log servers, auditors, or monitors - and so the client never gets the opportunity to “compare notes” with the rest of the system.  And the rest of the system (the legitimate log servers, auditors, and monitors) never have the opportunity to learn from the client that the client saw a MITM-attacked, forged set of CA certs, STHs, and SCTs.

> Suppose, for example, it ever so happens that a single company ends up running both a log server and a [sub-]CA, and keeps both in the same poorly-protected safe.  If an attacker can steal those two private keys, then the attacker can silently MITM any CT-aware client all it wants, by producing all the [non-EV] certificates it needs with a valid SCT, valid STH inclusion proofs in a fake log, etc.
> 
> Chrome's policy would require the subversion of at least two logs to achieve this, but for the sake of argument, I'll concede that.

I thought you were requiring CAs to have multiple SCTs only for EV certificates, no?  What if the attacker is happy to MITM attack the user with a non-EV certificate and forego showing the user the “green bar”?  Are you assuming that users will stop using the connection if they don’t see the green bar?

Or are you saying (contrary to my prior understanding) that Chrome requires *all* CT certs to have multiple SCTs signed by different log servers?
 
>  The web client isn’t going to learn about the problem via gossip with the website because that’s the MITM attacker, and the client can’t gossip with anyone else without the serious privacy risk of trusting a single audit server with his entire browsing history.  If the “trusted audit server” is actually co-located with the client, then the audit server in turn can’t gossip with the rest of the world without creating the same privacy risk.  Even if the client does voluntarily gossip with a remote trusted audit server, the MITM attacker - e.g., an ISP-level or state-level attacker - might simply block connections to all well-known audit servers.
> 
> This attack relies on a MitM that is sustained forever but indeed would succeed. We accept that CT cannot defeat such an attack. 

But isn’t that precisely what happened in the prior COMODO and DigiNotar cases, where the MITM attacks were detected only when a few more security-conscious users compared the certificates they were seeing against what the rest of the world was seeing through nonstandard “side-channels”?  Isn’t that 

> I posted an E-mail last week suggesting an alternative approach, in which log servers would not individually sign their STHs but instead collectively sign them with the active participation of (a suitable quorum of) the auditors and/or monitors watching their logs.  But I got no response to that, so I’d like to try again.
> 
> In short: the log server would propose log entries, but the auditors and/or monitors contribute to the STH signature, only after performing at least the “auditing” function of verifying that the log server is behaving like a correct log server.  In particular, all participants could proactively verify that the log server never forks or reverts the log, never signs something syntactically invalid or with a wildly-incorrect timestamp (say +/- 24 hours), etc.  Then, even if the log server’s private key was successfully stolen by a state-level attacker (and the attacker perhaps even compromises a minority of the monitor/auditor keys), the attacker will be unable to forge an STH signature that a Web client or anyone else will believe.
> 
> This would, in effect, convert each log server from yet another juicy central attack target into a strongest-link set (I like to use the term “cothority” or collective authority) with all the monitor and auditor servers watching it and contributing to its signatures.  Of course, the attacker still wins if he successfully compromises any single CA (or sub-CA) *and* any single “logging cothority” (i.e., any log server *and* a sufficient quorum of its followers).  But doing the latter becomes way, way harder if there’s enough size and diversity in each logging cothority.
> 
> How does this improve things for the Web client in Repressistan who's getting MITM attacked?  If the client is only looking at SCTs that are individually signed by a log server (and are in any case only a “promise to log soon” and not actual evidence that the cert has been logged), then unfortunately not much: the MITM attacker can still forge at least one SCT for each of its forged certs, and no one else learns because the MITM can keep the client’s view isolated from the rest of the world.
> 
> But say we enhance CT so clients can demand STHs *with* cert inclusion proofs from the web servers they talk to - as I suggested in the meeting today, and which I believe Ben Laurie mentioned is already in the works.  Then any Web client that does this will be proactively protected from MITM attacks involving faked, forked, or otherwise bad log entries.  And the client doesn’t have to compromise its privacy by gossiping with anyone.
> 
> Two points here:
> 
> 1. Is this any different to requiring n SCTs from different logs for each certificate (other than the inclusion proof part, which I address below)?

Semantically, no different, but how large many SCTs do you think is practical to require to be attached to each cert?  Two, three?  Ten?  A hundred?  How big is each SCT?  

With the multi-SCT approach, the amount of bandwidth consumed during TLS negotiation with every CT-supporting website increases linearly with n.  With the scalable multisignature approach, n can increase to arbitrarily large size - a hundred, a thousand if needed - e.g., including all the public auditors, monitors, etc. - without any increase in the size of certificates, number of SCTs attached, or ultimately the bandwidth/latency overhead during TLS negotiation.

> 2. Our original design for CT did indeed have certs served along with an STH and an inclusion proof. Unfortunately, CAs categorically rejected this approach because of the latency it introduced in the certificate issuance process. Personally, I think it would be a better approach. Now CAs are more accepting of CT, perhaps it would be worth revisiting the question with them?

Agreed, that would be great.

Bryan

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

---

From: Ben Laurie <[email-masked]>
Date: Thu, 06 Aug 2015 12:56:34 +0000

On Thu, 6 Aug 2015 at 10:17 Bryan Ford <[email-masked]> wrote:

> On Thu, 23 Jul 2015 at 23:27 Bryan Ford <[email-masked]> wrote:
>
>> *From: *Melinda Shore <[email-masked]>
>> *Subject: **[Trans] Call for adoption, draft-linus-trans-gossip-ct*
>> *Date: *July 23, 2015 at 2:03:24 PM GMT+2
>> *To: *"[email-masked]" <[email-masked]>
>>
>>
>> Hi, all:
>>
>> http://datatracker.ietf.org/doc/draft-linus-trans-gossip-ct/
>> While the draft represents a fine start at defining a gossip mechanism, I
>> would like to express serious reservations about the draft’s basic premise
>> that a gossip mechanism is the best approach - or even an adequate approach
>> - “to detect misbehavior by CT logs”, to quote the draft’s self-stated
>> purpose.  As such, I have serious reservations about the WG adopting the
>> draft, not because there’s anything wrong with the content of the draft per
>> se but because gossip is simply not the right approach.
>>
>> First, the gossip approach creates severe privacy problems, which are
>> already well-discussed so I won’t reiterate them.
>>
>
> Actually, I think you need to reiterate them, since we think that gossip
> as proposed does _not_ create privacy problems.
>
>
> It creates new privacy problems by requiring the client (browser user) to
> “opt out” of web browsing privacy in order to gain any security benefit.
> Either the user hands over all his browsing history to a remote “trusted
> auditor”, thereby opting out of privacy; or else the user remains fully
> vulnerable to the same kind of (potentially extended) MITM attacks that
> motivated CT in the first place.
>

CT is not intended to directly prevent MitM attacks, it is intended to
detect mis-issuance of certificates. It is true that if you can
persistently isolate a client from the rest of the 'net, then you can
defeat CT.

However, I don't see why it makes any difference whether you talk to
trusted auditors (not, AIUI, expected to be the default) or to the alleged
origin server. The MITM can control both paths...

>
>
> Second, the gossip approach can’t ensure that privacy-sensitive Web
>> clients (who can’t or don’t want to reveal their whole browsing history to
>> a Trusted Auditor) will ever actually be able “to detect misbehavior by CT
>> logs”, if for example the misbehaving log’s private key is controlled by a
>> MITM attacker between the Web client and the website the client thinks he
>> is visiting.
>>
>
> The intent of CT is not to enable clients to detect such behaviour -
> rather, it is to enable the system as a whole to detect it.
>
>
> Could you explain how “the system as a whole” detects such misbehavior in
> the case of the state/ISP-level MITM attacker scenario?
>

The state or ISP must isolate all clients they attack forever to avoid
detection. In practice, this does not generally seem to be possible.

>
> As I see it, if the client/browser doesn’t opt-out of privacy by gossiping
> his browsing history with a trusted auditor, then the client’s *only*
> connection to the rest of the world, i.e., “the
>
system as a whole”, is through the “web server”, which may well be the same
> kind of MITM attackers that have been known to subvert the CA system.  The
> client never gets to communicate to the rest of the system - i.e., the
> legitimate CT log servers, auditors, or monitors - and so the client never
> gets the opportunity to “compare notes” with the rest of the system.  And
> the rest of the system (the legitimate log servers, auditors, and monitors)
> never have the opportunity to learn from the client that the client saw a
> MITM-attacked, forged set of CA certs, STHs, and SCTs.
>

This is correct, and seems to me to be correct for any system - if you can
isolate your victim forever, you can show your own view of any system.

>
> Suppose, for example, it ever so happens that a single company ends up
>> running both a log server and a [sub-]CA, and keeps both in the same
>> poorly-protected safe.  If an attacker can steal those two private keys,
>> then the attacker can silently MITM any CT-aware client all it wants, by
>> producing all the [non-EV] certificates it needs with a valid SCT, valid
>> STH inclusion proofs in a fake log, etc.
>>
>
> Chrome's policy would require the subversion of at least two logs to
> achieve this, but for the sake of argument, I'll concede that.
>
>
> I thought you were requiring CAs to have multiple SCTs only for EV
> certificates, no?  What if the attacker is happy to MITM attack the user
> with a non-EV certificate and forego showing the user the “green bar”?  Are
> you assuming that users will stop using the connection if they don’t see
> the green bar?
>

Not at all. EV certificates are our first step for CT.

>
> Or are you saying (contrary to my prior understanding) that Chrome
> requires *all* CT certs to have multiple SCTs signed by different log
> servers?
>

Chrome makes no requirement on "CT certs", only on EV certs. But in the
long run, the intention is to require CT for all certs.

>
>
>  The web client isn’t going to learn about the problem via gossip with the
>> website because that’s the MITM attacker, and the client can’t gossip with
>> anyone else without the serious privacy risk of trusting a single audit
>> server with his entire browsing history.  If the “trusted audit server” is
>> actually co-located with the client, then the audit server in turn can’t
>> gossip with the rest of the world without creating the same privacy risk.
>> Even if the client does voluntarily gossip with a remote trusted audit
>> server, the MITM attacker - e.g., an ISP-level or state-level attacker -
>> might simply block connections to all well-known audit servers.
>>
>
> This attack relies on a MitM that is sustained forever but indeed would
> succeed. We accept that CT cannot defeat such an attack.
>
>
> But isn’t that precisely what happened in the prior COMODO and DigiNotar
> cases, where the MITM attacks were detected only when a few more
> security-conscious users compared the certificates they were seeing against
> what the rest of the world was seeing through nonstandard “side-channels”?
>

Comodo: I don't know, actually.

DigiNotar: no - this was detected through pinning violations. Furthermore,
the attacker would have had to do substantially more hacking to have
managed to get something that even fooled the browser in the face of CT,
and it still would've leaked.

>  Isn’t that
>
> I posted an E-mail last week suggesting an alternative approach, in which
>> log servers would not individually sign their STHs but instead collectively
>> sign them with the active participation of (a suitable quorum of) the
>> auditors and/or monitors watching their logs.  But I got no response to
>> that, so I’d like to try again.
>>
>> In short: the log server would propose log entries, but the auditors
>> and/or monitors contribute to the STH signature, only after performing at
>> least the “auditing” function of verifying that the log server is behaving
>> like a correct log server.  In particular, all participants could
>> proactively verify that the log server never forks or reverts the log,
>> never signs something syntactically invalid or with a wildly-incorrect
>> timestamp (say +/- 24 hours), etc.  Then, even if the log server’s private
>> key was successfully stolen by a state-level attacker (and the attacker
>> perhaps even compromises a minority of the monitor/auditor keys), the
>> attacker will be unable to forge an STH signature that a Web client or
>> anyone else will believe.
>>
>> This would, in effect, convert each log server from yet another juicy
>> central attack target into a strongest-link set (I like to use the term
>> “cothority” or collective authority) with all the monitor and auditor
>> servers watching it and contributing to its signatures.  Of course, the
>> attacker still wins if he successfully compromises any single CA (or
>> sub-CA) *and* any single “logging cothority” (i.e., any log server *and* a
>> sufficient quorum of its followers).  But doing the latter becomes way, way
>> harder if there’s enough size and diversity in each logging cothority.
>>
>> How does this improve things for the Web client in Repressistan who's
>> getting MITM attacked?  If the client is only looking at SCTs that are
>> individually signed by a log server (and are in any case only a “promise to
>> log soon” and not actual evidence that the cert has been logged), then
>> unfortunately not much: the MITM attacker can still forge at least one SCT
>> for each of its forged certs, and no one else learns because the MITM can
>> keep the client’s view isolated from the rest of the world.
>>
>> But say we enhance CT so clients can demand STHs *with* cert inclusion
>> proofs from the web servers they talk to - as I suggested in the meeting
>> today, and which I believe Ben Laurie mentioned is already in the works.
>> Then any Web client that does this will be proactively protected from MITM
>> attacks involving faked, forked, or otherwise bad log entries.  And the
>> client doesn’t have to compromise its privacy by gossiping with anyone.
>>
>
> Two points here:
>
> 1. Is this any different to requiring n SCTs from different logs for each
> certificate (other than the inclusion proof part, which I address below)?
>
>
> Semantically, no different, but how large many SCTs do you think is
> practical to require to be attached to each cert?  Two, three?  Ten?  A
> hundred?  How big is each SCT?
>

44 bytes each.

>
> With the multi-SCT approach, the amount of bandwidth consumed during TLS
> negotiation with every CT-supporting website increases linearly with n.
> With the scalable multisignature approach, n can increase to arbitrarily
> large size - a hundred, a thousand if needed - e.g., including all the
> public auditors, monitors, etc. - without any increase in the size of
> certificates, number of SCTs attached, or ultimately the bandwidth/latency
> overhead during TLS negotiation.
>

To be clear, you are proposing that instead of n logs with 1 signer each,
we have 1 log with n signers?

That seems unwise to me. You then have a SPOF for the whole network.

But clearly each log could have more than one signer, but still have
multiple logs. Then the question is: where is the trade off between number
of logs and number of signers, bearing in mind that more than one signer
introduces substantial complication.

>
> 2. Our original design for CT did indeed have certs served along with an
> STH and an inclusion proof. Unfortunately, CAs categorically rejected this
> approach because of the latency it introduced in the certificate issuance
> process. Personally, I think it would be a better approach. Now CAs are
> more accepting of CT, perhaps it would be worth revisiting the question
> with them?
>
>

It would.

A more likely outcome, though, is that servers serve inclusion proofs,
which become available some (short) time after the certificate becomes
available. This does leave a window in which the inclusion proof is not
available.

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

---

From: Tom Ritter <[email-masked]>
Date: Thu, 6 Aug 2015 08:46:04 -0700

Thanks for this Bryan.  I'm going to echo Ben a bit:

> motivated CT in the first place.

If the Trusted Auditor mode is a default that requires Opting Out
instead of Opting In I think I speak for every author when I say we
will have considered this a huge failure and will rally against it as
much as we can.

> connection to the rest of the world, i.e., “the system as a whole”, is
> through the “web server”, which may well be the same kind of MITM attackers
> that have been known to subvert the CA system.  The client never gets to
> communicate to the rest of the system - i.e., the legitimate CT log servers,
> auditors, or monitors - and so the client never gets the opportunity to
> “compare notes” with the rest of the system.  And the rest of the system
> (the legitimate log servers, auditors, and monitors) never have the
> opportunity to learn from the client that the client saw a MITM-attacked,
> forged set of CA certs, STHs, and SCTs.

In SCT Feedback the only connection to disclose data about Website A
is indeed website A.
In STH Feedback, assuming the client can resolve a Cert to a STH via
an inclusion proof (which we currently suggest via DNS, but other
mechanisms can exist, such as Tor) - that STH will be pollinated to
_any_ website.  And the split-view log will be caught. So that's how
the 'system as a whole' detects the issue.

The difference is of course because the SCT is private data that
reveals browsing history, the STH is not (not counting old-STH attacks
which we mitigate).

If an attacker can both persistently MITM someone to a website (or the
whole internet) and DoS the STH lookup mechanism (and compromise a log
and a CA) - yes, the attacker wins.

Attackers who can persistently MITM users forever are extremely
powerful and we have no way to defend against them except to make all
your client software just stop working.  This applies to the CA system
absent CT, it requires to the CA system with CT, and it applies to
software updates.  If you can write exploits, but not find bugs - just
wait for a patch to come out, block the update, take your leisurely
time reverse engineering, writing the exploit, and using it.

I don't mean to dismiss this concern, but a) I don't believe SCT
Feedback and STH Pollination cause privacy problems b) This problem is
so hard that no one is attempting to defend against it c) History
suggests such attackers are not all-powerful.  Or at least, we've
caught a lot of folks who could have gotten away with it that
supposedly had that capability and could have known better.

> Or are you saying (contrary to my prior understanding) that Chrome requires
> *all* CT certs to have multiple SCTs signed by different log servers?

As Ben said, the end goal is to use it for everything.  I don't know
when we'll get there, but in the interim there will probably be a
period of opt-in:
https://ritter.vg/blog-require_certificate_transparency.html

> what the rest of the world was seeing through nonstandard “side-channels”?

http://wiki.cacert.org/Risk/History and my recollection indicates
DigiNotar - Chrome Pinning google.com
TurkTrust - Chrome Pinning google.com
ANSSI - Chrome Pinning google.com
India CCA - Chrome Pinning google.com
CNNIC - that website indicates it was CT that caught it, but I think
that's a misunderstanding it was again Chrome Pinning google.com

The Comodo incident you reference, was that the mozilla.com cert in
2008?  That was someone just trying a RA portal and getting a cert:
http://www.theregister.co.uk/2008/12/29/ca_mozzilla_cert_snaf/

Despite all the effort to find such certs manually, via MEKAI,
Perspectives, Convergence, Cert Patrol, and others - I'm not aware of
anyone ever catching a CA-signed misissued cert manually.

> overhead during TLS negotiation.

While we aim to keep SCTs small as Ben indicated - yes, sending 10
would be quite a bit.  I'm not sure of a great answer here.. I think
the onus is kind of on the community to curate and run a fewer number
of high-quality, mutually distrusting, different-juristictional logs.

> 2. Our original design for CT did indeed have certs served along with an STH
> and an inclusion proof. Unfortunately, CAs categorically rejected this
> process. Personally, I think it would be a better approach. Now CAs are more
> accepting of CT, perhaps it would be worth revisiting the question with
> them?
>
>

I am most excited about the prospect of sending an inclusion proof to
a recent STH to the client - but I don't actually think the cert is
the answer. I think it's a TLS extension or (better) an OCSP staple.
Doing this would eliminate what I think is the weakest part of the
gossip document - the requirement to obtain a STH from a SCT (well a
cert) via some 'privacy preserving manner'.  (Which we, again,
theorize to be DNS, but I don't think that's the answer for everyone.)

If the STH was included in the Cert, that doesn't really change the game for me.
1) The STH could be a STH on the split view of the log, so the
immediate-decision security is no better that just sending a SCT.
2) The STH is too old. I don't want clients pollinate old STHs,
because as time goes on, old STHs will be rarer and will be indicative
of what website you visited. After 2.5 years there will only be 100?
1000? popular websites with that STH in the cert. So the old STH needs
to be resolved to a recent STH, and you pollinate _that_.

-tom

---

From: Bryan Ford <[email-masked]>
Date: Sat, 8 Aug 2015 12:56:50 -0400

Hi Tom,

> On Aug 6, 2015, at 11:46 AM, Tom Ritter <[email-masked]> wrote:
> 

Agreed.  With that in mind, would it be reasonable to include text to this effect in the “gossip” draft if it is adopted?  For example, “Implementations of CT must ensure that Trusted Auditor relationships are ‘opt-in’ relationships require the explicit consent of the user, and not a bundled system default” or something like that?

> the 'system as a whole' detects the issue.

OK, I see how STH pollination can at least raise the bar significantly for MITM attackers in a way that SCT feedback can’t.  But it still seems neither sufficient, nor the best we can do, nor convincingly “safe” in terms of privacy; see below.

> reveals browsing history, the STH is not (not counting old-STH attacks

I see there is already some text in the gossip draft acknowledging the privacy risks that “promiscuous” STH pollination, but the current text doesn’t go far enough and underestimates the risk.  For example, by the calculations in the text, suppose a malicious HTTPS server has up to 336 unique STHs per log that it could use to “tag” and track clients over time.  Supposing there are 10 well-known log servers, this is 3360 unique STHs total.  The current text seems to suggest that this is “small enough”, which may be true in the one particular attack the text suggests earlier, namely that the attacker picks one particular less-popular (e.g., somewhat-old) STH to give a client it wishes to track.  

But this is not the “real” attack of interest: a just slightly smarter attacker would probably use the presence or absence of these less-popular STHs in a client’s gossip cache as (noisy) bits in a tracking identifier.  The attacker would gossip to each client it hasn’t seen before some kind of ECC-encoded pattern of less-popular STHs.  Thus, the 3360 unique STHs the attacker gets to play with do not represents “the number of clients the attacker can track” as the current text seems to suggest, but rather the 3360 unique STHs may in fact be “tracking tag bits” that the attacker gets to play with in attempting to imprint clients with tracking tags via gossip.  And 3360 bits is a lot of bits: plenty of room for a highly-unique (say 64-bit) per-client tag to be encoded in a high-expansion, rather noise-tolerant encoding.

Of course, a user could still avoid being tracked in this fashion by using a stateless, “amnesiac” browsing platform like Tails, which would presumably start with an empty STH cache on each boot.  But this would also defeat CT’s ability to use STH polination to detect MITM attacks across client/browser sessions.

> your client software just stop working.

Attackers who can persistently MITM users forever are indeed extremely powerful but are not at all unrealistic, given the increasing presence of Great Firewall type attackers (and all the smaller wanna-be knockoffs), which can indeed persistently control the “networked view of the world” seen by any user who cannot or does not regularly travel internationally.

I disagree that we have no way to defend against them; if you think so you’re giving up too quickly.  Of course such an attacker can simply block or DoS all the user’s communication in any case, but in practice most of these attackers would rather let the client think they’re communicating securely while silently compromising them.  CT with gossip cannot even guarantee that such silent, persistent MITM attacks will ever even be detected (by anyone), let alone prevented.  But the multi-signed STH approach I suggested would do exactly that.  Since the pervasive MITM attacker would be unable to forge a single valid STH signature the client will accept without compromising a large quorum of monitor/witness/co-signer servers as well, the attacker is left with the choice of remaining silent and leaving the client’s communication uncompromised, or denying/blocking the communication entirely.  I claim that such a situation would be much, much preferable to the current state of affairs even with CT deployed.

> This applies to the CA system

Of course client-side software security is a huge and important problem in itself, but it’s orthogonal to the design of CT.  I have plenty of thoughts on how multi-signing or cothorities could be used to improve the situation there as well, but that’s another topic.

> Feedback and STH Pollination cause privacy problems

See above.

> b) This problem is
> so hard that no one is attempting to defend against it

I am; see above.

> c) History
> suggests such attackers are not all-powerful.  

Agreed, such attackers are not all-powerful, but pretty much any compromised or state-controlled ISP is certainly powerful enough to persistently MITM any client that always connects through that ISP - which is true at least of (a) desktop machines on a home or work network always attached via the same connection, and (b) smartphones roaming within a country but always using a data plan through the same cellular ISP.  These threat models do not seem unrealistic to me, but rather quite ubiquitous.

> Or at least, we've

Yes, a lot of current attackers have been sloppy in one way or another, but that doesn’t mean we should assume the they will not learn from their past mistakes and adopt less sloppy attacks in the future.  They will.

> As Ben said, the end goal is to use it for everything.

What is the “it” to be used for everything?  CT?  Or CT with a mandatory minimum of >1 SCTs?  And again, what do you think a reasonable mandatory minimum number of SCTs would be?  Two, five, ten, 100?  If it starts at 1 or 2 for pragmatic reasons, will it ever increase or will it stay forever at 2 due to inertia?  Is that good enough?

> I don't know
> https://ritter.vg/blog-require_certificate_transparency.html <https://ritter.vg/blog-require_certificate_transparency.html>

Nice blog post, but I don’t see where it addresses the issue of how many independent SCTs a browser should expect/require a cert to have even if it does decide to demand CT support.

> http://www.theregister.co.uk/2008/12/29/ca_mozzilla_cert_snaf/ <http://www.theregister.co.uk/2008/12/29/ca_mozzilla_cert_snaf/>

> anyone ever catching a CA-signed misissued cert manually.

I think it was the March 2011 incident, where a hacker was able to obtain fraudulent certificates through Comodo and then apparently attempted to use at least one of them, for ‘login.yahoo.com’, in some way: https://www.comodo.com/Comodo-Fraud-Incident-2011-03-23.html <https://www.comodo.com/Comodo-Fraud-Incident-2011-03-23.html>  Comodo’s report and the other information I found don’t make it clear exactly in what way the login.yahoo.com <http://login.yahoo.com/> cert was “seen live on the Internet” - perhaps it was Google pinning as well if Google was pinning Yahoo’s certs at that time (were they?), or perhaps it was manual forensics.  Perhaps you or someone else has better information about this.  But this is all incidental: it’s great that Google pinning has caught a lot of incidents, but nobody seems to be saying that means Google pinning is the best/final solution.

> of high-quality, mutually distrusting, different-juristictional logs.

This is precisely my point: by architecturally relying on multiple SCTs per cert we’re tying ourselves into the same bad old security tradeoff of having to trust a few “high-quality, mutually distrusting, different-jurisdictional logs” - i.e., a few conventional centralized authorities.  How do you choose them?  Who chooses them?  Do you let one of those 10 be run by (say) Iran or Syria, in the interest of diversity (at least they’re probably not colluding with the Five Eyes countries!) - even though their governments have a record of trying to MITM their users (https://www.eff.org/deeplinks/2011/03/iranian-hackers-obtain-fraudulent-https <https://www.eff.org/deeplinks/2011/03/iranian-hackers-obtain-fraudulent-https>, https://www.eff.org/deeplinks/2011/05/syrian-man-middle-against-facebook <https://www.eff.org/deeplinks/2011/05/syrian-man-middle-against-facebook>) and can probably be expected to try to exploit their control over “their” log server in any way the CT architecture allows them to (such as persistent MITM attacks as discussed above)?

With the scalable multi signing, in contrast, we could have 10 or 100 or 1000 monitor/co-signer servers contributing to each STH signature with *no* cost to client verification time, client CPU costs, TLS startup bandwidth consumed, etc.  One quite reasonable policy might be that *every* country that is technically capable of running a monitor/co-signer server could join and participate in the signing process of every STH of every well-known log.  If you’re claiming that it’s infeasible to decentralize trust in such a service beyond 10 or so well-known nodes, again I think you’re just giving up and conceding the field too quickly.

> theorize to be DNS, but I don't think that's the answer for everyone.)

Agreed on this.  In fact, it’s increasingly unclear to me what security purpose SCTs actually serve if it indeed ends up that the “real” security CT provides is eventually going to revolve mainly around STHs and inclusion proofs.  Out of curiosity, has anyone floated or elaborated on the idea of what CT would look like if simplified not to rely on SCTs at all?

> to be resolved to a recent STH, and you pollinate _that_.

Agreed again.

B

---

From: Bryan Ford <[email-masked]>
Date: Sat, 8 Aug 2015 13:25:41 -0400

On Aug 6, 2015, at 8:56 AM, Ben Laurie <[email-masked]> wrote:
> On Thu, 6 Aug 2015 at 10:17 Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:
>> On Jul 24, 2015, at 1:09 PM, Ben Laurie <[email-masked] <mailto:[email-masked]>> wrote:
> The state or ISP must isolate all clients they attack forever to avoid detection. In practice, this does not generally seem to be possible.
>  
> As I see it, if the client/browser doesn’t opt-out of privacy by gossiping his browsing history with a trusted auditor, then the client’s *only* connection to the rest of the world, i.e., “the 
> system as a whole”, is through the “web server”, which may well be the same kind of MITM attackers that have been known to subvert the CA system.  The client never gets to communicate to the rest of the system - i.e., the legitimate CT log servers, auditors, or monitors - and so the client never gets the opportunity to “compare notes” with the rest of the system.  And the rest of the system (the legitimate log servers, auditors, and monitors) never have the opportunity to learn from the client that the client saw a MITM-attacked, forged set of CA certs, STHs, and SCTs.
> 
> This is correct, and seems to me to be correct for any system - if you can isolate your victim forever, you can show your own view of any system.

To reiterate the key point I made in my response to Tom’s E-mail, this is not true of the multisignature-based STH signing I suggested.  Suppose for each CT log server there are (for example) 100 monitor servers widely distributed around the world, run by diverse companies, governments, etc.  And suppose that any STH must be collectively signed by the log server and at least 51 of its monitor servers in order for clients to consider it valid.  Assume the victim user/browser is isolated behind a MITM attacker (call it Repressistan) who controls all the paths in and out of Repressistan and never lets the user physically enter or leave Repressistan.  Thus the user never has opportunity to do CT gossip via any path not controlled by the Repressistani Firewall.  In CT’s current design, Repressistan wins - gaining the ability to silently compromise the user forever - simply by Pwning one CA key and one log server key.  (Or maybe two if you require two SCTs per cert.)  

In the multisignature approach, Repressistan gains the ability to forge a STH for a “client-customized world view" only if Repressistan can also compromise more than 50 monitors of a compromised log server’s collective signing pool.  Every valid, client-verifiable STH signature ensures to the client not only that the log server’s key signed the STH but also that at least 51 monitor servers also witnessed it (even if those monitors are doing no checking at all other than saying “I saw it”).  Repressistan can no longer forge a valid (above-threshold) STH signature without an inconceivably massive collusion or security breach.  Repressistan still simply prevent the user from communicating at all, of course, but loses the ability either to silently compromise the connection or silently evade detection.  And the client need not risk its privacy via gossip in any way to receive this protection.

> Chrome makes no requirement on "CT certs", only on EV certs. But in the long run, the intention is to require CT for all certs.

But what does “requiring CT” mean in terms of the number of SCTs a given cert (EV or non-EV) will be “required” to have?  What do you see as reasonable numbers there, for the near term and long term?

> To be clear, you are proposing that instead of n logs with 1 signer each, we have 1 log with n signers?

Possibly but not necessarily.  I envision n logs with m signers each, where say 1 <= n <= 10, but 10 <= m <= 1000.  (And different log servers need not have the same signers, or even the same number of signers.)

> That seems unwise to me. You then have a SPOF for the whole network.

If a single log server cannot sign anything without it being witnessed and validated by 10, 100, or 1000 signers, how is it a SPOF?  Again, I’m not saying n should be 1 - there are good reasons we might still want n to be greater than 1.  But if each log server can’t produce a valid STH without the active participation of a quorum of its m signers, and a reasonable number of those co-signers at least do minimal checking to ensure that the log server is behaving like a log (e.g., never signing two STHs with the same sequence number), then there’s a lot less a misbehaving log server - or an attacker who compromises that log server’s key - can do with it.

> But clearly each log could have more than one signer, but still have multiple logs. Then the question is: where is the trade off between number of logs and number of signers, bearing in mind that more than one signer introduces substantial complication.

As I pointed out before, the problem with the current model is that adding log servers *decreases* security, at least in certain realistic attack scenarios, by giving the attacker more possible log server targets to compromise.  Weakest-link security, just as in the current CA system.  Whereas increasing m, the number of signers per log server, can only increase security, assuming the multi-signing protocol/crypto itself isn’t broken.

B

---

From: Ben Laurie <[email-masked]>
Date: Mon, 10 Aug 2015 10:28:05 +0000

On Sat, 8 Aug 2015 at 17:56 Bryan Ford <[email-masked]> wrote:

> Agreed.  With that in mind, would it be reasonable to include text to this
> effect in the “gossip” draft if it is adopted?  For example,
> “Implementations of CT must ensure that Trusted Auditor relationships are
> ‘opt-in’ relationships require the explicit consent of the user, and not a
> bundled system default” or something like that?
>

We already decided for the main CT I-D that client behaviour of this kind
is out of scope.

Also, as previously mentioned, not all clients have privacy concerns (or
users, necessarily).

> OK, I see how STH pollination can at least raise the bar significantly for
> MITM attackers in a way that SCT feedback can’t.  But it still seems
> neither sufficient, nor the best we can do, nor convincingly “safe” in
> terms of privacy; see below.
>
> I see there is already some text in the gossip draft acknowledging the
> privacy risks that “promiscuous” STH pollination, but the current text
> doesn’t go far enough and underestimates the risk.  For example, by the
> calculations in the text, suppose a malicious HTTPS server has up to 336
> unique STHs per log that it could use to “tag” and track clients over
> time.  Supposing there are 10 well-known log servers, this is 3360 unique
> STHs total.  The current text seems to suggest that this is “small enough”,
> which may be true in the one particular attack the text suggests earlier,
> namely that the attacker picks one particular less-popular (e.g.,
> somewhat-old) STH to give a client it wishes to track.
>

How does it then track it? Also, the client then either reconciles the STH
with a newer one (or perhaps already has done so) and discards it, or it
gossips it, meaning other clients will start mentioning this "rare" STH.

> But this is not the “real” attack of interest: a just slightly smarter
> attacker would probably use the presence or absence of these less-popular
> STHs in a client’s gossip cache as (noisy) bits in a tracking identifier.
> The attacker would gossip to each client it hasn’t seen before some kind of
> ECC-encoded pattern of less-popular STHs.  Thus, the 3360 unique STHs the
> attacker gets to play with do not represents “the number of clients the
> attacker can track” as the current text seems to suggest, but rather the
> 3360 unique STHs may in fact be “tracking tag bits” that the attacker gets
> to play with in attempting to imprint clients with tracking tags via
> gossip.  And 3360 bits is a lot of bits: plenty of room for a highly-unique
> (say 64-bit) per-client tag to be encoded in a high-expansion, rather
> noise-tolerant encoding.
>

I'd be interested to see how this kind of attack would actually work out in
practice, especially given there are some relatively simple countermeasures.

a) Cache old STHs so they can be dropped immediately.

b) Always attempt to reconcile received STHs before gossiping them.

>
> Of course, a user could still avoid being tracked in this fashion by using
> a stateless, “amnesiac” browsing platform like Tails, which would
> presumably start with an empty STH cache on each boot.  But this would also
> defeat CT’s ability to use STH polination to detect MITM attacks across
> client/browser sessions.
>

I don't think that's correct. Detection can be done by any participant, so
all that is needed is for the browser to gossip at least once.

> Attackers who can persistently MITM users forever are indeed extremely
> powerful but are not at all unrealistic, given the increasing presence of
> Great Firewall type attackers (and all the smaller wanna-be knockoffs),
> which can indeed persistently control the “networked view of the world”
> seen by any user who cannot or does not regularly travel internationally.
>

That doesn't seem to be the case, in practice.

>
> I disagree that we have no way to defend against them; if you think so
> you’re giving up too quickly.  Of course such an attacker can simply block
> or DoS all the user’s communication in any case, but in practice most of
> these attackers would rather let the client think they’re communicating
> securely while silently compromising them.  CT with gossip cannot even
> guarantee that such silent, persistent MITM attacks will ever even be
> detected (by anyone), let alone prevented.  But the multi-signed STH
> approach I suggested would do exactly that.
>

I don't see how - both are numbers games. There's nothing in multi-signing
that provides strong guarantees, just statistical ones.

>  Since the pervasive MITM attacker would be unable to forge a single valid
> STH signature the client will accept without compromising a large quorum of
> monitor/witness/co-signer servers as well, the attacker is left with the
> choice of remaining silent and leaving the client’s communication
> uncompromised, or denying/blocking the communication entirely.  I claim
> that such a situation would be much, much preferable to the current state
> of affairs even with CT deployed.
>

If we tone down your rhetoric to admit the fallibility of your scheme, then
in principle I think its worth exploring, but:

a) We still need gossip,

b) There are architectural issues I mention in my previous email that need
resolving.

> Of course client-side software security is a huge and important problem in
> itself, but it’s orthogonal to the design of CT.  I have plenty of thoughts
> on how multi-signing or cothorities could be used to improve the situation
> there as well, but that’s another topic.
>
> Agreed, such attackers are not all-powerful, but pretty much any
> compromised or state-controlled ISP is certainly powerful enough to
> persistently MITM any client that always connects through that ISP
>

Eh? You have to also compromise a CA and some logs, as well as own the ISP.
And you have to MITM all protocols (I am assuming that over time gossip
will be a multi-protocol thing).

> - which is true at least of (a) desktop machines on a home or work network
> always attached via the same connection, and (b) smartphones roaming within
> a country but always using a data plan through the same cellular ISP.
> These threat models do not seem unrealistic to me, but rather quite
> ubiquitous.
>
> Or at least, we've
> Yes, a lot of current attackers have been sloppy in one way or another,
> but that doesn’t mean we should assume the they will not learn from their
> past mistakes and adopt less sloppy attacks in the future.  They will.
>
> What is the “it” to be used for everything?  CT?  Or CT with a mandatory
> minimum of >1 SCTs?  And again, what do you think a reasonable mandatory
> minimum number of SCTs would be?  Two, five, ten, 100?  If it starts at 1
> or 2 for pragmatic reasons, will it ever increase or will it stay forever
> at 2 due to inertia?  Is that good enough?
>
> I don't know
> Nice blog post, but I don’t see where it addresses the issue of how many
> independent SCTs a browser should expect/require a cert to have even if it
> does decide to demand CT support.
>
> I think it was the March 2011 incident, where a hacker was able to obtain
> fraudulent certificates through Comodo and then apparently attempted to use
> at least one of them, for ‘login.yahoo.com’, in some way:
> https://www.comodo.com/Comodo-Fraud-Incident-2011-03-23.html  Comodo’s
> report and the other information I found don’t make it clear exactly in
> what way the login.yahoo.com cert was “seen live on the Internet” -
> perhaps it was Google pinning as well if Google was pinning Yahoo’s certs
> at that time (were they?), or perhaps it was manual forensics.  Perhaps you
> or someone else has better information about this.  But this is all
> incidental: it’s great that Google pinning has caught a lot of incidents,
> but nobody seems to be saying that means Google pinning is the best/final
> solution.
>

In this case, though, CT would have caught the mis-issue.

> This is precisely my point: by architecturally relying on multiple SCTs
> per cert we’re tying ourselves into the same bad old security tradeoff of
> having to trust a few “high-quality, mutually distrusting,
> different-jurisdictional logs” - i.e., a few conventional centralized
> authorities.  How do you choose them?  Who chooses them?  Do you let one of
> those 10 be run by (say) Iran or Syria, in the interest of diversity (at
> least they’re probably not colluding with the Five Eyes countries!) - even
> though their governments have a record of trying to MITM their users (
> https://www.eff.org/deeplinks/2011/03/iranian-hackers-obtain-fraudulent-https,
> https://www.eff.org/deeplinks/2011/05/syrian-man-middle-against-facebook)
> and can probably be expected to try to exploit their control over “their”
> log server in any way the CT architecture allows them to (such as
> persistent MITM attacks as discussed above)?
>

Now you seem to be claiming that it is possible to persistently MITM an
entire nation. I find that difficult to swallow.

>
> With the scalable multi signing, in contrast, we could have 10 or 100 or
> 1000 monitor/co-signer servers contributing to each STH signature with *no*
> cost to client verification time, client CPU costs, TLS startup bandwidth
> consumed, etc.  One quite reasonable policy might be that *every* country
> that is technically capable of running a monitor/co-signer server could
> join and participate in the signing process of every STH of every
> well-known log.  If you’re claiming that it’s infeasible to decentralize
> trust in such a service beyond 10 or so well-known nodes, again I think
> you’re just giving up and conceding the field too quickly.
>
> STH
> more
> Agreed on this.  In fact, it’s increasingly unclear to me what security
> purpose SCTs actually serve if it indeed ends up that the “real” security
> CT provides is eventually going to revolve mainly around STHs and inclusion
> proofs.  Out of curiosity, has anyone floated or elaborated on the idea of
> what CT would look like if simplified not to rely on SCTs at all?
>

I believe I already mentioned that the original plan was to use inclusion
proofs, not SCTs. CAs did not like the consequent delay in certificate
issuance.

---

From: Rob Stradling <[email-masked]>
Date: Mon, 10 Aug 2015 22:05:34 +0100

On 10/08/15 11:28, Ben Laurie wrote:
>
> On Sat, 8 Aug 2015 at 17:56 Bryan Ford <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     Hi Tom,
>
>>     On Aug 6, 2015, at 11:46 AM, Tom Ritter <[email-masked]
>>     <mailto:[email-masked]>> wrote:
<snip>
>>     The Comodo incident you reference, was that the mozilla.com
>>     <http://mozilla.com> cert in
>     I think it was the March 2011 incident, where a hacker was able to
>     obtain fraudulent certificates through Comodo and then apparently
>     attempted to use at least one of them, for ‘login.yahoo.com
>     <http://login.yahoo.com>’, in some way:
>     https://www.comodo.com/Comodo-Fraud-Incident-2011-03-23.html
>     Comodo’s report and the other information I found don’t make it
>     clear exactly in what way the login.yahoo.com
>     <http://login.yahoo.com> cert was “seen live on the Internet” -
>     perhaps it was Google pinning as well if Google was pinning Yahoo’s
>     certs at that time (were they?), or perhaps it was manual
>     forensics.  Perhaps you or someone else has better information about
>     this.  But this is all incidental: it’s great that Google pinning
>     has caught a lot of incidents, but nobody seems to be saying that
>     means Google pinning is the best/final solution.
>
>

Had we (Comodo) been submitting all certs to CT logs at that time, then 
yes, CT would have caught these mis-issues.

Had Chrome been doing certificate pinning at that time (which I don't 
think it was, given that 
https://www.imperialviolet.org/2011/05/04/pinning.html is dated a couple 
of months later), it would have caught these mis-issues too, if any 
Chrome users had actually been exposed to any of these certs "live on 
the Internet".

The "seen live on the Internet" claim: Within a few hours of us noticing 
the mis-issuances, we'd analyzed our webserver logs looking for activity 
on the compromised account and we'd spotted some IP addresses allocated 
to Iran.  One of my colleagues did a port 443 scan across the relevant 
IP subnets and found a server that was sending that login.yahoo.com 
cert.  IIRC, that server wasn't up for long.

Incidentally, this is pretty fair summary of the incident:
https://www.chromium.org/Home/chromium-security/root-ca-policy
"In March of 2011, Comodo issued fraudulent certs for a number of 
well-known internet sites including Microsoft, Yahoo and Google. This 
was not due to a compromise at Comodo, but rather at an authorized 
Registration Authority operating on Comodo’s behalf. In that case, 
Comodo immediately spotted the mis-issuance, revoked the certificates, 
notified the affected parties, and made a full and public disclosure of 
what had happened, albeit a week after the event. While the compromise 
itself cannot be minimized, Comodo mostly acted in a manner consistent 
with the trust placed in them as a Root CA (earlier disclosure would 
have been better)."

My one complaint is the "mostly...earlier disclosure would have been 
better" part.  We wanted to disclose ASAP, but one of the browser 
providers said they needed 9 days to produce and test patches.  That may 
sound implausible now, but remember that this was before any of the 
browsers had introduced their certificate blacklisting mechanisms (i.e. 
Google's CRLSets, Microsoft's disallowed.stl, etc).

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Tom Ritter <[email-masked]>
Date: Wed, 12 Aug 2015 19:34:31 -0500

On 8 August 2015 at 12:25, Bryan Ford <[email-masked]> wrote:
> [Many good things]

Okay.  If I simplify unfairly I think I agree with many of the root
points of your email.

1) Yes, more logs plus even a weeks worth of STHs probably affords too
much ability for tracking. Releasing a STH will have some sort of
probability attached to it, but again 'statistics'[0]. I've open a
ticket to make sure we don't lose this.

2) Yes, a multi-signer log is more resistant to attack than a
single-signer log. I would note there's nothing that would stop
someone from running a multi-signer log using distributed signing; and
if you can work out the practicalities, your log would probably be
seen as one of the more trustworthy ones. I'm doubtful of the
likelihood of converting existing logs into this model, but since CT
can evolve over time, and logs can be removed/added, there's no reason
it can't be a long-term goal.

-tom

[0] I think there will be a revival (or at least a re-visit) of the
research done for pooling strategies in remailers. There was a paper
that summed up all the different pooling strategies. Don't remember
the name, but I know it's on http://www.freehaven.net/anonbib/

---

From: Rob Stradling <[email-masked]>
Date: Fri, 14 Aug 2015 15:57:44 +0100

<snip>
>> Out of curiosity, has anyone floated or elaborated on the idea of what
>> CT would look like if simplified not to rely on SCTs at all?
>
> I believe I already mentioned that the original plan was to use
> inclusion proofs, not SCTs. CAs did not like the consequent delay in
> certificate issuance.

Gossip seeks to strengthen CT, whereas the following idea proposes a 
weaker form of CT that could be much easier to deploy in the short-term. 
  This could form part of an incremental deployment strategy towards 
"full" CT.

PROBLEM

The long-term goal is for TLS clients to be able to abort TLS handshakes 
if an insufficient number of valid SCTs (or inclusion proofs - see TRAC 
ticket #10) are provided.  To achieve this goal, we will need the vast 
majority of the TLS servers on the planet to be upgraded and/or the vast 
majority of the CAs on the planet to embed SCTs in certs and/or OCSP 
responses.

This could take years!  While we wait...

IDEA

When a TLS server sends a cert accompanied by zero SCTs / inclusion 
proofs, let the TLS client attempt to fetch and verify an inclusion 
proof (from each known log?) for each certificate encountered.
(This would require a new log API for looking up an inclusion proof by 
certificate hash).
There are 3 possible outcomes:
1. If the TLS client obtains a valid inclusion proof, then all is well.
2. If the TLS client can't obtain any responses from any logs, it should 
act as if all is well (i.e. soft-fail).
3. If the TLS client receives responses from at least 1(?) log, 
indicating that there are zero inclusion proofs for the cert in 
question, it should flag the cert (to the browser vendor?) as 
potentially not logged.

TLS clients could start behaving this way sooner rather than later, 
since the only prerequisite is that each cert must be logged.  (And of 
course adding a cert to a log is something that can be done by the CA, 
the domain owner, or indeed anyone else that encounters the cert).

If CAs are required (by browser root inclusion policies) to log all 
certs they issue, then any evidence of certs not being logged would 
prove CA misbehaviour.

Ideally the "there are zero inclusion proofs for this cert" response 
from the log would be signed by the log, so that it's possible for 
anyone who has a valid and sufficiently old SCT for that cert to prove 
log misbehaviour.

If there are a large number of logs, it might be impractical for TLS 
clients to try to fetch inclusion proofs from all of them, so there 
might need to be some sort of mechanism for figuring out which subset of 
logs should be checked.

No doubt there are rough edges in this initial proposal, but is this 
idea worth pursuing?

Or do folks feel that pursuing this idea would be too much of a 
distraction, and that we should instead focus on the long-term goal of 
getting "full" CT specified and deployed?

---

From: Ben Laurie <[email-masked]>
Date: Tue, 25 Aug 2015 08:56:04 +0000

> ticket to make sure we don't lose this.

I've been thinking about this for a while now, and I'd like to know how
this attack works.

When a client communicates with a log, assuming it manages to do so
completely anonymously, it reveals at most two STHs it knows (i.e. if it
asks for an STH consistency proof).

A week's worth of STHs gives me ~10,000 pairs. Assuming, say, 1B people who
visit sites using CT in that week, that puts each person into an anonymity
set of size 100,000, assuming the attacker has full control over STHs the
user caches. Which he doesn't.

Also, once the attacker has narrowed the user to this set, what has he
learnt? Nothing, since he already knew the 2 STHs the user had cached (he
supplied them). Those two STHs are correlated with nothing else. What's
more, one of them is now going to be removed from the cache (the older
one), moving the user into a  really large anonymity set. In practice, the
user will soon replace that STH with a more recent one, and different users
will replace with different STHs, causing the set to become even larger
over time. Anyway, now you can determine that one of at least 10M people
visited some particular website. I find it hard to get excited about that.

In order to further narrow the user down, or to learn anything correlated
with the smaller (two STH) anonymity set, the attacker needs some other
persistent marker so he can correlate other requests. But if he has that
persistent marker, what is the STH marker for?

In short: I am not seeing how this represents a privacy problem. Perhaps
I'm missing something?