Stefan Lucks: Papers for Download

PostScript files are marked by , PDF files by .

• John Kelsey, Stefan Lucks: Collisions and Near-Collisions for Reduced-Round Tiger , Preproceedings of FSE 2006.

  We describe a collision-finding attack on 16 rounds of the Tiger hash function requiring the time for about 2^44 compression function invocations. Another attack generates pseudo-near collisions, but for 20 rounds of Tiger with work less than that of 2^48 compression function invocations. Since Tiger has only 24 rounds, these attacks may raise some questions about the security of Tiger. In developing these attacks, we adapt the ideas of message modification attacks and neutral bits, developed in the analysis of MD4 family hashes, to a completely different hash function design.

• Stefan Lucks: A Failure Friendly Design Principle for Hash Functions , Asiacrypt 2005.

  This paper reconsiders the established Merkle-Damgaard design principle for iterated hash functions. The internal state size w of an iterated n-bit hash function is treated as a security parameter of its own right. In a formal model, we show that increasing w quantifiably improves security against certain attacks, even if the compression function fails to be collision resistant. We propose the wide-pipe hash, internally using a w-bit compression function, and the double-pipe hash, with w=2n and an n-bit compression function used twice in parallel.

• Ulrich Kühn, Klaus Kursawe, Stefan Lucks, Ahmad-Reza Sadeghi, Christian Stüble: Secure Data Management in Trusted Computing , CHES 2005.

  In this paper we identify shortcomings of the TCG specification related to the availability of sealed data during software and hardware life cycles, i.e., software update or/and hardware migration. In our view these problems are major obstacles for large-scale use of trusted computing technologies, e.g., in e-commerce, as adopters are concerned that the use of this technology might render their data inaccessible.

  We propose both software and hardware solutions to resolve these problems. Our proposals could be easily integrated into the TCG specification and preserve the interests of involved parties with regard to security and availability as well as privacy.

• Stefan Lucks: Two-Pass Authenticated Encryption Faster than Generic Composition , Fast Software Encryption 2005.

  An Authenticated Encryption (AE) scheme is a secret-key cryptosystem designed for simultaneously protecting both a message's privacy and its authenticity. Traditionally, these two security goals had been handled separately by the means of encryption schemes and message authentication codes (MACs). In practice, however, the same message often needs to be kept both private and authentic, and gluing together encryption and message authentication is surprisingly tricky and error-prone. Hence, a couple of block cipher based AE schemes have been developed recently.

  Even more recently, people discovered that AE is not quite sufficient. Often, some header (associated data, AD) is not confidential, but vital for authentication. Authenticated Encryption with Associated Data (AEAD) schemes authenticate both the message and the associated data, but only encrypt the message. Most of today's AE and AEAD schemes are either ``two-pass'' schemes and thus as slow as encrypting and authenticating independently, or ``one-pass'' schemes whose usage is hindered by the patent situation. This paper proposes a new two-pass scheme. Depending on the size of the authentication tag, our solution can run significantly faster than generic composition or other non-patented two-pass AE(AD) schemes. Another advantage is simplicity: compared to other AE(AD) schemes, our solution and its proof of security is very simple and straightforward.

• Stefan Lucks: Ciphers Secure Against Related-Key Attacks , Fast Software Encryption 2004.

  In a related-key attack, the adversary is allowed to transform the secret key and request encryptions of plaintexts under the transformed key. This paper studies the security of PRF- and PRP-constructions against related-key attacks.

  For adversaries who can only transform a part of the key, we propose a construction and prove its security, assuming a conventionally secure block cipher is given. By the terms of concrete security, this is an improvement over a recent result by Bellare and Kohno (2003). Further, based on some technical observations, we present two novel constructions for related-key secure PRFs, and we prove their security under number-theoretical infeasibility assumptions.

• Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks, Tadayoshi Kohno: Helix - Fast Encryption and Authentication in a Single Cryptographic Primitive , Fast Software Encryption 2003, Preproceedings version.

  Helix is a high-speed stream cipher with a built-in MAC functionality. On a Pentium II CPU it is about twice as fast as Rijndael or Twofish, and comparable in speed to RC4. The overhead per encrypted/authenticated message is low, making it suitable for small messages. It is efficient in both hardware and software, and with some pre-computation can effectively switch keys on a per-message basis without additional overhead.

• Stefan Lucks: A Variant of the Cramer-Shoup Cryptosystem for Groups with Unknown Order , Asiacrypt 2002. Copyright: Springer Verlag.

  The Cramer-Shoup cryptosystem is an efficient and quite practical public-key cryptosystem provably secure in a standard model under standard assumptions. This paper describes an extension of the Cramer-Shoup cryptosystem for groups of unknown order, such as the group QR_N of quadratic residues modulo N, where the factorisation of N is unknown. The main assumption made for the proof of security is the Decisional Diffie-Hellman assumption for QR_N.

• Scott Fluhrer, Stefan Lucks: Analysis of the E0 Encryption System , SAC 2001.

  The encryption system E0, which is the encryption system used in the Bluetooth specification, is examined. In the current paper, a method of deriving the cipher key from a set of known keystream bits is given. The running time for this method depends on the amount of known keystream available, varying from O(2^{84}) if 132 bits are available to O(2^{73}), given 2^{43} bits of known keystream.

  Although the attacks are of no advantage if E0 is used with the recommended security parameters (64 bit encryption key), they provide an upper bound on the amount of security that would be made available by enlarging the encryption key, as discussed in the Bluetooth specification.

• Erik Zenner, Matthias Krause, Stefan Lucks: Improved Cryptanalysis of the Self-Shrinking Generator , ACISP 2001.

  We propose a new attack on the self-shrinking generator. The attack is based on a backtracking algorithm and will reconstruct the key from a short sequence of known keystream bits. We give both mathematical and empicical evidence for the effectiveness of this attack. The algorithm takes at most O(2^{0.694 L}) steps, where L is the key length. Thus, our attack is more efficient than previously known key reconstruction algorithms against the self-shrinking generator that operate on short keystream sequences.

• Paul Crowley, Stefan Lucks: Bias in the LEVIATHAN stream cipher , Fast Software Encryption 2001.

  We show two methods of distinguishing the LEVIATHAN stream cipher from a random stream using 2^36 bytes of output and proportional effort; both arise from compression within the cipher. The first models the cipher as two random functions in sequence, and shows that the probability of a collision in 64-bit output blocks is doubled as a result; the second shows artifacts where the same inputs are presented to the key-dependent S-boxes in the final stage of the cipher for two successive outputs. Both distinguishers are demonstrated with experiments on a reduced variant of the cipher.

• Stefan Lucks: The Saturation Attack - a Bait for Twofish , Fast Software Encryption 2001.

  We introduce the notion of a saturation attack and present attacks on reduced-round versions of the Twofish block cipher. Our attack for all generic key sizes of Twofish (i.e., for 128-bit, 192-bit and 256-bit keys) improves on exhaustive key search for seven rounds of Twofish with full whitening, and for eight rounds of Twofish without whitening at the end. The core of the attack is a a key-independent distinguisher for six rounds of Twofish. The distinguisher is used to attack up to 7 rounds of Twofish with full whitening and and 8 rounds of Twofish with prewhitening only - half of the cipher. The attacks take up to 2^127 chosen plaintexts (half of the codebook!) and are 2-4 times faster than exhaustive search.

• Rüdiger Weis, Stefan Lucks: How to Make DES-based Smartcards fit for the 21-st Century , Cardis 2000.

  With its 56-bit key size, the data encryption standard (DES) seems to be at end of its useful lifetime. Also, the 64-bit DES block size is dangerously small for some applications. We discuss techniques such as triple DES and DESX to push up the key size, and we present DEAL to increase both block and key size. We propose DEAL^KX, a new variant of DEAL with an improved key schedule.

• Matthias Krause, Stefan Lucks: On the Minimal Hardware Complexity of Pseudorandom Function Generators (full paper) , STACS 2001.

  A set F of Boolean functions is called a pseudorandom function generator (PRFG) if communication with a randomly chosen secret function from F cannot be efficiently distinguished from communicating with a truly random function. We ask for the minimal hardware complexity of a PRFG. This question is motivated by design aspects of secret key cryptosystems. Such cryptosystems should be efficient in hardware, but often are required to behave like PRFGs. By constructing efficient distinguishing schemes we show for a wide range of logic nonuniform complexity classes, induced by depth restricted branching programs and several types of constant depth circuits (including TC^0_2), that they do not contain PRFGs. On the other hand we show that the PRFG proposed by NAor and Reingold consists of TC^0_4-functions. The question if TC^0_3 functions can form PRFGs remains as an interesting open problem. We further discuss relations of our results to previous work on cryptographic limitations of learning and Natural Proofs.

• Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, Doug Whiting: Improved Cryptanalysis of Rijndael , Fast Software Encryption 2000.

  We improve the best attack on Rijndael reduced to 6 rounds from complexity 2^72 to 2^44. We also present the first known attacks on 7- and 8-round Rijndael. The attacks on 8-round Rijndael work for 192-bit and 256-bit keys. Finally, we discuss the key schedule of Rijndael and describe a related-key attack that can break 9-round Rijndael with 256-bit keys.

• Stefan Lucks: The Sum of PRPs is a Secure PRF , Eurocrypt 2000. Copyright: Springer Verlag.

  Given d independent pseudorandom permutations (PRPs) p_i, ..., p_d over {0,1}^n, it appears natural to define a pseudorandom function (PRF) by adding (or XORing) the permutation results: SUM^d(x)=p_1(x) (+) ... (+) p_d(x). This paper investigates the security of SUM^d and also considers a variant that only uses one single PRP over {0,1}^n.

• Stefan Lucks: Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys , Third AES Candidate Conference, AES3, New York, 2000.

  The authors of Rijndael [DR98] describe the "Square attack" as the best known attack against the block cipher Rijndael. If the key size is 128 bit, the attack is faster than exhaustive search for up to six rounds. We extend the Square attack on Rijndael variants with larger keys of 192 bit and 256 bit. Our attacks exploit minor weaknesses of the Rijndael key schedule and are faster than exhaustive search for up to seven rounds of Rijndael.

• Stefan Lucks: Accelerated Remotely Keyed Encryption , Fast Software Encryption 1999. Copyright: Springer Verlag.

  Remotely keyed encryption schemes (RKESs) support fast encryption and decryption using low-bandwidth devices, such as secure smartcards. The long-lived secret keys never leave the smartcard, but most of the encryption is done on a fast untrusted device, such as the smartcard's host.

  This paper describes an new scheme, the length-preserving "accelerated remotely keyed" (ARK) encryption scheme and, in a formal model, provides a proof of security. For the sake of practical usability, our model avoids asymptotics.

  Blaze, Feigenbaum, and Naor gave a general definition for secure RKESs [BFN98]. Compared to their length-preserving scheme, the ARK scheme is more efficient but satisfies the same security requirements.

• Stefan Lucks: On the Security of the 128-Bit Block Cipher DEAL , Fast Software Encryption 1999. Copyright: Springer Verlag.

  DEAL is a DES-based block cipher proposed by Knudsen. The block size of DEAL is 128 bits, twice as much as the DES block size. The main result of the current paper is a certificational attack on DEAL-192, the DEAL variant with a 192-bit key. The attack allows a trade-off between the number of plaintext/ciphertext pairs and the time for the attacker's computations. Nevertheless, the DEAL design principle seems to be a useful way of doubling the block size of a given block cipher.

• Stefan Lucks: Attacking Triple Encryption , Fast Software Encryption 1998.

  The standard technique to attack triple encryption is the meet-in-the-middle attack. In this paper, more efficient attacks are presented. Compared to meet-in-the-middle, our attacks either greatly reduce the number of single encryptions to be done, or somewhat reduce the overall number of steps.

  Especially, about $2^{108}$ steps of computation are sufficient to break three-key triple DES. If one concentrates on the number of single DES operations and assumes the other operations to be much faster, $2^{90}$ of these are enough. We use this to compare the security of triple DES and DESX.

• Stefan Lucks: Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys .

  Classical cryptographic protocols based on shared secret keys often are vulnerable to key-guessing attacks. For security, the keys must be strong, difficult to memorize for humans. Bellovin and Merritt (1992) proposed "encrypted key exchange" (EKE) protocols, to frustrate key-guessing attacks. EKE requires the use of asymmetric cryptosystems and is based on encrypting the public key, using a symmetric cipher.

  In this paper, a novel way of key exchange is presented, where public keys are sent openly, not encrypted. In contrast to EKE protocols, the same public-key/secret-key pair can be used for arbitrary many protocol executions. The RSA-based protocol variant is found to be quite efficient and practical.

  Compared to previous work on such protocols, a more solid formal treatment is given, influenced by the work of Bellare and Rogaway (1993) on key exchange protocols for strong common secrets.

• Stefan Lucks: On the Security of Remotely Keyed Encryption .

  The purpose of remotely keyed encryption is to efficiently realize a secret-key block cipher by sharing the computational burden between a fast untrusted device and a slow device trusted with the key. This paper deals with how to define the security of remotely keyed encryption schemes. Since the attacker can take over the slow device and actually take part in the encryption process, common definitions of the security of block ciphers have to be reconsidered.

  Using random mappings, collision resistant hash functions, and stream ciphers as building blocks, the Random Mapping based Remotely Keyed (RaMaRK) encryption scheme is proposed. Also GRIFFIN is proposed, a fast new block cipher for flexible but large blocks. The RaMaRK scheme and GRIFFIN are provably secure if the underlying building blocks are secure.

• Stefan Lucks: Faster Luby-Rackoff Ciphers .

  This paper deals with a generalization of Luby's and Rackoff's results (Luby and Rackoff, 1988) on the construction of block ciphers and their consequences for block cipher implementations. Based on dedicated hash functions, block ciphers are proposed which are more efficient and operate on larger blocks than their original Luby-Rackoff counterparts.

• Stefan Lucks: How Traveling Salespersons Prove Their Identity .

  In this paper a new identification protocol is proposed. Its security is based on the Exact Traveling Salesperson Problem (XTSP). The XTSP is a close relative of the famous TSP and consists of finding a Hamiltonian circuit of a given length, given a complete directed graph and the distances between all vertices. Thus, the set of tools for use in public-key cryptography is enlarged.

• Stefan Lucks: How to Exploit the Intractability of Exact TSP for Cryptography .

  We outline constructions for both pseudo-random generators and one-way hash functions. These constructions are based on the exact TSP (XTSP), a special variant of the well known traveling salesperson problem. We prove that these constructions are secure if the XTSP is infeasible. Our constructions are easy to implement, appear to be fast, but require a large amount of memory.