Post-quantum cryptography | Hacker News Reader

Post-quantum cryptography

en.wikipedia.org

50 pointsdrallison21 comments

Shameless plug: a few months back, I was going thru a coding bootcamp and for a 2-day sprint (forgive me) I wrote a simple, entirely insecure Lamport-Merkle digital signature algorithm implementation [0] in JavaScript based on the "spec" outlined in the Wiki [1].

It uses nothing but Merkle trees and SHA-256 hashes, lacks documentation and should be used by no one, but the code is pretty simple to follow [2] and I'd appreciate any and all comments/criticisms in terms of implementation, optimizations, usage requirements and API improvements:

[0] https://github.com/sunny-g/Lamport-Merkle.js [1] https://en.wikipedia.org/wiki/Merkle_signature_scheme [2] http://blog.sunnyg.io/2014/12/13/merkle-key-trees-and-signat...

By the way, this is a pretty good intro to post-quantum crypto if you are more mathy.

http://pqcrypto.org/

The NSA announced they will be transitioning to quantum resistant algorithm in the "not to distant future".

https://www.nsa.gov/ia/programs/suiteb_cryptography/index.sh...

So this is something that may be getting a lot more press in the...not to distant future.

Q: Why should we care about this? Why not deal with it when quantum computers finally start cracking existing crypto?

1. It takes time to implement new methods. Would it be acceptable for there to be a period of months or years during which we can't make credit card transactions, etc.?

2. Coded text of messages encoded using conventional cryptographic methods can be intercepted, archived and then broken at a later date. If you make a purchase today, somebody archives the coded exchange, and a quantum computer capable of cracking the encryption used in that exchange becomes available before your credit card expires, you've got a problem. You've got an even bigger problem if you transmit information that remains sensitive for longer than your credit card info.

As a general rule, don't use conventional encryption methods to transmit information with long-term sensitivity (e.g. medical records, etc.).

> As a general rule, don't use conventional encryption methods to transmit information with long-term sensitivity (e.g. medical records, etc.).

So what do you suggest I use today, given that I have a medical record here and I need it over there?

Most recent NSA transitional recommendations are for 3072-bit asymmetric, and AES-256 symmetric.

Details: https://www.nsa.gov/ia/programs/suiteb_cryptography/index.sh...

For network transfers, you'll likely also want to select your encryption with PFS:

https://en.wikipedia.org/wiki/Forward_secrecy

PFS will make it so connections need to be individually attacked but since most PFS is done with Diffie-Hellman variants (susceptible to Shor's algorithm), the group size also needs to be large enough to resist early quantum computers.

For defense against large quantum computers, different PFS schemes need to be used (fortunately not hard to construct from other post quantum primitives).

My current, somewhat underinformed understanding:

(A) Handling key exchange (Diffie-Hellmman) is ugly. There are other algorithms, but I'm unclear what a good choice is right now. I'm also unclear if larger key sizes are actually helpful. (B) For symmetric algorithms, AES, use AES-256. In the quantum case, it might be equivalent to ~127-128 bit AES, which is pretty decent. (C) For hashing, use SHA-512. It uses 64-bit words, and might be similar in strength to SHA-256 today. (D) A lot of hash algorithms can actually be used as signature schemes, especially if you combine them with Merkle tree like structures.

One time pads sent via some secure service is about all I can come up with. This works provided you know who you are going to talk to and don't suddenly run out of "pad". Sounds like an awful business model. I'm sure some consultancy could sell it though.

Post-quantum crypto already exists afaik, the only issue is performance and key sizes (I guess this supposes the of quantum difficulty of certain problems).

It's not enough to have an algorithm. You need to get down to "what do these bytes mean" and "what exactly do I do with them" and have that be implemented. It's a considerably more painful process than you might think if you haven't been exposed to IETF things.

One time pads offer zero integrity/authentication. They are "malleable".

One time pads are not secure against "beyond-time" tactics or attacks.

Also, all alphanumeric combinations have been generated.

Fax machine

Several years ago, I was asked to intervene in an argument with a institution handling extremely sensitive information that needed to be transmitted en masse.

The receiving party received the data on physical media in the mail, but refused to access it, as the tool used to encrypt the data wasn't validated to FIPS 140-2 Level 2. (It was a reasonably good commercial product, and had Level 1 validation, and the folks negotiating this had no clue what that meant anyway) Why did that matter? Who the hell knows.

Their counter proposal was that something like 2,000 pages of whatever would be securely transmitted via Fax.

The punchline is that the stuff ended up getting re-shipped in paper form via Fedex Same-Day, securely nestled in a big pelican case secured with zip ties and a $30 padlock. Everyone shook their heads, except for the poor secretary facing sending 2,000 pages through a fax machine :)

Most credit card transactions are atill point of sale which usually uses symmetric encryption so quantum computing doesn't play a role.

Also if tomorrow some one makes a quantum computer which can say break 2048bit RSA easily it won't break the world.

A state actor with a trillion dollar machine won't care about your credit card. And this won't change quickly quantum computing will be very expensive for decades to come.

And moving to symmetric encryption with key exchange instead of classical PKI is always an option.

As a general rule using anything but conventional encryption is a sure way of having your encryption broken unless you are a world grade cryptographer with 50 world grade friends that can audit your system.

I originally just told clients worried about this to use a split signature between a top classical one, NTRU, and McEliece. Was always interested in the Merkle Signatures, though, thinking they could be improved. To my delight, there's been quite a bit of progress there including unlimited signatures. I want more peer review before widespread deployment of them, though.

https://www.schneier.com/blog/archives/2015/03/friday_squid_...

My niche, high assurance, has seen a lot of use of old, Merkle trees for memory encryption and obfuscation. A few examples.

https://www.schneier.com/blog/archives/2014/06/friday_squid_...

Note: Merkle seems to be one of the under-appreciated cryptographers of history. His legacy might live on and get better than ever post-Quantum, though. ;)

Personally, I think this is another spot where a mini-Manhattan Project worth of brains should be put into. Specifically, finding more problems that can be turned into good, asymmetric crypto. I'm sure there's already a list of potential ones that a ridiculously hard to solve. Just need bright people thinking hard on how to leverage them for key exchange at the least.

No need for an algorithm when using Steganography and Deniable Cryptography. A lot of the quantum-breakable debate pretty much ends with those two. They are in-fact bulletproof and resistant to all attempts to uncover the message, if done right, of course.

https://en.wikipedia.org/wiki/Steganography

https://en.wikipedia.org/wiki/Deniable_encryption

> if done right, of course

That's a pretty big if.

Do you have any examples of steganography software tha you think does it right?

Thing is, all these cryptography will still be beaten by phishing attacks as long as we have humans as user and password field for authentication.

https://github.com/polysome/vane

This is really a misnomer and should be called "post-Shor cryptography".

Reply on news.ycombinator.com