Rambus security researchers have successfully conducted a side-channel assisted cryptanalysis attack against QcBits, a code-based public key algorithm based on a problem thought to be resistant to quantum computer attacks. QcBits – pronounced “quick-bits” – is a variant of the McEliece public-key cryptosystem based on quasi-cyclic (QC) moderate density parity check (MDPC) codes.
According to Rambus Security technical director Mark E. Marson, the attack only required researchers to observe a relatively small number of decryptions – approximately 200 power traces for the analyzed implementation. Moreover, less than 1% of each trace needed to be analyzed. As Marson told Rambus Press, the side-channel attack comprised two steps. The first, a Differential Power Analysis (DPA) attack, targeted the syndrome computation of the decryption operation.
“The operation used half of the private key. During this step, we recovered some information about that half of the key,” Marson explained. “Because of the way in which the implementation leaks, there was some ambiguity as to the exact location of the nonzero elements of the key.”
The second step was based on a linear algebra computation which exploited the sparseness of the private key and succeeded with high probability.
“We repeated this operation – varying the equations slightly each time – until the computation succeeded,” Marson elaborated. “This allowed us to recover the entire secret key.”
In a detailed paper that was presented at CHES 2017, the Rambus security team proposed a simple masking technique to help defend against future side-channel attacks targeting QcBits during the syndrome calculation process. Essentially, since QC-MDPC codes are linear, the XOR of two codewords is another codeword. In addition, all codewords are in the nullspace of the parity check matrix. As such, the corrupted codeword can be masked by XORing it with a random codeword – before passing it to the syndrome computation.
Importantly, the above-mentioned technique does not alter the outcome of the syndrome calculation, although it does effectively mask the DPA leak exploited by researchers. It should also be noted that this countermeasure is only effective during the syndrome calculation. Additional side-channel countermeasures are required to protect the private key during other calculations such as the bit flipping algorithm.
“Many proposals for post-quantum cryptography are based on noisy linear systems: lattices, learning with errors or error-correcting codes. In terms of side-channel resilience, these systems have an important difference from systems based on number-theoretic problems,” Marson added. “Leaking a few bits of a number-theoretic system may open up a new avenue of attack, but it usually doesn’t directly contribute to solving the underlying hard problem. For noisy linear systems, leaking a few bits of the secret is likely to directly erode the difficulty of the underlying hard problem. As such, designers may wish to consider the risks of side-channel analysis when evaluating post-quantum cryptographic algorithms.”
As we’ve previously discussed on Rambus Press, all cryptographic systems routinely leak information about the internal process of computing. In practical terms, this means attackers can exploit various techniques to extract the key and other secret information from a target device. This vector is known as side-channel attacks, which are commonly referred to as SCA.
Put simply, side-channel attacks monitor power consumption and electro-magnetic emissions while a device is performing cryptographic operations. Side-channel attacks conducted against electronic devices and systems are relatively simple and inexpensive to execute. This means attackers can exploit various side-channel techniques to gather data and extract secret cryptographic keys. As all physical electronic systems leak information, effective side-channel countermeasures should be implemented at the design stage to ensure protection of sensitive keys and data.
Interested in learning more about how Rambus security researchers cracked a post-quantum ‘QcBits’ cipher with side-channel power analysis? The full text of “A Side-Channel Assisted Cryptanalytic Attack Against QcBits,” written by Melissa Rossi, Mike Hamburg, Michael Hutter and Mark E. Marson is available for download here.
Be sure to stay tuned for more news about Rambus Security and our post-quantum cryptography projects, such as the quantum-resistant public-key cryptographic algorithms that we are preparing to submit to the National Institute of Standards and Technology (NIST).
