Projekt per år
Sammanfattning
Codebased cryptography is one of the main techniques enabling cryptographic primitives in a postquantum scenario. In particular, the MDPC scheme is a basic scheme from which many other schemes have been derived. These schemes rely on iterative decoding in the decryption process and thus have a certain small probability p of having a decryption (decoding) error.
In this paper we show a very fundamental and important property of codebased encryption schemes. Given one initial error pattern that fails to decode, the time needed to generate another message that fails to decode is strictly much less than 1/p. We show this by developing a method for fast generation of undecodable error patterns (error pattern chaining), which additionally proves that a measure of closeness in ciphertext space can be exploited through its strong linkage to the difficulty of decoding these messages. Furthermore, if sidechannel information is also available (time to decode), then the initial error pattern no longer needs to be given since one can be easily generated in this case.
These observations are fundamentally important because they show that a, say, 128 bit encryption scheme is not inherently safe from reaction attacks even if it employs a decoder with a failure rate of 2−128. In fact, unless explicit protective measures are taken, having a failure rate at all – of any magnitude – can pose a security problem because of the error amplification effect of our method.
A keyrecovery reaction attack was recently shown on the MDPC scheme as well as similar schemes, taking advantage of decoding errors in order to recover the secret key. It was also shown that knowing the number of iterations in the iterative decoding step, which could be received in a timing attack, would also enable and enhance such an attack. In this paper we apply our error pattern chaining method to show how to improve the performance of such reaction attacks in the CPA case. We show that after identifying a single decoding error (or a decoding step taking more time than expected in a timing attack), we can adaptively create new error patterns that have a much higher decoding error probability than for a random error. This leads to a significant improvement of the attack based on decoding errors in the CPA case and it also gives the strongest known attack on MDPClike schemes, both with and without using sidechannel information.
In this paper we show a very fundamental and important property of codebased encryption schemes. Given one initial error pattern that fails to decode, the time needed to generate another message that fails to decode is strictly much less than 1/p. We show this by developing a method for fast generation of undecodable error patterns (error pattern chaining), which additionally proves that a measure of closeness in ciphertext space can be exploited through its strong linkage to the difficulty of decoding these messages. Furthermore, if sidechannel information is also available (time to decode), then the initial error pattern no longer needs to be given since one can be easily generated in this case.
These observations are fundamentally important because they show that a, say, 128 bit encryption scheme is not inherently safe from reaction attacks even if it employs a decoder with a failure rate of 2−128. In fact, unless explicit protective measures are taken, having a failure rate at all – of any magnitude – can pose a security problem because of the error amplification effect of our method.
A keyrecovery reaction attack was recently shown on the MDPC scheme as well as similar schemes, taking advantage of decoding errors in order to recover the secret key. It was also shown that knowing the number of iterations in the iterative decoding step, which could be received in a timing attack, would also enable and enhance such an attack. In this paper we apply our error pattern chaining method to show how to improve the performance of such reaction attacks in the CPA case. We show that after identifying a single decoding error (or a decoding step taking more time than expected in a timing attack), we can adaptively create new error patterns that have a much higher decoding error probability than for a random error. This leads to a significant improvement of the attack based on decoding errors in the CPA case and it also gives the strongest known attack on MDPClike schemes, both with and without using sidechannel information.
Originalspråk  engelska 

Sidor (fråntill)  238258 
Tidskrift  IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) 
Volym  2019 
Nummer  1 
DOI  
Status  Published  2018 nov. 12 
Ämnesklassifikation (UKÄ)
 Datorsystem
Fingeravtryck
Utforska forskningsämnen för ”Error Amplification in Codebased Cryptography”. Tillsammans bildar de ett unikt fingeravtryck.Projekt
 1 Aktiva

Side channels on software implementations of postquantum cryptographic algorithms
Nilsson, A., Johansson, T. & Stankovski Wagner, P.
2017/09/01 → …
Projekt: Avhandling