Bad curves and weak crypto

Bad crypto curve. The geometry is a little bit off. Come to find out, it's a squared conic section.

Any area of applied science is going to need a “loser article” to describe what can and will go wrong, according to “Murphy’s Law.” There’s a totally Establishment-oriented SafeCurves® initiative that’s starting to become obnoxious at certain levels.

One of Bernstein’s goals was to avoid conditional branches and array look-ups based on secret keys or secret data in crypto algorithms. However the cycle counts on particular microprocessor models are irrelevant at best and misleading at worst to long-term security. The intention there has been to establish patent claims on elliptic curve cryptography as a tangible marketable invention, and tying the implementation to particular microprocessor architectures and specific sequences of machine instructions was perceived, perhaps wrongly, as a valid way to do that in court.

What implementers and users need is abstract pseudocode or general guidelines or feedback, peer review or auditing of open source code, on developing branch-free or look-up-free code for critical places in programs. However, peer review doesn’t work when the peers are all insiders of the educational and corporate government-political Establishment. The focus on extreme efficiency of implementation or hand-optimized machine or assembly code is misplaced. Of course we want applications of crypto code to be efficient, but we want the cracking of it to be as inefficient and difficult as possible. Clocking cycle counts on particular machine architectures is a general purpose computing concern, not especially relevant to the safety or security cryptographic operations.

The keys are too small, and when extremely “efficient” implementations exist, the same methods of linear and differential cryptanalysis, Turbo and Viterbi algorithms etc., applied to block ciphers might be used to back out the computations of elliptic curve encryption and recover secrets from ciphertext. Methods of simulated annealing, “quantum” or not, might be used, and even enhanced with artificial intelligence to pick up correlations from which secret keys and/or secret data may be derived.

So we’re doing it all wrong, and that’s why most of us are losers at the crypto game. We lack the abstract pseudocode, engineering diagrams, flowcharts, test vectors to describe the algorithm and where it needs to be made branch-free or look-up-free in critical spots. We don’t need to know the details of cache timing on your already outdated Pentium or PowerPC architecture to develop sound, theoretically justified secure architecture-independent crypto implementations, in any given programming language.

Back to Elliptic Curve Crypto:General disclaimer.