Subject: [Trans] Usage of Private Information Retrieval (PIR) in CT?

From: Matt Palmer <[email-masked]>
Date: Wed, 9 Sep 2015 05:49:10 +1000

Hi everyone,

As part of my research into another project, I came across the concept of
Private Information Retrieval (PIR).  From the Wikipedia page
(https://en.wikipedia.org/wiki/Private_Information_Retrieval):

> In cryptography, a private information retrieval (PIR) protocol allows a
> user to retrieve an item from a server in possession of a database without
> revealing which item is retrieved.

This sounds like rather a nice property to have for clients to retrieve
proofs from CT logs without needing to actually disclose which site they're
retrieving the proof *for*, which, as I understand it, is an unsolved
privacy-related problem in CT.  It *may* also be possible to use similar
concepts to improve privacy in gossip, although I'm far from certain on that
point.

My questions for those who have been working on the core CT specs are:

* Has PIR been investigated previously with regards to addressing any
  privacy concerns in CT?

* If so, in what ways were they considered lacking?

* If not, would a proposal to include PIR methods in CT be welcomed?

* In what way would a PIR-related proposal best be formulated, at this stage
  of the standardisation process?  As an inclusion in 6962bis, or as a
  separate proposed RFC?

I'm not committing to working with PIR and CT *yet*, but depending on the
answers to the above questions and my time availability, that lack of
commitment may change.

- Matt

---

From: Linus Nordberg <[email-masked]>
Date: Tue, 08 Sep 2015 22:17:27 +0200

Matt Palmer <[email-masked]> wrote
Wed, 9 Sep 2015 05:49:10 +1000:

| This sounds like rather a nice property to have for clients to retrieve
| proofs from CT logs without needing to actually disclose which site they're
| retrieving the proof *for*, which, as I understand it, is an unsolved
| privacy-related problem in CT.  It *may* also be possible to use similar
| concepts to improve privacy in gossip, although I'm far from certain on that
| point.

I think PIR is very interesting for CT. I'd like to point out [0] by
Devet and Goldberg, describing a hybrid PIR protocol which might be
useful.

[0] https://www.petsymposium.org/2014/papers/Devet.pdf

---

From: Adam Eijdenberg <[email-masked]>
Date: Tue, 08 Sep 2015 20:54:59 +0000

On Tue, Sep 8, 2015 at 12:49 PM Matt Palmer <[email-masked]> wrote:

> privacy-related problem in CT.

Hi Matt,

Here's what we (Google) are currently planning to do with relation to
performing inclusion proof checks in a privacy preserving manner from
Chrome:

"Google is planning to launch a set of DNS servers to be able to handle
inclusion proof checking over DNS. The primary motivation for doing so is
so that a client (such as Chrome, or other browsers that wish to use this)
can perform inclusion proof checks without directly revealing the browsing
history of the user to any new parties, including Google. The intent is
that the client will receive an inclusion proof by performing a DNS lookup
for a TXT record for a specially crafted hostname, via the user’s existing
DNS resolver (typically an ISP) which in turn will recurse to eventually
service the request from a Google DNS server.  In this manner the client is
only revealing the leaf hashes they see (and thus the sites they visit) to
their existing DNS resolver, which already (in practically all cases) has
just serviced a DNS request for that same site and thus already knows their
browsing history."
"Google is building out log mirrors for all logs included by Chrome, and
the intent is that read-only requests from Chrome (for STHes, or
inclusion-proofs (via the DNS mechanism above)) will be serviced by a log
mirror, rather than the underlying logs."
(from http://www.certificate-transparency.org/august-2015-newsletter)

We'd also be quite open to exploring other ideas, though the above is what
we're currently planning/started building out (and won't require additional
work by log operators).

Cheers, Adam

> It *may* also be possible to use similar
> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>

---

From: Rob Stradling <[email-masked]>
Date: Wed, 9 Sep 2015 10:53:19 +0100

On 08/09/15 21:54, Adam Eijdenberg wrote:
<snip>
> We'd also be quite open to exploring other ideas, though the above is
> what we're currently planning/started building out (and won't require
> additional work by log operators).

Note [1] that for 6962-bis we're planning to make it possible for
servers/certs to optionally embed/send inclusion proofs instead of SCTs.

When this option is used, the question of how to fetch inclusion proofs
in a privacy preserving manner doesn't even need to be asked.  :-)

[1] http://trac.tools.ietf.org/wg/trans/trac/ticket/104

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

---

From: Stephen Kent <[email-masked]>
Date: Thu, 10 Sep 2015 15:07:18 -0400

Rob,

I thought the intent, going forward was to make 6962-bis a description
of log operation. if so, then this new feature does not belong in that doc.
It belongs in a spec for Subjects (aka web site operators), or in the 
arch doc.

Steve

---

From: Rob Stradling <[email-masked]>
Date: Fri, 11 Sep 2015 22:22:57 +0100

> Rob,

Hi Steve.

> of log operation.

Log operation only?  If that's the current intent, I must have missed a
discussion/decision somewhere.

I thought the intent was for 6962-bis to describe "the protocol" as well
as log operation.

Perhaps the chairs could clarify exactly which documents this WG is
intending to produce, and what the scope of each is?

> if so, then this new feature does not belong in that doc.

Documentation of this "new feature" will be relevant to CAs (because it
will describe what they should put in certificates and OCSP responses)
as well as Subjects (because it will describe what they should put in
the CT TLS extension).

---

From: Karen Seo <[email-masked]>
Date: Wed, 23 Sep 2015 23:22:23 -0400

Hi, Rob et al.

Apologies for not chiming in sooner.  Steve was/is on vacation last week 
and  this week.  He'll be back next week.

Karen

---

From: Karen Seo <[email-masked]>
Date: Thu, 24 Sep 2015 00:17:31 -0400

Rob et al.,

> I thought the intent was for 6962-bis to describe "the protocol" as well
Could you clarify for me what you mean by "protocol?" (I'm not 
objecting, just asking for specifics.). There were previous discussions 
of whether to include TLS-related options/changes, whose resolution was 
left unclear (to me).
> intending to produce, and what the scope of each is?
Not meaning to usurp chair prerogatives and having not been able to 
attend the recent IETF (except remotely) and therefore having possibly 
missed something....

Recalling past messages, I believe there have been observations about 
(and no objection to) the need for further details/clarification on the 
following topics and to the general idea of fleshing these out in 
separate documents. I'm pretty sure various people volunteered to write 
at least 2 of them.  (1) a mechanism for ensuring correct behavior of 
the logs, i.e., GOSSIP, (2) auditor behavior and (3) monitor behavior.  
Discussions about client "behavior" have been more controversial but in 
any case, my 2 cents is that it would be simpler to separate the 
description of the client's behavior from 6962-bis and put it in its own 
document. It would be easier for implementers than hunting through 6962 
and would let 6962-bis progress while we hash out details re: client 
operations such as how does the cliemnt signal that it accepts SCTs, 
privacy concerns/solutions, what is the "somehow" whereby clients 
exchange STHs, how do clients obtain the necessary metadata, etc.

Thank you,
Karen

---

From: Melinda Shore <[email-masked]>
Date: Wed, 23 Sep 2015 20:49:02 -0800

On 9/23/15 8:17 PM, Karen Seo wrote:
> at least 2 of them.  

I haven't discussed this recently with Paul and he may
chime in with corrections or additional information, but I think
where we are with this is that if people want these documents
they really need to write initial drafts, and once we've got
agreement about the broad outline of the documents and the
drafts reflect that agreement we can put out a call for
adoption.  For the purpose of wrapping up 6962-bis, the
information they need is what will be moved out of the -bis
draft and into another document.  We definitely have
agreement to move client behavior into its own document.

So, basically, if you feel so moved to write an initial draft
on any of the aforementioned topics, you would be doing the
working group a great service.  We really can't move any of
this along without text.

Melinda

---

From: Paul Wouters <[email-masked]>
Date: Thu, 24 Sep 2015 11:55:50 -0400 (EDT)

> agreement to move client behavior into its own document.

I agree, but want to add a note that such a document should not hold
up the bis document. For example, what I don't want to see is that we
remove all client behaviour text from the bis document and then require
us to hold the document while the client document is being written. What
is fine with me is reducing parts of the bis text to scaffolding for
something we have adopted a separate document for.

Paul

---

From: Stephen Kent <[email-masked]>
Date: Mon, 28 Sep 2015 15:28:52 -0400

Rob,

> discussion/decision somewhere.
I thought that was the gist of a discussion at the meeting in Prague.
Ben and I agreed (surprise) that there should be a separate architecture 
doc,
which I am now writing. I said that I thought that 6962-bis should be a 
description
of log operation, which is what most of the text addresses now.
> I thought the intent was for 6962-bis to describe "the protocol" as well
certainly 6962-bis should describe how all log clients interact with it.
is that the "protocol" to which you allude above?
> intending to produce, and what the scope of each is?
good idea.
> as well as Subjects (because it will describe what they should put in
It is relevant to CAs, but I believe that CA requirements, other than how
to interact with the log, should not be part of 6962-bis. I have been 
including
CA, Monitor, Auditor  and TLS client requirements in the arch doc, since 
we have
no commitments to write individual docs for these. I have grabbed text from
6962-bis, where appropriate, for these sections. I would be happy to see 
others
volunteer to write requirements docs for these other elements of the CT 
system,
but until then I am gathering them into the arch doc.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Mon, 28 Sep 2015 15:39:10 -0400

Paul,

> something we have adopted a separate document for.
As I noted in a message I just sent, I have been putting (candidate) 
requirements
into the arch doc for all of the elements of the CT system other than 
the log.
I think this is consistent with your comment above. Also, I thought we 
agreed
that elements of client behavior (not directly related to log interactions)
are to be specified separately.

Steve

---

From: Rob Stradling <[email-masked]>
Date: Mon, 28 Sep 2015 21:02:57 +0100

On 28/09/15 20:28, Stephen Kent wrote:
> doc, which I am now writing. I said that I thought that 6962-bis should
> be a description of log operation, which is what most of the text
> addresses now.

Hi Steve.

AIUI, there isn't yet a -00 draft of your arch doc, and this WG has not
yet been asked to consider adopting it.

Meanwhile, there is a desire to complete 6962-bis ASAP.

> is that the "protocol" to which you allude above?

Yes.  I also consider the CT-specific parts of network interactions
between TLS clients and TLS servers to be part of "the protocol".

> to interact with the log, should not be part of 6962-bis.

Are there any specific "CA requirements" currently in 6962-bis that you
think should be removed from 6962-bis?  I can't find any that would fall
outside of "how to interact with the log".

> I have been including CA, Monitor, Auditor and TLS client requirements in
> the arch doc, since we have no commitments to write individual docs for
> these. I have grabbed text from 6962-bis, where appropriate, for these
> sections. I would be happy to see others volunteer to write requirements
> docs for these other elements of the CT system, but until then I am
> gathering them into the arch doc.

When do you expect to have a -00 draft of your arch doc ready?

---

From: Stephen Kent <[email-masked]>
Date: Tue, 29 Sep 2015 11:54:47 -0400

Rob,

> yet been asked to consider adopting it.
fair observation, but you reviewed the section I wrote for the Monitor
and you said that it looked good, except for two specific sentences
(one of which was derived from 6962-bis!).
> Meanwhile, there is a desire to complete 6962-bis ASAP.
publication of 6962-bis per se ought not be the goal. publication of 
documents
that clearly describe the CT system ought to be the goal of this WG, IMHO.
> between TLS clients and TLS servers to be part of "the protocol".
on this point we may disagree. there are several protocols (not one) 
that make up the
CT system: the comms used between the log and each of its clients,
comms between a TLS client and a server (which vary depending depending
on how SCTs are delivered), comms between a web site and a thrid-party  
Monitor,
and several protocols used to support the Auditor function (gossiping).
So, when you to "the protocol" it's hard for some of us to know which ones
you have in mind. if it's all of them, then I definitely disagree that 
they all
belong in 6962-bis.
> outside of "how to interact with the log".
right now, no.
> When do you expect to have a -00 draft of your arch doc ready?
by the end of this week.

Steve

---

From: Rob Stradling <[email-masked]>
Date: Tue, 29 Sep 2015 20:37:41 +0100

On 29/09/15 16:54, Stephen Kent wrote:
<snip>
> and you said that it looked good, except for two specific sentences

I did.

> (one of which was derived from 6962-bis!).

Which is still a work in progress.  ;-)

> documents that clearly describe the CT system ought to be the goal of
> this WG, IMHO.

Well, clearly we have different opinions on what the deliverables of
this WG should be, and the scope of each deliverable.

Chairs: Please could you settle this one way or another?

>>>> I thought the intent was for 6962-bis to describe "the protocol" as
>>>> well as log operation.
>>>
> they all belong in 6962-bis.

6962-bis has never tried to cover gossip.

Ripping out the TLS client/server comms from 6962-bis in the hope that
somebody will specify this in some future doc doesn't seem like a good
idea to me.

>>> It is relevant to CAs, but I believe that CA requirements, other than
>>> how to interact with the log, should not be part of 6962-bis.
>>

-- 
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: Stephen Kent <[email-masked]>
Date: Tue, 29 Sep 2015 16:50:19 -0400

Rob,

> ...
yes, in progress for a long time, especially compared to how long
I've been working on the arch doc ;-).
> ...
agreed.
> somebody will specify this in some future doc doesn't seem like a good
it's being done in the arch doc now. If the WG decides that we should have
separate specs for each elements (which I support) then we can extract text
from the arch doc and put it into those separate specs, making the arch doc
shorter and more consistently high level.
>>> outside of "how to interact with the log".
I did think of a few of examples from your discussion of redacted certs. 
Text in
3.2.2 tells a CA how to create a name-redacted pre-cert. This seems 
irrelevant to log
processing of pre-certs, since it doesn't appear to be a constraint 
enforced by a log.
Text in 3.2.3 seems to be a set of directions to a CA, and maybe checks 
to be performed by
a TLS client, but not constraints checked by a log.  These are examples 
of text that
was included in 6962-bis because it needed to be somewhere, but it does 
not fit the
notion of log/client interface description.

Steve