Researchers’ work recognized amongst notable computing books and articles of 2012

Research conducted by Michigan computer scientists has been selected for ACM Computing Review‘s Notable Computing Books and Articles of 2012. Based on nominations from reviewers, editors, the editors in chief of journals, and others in the computing community and compiled by the editorial board at Computing Review, the list recognizes 91 significant items from a range of publications or publishers.

Amongst the notables is the paper, “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices,” authored by U-M graduate students Zakir Durumeric and Eric Wustrow, Professor J. Alex Halderman, and UC San Diego postdoctoral researcher Nadia Heninger. The paper was presented at the 21st USENIX Security Symposium, where it won the Best Paper Award.

The paper details a large-scale study of RSA and DSA cryptographic keys in use on the Internet and find that large numbers of keys are insecure due to insufficient randomness. These keys are being used to secure TLS (HTTPS) and SSH connections for hundreds of thousands of hosts. According to the researchers, the security flaw largely affects headless and embedded network devices, such as routers, firewalls, and server management cards. These types of devices often generate keys automatically on first boot, and lack many of the physical sources of randomness used by traditional PCs to generate random numbers. They identified apparently vulnerable devices and software from 54 manufacturers and notified those companies about the problems.

Also recognized is the paper “The Computational Complexity of Nash Equilibria in Concisely Represented Games,” published in ACM Transactions on Computation Theory in May 2012 and authored by Prof. Grant Shoenebeck (then a post-doctoral researcher at Princeton) and Salil Vadhan of Harvard.

Their paper describes how different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. It then studies two models of concisely represented games and the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, the authors obtained tight results, showing that the problems are complete for various complexity classes.

Prof. J. Alex Halderman received his Ph.D. in Computer Science from Princeton University in 2009 and joined the faculty at Michigan the same year. He is a noted security expert whose research spans applied computer security and tech-centric public policy. His research projects have dealt with electronic voting, software security, data privacy, anticensorship, digital rights management, and cybercrime. He has taught EECS 588, “Computer and Network Security,” and EECS 388, “Introduction to Computer Security.” In Fall 2012, he taught “Securing Digital Democracy,” a massive open online course through Coursera.

Prof. Grant Shoenebeck received his PhD from the University of California, Berkeley in 2010. He joined the faculty at Michigan in 2012 from Princeton University, where he was a Simons Foundation Postdoctoral Research Fellow in Theoretical Computer Science. He has broad interests in theoretical computer science, and his research includes work on using linear and semidefinite programs to approximate NP-complete optimization problems, and computational complexity theory. He has taught EECS-598, “Social Networks: Reasoning About Structure and Processes,” and EECS 203, “Discrete Math.”