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.

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

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.

Preface to Volume 2017, Issue 1

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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$.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.}

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).

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.