Till Stegers

e-mail: *my last name* at cs.ucdavis.edu
PGP Key | Stats
 

Short Bio

I am a PhD student in the Department of Computer Science at the University of California, Davis. From 2001 to 2005, I studied Mathematics with Computer Science at TU Darmstadt in Germany. In 2002/2003, I was fortunate to attend the graduate program in Mathematics at Tulane University in New Orleans. Since joining UC Davis in Fall 2005, I've been having fun working on topics in cryptography and security. My advisor is Phil Rogaway.

 

Publications

 Format-Preserving Encryption
Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers
Selected Areas in Cryptography 2009
Download PDF of full version

Abstract: Format-preserving encryption (FPE) encrypts a plaintext of some specified format into a ciphertext of identical format — for example, encrypting a valid credit-card number into a valid credit-card number. The problem has been known for some time, but it has lacked a fully general and rigorous treatment. We provide one, starting off by formally defining FPE and security goals for it. We investigate the natural approach for achieving FPE on complex domains, the "rank-then-encipher" approach, and explore what it can and cannot do. We describe two flavors of unbalanced Feistel networks that can be used for achieving FPE, and we prove new security results for each. We revisit the cycle-walking approach for enciphering on a non-sparse subset of an encipherable domain, showing that the timing information that may be divulged by cycle walking is not a damaging thing to leak.
 


How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle
Ben Morris, Phillip Rogaway, and Till Stegers
Advances in Cryptology — CRYPTO 2009.
Download PDF

Abstract: We analyze the security of the Thorp shuffle, or, equivalently, a maximally unbalanced Feistel network. Roughly said, the Thorp shuffle on N cards mixes any N1-1/r of them in O(r log N) steps. Correspondingly, making O(r) passes of maximally unbalanced Feistel over an n-bit string ensures CCA-security to 2n(1-1/r) queries. Our results, which employ Markov-chain techniques, enable the construction of a practical and provably-secure blockcipher-based scheme for deterministically enciphering credit card numbers and the like using a conventional blockcipher.
 


Authentication without Elision: Partially Specified Protocols, Associated Data, and Cryptographic Models Described by Code.
22nd IEEE Computer Security Foundations Symposium (CSF 2009)
Phillip Rogaway and Till Stegers
Download PDF

Abstract: Specification documents for real-world authentication protocols typically mandate some aspects of a protocol's behavior but leave other features optional or undefined. In addition, real-world schemes often include parameter negotiations, authenticate associated data, and support a multiplicity of options. The cryptographic community has routinely elided such matters from our definitions, schemes, and proofs. We propose encompassing them by explicitly modeling the presence of unspecified protocol functionality. To demonstrate, we provide a new treatment for mutual authentication in the public-key setting, doing this in the computational cryptographic tradition. In our model, compactly described in pseudocode, a protocol core (PC) will call out to protocol details (PD), but, for defining security, such calls will be serviced by the adversary. Parties accepting an authentication exchange will output a string of associated data, the value of which may be determined by the PD calls. We illustrate the approach by re-proving security for the Needham-Schroeder-Lowe public-key protocol, but extended in a manner that would be typical were the mechanism embedded in a real-world standard.
 


Source Code Review of the Sequoia Voting System
Report to the Secretary of State of California, July 20, 2007
as part of the "Top-to-bottom Review" led by Matt Bishop and David Wagner
Authors: Matt Blaze, Arel Cordero, Sophie Engle, Chris Karlof, Naveen Sastry, Micah Sherr, Till Stegers, and Kai-Ping Yee
Download PDF file of our report
Decertification/recertification decision by Secretary of State Debra Bowen

Very Brief Abstract: We found significant security weaknesses throughout the Sequoia system. The nature of these weaknesses raises serious questions as to whether the Sequoia software can be relied upon to protect the integrity of elections. Every software mechanism for transmitting election results and every software mechanism for updating software lacks reliable measures to detect or prevent tampering. In certain cases, audit mechanisms may be able to detect and recover from some attacks, depending on county-specific procedures; other attacks may be more difficult to detect after-the-fact even with very rigorous audits.

Computational Soundness of Formal Indistinguishability and Static Equivalence
ASIAN 2006 and Cryptology ePrint Archive Report 2006/323
Gergei Bana, Payman Mohassel, and Till Stegers
Download full version: http://eprint.iacr.org/2006/323.pdf

Abstract: In the research of the relationship between the formal and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of formal indistinguishability. Previous work has shown that this yields the soundness of natural interpretations of some interesting equational theories, such as certain cryptographic operations and a theory of XOR. In this paper however, we argue that static equivalence is too coarse for sound interpretations of equational theories in general. We show some explicit examples how static equivalence fails to work in interesting cases. To fix this problem, we propose a notion of formal indistinguishability that is more flexible than static equivalence. We provide a general framework along with general theorems, and then discuss how this new notion works for the explicit examples where static equivalence failed to ensure soundness. We also improve the treatment by using ordered sorts in the formal view, and by allowing arbitrary probability distributions of the interpretations.
 
Security Analysis of the eVACS Open-Source Voting System
Manuscript, 2005
Ananya Das, Yuan Niu, and Till Stegers
Download PDF file: eVACS-final-report.pdf

Abstract: The electronic Voting and Counting System (eVACS) is an open-source software used in an electronic voting trial in the Australian Capital Territory, and has been recommended for use in future elections. In this paper, we report results from a review of the eVACS code and design, supported by static analysis tools. While no "hot exploits" have been found, several bad practices were identified.

 

Theses

Faugère's F5 Algorithm Revisited
Diplom thesis
Technische Universität Darmstadt, 2005 (last revised 2007-04-27)
Preprint: http://eprint.iacr.org/2006/404
Advisor: Johannes Buchmann
Download PDF file: diplom_stegers.pdf
Download Magma source code for F5: f5_magma.tar.gz

Abstract: We present and analyse the F5 algorithm for computing Gröbner bases. On the practical side, we correct minor errors in Faugère's pseudo code, and report our experiences implementing the -- to our knowledge -- first working public version of F5. While not designed for efficiency, it will doubtless be useful to anybody implementing or experimenting with F5. In addition, we list some experimental results, hinting that the version of F5 presented in Faugère's original paper can be considered as more or less naive, and that Faugère`s actual implementations are a lot more sophisticated. We also suggest further improvements to the F5 algorithm and point out some problems we encountered when attempting to merge F4 and F5 to an "F4.5" algorithm. On the theoretical side, we slightly refine Faugère's theorem that it suffices to consider all normalized critical pairs, and give the first full proof, completing his sketches. We strive to present a more accessible account of the termination and correctness proofs of F5. Unfortunately, we still rely on a conjecture about the correctness of certain optimizations. Finally, we suggest directions of future research on F5.

A Survey of Concrete Categories Where All Reflexive Objects Are Degenerate
Master of Science thesis
Tulane University, 2003
Advisor: Michael Mislove
Download PostScript file: thesis-refl-objects.ps.gz

Abstract: This thesis provides a survey of different degeneracy results for models of the untyped lambda calculus. The first chapter gives a motivation and introduces the basic syntactical notions. It also describes the set of lambda-terms using universal algebra. In the second chapter, we discuss cartesian closed categories, the definition of an environment model and briefly compare it to other notions of a model. The last chapter gives proofs for the degeneracy of models in the categories of partially ordered sets, complete-ultrametric spaces and (under the assumption of compactness) compactly generated Hausdorff spaces.

Aspects of the Discrete Logarithm
Bachelor of Science thesis
Technische Universität Darmstadt, 2002
Advisor: Michael Wüstner
Download PostScript file: dl.ps.gz

Abstract: We introduce the problem of discrete logarithms in groups and present the explicit formula for the group of units of a finite field. The Silver-Pohlig-Hellman algorithm for finite groups and the general outline of index-calculus methods are discussed, as well as some specialized index-calculus algorithms for finite fields.


What's this about?

Links