Gunnar Wolf and Jorge Luis Ortega Arjona*
Received: December 16, 2021; Published: February 14, 2022
*Corresponding author:Jorge Luis Ortega Arjona, National Autonomous University of Mexico, National Polytechnic Institute, Mexico
With an ever increasing proportion of Internet traffic being encrypted, the role of transitive trust models (TTMs) is each day more important. From the main two TTM models, this text focuses on the decentralized Web of Trust, mostly used for e-mail exchange and document processing. Several high-profile vulnerabilities have been found in the Open PGP key server network, the main WoT implementation, leading it to an existential crisis. This article presents the main identified threat, and sketches several possible ways forward.
Encryption is no longer a domain of few enthusiasts; although it took over 20 years from the introduction Netscape’s Secure Socket Layer (SSL) protocol, which evolved and got standardized by the IETF into Transport Layer Security (TLS)  nowadays a large majority of the traffic traveling through the Internet is encrypted . Open PGP, a protocol mostly used for encrypted e-mail exchange, encrypted document storage and document signing, has been available since 1991 as implemented in the PGP program , an nowadays as an IETF standard with many compatible implementations . But contrary to public perception, encryption is only one of the benefits these protocols offer to the end user: Authentication, this is, ensuring the corresponding endpoint for an encrypted communication is the desired party, and not an impostor. This work is presented as a review of existing works on the field, during the initial stages of a research project with the intention of presenting a protocol that keeps the distributed, decentralized properties of the Web of Trust model.
In order to be sure about a given host’s identity, a trust model must be followed. The most common trust models are transitive (TTM), this is, a host A directly trusts the identity of a small set of identities
Web server operator, W, requests the certification services of CA, and after all relevant checks are done, gets a certificate chain including the following assertions:
When user A wants to communicate with W, A verifies TA2 is a trusted Trust Anchor (different vendors could present different lists, although in practice they consist of mostly the same systems) and that all of the certification paths are valid. Certificates will often include important information other than the identity of the parties, such as validity periods, kind of validation performed, etc. Endpoints should ensure the CA/Browser Forum recommendations are followed . In the Web of Trust model (WoT, see Figure 1(b)), used for Open PGP, each user will have a different view of trust in the graph of nodes constituting the graph’s reachable set (the subset of a graph bound together by inbound and outbound edges). In the example in Figure 1(b), if user Bob (b) wants to send a message to user Karen (k), a trust path must be found so that b k is possible. The following paths are available:
Certifications under WoT can also carry validity information, and can be assigned different weights. In the example graph, if edge a → d has a weight of 0.5, but edges g → e and e → d have weights of 0.8, and assuming trust weight assessment can be represented by multiplication, the second path could result in a greater trust assigned to k than the first one. Different models can be followed for assessing trust levels .While it must be mentioned that there are other trust models not based on transitivity, such as Trust On First Use (TOFU ) used for instant messaging networks or the fully-centralized models used for intra-corporate communications, TTMs are much better suited for communications in open, large-scale networks. Under the WoT, validating a certification path requires being able to find keys for the identities of a prospective endpoint, or for the different keys in the certification path. For Open PGP, specific key server software was developed and later standardized [7, 8]. Independent key servers synchronize with each other using the Gossip large set reconciliation protocol (Minsky and Trachtenberg 2002). Gossip ensures keys uploaded to any of the key servers participating in a network quickly reach all other servers.
Figure 1A: Centralized model: PKI-CA. User verifies there is a valid path of trust from a prespecified trust anchor to the destination they want to reach.
Figure 1B: Distributed model: WoT. User b builds trust paths towards target k along the existing edges of a graph. Figure 1: TTMs. Black lines denote all trust relationships in the network, and blue dashed lines mean trust paths followed from a user to their target.
Both TTMs presented have suffered from weaknesses either in the way users understand and use them, or in how their infrastructure is supposed to work. Said weaknesses are inherent to the model, not particular to an implementation, so they are much harder to counter than implementation weaknesses. Steps can be, and have been, taken to reduce the impact of them — but there is undeniably need to reduce the magnitude of simple attacks.
While it is undeniable their net effect on Internet security has been clearly positive, a major source of weaknesses in the TTM is incomplete user understanding. Users have been instructed to be wary of submitting confidential information to sites presenting a broken or open padlock or a warning triangle (see Figure 2(a), and to trust interactions with web sites for which the Web browser displays a closed padlock (see Figure 2(b)). While this does aid the users identify whether a connection is encrypted or not, it does not present information regarding the trust on the other site’s identity. Figures 2(c) and 2(d) show the certificate chain is only displayed after two clicks. In an important push to increase the percentage of encrypted connections over the last decade, the depth of identity verification has decreased, and zero- cost CAs have become available. Browsers have removed the visual distinction between Domain Validation and Extended Validation certificates as they were never clearly understood [9-11].By 2018, half of all the phishing sites present valid TLS certificates . CAs are required by the CA/Browser Forum to follow strict practices to protect their signing keys, and are required to be swift and open when handling any kind of security incidents , but over the last decade, several cases of rogue certificate issuance derived from leaked keys have been observed [13-16].Many more cases are quickly hidden and not reported, probably because of the loss of trust such an admission would imply . After the Heartbleed vulnerability was disclosed in 2013, several implementations for switching TLS to TOFU-based schemes were pro- posed , but did not manage to get enough user traction to be adopted beyond a small group of proposers.
Figure 2: Getting to the trust information for the identity of a Web site requires user interaction; this simplifies browsing for the user but makes the trust model much less visible. Screenshots taken from version 90 of the Chromium Web browser.
The different tools that comprise the Open PGP ecosystems are often criticized as an example of bad user interface design [19- 22]. As was discussed in the previous section regarding the PKI-CA model, Open PGP is known for its encryption abilities, but many users don’t pay attention at all to the authentication abilities it presents. This has led to the vast majority of keys not being at all linked to the WoT: According to Yakubov et al. 2020, at the time of their study, out of 5 217 474 keys carried by the key servers, over 84% of them existed in isolation, not having any certifications that would allow other users to establish trust in communications to them. 8.14% of the keys had a single certificate, 2.53% had only two — and only 1.71% of the keys had over 10 certificates. From the keys that are certified by other keys, only 6000 comprise the strong set (the largest bidirectionally interconnected set of keys). This means that, effectively, the WoT is useful only for roughly 1% of the keys.
The design of the SKS key server network is explicitly designed to be resistant to a threat model including national governments’ interference or censorship. Data submission to the key servers is not authenticated (anybody can upload arbitrary OpenPGP data).By relying on gossip-based set synchronization protocols, the network accepts new keys and updates on existing keys, but no information can be realistically removed from it — Any server still carrying a packet not found at other servers will inject it back into the network; there is no central coordination among key servers. The protocol provides no provision for removing unwanted information. This issue has carried legal issues for key server operators, being unable to respond to deletion requests based on national privacy laws newer than the implementation . The adoption of the General Data Protection Regulation (GDPR) by the European Union in 2016 makes this issue even more important. The Open PGP message format standard specifies keys should have a User ID packet that “consists of UTF-8 text that is intended to represent the name and email address of the key holder. By convention, it includes an RFC 2822 mail named, but there are no restrictions on its content” . This is, there is no enforced format on the contents of User ID strings. An attack on this model is, then, the mass creation and upload of non-meaningful keys, using the WoT as some way of graffiti pad . An example was presented by Lee at the Observe. Hack. Make. 2013 hacker gathering: by generating one Open PGP key per line with arbitrary ASCII characters in the field regularly used for the owner’s user ID (see Figure 3(a)), he signed his own Open PGP key (Figure 3(b)), resulting in the graffiti depicted in Figure 3(c).
The impact of this attack persé is not very high: The creation of some throwaway identities, and the use of the WoT in a way other than intended, but it resulted in highlighting a huge potential for abuse. But in 2018 –again, as a proof of concept, showing it would be impossible to properly take action against a GDPR request for information deletion – a program was published that enabled the encoding of arbitrary information as key and certifications material , allowing the abuse of the SKS network for arbitrary file storage. While this attack has not been widely observed, its effects can be devastating on the key server network, as it potentially becomes a distributed, append-only media, with no content removal facilities. If files deemed illegal to be possessed were to be uploaded in this way, this could make many server operators to shut down their servers, with a reasoning similar to . But while the above described exercise is not malicious, it does lead to a crippling attack known as certificate flooding or certificate poisoning.
If Alice has key kA and wants to communicate with Bob, who has key kB and the certificate chain CBK Alice connects to the key server network and requests for firstname.lastname@example.org. She verifies the results and imports the key into her local keyring. As Alice checks thoroughly to ensure that KB is certified by their mutual friends Charly (C) and Diana (D). Open PGP keys are also self-certified, as the self-signature carries information such as the validity period. She then introduces herself to Bob. At this point, we have:
Mallory wants to disrupt the communication between them, so she creates thousands of throwaway keys with no meaningful information; they do not even lead back to Mallory. So Mallory controls:
kM1, kM2, kM3,..., kM9999, kM10000
Mallory proceeds to certify kA with all of her throwaway keys and uploads the result to the key server, so that a request for kA will now return a substantially larger result:
Open PGP keys typically measure few kilobytes; very well connected keys (having many certificates) can reach the few hundreds. At this point, kA will measure tens or hundreds of megabytes and has become poisoned unusable. When Bob attempts to get kA his Open PGP client will be faced with orders of magnitude more information to what it is designed to handle. Observed failures from this range from the program freezing to corruption in Bob’s local key store. Alice’s key cannot be used anymore, and she has to migrate to a new k'A but she will also have to meet face to face to cross-verify identities to rebuild trust and enter again the WoT. And besides that, once k'A gained enough signatures to be useful, Mallory can repeat her attack.
While few actual such attacks have been reported , they are a looming threat to the Open PGP community as a whole, and are part of the reasons the key server network is perceived as dying .
There are several proposals on changes to different aspects of key server operations that in some way might lead to fixing the described situation; they can all be categorized under the broad suggestions presented by . While said document is merely enunciatively of different ways the stated problem could be tackled, it does not implement or analyze in detail any of the presented alternatives. It is, however, a very valuable starting point against which other analyzed works can be measured to. We have categorized works tackling the problems here described as follows:
Key discovery mechanisms: Given the attacks involve abusing the permissive trust scheme presented by key servers, the following proposals replace it by other mechanisms:
a) Wouters 2016 is a standard for implementing DNS-based Authentication of Named Entities (DANE) for Open PGP, where keys can be queried as specific records on the DNS zone corresponding to the mail address. DANE requires, however, the mail provider to present this centralized facility, not only becoming a single point of failure, but also requiring the domain owner to take interest in providing this facility; nowadays, with the amount of mail users in large-scale mail providers such as Google’s Gmail, a large amount of e-mail users would be effectively shut off this mechanism.
b) Koch 2021 proposes a Web Key Directory (WKD), presenting keys under the mail address’ domain (as DANE does), but with provisions for autonomous updates by users, although it still works in a centralized way. It shares many of DANE’s caveats.
c) Walfield and Koch 2016 presents an adequation of Gnu PG, the leading Open PGP implementation, to support the Trust On First Use model (TOFU), reasoning that most users don’t really use the WoT model, and that while theoretical strength of WoT is better, TOFU presents a better practical protection.
Server synchronization mechanisms: Recognizing part of the issue is Gossip’s impossibility to remove or stop serving given keys or certificates, the following works present different synchronization schemes:
a) Yakubov et al. 2020 suggests using an Ethereum-derived block chain for representing changes in the key server data. This solution can address propagation times of keys to the whole network and better bringing up to date servers that have fallen behind on the synchronization. While the key server operation would thus retain its decentralized way, it does introduce an administrator account that could remove toxic information from the block chain; this is often seen as antithetical to the decentralized philosophy of Open PGP.
b) Rucker 2017 presents a lighter, more efficient protocol than Gossip for synchronizing key servers, through the use of Invertible Bloom Filters (Epstein et al. 2011), allowing for more frequent polling for updates.
c) Lee 2019 presents a non-formal paper arguing the key server network state has reached a point of no return and identifies poisoned certificates as the “nail in SKS’s coffin”. This paper introduces the Hagrid verifying key server that among other properties, makes it impossible for keys to be poisoned by discarding all signatures from the server data — it allows for users to query for keys, but does away with all needed information for establishing a WoT.
Moving away from Open PGP: Open PGP can be characterized as belonging to a different era, and new protocols have been proposed to replace it, with different starting assumptions and threat models.
a) Borisov, Goldberg, and Brewer 2004 introduces the Off-the-Record (OTR) protocol, aimed at low-latency messageoriented interactions, such as instant messenger. It implements perfect forward secrecy, very short-lived session keys and explicit reputability. The trust model is TOFU, but with the possibility to authenticate a peer’s key off-band.
This review illustrates the issues faced by the transitive trust model as implemented by the Open PGP standard, the most widely used encryption model, and key for the interaction of several largescale geographically distributed software development projects. The problem presented is still an open issue to work on, and this article is limited to sketching the ground for study. Our working hypothesis is that it is possible to implement a key server network protocol that preserves the main characteristics of the Web of Trust transitive trust model, by performing relatively small modifications to the existing HKP key server interaction model.
Bio chemistryUniversity of Texas Medical Branch, USA
Department of Criminal JusticeLiberty University, USA
Department of PsychiatryUniversity of Kentucky, USA
Department of MedicineGally International Biomedical Research & Consulting LLC, USA
Department of Urbanisation and AgriculturalMontreal university, USA
Oral & Maxillofacial PathologyNew York University, USA
Gastroenterology and HepatologyUniversity of Alabama, UK
Department of MedicineUniversities of Bradford, UK
OncologyCirculogene Theranostics, England
Radiation ChemistryNational University of Mexico, USA
Analytical ChemistryWentworth Institute of Technology, USA
Minimally Invasive SurgeryMercer University school of Medicine, USA
Pediatric DentistryUniversity of Athens , Greece
The annual scholar awards from Lupine Publishers honor a selected number Read More...