International Association for Cryptologic Research

International Association
for Cryptologic Research


Dong-Guk Han


Novel Side-Channel Attacks on Quasi-Cyclic Code-Based Cryptography 📺
Chou suggested a constant-time implementation for quasi-cyclic moderatedensity parity-check (QC-MDPC) code-based cryptography to mitigate timing attacks at CHES 2016. This countermeasure was later found to become vulnerable to a differential power analysis (DPA) in private syndrome computation, as described by Rossi et al. at CHES 2017. The proposed DPA, however, still could not completely recover accurate secret indices, requiring further solving linear equations to obtain entire secret information. In this paper, we propose a multiple-trace attack which enables to completely recover accurate secret indices. We further propose a singletrace attack which can even work when using ephemeral keys or applying Rossi et al.’s DPA countermeasures. Our experiments show that the BIKE and LEDAcrypt may become vulnerable to our proposed attacks. The experiments are conducted using power consumption traces measured from ChipWhisperer-Lite XMEGA (8-bit processor) and ChipWhisperer UFO STM32F3 (32-bit processor) target boards.
Side-Channel Attacks on Post-Quantum Signature Schemes based on Multivariate Quadratic Equations - Rainbow and UOV -
In this paper, we investigate the security of Rainbow and Unbalanced Oil-and-Vinegar (UOV) signature schemes based on multivariate quadratic equations, which is one of the most promising alternatives for post-quantum signature schemes, against side-channel attacks. We describe correlation power analysis (CPA) on the schemes that yield full secret key recoveries. First, we identify a secret leakage of secret affine maps S and T during matrix-vector products in signing when Rainbow is implemented with equivalent keys rather than random affine maps for optimal implementations. In this case, the simple structure of the equivalent keys leads to the retrieval of the entire secret affine map T. Next, we extend the full secret key recovery to the general case using random affine maps via a hybrid attack: after recovering S by performing CPA, we recover T by mounting algebraic key recovery attacks. We demonstrate how this leakage on Rainbow can be practically exploited on an 8-bit AVR microcontroller using CPA. Consequently, our CPA can be applied to Rainbow-like multi-layered schemes regardless of the use of the simple-structured equivalent keys and UOV-like single layer schemes with the implementations using the equivalent keys of the simple structure. This is the first result on the security of multivariate quadratic equations-based signature schemes using only CPA. Our result can be applied to Rainbow-like multi-layered schemes and UOV-like single layer schemes submitted to NIST for Post-Quantum Cryptography Standardization.
TinyECCK: Efficient Elliptic Curve Cryptography Implementation over $GF(2^m)$ on 8-bit MICAz Mote
In this paper, we revisit a generally accepted opinion: implementing Elliptic Curve Cryptosystem (ECC) over $GF(2^m)$ on sensor motes using small word size is not appropriate because XOR multiplication over $GF(2^m)$ is not efficiently supported by current low-powered microprocessors. Although there are some implementations over $GF(2^m)$ on sensor motes, their performances are not satisfactory enough to be used for wireless sensor networks (WSNs). We have found that a field multiplication over $GF(2^m)$ are involved in a number of redundant memory accesses and its inefficiency is originated from this problem. Moreover, the field reduction process also requires many redundant memory accesses. Therefore, we propose some techniques for reducing unnecessary memory accesses. With the proposed strategies, the running time of field multiplication and reduction over $GF(2^{163})$ can be decreased by 21.1\% and 24.7\%, respectively. These savings noticeably decrease execution times spent in Elliptic Curve Digital Signature Algorithm (ECDSA) operations (signing and verification) by around $15\% \sim 19\%$. We present TinyECCK (Tiny Elliptic Curve Cryptosystem with Koblitz curve -- a kind of TinyOS package supporting elliptic curve operations) which is the fastest ECC implementation over $GF(2^m)$ on 8-bit sensor motes using ATmega128L as far as we know. Through comparisons with existing software implementations of ECC built in C or hybrid of C and inline assembly on sensor motes, we show that TinyECCK outperforms them in terms of running time, code size and supporting services. Furthermore, we show that a field multiplication over $GF(2^m)$ can be faster than that over $GF(p)$ on 8-bit ATmega128L processor by comparing TinyECCK with TinyECC, a well-known ECC implementation over $GF(p)$. TinyECCK with sect163k1 can compute a scalar multiplication within 1.14 secs on a MICAz mote at the expense of 5,592-byte of ROM and 618-byte of RAM. Furthermore, it can also generate a signature and verify it in 1.37 and 2.32 secs with 13,748-byte of ROM and 1,004-byte of RAM.
Construction of efficient and secure Pairing Algorithm and its Application
Doo Ho Choi Dong-Guk Han Howon Kim
The randomized projective coordinate (RPC) method on pairing computing algorithm is a good solution which leads an efficient countermeasure against side channel attacks. In this paper, we investigate measures for the efficiency of the RPC based countermeasures of the pairing algorithm and construct a method that induce an efficient RPC based countermeasure against side channel attacks. As it application, we apply our construction method to the well-known $\eta_T$ pairing algorithm over binary fields and so we obtain an RPC based countermeasure of $\eta_T$ pairing which is more efficient than the RPC method on the original $\eta_T$ pairing algorithm.
Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields
Pairings on elliptic curves have been used as cryptographic primitives for the development of new applications such as identity based schemes. For the practical applications, it is crucial to provide efficient and secure implementations of the pairings. There have been several works on efficient implementations of the pairings. However, the research for secure implementations of the pairings has not been thoroughly investigated. In this paper, we investigate vulnerability of the pairing used in some pairing based protocols against side channel attacks. We propose an efficient algorithm secure against such side channel attacks of the eta pairing using randomized projective coordinate systems for the pairing computation.
Collision Attack on XTR and a Countermeasure with a Fixed Pattern
Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing systems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most efficient one is the Improved XTR Single Exponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most efficient one suitable for ubiquitous computer. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 2^{40} where the key size is 160-bit, which is 55% improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using a fixed pattern which is secure against SPA. We deploy a variant of Euclidean algorithm whose one of the registers is a monotone decreasing function with odd value. From our estimation of the efficiency of the proposed method, XTR exponentiation, computing Tr(g^n) with Tr(g) and n, takes 11.2log_2n multiplications in F_{p^2}. In the sense of both efficiency and security the proposed countermeasure is the best one among the previous countermeasures- it is about 30% faster.
Some Explicit Formulae of NAF and its Left-to-Right Analogue
Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run length appeared in FAN is asymptotically 16/7, which is longer than that of the standard NAF. We also apply the proposed formulae to the speed estimation of elliptic curve cryptosystems.
Some Analysis of Radix-r Representations
Dong-Guk Han Tsuyoshi Takagi
We deal with the radix-r representation used for the scalar multiplication of pairing-based cryptosystems with characteristic r. Our goal of this paper is to present some invariant properties about the signed radix-r representation; (1) approximation formulae for the average significant length and the average hamming weight of gNAF and wrNAF representation, (2) some classification formulae of equivalent classes called as Cutting Lemma, Collision Lemma, and Search Space Theorem. We also analyze the security of signed radix-r representations in the sense of side channel attacks, and to this end we propose a secure countermeasure.
On security of XTR public key cryptosystems against Side Channel Attacks
The XTR public key system was introduced at Crypto 2000. Application of XTR in cryptographic protocols leads to substantial savings both in communication and computational overhead without compromising security. It is regarded that XTR is suitable for a variety of environments, including low-end smart cards, and XTR is the excellent alternative to either RSA or ECC. In \cite{LV00a,SL01}, authors remarked that XTR single exponentiation (XTR-SE) is less susceptible than usual exponentiation routines to environmental attacks such as timing attacks and Differential Power Analysis (DPA). In this paper, however, we investigate the security of side channel attack (SCA) on XTR. This paper shows that XTR-SE is immune against simple power analysis (SPA) under assumption that the order of the computation of XTR-SE is carefully considered. However we show that XTR-SE is vulnerable to Data-bit DPA (DDPA)\cite{Cor99}, Address-bit DPA (ADPA)\cite{IIT02}, and doubling attack \cite{FV03}. Moreover, we propose two countermeasures that prevent from DDPA and a countermeasure against ADPA. One of the countermeasures using randomization of the base element proposed to defeat DDPA, i.e., randomization of the base element using field isomorphism, could be used to break doubling attack. Thus if we only deal with SPA, DDPA, ADPA, and doubling attack as the attack algorithm for XTR-SE, XTR-SE should be added following countermeasures: randomization of the base element using field isomorphism (DDPA and doubling attack) + randomized addressing (ADPA). But the proposed countermeasure against doubling attack is very inefficient. So to maintain the advantage of efficiency of XTR a good countermeasure against doubling attack is actually necessary.

Program Committees

Asiacrypt 2015
CHES 2014
CHES 2011