Researchers earn USENIX Test of Time for work in exposing network key vulnerabilities

University of Michigan researchers have been recognized with the 2022 USENIX Security Symposium Test of Time Award for their 2012 study, “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices.” Authored by Prof. J. Alex Halderman and his former students Eric Wustrow and Zakir Durumeric with their collaborator Nadia Heninger, the paper introduced powerful methodologies for discovering Internet security problems and uncovered cryptographic flaws that affected tens of millions of devices. The USENIX Test of Time award recognizes papers presented at its respective conference from at least 10 years ago that have had a lasting impact on their fields. 

The researchers set out to  expose failures in the processes that generate RSA and DSA encryption keys, but, along the way, they completed what were at the time the  most comprehensive Internet-wide scans That work would later inspire Halderman and his students to create the ZMap network scanner, which has become a standard tool for Internet-wide measurement.

However, the team’s most significant contribution was a new route for discovering vulnerabilities in cryptographic implementations. Previously, such problems were found through time-intensive reverse engineering (or plain luck, when users happened to observe specific symptoms of underlying issues). The researchers’ insight was that by applying specialized data mining algorithms to the kind of Internet-wide scan data they collected, they could detect subtle clues indicating more widespread underlying problems. “Many of the collisions we found were too rare to ever have been observed by a single user but quickly became apparent with a near-global view of the universe of public keys. The results are a reminder to all that vulnerabilities can sometimes be hiding in plain sight,” the paper concluded.

Among other issues, they spotted a major flaw in the Linux kernel’s random number generator that could weaken the security of cryptographic keys, especially those generated in embedded systems such as the devices that make up the Internet of Things. The study was found to be a “wake-up call that secure random number generation continues to be an unsolved problem in important areas of practice.” Unfortunately, that still holds true today, and the Linux kernel continues to undergo changes to better guard against exactly the sort of vulnerabilities the authors discovered.

Since its publication, the paper has often been cited for its groundbreaking scope and contributions to the understanding of encryption and entropy problems caused by insufficient randomness in operating systems. The concepts outlined in this paper would also go on to impact the field of network security and inspire new innovations in defense for developers and users alike.

But to Halderman, the work’s most important legacy will be a human one. “Ten years later, I’m most proud that all of my coauthors from this paper have gone on to be successful professors in their own right, each leading a thriving research group,” he said. “That’s ultimately the most satisfying kind of contribution our work can have.”

Prof. Halderman’s research focuses on computer security and privacy, with an emphasis on problems that broadly impact society and public policy. At this year’s USENIX Security, he also received a remarkable two best paper awards and the Internet Defense Prize (together with Prof. Roya Ensafi), which “celebrates security research contributions to the protection and defense of the Internet.”