11
$\begingroup$

In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain security by having the basepoint for the key exchange (a polynomial with coefficients in a finite field) randomly generated by the key exchange initiator for every key exchange.

My question is whether this basepoint generation scheme is vulnerable to a lattice analog of Bernstein's attack on the NIST elliptic curves in his paper, "How to Manipulate Standards: A White Paper for a Black Hat." In that paper a single party is allowed to randomly generate a sensitive cryptographic parameter that was to be used by others.

$\endgroup$
1
  • 1
    $\begingroup$ Correct me if I'm wrong, but don't both parties of the key exchange have to trust each other with the symmetric key anyway and no one else uses the same random values? $\endgroup$
    – otus
    Commented May 21, 2016 at 15:34

1 Answer 1

4
$\begingroup$

Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange.

Here is why the attack does indeed apply. Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange. Bob will be the key exchange initiator and Alice will be the key exchange responder. Bob wants to help the internet surveillance authorities run by Bernstein's "heroic" eavesdropper "Eve." However, Bob does not want to be seen cooperating with Eve by turning over the key for the key exchange or the plaintext information to Eve. Bob asks Eve for a more subtle way to help her "heroic" cause.

In Bernstein's "White Paper for a Black Hat" he and his co-authors assume that Eve knows a class of weak elliptic curves unknown to the rest of the world. Eve knows that one would randomly select one of these weak elliptic curves with probability p. To carry this attack over to the New Hope Lattice domain we must assume that Eve knows a class of weak New Hope basepoints that are unknown to the rest of the world. Let us assume that Eve knows of such a class of weak basepoints and that these weak basepoints occur with probability p.

The New Hope basepoint generation scheme would have Bob generate a random seed and use the SHAKE-128 algorithm and some other processing to produce a random basepoint (polynomial) for the key exchange. Bob is supposed to do this only once. Hence the probability that Bob randomly hits a weak basepoint is p. However, Eve tells Bob not to generate just one basepoint but gives Bob a long list of seeds that will generate weak basepoints. Instead of generating RANDOM seeds Bob uses a seed from the list that Eve gave him.

Bob and Alice complete the New Hope key exchange as described by its authors. Eve collects the key exchange and uses her knowledge of the weakness in the basepoints to break the key exchange and recover the traffic. While it is true that Bob could have compromised the key exchange to Eve in many other ways. The method pointed to in your question is a protocol weakness that could be corrected.

Fortunately, there is a very easy fix to the New Hope protocol that eliminates this attack. If the initiator and the responder both generate random seeds, exchange them and a concatenation of these seeds is used in the generation of a random basepoint then the attack only works if BOTH Bob and Alice are colluding with Eve. The right thing to do in New Hope is to have both initiator and responder contribute to the basepoint generation process. In protocols like TLS that already have exchanges of random information (the "Hello" messages) this protocol change seems entirely fitting.

Ironically Bernstein has been questioning the underlying security of the cryptography on which the New Hope scheme is based and has referenced a number of large classes of lattice parameter sets that are weak

$\endgroup$
4
  • $\begingroup$ Eve could still compromise the cryptosystem if Bob waits for Alice' random seed to arrive, gives it to Eve, and she finds Bob's seed that yields the secret elliptic curve. Or do I miss something? $\endgroup$
    – yo'
    Commented May 21, 2016 at 19:50
  • 1
    $\begingroup$ Thank you. Yes you are correct. I overlooked that fact in my answer. To be a fair protocol, Bob should first a hash of his seed and send the hash of the seed to Alice as a "commitment". Then Alice sends her seed to Bob. That constitutes the first exchange. Bob then concatenates Alice's seed with his own and uses the new hope scheme to generate the New Hope Basepoint. During the New Hope Key Exchange Bob sends his seed along with his key exchange information. Before generating the basepoint, Alice first checks to see that Bob's seed hashes to the value he committed to. That should work $\endgroup$ Commented May 21, 2016 at 22:51
  • $\begingroup$ And I of course forgot about this simple way of preventing that attack... $\endgroup$
    – yo'
    Commented May 21, 2016 at 23:06
  • 5
    $\begingroup$ Regarding the last paragraph: Bernstein has certainly questioned the security of the crypto underlying New Hope (specifically, Ring-LWE in cyclotomics with certain error distributions), but no plausible attack strategy that beats standard lattice attacks has been proposed. In particular, none of the suggested parameter sets are known to be weak. (Other variants of Ring-LWE are known to be weak, but they are pathological: see, e.g., eprint.iacr.org/2016/239 and eprint.iacr.org/2016/351 ) $\endgroup$ Commented May 22, 2016 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.