Subject: Re: [saag] Scaling a PGP Key signing

From: Jeffrey Hutzelman <[email-masked]>
Date: Sun, 02 Feb 2014 13:59:55 -0500

On Sun, 2014-02-02 at 11:14 -0500, Phillip Hallam-Baker wrote:
> There has been a proposal to hold a PGP key signing in London. Exchanging
> keys between thirty or a hundred people seems pretty pointless to me.

We used to have one at every IETF meeting.  I ran them for several
years, until I stopped being able to come to meetings.  Before me, Ted
Ts'o ran them.  Despite trying several different times during the week,
the largest attendance I've ever had was 24 people.

I disagree that exchanging keys between that number of people is
pointless.  The IETF is one of a relatively small number of groups that
regularly brings together in one place people with a technical mindset
(who are likely to engage in events like PGP key signings) from all over
the world.  Exchanging keys among even a small group of such people
brings much-needed geographic connectivity to the web of trust.

>  If
> the exercise is going to be worthwhile we should aim to have a system that
> could scale to the point where if everyone attending IETF 89 wants to
> participate, this is practical.

On the other hand, I don't think it's worth spending effort on figuring
out how to scale a key signing to thousands of people unless you can
also figure out some way to get thousands of people to want to
participate.  Additionally, for such a thing to be useful, you need to
figure out how to do it without signers ending up having to make a
weaker assertion (instead of "I verified this person's credentials",
something like "someone at the same conference as me may have verified
this person's credentials").  This is especially important because if
you succeed in getting a large fraction of IETF meeting attendees to
play, most of them will not understand the properties of the
verification process, which is, after all, a rather convoluted security
protocol.

That said, if you can figure out a way to get a thousand people to come
to a key signing, that would be a great thing.  And if you can't, but
are willing to host a traditional key-signing with 10-20 people in a
room, that would be good, too. 

In some paragraph I already deleted, you said the effort required of
participants needs to be constant.  But that is not possible.  Since
creating a signature is itself an action that takes nonzero time,
memory, and energy, the task of creating N independent signatures cannot
be better than O(N).

Therefore, I assume either that you really mean that the constant factor
associated with that term must be small (how small?), or that you are
proposing a system in which each participant receives only a limited
number of signatures, rather than the signatures of every other
participant.  I think you mean the former and will base the rest of my
comments on that assumption.  If you really meant the latter, I imagine
I'll have to start over.

> Here is one proposal
> 
> 1) Appoint Registrars
> 
> If we want to tie the validation process to government documents then we
> will need people to look at them.
> 
> If there are 1000 attendees, then we might have ten registrars, appointing
> more during the conference should the need arise.

What is the value of a signature that is not based on actually verifying
the signed uid?  The model is built on the premise that each signature
represents some actual, independent verification.  If a hundred people
each sign a key based on the verification done by one "registrar" not
even in the presence of the people doing the signing, then you haven't
gained any value beyond that of the signature created by the registrar
himself.  However, you _have_ diluted the value of the web of trust, by
flooding it with signatures that not only are based on weak
verification, but which are probably not correctly tagged to that
effect.

When educating people about PGP, we are generally careful to warn them
never to create and publish a signature based solely on some existing
signature.  That's because doing so adds no value to the web of trust,
effectively makes a false assertion about the signer's knowledge about
that key, and interferes with the algorithms used for deciding how much
trust to place in a key which is several hops away.  Requiring N
independent signatures on a key doesn't help if you can't tell that
they're not really independent.

> 
> 2) Sign up Web site.
> 
> To sign up for the key signing, participants have to generate a pgp keypair
> (if they haven't got one already) and submit their purported name,
> purported email address and PGP fingerprint to a Web form. [We assume the
> pgp key corresponding to the fingerprint is loaded on to some PGP key
> server that we can find]

The process Ted and I both used was to collect keys (not fingerprints)
via email.  It turns out that it is relatively easy to collect these
messages, construct a keyring, and publish both the keyring and a list
of fingerprints.  The process is certainly O(N), but the linear part is
mostly in work done by a computer, not by the person collecting the
keys.

Note that we ask people to submit keys, rather than fingerprints.  This
is useful for several reasons.  First, it means we don't have to assume
that keys will already be published on the key servers.  That's
important because such an assumption will probably be false for
newly-generated keys, and because some people may not care to upload
their keys immediately, or ever.  Second, it means we get a complete
list of UIDs associated with that key, which include names, email
addresses, and other information, rather than only a single name.  And
third, it eliminates a variety of errors, including mismatched
fingerprints, key IDs, and UIDs.

Additionally, collecting keys rather than fingerprints allows us to
trivially construct a keyring containing exactly the keys of
participants in the event.  In fact, that keyring is constructed as an
intermediate step in producing the list of fingerprints.  That makes it
easy to provide participants with a keyring they can download and either
import or manage separately for the event.

> The sign up Web site can verify the email part by sending an email
> challenge encrypted under the corresponding public key.

We don't do that.  General practice is to do this by having each
participant send the signed key to the relevant email address.  This
gets people in the habit of doing this rather than simply uploading
signed keys to the keyservers without verification.  It also means that
signers don't have to depend on the organizers to have done this and
done it correctly.  That's valuable because the entire process is
designed to avoid anyone having to place trust in the organizers.

> What we need to do at the conference is to establish the binding between
> the fingerprint and the person's name. Here we have a choice of validation
> policy. Should we require validation to the IETF name badge?

Certainly not.  The information on IETF name badges is provided entirely
by the participant, is not validated by the conference staff, and is not
required to match anything about the participant's actual identity.  For
example, some readers of this list may remember a meeting in 2002 when a
number of Security Area folks went around with badges saying their names
were "Steve".

>  or to
> government issued documents?

This is usual, but has the problem that most folks are unfamiliar with
what they're supposed to look like and lack the tools or access to
validate them correctly.  Nonetheless, it's usually the best we can do.
If you're going to have a small cadre of verifiers supporting a large
population, it might be valuable for them to get some advance
information about the correct appearance, and security features of the
documents they will examine, as well as some general information on
expected verification procedures.

> Otherwise people would have to find one of the registrars while at the
> conference, show their government identity documents and the registrar
> would have to enter some sort of confirmation that this has happened into
> the Web site.

Again, you're introducing the notion of trusting the event organizers
and the web site to accurately report information.  Why not simply have
the registrar make a PGP signature and get on with it?

Note, BTW, that it's not good enough for the registrar to look at my
documents and decide that I am who I say I am.  It is also necessary to
take a statement from me to the effect that the published fingerprint is
correct.  And, it is necessary to record that statement in a way that
ties verification of my identity to the fingerprint I actually
confirmed, and not to some different fingerprint that is published later
by the event organizers.

> 4) Distribute a signed directory of user names to keys.

Signed by whom?

Overall, this proposal seems to introduce a lot of points at which the
participants must trust both the intentions and competence of the event
organizers.  I know that, as someone who has worked for multiple CAs,
you're used to thinking in terms of having a more-or-less
universally-trusted party.  And, I know you have a pretty good idea of
what such a party has to do in order to be worthy of that trust, and of
how badly (and how easily) it is possible to screw up.

PGP, however, is built on a different model, which distributes that
trust among all of the individual signers.  In this model, events like
key signings are deliberately organized such that signers end up doing
the same verifications they would do in a one-on-one signing, but in a
scalable way.  It's important that they be able to do so _without_
having to trust the event organizers not to slip in a false key.

That means
- NOT trusting organizers to verify email addresses
- NOT trusting organizers to correctly relay submitted key fingerprints
- NOT trusting organizers to relate submitted UIDs to IETF registrations
- NOT trusting organizers to decide who will verify government documents
- NOT trusting organizers to track which verifications have been done
- NOT trusting organizers to assert a name and fingerprint go together

In other words, not trusting organizers to do much at all other than
obtain a room, convince people to participate, collect and redistribute
submitted keys (which will then be verified by participants), and to
produce untrusted, verifiable aids to scalability.

It is not possible to reduce the effort required of a participant below
O(N).  It _is_ possible to arrange to be able to do the whole process in
O(N) time.  However, the time involved is at least one minute per
participant, so for N=1000, you're going going to be there all day.  To
handle such a large group, you need to find a way to reduce the constant
factor and to let participants spread their time commitment over a much
longer period of time, preferably including _not_ having to do
everything at the IETF meeting.

For example, have participants print a stack of business cards with
their name, email address, etc, and key fingerprint(s).  Then the amount
of time I have to spend per participant is the time it takes to look at
each others' documents and trade business cards, which can be done
anytime during the week.

One final note, in the event you were thinking of a model in which only
the relatively small number of "registrars" actually verify documents
and sign keys.  That sounds good in theory, especially if you can make
it easy to find not just one but several such persons over the course of
the week.  However, you may find it difficult to find qualified
volunteers who are willing to give up 16 hours of their time over the
course of IETF week...

-- Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 2 Feb 2014 15:01:47 -0500

On Sun, Feb 2, 2014 at 1:59 PM, Jeffrey Hutzelman <[email-masked]> wrote:

> the world.

And how many people used them afterwards?

I want to create an expectation that the keys get used. Hence there has to
be at least the possibility of getting to ubiquity within the organization.

We are under attack here. We need to have the capability of exchanging
secure mail between people working on privacy technologies. The point of
the exercise would not be promoting the use of PGP. It would be to provide
the secure communications capability should we need it and to work out what
we need to change in the PGP/SMIME architectures.

> memory, and energy, the task of creating N independent signatures cannot

What I said was that the effort required of the participant has to be a
constant. Thus 100 participants, each expends effort x, total effort =
100x, 1000 participants, each expends effort x, total effort = 1000x.

For the scheme to be considered scalable there can't be a human in the loop
being required to do more than a constant amount of work. So if we have
registrars we have to be able to scale up the number of registrars if the
attendees increases.

> participant.

This is where I think we should move away from the PGP protocol in future.
Instead of atomic peer to peer signatures, I think we want to have one list
of fingerprints / addresses / names and have that signed by all the
registrars attesting to it. And then checkpoint that list with a CT like
protocol.

> verification, but which are probably not correctly tagged to that

My objective is to provide the strongest degree of trust that is practical
and ubiquitous. Cryptoperfectionism has harmed deployment of crypto from
the start. It burned PEM and it burns PGP.

If we get deployment we can increase the trust.

There is no way that we can have 1000 participants each check each other's
keys.

> trust to place in a key which is several hops away.

You make that claim, but where are your metrics? what is your model?

My model is the time based work function and I can show the value of a
keysigning in terms of how much it would cost to have faked it.

We know that right now the value of faking out signatures against our
community is at least whatever the price of the attack used against
Quisquateur in the TAO catalog. But they probably can't send a hundred
impostors to IETF89.

>  Requiring N

Which is why I don't plan to use the PGP'91 model in the future. That is an
area where more research is needed.

We need to combine features of the PKIX and PGP models.

> The process Ted and I both used was to collect keys (not fingerprints)

via email.

Yeah, they have to be available somehow.

I want to drive all this into tools so it is one click at some point in the
future.

> designed to avoid anyone having to place trust in the organizers.

I would prefer to Trust but Verify.

> number of Security Area folks went around with badges saying their names

But does that matter?

Since we are facing government adversaries, why trust government documents?

> how badly (and how easily) it is possible to screw up.

Of course, that is how we scaled the Web PKI to two billion relying parties.

-- 
Website: http://hallambaker.com/

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Sun, 02 Feb 2014 15:49:52 -0500

> And how many people used them afterwards?

I wish we had that sort of data.

> be at least the possibility of getting to ubiquity within the organization.

Well, if you're specifically thinking in terms of intra-IETF
communication rather than something more global, the requirements might
be different.  It's still hard, though, because face-to-face meetings
are not supposed to be our focus.

> 100x, 1000 participants, each expends effort x, total effort = 1000x.

Right.  So the effort required of any given participant must be
constant.  I argue that cannot be the case, if every participant is
going to sign every other participant's key, because signing N keys
takes O(N) time.

However, if what you're really looking for is short paths between IETF
participants, then there is no such requirement.  You just need a
reasonable number of paths to everyone.  IIRC, the Debian project has
done something along these lines, with a quite a bit of success, for
many years.  It doesn't require a large key-signing "event", only that
pairwise key signings happen when someone joins the group.  The real
problem is bootstrapping an already-large group, which I now assume is
your focus.

> registrars attesting to it. And then checkpoint that list with a CT like

So do away with the web of trust altogether, in favor of centralized
authorities?  I can't decide whether that's practical for the IETF.  I
also can't decide whether it's as effective a defense against the kinds
of attacks you're worried about(*).  I do know it will be unpopular
among PGP purists.

> There is no way that we can have 1000 participants each check each other's

I think we're agreed on that point.

> You make that claim, but where are your metrics? what is your model?

I'm sorry.  I made several claims there; which one are you asking about?

> Quisquateur in the TAO catalog. But they probably can't send a hundred

Why not?  $70K is not a large number for a nation-state.  It would be a
nice influx of cash for the IETF, though. :-)

> Since we are facing government adversaries, why trust government documents?

That is a very important point, and perhaps a good focus for another
whole discussion.  To date, pretty much everyone trusts government
documents in validating identity for key signing.  In the IETF, I wonder
if we would be better off ignoring such validation entirely, and instead
taking a LoF/TOFU approach.  If I sign every message I send, then even
though you don't know I'm a dog, you can assume messages signed with the
same key came from "me".

> Of course, that is how we scaled the Web PKI to two billion relying parties.

And it seems to work reasonably well, despite the fact that virtually
none of those RPs have any recourse against a CA that screws up.  I
suspect it does not work quite as well against attackers funded by major
nation-states.  Or at least, not competent ones.  But, we're going off
topic, so if we're going to talk more about the web pki model, let's do
it in a separate thread.

-- Jeff

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 02 Feb 2014 21:48:44 +0000

On 02/02/2014 08:49 PM, Jeffrey Hutzelman wrote:
> In the IETF, I wonder

IMO yes. Works just fine with OTR.

S.

---

From: Mouse <[email-masked]>
Date: Sun, 2 Feb 2014 17:23:34 -0500 (EST)

> It's still hard, though, because face-to-face meetings are not
> supposed to be our focus.

Indeed, I would argue that the whole key-signing paradigm is...well, I
first wrote "broken", but I think that's putting it too strongly...for
an organization that, like the IETF, is about doing the work, usually
remotely, rather than caring about details that are irrelevant to the
work.

For example, I have actively declined to do the key-signing thing for
my key, because they bind the key to the meatspace identity, but I want
my key bound to my electronic identity, not my meatspace identity.
Looking for an alternative, I put the fingerprint in my signature, so
there is evidence scattered all over the world in list archives and
mailboxes when I - the digital "I", which is the only one of me which
uses PGP - have occasion to produce the key and claim it as mine.  (So
far, this has happened only once, I think.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 2 Feb 2014 17:41:04 -0500

> of attacks you're worried about(*).  I do know it will be unpopular

I see four trust models in use or close to it:

1) Direct trust using PGP fingerprints exchanged from subject to relying
party
2) Indirect peer to peer trust (Web O'Trust)
3) Indirect hierarchical trust (PKIX/WebPKI)
4) Certificate Transparency

We need all four models and they are mutually reinforcing. So I am not
saying do away with Web of Trust, I am saying do away with the idea that
its the Web o' Trust or nothing.

I don't care about not having the PGP purists, there are far more people
who want secure email than people who want PGP secure email or nothing at
all.

> nice influx of cash for the IETF, though. :-)

They can't go back in time to spend it.

If we timestamp the key signing output CT style, the government has to
decide to spend that $70K before the signature manifest was notarized. We
can put a timestamp notary beyond reasonable doubt using hash chain type
approaches.

> though you don't know I'm a dog, you can assume messages signed with the

That is my view. Having a lightweight check on the mail address avoids
having to deal with large numbers of spurious key registrations. But the
real value would come from having the list checkpointed in time.

One of the weaknesses of the PGP trust model is that it doesn't really
address revocation in a meaningful sense. Neither does the direct model. So
that requires the initial key signing to be very accurate.

Lets look ahead to IETF 92. If a key has been on the list unchallenged for
a whole year then that is a data point. I would like to make it an
important data point, one that conclusions can be drawn from.

> topic, so if we're going to talk more about the web pki model, let's do

So far the only major breaks have been government sponsored.

I am quite happy if what we achieve here is merely degrading the NSA
capabilities to the point where they have to choose their targets rather
than apply the dragnet approach.

This does not need to be about putting the NSA out of business. I have no
problem with Lawful Intercept by civilian authorities under specific court
orders.

---

From: Theodore Ts'o <[email-masked]>
Date: Sun, 2 Feb 2014 17:43:29 -0500

> > (who are likely to engage in events like PGP key signings) from all over

One of the more useful thing about having people who are willing and
interested in using PGP/GPG sign keys at meetings/conferences where
people travel long distances to attend is that it helps seed the long
distance links.  If I and Bob Morgan from Stanford sign each others'
keys, then when he goes back to California, and I go back to Boston,
and sign people who are local, it greatly helps bootstrap the global
trust system.

> be at least the possibility of getting to ubiquity within the organization.

They way you get to ubiquity is that you require them to be used.
This is going to be really unpopular, but that's the only way to do
it.

For example, in the Linux kernel development community, after the
kernel.org disaster, you can't upload to a git tree or upload software
to be distributed via ftp.kernel.org without having a GPG key which is
within two hops of five people who formed the "root certification" of
the web of trust.  (In addition, if you want to send a pull request to
Linus Torvalds, you need to have the git tag be GPG-signed via "git
tag -s", or face additional scrutiny and verification before he will
accept your pull request.)

The five people who formed the "root of trust" were chosen as people
who were well-known in the community, and who travel enough that it
was relatively easy to get the web of trust bootstrapped globally.
For example, when I was in Mountain View, I held a PGP key signing for
kernel developers at the Google offices, and that nicely took care of
a large number of the developers in the Bay Area who hadn't been able
to make it to one of the Linux conferences.

What if, for example, in order to upload an I-D to the FTP server, the
I-D had to be GPG signed.  And what if the tools largely automated
this process?  Since tools.ietf.org hasn't yet suffered a catastrophic
security incident, you'll probably have to phase it in over a period
of six months, but if there was consensus that this was a good thing
to do for the IETF, the kernel.org web of trust bootstrap is a pretty
good worked example of how to go about it.  It was mostly painless,
especially compard to what we had to do to recover from the security
compromise.  :-)

(And if there are people who can't make it to a meeting, and haven't
had a chance to do an off-line key signing with someone local to their
area, they can have someone else upload the I-D for them.  The idea is
to add just enough extra work to motivate people to actually get
integrated into the web of trust.)

> registrars we have to be able to scale up the number of registrars if the

Instead of having formal registrars, and one really big PGP signing
party, what might be better is having tools to make it easy for people
to share their fingerprints.  If there is an easy way to print out a
sheet of paper which can be cut up into business-card sized
fingerprints with the person's username and e-mail address, then
people can exchange fingerprints and do whatever off-line verification
is needed at working group meetings.  Encourage wg chairs and IESG
members to serve as unofficial "roots of trust" --- a wg chair will
likely be able to authenticate the bag of protoplasm standing in front
of him, not just by verifying government I-D, but also by having a
technical conversation about an I-D of mutual interest, based on
previous e-mail conversations on the wg mailing list.

After all, someone might forge government ID for Steve Kent or Sam
Hartman, but having interacted with them for years, in some sense
that's actually *better* verification than the government ID.

This is also much more scalable because many more critical
conversations will be happening within working groups and IETF areas,
so just let people exchange fingerprints at the beginning or end of wg
meetings or area meetings.

> There is no way that we can have 1000 participants each check each other's

That's true, and it's also true that we don't have to have everyone
certify each other's key.  But it's also true that each IETF attendee
is probably primarily interacting with a few dozen fellow engineers,
and that partition is largely, although not completely, based on areas
and wgs.

						- Ted

---

From: Michael Richardson <[email-masked]>
Date: Mon, 03 Feb 2014 09:39:35 -0500

> far, this has happened only once, I think.)

But, since you didn't sign your email as a regular habit, you could have been
showing anyone's finger print.

--
Michael Richardson <[email-masked]>, Sandelman Software Works

---

From: Mouse <[email-masked]>
Date: Mon, 3 Feb 2014 10:16:42 -0500 (EST)

>> [...], I put the [PGP key] fingerprint in my signature, so there is
>> evidence scattered all over the world in list archives and mailboxes
>> when I - the digital "I", which is the only one of me which uses PGP
>> - have occasion to produce the key and claim it as mine.
> But, since you didn't sign your email as a regular habit, you could
> have been showing anyone's finger print.

True as far as it goes.  But if I don't have the private data for the
key whose fingerprint I'm showing, there's no benefit to me from
showing it; if I do, it's effectively my key.

There is the key-fingerprint-collision risk, it's true.  But that's not
an attribute of the meatspace-vs-digital divide; it's an attribute of
identifying the key by its fingerprint.  If-&-when I produce my key and
someone else produces another key with the same fingerprint, I'll have
to deal with the collision.  But this is hardly new; how many people
can present government photo ID - unforged, even! - identifying them as
(say) David Smith?  (That's not a hypothetical example; one of my
digital friends has that as his meatspace name.)

If anyone is willing to sign my key as belonging to my _digital_
identity - see Ted Ts'o's remark upthread about a WG chair identifying
someone by chatting about work-in-progress - I'm most certainly up for
it.  I avoid key-signing parties not because there's anything I dislike
about binding keys to identities, but because (IME) in my case they'd
bind the key to the wrong identity.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign