[messaging] Zero knowledge proofs of passport

[Mike Hearn]

Pond is a great advance for secure messaging, but it suffers from the fact
that I can't send someone a cold intro if they don't already know me. For
that reason it does not solve the Snowden/Greenwald problem.

Pond users *do* have email-address like things and servers *could* receive
and store arbitrary messages: it's only the "forward secure or nothing"
policy that forbids this. If you knew a static public key+server key for a
Pond user, you could send an message with the DH KeyExchange protobuf
attached and bootstrap the conversation that way.

So for many interesting conversations we end up back at the decades old PKI
problem, which is what this message is about.

*Problem statement*

The traditional PKI allows me to select a public key and work with a well
known CA to bind that key to some identity, additionally, to publish that
in some directory. When the fact that someone uses encrypted email is not
sensitive, it's useful. But it suffers from several flaws:

   - Although obtaining a cert for an email address is not too hard, often
   people think in other terms. Snowden may not have known Greenwald's email
   address at the start, he just knew he wanted to talk to "an American guy
   with the name Glenn Greenwald, who writes this particular blog" and maybe
   "who looks like this photo/video I saw". Finding the right email address
   introduces a potential for a savvy opponent to MITM messages right from the
   start.

   - Obtaining a CA cert for a natural name requires showing some proof of
   identity, but is annoying and expensive to obtain. I got mine by going to
   the local post office and paying a fee, then waiting a day or two. Hardly
   anyone will put up with this.

   - Even if you obtain such a cert, it typically only attests to your
   legal name and your email address. But names are not unique and can
   collide. Social networks use name+photo plus other useful details as
   disambiguators, but in practice X.509 certs do not allow this.

   - The directories are LDAP based and suck, so nobody uses them.

PGP key servers solve some of these problems, but the entries are
unauthenticated by anything except the WoT which leaks valuable social
metadata. Plus finding a path through the WoT can often be hard or
impossible.

It would be ideal if a user could create a findable human-oriented identity
similar to that of a social network, but that was hard to forge, and which
bound that identity to a public key. Additionally to do it for free, from
home, without any special new infrastructure like new CAs.

*e-Passports*

Starting from the early 2000's the international passport system (run by
the International Civil Aviation Organisation or ICAO) started being
upgraded to feature NFC readable chips that contain a copy of the data
inside the paper version, digitally signed by the issuing government. Some
passports have additional data and features, however they do not concern us
here.

If you have a passport and it was replaced in recent years it probably
already supports NFC. The wikipedia page here has an excellent list of each
countries implementation of the scheme:

http://en.wikipedia.org/wiki/Biometric_passport

The basic contents of the e-Passport are authenticated by a regular X.509
certificate chain and encrypted under a simple low entropy key derived from
details written on the photo page. This means the data is readable by
anyone with an NFC capable Android phone, using e.g. this app:

https://play.google.com/store/apps/details?id=nl.novay.nfcpassportreader&hl=en

Using this app you can obtain a copy of your e-Passport details by doing
nothing more than pointing your camera at the machine-readable zone at the
bottom of the photo page (to calculate the BAC key) and then holding the
phone against the passport for a few seconds. With an appropriate GUI this
is a task anyone with a passport and compatible phone can accomplish.

Some passports have an unextractable private key hidden inside them. It
should be obvious how this could be used to in turn sign a short-term
private key that is usable for encrypted messaging, with the public part
(including a clear photo) uploaded to a searchable, Facebook like directory.

However this plan has a couple of fatal flaws:

   1. Most passports do not have such a private key inside them, presumably
   for cost reasons. Therefore it cannot work for most people.
   2. It requires uploading a full copy of the data inside your passport,
   including things like your passport number. This is inflexible and many
   would refuse to do this.


*General zero knowledge proofs*

It is expected that within the next year or two a fully usable ZKP
framework will become available via libsnark:

https://github.com/scipr-lab/libsnark

Some code is already available but is currently too low level to be useful.
But the researchers have created, amongst other things, a version of GCC
that compiles imperative C programs down to a form which can be turned into
a very small zero knowledge proof with both private and public inputs
allowed. Those programs can have private inputs, they can contain loops,
reuse existing C libraries and do other things that have historically been
impossible to accomplish under zero knowledge. And they plan to get most of
it out there under open source licenses.


*ZKPOP*

By combining libsnark with the Android NFC passport reader, we should be
able to build a proof that the user has a valid certificate signed by a
national passport agency, but selectively revealing only the parts the user
wishes. Additionally, by setting a private key as a private input, and the
public key as a public input, we can bind this proof to a key of our
choosing.

This has a couple of interesting uses for building a private messaging
system:

   - By selectively revealing things like real name, photo, and year of
   birth and publishing the proof to a searchable directory, we can easily
   create a Facebook-like directory of verified public keys without the need
   for the user to leave their own home and without the need to rely on social
   networks of key verifiers.

   This can help mitigate a Greenwald/Snowden type introduction problem.
   Although the issuing government could create a fake profile entry, other
   governments could not (at least not without breaking the security of the
   other governments passport infrastructure, which we assume they are
   incentivised to protect). Additionally as the entries are public such
   behaviour could be noticed quite easily.

   - By revealing only a hash of the given passport without anything else,
   you can create a quasi-anonymous yet expensive identity. This has
   implications for spam filtering - someone anonymous can send emails, and if
   they turn out to be an asshat spammer their passport hash can be blocked.
   This is likely to be a more troublesome roadblock to spamming than an IP
   address block. For Pond, which has low bandwidth, a strong anti-spam
   solution that does not require metadata analysis seems important.

   I say "quasi-anonymous" because an issuing government that is storing
   the exact bytes written to every passport could of course simply enumerate
   all of them and reverse the hash. Additionally, governments that record the
   contents of passports when people travel across borders could also do this.
   However a government that is not your own/is hostile to your own and where
   you have never travelled should find deanonymisation hard.

   Additionally, any adversary that is *not* a government should find
   deanonymisation very hard indeed. Often a weaker threat model is sufficient
   e.g. you wish to be anonymous not from the NSA but non-state actors you
   might fear, like a local drug cartel.


*Other use cases*

Any system in which sybil attacks are a problem could potentially use these
quasi-anonymous credentials to help separate nodes. For example Tor router
operators could publish such a ZKPOP that reveals *only* the issuing
country. Clients could then build circuits through routers owned by
citizens of countries that dislike each other and are unlikely to
co-operate.


*Methods of attack*

No key scheme is perfect and nor is this one. Some attacks were already
listed above, but additional ones worth highlighting are:

   - Passports are not two factor credentials. Thus anyone who can get
   physical access to your passport for a few minutes can create an identity
   as you.

   - People routinely give up their passport when crossing borders,
   checking in to hotels and doing other travel-related things. So it may be
   that the number of people who can fraudulently create such identities is
   high enough to make it unworkable.

   - Host governments can manufacture fake identities at will, although
   only for their own country.

   - There is a trade in stolen or sold passports; it's not uncommon for
   flights to have people travelling on bogus passports quite successfully as
   almost all countries do not check for theft.

It might be possible to address the theft issue by having users also do a
"salute"; this means they take a selfie (photo or video) in which they are
performing some action that was selected by some third party, like holding
up a certain number of fingers or holding a code written on paper, with
their face clearly visible. The third party then checks that the face in
the salute is the same as the face in the passport. In this way they
authenticate the act of creating the ZKPOP with their body. How to achieve
this in a mostly decentralised setting is a topic for further research.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140726/e4f9f25a/attachment.html>