How I discovered the weak key vulnerability in Debian

For those new to information technology, it may be discoverythat next month we will celebrate the 16th anniversary of a significant event: it was revealed that within 18 months the package OpenSSL on Debian worked out completely predictable private keyswhich was sensational news at the time.

A recent threat associated with xz-stential (Thank you @nixCraft behind drawing attention to this problem), prompted me to remember my own unexpected experience of discovering a serious vulnerability. Given that the deadline for legal prosecution has likely passed, I thought I'd share my experience as an example of how an unbiased “hmm, that's weird” can lead to the identification of serious security threats – provided you have the time, of course. and patience to unravel this thread further.

Let's start diving into history

My story begins in March 2008. At the time, I was part of the Engine Yard (EY) team, a company that once occupied a leading position in the field of hosting applications on Rails and made significant contributions to the development of this field. One of EY's most memorable achievements was providing support for the small but promising code hosting platform that many people know today – providing free infrastructure at a time when it was just a small blip in the ocean of the Internet.

We are, of course, talking about a product that is now owned by Microsoft – GitHub.

GitHub appeared on the market on time with its offer, which was liked by many, and thanks to this it began to quickly grow and expand its audience. With increasing popularity comes new problems, and one of them that we will look at today was the time of authorization via SSH. Just as now, GitHub provided access to hosted git repositories via an SSH connection to git@github.com and authentication using public keys. To manage keys, a standard method was used – file ~/.ssh/authorized_keyswhich has caused problems over time due to the steadily increasing number of keys.

During the SSH authentication process, the system scans the file ~/.ssh/authorized_keys for the presence of a key corresponding to the one presented by the user. Usually this sequential search is not difficult, since few people add more than a few keys to the file. But what happens when there are too many keys?

As a popular and actively growing service, GitHub quickly attracted more and more users, until at some point it became obvious that one massive file containing all SSH keys began to significantly slow down the SSH login process. The problem was getting worse every day and a solution needed to be found.

Engine Yard management was focused on ensuring the stable operation of GitHub and, despite the fact that the problem did not directly concern hosting, they expressed their willingness to help solve it. For some reason, the great and late Ezra Zygmuntowicz decided to point GitHub to me, giving me the opportunity to dive into this problem with their team. After considering various approaches, we decided that the least bad solution would be to change OpenSSH so that keys are looked up in a MySQL database indexed by key fingerprints.

This decision was not made spontaneously – we did not approach this as an easy “let's just change OpenSSH and see what happens.” We realized that this approach could be disastrous if things went wrong, so you can imagine how terrible the other options were. We have gone to great lengths to ensure that changes are made safely. Ultimately, the innovation was implemented in early April, and voila! Logging in via SSH became much faster and we were confident that this problem would not bother us in the near future.

One would think that “making changes to OpenSSH to speed up bulk authentication over SSH” would be a decent story in itself. But no, this was just the beginning.

Loading Chekhov's Gun

Let's rewind the clock to the first days of May 2008, which was just under a month after the events described earlier. I received an email from a member of the GitHub team indicating that users were somehow accessing other people's repositories via SSH. Given that we recently implemented a special patch for OpenSSH that affects this particular area, the code I developed naturally became a prime suspect. Because of this, I was immediately called upon to help resolve the problem.

Eventually, after quite a bit of debugging, we discovered that somehow two users had keys with the same fingerprint. This is absolutely impossible – it's like winning the lottery twice in a row – unless, of course, users somehow shared their keys with each other. Still, it was worth investigating in case it was a bug in the web app, so the GitHub team contacted affected users to try to figure out what was going on.

The users said they didn't know each other, neither admitted to publishing their key and could offer no explanation for how the other person could have obtained their key.

Then the situation began to move from “strange” to “what the…?”. Because there was another pair of users sharing one key fingerprint – but it was a different shared key fingerprint. The odds have now gone from “winning the lottery several times in a row” to “it's literally impossible for this to happen.”

Once we were confident in eliminating the OpenSSH patch from the list of possible causes of the problem, my role in solving it was effectively over. Since I was not a GitHub employee and there were many other clients at Engine Yard that needed my support, I could not actively participate in further investigation of the duplicate keys mystery.

However, the GitHub team continued to interact with the affected users and identified one common thread: they all stated that their systems were running Debian or Ubuntu, which is where their SSH keys were supposedly generated.

This was the only significant conclusion that the investigation was able to reach before May 13, 2008.

A loaded gun fires

When was the update released? DSA-1571-1, everything became clear. As a result of a well-intended but disastrous fix to a vulnerability in the OpenSSL random number generation code carried out by the Debian team, the developer accidentally reduced the number of potential keys available for generation for each user from “bazillions” to just over 32,000. Given that With many people registering on GitHub and many likely following security guidelines to generate unique keys, it is not surprising that cross-key matches occurred.

One can easily imagine the “a-ha” feeling among those who have become aware of the problem. Personally, I was relieved that definitive proof of my OpenSSH patch had been found. However, I didn't yet realize how deeply I would dive into the problem of vulnerable Debian keys in the future. This included management a huge database of compromised keys and their use to detect unscrupulous behavior certification centersamong other things.

Lessons Learned

There is no exact chronology of how Luciano Bello identified the vulnerability, later designated CVE-2008-0166, but my guess is that he encountered it long before it was publicly disclosed and likely before it became known to GitHub. Given that the vulnerable version of Debian had been released a year earlier, Luciano had plenty of time to notice the duplicate keys and begin the investigation that eventually led to solving the mystery.

The same “something is wrong here” approach and subsequent in-depth research led to the discovery of the recent vulnerability in XZ. However, the key here is the ability to dedicate yourself to such a thorough investigation.

Looking back on my encounter with Debian's weak key problem, I realize that I didn't do as much analysis. It's interesting to think about how long it would have been before the vulnerability would have been found if Luciano hadn't made his discovery. Perhaps the GitHub team would have continued their investigation, and perhaps they or I would have eventually found it. But each of us had many other tasks – I was engaged in customer support at Engine Yard, and GitHub was intensively developing its service.

Luciano took the time to dive deep into the issue and understand it. However, the industry appears to have been fortunate to have someone with the right skills, time and energy in the right place at the right time to make a significant contribution.

The opportunity to delve into a detailed study of a problem is a luxury that few people can afford. Perhaps one of the underappreciated takeaways is that we should all take the time to listen to our inner voice and pay attention to those moments that make us feel like “something is wrong here.”

Thank you for your attention(: