The work of the Chair of Media Security at the Bauhaus-Universität Weimar focuses on the following three cutting-edge research topics in symmetric cryptography:
1. The analysis of existing cryptosystems and security protocols to understand both their weaknesses and strengths.
2. The design of novel cryptosystems and security protocols that provide practical benefits in terms of security, robustness, or performance.
3. The secure and robust implementation of cryptography that protects both users and implementors against side channels and unintentional errors.
Most of our research combines the concerns of multiple of these topics.
Selected Projects
Password-Hashing
Password-based user authentication applies a one-way function that "hashes" the password and compares only the resulting hash to a previously stored value. So, even a leaked hash database does not reveal the underlying passwords.
To prevent adversaries from testing many passwords very fast, password hashing functions are designed to be intentionally slow, which means they consume the highest possible amount of computing time that is still not negatively perceived by users (about 0.2 seconds). Previous designs tried to achieve this by repeating a simple cryptographic operation many times. With the rapidly advancing progress of hardware performance, this approach has become less and less useful. For example, cheap off-the-shelf Graphical Processing Units (GPUs) possess thousands of cores that can run in parallel. Though, while computing power has become much cheaper during the recent years, fast memory is still comparably expensive.
In 2014 [5,6], the Chair of Media Security proposed the Catena password hashing framework as its submission to the international Password-Hashing Competition (PHC) [11]. Catena introduced and adopted a variety of novel ideas that represent the state-of-the-art of password hashing. It requires to allocate a large amount of memory, which lets it run very fast on typical user PCs or authentication servers with Gigabytes of RAM, but effectively slows down graphic cards that possess little fast memory. On the other hand, Catena is provably secure and easy to grasp since its structure stems from well-studied concepts from graph theory (the bit-reversal graph and the double butterfly graph) and pebbling games. In addition, Catena provides a high degree of flexibility by various tuning options, support for key derivation and proof of work, as well as support for relieving the major computational effort from the server to clients, or strengthening existing password hashes without the need for client interaction.
McOE
In 2012 [4], we introduced McOE, the first family of robust online authenticated-encryption (AE) schemes.
Application software mostly requires a network channel that guarantees both the privacy and the authenticity of transmitted messages. AE schemes aim at providing both goals at the same time. To secure its privacy, every encrypted and authenticated message is sent with an additional parameter that must never repeat - a so-called nonce ("number used once"). While the concept of never repeating a nonce appears trivially easy in theory, it can easily implemented wrongly - with severe consequences and costs in the past.
Prior to McOE, the security of all previously published AE schemes either fell completely apart or was constrained to processing every message multiple times. McOE offered for the first time a single-pass authenticated encryption which still provided a provable level of reasonable security (adversaries can only notice the longest common message prefix) for the case when nonces repeat.
The research from McOE has influenced many following works on authenticated encryption. Its core ideas have been adopted by more than 20 (out of 57) schemes that were submitted to the CAESAR (Competition for Authenticated Encryption: Security, Applicability, and Robustness) competition in March 2014 [10].
POET
The Chair of Media Security has also been contributing to the CAESAR competition. In joint work with top-level researchers from Cisco Systems, Inc., we submitted the novel online authenticated-encryption scheme POET. POET follows directly the spirit of McOE, inheriting its performant single-pass encryption and its robustness against nonce reuse. As a significant step ahead, POET adds robustness also for the case when invalid decrypted messages leak, which may occur in environments with demandingly low latency constraints or due to implementation failures.
In 2012 [7], we introduced an API that effectively hinders implementation mistakes for a cryptographic library in the security-related programming language Ada.
In 2013 [3], we proposed an automated tool for biclique cryptanalysis, a technique recently introduced to improve the cryptanalysis of block ciphers and hash functions [12]. Manually performing biclique cryptanalysis is tedious and error-prone. The tool greatly simplifies the process.
In 2013, Prof Lucks presented attacks on the EAX' scheme for authenticated encryption that had been proposed for standardization [8,9]. In addition, [8,9] also describe how to repair EAX' and provide a formal proof of security for the repaired version.
Inspired by our recent results and following our research focus, several top-level research projects can now be realized with the help of the new capabilities in the Digital Bauhaus Lab.
Password Security
In spite of decades of research on more intuitive and more secure user-authentication methods, passwords are still the most common way to authenticate at a computer or web server. The crux of passwords is the fact that they represent a compromise between being easy to remember but hard to guess by others. This project studies the security of passwords that result from existing password-generation rules and their potential for improvements. Questions tackled in this project include:
1.1 How good are common rules to generate passwords? Given a predefined amount of guesses for different adversary scenarios, which rules allow users to generate passwords that are still easily memorable, and how long should the generated passwords be in order to prevent adversaries from guessing them efficiently?
1.2 How good are password-recovery tools concerning the benefits of current hardware? During the recent years, several student projects at the Chair of Media Security developed the "Mack the Knife" password-recovery framework for NVIDIA CUDA-based GPUs. From this base, one can further improve the performance and usability of Mack the Knife and study the limits of password recovery on modern GPUs.
Another approach to password recovery bases on cryptanalytic time-memory tradeoffs. The basic idea was introduced by Hellman in the early 1980s. Instead of testing every password for every password hash again and again, one precomputes and stores a feasible amount in advance. In 2003, Oechslin further developed this method to the so-called rainbow tables, which can hold more precomputed password hashes with significantly reduced memory. Still, rainbow tables are usually too large to fit into the main memory of PCs; therefore, the speed of lookup, caching and reloading represents the bottleneck of password recovery. Fortunately, a large amount of Solid State Disks (SSDs) could be made available in the Digital Bauhaus Lab, which allow a improved implementations and benchmarks.
1.3 How good are memory-intensive password scramblers? For some, such as Catena, there are lower bounds proven on a time-memory tradeoff (i.e., for a given amount of storage, the minimum running time is proven). Most of these bounds are asymptotic, and the best algorithms known do not match the known bounds anyway. The challenge is to identify and implement practical time-memory tradeoffs. This implies an empirical study which could only be realized on the recent hardware in the Digital Bauhaus Lab.
Implementation Security
While cryptography is easy to get wrong from conceptional flaws, the most frequent source of insecure cryptography stems from implementation errors. There is an endless list of examples from the past, such as the famous heartbleed bug or Apple's goto fail.
The Chair of Media Security contributes to the research in safer and more secure cryptographic implementations. Therefore, we use the programming language Ada, which targets security- and safety-critical applications. This project wants to further develop the following subprojects:
2.1 Ada Cryptographic Library (ACL). The Chair of Media Security maintains a cryptographic library, called ACL, written in Ada. In the context of this project, we want to maintain, redesign and improve the ACL as well as the addition of recent important cryptographic algorithms and protocols.
2.2 AdaTLS. The "Transport Layer Security" (TLS) is one of the most relevant and widely used Internet protocols. A goal of this project is to define and implement a subset of the highly sophisticated TLS protocol suite. This subset must cover the essential parts that are necessary to realize the practical needs of implementing TLS in Ada while being small enough to avoid insecure usages. Naturally, the implementation will base on the ACL.
2.3 Weimar Secure Filesystem (WSFS). This project aims at implementing an encrypted and authenticated filesystem which supports local operations on the user's hard drive as well as remote file-system operations on data in the cloud. Cryptographic mechanisms must be implemented both to defend the privacy and authenticity of the concerned data, as well as to administrate access rights. Again, the implementation will use the ACL.
Time-Memory-Tradeoff Cryptanalysis
Time-memory tradeoffs are an extremely helpful approach not only for recovering passwords, but also for analyzing the strength of cryptographic primitives, such as stream ciphers, block ciphers, or hash functions. Instead of testing every key over and over again, one can store a significant amount of precomputations in tables. Though, the time-memory tradeoff is often not sufficiently understood, and their analysis often bases on simplifications, such as assuming the independence of certain parts of the primitives. Moreover, the theoretical analysis usually bases either on a very abstract machine model, or on asymptotic behaviors. Thus, the gain of practical implementations may differ significantly from theoretical results.
This project aims at implementing, performing, and benchmarking time-memory-tradeoff attacks in realistic adversarial scenarios. Such benchmarks usually require more memory than available on a typical machine, therefore requiring fast secondary storage. Thus, we imagine this project to benefit greatly from the solid state disks (SSDs) storage available in the Digital Bauhaus Lab.
Publications
[1] Farzaneh Abed, Scott Fluhrer, John Foley, Christian Forler, Eik List, Stefan Lucks, David McGrew, Jakob Wenzel: The POET Family of On-Line Authenticated Encryption Schemes -- Submission to the CAESAR competition, 2014. http://www.uni-weimar.de/de/medien/professuren/mediensicherheit/research/poet.
[2] Farzaneh Abed, Scott Fluhrer, John Foley, Christian Forler, Eik List, Stefan Lucks, David McGrew, Jakob Wenzel: Pipelineable On-Line Encryption, Fast Software Encryption (FSE) 2014.
[3] Farzaneh Abed, Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel: A Framework for Automated Independent-Biclique Cryptanalysis. Fast Software Encryption (FSE 2013).
[4] Ewan Fleischmann, Christian Forler, Stefan Lucks: McOE: A Family of Almost Foolproof On-Line Authenticated Encryption Schemes. Fast Software Encryption (FSE) 2012.
[5] Christian Forler, Stefan Lucks, Jakob Wenzel: Memory-Demanding Password Scrambling. ASIACRYPT 2014.
[6] Christian Forler, Stefan Lucks, Jakob Wenzel: The Catena Password Scrambling Framework (Submission to the PHC competition), 2014, http://www.uni-weimar.de/de/medien/professuren/mediensicherheit/research/catena.
[7] Christian Forler, Stefan Lucks, Jakob Wenzel: Designing the API for a Cryptographic Library - A Misuse-Resistant Application Programming Interface. Ada-Europe 2012
[8] Kazuhiko Minematsu, Stefan Lucks, Hiraku Morita, Tetsu Iwata: Attacks and Security Proofs of EAX-Prime. Fast Software Encryption (FSE) 2013.
[9] Kazuhiko Minematsu, Stefan Lucks, Tetsu Iwata: Improved Authenticity Bound of EAX, and Refinements. ProvSec 2013: 184-201.
[10] CAESAR Submissions Published http://cryptome.org/2014/03/caesar-submissions.htm
[11] Password Hashing Competition https://password-hashing.net/candidates.html
[12] Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger: Biclique Cryptanalysis of the Full AES. ASIACRYPT 2011.