Exploiting Decryption Failures in Mersenne Number Cryptosystems
| Autor: | Jan-Pieter D'Anvers, Marcel Tiepelt |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
050101 languages & linguistics
Computer science business.industry Modulo 05 social sciences Mersenne prime Data_CODINGANDINFORMATIONTHEORY 02 engineering and technology Encryption law.invention law 0202 electrical engineering electronic engineering information engineering Key (cryptography) Code (cryptography) NIST Cryptosystem 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Arithmetic business Cryptanalysis GeneralLiterature_REFERENCE(e.g. dictionaries encyclopedias glossaries) |
| Zdroj: | Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography APKC@AsiaCCS |
| DOI: | 10.1145/3384940.3388957 |
| Popis: | Mersenne number schemes are a new strain of potentially quantum-safe cryptosystems that use sparse integer arithmetic modulo a Mersenne prime to encrypt messages. Two Mersenne number based schemes were submitted to the NIST post-quantum standardization process: Ramstake and Mersenne-756839. Typically, these schemes admit a low but non-zero probability that ciphertexts fail to decrypt correctly. In this work we show that the information leaked from failing ciphertexts can be used to gain information about the secret key. We present an attack exploiting this information to break the IND-CCA security of Ramstake. First, we introduce an estimator for the bits of the secret key using decryption failures. Then, our estimates can be used to apply the Slice-and-Dice attack due to Beunardeau et al. at significantly reduced complexity to recover the full secret. We implemented our attack on a simplified version of the code submitted to the NIST competition. Our attack is able to extract a good estimate of the secrets using $2^12 $ decryption failures, corresponding to $2^74 $~failing ciphertexts in the original scheme. Subsequently the exact secrets can be extracted in $O(2^46 )$ quantum computational steps. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|