CryptoDB
Bart Preneel
Affiliation: KU Leuven, Belgium
Publications
Year
Venue
Title
2020
TCHES
Dismantling DST80-based Immobiliser Systems
📺
Abstract
Car manufacturers deploy vehicle immobiliser systems in order to prevent car theft. However, in many cases the underlying cryptographic primitives used to authenticate a transponder are proprietary in nature and thus not open to public scrutiny. In this paper we publish the proprietary Texas Instruments DST80 cipher used in immobilisers of several manufacturers. Additionally, we expose serious flaws in immobiliser systems of major car manufacturers such as Toyota, Kia, Hyundai and Tesla. Specifically, by voltage glitching the firmware protection mechanisms of the microcontroller, we extracted the firmware from several immobiliser ECUs and reverse engineered the key diversification schemes employed within. We discovered that Kia and Hyundai immobiliser keys have only three bytes of entropy and that Toyota only relies on publicly readable information such as the transponder serial number and three constants to generate cryptographic keys. Furthermore, we present several practical attacks which can lead to recovering the full 80-bit cryptographic key in a matter of seconds or permanently disabling the transponder. Finally, even without key management or configuration issues, we demonstrate how an attacker can recover the cryptographic key using a profiled side-channel attack. We target the key loading procedure and investigate the practical applicability in the context of portability. Our work once again highlights the issues automotive vendors face in implementing cryptography securely.
2020
TCHES
Revisiting a Methodology for Efficient CNN Architectures in Profiling Attacks
📺
Abstract
This work provides a critical review of the paper by Zaid et al. titled “Methodology for Efficient CNN Architectures in Profiling attacks”, which was published in TCHES Volume 2020, Issue 1. This work studies the design of CNN networks to perform side-channel analysis of multiple implementations of the AES for embedded devices. Based on the authors’ code and public data sets, we were able to cross-check their results and perform a thorough analysis. We correct multiple misconceptions by carefully inspecting different elements of the model architectures proposed by Zaid et al. First, by providing a better understanding on the internal workings of these models, we can trivially reduce their number of parameters on average by 52%, while maintaining a similar performance. Second, we demonstrate that the convolutional filter’s size is not strictly related to the amount of misalignment in the traces. Third, we show that increasing the filter size and the number of convolutions actually improves the performance of a network. Our work demonstrates once again that reproducibility and review are important pillars of academic research. Therefore, we provide the reader with an online Python notebook which allows to reproduce some of our experiments1 and additional example code is made available on Github.2
2019
TCHES
Fast, Furious and Insecure: Passive Keyless Entry and Start Systems in Modern Supercars
📺
Abstract
The security of immobiliser and Remote Keyless Entry systems has been extensively studied over many years. Passive Keyless Entry and Start systems, which are currently deployed in luxury vehicles, have not received much attention besides relay attacks. In this work we fully reverse engineer a Passive Keyless Entry and Start system and perform a thorough analysis of its security.Our research reveals several security weaknesses. Specifically, we document the use of an inadequate proprietary cipher using 40-bit keys, the lack of mutual authentication in the challenge-response protocol, no firmware readout protection features enabled and the absence of security partitioning.In order to validate our findings, we implement a full proof of concept attack allowing us to clone a Tesla Model S key fob in a matter of seconds with low cost commercial off the shelf equipment. Our findings most likely apply to other manufacturers of luxury vehicles including McLaren, Karma and Triumph motorcycles as they all use the same system developed by Pektron.
2017
TOSC
Efficient Length Doubling From Tweakable Block Ciphers
Abstract
We present a length doubler, LDT, that turns an n-bit tweakable block cipher into an efficient and secure cipher that can encrypt any bit string of length [n..2n − 1]. The LDT mode is simple, uses only two cryptographic primitive calls (while prior work needs at least four), and is a strong length-preserving pseudorandom permutation if the underlying tweakable block ciphers are strong tweakable pseudorandom permutations. We demonstrate that LDT can be used to neatly turn an authenticated encryption scheme for integral data into a mode for arbitrary-length data.
2015
EPRINT
2012
FSE
2010
EPRINT
MQ^*-IP: An Identity-based Identification Scheme without Number-theoretic Assumptions
Abstract
In this article, we propose an identification scheme which is based on
the two combinatorial problems Multivariate
Quadratic equations (MQ) and Isomorphism of Polynomials (IP).
We show that this scheme is statistical zero-knowledge.
Using a trapdoor for the MQ-problem, it is possible to make it also identity-based, i.e., there is no need for distributing public keys or for certificates within this scheme.
The size of the public keys and the communication complexity\
are within the range of other non-number-theoretic identification schemes. In contrast to MQ^*-IP, these schemes do usually no permit identity-based public keys.
2010
EPRINT
Related-Key Boomerang and Rectangle Attacks
Abstract
This paper introduces the related-key boomerang and the related-key
rectangle attacks. These new attacks
can expand the cryptanalytic toolbox, and can be applied to
many block ciphers. The main advantage of these new attacks, is the ability
to exploit the related-key model twice. Hence, even ciphers which were
considered resistant to either boomerang or related-key differential attacks
may be broken using the new techniques.
In this paper we present a rigorous treatment of the related-key boomerang and
the related-key rectangle distinguishers. Following this treatment, we
devise optimal distinguishing algorithms using the LLR
(Logarithmic Likelihood Ratio)
statistics. We then analyze the success probability under
reasonable independence assumptions, and verify the
computation experimentally by implementing an actual attack on a
6-round variant of KASUMI. The paper ends with a demonstration of the strength
of our new proposed techniques with attacks on 10-round AES-192 and the full
KASUMI.
2010
EPRINT
Increased Resilience in Threshold Cryptography: Sharing a Secret with Devices That Cannot Store Shares
Abstract
Threshold cryptography has been used to secure data and control access by sharing a private cryptographic key over different devices. This means that a minimum number of these devices, the threshold $t+1$, need to be present to use the key. The benefits are increased security, because an adversary can compromise up to $t$ devices, and resilience, since any subset of $t+1$ devices is sufficient.
Many personal devices are not suitable for threshold schemes, because they do not offer secure storage, which is needed to store shares of the private key. This article presents several protocols in which shares are stored in protected form (possibly externally). This makes them suitable for low-cost devices with a factory-embedded key, e.g., car keys and access cards. All protocols are verifiable through public broadcast, thus without private channels. In addition, distributed key generation does not require all devices to be present.
2010
EPRINT
On the Indifferentiability of the Gr{\o}stl Hash Function
Abstract
The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the exhibited bounds. In this work we prove the indifferentiability of Gr{\o}stl, a second round SHA-3 hash function candidate. Gr{\o}stl combines characteristics of the wide-pipe and chop-Merkle-Damg{\aa}rd iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Gr{\o}stl, we prove that the advantage of a distinguisher to differentiate Gr{\o}stl from a random oracle is upper bounded by O((Kq)^4/2^l), where the distinguisher makes at most q queries of length at most K blocks. For the specific Gr{\o}stl parameters, this result implies that Gr{\o}stl behaves like a random oracle up to q=O(2^{n/2}) queries, where n is the output size.
Furthermore, we show that the output transformation of Gr{\o}stl, as well as `Gr{\o}stail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This renders out indifferentiability proofs which rely on the idealness of a final state transformation.
2010
EPRINT
Improved Collision Attacks on the Reduced-Round Gr{\o}stl Hash Function
Abstract
We analyze the Gr{\o}stl hash function, which is a 2nd-round candidate of the SHA-3 competition.
Using the start-from-the-middle variant of the rebound technique, we
show collision attacks on the Gr{\o}stl-256 hash function reduced to
5 and 6 out of 10 rounds with time complexities $2^{48}$ and $2^{112}$, respectively.
Furthermore, we demonstrate semi-free-start collision attacks on the
Gr{\o}stl-224 and -256 hash functions reduced to 7 rounds and the Gr{\o}stl-224 and -256 compression functions reduced to 8 rounds.
Our attacks are based on differential paths between the two permutations $P$ and $Q$ of Gr{\o}stl, a strategy introduced by Peyrin to construct distinguishers for the compression function.
In this paper, we extend this approach to construct collision and semi-free-start collision attacks for both the hash and the compression function.
Finally, we present improved distinguishers for reduced-round versions of the Gr{\o}stl-224 and -256 permutations.
2010
EPRINT
Security Reductions of the Second Round SHA-3 Candidates
Abstract
In 2007, the US National Institute for Standards and Technology announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. At present, 14 candidates are left in the second round. An important criterion in the selection process is the SHA-3 hash function security and more concretely, the possible security reductions of the hash function to the security of its underlying building blocks. While some of the candidates are supported with firm security reductions, for most of the schemes these results are still incomplete. In this paper, we compare the state of the art provable security reductions of the second round candidates. We discuss all SHA-3 candidates at a high functional level, and analyze and summarize the security reduction results. Surprisingly, we derive some security bounds from the literature, which the hash function designers seem to be unaware of. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.
2008
EPRINT
Collisions and other Non-Random Properties for Step-Reduced SHA-256
Abstract
We study the security of step-reduced but otherwise unmodified SHA-256. We show the first collision attacks on SHA-256 reduced to 23 and 24 steps with complexities $2^{18}$ and $2^{28.5}$, respectively. We give example colliding message pairs for 23-step and 24-step SHA-256. The best previous, recently obtained result was a collision attack for up to 22 steps. We extend our attacks to 23 and 24-step reduced SHA-512 with respective complexities of $2^{44.9}$ and $2^{53.0}$. Additionally, we show non-random behaviour of the SHA-256 compression function in the form of free-start near-collisions for up to 31 steps, which is 6 more steps than the recently obtained non-random behaviour in the form of a free-start near-collision. Even though this represents a step forwards in terms of cryptanalytic techniques, the results do not threaten the security of applications using SHA-256.
2007
EPRINT
Weaknesses in the Pseudorandom Bit Generation Algorithms of the Stream Ciphers TPypy and TPy
Abstract
The stream ciphers Py, Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM
project in 2005. However, due to several recent cryptanalytic attacks on them, a
strengthened version Pypy was proposed to rule out those attacks. The ciphers have been
promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. The impressive
speed of the ciphers make them the forerunners in the competition. Unfortunately, even the
new cipher Pypy was found to retain weaknesses, forcing the designers to again go for
modifications. As a result, three new ciphers TPypy, TPy and TPy6 were built. Among all the
members of the Py-family of ciphers, the TPypy is conjectured to be the strongest. So far,
there is no known attack on the TPypy. This paper shows that the security of TPypy does not
grow exponentially with the key-size. The main achievement of the paper is the detection of
input-output correlations of TPypy that allow us to build a distinguisher with $2^{281}$
randomly chosen key/IVs and as many outputwords (each key generating one outputword). The
cipher TPypy was claimed by the designers to be secure with keysize up to 256 bytes, i.e.,
2048 bits. Our results establish that the TPypy fails to provide adequate security if the
keysize is longer than 35 bytes, i.e., 280 bits. Note that the distinguisher is built
within the design specifications of the cipher. Because of remarkable similarities between
the TPypy and the TPy, our attacks are shown to be effective for TPy also. The paper also
points out how the other members of the Py-family (i.e., Pypy and Py) are also weak against
the current attacks.
2007
EPRINT
Cryptanalysis of White-Box DES Implementations with Arbitrary External Encodings
Abstract
At DRM 2002, Chow et al. presented a method for implementing the DES block cipher such that it becomes hard to extract the embedded secret key in a white-box attack context. In such a context, an attacker has full access to the implementation and its execution environment. In order to provide an extra level of security, an implementation shielded with external encodings was introduced by Chow et al. and improved by Link and Neumann. In this paper, we present an algorithm to extract the secret key from such white-box DES implementations. The cryptanalysis is a differential attack on obfuscated rounds, and works regardless of the shielding external encodings that are applied. The cryptanalysis has a average time complexity of $2^{14}$ and a negligible space complexity.
2007
EPRINT
Seven-Property-Preserving Iterated Hashing: ROX
Abstract
Nearly all modern hash functions are constructed by iterating a
compression function. At FSE'04, Rogaway and Shrimpton [RS04] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations.
Our study points out that none of them preserves more than three
notions from [RSh04]. In particular, only a single iteration preserves Pre, and none preserves Sec, aSec, or aPre. The latter two notions are particularly relevant for practice, because they do not rely on the problematic assumption that practical compression functions be chosen uniformly from a family. In view of this poor state of affairs, even the mere existence of seven-property-preserving iterations seems uncertain.
As a second contribution, we propose the new Random-Oracle XOR(ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.
2007
EPRINT
New Weaknesses in the Keystream Generation Algorithms of the Stream Ciphers TPy and Py
Abstract
The stream ciphers Py, Py6 designed by Biham and Seberry were promising
candidates in the
ECRYPT-eSTREAM project because of their impressive speed. Since their
publication in April
2005, a number of cryptanalytic weaknesses of the ciphers have been
discovered. As a
result, a strengthened version Pypy was developed to repair these
weaknesses; it was
included in the category of `Focus ciphers' of the Phase II of the
eSTREAM competition.
However, even the new cipher Pypy was not free from flaws, resulting in
a second redesign.
This led to the generation of three new ciphers TPypy, TPy and TPy6. The
designers claimed
that TPy would be secure with a key size up to 256 bytes, i.e., 2048
bits. In February
2007, Sekar \emph{et al.\ }published an attack on TPy with $2^{281}$
data and comparable
time. This paper shows how to build a distinguisher with $2^{275}$
key/IVs and one
outputword for each key (i.e., the distinguisher can be constructed
within the design
specifications); it uses a different set of weak states of the TPy. Our
results show that distinguishing attacks with complexity lower than the
brute force
exist if the key size of TPy is longer than 275 bits. Therefore, for
such keys, our attack constitutes an academic break of the cipher.
Furthermore, we discover a large number of similar bias-producing
states of TPy and provide a general framework to compute them. The
attacks on TPy are also shown to be effective on Py.
2007
EPRINT
New Attacks on the Stream Cipher TPy6 and Design of New Ciphers the TPy6-A and the TPy6-B
Abstract
The stream ciphers Py, Pypy and Py6 were designed by Biham and Seberry for the
ECRYPT-eSTREAM project in 2005. The ciphers were promoted to the `Focus' ciphers of the
Phase II of the eSTREAM project. However, due to some cryptanalytic results on the
ciphers, strengthened versions of the ciphers, namely TPy, TPypy and TPy6 were built. So
far there exists no attacks on TPy6. In this paper, we find hitherto unknown weaknesses in
the keystream generation algorithms of the Py6 and of its stronger variant TPy6. Exploiting
these weaknesses, a large number of distinguishing attacks are mounted on the ciphers, the
best of which works with $2^{224.6}$ data and comparable time. In the second part, we present two new
ciphers derived from the TPy6, namely TPy6-A and TPy6-B, whose performances are 2.65
cycles/byte and 4.4 cycles/byte on Pentium III. As a result, to the best of our knowledge,
on Pentium platforms TPy6-A becomes the fastest stream cipher in the literature. Based on our security analysis,
we conjecture that no attacks better than brute force are possible on the ciphers TPy6-A and
TPy6-B.
2006
EPRINT
On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1
Abstract
HMAC is a widely used message authentication code and a
pseudorandom function generator based on cryptographic hash
functions such as MD5 and SHA-1. It has been standardized by ANSI,
IETF, ISO and NIST. HMAC is proved to be secure as long as the
compression function of the underlying hash function is a
pseudorandom function. In this paper we devise two new
distinguishers of the structure of HMAC, called {\em differential}
and {\em rectangle distinguishers}, and use them to discuss the
security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. We
show how to distinguish HMAC with reduced or full versions of
these cryptographic hash functions from a random function or from
HMAC with a random function. We also show how to use our
differential distinguisher to devise a forgery attack on HMAC. Our
distinguishing and forgery attacks can also be mounted on NMAC
based on HAVAL, MD4, MD5, SHA-0 and SHA-1. Furthermore, we show
that our differential and rectangle distinguishers can lead to
second-preimage attacks on HMAC and NMAC.
2006
EPRINT
A Weakness in Some Oblivious Transfer and Zero-Knowledge Protocols
Abstract
We consider oblivious transfer protocols and their applications that
use underneath semantically secure homomorphic encryption scheme
(e.g. Paillier's). We show that some oblivious transfer protocols
and their derivatives such as private matching, oblivious polynomial
evaluation and private shared scalar product could be subject to an
attack. The same attack can be applied to some non-interactive
zero-knowledge arguments which use homomorphic encryption schemes
underneath. The roots of our attack lie in the additional property
that some semantically secure encryption schemes possess, namely,
the decryption also reveals the random coin used for the encryption,
and that the (sender's or prover's) inputs may belong to a space,
that is very small compared to the plaintext space. In this case it
appears that even a semi-honest chooser (verifier) can derive from
the random coin bounds for all or some of the sender's (prover's)
private inputs with non-negligible probability. We propose a fix
which precludes the attacks.
2005
EPRINT
Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations
Abstract
Multivariate quadratic systems can be used to construct both secure and efficient public key schemes. In this article, we introduce the necessary mathematical tools to deal with multivariate quadratic systems, present an overview of important schemes known so far and outline how they fit into a taxonomy of only four basic schemes and some generic modifiers. Moreover, we suggest new constructions not previously considered. In this context, we propose some open problems and new research directions in the field of multivariate quadratic schemes.
2005
EPRINT
On the Algebraic Immunity of Symmetric Boolean Functions
Abstract
In this paper, we analyse the algebraic immunity of symmetric Boolean functions. We identify a set of lowest degree annihilators for symmetric functions and propose an efficient algorithm for computing the algebraic immunity of a symmetric function. The existence of several symmetric functions with maximum algebraic immunity is proven. In this way, a new class of function which have good implementation properties and maximum algebraic immunity is found. We also investigate the existence of symmetric functions with high nonlinearity and reasonable order of algebraic immunity. Finally, we give suggestions how to use symmetric functions in a stream cipher.
2005
EPRINT
On the Security of Encryption Modes of MD4, MD5 and HAVAL
Abstract
MD4 is a cryptographic hash function introduced in 1990 by Rivest.
After MD4 was proposed, several hash functions such as MD5, HAVAL,
RIPEMD, RIPEMD-160, SHA-1 and SHA-256 were designed based on the
MD4 structure. In this paper, we cryptanalyze the compression
functions of MD4, MD5 and 4-, 5-pass HAVAL in encryption modes. We
exploit the recently proposed related-key rectangle and boomerang
techniques to show non-randomness of MD4, MD5 and 4-, 5-pass HAVAL
and to distinguish them from a randomly chosen cipher. The attacks
are highly practical and have been confirmed by our experiments.
2005
EPRINT
Classification of Cubic $(n-4)$-resilient Boolean Functions
Abstract
Carlet and Charpin classified in \cite{CC04} the set of cubic $(n-4)$-resilient Boolean functions into four different types with respect to the Walsh spectrum and the dimension of the linear space. Based on the classification of $RM(3,6)/RM(1,6)$, we completed the classification of the cubic $(n-4)$-resilient Boolean function by deriving the corresponding ANF and autocorrelation spectrum for each of the four types. In the same time, we solved an open problem of \cite{CC04} by proving that all plateaued cubic $(n-4)$-resilient Boolean functions have dimension of the linear space equal either to $n-5$ or $n-6$.
2005
EPRINT
On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)
Abstract
Stream ciphers play an important role in symmetric cryptology because of
their suitability in high speed applications where block ciphers fall short. A large number
of fast stream ciphers or pseudorandom bit generators (PRBG's) can be found in the
literature that are based on arrays and simple operations such as modular additions,
rotations and memory accesses (e.g. RC4, RC4A, Py, Py6, ISAAC etc.). This paper
investigates the security of array-based stream ciphers (or PRBG's) against certain types
of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most
useful characteristic of an array, namely, the association of array-elements with unique
indices, may turn out to be the origins of distinguishing attacks if adequate caution is
not maintained. In short, an adversary may attack a cipher simply exploiting the dependence
of array-elements on the corresponding indices. Most importantly, the weaknesses are not
eliminated even if the indices and the array-elements are made to follow uniform
distributions separately. Exploiting these weaknesses we build distinguishing attacks with
reasonable advantage on five recent stream ciphers (or PRBG's), namely, Py6 (2005, Biham
\emph{et al.}), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong \emph{et al.}) with
data complexities $2^{68.61}$, $2^{32.89}$, $2^{16.89}$, $2^{32.89}$ and $2^{32.89}$
respectively. In all the cases we worked under the assumption that the key-setup algorithms
of the ciphers produced uniformly distributed internal states. We only investigated the
mixing of bits in the keystream generation algorithms. In hindsight, we also observe that
the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be
explained in the general framework developed in this paper. We hope that our analyses will
be useful in the evaluation of the security of stream ciphers based on arrays and modular
addition.
2005
EPRINT
Equivalent Keys in Multivariate Quadratic Public Key Systems
Abstract
Multivariate Quadratic public key schemes have been suggested back in 1985 by Matsumoto and Imai
as an alternative for the RSA scheme.
Since then, several other schemes have been proposed, for example Hidden Field Equations,
Unbalanced Oil and Vinegar schemes, and Stepwise Triangular Schemes.
All these schemes have a rather large key space for a secure choice of parameters.
Surprisingly, the question of equivalent keys has not been discussed in the open literature
until recently.
In this article, we show that for all basic classes mentioned above,
it is possible to reduce the private --- and hence the public ---
key space by several orders of magnitude. For the Matsumoto-Imai scheme, we are even able to show that
the reductions we found are the only ones possible, i.e., that these reductions are tight.
While the theorems developed in this article are of independent interest themselves
as they broaden our understanding of Multivariate Quadratic public key systems,
we see applications of our results both in cryptanalysis and in
memory efficient implementations of MQ-schemes.
2004
CHES
2004
FSE
2004
EPRINT
Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality
Abstract
A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.
2004
EPRINT
Extending the Resynchronization Attack
Abstract
Synchronous stream ciphers need perfect synchronization between
sender and receiver. In practical applications, this is ensured by a
resync mechanism. Daemen et al first described attacks on ciphers using such a resync mechanism. In this paper, we extend their attacks in several ways by combining the standard attack with several cryptanalytic techniques such as algebraic attacks and linear cryptanalysis. Our results show that using linear resync mechanisms should be avoided, and give lower bounds for the nonlinearity required from a secure resync mechanism.
2004
EPRINT
Equivalent Keys in HFE, C$^*$, and variations
Abstract
In this article, we investigate the question of equivalent keys for
two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic
public key schemes HFE and C$^{*--}$ and
improve over a previously known result, to appear at PKC 2005.
Moreover, we show a new non-trivial extension of these results to the
classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically
stronger variants of the original
HFE and C$^*$ schemes.
In particular, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
While the results are of independent interest themselves,
we also see applications both in cryptanalysis
and in memory efficient implementations.
2004
EPRINT
Superfluous Keys in Multivariate Quadratic Asymmetric Systems
Abstract
In this article, we show that public key schemes based on multivariate quadratic
equations allow many equivalent, and hence superfluous private keys.
We achieve this result by investigating several transformations to identify these keys and
show their application to Hidden Field Equations (HFE), C$^*$,
and Unbalanced Oil and Vinegar schemes (UOV).
In all cases, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
We see applications of our technique both in cryptanalysis of these
schemes and in memory efficient implementations.
2004
EPRINT
Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties
Abstract
This paper presents an efficient approach for classification of
the affine equivalence classes of cosets of the first order
Reed-Muller code with respect to cryptographic properties such as
correlation-immunity, resiliency and propagation characteristics.
First, we apply the method to completely classify all the $48$
classes into which the general affine group $AGL(2,5)$ partitions
the cosets of $RM(1,5)$. Second, we describe how to find the affine
equivalence classes together with their sizes of Boolean functions in 6 variables.
We perform the same classification for these classes. Moreover, we
also determine the classification of $RM(3,7)/RM(1,7)$.
We also study the algebraic immunity of the corresponding affine equivalence classes.
Moreover, several relations are derived between the algebraic immunity
and other cryptographic properties.
Finally, we introduce two new indicators which can be used to distinguish
affine inequivalent Boolean functions when the known criteria are
not sufficient. From these indicators a method can be derived for
finding the affine relation between two functions (if such
exists). The efficiency of the method depends on the structure of
the Walsh or autocorrelation spectrum.
2004
EPRINT
On Boolean Functions with Generalized Cryptographic Properties
Abstract
By considering a new metric, we generalize cryptographic
properties of Boolean functions such as resiliency and propagation
characteristics. These new definitions result in a better understanding
of the properties of Boolean functions and provide a better insight in
the space defined by this metric. This approach leads to the
construction of ``hand-made'' Boolean functions, i.e., functions for
which the security with respect to some specific monotone sets of inputs
is considered, instead of the security with respect to all possible
monotone sets with the same cardinality, as in the usual definitions.
This approach has the advantage that some trade-offs between important
properties of Boolean functions can be relaxed.
2004
EPRINT
Solving Systems of Differential Equations of Addition
Abstract
Mixing addition modulo $2^n$ ($+$) and exclusive-or ($\oplus$) have a host of applications
in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with
a frequently encountered equation $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. The difficulty
of solving an arbitrary system of such equations -- named \emph{differential equations of
addition} (DEA) -- is an important consideration in the evaluation of the security of many
ciphers against \emph{differential attacks}. This paper shows that the satisfiability of an
arbitrary set of DEA -- which has so far been assumed \emph{hard} for large $n$ -- is in
the complexity class P. We also design an efficient algorithm to obtain all solutions to an
arbitrary system of DEA with running time linear in the
number of solutions.\\
Our second contribution is solving DEA in an \emph{adaptive query model} where an equation
is formed by a query $(\x,\y)$ and oracle output $\z$. The challenge is to optimize the
number of queries to solve $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. Our algorithm solves
this equation with only 3 queries in the worst case. Another algorithm solves the equation
$(x+y)\oplus(x+(y\oplus\y))=\z$ with $(n-t-1)$ queries in the worst case ($t$ is the
position of the least significant `1' of $x$), and thus, outperforms the previous best
known algorithm by Muller -- presented at FSE~'04 -- which required $3(n-1)$ queries. Most
importantly, we show that the upper bounds, for our algorithms, on the number of queries
match worst case lower bounds. This, essentially, closes further research in this direction
as our lower bounds are \emph{optimal}. Finally we describe applications of our results in
\emph{differential
cryptanalysis.
2003
EPRINT
Cryptanalysis of the Alleged SecurID Hash Function
Abstract
The SecurID hash function is used for authenticating users to a
corporate computer infrastructure. We analyse an alleged
implementation of this hash function. The block cipher at the
heart of the function can be broken in few milliseconds on a PC
with 70 adaptively chosen plaintexts. The 64-bit secret key of
10$\%$ of the cards can be discovered given two months of token
outputs and $2^{48}$ analysis steps. A larger fraction of cards
can be covered given more observation time.
2003
EPRINT
Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case
Abstract
We use a general treatment of both information-theoretic and cryptographic settings for
Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme.
Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication
of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes.
First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures
and we prove some properties of the resulting MSP ${\cal M}$.
Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC.
Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary).
The knowledge of the resulting MSP and the access structure it computes allows us to build an analog
of the algebraic simplification protocol of Gennaro et~al.
We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case,
through the application of homomorphic commitments.
There is an open problem how efficiently we can determine $\Gamma$ the access structure of the resulting MSP
${\cal M}$. This open problem reflects negatively on the efficiency of the proposed solution.
2002
EPRINT
Square Attacks on Reduced-Round Variants of the Skipjack Block Cipher
Abstract
This report surveys on a series of Square attacks on reduced-round
versions of the Skipjack block cipher.
{\bf Skipjack} is an iterated block cipher encrypting 64-bit plaintext
blocks into 64-bit ciphertext blocks, using an 80-bit key. Its
design is based on a generalized Feistel Network making up 32 rounds
of two different types. This cipher was developed by the National Security
Agency for the Clipper chip and Fortezza PC card.
2002
EPRINT
A note on Weak Keys of PES, IDEA and some Extended Variants
Abstract
This paper presents an analysis of the PES cipher in a similar setting as
done by Daemen et al. at Crypto'93 for IDEA. The following results were
obtained for 8.5 round PES: a linear weak-key class of size
$2^{48}$; two distinct differential weak-key classes of size $2^{41}$; two
differential-linear weak-key classes of size $2^{62}$. For 17-round PES
(double-PES): a linear weak-key class of size $2^7$, and a differential
weak-key class of size $2^7$ were found. Daemen suggested a modified key
schedule for IDEA in order to avoid weak keys. We found a differential
weak-key class of size $2^{83}$ for 2.5-round IDEA under his redesigned
key schedule, and differential-linear relations for 3.5-round IDEA.
2002
EPRINT
Applying General Access Structure to Metering Schemes
Abstract
In order to decide on advertisement fees for web servers, Naor and Pinkas introduced metering schemes secure against coalition of corrupt servers and clients. In their schemes any server is able to construct a proof to be sent to an audit agency if and only if it has been
visited by at least a certain number of clients. Several researchers have generalized the idea of Naor and Pinkas: first metering scheme with pricing and dynamic multi-threshold metering schemes have been proposed; later the solution has been extended to allow for
general access structures and an approach on linear algebra has been introduced. In this paper we are interested in the efficiency of applying general access structures and linear algebra techniques to metering schemes. We propose a new model considering general access structures for clients, corrupted clients and servers. Then we bind the
access structures for clients and corrupted clients into one. We propose a new metering scheme, which is more efficient w.r.t.\ communication complexity and memory requirements than the scheme of Blundo \textit{et al.}
2002
EPRINT
Applying General Access Structure to Proactive Secret Sharing Schemes
Abstract
Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer \cite{CDM99,CDM00,Cra00}.
They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the
monotone span program model of Karchmer and Wigderson \cite{KW93} deals with arbitrary monotone access structures and not just threshold ones. Stinson and Wei \cite{SW99} proposed a proactive SSS based on threshold (polynomial) VSS. The purpose of this paper is to build unconditionally secure proactive SSS over any access structure, as long as it admits a linear secret sharing scheme (LSSS).
2001
EPRINT
SQUARE Attacks on Reduced-Round PES and IDEA Block Ciphers
Abstract
This paper reports on variants of the Square attack applied to
reduced-round versions of the PES and IDEA block ciphers. Attacks
on 2.5 rounds of IDEA require $3\cdot 2^{16}$ chosen-plaintexts and
recover 78 key bits. A new kind of attack, the Square
related-key attack, is applied on 2.5 rounds of IDEA and recovers
32 key bits, with 2 chosen-plaintexts and $2^{17}$
related keys. Similar results hold for 2.5 rounds of PES.
Implementations of the attacks on 32-bit block mini-versions of both
ciphers confirmed the expected computational complexity. Although
our attacks do not improve on previous approaches, this report shows
new variants of the Square attack on word-oriented block ciphers
like IDEA and PES.
1994
FSE
1989
CRYPTO
Program Committees
- FSE 2020
- Eurocrypt 2019
- FSE 2019
- Eurocrypt 2018
- FSE 2018
- Asiacrypt 2017
- FSE 2017
- Crypto 2016
- CHES 2015
- Asiacrypt 2015
- Crypto 2015
- Crypto 2012
- Asiacrypt 2012
- Crypto 2011
- CHES 2011
- FSE 2010
- Eurocrypt 2010
- Crypto 2009
- Asiacrypt 2009
- FSE 2009
- Asiacrypt 2008
- FSE 2008
- Crypto 2007
- FSE 2007
- Asiacrypt 2007
- Asiacrypt 2006
- FSE 2006
- Crypto 2006
- CHES 2005
- FSE 2005
- Eurocrypt 2005
- FSE 2004
- Asiacrypt 2004
- Crypto 2004
- CHES 2003
- FSE 2003
- Crypto 2003
- Crypto 2002
- FSE 2002
- Asiacrypt 2002
- Eurocrypt 2002
- CHES 2002
- FSE 2001
- CHES 2001
- Crypto 2000
- Eurocrypt 2000
- FSE 2000
- Crypto 1999
- FSE 1999
- FSE 1998
- Eurocrypt 1998
- Eurocrypt 1997
- FSE 1997
- Asiacrypt 1996
- Eurocrypt 1996
- FSE 1996
- Crypto 1996
- FSE 1994
- Asiacrypt 1994
- Eurocrypt 1993
- FSE 1993
Coauthors
- Sergey Agievich (1)
- Elena Andreeva (4)
- Frederik Armknecht (1)
- Victor Arribas (1)
- Tomer Ashur (1)
- Steve Babbage (1)
- Paulo S. L. M. Barreto (2)
- Lejla Batina (3)
- Filipe Beato (1)
- Eli Biham (2)
- Gert Bijnens (2)
- Alex Biryukov (5)
- Yuri Borissov (2)
- Johan Borst (1)
- Antoon Bosselaers (3)
- An Braeken (6)
- Johan Buelens (1)
- Christophe De Cannière (3)
- Christophe De Cannière (1)
- David Chaum (1)
- Yu Long Chen (1)
- Carl D'Halluin (2)
- Joan Daemen (1)
- Hans Dobbertin (1)
- Orr Dunkelman (2)
- Walter Fumy (1)
- Soichi Furuya (1)
- Flavio D. Garcia (1)
- Benedikt Gierlichs (4)
- Paul Gorissen (1)
- Anastasiya Gorodilova (1)
- René Govaerts (6)
- H.Y.Kim (1)
- Helena Handschuh (2)
- Anthony Van Herrewege (1)
- Alireza Hodjat (1)
- Dowon Hong (1)
- Seokhie Hong (4)
- Deukjo Hong (1)
- David Hwang (1)
- Kota Ideguchi (1)
- Sebastiaan Indesteege (4)
- Cees J. A. Jansen (1)
- Jorge Nakahara Jr. (5)
- Ju-Sung Kang (1)
- Nathan Keller (2)
- Jongsung Kim (5)
- Hae Yong Kim (1)
- Jun Kitahara (1)
- Lars R. Knudsen (4)
- Nikolay Kolomeec (1)
- Özgül Küçük (1)
- Xuejia Lai (1)
- Peter Landrock (1)
- Joseph Lano (3)
- Sangjin Lee (3)
- Werner Van Leekwijck (1)
- Vincent van der Leest (1)
- Luc Van Linden (1)
- Atul Luykx (4)
- Eduard Marin (1)
- Willi Meier (1)
- Florian Mendel (1)
- Bart Mennink (8)
- Wil Michiels (1)
- Nicky Mouha (3)
- María Naya-Plasencia (1)
- Wim Nevelsteen (1)
- Gregory Neven (2)
- Ventzislav Nikov (6)
- Svetla Nikova (9)
- Marnix Nuttin (1)
- Katsuyuki Okeya (1)
- Paul C. van Oorschot (2)
- Siddika Berna Örs (2)
- Elisabeth Oswald (1)
- David Oswald (1)
- Souradyuti Paul (8)
- Roel Peeters (1)
- Michaël Quisquater (1)
- Christian Rechberger (1)
- Vincent Rijmen (11)
- Gert Roelofsen (1)
- Bart Van Rompay (2)
- Heuisu Ryu (1)
- Kazuo Sakiyama (1)
- Gautham Sekar (4)
- Taizo Shirai (1)
- Thomas Shrimpton (2)
- George Shushuev (1)
- Koen Simoens (1)
- Erik van der Sluis (1)
- François-Xavier Standaert (1)
- Yue Sun (1)
- Iraklis Symeonids (1)
- Alan Szepieniec (2)
- Kazuo Takaragi (1)
- Elmar Tischhauser (3)
- Natalia Tokareva (1)
- Pagona Tsormpatzoudi (1)
- Pim Tuyls (1)
- Jan Van den Herrewegen (1)
- Joos Vandewalle (19)
- Vesselin Velichkov (2)
- Ingrid Verbauwhede (3)
- Frederik Vercauteren (1)
- Sven Verdoolaege (1)
- Valeriya Vitkup (1)
- Meiqin Wang (1)
- Dai Watanabe (3)
- Erik De Win (1)
- Christopher Wolf (7)
- Lennert Wouters (3)
- Hongjun Wu (5)
- Brecht Wyseur (1)
- Kan Yasuda (2)
- Hirotaka Yoshida (2)