Post quantum crypto

[Paragis]

Given that age aims to be the encryption tool for the future, it should include (asymmetric) crypto that will survive the expected arrival of quantum computers.

openssh already has this implemented:

... based on a combination of Streamlined NTRU Prime 4591^761 and X25519.
https://www.openssh.com/releasenotes.html

Alternatively the NIST Competition for post-quantum crypto is getting to the final round in summer 2020
https://en.wikipedia.org/wiki/Post-Quantum_Cryptography_Standardization

[Macil]

Do we know if the public keys for these systems are still short enough to use as command-line arguments comfortably, or would a post-quantum age need arguments that are files containing the public keys? I know some post-quantum systems have very large public keys.

[qnfm]

The length of encoded kyber512's public key is 1286 char. To trim its secret key size, I only store its key seed which is 32 bytes

[keisentraut]

The key sizes of sntrup761 are as following (see here):

• secret key: 1763 bytes
• public key: 1039 bytes

With Bech32 encoding, this will expand by +60% and result in very large recipients/identities.

[qnfm]

Sorry about that,the key seed size "32 bytes" was ture for kyber512's cpa-public key encryption,which I used to integrate into my first two version(<rc.3).
The key sizes before being encoded by bech32 in rc.3,which calls to cca-kyber512-kem, are as following:

• key seed: 64bytes
• public key:800bytes

[qnfm]

The key sizes of sntrup761 are as following (see here):

* secret key: 1763 bytes

* public key: 1039 bytes

With Bech32 encoding, this will expand by +60% and result in very large recipients/identities.

sntrup761's public key size is 1158 from this

[cyb3rz3us]

Given that the exchange method suggested above is still experimental, IMO this seems a bit premature for insertion into 'age' at present.

[Timo67235]

The 3. round of the NIST Post-Quantum Cryptography Standardization has already revealed a number of potential candidates for future post-quantum algorithms https://en.wikipedia.org/wiki/Post-Quantum_Cryptography_Standardization

The remaining algorithm all seem to have significantly larger key sizes, wich means that no matter which algorithms will be chosen in the end, large keys sizes will remain an issue would have to be dealt with.

With ed25519 breaking as soon as quantum computers with 3000 qubits arrive, modern crypto tools like age will need support for post quantum crypto rather sooner then later.

[keisentraut]

Just a small remark: Password-based encryption is already post-quantum secure because it only uses scrypt for key derivation and ChaCha20-Poly1305 for (authenticated) encryption. You can expect 128bit of post-quantum security against a powerful quantum computer who can run Grover's algorithm on the complete 256bit search space.

[markdascher]

I'm curious how confident we all are in this statement? The part that makes me wonder is the 128-bit file key.

I'm unfamiliar with the actual math myself–just that 128-bit is bad and 256-bit is good. 😄

Found a similar question asked here but with only a handful of comments.

[keisentraut]

You are right and my statement was wrong. You can expect only 64bit of post-quantum security against a powerful quantum computer. AFAIK, this should still be a much harder task than breaking the DLP problem for curve25519 with a quantum computer, i.e. breaking the default age recipient.

[FiloSottile]

I looked into this and according to more realistic models, the 128-bit key might be ok. https://twitter.com/FiloSottile/status/1544680619346694147

[agucova]

OpenSSH moved to make it a default on 9.0:

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.

[qnfm]

Here is my experimental implementation(for demo usage):
https://github.com/qnfm/age

[qnfm]

It could be compatible with original version.I just tweakd it for myself

[keisentraut]

@qnfm This is funny, I did something similiar.
I wrote a age plugin which does a hybrid encryption with x25519 and sntrup761. However, it comes with two downsides: You cannot convert a secret key to a public key and the recipients/identities are very long. But it should be as least as safe as x25519 alone. My plugin only runs with rage so far, because age does currently not support any plugins. See https://github.com/keisentraut/age-plugin-sntrup761x25519 .

[qnfm]

For the first issus, due to cloudflare's excellent work, there is an api to generate key pair deterministically from the given seed:
(pk,sk)<-Gene(seed)
And yeah, it is inevitable according to all round3 kem finalists, there will be at least one key containing a lot of info(e.g matrix). So I'm thinking about whether qrcode can be another way to represent public keys

[FiloSottile]

Now that NIST selected a post-quantum KEM for standardization, I will start to experiment with a Kʏʙᴇʀ512+X25519 plugin.

There are definitely UX issues around the public key size that will need solving, and I don't expect it to exit an experimental state until the NIST standard is published in 2024. Note that there might be patent issues with using Kʏʙᴇʀ before a NIST standard is available.

The good news is that we might not need to version the protocol to extend the file key, though. https://twitter.com/FiloSottile/status/1544680619346694147

[artemislena]

T.: W long key sizes, people're gonna use hashes for easier identification n verification (e.g. as for the latter, people might download the key from an official source, then compare its hash w, say, one that's specified on one or several third-party sources like https://artemislena.eu/services/verify.html). We'd suggest'ving some hashing stuff built in (or at the very least, a standard scheme being recommended), prolly based on BLAKE2b or SHA3 w sufficient digest size (256 bits or more?). 'f there's no official standard on hashing, people might mix these as well as less secure hashing functions, which'd worsen UX (n security).

[artemislena]

T.: https://blog.cr.yp.to/20231003-countcorrectly.html Ya may wanna reconsider Kyber512 specifically? Larger Kyber keys (or just using NTRU instead) might be fine, but accordinga this, Kyber512 doesn't even reach AES128's security margin.

[JosiahBSharkey]

Kyber was chosen because it was one of the least secure options like aes being chosen as standard instead of threefish or serpent that are more secure in every way but slower than hardware accelerated aes. For offline encryption you should not use the least secure standardized encryption because they are made to make people not notice the time it takes for online encryption. aes should also be replaced with serpent 256 using a tweakable stream cypher mode and kmac or threefish 1024 authenticated tweakable stream cypher because they are both better in every way than aes and just a little bit slower than hardware accelerated aes especially for offline encryption. Post quantum encryption is new and less tested than pre quantum and decryption time doesn't matter because it is offline so the best option would be a cascade of multiple hybrid post quantum algorithms. Scrypt should also be replaced with argon2 then the key size doesn't matter you can just put it in a file with more than 30 seconds of argon2 and a long password then you can store your secret keys with the secrets. This is what I do already but I keep my secrets in a luks loopback file and my keys in a luks loopback file inside of that because serpent is more secure than aes and it gives me a cascade of post quantum algorithms using a post quantum plugin to access secrets and a cascade of serpent and aes to protect secrets and I can store everything publicly without losing security because of a cascade of serpent protected with more than 30 seconds of argon2 with long passwords or sss locked with clevis and tang over wireguard psk for post quantum security, because sss is post quantum as long as you don't have threshold keyshares, to access secret keys and I sign the luks loopback files with sphincs+ so they can't be trusted if it is modified then I can use tools that require age without getting hacked by the NSA because they think I am a spy or a criminal because my opsec is so good they don't know what I am doing without hacking me even though they can trace me because there aren't any post quantum anonymity nets but they can't break the post quantum privacy of ssh session keys but they can steal the authentication key or host key and use those to hack you because they are pre quantum unless you run it over a post quantum VPN like wireguard psk

[JosiahBSharkey]

any encryption software that isn't post quantum is broken the only reason I can use age is because it has post quantum age plugins I have had a persistent active attacker that has broken into my house and covertly stolen things like encrypted drives and I was running ssh ed25519 and passwords turned off and tor authorized clients ed25519 and after a month I would have malware on my computer and that was before I have evidence of them stealing from me or breaking into my house this has been happening for a few years now so that means that a nation state that thinks I'm trying to hide something from them with my anonymity but I just want privacy for everything I don't tell people has been attacking me with a pretty slow quantum computer because it takes it a month to break 2 ed25519 keys

[lirc572]

Now that the NIST PQC standards are published, shall we start working on the new PQC recipient type?

Other references:

• ML-KEM X25519 support in OpenSSH 9.9
  • IETF draft: PQ/T Hybrid Key Exchange in SSH

[qnfm]

Agree