Bad curves and weak crypto

From Elliptic Curve 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 [1][2][3][4][5][6].

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, logit and probit models, 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.

So back to Elliptic Curve Crypto:General disclaimer.

Recommendations for elliptic curve PKE

At the same time we cannot have an article that is all negative, without suggestions to move things along in a more positive direction for elliptic curve public key encryption schemes of adequate security.

Public key encryption schemes of adequate security

The basic recommendations of a total beginner at the black arts would be to start at the beginning with irreducible elliptic curves in the classic Weierstraß normal form

using rational coefficients a and b chosen at random and enforced to be of a minimum height or algebraic complexity. The classic point group operation may be employed, without oversimplifying it to a simple cyclic group.

Large prime numbers, again, chosen at random, should be used as moduli in all elliptic curve cryptographic schemes.

We should generally be on the lookout for weak keys and strive to avoid them without overspecifying the implementation. If there isn't a good justifiable reason to specify particular common magic numbers for any cryptographic scheme, then they should be chosen at random, unique for each user.

Do not pay attention to clamors for extreme efficiency in particular implementations or cycle counts on particular machine architectures. Instead, publish full engineering specifications with theoretical justifications of all “choices” made for implementation of recommended algorithms by qualified software engineers in any programming language of their choice with all the diagrams, flow charts, and pseudocode, with indications of critical sections of code that need to be made branch-free or lookup-free to guard against timing attacks.

  1. Dustin Moody. “Announcing Issuance of Federal Information Processing Standard (FIPS) 186-5, Digital Signature Standard.” Federal Register, 02/03/2023. https://www.federalregister.gov/documents/2023/02/03/2023-02273/announcing-issuance-of-federal-information-processing-standard-fips-186-5-digital-signature-standard
  2. Anonymous. (FBI). The Need for Lawful Access FBI Asks Technology Companies for Support in Pursuing Child Abusers, Other Criminals, Oct 4, 2019. https://www.fbi.gov/news/stories/wray-speaks-at-lawful-access-summit-100419
  3. S.4051 - Lawful Access to Encrypted Data Act. Latest Action: Senate - 06/23/2020 Read twice and referred to the Committee on the Judiciary. https://www.congress.gov/bill/116th-congress/senate-bill/4051
  4. William Mack. “The Key to Lawful Access: An Analysis of the Alternatives Offered in the Encryption Debate.” Homeland Security Affairs: The Journal of the NPS Center for Homeland Defense and Security. September 2020. https://www.hsaj.org/articles/16650
  5. U.S. Department of Justice // Office of Legal Policy // Lawful Access // Encryption and Lawful access. https://www.justice.gov/olp/lawful-access#5
  6. NIST // Information Technology Laboratory // Computer Security Resource Center // Projects // Elliptic Curve Cryptography (ECC) https://csrc.nist.gov/Projects/Elliptic-Curve-Cryptography