),
some as gnu-zipped PDF-files
Most papers are stored as PostScript files, some also as
PDF-files
(marked by ),
some as gnu-zipped PDF-files
Stefan Lucks, 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.
Stefan Lucks, Fast Software Encryption 2004.
Preproceedings version.
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.
NielsFerguson, Doug Whiting,
Bruce Schneier, John Kelsey,
Stefan Lucks, Tadayoshi Kohno, 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, Asiacrypt 2002. Copyright: Springer.
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. 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. 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. 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. 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. 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. 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, and Doug Whiting. 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. 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. 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. 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. 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. 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.
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.
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.
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.
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.
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.
Ciphers Secure Against
Related-Key Attacks
Helix
Fast Encryption and Authentication in a Single Cryptographic Primitive
A Variant of the Cramer-Shoup Cryptosystem for Groups with
Unknown Order
Analysis of the E0 Encryption System
Improved Cryptanalysis of the Self-Shrinking Generator
Bias in the LEVIATHAN stream cipher
See a
page maintained by Paul for further information on LEVIATHAN.
The Saturation Attack - a Bait for Twofish
How to Make DES-based Smartcards fit for the 21-st Century
On the Minimal Hardware Complexity of
Pseudorandom Function Generators (full paper)
Improved Cryptanalysis of Rijndael
The Sum of PRPs is a Secure PRF
Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys
Accelerated Remotely Keyed Encryption
On the Security of the 128-Bit Block Cipher DEAL
Attacking Triple Encryption
Open Key Exchange:
How to Defeat Dictionary Attacks Without Encrypting Public Keys
On the Security of Remotely Keyed Encryption
Faster Luby-Rackoff Ciphers
How Traveling Salespersons Prove Their Identity
How to Exploit the Intractability of Exact TSP for Cryptography
Last modified: 01/2004.
Back to homepage of Stefan Lucks
This Web page is
HTML 2.0 Checked
and
friendly 
to all browsers.