Selected Areas in Cryptography

It is widely believed that genus four hyperelliptic curve cryptosystems (HECC) are not attractive for practical applications because of their complexity compared to systems based on lower genera, especially elliptic curves. Our contribution shows that for low cost security applications genus-4 hyperelliptic curves (HEC) can outperform genus-2 HEC and that we can achieve a performance similar to genus-3 HEC. Furthermore our implementation results show that a genus-4 HECC is an alternative cryptosystem to systems based on elliptic curves.

In the work at hand we present for the first time explicit formulae for genus-4 HEC, resulting in a 60% speed-up compared to the best published results. In addition we implemented genus-4 HECC on a Pentium4 and an ARM microprocessor. Our implementations on the ARM show that for genus four HECC are only a factor of 1.66 slower than genus-2 curves considering group order ≈ 2¹⁹⁰. For the same group order ECC and genus-3 HECC are about a factor of 2 faster than genus-4 curves on the ARM. The two most surprising results are: 1) for low cost security application, namely considering an underlying group of order 2¹²⁸, HECC with genus 4 outperform genus-2 curves by a factor of 1.46 and has similar performance to genus-3 curves on the ARM and 2) when compared to genus-2 and genus-3, genus-4 HECC are better suited to embedded microprocessors than to general purpose processors.

We propose a simple algorithm to select group generators suitable for pairing-based cryptosystems. The selected parameters are shown to favor implementations of the Tate pairing that are at once conceptually simple and efficient, with an observed performance about 2 to 10 times better than previously reported implementations, depending on the embedding degree. Our algorithm has beneficial side effects: various non-pairing operations become faster, and bandwidth may be saved.

Counting rational points on Jacobian varieties of hyperelliptic curves over finite fields is very important for constructing hyperelliptic curve cryptosystems (HCC), but known algorithms for general curves over given large prime fields need very long running time. In this article, we propose an extremely fast point counting algorithm for hyperelliptic curves of type y ²=x ⁵+ax over given large prime fields \(\mathbb{F}_{p}\), e.g. 80-bit fields. For these curves, we also determine the necessary condition to be suitable for HCC, that is, to satisfy that the order of the Jacobian group is of the form l· c where l is a prime number greater than about 2¹⁶⁰ and c is a very small integer. We show some examples of suitable curves for HCC obtained by using our algorithm. We also treat curves of type y ²=x ⁵+a where a is not square in \(\mathbb{F}_{p}\).

Increasing key length is a standard counter-measure to cryptanalysis. However, longer key length generally means greater side channel leakage. For embedded RSA crypto-systems the increase in leaked data outstrips the increase in secret data so that, in contrast to the improved mathematical strength, longer keys may, in fact, lead to lower security. This is investigated for two types of implementation attack. The first is a timing attack in which squares and multiplications are differentiated from the relative frequencies of conditional subtractions over several exponentiations. Once keys are large enough, longer length seems to decrease security. The second case is a power analysis attack on a single m-ary exponentiation using a single k-bit hardware multiplier. For this, despite certain counter-measures such as exponent blinding, uncertainty in determining the secret bits decreases so quickly that longer keys appear to be noticeably less secure.

Differential power analysis (DPA) attacks can be of major concern when applied to cryptosystems that are embedded into small devices such as smart cards. To immunize elliptic curve cryptosystems (ECCs) against DPA attacks, recently several countermeasures have been proposed. A class of countermeasures is based on randomizing the paths taken by the scalar multiplication algorithm throughout its execution which also implies generating a random binary signed-digit (BSD) representation of the scalar. This scalar is an integer and is the secret key of the cryptosystem. In this paper, we investigate issues related to the BSD representation of an integer such as the average and the exact number of these representations, and integers with maximum number of BSD representations within a specific range. This knowledge helps a cryptographer to choose a key that provides better resistance against DPA attacks. Here, we also present an algorithm that generates a random BSD representation of an integer starting from the most significant signed bit. We also present another algorithm that generates all existing BSD representations of an integer to investigate the relation between increasing the number of bits in which an integer is represented and the increase in the number of its BSD representations.

Ad-hoc networks and even more intrinsic pervasive networks face huge security lacks. In the most general case entities need to build up a well-defined security association without any pre-established secret or common security infrastructure. Under these circumstances it turns out that without unrealistic assumptions authentication of previously unknown parties is not achievable. However, for a wide spectrum of scenarios much weaker authentication forms are reasonable, e.g., for routing protocols and other protocols aiming to intensify cooperation. Like in real world when foreign subjects meet for the very first time, inferring the opposites identity is impossible. Nevertheless even from this zero common-knowledge status some minor level of trust establishment is possible for both scenarios, in real world and on a technical level. In this paper we will present a very light-weight still provably secure authentication protocol not aiming at inferring the involved entities’ identities but re-recognizing foreign communication partners whenever necessary. We do not make any assumptions to the scenario, and we also have no requirements for the devices’ abilities. For the technical realization we propose extremely efficient security primitives applicable for nearly all types of restricted devices. Our solution is more efficient than a public-key operation by some orders of magnitude.

Blakley, Blakley, Chan and Massey conjectured a lower bound on the entropy of broadcast messages in threshold schemes with disenrollment. In an effort to examine the conjecture, we identify their original scheme definition has a limitation: a coalition of participants can reconstruct all shared secrets without broadcast from the dealer, and hence render the dealer no control over disenrollment. We introduce a constraint that delays this lack of control of the dealer over disenrollment. We also establish the lower bounds on the entropy of broadcast messages in such a model. We demonstrate the need for new models by presenting a construction under an open problem.

In this paper we introduce a novel meet-in-the-middle attack on the IDEA block cipher. The attack consists of a precomputation and an elimination phase. The attack reduces the number of required plaintexts significantly for 4 and 4.5 rounds, and, to the best of our knowledge, it is the first attack on the 5-round IDEA.

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⁴⁸ analysis steps. A larger fraction of cards can be covered given more observation time.

In this paper, we investigate the authenticated encryption paradigm, and its security against blockwise adaptive adversaries, mounting chosen ciphertext attacks on on-the-fly cryptographic devices. We remark that most of the existing solutions are insecure in this context, since they provide a decryption oracle for any ciphertext. We then propose a generic construction called Decrypt-Then-Mask, and prove its security in the blockwise adversarial model. The advantage of this proposal is to apply minimal changes to the encryption protocol. In fact, in our solution, only the decryption protocol is modified, while the encryption part is left unchanged. Finally, we propose an instantiation of this scheme, using the encrypted CBC-MAC algorithm, a secure pseudorandom number generator and the Delayed variant of the CBC encryption scheme.

Golle, Zhong, Boneh, Jakobsson, and Juels [9] recently presented an efficient mix-net, which they claim to be both robust and secure. We present five practical attacks for their mix-net, and break both its privacy and robustness.

The fourth attack may be viewed as a novel combination of the ideas of Lim and Lee [16] and Pfitzmann [24, 23]. It breaks the privacy of any given sender, and requires that the first and last mix-servers are corrupted. This attack breaks also Jakobsson [14], including the fixed version of Mitomo and Kurosawa [18].

The fifth attack breaks the robustness in a novel way. It requires corruption of some senders and the first mix-server. This attack breaks also Jakobsson and Juels [15].

This paper studies the security of SHA-256, SHA-384 and SHA-512 against collision attacks and provides some insight into the security properties of the basic building blocks of the structure. It is concluded that neither Chabaud and Joux’s attack, nor Dobbertin-style attacks apply. Differential and linear attacks also don’t apply on the underlying structure. However we show that slightly simplified versions of the hash functions are surprisingly weak : whenever symmetric constants and initialization values are used throughout the computations, and modular additions are replaced by exclusive or operations, symmetric messages hash to symmetric digests. Therefore the complexity of collision search on these modified hash functions potentially becomes as low as one wishes.

In this paper, we show that the key scheduling algorithm of the recently proposed stream cipher Turing suffers from important flaws. These weaknesses allow an attacker that chooses the initialization vector (IV) to recover some partial information about the secret key. In particular, when using Turing with a 256-bit secret key and a 128-bit IV, we present an attack that requires the ability to choose 2³⁷ IV and then recovers the key with complexity 2⁷², requiring 2³⁶ bytes of memory.

A related-key differential cryptanalysis is applied to the 192-bit key variant of AES. Although any 4-round differential trail has at least 25 active bytes, one can construct 5-round related-key differential trail that has only 15 active bytes and break six rounds with 2¹⁰⁶ plaintext/ciphertext pairs and complexity 2¹¹². The attack can be improved using truncated differentials. In this case, the number of required plaintext/ciphertext pairs is 2⁸¹ and the complexity is about 2⁸⁶. Using impossible related-key differentials we can break seven rounds with 2¹¹¹ plaintext/ciphertext pairs and computational complexity 2¹¹⁶. The attack on eight rounds requires 2⁸⁸ plaintext/ciphertext pairs and its complexity is about 2¹⁸³ encryptions. In the case of differential cryptanalysis, if the iterated cipher is Markov cipher and the round keys are independent, then the sequence of differences at each round output forms a Markov chain and the cipher becomes resistant to differential cryptanalysis after sufficiently many rounds, but this is not true in the case of related-key differentials. It can be shown that if in addition the Markov cipher has K-f round function and the hypothesis of stochastic equivalence for related keys holds, then the iterated cipher is resistant to related-key differential attacks after sufficiently many rounds.

SNOW 2.0 was developed by Johansson and Ekdahl in 2002, as a modified version of SNOW 1.0. In this paper we present the application of linear (masking) attack to SNOW 2.0 stream cipher. Our attack requires 2²²⁵ output words (2²³⁰ bits) and 2²²⁵ steps of analysis to distinguish the output of SNOW 2.0 from a truly random bit sequence.

We show that the pairwise independence of the APA construction is related to the impossible differentials properties. We notice that inversion has many impossible differentials, so x -> 1/(x+a)+b is not pairwise independent.

In 1998, Vaudenay proposed the random harmonic permutation h:x -> a/(x-b)+c. Although it is not perfectly 3-wise independent (despite what was originally claimed), we demonstrate in this paper that it is almost 3-wise independent. In particular we show that any distinguisher limited to three queries between this permutation and a perfect one has an advantage limited to 3/q where q is the field order. This holds even if the distinguisher has access to h ^− 1.

Finally, we investigate 4-wise independence and we suggest the cross-ratio as a new tool for cryptanalysis of designs involving inversion.

A T-function is a mapping in which the i-th bit of the output can depend only on bits 0,1,..., i of the input. All the bitwise machine operations and most of the numeric machine operations in modern processors are T-functions, and their compositions are also T-functions. In this paper we show that T-functions can be used to construct exceptionally efficient cryptographic building blocks which can be used as nonlinear maximal length state transition functions in stream ciphers, as large S-boxes in block ciphers, and as non-algebraic multipermutations in hash functions.

The edit distance correlation attack on the well-known alternating step generator for stream cipher applications was proposed by Golić and Menicocci. The attack can be successful only if the probability of the zero edit distance, the so-called embedding probability, conditioned on a given segment of the output sequence, decreases with the segment length, and if the decrease is exponential, then the required segment length is linear in the total length of the two linear feedback shift registers involved. The exponential decrease for the maximal value of the embedding probability as a function of the given output segment was estimated experimentally by Golić and Menicocci. In this paper, by using the connection with the interleaving and decimation operations, the embedding probability is theoretically analyzed. Tight exponentially small upper bounds on the maximal embedding probability are thus derived. Sharp exponentially small lower and upper bounds on the minimal embedding probability are also determined.

Vectorial functions (i.e. mappings from F ₂ ⁿ into F ₂ ^m , also called S-boxes) can be used in pseudo-random generators with multiple outputs. The notion of maximum correlation of these S-boxes to linear functions, introduced by Zhang and Chan, plays a central role in the resistance of the resulting stream ciphers to correlation attacks. It can be related to a notion of “unrestricted nonlinearity”. We obtain a new lower bound on the overall maximum correlation to linear functions of vectorial functions which results in an upper bound on the unrestricted nonlinearity. We compare it with the known upper bounds on the nonlinearity (which are also valid for the unrestricted nonlinearity of balanced functions). We study its tightness and we exhibit a class of balanced functions whose nonlinearity and unrestricted nonlinearity are high relatively to the upper-bounds.

It is known that every positive integer n can be represented as a finite sum of the form n = sum(a _i 2 ⁱ ), where a _i in {0,1,-1} for all i, and no two consecutive a _i ’s are non-zero. Such sums are called nonadjacent representations. Nonadjacent representations are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications.

In this paper, we investigate if other digit sets of the form {0,1,x}, where x is an integer, provide each positive integer with a nonadjacent representation. If a digit set has this property we call it a nonadjacent digit set (NADS). We present an algorithm to determine if {0,1,x} is a NADS; and if it is, we present an algorithm to efficiently determine the nonadjacent representation of any positive integer. We also present some necessary and sufficient conditions for {0,1,x} to be a NADS. These conditions are used to exhibit infinite families of integers x such that {0,1,x} is a NADS, as well as infinite families of x such that {0,1,x} is not a NADS.

In the past years several authors have considered finite fields extensions of odd characteristic optimised for a given architecture to obtain performance gains. The considered fields were however very specific.

We define a Processor Adequate Finite Field (PAFF) as a field of odd characteristic p<2 ^w where w is a CPU related word length. PAFFs have several attractive properties for cryptography. In this paper we concentrate on arithmetic aspects. We present some algorithms usually providing better performance in PAFFs than in prime fields and in previously proposed instances of extension fields of comparable size.

In 1999, Jerome Solinas introduced families of moduli called the generalized Mersenne numbers. The generalized Mersenne numbers are expressed in a polynomial form, p = f(t), where t is a power of 2. It is shown that such p’s lead to fast modular reduction methods which use only a few integer additions and subtractions. We further generalize this idea by allowing any integer for t. We show that more generalized Mersenne numbers still lead to a significant improvement over well-known modular multiplication techniques. While each generalized Mersenne number requires a dedicated implementation, more generalized Mersenne numbers allow flexible implementations that work for more than one modulus. We also show that it is possible to perform long integer modular arithmetic without using multiple precision operations when t is chosen properly. Moreover, based on our results, we propose efficient arithmetic methods for XTR cryptosystem.

We show that any scheme to encrypt m blocks of size n bits each, which assures message integrity, is linear in (GF2) ⁿ , uses m+k invocations of random functions (from n bits to n bits) and vn bits of randomness, must have k+v at least Ω(logm). This lower bound is proved in a very general model which rules out many promising linear modes of operations for encryption with message integrity. This lower bound is tight as in an earlier paper “Encryption Models with Almost Free Message Integrity”, Proc. Eurocrypt 2001, we show a linear scheme to encrypt m blocks while assuring message integrity by using only m+2+logm invocations of random permutations.