24 research outputs found
(One) Failure Is Not an Option:Bootstrapping the Search for Failures in Lattice-Based Encryption Schemes
No full textsponsorship: J.-P. D'Anvers-The research of D'Anvers was supported the European Commission through the Horizon 2020 research and innovation programme Cathedral ERC Advanced Grant 695305, by the CyberSecurity Research Flanders with reference number VR20192203 and by the Semiconductor Research Corporation (SRC), under task 2909.001. M. Rossi-The research of Rossi was supported by the European Union's H2020 Programme under PROMETHEUS project (grant 780701). It was also supported by the French Programme d'Investissement d'Avenir under national project RISQ P14158. F. Virdia-The research of Virdia was supported by the EPSRC and the UK government as part of the Centre for Doctoral Training in Cyber Security at Royal Holloway, University of London (EP/P009301/1). (European Commission through the Horizon 2020 research and innovation programme Cathedral ERC Advanced Grant|695305, CyberSecurity Research Flanders|VR20192203, Semiconductor Research Corporation (SRC)|2909.001, European Union's H2020 Programme under PROMETHEUS project|780701, French Programme d'Investissement d'Avenir|RISQ P14158, EPSRC, UK government as part of the Centre for Doctoral Training in Cyber Security at Royal Holloway, University of London|EP/P009301/1)status: Publishe
Post-Quantum Cryptography: Cryptanalysis and Implementation
No full textPost-quantum cryptography is the field of study and development of cryptographic primitives providing security in the presence of adversaries capable of running large-scale error-tolerant quantum computations. Works in this area span from theoretical analysis of security definitions and protocols, to the research of classical and quantum cryptanalytic algorithms, to the development of cryptographic schemes that can be deployed for real-world usage.In this thesis, we investigate three topics in practical post-quantum cryptography. First, we research quantum circuit depth-width trade-offs in the case of Grover’s algorithm and how these impact the cost of running key-search attacks against block ciphers. Such attacks have been proposed by the US National Institute of Standards and Technology as benchmarks to define quantum security, and hence their cost should be well understood. Furthermore, Grover speed-ups are a component of many quantum attacks, making the study of these trade-offs of independent interest.Second, we study the "primal attack" on lattice-based cryptosystems. This consists of using lattice reduction to recover an unusually short vector in a q-ary lattice, which results in a break of LWE- and NTRU-based schemes. We compare two alternative heuristics used to estimate the expected cost of this attack due to Gama et al. (Eurocrypt 2008) and Alkim et al. (USENIX 2016) and provide experimental evidence of the validity of the latter. Then, using the techniques introduced in Dachman-Soled et al. (Crypto 2020), we continue this line of work to provide estimates on the full probability distribution of the cost of the attack, providing further experimental validation.In the last chapter, we move our focus from cryptanalysis to implementation. We implement a lattice-based actively secure key encapsulation mechanism on a currently commercially available smart card from the SLE 78 family by Infineon. We do this by repurposing classic arithmetic techniques that enable us to take advantage of the card’s RSA coprocessor to compute polynomial multiplications in Z_q [x]/(x^256 +1). The resulting scheme, a variant of Kyber768, runs key generation in 79.6 ms, encapsulation in 102.4 ms, and decapsulation in 132.7 ms. Our techniques can be adapted to other RSA/ECC coprocessors and demonstrate the feasibility of repurposing already deployed cryptographic coprocessors to run post-quantum encryption with reasonable performances.<br/
Popping “R-propping”: breaking hardness assumptions for matrix groups over F_{2^8}
No full textA recent series of works (Hecht, IACR ePrint, 2020–2021) propose to build post-quantum public-key encapsulation, digital signatures, group key agreement and oblivious transfer from R-propped variants of the Symmetrical Decomposition and Discrete Logarithm problems for matrix groups over . We break all four proposals by presenting a linearisation attack on the Symmetrical Decomposition platform, a forgery attack on the signature scheme, and a demonstration of the insecurity of the instances of the Discrete Logarithm Problem used for signatures, group key agreement and oblivious transfer, showing that none of the schemes provides adequate security
A note on securing insertion-only Cuckoo filters
No full textWe describe a small tweak to Cuckoo filters that allows securing them under insertions using the techniques from Filić et al. (ACM CCS 2022), without the need for an outer PRF call
On the Success Probability of Solving Unique SVP via BKZ
No full textAs lattice-based key encapsulation, digital signature, and fully homomorphic encryption schemes near standardisation, ever more focus is being directed to the precise estimation of the security of these schemes. The primal attack reduces key recovery against such schemes to instances of the unique Shortest Vector Problem (uSVP). Dachman-Soled et al. (Crypto 2020) recently proposed a new approach for fine-grained estimation of the cost of the primal attack when using Progressive BKZ for lattice reduction. In this paper we review and extend their technique to BKZ 2.0 and provide extensive experimental evidence of its accuracy. Using this technique we also explain results from previous primal attack experiments by Albrecht et al. (Asiacrypt 2017) where attacks succeeded with smaller than expected block sizes. Finally, we use our simulators to reestimate the cost of attacking the three lattice KEM finalists of the NIST Post Quantum Standardisation Process
Practical Semi-Open Chat Groups for Secure Messaging Applications
No full textChat groups in secure messaging applications such as Signal, Telegram, and Whatsapp are nowadays used for rapid and widespread dissemination of information to large groups of people. This is common even in sensitive contexts, associated with the organisation of protests, activist groups, and internal company dialogues. Manual administration of who has access to such groups quickly becomes infeasible, in the presence of hundreds or thousands of members.
We construct a practical, privacy-preserving reputation system, that automates the approval of new group members based on their reputation amongst the existing membership. We demonstrate security against malicious adversaries in a single-server model, with no further trust assumptions required. Furthermore, our protocol supports arbitrary reputation calculations while almost all group members are offline (as is likely). In addition, we demonstrate the practicality of the approach via an open-source implementation. For groups of size 50 (resp. 200), an admission process on a user that received 40 (resp. 80) scores requires 1312.2 KiB (resp. 5239.4 KiB) of communication, and 3.3s (resp. 16.3s) of overall computation on a single core. While our protocol design matches existing secure messaging applications, we believe it can have value in distributed reputation computation beyond this problem setting
Finding Bugs and Features Using Cryptographically-Informed Functional Testing
No full textIn 2018, Mouha et al. (IEEE Trans. Reliability, 2018) performed a postmortem investigation of the correctness of reference implementations submitted to the SHA3 competition run by NIST, finding previously unidentified bugs in a significant portion of them, including two of the five finalists. Their innovative approach allowed them to identify the presence of such bugs in a black-box manner, by searching for counterexamples of expected cryptographic properties of the implementations under test. In this work, we extend their approach to key encapsulation mechanisms (KEMs) and digital signature schemes (DSSs). We perform our tests on multiple versions of the LibOQS collection of post-quantum schemes to capture implementations at different points of the recent Post-Quantum Cryptography Standardization Process run by NIST. We identify multiple bugs, ranging from software bugs (segmentation faults, memory overflows) to cryptographic bugs, such as ciphertext malleability in KEMs claiming IND-CCA security. We also observe various features of KEMs and DSSs that do not contradict any security guarantees but could appear counter-intuitive. Finally, we compare this methodology with a traditional fuzzing campaign against LibOQS and SUPERCOP, observing that traditional fuzzing harnesses appear less effective in surfacing software and logical bugs
Finding Bugs and Features Using Cryptographically-Informed Functional Testing
No full textIn 2018, Mouha et al. (IEEE Trans. Reliability, 2018) performed a post-mortem investigation of the correctness of reference implementations submitted to the SHA3 competition run by NIST, finding previously unidentified bugs in a significant portion of them, including two of the five finalists. Their innovative approach allowed them to identify the presence of such bugs in a black-box manner, by searching for counterexamples of expected cryptographic properties of the implementations under test. In this work, we extend their approach to key encapsulation mechanisms (KEMs) and digital signature schemes (DSSs). We perform our tests on multiple versions of the LibOQS collection of post-quantum schemes to capture implementations at different points of the recent Post-Quantum Cryptography Standardization Process run by NIST. We identify multiple bugs, ranging from software bugs (segmentation faults, memory overflows) to cryptographic bugs, such as ciphertext malleability in KEMs claiming IND-CCA security. We also observe various features of KEMs and DSSs that do not contradict any security guarantees but could appear counter-intuitive. Finally, we compare this methodology with a traditional fuzzing campaign against LibOQS and SUPERCOP, observing that traditional fuzzing harnesses appear less effective in surfacing software and logical bugs
