Hanno's blog

In discussions around the PGP ecosystem one thing I often hear is that while PGP has its problems, it's an important tool for package signatures in Linux distributions. I therefore want to highlight a few issues I came across in this context that are rooted in problems in the larger PGP ecosystem.

Let's look at an example of the use of PGP signatures for deb packages, the Ubuntu Linux installation instructions for HHVM. HHVM is an implementation of the HACK programming language and developed by Facebook. I'm just using HHVM as an example here, as it nicely illustrates two attacks I want to talk about, but you'll find plenty of similar installation instructions for other software packages. I have reported these issues to Facebook, but they decided not to change anything.

The instructions for Ubuntu (and very similarly for Debian) recommend that users execute these commands in order to install HHVM from the repository of its developers:



The crucial part here is the line starting with apt-key. It fetches the key that is used to sign the repository from the Ubuntu key server, which itself is part of the PGP keyserver network.

Attack 1: Flooding Key with Signatures

The first possible attack is actually quite simple: One can make the signature key offered here unusable by appending many signatures.

A key concept of the PGP keyservers is that they operate append-only. New data gets added, but never removed. PGP keys can sign other keys and these signatures can also be uploaded to the keyservers and get added to a key. Crucially the owner of a key has no influence on this.

This means everyone can grow the size of a key by simply adding many signatures to it. Lately this has happened to a number of keys, see the blog posts by Daniel Kahn Gillmor and Robert Hansen, two members of the PGP community who have personally been affected by this. The effect of this is that when GnuPG tries to import such a key it becomes excessively slow and at some point will simply not work any more.

For the above installation instructions this means anyone can make them unusable by attacking the referenced release key. In my tests I was still able to import one of the attacked keys with apt-key after several minutes, but these keys "only" have a few ten thousand signatures, growing them to a few megabytes size. There's no reason an attacker couldn't use millions of signatures and grow single keys to gigabytes.

Attack 2: Rogue packages with a colliding Key Id

The installation instructions reference the key as 0xB4112585D386EB94, which is a 64 bit hexadecimal key id.

Key ids are a central concept in the PGP ecosystem. The key id is a truncated SHA1 hash of the public key. It's possible to either use the last 32 bit, 64 bit or the full 160 bit of the hash.

It's been pointed out in the past that short key ids allow colliding key ids. This means an attacker can generate a different key with the same key id where he owns the private key simply by bruteforcing the id. In 2014 Richard Klafter and Eric Swanson showed with the Evil32 attack how to create colliding key ids for all keys in the so-called strong set (meaning all keys that are connected with most other keys in the web of trust). Later someone unknown uploaded these keys to the key servers causing quite some confusion.

It should be noted that the issue of colliding key ids was known and discussed in the community way earlier, see for example this discussion from 2002.

The practical attacks targeted 32 bit key ids, but the same attack works against 64 bit key ids, too, it just costs more. I contacted the authors of the Evil32 attack and Eric Swanson estimated in a back of the envelope calculation that it would cost roughly $ 120.000 to perform such an attack with GPUs on cloud providers. This is expensive, but within the possibilities of powerful attackers. Though one can also find similar installation instructions using a 32 bit key id, where the attack is really cheap.

Going back to the installation instructions from above we can imagine the following attack: A man in the middle network attacker can intercept the connection to the keyserver - it's not encrypted or authenticated - and provide the victim a colliding key. Afterwards the key is imported by the victim, so the attacker can provide repositories with packages signed by his key, ultimately leading to code execution.

You may notice that there's a problem with this attack: The repository provided by HHVM is using HTTPS. Thus the attacker can not simply provide a rogue HHVM repository. However the attack still works.

The imported PGP key is not bound to any specific repository. Thus if the victim has any non-HTTPS repository configured in his system the attacker can provide a rogue repository on the next call of "apt update". Notably by default both Debian and Ubuntu use HTTP for their repositories (a Debian developer even runs a dedicated web page explaining why this is no big deal).

Attack 3: Key over HTTP

Issues with package keys aren't confined to Debian/APT-based distributions. I found these installation instructions at Dropbox (Link to Wayback Machine, as Dropbox has changed them after I reported this):



It should be obvious what the issue here is: Both the key and the repository are fetched over HTTP, a network attacker can simply provide his own key and repository.

Discussion

The standard answer you often get when you point out security problems with PGP-based systems is: "It's not PGP/GnuPG, people are just using it wrong". But I believe these issues show some deeper problems with the PGP ecosystem. The key flooding issue is inherited from the systemically flawed concept of the append only key servers.

The other issue here is lack of deprecation. Short key ids are problematic, it's been known for a long time and there have been plenty of calls to get rid of them. This begs the question why no effort has been made to deprecate support for them. One could have said at some point: Future versions of GnuPG will show a warning for short key ids and in three years we will stop supporting them.

This reminds of other issues like unauthenticated encryption, where people have been arguing that this was fixed back in 1999 by the introduction of the MDC. Yet in 2018 it was still exploitable, because the unauthenticated version was never properly deprecated.

Fix

For all people having installation instructions for external repositories my recommendation would be to avoid any use of public key servers. Host the keys on your own infrastructure and provide them via HTTPS. Furthermore any reference to 32 bit or 64 bit key ids should be avoided.

Update: Some people have pointed out to me that the Debian Wiki contains guidelines for third party repositories that avoid the issues mentioned here.

I recently noted that I have never blogged about this nice little device I now own for a couple of years. I originally bought the Toshiba AC100 before a two-month-long trip through Russia and China.

I was looking for a possibility to have a basic laptop, but without much weight. The AC100 is an ARM-based laptop which originally ships with the Android operating system. It weights less than 800 gramms and thus is lighter than the usual subnotebooks. According to my knowledge, it's not produced any more, but it can still be bought on ebay.

The nice thing is: You can install Linux on it and thus it will give you the possibility to run an almost full desktop-system. Though a warning ahead: While basic things work, it is quite a hacky business and you should expect to see problems. If you aren't prepared to solve them, this is probably not the solution for you.

Originally I was running Gentoo Linux on it (and it did well on my two-month trip), but now I'm running Ubuntu. The reason is that it was just too hard to get anything fixed if it didn't work. I rarely could find help anywhere, I assume there are only a handful of people that ever tried installing Gentoo on this Device. Ubuntu up until version 12.10 has reasonable support.

The great thing is: This is probably one of the lightest solutions to have a desktop/laptop-like machine with a real keyboard. Perfect for travelling. As it's running Linux, you can have access to a large number of standard applications. With lightweight apps like Abiword or Claws-Mail you can use basic applications.

The limitations are the Browser and Video. You can run Chromium or Firefox, but the device clearly shows its limits. Expect to wait longer sometimes, don't open too many tabs - and I always have to remember to never try to open Chromium and Firefox at the same time, as this makes the system mostly unusable. Obviously there's no Flash and nothing else that's only available in binary form, because ARM Linux is such a niche OS that nobody will provide binary apps for it.

Videos work, but limited. There's no xv support in the free driver. That means if you want to upscale a video to fullscreen, this has to be done in software and that usually means you cannot play videos fast enough. There's a binary graphics driver by Nvidia (the internals of the device are based on the Nvidia Tegra chipset), but I haven't had much success with it.

Just saw yesterday that there were advertisements for the new Ubuntu 8.10 release (two days ago) in the subway of Berlin.

Quite cool, they also were advertising for the Ubuntu release party in the C-Base tonight (though I'm no longer in Berlin at the moment).

Seit heute morgen um 10 sind wir hier aktiv bei der Linux-Installationsparty der LUG Backnang.
Von kaputten RAMs, seltsamen WLAN-Karten und Scannern, die nur mit Binärtreibern laufen wollen, sind wir schon einer breite Palette von Problemen begegnet. Insgesamt circa 20 Besucher und fast ebenso viele neue Kubuntu-Linux-PCs.