| Network Working Group | P. Hallam-Baker |
| Internet-Draft | Comodo Group Inc. |
| Expires: April 19, 2014 | October 16, 2013 |
PRISM Proof Trust Model
draft-hallambaker-prismproof-trust-00
This paper extends Shanon's concept of a 'work factor' to provide an objective measure of the practical security offered by a protocol or infrastructure design. Considering the hypothetical work factor based on an informed estimate of the probable capabilities of an attacker with unknown resources provides a better indication of the relative strength of protocol designs than the computational work factor of the best known attack.
The social work factor is a measure of the trustworthiness of a credential issued in a PKI based on the cost of having obtained the credential through fraud at a certain point in time. Use of the social work factor allows evaluation of Certificate Authority based trust models, peer to peer (Web of Trust) models to be evaluated in the same framework. The analysis shows that each model has clear benefits over the other for some classes of user but most classes of user are served better by a combination of both.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 19, 2014.
Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Recent events have highlighted both the need for open standards based security protocols and the possibility that the design of such protocols may have been sabotaged. The community thus faces two important and difficult challenges, first to design an Internet security infrastructure that offers practical security against the class of attacks revealed, and secondly, to convince potential users that the proposed new infrastructure has not been similarly sabotaged.
The security of a system should measured by the difficulty of attacking it. The security of a safe is measured by the length time it is expected to resist attack using a specified set of techniques. The security of a cryptographic algorithm against a known attack is measured by the computational cost of the attack.
This paper extends Shanon's concept of a 'work factor' to provide an objective measure of the security a protocol or infrastructure offers against other forms of attack.
The term 'Computational Work Factor' is used to refer to Shanon's original concept.
One of Shanon's key insights was that the work factor of a cryptographic algorithm could be exponential. Adding a single bit to the key size of an ideal symmetric algorithm presents only a modest increase in computational effort for the defender but doubles the work factor for the attacker.
More precisely, the difficulty of breaking a cryptographic algorithm is generally measured by the work-factor ratio. If the cost of encrypting a block with 56 bit DES is x, the worst case cost of recovering the key through a brute force attack is x * 2^56. The security of DES has changed over time because the cost x has fallen exponentially.
While the work factor is traditionally measured in terms of the number of operations, many cryptanalytic techniques permit memory used to be traded for computational complexity. An attack requiring 2^64 bytes of memory that reduces the number of operations required to break a 128 bit cipher to 2^64 is a rather lower concern than one which reduces the number of operations to 2^80. The term 'cost' is used to gloss over such distinctions.
[Note that in the following analysis, the constraints of the IETF document format make use of the established notation impractical and a confusing mess, hence the departure from Shannon's notation.]
The Computational Work Factor ratio WF_C (A) of a cryptographic algorithm A, is the cost of the best known attack divided by the cost of the algorithm itself.
Modern cryptographic algorithms use keys of 128 bits or more and present a work factor ratio of 2^128 against brute force attack. This work factor is at least 2^72 times higher than DES and comfortably higher than the work factor of 2^80 operations that is generally believed to be about the limit to current attacks.
While an exceptionally well resourced attacker may gain performance advances through use of massive parallelism, faster clock rates made possible by operating at super-low temperatures and custom designed circuits, the return on such approaches is incremental rather than exponential.
Performance improvements may allow an attacker to break systems with a work factor several orders of magnitue greater than the public state of the art. But an advance in cryptanalysis might permit a potentially more significant reduction in the work factor.
The primary consideration in the choice of a cryptographic algorithm therefore is not the known computational work factor as measured according to the best publicly known attack but the confidence that the computational work factor of the best attack that might be known to the attacker.
While the exact capabilities of the adversary are unknown, a group of informed experts may arrive at a conservative estimate of their likely capabilities. The probability that a government attacker has discovered an attack against AES-128 with a work factor ratio of 2^120 might be considered relatively high while the probability that an attack with a work factor ratio of less than 2^64 is very low.
We define the hypothetical work factor function WF_H (A, p) as follows: If WF is a work factor ratio and p is an informed estimate of the probability that an adversary has developed an attack with a work factor ratio against algorithm A of WF or less then WF_H (A, p) = WF.
Since the best known public attack is known to the attacker, WF_H(A, 1) <= WF_C (A)
The inverse function WF_H' (A, WF) returns the estimated probability that the work factor of algorithm A is at least WF.
The hypothetical work factor and its inverse may be used to compare the relative strengths of protocol designs. Given designs A and B, we can state that B is an improvement on A if WF_H(A,p) > WF_H (B,p) for all p.
When considering a protocol or infrastructure design we can thus improve a protocol by either:
Unlike the computational work factor, the hypothetical work factor does not provide an objective measure of the security offered by a design. The purpose of the hypothetical work factor is to allow the protocol designer to compare the security offered by different design choices.
The task that the security engineer faces is to secure the system from all attacks whether the attacks themselves are known or unknown. In the current case it is known that an attacker is capable of breaking at least some of the cryptographic algorithms in use but not which algorithms are affected or the nature of the attack(s).
Unlike the computational work factor, the hypothetical work factor does not deliver an academically rigorous, publication and citation worthy measure of the strength of a design. That is not its purpose. the purpose of the hypothetical work factor is to assist the protocol designer in designing protocols.
Design of security protocols has always required the designer to consider attackers whose capabilities are not currently known and thus involved a considerable degree of informed opinion and guesswork. Whether correctly or not, the decision to reject changes to the DNSSEC protocol to enable deployment in 2002 rested in part on a statement by a Security Area Director that a proposed change gave him a bad feeling in his gut. The hypothetical work factor permits the security designer to model to quantify such intestinally based assumptions and model the effect on the security of the resulting design.
Security is a property of systems rather than individual components. While it is quite possible that there are no royal roads to cryptanalysis and cryptanalysis of algorithms such as AES 128 is infeasible even for the PRISM-class adversaries, such adversaries are not limited to use of cryptanalytic attacks.
Despite the rise of organized cyber-crime, many financial systems still employ weak cryptographic systems that are known to be vulnerable to cryptanalytic attacks that are well within the capabilities of the attackers. But fraud based on such techniques remains vanishingly rare as it is much easier for the attackers to persuade bank customers to simply give their access credentials to the attacker.
Even if a PRISM-class attacker has a factoring attack which renders an attack on RSA-2048 feasible, it is almost certainly easier for a PRISM-class attacker to compromise a system using RSA-2048 in other ways. For example persuading the target of the surveillance to use cryptographic devices with a random number generator that leaks a crib for the attacker. Analyzing the second form of attack requires a different type of analysis which is addressed in the following section on social work factor.
The motivation behind introducing the concept of the hypothetical work factor is a long experience of seeing attempts to make security protocols more robust being deflected by recourse to specious arguments based on the computational work factor.
For example, consider the case in which a choice between a single security control and a defense in depth strategy is being considered:
If the computational work factor for both algorithms X and Y is 2^128, both options present the same work factor ratio. Although Option B offers twice the security, it also requires twice the work.
The argument that normally wins is that both options present the same computational work factor ratio of 2^128, Option A is simpler and therefore Option A should be chosen. This despite the obvious fact that only Option B offers defense in depth.
If we consider the adversary of being capable of performing a work factor ratio of 2^80 and the probability the attacker has discovered an attack capable of breaking algorithms X and Y to be 10% in each case, the probability that the attacker can break Option A is 10% while the probability that an attack on Option B is only 1%, a significant improvement.
While Option B clearly offers a significant potential improvement in security, this improvement is only fully realized if the probabilities of a feasible attack are independent.
The defense in depth approach affords a significant improvement in security but an improvement that is incremental rather than exponential in character. With mutual reinforcement we design the mechanism such that in addition to requiring the attacker to break each of the component algorithms, the difficulty of the attacks is increased.
For example, consider the use of a Deterministic Random Number Generator R(s) which returns a sequence of values R(s)_1, R(s)_2 from an initial seed s.
Two major concerns in the design of such generators are the possibility of bias and that the seed value be somehow leaked through a side channel.
Both concerns are mitigated if instead of using the output of one generator directly, the value R1(s1) XOR R2(s2) is used where R1 and R2 are independent random number generators and s1, s2 are distinct seeds.
The XOR function has the property of preserving randomness so that the output is guaranteed to be at least as random as either of the generators from which it is built (provided that there is not a common failure mode). Further, recovery of either random seed is at least as hard as using the corresponding generator on its own. Thus the Hypothetical work factor for the combined system is improved to at least the same extent as in the defense in depth case.
But any attempt to break either generator must now face the additional complexity introduced by the output being masked with the unknown output of the other. An attacker cannot cryptanalyze the two generator functions independently. If the two generators and the seeds are genuinely independent, the combined hypothetical work factor is the product of the hypothetical work factors from which it is built.
While implementing two independent generators and seeds represents a significant increase in cost for the implementer, a similar exponential leverage might be realized with negligible additional complexity through use of a cryptographic digest of the generator output to produce the masking value.
In a traditional security analysis the question of concern is whether a cryptanalytic attack is feasible or not. When considering an indiscriminate intercept capability as in a PRISM-class attack, the concern is not just whether an individual communication might be compromised but the number of communications that may be compromised for a given amount of effort.
'Perfect' Forward Secrecy is an optional feature supported in IPSec and TLS. Current implementations of TLS offer a choice between:
Using the computational work factor alone suggests that the second scheme has little advantage over the first since the computational work factor of Diffie Hellman using the best known techniques 2^80 while the computational work factor for RSA 2048 is 2^112. Use of the perfect forward secrecy exchange has a significant impact on server performance but does not increase the difficulty of cryptanalysis.
Use of perfect forward secrecy with a combination of RSA and Diffie Hellman does not provide a significant improvement in the hypothetical work factor either if individual messages are considered. The RSA and Diffie Hellman systems are closely related and so an attacker that can break RSA 2048 can almost certainly break RSA 1024. Moreover computational work factor for DH 1024 is only 2^80 and thus feasibly within the reach of a well funded and determined attacker.
Use of perfect forward secrecy does provide an important security benefit when multiple messages are considered. While a sufficiently funded and determined attacker could conceivably break tens, hundreds or even thousands of DH 1024 keys a year, it is rather less likely that an attacker could break millions a year. The Comodo OCSP server receives over 2 billion hits a day and this represents only a fraction of the number of uses of SSL on the Internet. Use of perfect forward secrecy does not prevent an attacker from decrypting any particular message but raises the cost of indiscriminate intercept and decryption.
There is security in numbers: If every communication is protected by perfect forward secrecy the hypothetical work factor for decrypting every communication is the hypothetical work factor of decrypting one communication times the number of communications.
As previously discussed, cryptanalysis is not the only tool available to an attacker. Faced with a robust cryptographic defense, Internet criminals have employed 'social engineering' instead. A PRISM-class attacker may use any and every tool at their disposal including tools that are unique to government backed adversaries such as the threat of legal sanctions against trusted intermediaries.
Although attackers can and will use every tool at their disposal, each tool carries a cost and some tools require considerable advance planning to use. It is conceivable that the AES standard published by NIST contains a backdoor that somehow escaped the extensive peer review. But any such effort would have had to have begun well in advance of 1998 when the Rijndael cipher was first published. Subversion of cryptographic apparatus such as Hardware Security Modules (HSMs) and SSL accelerators faces similar constraints. A HSM may be compromised by an adversary but the compromise must have taken place before the device was manufactured or serviced.
Just as computational attacks are limited by the cryptanalytic techniques known to and the computational resources available to the attacker, social attacks are limited by the cost of the attack and the capacity of the attacker.
The Cost Factor C(t) is an estimate of the cost of performing an attack on or before a particular date in time (t).
For the sake of simplicity, currency units are used under the assumption that all the resources required are fungible and that all attackers face the same costs. But such assumptions may need to be reconsidered when there is a range of attackers with very different costs and capabilities. A hacktivist group could not conceivably amass the computational and covert technical resources available to the NSA but such a group could in certain circumstances conceivably organize a protest with a million or more participants while the number of NSA employees is believed to still be somewhat fewer.
The computational and hypothetical work factors are compared against estimates of the computational resources of the attacker. An attack is considered to be infeasible if that available computational resources do not allow the attack to be performed within a useful period of time.
The cost factor is likewise compared against an incentive estimate, I(t) which is also time based.
An attack is considered to be productive for an attacker if there was a time t for which I(t) > C(t).
An attack is considered to be unproductive if there is no time at which it was productive for that attacker.
Unlike Cost Factor for which a lower bound based on the lowest cost and highest capacity may be usefully applied to all attackers, differences in the incentive estimate between attackers are likely to be very significant. Almost every government has the means to perform financial fraud on a vast scale but only rarely does a government have the incentive and when governments do engage in activities such as counterfeiting banknotes this has been done for motives beyond mere peculation.
While government actors do not respond to the same incentives as Internet criminals, governments fund espionage activities in the expectation of a return on their investment. A government agency director who does not produce the desired returns is likely to be replaced.
For example, when the viability of SSL and the Web PKI for protecting Internet payments was considered in the mid 1990s, the key question was whether the full cost of obtaining a fraudulently issued certificate would exceed the expected financial return where the full cost is understood to include the cost of registering a bogus corporation, submitting the documents and all the other activities that would be required if a sustainable model for payments fraud was to be established.
For an attack to be attractive to an attacker it is not just necessary for it to be productive, the time between the initial investment and the reward and the likelihood of success are also important factors. An attack that requires several years of advance planning is much less attractive than an attack which returns an immediate profit.
An attack may be made less attractive by
In the cost factor analysis it is assumed that all costs are fungible and the attack capacity of the attacker is only limited by their financial resources. Some costs are not fungible however, in particular inducing a large number of people to accept a forgery without the effort being noticed requires much more than a limitless supply of funds.
In a computational attack an operation will at worst fail to deliver success. There is no penalty for failure beyond having failed to succeed. When attempting to perpetuate a fraud on the general public, every attempt carries a risk of exposure of the entire scheme. When attempting to perform any covert activity, every additional person who is indoctrinated into the conspiracy increases the chance of exposure.
The totalitarian state envisioned by George Orwell in 1984 is only possible because each and every citizen is in effect a party to the conspiracy. The erasure and replacement of the past is possible because the risk of exposure is nil.
In 2011 I expressed concern to a retired senior member of the NSA staff that the number of contractors being hired to perform cyber-sabotage operations represented a security risk and might be creating a powerful constituency with an interest in the aggressive militarization of cyberspace rather than preparing for its defense. Subsequent disclosures by Robert Snowden have validated the disclosure risk aspect of these concerns.
Empirically, the NSA, an organization charged with protecting the secrecy of government documents, was unable to maintain the secrecy of their most important secrets when the size of the conspiracy reached a few ten thousand people.
The community of commercial practitioners cryptographic information security is small in size but encompases many nationalities. Many members of the community are bound by ideological commitments to protecting personal privacy as an unqualified moral objective.
Introducing a backdoor into a HSM, application or operating system platform requires that every person with access to the platform source or who might be called in to audit the code be a party to the conspiracy. Tapping the fiber optic cables that support the Internet backbone requires only a small work crew and digging equipment. Maintaining a covert backdoor in a major operating system platform would require hundreds if not thousands of engineers to participate in the conspiracy.
The Social Work Factor WF_S(t) is a measure of the cost of establishing a fraud in a conspiracy starting at date t. The cost is measured in the number of actions that the party perpetrating the fraud must perform that carry a risk of exposure.
In general, the Social Work Factor will increase over time. Perpetrating a fraud claiming that the Roman emperor Nero never existed today would require that millions of printed histories be erased and rewritten, every person who has ever taught or taken a lesson in Roman history would have to participate in the fraud. The Social Work Factor would be clearly prohibitive.
The Social Work Factor of perpetrating such a fraud today is prohibitive, the cost in the immediate aftermath of Nero's assassination in 68 would have been considerably lower. While the emperor Nero was obviously not erased from history there is a strong consensus among Egyptian archeologists that something of the sort happened to Tutankhamun before the discovery of his tomb by Howard Carter.
The Prism-Proof Email testbed attempts to facilitate the development and deployment of a new email privacy protection infrastructure by dividing the problem into the parts for which there are known, well established (if not necessarily perfect) solutions and the parts for which there are not with clearly defined interfaces between the two parts.
The Trust Publication Web Service is a JSON/REST Web service that supports the publication of all existing forms of trust assertion (PKIX, OpenPGP, SAML). For the sake of future simplicity, a new ASN.1 message format for OpenPGP-style key endorsement is proposed so that all the forms of trust assertion that might be used in a PKI may be expressed without recourse to multiple data encoding formats. The Trust Publication Web Service need not be a trusted service since its role is essentially that of a proxy, routing messages such as certificate requests to the appropriate destination(s).
The Omnibroker Web Service is a trusted service that a mail user agent or proxy can query to determine which security enhancements (encryption, signature, etc.) should be added to an outbound message (among other functions).
Between the Trust Publication Web Service and the Omnibroker service sits the hard research problem of how to make sense of and what value to place on the CA issued certificates, peer to peer key endorsements, revocation information and other signed assertions that might exist.
Robust implementation of public key cryptography allows the signature on a signed assertion to be verified as belonging to a holder of the corresponding signature key with near certainty. But such an assertion can only be considered trustworthy if the purported signer is trustworthy and is the actual holder of the corresponding signing key, claims that are in turn established by more signed assertions. Expanding the scope of our search increases the number of documents on which we are relying for trust rather than answering the question we wish to answer.
Attempting to analyze the trustworthiness of a signed assertion in a heterarchical topology such as Phil Zimmerman's Web of Trust leads to an infinite regression. Alice may see that Bob's key has been signed by Carol, Doug and Edward but this should only give Alice more confidence in the validity of Bon's key if she knows that Carol Doug and Edward are distinct individuals.
Probability is a model of events that are random. An attack is a conscious act on the part of an attacker and is only random insofar as the attacker's motive may not require a particular choice of victim or method. In such cases the particular attack is 'random' from the point of view of the victim but that an attack would take place is due to the fact that the attacker had motive, means and opportunity.
The motive for an attacker depends on the perceived rather than the actual difficulty of breaking a system. It might be some time before a competent attacker attempts to break an insecure system that is for some reason generally believed to be secure. But the rate of attack is likely to increase rapidly once the vulnerability is widely known. The system has not become less trustworthy over time, rather the system was always untrustworthy and it is only the consequences of that fact that have changed.
Analyzing the trustworthiness of a Web of Trust using an estimate of the probability that an assertion might be fraudulent is unsatisfactory because it requires us to provide as an input to our calculations the very quantity we are trying to arrive at as an output.
Attempting to estimate the probability of default for each assertion in a Web of trust leads us to an infinite recursion as Alice trusts Bob trusts Carol trusts Alice. We can define the inductive step but have no base case to ground it with.
Another frequently proposed metric for analyzing the trustworthiness of assertions is 'reputation'. Reputation is a measure of risk based on reports of past behavior.
Reputation has proved somewhat effective in online restaurant reviews. A restaurant that receives a high number of good reviews is likely to be worth visiting but ratings based on a small number of reviews can be wildly inaccurate. A glowing review may have been written by a satisfied customer or by an unscrupulous proprietor. A series of negative reviews may be written by unsatisfied customers or a jealous competitor.
Restaurant reviews work because there is a widely shared understanding of what makes a good or a bad restaurant. There is no similar shared understanding of the quality of a public key validation process except among specialists in the field.
'Reputation based' systems have proved highly effective at controlling email abuse but these systems use a large quantity of empirical data including from honeypot email servers, expert analysis of abuse traffic and content analysis to arrive at reputation scores. It is the action of the curator that turns the raw data into a useful measure of risk rather than the mechanical application of a clever algorithm.
There is a good argument to be made for introducing a curator into a PKI trust model but that is an argument about who should perform the analysis rather than how the analysis is to be performed.
The problem of grounding the Web of Trust is solved if there is available a notary authority whose trustworthiness is beyond reasonable dispute. Once a trust assertion has been notarized by such a notary authority, the cost of forgery becomes the cost of suborning the notary authority.
As is demonstrated later, use of linked timestamps and cross-notarization amongst notaries makes it possible to establish a timestamp notary infrastructure such that perpetrating a forgery requires each and every notary in the infrastructure is compromised.
The analysis of the set of trust assertions begins by asserting a Social Work Factor to the earliest assertion prior to the time at which it was notarized. This provides the base case of the induction from which the rest of the analysis proceeds.
As previously described, the purpose of the Social Work Factor is to support the design process by allowing the consequences of different design approaches to be considered.
When designing a trust infrastructure, there are two different attacks that need to be considered. First there is the attack where a credential is issued for an entirely fictitious persona, secondly there is the attack where a credential is issued to an impostor impersonating a real persona.
The consequences of the two attacks are very different, particularly where a confidentiality infrastructure is concerned. Indeed it might be considered desirable to encourage participants to create and use fictitious personas to provide anonymity for their actions in certain circumstances. An impostor who gains a credential for a real person can use it to persuade relying parties that their communications are confidential when they are in fact compromised and can steal the use of the target's reputation.
The context of an attack is also important. The confidentiality of the private communications of an individual is an issue for that individual and their correspondents alone. The confidentiality of the communications of an individual acting for their employer is much more complex. In addition to the employer having an interest in protecting the confidentiality of the communication, there may be a legitimate employer interest in being able to view the contents. For example, it is now generally accepted in many countries that most government employees do not have a right of privacy from the people who they ultimately work for unless their job function falls into a narrowly scoped exception.
A trust specifier is a mechanism that identifies a public key either directly (e.g. a self-signed certificate) or indirectly (e.g. a Key identifier).
Trust specifiers are not trust assertions but may be used to create trust assertions. For example, an OpenPGP fingerprint does not make any statement about the owner of a public key but an OpenPGP fingerprint printed on a business card is an explicit claim that the specified public key may be used to send encrypted email to the individual named on the card.
PGP introduced the use of key fingerprints as the basis for key exchange. A cryptographic digest value is computed from the user's public key and used as the basis for key endorsement (called key signing in the PGP terminology).
The term 'fingerprint' has no formal definition in the PKIX specifications but the term is widely used to refer to a message digest of the entire contents of a certificate. Since this use is incompatible with the PGP usage, the term Key Identifier is prefered as this is unambiguous in both contexts.
In PKIX, the key identifier value is a value chosen by the issuer to uniquely identify a public key. The Key Identifier value of the issuing public key is specified using the authorityKeyInfo extension and the Key Identifier value of the subject is specified in the subjectKeyIdentifier extension.
While a PKIX Key Identifier is not required to have the strong binding to the corresponding public key that an OpenPGP identifier does, a profile could require that certificates specify 'strong' Key Identifiers formed using a cryptographic message digest of the public key parameters.
Strong Key Identifiers are not trust assertions but they may be used to facilitate the creation of trust assertions through key signing, a form of the endorsement mechanism discussed below.
Strong Key Identifiers may also be used to publish informal key assertions by adding them to a business card or a Web Page. Such uses might be facilitated through definition of appropriate URI and QR code formats.
In the context of PKI, the term 'certificate' is generally understood to refer to an X.509 public key certificate that binds a name and/or an Internet address to a public key.ublic key.
A certificate may be either a self signed certificate or a CA issued certificate. Since the work factor of creating a self-signed certificate is negligible, such certificates demonstrate little in themselves but present the subject's public key data in a format that is compatible with many existing applications.
As with Key Identifiers, a self signed certificate is not a useful trust assertion in its own right but may be used to facilitate the creation of trust assertions through notarization or endorsement. A public key certificate may also be used as the basis for making a Certificate Signing Request to a Certificate Authority.
In a PKI, a trust assertion makes a statement about the holder of a public key. In the PKIX model as currently deployed and used, the only forms of trust assertion are Key Signing Certificates and End Entity Certificates. In the OpenPGP model every user is also a trust provider and trust assertions are created in peer-to-peer fashion to create a Web of Trust.
A Certificate Authority (CA) is a trusted third party that issues digital certificates. A private CA issues certificates for a closed community of relying parties, a public CA issues certificates without restriction on the relying parties.
In the Web PKI, providers of Web browsers and platform providers embed the trust anchors of selected public Certificate Authorities into the application as default trust providers.
Operation of a Certificate Authority involves two types of certificate. A certificate is either a certificate signing certificate or an end entity certificate. While it is possible for a Certificate Authority to lose control of a signing key used to issue certificates, the Social Work Factor for such attacks can be made prohibitively high.
A CA Certificate Policy defines (among other things) the validation criteria that the CA applies before deciding to issue a certificate. A certificate policy is designed to provide a balance between the social work factor presented to an attacker and the cost to the CA and the subject. The CA-Browser forum Extended Validation practices are designed to present a very high social work factor to attackers while Domain Validation presents a significantly lower cost to both subjects and attackers.
The EV guidelines in particular are designed to present a social work factor that increases each time an attacker attempts an attack. Registering one corporation is relatively straightforward. Registering a corporation in a way that prevents ownership being traced back to the owners is rather more difficult. Registering hundreds of false front corporations is considerably harder as any common link between the corporations means that if one corporation is discovered to be a front for fraudulent purposes, the rest will come under close scrutiny. scrutiny.
A major advantage of the CA certificate issue approach is that they allow a high degree of trust to be established very quickly while it takes a considerable time to establish trust in a pure Web of Trust approach.
The main drawback to the CA issue approach is in providing trust to individuals for personal use rather than corporate or government entities or to employees working for such entities. Corporations and Government entities invest in obtaining EV validated certificates as a cost of doing business that has an established return. There is no obvious return on obtaining a similar high assurance credential for personal use but validating an individual's credentials is just as complicated as validating the credentials of a corporation. The history of the UK National Identity card suggests that there is no reason to expect that the cost of provisioning credentials would be significantly reduced at scale.
The CA issue model has been successfully applied to issue of credentials to employees for use within an organization and such credentials are occasionally used for external purposes such as S/MIME email. But such certificates are not intended for personal use and are typically revoked when employment ends.
In the OpenPGP model every key holder is a trust provider and every key may be used to provide trust through 'key signing'. The trust value of key signing depends on how close the relying party is to the signer. A key that I have signed myself is far more trustworthy than a key signed by a friend of a friend of a friend.
The Social Work Factor of forging an individual key signing is low but could be fixed in time through use of a notary. A recent key signing purporting to be for the public key of Barack Obama would have negligible evidentiary value unless produced by someone very close to me or endorsed through other means. A key signing that had been notarized during his time as a Harvard student would be considerably more trustworthy.
As the separation between the relying party and the signer becomes larger it becomes increasingly desirable to require multiple independent key signing paths. The Social Work Factor combined with an absolutely reliable notary service provide a firm basis for evaluating the trust value of such Webs of trust: The trustworthiness of a key is dependent on whether the incentive to create a forgery ever exceeded the Social Work Factor of performing a forgery.
Use of peer-to-peer key signing does provide a viable model for establishing high assurance credentials for personal use but establishing a high degree of assurance is like making the best quality Scotch whisky: the product takes an inordinately long time to reach maturity. It is hard to see how key-signing could be made a viable model for commercial use. It is an especially poor fit for issue of credentials to employees as the employer has no control over the issue or use of the credential and no ability to revoke the credential when an employee is terminated.
One advantage frequently cited for OpenPGP over PKIX is that there is no CA role and the infrastructure is therefore 'free'. Neither the premise, nor the conclusion holds, Many profitable businesses have been built on the basis of open source software and a Web of Trust that reached critical mass would offer abundant opportunities to companies with PKI expertise.
Nor is the lack of business stakeholders in an infrastructure necessarily an advantage. One of the reasons that the Web PKI has been successful is that there are many businesses that promote the use of SSL certificates.
Considering the Social Work Factor presented by trust assertions in the PKIX and OpenPGP model establishes clear benefits to both approaches. Each model best suits a different community.
One approach to a next generation PKI therefore would be to simply enable the use of either scheme in any application. This is not the best approach however as it leaves the email security market in a BetaMax/VHS standards war that has been stalemated for almost two decades. Further, attempting to maintain the use of two different PKIs leads to an unnecessary increase in complexity.
A PKI that combines the PKIX and OpenPGP approaches offers clear advantages over both. For many practical reasons that will only be summarised here, it is better to extend the existing PKIX infrastructure to support Key Signing rather than start from the OpenPGP message formats or attempt to design a system based on a new encoding format. These include the deployed base of S/MIME email clients, the use of PKIX to support SSL and the widespread support for PKIX in common code platforms.
Rather than attempting to force peer-to-peer Key Signing model into the existing PKIX model, a new structure, the Key Endorsement is proposed instead. While it is technically possible to use PKIX cross certificates as a substitute for PGP Key Signing, the legacy PKIX infrastructure is designed on the assumption that a cross certificate is either completely trustworthy or completely untrustworthy. It is better to introduce a new data format to represent new semantics than to attempt to retrofit new semantics into a legacy format with a deployed infrastructure.
I propose the introduction of a Key Endorsement, similar to a PKIX certificate except that:
Adding Key Endorsements to the PKIX model allows the use of both trust models in combination.
Key endorsement may also be used to endorse keys of peers. While the ability of the 16 year old Alice to accurately validate the public keys of her peers is questionable, the value of a notarized endorsement increases over time.
Relying on peer endorsement alone requires that the relying party be 'close' to the signer. Using a combination of CA issued certificates and Key Endorsements allows a high social work factor to be established even for a remote population. It is quite feasible for an attacker to generate a network of one, a hundred or even a million key signing events but generating a fraudulent network that contains a mixture of CA validated certificates and key endorsements has a much higher social work factor.
Self endorsement is a special form of endorsement as a person is least likely to make false statements that might harm their own security. Although this is possible in the case that coercion or undue psychological pressure is applied.
A user may be expected to have multiple public keys issued over the course of their life, for use at school, university, at different employers and for personal use. In the existing PKIX model each of these keys are independent. Key endorsement allows a user to countersign new keys with older keys, establishing a personal web of trust that develops over time so that the social work factor is preserved and increased over time rather than starting from scratch each time a certificate is issued.
For example, Alice is issued a certificate at school which she uses to sign a key endorsement for a personal key she creates. When Alice goes to University, she endorses her university key with her personal key and vice versa. On graduating, Alice becomes a journalist. Sources can send her encrypted messages containing tips confident in the knowledge that Alice is the same Alice who attended the high school and university listed in her official biography.
A PGP Key Signing party is an event held to facilitate exchange of PGP fingerprints. Like the use of hashtags and many other important constructs in social media, key signing parties are a practice that have arisen out of use rather than being part of the original model.
Recognizing a Key Endorsement Party as being a special form of peer endorsement enables special consideration when making a trust evaluation. It is not practical for a thousand attendees at an international conference to perform mutual key endorsements with every other participant (a half million pairs!) but it is entirely practical to establish a scheme in which anyone who gets their key endorsed by some number (e.g. five) of qualified Key Endorsers will have their key endorsed by the Key Endorsement Party key at the end.
Trust Meta Assertions are trust assertions that make statements about other trust assertions
Real users and real administrators make mistakes from time to time. Private keys are lost or stolen or misused. Any system that does not provide a mechanism for forgiving mistakes is unlikely to be practical in the real world.
Revocation checking limits the incentive for attack by allowing the time window of vulnerability to be limited in the case of a fraudulent certificate issue or that a private key is discovered to be lost or stolen. This does not increase the social work factor but decreases the value of an attack.
Notarization or a Trust Assertion of Key Identifier by a trustworthy notary allows the social work factor of forging the trust assertion or key identifier to be raised to an infeasible level for dates after the notarization took place.
While a traditional notary might be suborned relatively easily, a digital notary can be constructed in such a fashion that post dating a notary assertion by more than a few hours or days is infeasible.
Certificate Transparency is a proposed infrastructure to (Laurie et. al.). [[Describe]
Publishing issued certificates increases the probability that an attempted fraud will be discovered and thus increases the Social Work Factor and reduces the incentive.
The X.509/PKIX and OpenPGP infrastructures are not the only infrastructures that have been proposed by they are the only large scale infrastructures which large numbers of users rely on today. The Social Work Factor over time may be used to evaluate alternative PKI options that have not (yet) achieved widespread use.
Like PKIX, DNSSEC is based on a hierarchical trust model. Unlike PKIX, DNSSEC is only capable of making statements about DNS names.
The Social Work Factor is not a useful tool to analyze DNSSEC assertions because there is no historical dimension to the DNSSEC infrastructure. The trustworthiness of a DNSSEC assertion depends on the trustworthiness of the root operator, the TLD registry and the party that signed the corresponding DNS zone. If these are trustworthy then so is the assertion, there is no alternative if not.
While the root and registry operators have strong commercial incentives not to default, a default may be coerced through government action and relying parties have no independent means to determine if a default has taken place.
The chief distinguishing characteristic of SPKI is that SPKI names are not universal. While this has the interesting effect of simplifying the evaluation of trust within the SPKI naming infrastructure, this effect is lost when attempting to send an email because the Internet email system is based on the assumption that the namespace is universal. It does not make sense to talk about 'Alice's bob@example.com' (although UUCP email did use a scheme of that type.
Identity based cryptography is a frequently touted 'alternative' to conventional public key cryptography in which the public key of each subject is a deterministic function of their name and a master public key which is known to everyone. Each user obtains their private key from the party that created the master public key pair using the master private key.
While many benefits have been claimed for the Identity based approach, applying to the holder of the master private key for a private key offers no benefits to key holders over applying to a certificate from a CA.
Identity based cryptography does offer relying parties the ability to obtain the public key for a counterparty without the need to communicate with another party, but this is hardly much of an advantage unless there is no means for certificates to be passed in-ban and there is no advantage at all if an external source has to be queried to obtain the status of a public key to determine that the private key has not been reported lost or compromised.
The simplicity of certificate chain validation and status checking in Identity Based Cryptography is the result of the technology being unable to support these features rather than the features being unnecessary.
The ability to determine that a trust event occurred before a certain point in time increases the social work factor for forging the event after that point in time. If suborning the notary is infeasible, the Social Work Factor is raised to an infeasible level.
Harber and Stornetta proposed a notary that produced a 'catenate certificate' in which each notary output is fed as an input into the next. It is thus impossible to insert notary events between two prior notary events without breaking the cryptographic algorithm used for authentication.
A chain of notary events may be fixed in time by notarizing events that are unpredictable in advance but known with a high degree of certainty afterward. For example the weekly lottery numbers or the closing prices on various equity markets.
The principal drawback to grounding the notary chains using external events is that the ability of a party to verify the trustworthiness of the notary is bounded by the trustworthiness of the reports of the external events used for verification.
A better approach is to have establish a large number of independently operated notaries and a procedure for cross notification that ensures that no notary can default unless every other notary defaults. The Social Work Factor of suborning any notary then becomes the Social Work Factor of suborning every notary and erasing all histories for their notary events.
For ease of explanation, a two tier notary infrastructure is envisaged in which a notary is either a local notary or a meta notary.
Local notaries are notaries that produce a catenate log of notarization requests submitted by its users. The current value of the notary chain is presented to one or more meta-notaries at regular time intervals (e.g. an hour) to prevent backdating of notary claims and notarizes the output of one or more meta notaries at regular intervals to prevent predating.
Meta notaries are notaries that only notarize the requests submitted by local notaries and by other meta notaries. Before accepting a notarization request, a meta notary audits the actions of the notary making the request to ensure that the time-stamp values etc. are consistent and correct.
The schedule of peer to peer notification among meta notaries is set such that a notary request made to any of the local notaries served will affect the output of every meta notary within a predetermined period of time.
To make use of such a notary infrastructure, a relying party chooses at least one meta notary and obtains and maintains a record of the catenate certificate chain over time. The trust chain of the chosen meta notary may then be used to verify any notary assertion presented by any other meta notary which may in turn be used to verify any notary assertion from a local notary that participates in the scheme.
A significant benefit of this approach is that the ability to verify notary assertions is assured even if the Local Notary that originally produced it ceases functioning. All that is necessary for the continued operation of the system to be assured is for the pool of meta notaries to be sufficiently large to render suborning all of them infeasible.
It has not escaped the notice of the author that the social work factor might be applied as a general metric for assessing the viability of a political conspiracy hypothesis.