Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Implementation of a Leakage-Resilient ElGamal Key Encapsulation Mechanism Galindo, David ; Groszschädl, Johann ; Liu, Zhe et al in Journal of Cryptographic Engineering (2016), 6(3), 229-238 Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach ... [more ▼] Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis. [less ▲] Detailed reference viewed: 88 (2 UL)Provably Secure Countermeasures against Side-channel Attacks Vadnala, Praveen Kumar Doctoral thesis (2015) Side-channel attacks exploit the fact that the implementations of cryptographic algorithms leak information about the secret key. In power analysis attacks, the observable leakage is the power consumption ... [more ▼] Side-channel attacks exploit the fact that the implementations of cryptographic algorithms leak information about the secret key. In power analysis attacks, the observable leakage is the power consumption of the device, which is dependent on the processed data and the performed operations.\ignore{While Simple Power Analysis (SPA) attacks try to recover the secret value by directly interpreting the power measurements with the corresponding operations, Differential Power Analysis (DPA) attacks are more sophisticated and aim to recover the secret value by applying statistical techniques on multiple measurements from the same operation.} Masking is a widely used countermeasure to thwart the powerful Differential Power Analysis (DPA) attacks. It uses random variables called masks to reduce the correlation between the secret key and the obtained leakage. The advantage with masking countermeasure is that one can formally prove its security under reasonable assumptions on the device leakage model. This thesis proposes several new masking schemes along with the analysis and improvement of few existing masking schemes. The first part of the thesis addresses the problem of converting between Boolean and arithmetic masking. To protect a cryptographic algorithm which contains a mixture of Boolean and arithmetic operations, one uses both Boolean and arithmetic masking. Consequently, these masks need to be converted between the two forms based on the sequence of operations. The existing conversion schemes are secure against first-order DPA attacks only. This thesis proposes first solution to switch between Boolean and arithmetic masking that is secure against attacks of any order. Secondly, new solutions are proposed for first-order secure conversion with logarithmic complexity (${\cal O}(\log k)$ for $k$-bit operands) compared to the existing solutions with linear complexity (${\cal O}(k)$). It is shown that this new technique also improves the complexity of the higher-order conversion algorithms from ${\cal O}(n^2 k)$ to ${\cal O}(n^2 \log k)$ secure against attacks of order $d$, where $n = 2d+1$. Thirdly, for the special case of second-order masking, the running times of the algorithms are further improved by employing lookup tables. The second part of the thesis analyzes the security of two existing Boolean masking schemes. Firstly, it is shown that a higher-order masking scheme claimed to be secure against attacks of order $d$ can be broken with an attack of order $d/2+1$. An improved scheme is proposed to fix the flaw. Secondly, a new issue concerning the problem of converting the security proofs from one leakage model to another is examined. It is shown that a second-order masking scheme secure in the Hamming weight model can be broken with a first-order attack on a device leaking in the Hamming distance model. This result underlines the importance of re-evaluating the security proofs for devices leaking in different models. [less ▲] Detailed reference viewed: 194 (17 UL)Faster Mask Conversion with Lookup Tables Vadnala, Praveen Kumar ; Groszschädl, Johann in Mangard, Stefan; Poschmann, Axel Y. (Eds.) Constructive Side-Channel Analysis and Secure Design, 6th International Workshop, COSADE 2015, Berlin, Germany, April 13-14, 2015. Revised Selected Papers (2015, April) Masking is an effective and widely-used countermeasure to thwart Differential Power Analysis (DPA) attacks on symmetric cryptosystems. When a symmetric cipher involves a combination of Boolean and ... [more ▼] Masking is an effective and widely-used countermeasure to thwart Differential Power Analysis (DPA) attacks on symmetric cryptosystems. When a symmetric cipher involves a combination of Boolean and arithmetic operations, it is necessary to convert the masks from one form to the other. There exist algorithms for mask conversion that are secure against first-order attacks, but they can not be generalized to higher orders. At CHES 2014, Coron, Großschädl and Vadnala (CGV) introduced a secure conversion scheme between Boolean and arithmetic masking of any order, but their approach requires d=2t+1 shares to protect against attacks of order t. In the present paper, we improve the algorithms for second-order conversion with the help of lookup tables so that only three shares instead of five are needed, which is the minimal number for second-order resistance. Furthermore, we also improve the first-order secure addition method proposed by Karroumi, Richard and Joye, again with lookup tables. We prove the security of all presented algorithms using well established assumptions and models. Finally, we provide experimental evidence of our improved mask conversion applied to HMAC-SHA-1. Simulation results show that our algorithms improve the execution time by 85% at the expense of little memory overhead. [less ▲] Detailed reference viewed: 222 (5 UL)Higher-Order Masking in Practice: A Vector Implementation of Masked AES for ARM NEON ; Vadnala, Praveen Kumar ; Groszschädl, Johann et al in Nyberg, Kaisa (Ed.) Topics in Cryptology - CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, San Francisco, CA, USA, April 20-24, 2015. Proceedings (2015, April) Real-world software implementations of cryptographic algorithms need to be able to resist various kinds of side-channel attacks, in particular Differential Power Analysis (DPA). Masking is a widely-used ... [more ▼] Real-world software implementations of cryptographic algorithms need to be able to resist various kinds of side-channel attacks, in particular Differential Power Analysis (DPA). Masking is a widely-used countermeasure to protect block ciphers like the Advanced Encryption Standard (AES) against DPA attacks. The basic principle is to split all sensitive intermediate variables manipulated by the algorithm into two shares and process these shares separately. However, this approach still succumbs to higher-order DPA attacks, which exploit the joint leakage of a number of intermediate variables. A viable solution is to generalize masking such that at least d+1 shares are used to protect against d-th order attacks. Unfortunately, all current higher-order masking schemes introduce a significant computational overhead compared to unmasked implementations. To facilitate the deployment of higher-order masking for the AES in practice, we developed a vector implementation of Coron et al's masking scheme (FSE 2012) for ARM NEON processors. After a comprehensive complexity analysis, we found that Coron et al's scheme with n shares for each sensitive variable needs O(n^2) multiplications in the field GF(2^8) and O(n^2) random-number generations. Both of these performance-critical operations are executed with only 15 instructions in our software, which is possible thanks to the rich functionality of the NEON instruction set. Our experimental results demonstrate that the performance penalty caused by the integration of higher-order masking is significantly lower than in generally assumed and reported in previous papers. For example, our second-order DPA-protected AES (with three shares for each sensitive variable) is merely eight times slower than an unmasked baseline implementation that resists cache-timing attacks. [less ▲] Detailed reference viewed: 185 (5 UL)Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity Coron, Jean-Sébastien ; Groszschädl, Johann ; et al in Leander, Gregor (Ed.) Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers (2015, March) A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean ... [more ▼] A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm. [less ▲] Detailed reference viewed: 202 (8 UL)Secure Conversion between Boolean and Arithmetic Masking of Any Order Coron, Jean-Sébastien ; Groszschädl, Johann ; Vadnala, Praveen Kumar in Batina, Lejla; Robshaw, Matthew (Eds.) Cryptographic Hardware and Embedded Systems - CHES 2014, 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings (2014, September) Detailed reference viewed: 154 (12 UL)Algorithms for Switching between Boolean and Arithmetic Masking of Second Order Vadnala, Praveen Kumar ; Groszschädl, Johann in Gierlichs, Benedikt; Guilley, Sylvain; Mukhopadhyay, Debdeep (Eds.) Security, Privacy, and Applied Cryptography Engineering - Third International Conference, SPACE 2013, Kharagpur, India, October 19-23, 2013. Proceedings (2013, October) Masking is a widely-used countermeasure to thwart Differential Power Analysis (DPA) attacks, which, depending on the involved operations, can be either Boolean, arithmetic, or multiplicative. When used to ... [more ▼] Masking is a widely-used countermeasure to thwart Differential Power Analysis (DPA) attacks, which, depending on the involved operations, can be either Boolean, arithmetic, or multiplicative. When used to protect a cryptographic algorithm that performs both Boolean and arithmetic operations, it is necessary to change the masks from one form to the other in order to be able to unmask the secret value at the end of the algorithm. To date, known techniques for conversion between Boolean and arithmetic masking can only resist first-order DPA. This paper presents the first solution to the problem of converting between Boolean and arithmetic masking of second order. To set the context, we show that a straightforward extension of first-order conversion schemes to second order is not possible. Then, we introduce two algorithms to convert from Boolean to arithmetic masking based on the second-order provably secure S-box output computation method proposed by Rivain et al (FSE 2008). The same can be used to obtain second-order secure arithmetic to Boolean masking. We prove the security of our conversion algorithms using similar arguments as Rivain et al. Finally, we provide implementation results of the algorithms on three different platforms. [less ▲] Detailed reference viewed: 173 (11 UL) |
||