In implementing cryptographic algorithms on limited devices such as smart cards, speed and memory requirements had always presented a challenge. With the advent of side channel attacks, this task became even more difficult because a programmer must take into account countermeasures against such attacks, which often increases computational time, or memory requirements, or both. In this paper we describe a new method for secure implementation of the Advanced Encryption Standard algorithm. The method is based on a data masking technique, which is the most widely used countermeasure against power analysis and timing attacks at a software level. The change of element representation allows us to replace all multiplications in the field with table lookups using masked log/alog tables, and achieve an efficient solution that combines low memory requirements with high speed and resistance to attacks.

We show how to attack an FPGA implementation of AES where all bytes are processed in parallel using differential electromagnetic analysis. We first focus on exploiting local side channels to isolate the behaviour of our targeted byte. Then, generalizing the Square attack, we describe a new way of retrieving information, mixing algebraic properties and physical observations.

In this paper, two different normal basis multiplication algorithms for software implementation are proposed over GF(2n). The first algorithm is suitable for high complexity normal bases and the second algorithm is fast for type-I optimal normal bases and low complexity normal bases. The ANSI C source program is also included in this paper.

This document discusses masking approaches with a special focus on the AES S-box. Firstly, we discuss previously presented masking schemes with respect to their security and implementation. We conclude that algorithmic countermeasures to secure the AES algorithm against side-channel attacks have not been resistant against all first-order side-channel attacks. Secondly, we introduce a new masking countermeasure which is not only secure against first-order side-channel attacks, but which also leads to relatively small implementations compared to other masking schemes when implemented in dedicated hardware.

Golle et al introduced universal re-encryption, defining it as re- encryption by a player who does not know the key used for the original encryption, but which still allows an intended player to recover the plaintext. Universal re-encryption is potentially useful as part of many information-hiding techniques, as it allows any player to make ciphertext unidentifiable without knowing the key used. Golle et al’s techniques for universal re-encryption are reviewed, and improved constructions for both simple and hybrid universal re-encryption systems are presented, including a hybrid construction that permits indefinite re-encryptions with better efficiency and an almost-optimally small increase in file size. Some implementational issues and possible future directions are also discussed.

GNFS (general number field sieve) algorithm is currently the fastest known algorithm for factoring large integers. Up to the present, several running time estimates for GNFS are announced. These estimates are usually based on the previous factoring results. However, since the previous factoring results were done by various programs and/or computers, it is difficult to compare those running time. We implemented GNFS and factored 100- to 150-digits number on the same environment. This manuscript describes the statistics of these factorings.

In this paper we introduce a new way to represent elements of a finite field of characteristic $2$. We describe a new type of polynomial basis, called {\it redundant trinomial basis} and discuss how to implement it efficiently. Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$ when no irreducible trinomial of degree $n$ exists. Tests with {\tt NTL} show that improvements for squaring and exponentiation are respectively up to $45$\% and $25$\%. More attention is given to relevant extension degrees for doing elliptic and hyperelliptic curve cryptography. For this range, a scalar multiplication can be speeded up by a factor up to $15$\%.

We present algorithms for computing the {\it squared} Weil and Tate pairings on an elliptic curve and the {\it squared} Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30\% over the usual pairings.

This paper describes the synthesis of Dynamic Differential Logic to increase the resistance of FPGA implementations against Differential Power Analysis. The synthesis procedure is developed and a detailed description is given of how EDA tools should be used appropriately to implement a secure digital design flow. Compared with an existing technique to implement Dynamic Differential Logic on FPGA, the technique saves a factor 2 in slice utilization. Experimental results also indicate that a secure version of the AES encryption algorithm can now be implemented with a mere 50% increase in time delay and 90% increase in slice utilization when compared with a normal non-secure single ended implementation.

Charge Recycling Sense Amplifier Based Logic is presented. This logic is derived from Sense Amplifier Based Logic, which is a logic style with signal independent power consumption that is capable to protect security devices such as Smart Cards against power attacks. Experimental results show that utilization of advanced circuit techniques save 20% in power consumption and 63% in peak supply current and that the logic style preserves the energy masking behavior.

We present a dynamic and differential CMOS logic style, which has a signal independent switching behavior. It is shown that during each clock cycle, power consumption and all circuit characteristics, such as leakage current, instantaneous current and input-output delay are identical and independent of the logic value and the sequence of the input data. Implementing the encryption module in this logic will protect it against any Side Channel Attack that takes advantage of power, timing and leakage information. We have built a set of logic gates and a flip-flop needed for cryptographic functions and implemented a larger module, for which area, total power consumption and variation on the power consumption have been compared with implementations in Static Complementary CMOS logic, genuine Dynamic and Differential Logic and Current Mode Logic.

Pairing-based cryptosystems rely on bilinear non-degenerate maps called pairings, such as the Tate and Weil pairings defined over certain elliptic curve groups. In this paper we show how to compress pairing values, how to couple this technique with that of point compression, and how to benefit from the compressed representation to speed up exponentiations involving pairing values, as required in many pairing based protocols.

Hardware accelerators are often used in cryptographic applications for speeding up the highly arithmetic-intensive public-key primitives, e.g. in high-end smart cards. One of these emerging and very promising public-key scheme is based on HyperElliptic Curve Cryptosystems (HECC). In the open literature only a few considerations deal with hardware implementation issues of HECC. Our contribution appears to be the first one to propose architectures for the latest findings in efficient group arithmetic on HEC. The group operation of HECC allows parallelization at different levels: bit-level parallelization (via different digit-sizes in multipliers) and arithmetic operation-level parallelization (via replicated multipliers). We investigate the trade-offs between both parallelization options and identify speed and time-area optimized configurations. We found that a coprocessor using a single multiplier (D = 8) instead of two or more is best suited. This coprocessor is able to compute group addition and doubling in 479 and 334 clock cycles, respectively. Providing more resources it is possible to achieve 288 and 248 clock cycles, respectively.

To ensure the security of software executing on malicious hosts, as in digital rights management (DRM) applications, it is desirable to encrypt or decrypt content using white-box encoded cryptographic algorithms in the manner of Chow et al. Such encoded algorithms must run on an adversary’s machine without revealing the private key information used, despite the adversary’s ability to observe and manipulate the running algorithm. We have implemented obfuscated (white-box) DES and 3DES algorithms along the lines of Chow et al., with alterations that improve the security of the key, eliminating attacks that extract the key from Chow et al.’s obfuscated DES. Our system is secure against two previously published attacks on Chow et al.’s system, as well as a new adaptation of a statistical bucketing attack on their system. During implementation of white-box DES we found that a number of optimizations were needed for practical generation and execution. On a typical laptop we can generate obfuscated DES functions in a Lisp environment in under a minute allocating 11 MB, including the space required for the resulting function. The resulting function occupies 4.5 MB and encrypts or decrypts each block in approximately 30 ms on an 800 MHz G4 processor; slight run-time performance of the obfuscated DES could be traded to further reduce our algorithm’s representation to 2.3 MB. Although it is over an order of magnitude slower than typical DES systems, we believe it is fast enough for application to some DRM problems.

In many crypographic hardware or software packages, a considerable part is devoted to finite field arithmetic. The finite field arithmetic is a very costly operation in comparison to other finite field operations. Taming the complexity of this operation has been a major challenge for researchers and implementers. One approach for the purpose is accumulate all the elements to be inverted and to compute several inversions simultaneously at the cost of one inversion and some multiplictions. One such algorithm is known as Montgomery's trick. However Montgomery's trick does not allow much parallelism. In~\cite{SMB03} an algorithm for computation of inverses of several field elements simultaneously in parallel has been proposed. The algorithm allows ample scope for parallelism and performes well if there is no restriction on the number of processors used. In the current work, we present an algorithm, which is same in complexity as Montgomery's trick but suitable for a parallel implementation. In parallel implementation, it computes inverse of $n$ elements in $2\log n$ parallel rounds. It performs better than both the previous algorithms under the circumstances where the restricted number of multipliers is used.

Alghoritms: HIEROCRYPT-3, CAMELLIA and ANUBIS, GRAND CRU, NOEKEON, NUSH, Q, RC6, SAFER++128, SC2000, SHACAL were requested for the submission of block ciphers (high level block cipher) to NESSIE (New European Schemes for Signatures, Integrity, and Encryption) project. The main purpose of this project was to put forward a portfolio of strong cryptographic primitives of various types. The NESSIE project was a three year long project and has been divided into two phases. The first was finished in June 2001r. CAMELLIA, RC6, SAFER++128 and SHACAL were accepted for the second phase of the evaluation process. HIEROCRYPT-3 had key schedule problems, and there were attacks for up to 3,5 rounds out of 6, at least hardware implementations of this cipher were extremely slow. HIEROCRYPT-3 was not selected to Phase II. CAMELLIA was selected as an algorithm suggested for future standard. In the paper we present the hardware implementations these two algorithms with 128-bit blocks and 128-bit keys, using ALTERA devices and their comparisons.

This paper presents an implementation of genus 2 and 3 hyperelliptic curves over prime fields, with a comparison with elliptic curves. To allow a fair comparison, we developed an ad-hoc arithmetic library, designed to remove most of the overheads that penalise implementations of curve-based cryptography over prime fields. These overheads get worse for smaller fields, and thus for large genera. We also use techniques such as lazy and incomplete modular reduction, originally developed for performing arithmetic in field extensions, to reduce the number of modular reductions occurring in the formulae for the group operations. The result is that the performance of hyperelliptic curves of genus 2 over prime fields is much closer to the performance of elliptic curves than previously thought. For groups of 192 and 256 bits the difference is about 18% and 15% respectively.

The optimization of the Harley algorithm is an active area of hyperelliptic curve cryptography. We propose an efficient method for software implementation of genus three Harley algorithm over GF(2^n). Our method is based on fast finite field multiplication using one SIMD operation, SSE2 on Pentium 4, and parallelized Harley algorithm. We demonstrated that software implementation using proposed method is about 11% faster than conventional implementation.

This paper introduces simple methods to convert a cryptographic algorithm into an algorithm protected against simple side-channel attacks. Contrary to previously known solutions, the proposed techniques are not at the expense of the execution time. Moreover, they are generic and apply to virtually any algorithm. In particular, we present several novel exponentiation algorithms, namely a protected square-and-multiply algorithm, its right-to-left counterpart, and several protected sliding-window algorithms. We also illustrate our methodology applied to point multiplication on elliptic curves. All these algorithms share the common feature that the complexity is globally unchanged compared to the corresponding unprotected implementations.

Low power consumption, low gate count and high throughput used to be standard design criteria for cryptographic coprocessors designated for smart cards and related embedded devices. Not anymore. With the advent of side channel attacks, the first and foremost concern is device resistance to such attacks. This paper describes how to to embed data masking technique at a hardware level for an AES coprocessor. We concentrate on inversion in the field since it is the only non-linear operation that was assumed to require complex transformations on masked data and on masks. Our paper demonstares that it is possible to compute inverses directly on masked data, without ever revealing unmasked intermediate results in the process. Our approach consists in transition to composite fields, where inversion can be efficiently implemented in combinational logic using only bitwise XOR and AND operations. A breakthrough idea is to replace these operations on masked data by simple combinational circuits operating on bits of masked data and on bits of a mask in such a manner that a proper "mask correction" is computed on-the fly. Combining these elementary building blocks, we obtain a complete hardware solution for a "masked AES", thus effectively resolving the problem of a secure AES co-processor.

This paper presents a new attack on keyboards. \smallskip The attack consists in depositing on each keyboard key a small ionic salt quantity ({\sl e.g.} some NaCl on key 0, some KCl on key 1, LiCl on key 2, SrCl$_2$ on key 3, BaCl$_2$ on key 4, CaCl$_2$ on key 5...). As the user enters his PIN, salts get mixed and leave the keyboard in a state that leaks secret information. Nicely enough, evaluating the entropy loss due to the chemical trace turns out to be a very interesting combinatorial exercise. \smallskip Under the assumption that mass spectroscopic analysis can reveal with accuracy the mixture of chemical compounds generated by the user, we show that, for moderate-size decimal PINs, the attack would generally disclose the PIN. \smallskip The attack may apply to door PIN codes, phone numbers dialed from a hotel rooms, computer keyboards or even ATMs. \ss While we did not implement the chemical part of the attack, a number of mass spectrometry specialists confirmed to the authors its feasibility.

We present a cryptographic architecture optimization technique called divide-and-concatenate based on two observations: (i) the area of a multiplier and associated data path decreases exponentially and their speeds increase linearly as their operand size is reduced. (ii) in hash functions, message authentication codes and related cryptographic algorithms, two functions are equivalent if they have the same collision probability property. In the proposed approach we divide a 2w-bit data path (with collision probability 2-2w) into two w-bit data paths (each with collision probability 2-w) and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2-2w). We applied this technique on NH hash, a universal hash function that uses multiplications and additions. When compared to the 100% overhead associated with duplicating a straightforward 32-bit pipelined NH hash data path, the divide-and-concatenate approach yields a 94% increase in throughput with only 40% hardware overhead. The NH hash associated message authentication code UMAC architecture with collision probability 2-32 that uses four equivalent 8-bit divide-and-concatenate NH hash data paths yields a throughput of 79.2 Gbps with only 3840 FPGA slices when implemented on a Xilinx XC2VP7-7 Field Programmable Gate Array (FPGA).

Nowadays, there exists a manifold variety of cryptographic applications: from low level embedded crypto implementations up to high end cryptographic engines for servers. The latter require a flexible implementation of a variety of cryptographic primitives in order to be capable of communicating with several clients. On the other hand, on the client it only requires an implementation of one specific algorithm with fixed parameters such as a fixed field size or fixed curve parameters if using ECC/ HECC. In particular for embedded environments like PDAs or mobile communication devices, fixing these parameters can be crucial regarding speed and power consumption. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem of genus two, well suited for these constraint devices. In recent years, a lot of effort was made to speed up arithmetic on genus-2 HEC. This work is based on the work of Lange and presents a major improvement of HECC arithmetic for curves defined over fields of characteristic two. We optimized the group doubling operation for certain types of genus-2 curves and we were able to reduce the number of required multiplications to a total of 9 multiplications. The saving in multiplications is 47% for the cost of one additional squaring. Thus, the efficiency of the whole cryptosystem was drastically increased.

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of arithmetic using affine coordinates.

A number $p$ is a safe prime if both $p$ and $(p-1)/2$ are prime. This note describes a method of generating safe primes that is considerably faster than repeatedly generating random primes $q$ until $p=2q+1$ is also prime.

Safe primes are prime numbers of the form $p=2\/q+1$ where $q$ is prime. This note introduces a simple method for doubling the speed of safe prime generation. The method is particularly suited to settings where a large number of RSA moduli must be generated.

A method for elliptic curve point multiplication is proposed with complex multiplication by Sqrt[-2] or by (1+Sqrt[-7])/2 instead of point duplication, speeding up multiplication about 1.34 times. Higher radix makes it possible to use one point duplication instead of two and to speed up computation about 1.6 times. We employ prime group order factorization in corresponding quadratic order and integer exponent reduction modulo quadratic prime in the Euclidean imaginary quadratic ring.

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.

A hardware random number generator was described at CHES 2002 by T. Tkacik. In this paper, we analyze its method of generating randomness and, as a consequence of the analysis, we describe how, in principle, an attack on the generator can be executed.

Elliptic curve cryptosystems in the presence of faults were studied by Biehl, Meyer and Mueller (2000). The first fault model they consider requires that the input point P in the computation of dP is chosen by the adversary. Their second and third fault models only require the knowledge of P. But these two latter models are less `practical' in the sense that they assume that only a few bits of error are inserted (typically exactly one bit is supposed to be disturbed) either into P just prior to the point multiplication or during the course of the computation in a chosen location. This report relaxes these assumptions and shows how random (and thus unknown) errors in either coordinates of point P, in the elliptic curve parameters or in the field representation enable the (partial) recovery of multiplier d. Then, from multiple point multiplications, we explain how this can be turned into a total key recovery. Simple precautions to prevent the leakage of secrets are also discussed.

A way for preventing SPA-like attacks on elliptic curve systems is to use the same formula for the doubling and the general addition of points on the curve. Various proposals have been made in this direction with different results. This paper re-investigates the Jacobi form suggested by Liardet and Smart (CHES 2001). Rather than considering the Jacobi form as the intersection of two quadrics, the addition law is directly derived from the underlying quartic. As a result, this leads to substantial memory savings and produces the fastest unified addition formula for curves of order a multiple of 2.

We describe fast new algorithms to implement recent cryptosystems based on the Tate pairing. In particular, our techniques improve pairing evaluation speed by a factor of about 55 compared to previously known methods in characteristic 3, and attain performance comparable to that of RSA in larger characteristics. We also propose faster algorithms for scalar multiplication in characteristic 3 and square root extraction over $\GF{p^m}$, the latter technique being also useful in contexts other than that of pairing-based cryptography.

We present an algorithm that speeds exponentiation on a general elliptic curve by an estimated 3.8% to 8.5% over the best known general exponentiation methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give applications to simultaneous multiple exponentiation and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8%.

This article describes concrete results and practically approved countermeasures concerning differential fault attacks on RSA using the CRT. It especially investigates smartcards with a RSA coprocessor where any hardware countermeasure to defeat such fault attacks have been switched off. This scenario has been chosen in order to completely analyze the resulting effects and errors occurring inside the hardware. Using the results of this kind of physical stress attack enables the development of completely reliable software countermeasures. Although {\em successful\/} RSA attacks on the investigated hardware have been only possible with an expensive enhanced laboratory equipment, the effects on the unprotected hardware have been tremendously. This caused lots of analysis efforts to investigate what really happened during the attack. Indeed, this will be addressed in this paper. We first report on the nature of the resulting errors within the hardware due to the physical stress applied to the smartcard. Hereafter, we describe the experiments and results with a very efficient and prominent software RSA-CRT DFA countermeasure. This method could be shown to be insufficient, i.e., detected nearly no error, when we introduced stress at the right position during the computation. Naturally, a detailed error analysis model followed, specifying every failure point during the RSA-CRT operation. This model finally allowed to develop and present here new very practically oriented software countermeasures hedging the observed and characterized fault attacks. Eventually, we present the security analysis of our new developed software RSA-CRT DFA countermeasures. Thanks to their careful specification according to the observed and analyzed errors they resisted all kinds of physical stress attacks and were able to detect any subtle computation error, thus avoiding to break the smartcard by fault attacks. Nevertheless, we stress, that although our software countermeasures have been fully approved by practical experiments, we are convinced that only sophisticated hardware countermeasures like sensors and filters in combination with software countermeasures will be able to provide a secure and comfortable base to defeat in general any conceivable fault attacks scenario on smartcards properly.

For speeding up elliptic curve scalar multiplication and making it secure against side-channel attacks such as timing or power analysis, various methods have been proposed using specifically chosen elliptic curves. We show that both goals can be achieved simultaneously even for conventional elliptic curves over $\mathbb{F}_p$. This result is shown via two facts. First, we recall the known fact that every elliptic curve over $\mathbb{F}_p$ admits a scalar multiplication via a (Montgomery ladder) Lucas chain. As such chains are known to be resistant against timing- and simple power/electromagnetic radiation analysis attacks, the security of our scalar multiplication against timing and simple power/electromagnetic radiation analysis follows. Second, we show how to parallelize the 19 multiplications within the resulting \lq\lq double" and \lq\lq add" formulas of the Lucas chain for the scalar multiplication. This parallelism together with the Lucas chain results in 10 parallel field multiplications per bit of the scalar. Finally, we also report on a concrete successful implementation of the above mentioned scalar multiplication algorithm on a very recently developed and commercially available coprocessor for smart cards.

Some attacks on cryptographic systems exploit the leakage of information through so-called ``side channels'', such as power consumption or time employed by a computation. For cryptosystems involving an exponentiation, a few possible countermeasures are suggested. In the case of elliptic curves over a binary finite field, we show how to split point addition into two blocks which, through the addition of a little overhead, can be made undistinguishable from a point doubling. This allows the whole exponentiation process to be performed as a sequence of homogeneous steps. To add some randomization to the exponentiation process in the ECC case, we suggest the use of points of small order, computed on the fly. This presents some disadvantages over known methods, but allows to avoid the storage of points in non-volatile RAM. A multiplicative variation of ``additive exponent blinding'' is suggested. This involves a two-phase exponentiation and is valid both for discrete log and RSA settings. Computer experiments implementing some of these ideas are described and analyzed.

In this paper, we report preliminary results obtained as a result of a systematic investigation of leakage of compromising information via EM emanations from chipcards and other devices. Our findings show that the EM side--channel is more powerful than other side--channels such as timing and power analysis. Specifically, in some cases, one can obtain much more compromising information about computations and one can use this information to defeat the protection provided by countermeasures to the other side--channel attacks.

This paper describes various techniques to reduce the number of logic gates needed to implement the DES S-boxes in bitslice software. Using standard logic gates, an average of 56 gates per S-box was achieved, while an average of 51 was produced when non-standard gates were utilized. This is an improvement over the previous best result, which used an average of 61 non-standard gates.

This document describes the Advanced Cryptographic Engine (ACE). It specifies a public key encryption scheme as well as a digital signature scheme with enough detail to ensure interoperability between different implementations. These schemes are almost as efficient as commercially used schemes, yet unlike such schemes, can be proven secure under reasonable and well-defined intractability assumptions. A concrete security analysis of both schemes is presented.