[guardian-dev] WOT and Authentication Research

Melvin Carvalho melvincarvalho at gmail.com
Tue Dec 4 08:29:34 EST 2012


On 2 December 2012 03:24, Patrick Baxter <patch at cs.ucsb.edu> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> Hi all,
>
> I have a couple research ideas dealing with Authentication and the WOT. I'm
> looking for any criticism, opinions, or thoughts on my current directions.
> Mostly, I want to make sure I'm not barking at the wrong problems or that
> there
> are not any reasons why some of my current ideas fundamentally would never
> work
> either in practice or in theory. It'd be ideal to incrementally deploy any
> of
> these solutions, but I'm not assuming that redesigning things is out of the
> question. Particularly, when it comes to the role of keyservers.
>
> One way to describe the general problem of authentication that I think was
> stated well was in "Distributed Identity Management in the PGP Web of
> Trust"[1]:
>
> >we are trying to map unique and unforgeable identifiers (in this case
> public
> >keys) to ambiguous and potentially contested identifiers (names, e-mail
> >addresses, ect.)
>
> I'd state this one step further and say that really you want to know that
> an
> identity controls both this forgeable identity and sole access to the
> private
> key. Correctly mapping a public key to a communication domain is important
> but
> it is better when you can also capture the identity behind it. Google
> should
> control its own domain name but also the private key of the public key
> associated with it. Alice should actually control alice at alice.tld and her
> private key.
>
> When I say communication domain I am mainly considering any sort of unique
> namespace as part of a communication medium that needs authentication (but
> may
> not always require it). Usually these are handed out by single
> authorities. The
> obvious cases are e-mail accounts, domain names, XMPP accounts. All have
> common
> ways to encrypt and sign information (straight PGP, HTTPS, OTR
> respectively)
> The actual keys used for each encryption scheme can be subkeys of the
> master
> identity.
>
> Ultimately though you must also consider that private keys can be stolen or
> lost. Their are two independent failure involved: stolen/lost private keys
> and/or lost control of a communication domain. To account for these
> failures
> you can't make knowledge of this mapping immutable, but you also don't
> want to
> make it trivial for someone to claim a new public key for an email address
> whose real owner has already published a key. Malicious people can always
> of
> course publish new mappings, so instead I want a strategy to generally
> restrict
> publishing of bad mappings while balancing the ability to update mappings
> for
> legitimate reasons.
>
> I'd like to bring the discussion to find a more sane way to balance these
> constraints. I have some ideas for improvements in two areas, but keep in
> mind
> none of this is tested or fully worked out. First, what I see as the
> problems
> with current infrastructure.
>
> Problem 1: WOT
>
> I see the main function of the WOT is to maximize the chances that, when
> introduced to a new party, that user van verify the key through a path in
> the
> WOT. It'd be nice to have some sense of reliability in this validity and to
> detect whether this new party is malicious or not (their public key ->
> domain
> mapping is not the identity you expect).
>
> 1) Trust metrics don't scale in finding valid paths, other proposed trust
> metrics return non-binary results. When is a WOT path good enough?
>
> Current GPG uses a trust metric to say whether or not a key you signed is
> trusted to introduce another key. Although it makes sense to add a metric
> for a
> keys trustworthyness to introduce new keys[2], I don't think this scales
> logically. Even in the strongly connected WOT [3] the average distance is
> around 6. This means that to introduce yourself to a new key you need
> already
> have determined trust worthiness of 5 arbitrary nodes as introducers. You
> want
> to use the web to validate new people and I think in most cases its very
> unlikely you are capable of making this many trust decisions for some
> random
> path.
>
> You can make a trade off by using the trust metric of each node only to the
> keys it signs. Now you might be able to validate longer paths, but the
> trust
> metric is less meaningful.
>
> Instead users often use the presence of a key on a keyserver for validation
> (bad) or they attend many key signing parties and have directly signed the
> keys
> they talk too. There is a lot of room for improvement, even the existence
> of
> one valid path in the WOT (without trust metrics) is better then just
> taking a
> key from a keyserver.
>
> 2) Multiple keys can contain the same UID.
>
> This is a problem because multiple keys can claim ownership to a single
> name or
> email address. This allowed because that email address might have multiple
> keys
> used with it. I think this is a huge area of improvement. I'd like to
> impose
> some sort of structure or restrictions to how non-malicious nodes maintain
> a
> WOT. This way there must be some consensus on a single established mapping
> so
> that it is not easy for Mallory to create a new key and claim it belongs
> to an
> email they don't own.
>
> Problem 2: End-user Usability and Accessibility
>
> The current WOT and PGP infrastructure is limited to advanced users. It
> requires manual signing and knowledge to make abstract verification and
> trust
> decisions.  This is the usability problem. I think a lot of this can be
> solved
> through implementation and my current idea revolves around building
> signatures
> for a WOT by automatically signing keys you've 'verified'. There are lots
> of
>   ways to capture out of band user interactions to build a web.
>
> User-to-user interaction provides many ways of remembering and establishing
> validity with identities. People close to you in your social network
> should be
> strongly validated and remembered. No paths through the WOT is necessary.
> Users
> need a structured approach to both remembering and validating keys but
> also a
> way to sign keys and participate in the WOT.
>
> The Guardian Project has already started work on this end of things in
> their
> PSST project [6]. I've interned for them this past Summer and the PSST
> project
> of theirs has largely inspired (or overlapped with) things I am writing
> now.
>
> General Solution:
>
> Basically, I think there should be a single publicly established mapping of
> public keys to domain identifiers. One of each type of domain identifier
> per
> public key. It is assumed that each of these domains can provide some sort
> of
> proof of control and that as long as you control your domain identifiers
> and
> sole access to you private key you can always keep your mapping valid and
> prevent others from claiming control. Ideally, if private keys couldn't be
> lost, you could always use your private key to prove ore reestablish
> ultimate
> control of something like an email account. However, private keys can be
> lost
> or stolen too and this must be considered.
>
> Should a failure of lost access/control of EITHER a private key or domain
> identifier occur there needs to be a best effort approach to resolving this
> issue. If you lose everything, nothing can be done and you now no longer
> have
> control of those accounts or communication channels. This is already true.
> However, if this mapping also captured some real-world identity of yours.
> You
> may be able to appeal through out of band channels to those who validated
> you
> based on this knowledge.
>
> The big picture is that I want to use some sort of consensus or proof of
> control to publicly bind this single mapping. A keyserver infrastructure to
> support this will be necessary but can be designed to require consensus on
> a
> single WOT across many keyservers. Of course, all verification of paths
> should
> take place offline and we want to servers to have the least authority as
> possible. They ultimately will have some authority on what mappings are
> valid.
> This places a stricter requirement on how we spread WOT information, but
> will
> place a higher confidence in the ability to use that information.
>
> Improving the role of the WOT:
>
> In general, I think the WOT is necessary to provide introductions to new
> identities. There needs to be some established guarantee of what it can
> provide
> and what it cannot. I'd like to see existing paths in the WOT better
> leveraged
> for new introductions.
>
> 1) 1-1 Mapping and Proof of Identity:
>
> I mentioned this mapping above in that the WOT data structure requires a
> 'consensus' on a single mapping for each public key to a domain(There can
> only
> be one!). Also a proof of control is necessary to create or change
> mappings.
> Much of the details of this still need to be worked out.
>
> There needs to be some cost to changing this identity for legitimate
> reasons so
> that malicious users cannot either: present a different public key for a
> domain
> identity they don't own OR that by having control of a domain identity
> they are
> able to remove the public key the legitimate user controls .
>
> There may be some practical solutions that mitigate this problem. For
> email for
> example, when you wish to change your master key but keep your email, there
> could be a lead time on making the change if you lose your key. So when a
> token
> is sent to the email to confirm the change, even if its intercepted, as
> long as
> it isn't censored, the user in control of the email address will have time
> to
> react and prove the key isn't actually lost. A different set of criteria
> could
> be determined for each domain of potentially contested mappings. In the
> future,
> if a user has a stronger ability to guarantee their private keys are not
> stolen
>   (ie they have a trusted security token with backups) or that they will at
>   least have access to revocation, stricter requirements could be added to
>   update a key server identity.
>
> An important point I think here is also drawing the line between when its
> good
> to be flexible in allowing keys to change and when to fail to prevent MITM
> attacks. Different domains will have different requirements. Also, there
> are a
> lot of advantages to a central key infrastructure, but at some point it is
> still a central point of failure. Maybe if this *better* keyserver thing
> plays
> out, work into a distributed WOT data structure that supplements the key
> servers could be done. There would need to be a meaningful way to solve
> conflicts between what a user learns from another user and what the
> keyserver
> shows.
>
> Initial links into this WOT and identities of the keyservers should be
> distributed with user software that manages these keys. This way they have
> secure HTTPS communication with the server and eventually they can move to
> verifying their own seeds into the WOT. This is essentially key pinning
> and is
> where the bootstrapping will occur. Since your often already required to
> trust
> that software is non-maliciously distributed why not reduce the bootstrap
> process to a single point. This reduce the opportunities for malicious
> attacks
> to one. If people had physical keyrings (I think this is one day ideal,
> something like GPG smart cards that store more data) you could also trust
> an
> entity to supply some initial pinned keys through snail mail rather then
> the
> network. That may or may not be a better.
>
> 2) WOT structure, path computability, and utility
>
> A lot of interesting statistics and research has been done on the current
> strong set of PGP keys. The most recent attempt on improving trust metrics
> I've
> found is in the paper cited as [1]. They argue that current users often
> simply
> validate a key by its existence on a public keyserver and that "without
> automated tools for determining the trust of keys in the web of trust in an
> established way, users have no feasible alternatives to these bad
> practices."
> This paper assigns a trust rating for 3 different methods of determining
> trust:
> Disjoint paths, Network Flow, and Strongest Path. I think these are
> interesting
> methods, but in the paper, random weights of introduction trust are
> assigned to
> each edge in the WOT. This is at least scalable compared to the current GPG
> solution because you only need a trust metric for keys you signed. I'm not
> convinced trust introduction metrics are useful beyond a localized scope,
> but I
> think path analysis will be.
>
> Other statistics and analysis of paths in the WOT: [4][5]. It is not clear
> to
> me what is the best way to validate in the WOT and what decision to make
> when
> you receive a non-binary metric.
>
> For the moment, I think using strongest or disjoint paths would be fine to
> validate (but not necessarily sign) keys in the WOT once we have some
> better
> guarantees that the mapping is correct. So you are essentially trusting the
> maintenance of the WOT by keyservers combined with an existing valid path
> that
> you compute yourself.
>
> One interesting way to structure the WOT is by creating a Hypercube of
> Trust[7].  Based on the size of the Hypercube you have a strict # of
> bounded
> disjoint paths that are easily computed and some guarantees on malicious
> nodes.
> Quite interesting, but the obvious problem is that this structure doesn't
> reflect the reality of how the WOT necessarily must be created
> (socially/randomly). It may be possible to use existing signatures in the
> WOT
> to create hypercubes, but thats just another research path. Maybe you could
> detect what specific signatures you need to create a hypercube and ask
> those
> users to validate each other. The hypercube would sort of be a overlay
> structure used for computability and possibly for better guarantees on
> malicious nodes (people who make bad signatures on purpose or not).
>
> Improving WOT building and user accessibility:
>
> A user's own keyring provides the strongest level of verification. Certain
> types of validation interactions with people they know can be captured as
> key
> signatures. Manual signing of course would still be possible to help build
> connectivity in the WOT. Also, it will be necessary that a user has access
> to
> their private keys whenever possible. Most domains of communications don't
> require authentication, but its ideal that a user always has the option.
> This
> of course ties directly into the "Portable Shared Security Tokens"
> research by
> the Guardian Project[6].
>
> At some point a user may not be able to verify or validate through the WOT.
> Then you must fall back to the SSH model of simply remembering keys
> otherwise
> known as TOFU/POP (Trust on first use persistence of pseudonym). Verifying
> a
> user and keeping a signature is simply the stronger model of this and will
> also
> contribute signatures to the WOT. Trusting on first use is bad, so this
> should
> be minimized whenever possible or even disallowed for certain use cases.
>
> More details will need to worked out. What if you are forced to trust
> someone
> on first use, but are MITM'd? Then the next time you talk to this person
> (still
> MITM'd) you discover a valid link through the WOT to the real public key.
> It'd
> be nice to say that there is enough knowledge to abort your MITM
> connection,
> but I'm not yet convinced there is a clear hierarchy of validity here.
>
> 1) Automatically building WOT signatures by capturing validation events
> It'd be
> nice if every user can contribute to the WOT but also easily verify their
> own
> close friends they talk to. Protocols like OTR employ the socialist
> millionaire
> protocol for verification and ZRTP can leverage knowledge of a user's
> voice to
> verify each other's keys. This is a pretty strong verification I would
> argue.
> These exchanges should be captured as signatures. The more ways to capture
> these interactions the better. Android NFC 'key bumping' might be another
> valid
> out of band signing process and you could always find new ways.
>
> 2) Minimizing Trust Decisions through portability and use of key hierarchy.
> Ideally, if Alice validates\ Bob through the OTR socialist millionaire
> protocol, it'd be nice if this translates over to email as well. By tying
> multiple accounts to a single identity you can minimize the amount of
> verification or blind trust decisions a user must make. Thus you have a
> master
> key that has signatures for subkeys of each communication domain. So Alice
> and
> Bob talk on Jabber and validate each other's OTR keys. Then since they both
> have their master key present, these keys are exchanged after the OTR
> sequence
> and they both sign and verify each other's keys. Now when they use their
> email
> encryption and signing subkeys they can validate it through this same
> signature. Even if they are sending email on a different computer that
> doesn't
> have access to their private master key, as long as they know the public
> key of
> their master key -> this original verification signature can be passed
> along
> safely to their devices that have email since signatures are not private
> and
> cannot be forged. This improves portability as well.
>
> Open Problems: How can we minimize authority of the key servers? Users will
> have strong guarantees of people signed in their keyring but must trust the
> keyservers to establish single mappings between public key and unique
> communication domain identifier. Also, how would you handle discrepancies
> between user and keyserver if they wish to build and maintain their own
> WOT. Is
> it practical for users to initiate their own proof of control? Can
> everyone be
> a keyserver?
>
> Also one thing I realized about this mapping I'd want to enforce is that
> this
> is precisely what certificate authorities are supposed to be doing when
> they
> are doing their job. Except we want to capture this without centralized
> failures and retain the ability to create our own keys and signatures.
>
> So thank you for reading any of this email. I apologize for the verbosity,
> much
> of this writing I kept to help organize my own thoughts. Some of this
> material
> revolves around trying to develop some sort of community consensus around
> best
> practices for authentication infrastructure and some of this is research
> that
> still needs exploring, thinking, and results.
>
> I am a new grad student at UCSB and interned for the Guardian Project this
> past
> summer. I have been interested in authentication for some time, and
> discussions
> about Guardian Project's PSST project has been an initial building block
> for
> some of these thoughts.
>

Not sure I've grokked everything in this thread, but some thoughts.

Tying a key to a 'domain' (aka URI) is something that can be done already
using linked data.

I do so on my home page already:

http://melvincarvalho.com/

This contains my GPG key, fingerprint, hex_id, modulus and exponent.

Here is the data view of the same page:

http://graphite.ecs.soton.ac.uk/browser/?uri=http%3A%2F%2Fmelvincarvalho.com%2F

Scroll down to see the PKI fields.

I can use this key to sign and encrypt mail, for s/MIME as an x.509
certificate, to login via ssh and also encrypted chat on retroshare

I also have links to other people storing keys in a kind of web of trust.

What you call the WOT is really a Graph of Trust (GOT) or Network of Trust
(NOT) in so far as the Web is normally loosely associated with HTTP.

I think in terms of accessibility and usability we need a GPG equivalent of
what "hotmail" did to email.  This is what we call "webizing".  Then people
can make relations, sign and encrypt, over the web just as easily as they
do with desktop clients.  Obviously a huge task and the crypto in the
browser group will help.

I think what would be of immense value is a meta system that can handle web
based trust (eg bitcoin OTC) but also GPG strong set and others.  But
that's a big project and would probably take 1-2 full time people, which is
resource we probably dont have right now.


>
> Regards,
>
> Patrick Baxter
>
> References
>
> [1] "Distributed Identity Management in the PGP Web of Trust"
> http://www.seas.upenn.edu/~cse400/CSE400_2005_2006/Margolis/paper.pdf
>
> [2] GNU Privacy Handbook: Using Trust to Validate Keys
> http://www.gnupg.org/gph/en/manual.html#AEN385
>
> [3] Analysis of the Strong Set in the PGP Web of Trust
> http://pgp.cs.uu.nl/plot/
>
> [4] Neal McBurnett, PGP Web of Trust Statistics
> http://bcn.boulder.co.us/~neal/pgpstat/
>
> [5] pgp keys, pathfinder, statistics, references
> http://www.staff.science.uu.nl/~penni101/henkp/pgp/
>
> [6] Portable Shared Security Token http://guardianproject.info/wiki/PSST
>
> [7] Improving Webs of Trust Through Predetermined Graph Structure
> http://repository.lib.ncsu.edu/ir/bitstream/1840.16/617/1/etd.pdf
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
>
> iQGcBAEBCgAGBQJQurtXAAoJEByqL5nxaJPJGsoL/jcVEbx4qBwMdOTlFb0xYqUu
> Y8+i9x36GbB2MIuvoIKj9erKwrT/h+wzcuGVAXb2SaGRgCStPWxGjxrcE9y5dI/z
> g7Q8d77LeU6QjdLzr0arhLajuRkL9/E4KQfdJDUVtdqWPrRitx15mX50VXKwS36v
> AsJuFKXGqqncGXRERTQbGxqngBXMDME27a4emHcidi40ftd1yec3ESEBmLfNSPMx
> Nu49VnytjD8XguKC7gF7E1qnIQ5toFU2VlioZqfGFbrVnJf4wmSEU/aiMAYurLcx
> oYYGTNia9c66E6uUpTd4gXYMQOgEgRwhOfE1diQj3w9TXyaOzuFQDxvHTiID5Geg
> tJFqZxkOVzuragDrRAhwBaf3RoBwhDSgym8DkneRDq8EqgMHiYiQL240Jsp9j9RO
> cMOEpRgt4WjyMpy5iKNiU31W3OodsF+npX1MVGhWo7pIR3BFO+ee45wuOwnNjhOv
> SA9WE5iJ5sxTe+Ibjip9Yfr9llQIl+6XRrFALVAGcg==
> =a9bQ
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gnupg-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mayfirst.org/pipermail/guardian-dev/attachments/20121204/b5ed3f8a/attachment-0001.html>


More information about the Guardian-dev mailing list