CyLab faculty earn two ‘Test of Time’ awards at IEEE Symposium on Security and Privacy

The Institute of Electrical and Electronics Engineers (IEEE) awarded two ‘Test of Time’ awards during its 44th Symposium on Security and Privacy, both going to papers co-authored by CyLab faculty members.

Initiated in 2019, the ‘Test of Time’ award recognizes published papers previously presented at the annual symposium that have had a broad and lasting impact on both research and practice in computer security and privacy. This year, the awarding committee considered papers presented in 2011 through 2013.

Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms (2012)
Patrick Gage Kelley, Saranga Komanduri, Michelle L. Mazurek, Richard Shay, Timothy Vidas, Lujo Bauer, Nicolas Christin, Lorrie Faith Cranor, Julio Lopez 

In 2012, text-based passwords remained the dominant authentication method in computer systems, despite attackers’ increasingly advanced password-cracking capabilities. In response to the threat, password composition policies became more complex; however, there was a lack of research defining the metrics to characterize password strength and evaluate those policies.

In the paper ‘Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms,’ researchers analyzed 12,000 passwords collected under seven composition policies and developed an efficient distributed method for calculating how effectively several heuristic password-guessing algorithms guessed passwords. Leveraging this method, the study’s authors investigated the resistance of passwords created under different conditions, such as the performance of guessing algorithms under different training sets, the relationship between passwords explicitly created under a given composition policy and other passwords that happen to meet the same requirements, and the relationship between guessability as measured with password-cracking algorithms and entropy estimates. The study advanced the understanding of both password-composition policies and metrics for quantifying password security.

While two-factor authentication now provides additional protection, not all services require the extra layer of security, and even when it’s offered, many users bypass the feature. With text-based passwords continuing to be a widely used authentication method, the researchers’ work continues to provide utility, helping to inform ever-evolving password policies.

“I'm particularly proud of this work and this paper because I think it exemplifies some of what I like best in research,” says Lujo Bauer, professor in Carnegie Mellon’s Electrical and Computer Engineering and Software and Societal Systems departments. “First, it tackled a real problem and led to insights that changed how people study passwords. Second, it really took a team effort; all the co-authors contributed in a significant way. We also persevered in improving the work and the paper through multiple cycles of submission and rejection. I'm both grateful and humbled that our work was recognized by this award.”

“Computer science in general, and computer security in particular, is an area that moves really fast, and where work can age quite quickly,” says Professor of Engineering and Public Policy and Software and Societal Systems, Nicolas Christin. “It's really humbling to receive this award, which means that our research has remained relevant for over a decade.”

Pinocchio: Nearly Practical Verifiable Computation (2013)
Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova

In 2013, researchers identified a need to instill greater confidence in computations outsourced to the cloud and enable clients to verify the correctness of the returned results. To address this, a team of Microsoft and IBM researchers, including now Carnegie Mellon Computer Science and Electrical and Computer Engineering Associate Professor Bryan Parno, developed and introduced Pinocchio, a built system for efficiently verifying general computations while relying only on cryptographic assumptions.

Pinocchio enables clients to create a public evaluation key to describe their computation. Workers then evaluate the computation on a particular input, using the evaluation key to produce a proof of correctness. At only 288 bytes, regardless of the computation performed or the size of the inputs and outputs, Pinocchio makes it possible for anyone to use a public verification key to check the proof. 

The study’s authors evaluated Pinocchio on seven applications, demonstrating its efficiency in practice. The tool averaged ten millisecond verification times, 5 to 7 orders of magnitude less than previous work. Pinocchio became the first general-purpose system to demonstrate verification at a lower cost than native execution, and it reduced workers’ proof efforts by up to a factor of 60. As an additional feature, Pinocchio provides zero-knowledge proofs at a nominal cost over the base protocol, which led to its popularity in various blockchain use cases. 

“Many blockchains were directly built around or later adopted the idea of generating zero-knowledge proofs, rather than publishing the details for each blockchain transaction” says Parno. “The proofs show the sender had enough money and that the money was correctly transferred to the other party, all while concealing the identity of involved parties.”

“Receiving the ‘Test of Time’ award is a nice reminder that our work has had a significant impact, both academically and in the real world.”