Wishlist: Post-Quantum Cryptography

[DonaldTsang]

• Open Quantum https://github.com/open-quantum-safe/liboqs
• NTRU https://github.com/NTRUOpenSourceProject
• SPHINCS https://github.com/gravity-postquantum/gravity-sphincs and https://github.com/ahf/sphincs and https://github.com/sphincs
• XMSS Wishlist: Post-Quantum Cryptography #461 (comment)
• LMS Wishlist: Post-Quantum Cryptography #461 (comment)

Proven insecure and therefore removed from the list

• SIDH https://github.com/Microsoft/PQCrypto-SIDH and https://github.com/sidh-crypto/sidh-c-reference and https://github.com/tigusoft/libsidhms, c.f. Wishlist: Post-Quantum Cryptography #461 (comment)

[dmwheel1]

What about hash-based signatures?

• XMSS (RFC 8391 https://tools.ietf.org/html/rfc8391)
• LMS (RFC 8554 https://tools.ietf.org/html/rfc8554)

If I were to work on such a codebase, what would the preference be for integration into LTC?
a) Add a new top-level directory for PQC with directories for types of crypto
EX: src/pqc/hbs/xmss and src/pqc/hbs/lms
b) Add these directly into existing structure without notation as to their PQC heritage
EX: src/pk/xmss and src/pk/lms
c) Add a new top-level directory for hash-based signatures, since they are kind of a new animal
EX: src/hbs/xmss and src/hbs/lms

Or something else? Suggestions/direction being solicited. Thanks.

[DonaldTsang]

@dmwheel1 @sjaeckel I think the priorities are : complete cryptosystems with low footprint > complete cryptosystems with high footprints > pure signature schemes, also those who are being standardized > those made by others
Please check https://en.wikipedia.org/wiki/Post-quantum_cryptography#Open_Quantum_Safe_project and https://en.wikipedia.org/wiki/Post-Quantum_Cryptography_Standardization#Round_Two

[dmwheel1]

@DonaldTsang XMSS and LMS actually ARE part of the NIST PQC set, but are not experimental, so they do not fall into the Round Two set - their security is not in question, since they are based on solid cryptographic techniques going back to the mid-1970's. See https://csrc.nist.gov/Projects/stateful-hash-based-signatures/news and the draft standard here https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208-draft.pdf
SPINCS+(one of the Round Two Candidates) is actually an extension of XMSS but using "many-time-signatures" instead of "one-time-signatures" and this extension needs some more scrutiny.
HBS schemes have many advantages over the other PQC algorithms, including speed and root public key size; Signature size (and fully expanded public key) are an order of magnitude larger than RSA keys. All that to say, IMHO, the HBS schemes are an important (though perhaps less glamorous) addition to the PQC algorithm set.

BTW, one of my team members is working on BIKE and Classic McEliece, so a future contribution in this area would be possible.

[DonaldTsang]

@dmwheel1 in that case are there any documents that give info into which current cryptographic algorithms is based on what other algorithms/principles? Good to have BIKE people here tho.

[dmwheel1]

@DonaldTsang I am not aware of a specific documentation that lists the relations among the PQC candidates, though I have seen some categorizations in various papers and presentations. My comment regarding SPINCS+ is based on my personal analysis reading the HBS academic papers and standards.

[sjaeckel]

I think it makes sense to go with standardized solutions for now instead of spending effort on proposals. If it doesn't have an RFC or other freely available specification (i.e. IETF, NIST or some other standards body published it) it doesn't make sense to be included IMO.

Regarding the integration, I like the proposal of going with b) and putting them in src/pk/xmss resp. src/pk/lms as these are "simply" new PK algorithms IIUC.

If we'll ever go and add "draft" algorithms (which I doubt since the issue with #256) I'd propose to add new src/experimental/{cipher,pk,...} folders where they can be added.

[DonaldTsang]

The problem is that nothing Post-Quantum related are standardized yet, all the citations made are proposals that are so close of being standardized.

[dmwheel1]

@DonaldTsang Respectfully, I believe you are mistaken regarding HBS algorithms not being standardized (or we have different views of that definition). Both XMSS and LMS are published standards out of the IETF Crypto Research Group (link above). NIST has published their DRAFT standard and the public comment period is over (link above), meaning that publication of the final standard is imminent (definition of imminent with a government involved and in these COVID-19 challenging times is up for debate ;-) ). If NIST publishes their specification, would that meet your definition of a standardized algorithm, or would you look for other criteria?
@ALL - I'll begin work on this and in the meantime, perhaps NIST will publish their final specification.

[sjaeckel]

They have an RFC -- yes I'm aware the RFC's are only informational and from the IRTF/CFRG, not IETF -- but I call this usually standardized. Or am I wrong there?

[dmwheel1]

The CFRG (Crypto Forum Research Group) - the crypto group at IETF - only publishes informational RFCs. Until I started regularly attending IETF meetings, I was unaware of this fact. The CFRG actually is organized in the research side of the group (the IRTF) not the engineering side (the IETF).
Anyway, from the IETF perspective, XMSS and LMS are available for use in standards, if a standards working group believes it is prudent. No further "standardization" steps are required for these algorithms to be brought into an IETF RFC (what we would more colloquially call a standard).

[oittaa]

OpenSSH ships with a post quantum algorithm enabled by default.

OpenSSH 9.0/9.0p1 (2022-04-08)

• ssh(1), sshd(8): use the hybrid Streamlined NTRU Prime + x25519 key
  exchange method by default ([email protected]).
  The NTRU algorithm is believed to resist attacks enabled by future
  quantum computers and is paired with the X25519 ECDH key exchange
  (the previous default) as a backstop against any weaknesses in
  NTRU Prime that may be discovered in the future. The combination
  ensures that the hybrid exchange offers at least as good security
  as the status quo.

  We are making this change now (i.e. ahead of cryptographically-
  relevant quantum computers) to prevent "capture now, decrypt
  later" attacks where an adversary who can record and store SSH
  session ciphertext would be able to decrypt it once a sufficiently
  advanced quantum computer is available.

[TPS]

SIDH/SIKE are proven "insecurable" & the authors have posted such @ NIST. Could the top post be updated?

[VA1DER]

You should put implementing RSA in larger key sizes on your list.

RSA in key sizes supported by OpenSSH (16384-bit) is a great practical post-quantum algorithm in the exact same way it is a great algorithm today. It works today because no practical computer can be built to factor it. It works post-quantum because in order for Shore's algorithm to work on a 16384-bit key, you need a quantum computer with a quantum gate count into the billions. In short, no practical quamtum computer on the conceivable horizon can make one.

To factor a prime number with Shores, you need somewhere between O(n^2 * log(n)) (the number of gates for the quantum Fourier transform) and O(n^3) (overall complexity) gates.

This makes good old RSA with key sizes on the upper-end of what is already commonly available a good choice for quantum resistance since it requires a gate count far in excess of what is likely on the horizon in a time frame equal to classical computer factoring capabilities growth.

tl;dr Please support RSA key sizes up to and including the 16384-bit sizes that most SSH implementations support.

[sjaeckel]

tl;dr Please support RSA key sizes up to and including the 16384-bit sizes that most SSH implementations support.

We don't limit RSA key sizes, i.e. you're limited by what your math provider and your hardware constraints allow.

If you use ltm or GMP your limit is "the sky"^TM, tfm in default config is indeed limited to RSA 2048, but you could also compile it with RSA16384 support (which will most likely cause some stack overflows if you aren't careful :) ).

C.f. e.g. https://github.com/libtom/libtomcrypt/blob/develop/tests/rsa/rsa_size_16384_bits.der which is used here

libtomcrypt/tests/rsa_test.c

Line 477 in e0d90c5

DO(test_process_dir("tests/rsa", &key, s_rsa_import_x509, NULL, (dir_cleanup_cb)rsa_free, "rsa_test"));

If you find out that this is not true or something doesn't work as expected, feel free to open an issue! This would be a bug.

[VA1DER]

libtomcrypt/src/math/rand_prime.c

   /* allow sizes between 2 and 512 bytes for a prime size */
   if (len < 2 || len > 512) {
      return CRYPT_INVALID_PRIME_SIZE;
   }

So it will use, but not generate RSA16384 keys?

[sjaeckel]

So it will use, but not generate RSA16384 keys?

Indeed that looks like there's a limit that we will only generate up to 81924096 bit keys. Seems like an arbitrary limit that most likely could be lifted.

Also as mentioned above: please open a separate issue (or you're also free to provide a PR fixing this :) ).

[sjaeckel]

RSA16384 support (which will most likely cause some stack overflows if you aren't careful :) ).

@levitte asked for it, so I had a deeper look and did some numbers and I now believe that my statement was wrong for most use cases.

Please check libtom/tomsfastmath#32 (comment) for details.