Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack? 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.
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