Preventing Potential backdoors in bike algorithm

Pavol Zajac, Peter Špaček


BIKE suite of algorithms is one of the candidates in NIST call for public-key post-quantum cryptographic algorithms. It is a key-encapsulation mechanism based on QC-MDPC codes with purely ephemeral keys. The security device implementing such an algorithm therefore needs to generate multiple key pairs in its lifetime very efficiently. In our paper we explore the situation where BigBrother-type adversary can subtly corrupt the vendor(s) of the security devices (e.g. by altering the standard algorithms).

In our model, BigBrother cannot preload the keys or synchronize the key generator by covert channel, but is able to learn secrets of security devices by observing the public execution of the KEM protocols. BigBrother typically obtains the secret through the usage of (masked) weak keys. However, we can also imagine other covert channel embedded into the ephemeral public keys by some unknown algorithm.

 To prevent these classes of attacks, we propose that the standard should explicitly specify a verifiable algorithm to transform the required key randomness into a set of keys.

Full Text: