La prochaine édition du séminaire C2 se tiendra le vendredi 16 novembre 2018 dans la salle 105 couloir 25-26 du LIP6 de Sorbonne Université
- 10h00 : Alice Pellet-Mary, LIP ENS-Lyon : Quantum attack against some candidate obfuscators based on GGH13
Résumé : Since the first candidate indistinguishability obfuscator (iO) has been proposed in 2013 by Garg, Gentry, Halevi, Raykova, Sahai and Waters, a lot of other candidates have been proposed. All these constructions are only candidate constructions, in the sense that they come with no security proof. Alongside with all these constructions, some attacks have also been proposed, breaking many of the candidates.
In this talk, I will present a quantum attack against some iO that were not broken yet. This attack relies on recovering a short generator of a principal ideal in a cyclotomic field, which can be done in quantum polynomial time thanks to the works of Biasse and Song (SODA 2016) and Cramer, Ducas, Peikert and Regev (Eurocrypt 2016). Once this short generator is recovered, the rest of the attack is a mixed-input attack, which does not require any quantum computer.
- 11h15 : Baptiste Lambin, IRISA : On Recovering Affine Encodings in White-Box Implementations
Résumé : Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., other constructions were later built around the same framework. In this framework, the round function of the cipher is “encoded” by composing it with non-linear and affine layers known as encodings. However, all such attempts were broken by a series of increasingly efficient attacks that are able to peel off these encodings, eventually uncovering the underlying round function, and with it the secret key. These attacks, however, were generally ad-hoc and did not enjoy a wide applicability. As our main contribution, we propose a generic and efficient algorithm to recover affine encodings, for any Substitution-Permutation-Network (SPN) cipher, such as AES, and any form of affine encoding. For AES parameters, namely 128-bit blocks split into 16 parallel 8-bit S-boxes, affine encodings are recovered with a time complexity estimated at 2^32 basic operations, independently of how the encodings are built. This algorithm is directly applicable to a large class of schemes. We illustrate this on a recent proposal due to Baek, Cheon and Hong, which was not previously analyzed. While Baek et al. evaluate the security of their scheme to 110 bits, a direct application of our generic algorithm is able to break the scheme with an estimated time complexity of only 2^35 basic operations. As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2^31 . We also provide an implementation of the attack, which is able to recover the secret key in about 12 seconds on a standard desktop computer.
- 13h45 : Jean-Marc Robert, Université de Toulon : Enhanced Digital Signature using Splitted Digit Exponent Representation
Résumé : Digital Signature Algorithm (DSA) involves modular exponentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory, to its small size and to the latency of access, previous research sought for minimization of the storage. In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponentiation computation. The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches. This work has been presented at WAIFI 2016 conference. We extend this approach to the Elliptic Curve Scalar Multiplication with another multiplicative digit approach we call R-splitting, providing side-channel resistance.
- 15h00: Anand Kumar Narayanan, LIP6 , Sorbonne université : Nearly linear time encodable codes beating the Gilbert-Varshamov bound.
