News for hackers. Stuff that matters.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by Nokinside on Wednesday December 27, 2017 @01:51PM (#16016952)
If you can tolerate ~1MB private keys, Classic McEliece is probably the best conservative and secure post-quantum option just now before others are analyzed more. It's old and proven.

>9 Advantages and limitations (2.B.6)

>The central advantage of this submission is security. See the design rationale.

>Regarding efficiency, the use of random-looking linear codes with no visible structure forces public-key sizes to be on the scale of a megabyte for quantitatively high security: the public key is a full (generator/parity-check) matrix. Key-generation software is also not very fast. Applications must continue using each public key for long enough to handle the costs of generating and distributing the key.

>There are, however, some compensating efficiency advantages. Encapsulation and decapsu- lation are reasonably fast in software, and impressively fast in hardware, due to the simple nature of the objects (binary vectors) and operations (such as binary matrix-vector multiplications). Key generation is also quite fast in hardware. The hardware speeds of key generation and decoding are already demonstrated by our FPGA implementation. Encapsulation takes only a single pass over a public key, allowing large public keys to be streamed through small coprocessors and small devices.

>Furthermore, the ciphertexts are unusually small for post-quantum cryptography: under 256 bytes for our suggested high-security parameter sets. This allows ciphertexts to fit comfortably inside single network packets. The small ciphertext size can be much more important for total traffic than the large key size, depending on the ratio between how often keys are sent and how often ciphertexts are sent. System parameters can be adjusted for even smaller ciphertexts.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by hackcasual on Wednesday December 27, 2017 @07:41PM (#16019390)
Can't really see standardization settling on something that requires ~1,000-10,000x overhead from its competitors. 1mb public keys would mean things like IoT devices and block chain type usages, not to mention local caching taking possibly gigabytes.

Hybrid secret-sharing schemes do a lot to mitigate both future quantum risk and present broken cipher system risk.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by bascule on Wednesday December 27, 2017 @11:15AM (#16015583)
One of them has already fallen victim to a key recovery attack:

https://twitter.com/yx7__/status/945283780851400704

Round2 (LWE-based) and SIKE (isogeny-based) are the particularly interesting ones to me. Both support comparatively small keys (~1kB), with Round2 seemingly winning on performance, but also patented.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by mort96 on Wednesday December 27, 2017 @11:54AM (#16015961)
I never understood how or why patenting math is a thing.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by garmaine on Wednesday December 27, 2017 @12:37PM (#16016382)
It is patenting the application of math.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by mort96 on Wednesday December 27, 2017 @02:34PM (#16017302)
How do you differentiate between math and the "application of math"?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by garmaine on Wednesday December 27, 2017 @02:46PM (#16017435)
You can't patent an S-box transform. You can patent using a specific S-box transform to encrypt / decrypt data. That's the justification at least.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by betterunix2 on Wednesday December 27, 2017 @03:19PM (#16017689)
More like you can patent math when it is applied via a computer. So you would not be violating the patent by evaluating the S-box with pen and paper.

It makes no particular sense, but the theory behind math patents being out of bounds is that math is a fact. Software patents, including crypto patents, do not "feel" like facts to most judges, even if they technically are (see: Curry-Howard Correspondence).

Re:NIST Post-Quantum Cryptography Round 1 Submissions by exabrial on Wednesday December 27, 2017 @12:01PM (#16016029)
I like to ask dumb questions... So here is one: Are forward secrecy guarantees made by TLS valid in a post-quantum world?

Specifically, say I connect via TLS to a server that uses FS and exchange some information that will be valuable in 150 years. If the entire conversation is recorded at the wire, does quantum computing break this promise? (or have I misunderstood FS completely?)

Re:NIST Post-Quantum Cryptography Round 1 Submissions by modalduality on Wednesday December 27, 2017 @12:11PM (#16016128)
In general forward security involves generating a new key for each conversation with Diffie-Hellman or similar.

According to https://crypto.stackexchange.com/questions/5610/diffie-hellm..., Diffie-Hellman is not post-quantum secure, but https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exch... is a DH alternative that is.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by jgrahamc on Wednesday December 27, 2017 @12:12PM (#16016142)
Which is partly why we wrote and open sourced a SIDH implementation in TLS 1.3: https://blog.cloudflare.com/sidh-go/
Re:NIST Post-Quantum Cryptography Round 1 Submissions by exabrial on Wednesday December 27, 2017 @02:06PM (#16017070)
I <3 cloudflare, you guys are awesome!
Re:NIST Post-Quantum Cryptography Round 1 Submissions by newman314 on Wednesday December 27, 2017 @07:07PM (#16019240)
Do you have any performance numbers for SIDH vs ECDHE?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by grittygrease on Sunday December 31, 2017 @01:09PM (#16041756)
Cloudflare has a Go implementation of SIDH with p751: https://blog.cloudflare.com/sidh-go/

Here’s an overview of the performance from a patch by Armando Faz Hernandez: https://github.com/cloudflare/p751sidh/pull/2

Re:NIST Post-Quantum Cryptography Round 1 Submissions by CiPHPerCoder on Wednesday December 27, 2017 @12:11PM (#16016137)
https://www.fredericjacobs.com/blog/2016/04/07/qc-axolotl/ might be a good place to start answering this question.

If you can break the ECDH, you can figure out the key that was calculated. However, if other unknown data (e.g. past ECDH outputs) is hashed together to generate the key (like Signal does, as a very rough description), it's only post-quantum secure if the adversary ever misses a single message.

Other than weird saved-by-the-bell corner cases, the answer is "No".

Re:NIST Post-Quantum Cryptography Round 1 Submissions by bascule on Wednesday December 27, 2017 @02:33PM (#16017299)
I wrote a blog post about this. tl;dr: no, not unless you were using PQ hard algorithms

https://tonyarcieri.com/imperfect-forward-secrecy-the-coming...

Re:NIST Post-Quantum Cryptography Round 1 Submissions by nokcha on Wednesday December 27, 2017 @12:15PM (#16016179)
>Are forward secrecy guarantees made by TLS valid in a post-quantum world?

No, forward secrecy doesn't apply if the underlying public-key cryptography gets broken (such as by a quantum computer).

Re:NIST Post-Quantum Cryptography Round 1 Submissions by late2part on Wednesday December 27, 2017 @11:40AM (#16015814)
I'm seriously considering moving to pre-shared keys. Vernor Vinge's books (_A Deepness In The Sky_, others) talk about how much of interstellar shipping is the secure transportation of random pre-shared keys.

Although I'm unfamiliar w/ anything more sophisticated than a password manager like 1Password and S/Key - I'd like to see if I could have a go with this for my personal kit.

Can anyone recommend keywords/papers that talk about pre-shared key authentication at automated scale?

Re:NIST Post-Quantum Cryptography Round 1 Submissions by CiPHPerCoder on Wednesday December 27, 2017 @12:07PM (#16016089)
PSK isn't really a good solution, mostly because of scaling problems.

Today, all you need is a 32-byte ECDH private key, and a corresponding 32-byte public key. To talk to any of the billions of devices on the Internet securely, all you need is their 32-byte public key, and some means to verify that it is authentic (i.e. certificate authorities + certificate transparency). With this information, you can calculate a shared secret (or use a sealing API given only their public key, if you really want).

Total local storage: PKI overhead plus your own keys, under a few megabytes.

Doing PSK at scale means storing billions of 32-byte binary strings. One for each participant you intend to communicate with. They must also do this for every possible device they wish to communicate with, otherwise others can just eavesdrop on their conversations if keys are reused.

You've turned an O(n) space problem into an O(n^2) space problem.

If your n is small, you might still be tempted to make the move, but it will quickly become unmanageable as n grows.

Furthermore, if a devices loses their key, you must:

1. Generate/share a new keypair with n devices (which at Internet scale is billions), and

2. Do so in a way that doesn't open the door for backdoors, which probably requires digital signatures and therefore you're not actually getting rid of public-key cryptography

I think at Internet scale, we're still years away from having reliable post-quantum cryptography to even recommend let alone adopt, but that's going to be the way to go. Something something baby and bathwater.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by colmmacc on Wednesday December 27, 2017 @02:09PM (#16017089)
Passwords are PSKs and are the overwhelming default authentication mechanism for Internet scale systems.

Storing, distributing, and synchronizing billions of small blobs is actually a solved problem and not that big a deal. I wouldn't be so quick to write it off, because it has a real, working, easily understood invalidation and revocation story, which PKI does not.

A system that combines asymmetric crypto public-private key pairs with the distributed-whitelist properties of simple passwords, by treating the public keys as PSKs, has a lot of compelling benefits.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by CiPHPerCoder on Wednesday December 27, 2017 @04:05PM (#16018027)
> Passwords are PSKs and are the overwhelming default authentication mechanism for Internet scale systems.

Not for HTTPS, which is what we're talking about.

For WPA2-PSK, okay, you have a small n, it might work.

For user authentication against a local database, you're not encrypting, you're using validating against a password hash and then elevating the user's privilege for the duration of their session. That's far removed from what we mean when we say PSK (pre-shared keys), where encryption is implied.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by late2part on Thursday December 28, 2017 @03:34PM (#16024691)
To be fair, that’s what you’re talking about. I am mostly talking about SSH access.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by tscs37 on Wednesday December 27, 2017 @04:30PM (#16018198)
Passwords are largely stored in servers with enough storage to deal with the users of them.

However, distributing a PSK to every device is not friendly. 10 Million Passwords will at minimum take about 80 MB, some phones and IoT devices have only ten times of that as permanent storage or less.

Passwords work mostly because the other side has the storage and cpu capacity to operate with them

Re:NIST Post-Quantum Cryptography Round 1 Submissions by IncRnd on Wednesday December 27, 2017 @02:31PM (#16017272)
Are you aware of what forms of asymmetric crypto are broken by quantum computing?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by staticassertion on Wednesday December 27, 2017 @01:18PM (#16016669)
That's not N^2 it's N*k where k is number of devices and is generally very low. Most people will have at most 3 or 4 devices. You could also have a single key and store it on a wearable device, like a phone or watch, and we're back down to a single key per person.

I think the bigger issue with PSK at scale is key generation and distribution.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by IncRnd on Wednesday December 27, 2017 @02:37PM (#16017343)
It's n^2 across all devices. You don't use the same key between two different pairs of parties.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by betterunix2 on Wednesday December 27, 2017 @03:24PM (#16017732)
In practice you would probably use something like Kerberos to avoid the quadratic overhead.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by IncRnd on Wednesday December 27, 2017 @05:56PM (#16018793)
As long as the AES key size is 256 and not one of the 128 versions.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by staticassertion on Wednesday December 27, 2017 @02:42PM (#16017391)
Ohh, I see what you're saying.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by dsr_ on Wednesday December 27, 2017 @01:41PM (#16016867)
Actually, he ships around giant blocks of random numbers in a k of n format to be reassembled as a one-time pad.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by late2part on Thursday December 28, 2017 @03:35PM (#16024697)
Thank you for elucidating
Re:NIST Post-Quantum Cryptography Round 1 Submissions by Klathmon on Wednesday December 27, 2017 @11:24AM (#16015662)
Does NIST require submissions to be free (as in open software)?

Or is this going to be a bunch of advertising for proprietary patented algorithms?

Re:NIST Post-Quantum Cryptography Round 1 Submissions by pkaye on Wednesday December 27, 2017 @12:14PM (#16016160)
You can read their Intellectual Property statements here. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Crypt.... They will allow patents but their goal seems to be a royalty-free implementation.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by IncRnd on Wednesday December 27, 2017 @02:24PM (#16017203)
This is to form PQC (post quantum crypto) algorithms driven by the industry. In practice, as long as quantum computers don't both work and become scalable in the interim, you have another 4 years to worry about recommendations.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by mulmen on Wednesday December 27, 2017 @04:06PM (#16018032)
That's not really true though is it? What about any of my data that is encrypted today with a non-PQC algorithm and has been intercepted? If quantum computers become functional and scalable while that data is still of value to me then I need to worry.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by IncRnd on Wednesday December 27, 2017 @05:50PM (#16018753)
Yes, it's true. I spoke about future pqc recommendations from NIST at a scheduled time. I never said there was nothing to worry about, but that NIST's future pqc recommendations don't need to be worried about today.

You are making a reference to something other than the pqc future recommendations from NIST. Of course, if the agility is low, requiring a large ramp up time, a company can turn to the CNSA values today.

As you point out, working scalability is the issue. Even when there is a computer than can run grover or schor over something, the number of qubits will be the issue.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by yalogin on Wednesday December 27, 2017 @03:26PM (#16017743)
Are there any blogs that talk about what’s required in a crypto algorithm to withstand quantum computing? Is a straightforward increasing the key size enough? Or are there new paradigms explored? Are these algorithms symmetric or asymmetric?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by betterunix2 on Wednesday December 27, 2017 @03:37PM (#16017826)
PQ crypto has to be secure against a scalable quantum computer i.e. one that can be increased to attack arbitrarily large keysizes. Building a quantum computer with enough qbits to attack RSA2048 is not a problem if there is no known way to increase the number of qbits to attack RSA3072 -- but if you can keep adding more qbits, then we need a post-quantum algorithm.

The interest in post-quantum crypto is mainly in public-key systems, because for symmetric key systems you can essentially double the key size to achieve the same security level. In other words, AES256 is as secure against a quantum computer as AES128 is against a classical computer. On the other hand, quantum algorithms break RSA and DLOG (include ECDLOG), so the research has been on new approaches to public key crypto that seem hard for quantum computers. For example, the Learning With Errors (LWE) problem:

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

Re:NIST Post-Quantum Cryptography Round 1 Submissions by yalogin on Wednesday December 27, 2017 @03:56PM (#16017964)
Interesting. But an ec 512 bit key has a theoretically same strength as an aes 256 bit key. How is aes able to withstand it when ec and rsa can’t?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by CiPHPerCoder on Wednesday December 27, 2017 @04:10PM (#16018065)
AES's security reduction in the quantum scenario comes from a sqrt(n) reduction in search time. It's an optimized brute force against the key.

ECC gets broken because there is a quantum algorithm that solves the Elliptic Curve Discrete Logarithm Problem much faster than sqrt(n).

Re:NIST Post-Quantum Cryptography Round 1 Submissions by yalogin on Wednesday December 27, 2017 @08:12PM (#16019532)
Thanks. Looks like I have a wrong understanding of quantum computing. I thought QC increases the computing power by a lot there by making it easier or practical to compute the discrete log. So are you saying that the QC paradigm lends itself to a different class of algorithms?
Re:NIST Post-Quantum Cryptography Round 1 Submissions by CiPHPerCoder on Wednesday December 27, 2017 @08:51PM (#16019711)
Yes, look up Shor's Algorithm and Grover's Algorithm.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by westurner on Tuesday January 02, 2018 @10:21AM (#16052295)
This paper lists a few of the practical concerns for quantum-resistant algos (and proposes an algo that wasn't submitted to NIST Post-Quantum Cryptography Round 1):

"Quantum attacks on Bitcoin, and how to protect against them" https://arxiv.org/abs/1710.10377 (~2027?)

A few Quantum Computing and Quantum Algorithm resources: https://news.ycombinator.com/item?id=16052193

Responsive HTML (arxiv-vanity/engrafo, PLoS,) or Markdown in a Jupyter notebook (stored in a Git repo with a tag and maybe a DOI from figshare or Zenodo) really would be far more useful than comparing LaTeX equations rendered into PDFs.

Re:NIST Post-Quantum Cryptography Round 1 Submissions by algorithmsRcool on Wednesday December 27, 2017 @11:12AM (#16015555)
This seems to have generated a lot of collaboration.

DJB is listed on 5 separate submissions.

Phillippe Gaborit is on 8!

Re:NIST Post-Quantum Cryptography Round 1 Submissions by maxharris on Wednesday December 27, 2017 @09:52PM (#16019971)
If I were you, I wouldn't be so quick to trust any cryptography standard set by a government agency. They have an obvious incentive to ensure that any standard that is eventually set be open to attack by whatever means the NSA has (or will have in the near future.)

So pay careful attention to things they reject, or things they modify!

I have no insider knowledge here. I'm just applying common sense...

Re:NIST Post-Quantum Cryptography Round 1 Submissions by Sami_Lehtinen on Wednesday December 27, 2017 @10:14AM (#16015146)
Re:NIST Post-Quantum Cryptography Round 1 Submissions by dang on Wednesday December 27, 2017 @03:13PM (#16017660)
I guess we'll leave this one up since that one didn't attract discussion while this one has.
Re:NIST Post-Quantum Cryptography Round 1 Submissions by AgentME on Wednesday December 27, 2017 @04:29PM (#16018186)
I sure hope we can get a post-quantum version of Dual_EC_DRBG from the trustworthy people at NIST. /s

Not that I especially think any of these algorithms are going to be backdoored (though I certainly hope they get extra scrutiny just in case). I'm mostly just disappointed that there aren't any real consequences for a group like NIST for rubber-stamping backdoored things.