Theoretically secure cryptosystems, digital signatures may not be secure after being implemented on Internet of Things (IoT) devices and PCs because of side-channel attacks (SCA). Because RSA key generation and ECDSA require GCD computations or modular inversions, which are often computed using the binary Euclidean algorithm (BEA) or binary extended Euclidean algorithm (BEEA), the SCA weaknesses of BEA and BEEA become a serious concern. Constant-time GCD (CT-GCD) and constant-time modular inversion (CTMI) algorithms are effective countermeasures in such situations. Modular inversion based on Fermat's little theorem (FLT) can work in constant time, but it is not efficient for general inputs. Two CTMI algorithms, named BOS and BY in this paper, were proposed by Bos, Bernstein and Yang, respectively. Their algorithms are all based on the concept of BEA. However, one iteration of BOS has complicated computations, and BY requires more iterations. A small number of iterations and simple computations during one iteration are good characteristics of a constant-time algorithm. Based on this view, this study proposes new short-iteration CT-GCD and CTMI algorithms over Fp borrowing a simple concept from BEA. Our algorithms are evaluated from a theoretical perspective. Compared with BOS, BY, and the improved version of BY, our short-iteration algorithms are experimentally demonstrated to be faster.

We have proposed a generic architecture that can integrate the aspects of confidentiality and integrity into the A/D conversion framework. A conceptual account of the development of the proposed architecture is presented. Using the principle of this architecture we have presented a CMOS circuit design to facilitate a fully integrated Authenticated-Encrypted ADC (AE-ADC). We have implemented and demonstrated a partial 8-bit ADC Analog Front End of this proposed circuit in 0.18µm CMOS with an ENOB of 7.64 bits.

This paper presents a power analysis that applies to elliptic curves over generalized Mersenne prime field Fp. This prime field enables efficient modular reductions which influence the computational performance of an elliptic curve cryptosystem. The general modular reductions stochastically calculate extra operations. Some studies showed the possibility of power analysis attacks to scalar multiplication with a unified code by using the statistical information of extra operations. In this paper, we present the statistical experiment and possibility of attacks, and propose the more sensitive attack and the countermeasure without performance impact.

Scan-based side channel attack on hardware implementations of cryptographic algorithms has shown its great security threat. Unlike existing scan-based attacks, in our work we observed that instead of the secret-related-registers, some non-secret registers also carry the potential of being misused to help a hacker to retrieve secret keys. In this paper, we first present a scan-based side channel attack method on AES by making use of the round counter registers, which are not paid attention to in previous works, to show the potential security threat in designs with scan chains. And then we discussed the issues of secure DFT requirements and proposed a secure scan scheme to preserve all the advantages and simplicities of traditional scan test, while significantly improve the security with ignorable design overhead, for crypto hardware implementations.

In this paper, we present a fault analysis of the original NTRU public key cryptosystem. The fault model in which we analyze the cipher is the one in which the attacker is assumed to be able to fault a small number of coefficients of the polynomial input to (or output from) the second step of the decryption process but cannot control the exact location of injected faults. For this specific original instantiation of the NTRU encryption system with parameters (N,p,q), our attack succeeds with probability≈ and when the number of faulted coefficients is upper bounded by t, it requires O((pN)t) polynomial inversions in Z/p Z[x]/(xN-1).

This paper shows two power analysis attacks against a software implementation of a first-order DPA resistant S-box algorithm that is based on the discrete Fourier Transform (DFT). The DPA resistant S-box algorithm based on DFT was proposed by Prouff et al. in 2006 and improved by Coron et al. in 2008, respectively. In our attacks against the improved one, we pre-process the power traces by separating them into two subgroups, so that each has a biased mask. For the separated power traces, two post analysis methods are proposed to identify the key. One is based on DPA attack against one subgroup, and the other utilizes the difference of means for two subgroups and a pattern matching. Finally, we compare these two attack methods and propose an algorithm-level countermeasure to enhance the security of S-box calculation based on the DFT.

Correlation power analysis (CPA) is a well-known attack against cryptographic modules with which an attacker evaluates the correlation between the power consumption and the sensitive data candidates calculated from a guessed sub-key and known data such as plaintexts and ciphertexts. This paper enhances CPA to propose a new general power analysis, built-in determined sub-key CPA (BS-CPA), which finds a new sub-key by using the previously determined sub-keys recursively to compute the sensitive data candidates and to increase the signal-to-noise ratio in its analysis. BS-CPA also reuses the power traces in the repetitions of finding sub-keys to decrease the total number of the required traces for determining the all sub-keys. BS-CPA is powerful and effective when the multiple sensitive data blocks such as sbox outputs are processed simultaneously as in the hardware implementation. We apply BS-CPA to the power traces provided at the DPA contest and succeed in finding a DES key using fewer traces than the original CPA does.

HMAC is one of the most famous keyed hash functions, and widely utilized. In order to design secure hash functions, we often use PGV construction consisting of 64 schemes, each of which utilizes a block cipher. If the underlying block cipher is ideal, 12 schemes are proven to be secure. In this paper, we evaluate the security of these schemes in view of side channel attacks. As it turns out, HMACs based on 11 out of 12 secure PGV schemes are vulnerable to side channel attacks, even if the underlying block cipher is secure against side channel attacks. These schemes are classified into two groups based on their vulnerabilities. For the first group which contains 8 schemes, we show that the attacker can reveal the whole key of HMAC, and selectively forge in consequence. For the other group which contains 3 schemes, we specify the importance of the execution sequence for the inner operations of the scheme, and refine it. If wrong orders of operations are used, the attacker can reveal a portion of the key of HMAC. Hence, the use of HMACs based on such PGV schemes as they are is not recommended when the resistance against side channel attacks is necessary.

We propose a new analysis technique against a class of countermeasure using randomized binary signed digit (BSD) representations. We also introduce some invariant properties between BSD representations. The proposed analysis technique can directly recover the secret key from power measurements without information for algorithm because of the invariant properties of BSD representation. Thus the proposed attack is applicable to all countermeasures using BSD representations. Finally, we give the simulation results against some countermeasures using BSD representation such as Ha-Moon method, Ebeid-Hasan method, and the method of Agagliate et al. The results show that the proposed attack is practical analysis method.

Koblitz curves belong to a special class of binary curves on which the scalar multiplication can be computed very efficiently. For this reason, they are suitable candidates for implementations on low-end processors. However, such devices are often vulnerable to side channel attacks. In this paper, we propose a new countermeasure against side channel attacks on Koblitz curves, which utilizes a fixed-pattern recoding to defeat simple power analysis. We show that in practical cases, the recoding can be performed from left to right, and can be easily stored or even randomly generated.

Elliptic curves offer interesting possibilities for alternative cryptosystems, especially in constrained environments like smartcards. However, cryptographic routines running on such lightweight devices can be attacked with the help of "side channel information"; power consumption, for instance. Elliptic curve cryptosystems are not an exception: if no precaution is taken, power traces can help attackers to reveal secret information stored in tamper-resistant devices. Okeya-Takagi scheme (OT scheme) is an efficient countermeasure against such attacks on elliptic curve cryptosystems, which has the unique feature to allow any size for the pre-computed table: depending on how much memory is available, users can flexibly change the table size to fit their needs. Since the nature of OT scheme is different from other side-channel attack countermeasures, it is necessary to deeply investigate its security. In this paper, we present a comprehensive security analysis of OT scheme, and show that based on information leaked by power consumption traces, attackers can slightly enhance standard attacks. Then, we explain how to prevent such information leakage with simple and efficient modifications.

The XTR public key cryptosystem was introduced in 2000. XTR is suitable for a variety of environments including low-end smart cards, and is regarded as an excellent alternative to RSA and ECC. Moreover, it is remarked that XTR single exponentiation (XTR-SE) is less susceptible than usual exponentiation routines to environmental attacks such as the timing attack and the differential power analysis (DPA). This paper investigates the security of side channel attack (SCA) on XTR. In this paper, we show the immunity of XTR-SE against the simple power analysis if the order of the computation of XTR-SE is carefully considered. In addition, we show that XTR-SE is vulnerable to the data-bit DPA, the address-bit DPA, the doubling attack, the modified refined power analysis, and the modified zero-value attack. Moreover, we propose some countermeasures against these attacks. We also show experimental results of the efficiency of the countermeasures. From our implementation results, if we compare XTR with ECC with countermeasures against "SCAs," we think XTR is as suitable to smart cards as ECC.

Side channel attacks (SCA) are serious attacks on mobile devices. In SCA, the attacker can observe the side channel information while the device performs the cryptographic operations, and he/she can detect the secret stored in the device using such side channel information. Ha-Moon proposed a novel countermeasure against side channel attacks in elliptic curve cryptosystems (ECC). The countermeasure is based on the signed scalar multiplication with randomized concept, and does not pay the penalty of speed. Ha-Moon proved that the countermeasure is secure against side channel attack theoretically, and confirmed its immunity experimentally. Thus Ha-Moon's countermeasure seems to be very attractive. In this paper we propose a novel attack against Ha-Moon's countermeasure, and show that the countermeasure is vulnerable to the proposed attack. The proposed attack utilizes a Markov chain for detecting the secret. The attacker determines the transitions in the Markov chain using side channel information, then detects the relation between consecutive two bits of the secret key, instead of bits of the secret key as they are. The use of such relations drastically reduces the search space for the secret key, and the attacker can easily reveal the secret. In fact, around twenty observations of execution of the countermeasure are sufficient to detect the secret in the case of the standard sizes of ECC. Therefore, the single use of Ha-Moon's countermeasure is not recommended for cryptographic use.

In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.

Differential power analysis (DPA) might break implementations of elliptic curve cryptosystem (ECC) on memory constraint devices. Goubin proposed a variant of DPA using a point (0,y), which is not randomized in Jacobian coordinates or in an isomorphic class. This point often exists in standardized elliptic curves, and we have to care this attack. In this paper, we propose zero-value register attack as an extension of Goubin's attack. Note that even if a point has no zero-value coordinate, auxiliary registers might take zero value. We investigate these zero-value registers that cannot be randomized by the above randomization. Indeed, we have found several points P = (x,y) which cause the zero-value registers, e.g., (1) 3x2 + a = 0,(2) 5x4 + 2ax2 - 4bx + a2 = 0,(3) P is y-coordinate self-collision point, etc. We demonstrate the elliptic curves recommended in SECG that have these points. Interestingly, some conditions required for zero-value register attack depend on explicit implementation of addition formulae -- in order to resist this type of attacks, we have to care how to implement the addition formulae. Finally, we note that Goubin's attack and the proposed attack assume that a base point P can be chosen by attackers and a secret scalar d is fixed, so that they are not applicable to ECDSA.

This paper proposes fast elliptic curve multiplication algorithms resistant against side channel attacks, based on the Montgomery-type scalar multiplication. The proposed scalar multiplications can be applied to all curves over prime fields, e.g., any standardized curves over finite fields with characteristic larger than 3. The method utilizes the addition formulas xECDBL and xECADD assembled by only x-coordinates of points, and is applicable for any types of curves over finite fields. Then, we encapsulate two addition formulas into one formula xECADDDBL, which accomplishes a faster computation because several auxiliary variables of two formulas can be shared. We also develop a novel addition chain for the new formula, with which we can compute scalar multiplications. The improvement of our scalar multiplications over previous Coron's dummy operation method is about 18% for a 160-bit scalar multiplication. Our method requires no table-up of precomputed points and it is suitable for the implementation on memory constraint computing architectures, e.g., smart cards. Moreover, we optimize the proposed algorithms for parallelized implementations with SIMD operations. Compared with the similar scheme proposed by Fischer et al., our scheme is about 16% faster.

SFLASH was chosen as one of the final selection of the NESSIE project in 2003. It is one of the most efficient digital signature scheme and is suitable for implementation on memory-constrained devices such as smartcards. Side channel attacks (SCA) are a serious threat to memory-constrained devices. If the implementation on them is careless, the secret key may be revealed. In this paper, we experimentally analyze the effectiveness of a side channel attack on SFLASH. There are two different secret keys for SFLASH, namely the proper secret key (s,t) and the random seed Δ used for the hash function SHA-1. Whereas many papers discussed the security of (s,t), little is known about that of Δ. Steinwandt et al. proposed a theoretical DPA for finding Δ by observing the XOR operations. We propose another DPA on Δ using the addition operation modulo 232, and present an experimental result of the DPA. After obtaining the secret key Δ, the underlying problem of SFLASH can be reduced to the C* problem broken by Patarin. From our simulation, about 1408 pairs of messages and signatures are needed to break SFLASH. Consequently, SHA-1 must be carefully implemented in order to resist SCA on SFLASH.

Isogeny for elliptic curve cryptosystems was initially used for efficient improvement of order counting methods. Recently, Smart proposed a countermeasure using isogeny for resisting a refined differential power analysis by Goubin (Goubin's attack). In this paper, we examine a countermeasure using isogeny against zero-value point (ZVP) attack that is generalization of Goubin's attack. We show that some curves require higher order of isogeny to prevent ZVP attack. Moreover, we prove that the class of curves that satisfies (-3/p) = 1 and whose order is odd cannot be mapped by isogeny to curves with a = -3 and secure against ZVP attack. We point out that three SECG curves are in this class. In the addition, we compare some efficient algorithms that are secure against both Goubin's attack and ZVP attack, and present the most efficient method of computing a scalar multiplication for each curve from SECG. Finally, we discuss another improvement for an efficient scalar multiplication, namely the usage of a point (0,y) for a base point of curve parameters. We are able to improve about 11% for double-and-add-always method, when the point (0,y) exists in an underlying curve or its isogeny.

The side channel attack (SCA) is a serious attack on wearable devices that have scarce computational resources. Cryptographic algorithms on them should be efficient using small memory--we have to make efforts to optimize the trade-off between efficiency and memory. In this paper we present efficient SCA-resistant scalar multiplications based on window method. Moller proposed an SPA-resistant window method based on 2w-ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive and it requires 2w points of table (or 2w-1 + 1 points if the signed 2w-ary is used). The most efficient window method with small memory is the width-w NAF, which requires 2w-2 points of table. In this paper we convert the width-w NAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. |00x|00x||00x|, where x is positive odd points < 2w. Thus the size of the table is 2w-1, which is optimal in the construction of the SPA-resistant chain based on width-w NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Moller's scheme for w = 2,3,4,5, which are relevant choices in the sense of efficiency for 160-bit ECC.

The Single Instruction, Multiple Data (SIMD) architecture enables computation in parallel on a single processor. The SIMD operations are implemented on some processors such as Pentium 3/4, Athlon, SPARC, or even on smart cards. This paper proposes efficient algorithms for assembling an elliptic curve addition (ECADD), doubling (ECDBL), and k-iterated ECDBL (k-ECDBL) with SIMD operations. We optimize the number of auxiliary variables and the order of basic field operations used for these addition formulas. If an addition chain has k-bit zero run, we can replace k-time ECDBLs to the proposed faster k-ECDBL and the total efficiency of the scalar multiplication can be improved. Using the singed binary chain, we can compute a scalar multiplication about 10% faster than the previously fastest algorithm proposed by Aoki et al. Combined with the sliding window method or the width-w NAF window method, we also achieve about 10% faster parallelized scalar multiplication algorithms with SIMD operations. For the implementation on smart cards, we establish two fast parallelized scalar multiplication algorithms with SIMD resistant against side channel attacks.