Monday, October 2, 2017

The shape of a cryptographic keyring: How is the Debian project social structure like?

By: Gunnar Wolf 
Associate editor: Stefano Zacchiroli (@zacchiro)

Quite often, we can be quite familiar with a set of data; But looking at it with a different viewpoint reveals a completely unexpected reality.

I am part of the keyring-maint group in Debian: The developers that manages the cryptographic keyring through which developers identify themselves for most of our actions — Most important, voting in project decisions and uploading software.

There are two main models for establishing trust via cryptographic signatures: The centralized, hierarchical model based on Certification Authorities (CAs) from where all trust and authority stems and flows only downwards, and a decentralized one, the Web of Trust where each participant in the network can sign other participants' public keys; the first one is most often used in HTTPS (encrypted Web), and our project uses a specific mode of the second one, which we have termed the Curated Web of Trust [1].

Cryptographic signatures are way more secure as identifications to the omnipresent but very weak username/password scheme. However, technological advances must be factored in. Being already 24 years old, Debian is a very long-lived free software project, and it sports a great retention: Many of its developers have been active for over ten years. In the late 1990s, the recommended key size was 1024 bits — Public key cryptography is very expensive computationally, and said key size was perceived secure enough for the foreseeable future. However, according to a study on algorithms and keysizes in 2012, [2] this key size is today good only for Short-term protection against medium organizations, medium-term protection against small organizations — Clearly not below our required standards.

Our group had started pushing for migration to stronger keys back in 2009. By 2014, as the Figure 1 shows, we had achieved the migration of half of the developers to stronger keys; But the pace of migration was really insufficient. At the Debian Developers' Conference that year (DebConf14), we announced that by January 1st, 2015, we would remove all keys shorter than 2048 bits.

Figure 1: Number of keys by length in the Debian Developers keyring, between mid 2008 and late 2015

The migration process was hard and intensive. Given the curated Web of Trust model followed, our policy is that, for a key replacement, a new key must be signed by two currently trusted keys in our keyrings; being Debian a globally distributed project, many people are simply unable to meet other developers. This migration process resulted in us losing close to a fourth of all keys (that is, a fourth of all Debian Developers could no longer perform their work without asking somebody to "sponsor" their actions), we felt it to be quite successful. This migration prompted a deeper analysis into what the keyrings were able to tell about the developers themselves.

Trying to find any emergent properties, we graphed the signatures in the keyring at different points in time. Although most times we got just a useless huge blob, we observed a very odd division starting around 2011; Figure 2 shows the graph close to the point where this split was maximum: January 2012.

Figure 2: Trust relationships in the Debian keyring near the maximum /split/, January 2012

Then, trying to find the meaning of this split, we colored the edges according to their relative age — How long before each of the snapshots was each of the signatures made. This is shown for the above presented keyring in Figure 3.

Figure 3: Trust relationships in the Debian keyring near the maximum /split/, January 2012, graphed by signature age: (Blue: less than one year old; green: one to two years old; yellow: two to three years old; orange: three to four years old; red: over four years old)

Our hypothesis was that the red blob mostly represents an earlier generation of Debian Developers, who have mostly faded from project activity. We presented our findings last May at the 13th International Conference on Open Source Systems [3], together with a first foray into a statistical analysis on key aging and survival.

This rich data set can still yield much more information on the Debian project's social interactions. It's basically just a matter of finding other angles from which to read it!

[1] Wolf, G. E., & Gallegos-GarcĂ­a, G. (2016). Strengthening a curated web of trust in a geographically distributed project. Cryptologia, 1-16.
[2] ECRYPT, I. (2012). Yearly Report on Algorithms and Keysizes (2011-2012), Rev. 1.0. ECRYPT II Network of Excellence (NoE), funded within the Information Societies Technology (IST) Programme of the European Commission’s Seventh Framework Programme (FP7).
[3] Wolf, G., & Quiroga, V. G. (2017, May). Progression and Forecast of a Curated Web-of-Trust: A Study on the Debian Project’s Cryptographic Keyring. In IFIP International Conference on Open Source Systems (pp. 117-127). Springer, Cham.