News for hackers. Stuff that matters.
Re:Experimenting with Post-Quantum Cryptography by bradleyjg on Thursday July 07, 2016 @01:32PM (#12050827)
As I understand it that the picture for symmetric encryption in a quantum computer world is still relatively rosy. The key strength of something like AES is halved, but with the important caveat that the difficulty is with respect to quantum operations rather than classical operations and there's no guarantee quantum computers will be able to scale as well over time as silicon has. The situation for asymmetric encryption is where the real potential trouble lies. Please correct me if I misunderstand the situation.
Re:Experimenting with Post-Quantum Cryptography by aparent on Thursday July 07, 2016 @01:54PM (#12050979)
You are mostly correct. In fact the key strength of something like AES is realistically not even going to be reduced by half. In terms of the query complexity (the number of calls to AES that are needed) using Grover's algorithm the key strength is half what it would be with classical brute force. In practice though these queries must be implemented as quantum circuits and run a on quantum computer which adds a pretty large overhead.

This article is about the implementation of an asymmetric protocol based on the RLWE (https://en.wikipedia.org/wiki/Ring_Learning_with_Errors) problem.

Re:Experimenting with Post-Quantum Cryptography by aruss on Thursday July 07, 2016 @02:25PM (#12051179)
That's right, symmetric encryption is fine. You're also right that protocols that rely on factoring or discrete log (more generally, any hidden subgroup problem) will be broken by quantum computers. However, this still means symmetric encryption is in trouble; namely in that we still need a post-quantum method for exchanging keys, otherwise symmetric ciphers will be virtually useless.
Re:Experimenting with Post-Quantum Cryptography by e12e on Friday July 08, 2016 @02:10AM (#12053836)
How about hashing - in particular wrt key derivation? Does anyone have some insight there? Is it likely passphrase+salt+stretching might be in danger from quantum attacks? (I also wonder if DNA/RNA based biologic computing (or computing inspired by biology) might somehow change things around in terms of guessing passwords or look for hash collision...)
Re:Experimenting with Post-Quantum Cryptography by indolering on Friday July 08, 2016 @10:07PM (#12059754)
Hashing is in a similar position in that we just need to increase the size. Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.
Re:Experimenting with Post-Quantum Cryptography by e12e on Saturday July 09, 2016 @02:08AM (#12060338)
> Hashing is in a similar position in that we just need to increase the size.

Size of hash, or number of iterations? Or either? And will it still be "convenient security" available for those that "only" have classical computers? (ie: is will be get away with "small" increases in size, and get to keep (some of) our current speed)?

> Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.

I didn't think otherwise. But they might be relevant to combinatorial problems, and so relevant to security?

Re:Experimenting with Post-Quantum Cryptography by naibafo on Friday July 08, 2016 @03:17AM (#12054014)
There are some quantum key distribution protocols[1], though they still have their faults.

[1](https://en.wikipedia.org/wiki/Quantum_key_distribution)

Re:Experimenting with Post-Quantum Cryptography by bradleyjg on Friday July 08, 2016 @06:19AM (#12054545)
Based on what I've read, QKD requires a out of band shared secret to authenticate and rule out an active man in the middle. Given that I don't see the point at all.
Re:Experimenting with Post-Quantum Cryptography by gfody on Thursday July 07, 2016 @01:42PM (#12050904)
I discovered NTRU while searching for a fast alternative to RSA for asymmetric encryption. It's said to be quantum resistant as well but I can only vouch for its speed (it is very fast and served my purpose perfectly).

https://github.com/NTRUOpenSourceProject/ntru-crypto

Re:Experimenting with Post-Quantum Cryptography by aseipp on Thursday July 07, 2016 @02:10PM (#12051096)
NTRU is patented though and requires you to use their GPL library for patent exemption, or have a paid license (as said in the project README). However, given that, there's also http://tbuktu.github.io/ntru/ as BSD, so I'm not sure how to square that with what the owners of NTRU publicly stated. Apparently the EU is also considering it for some sort of standardization?

Bernstein also recently released a paper on NTRU Prime which I just became aware of, although it makes no mention of the patent issue. https://ntruprime.cr.yp.to/ntruprime-20160511.pdf

In any case, it'd be interesting to get an answer on this, since NTRU has looked interesting for a long time, but the patents were pretty unfortunate.

Re:Experimenting with Post-Quantum Cryptography by eximius on Thursday July 07, 2016 @04:44PM (#12051956)
It is lattice based so the state of the art to attack it uses LLL lattice reduction, I believe. I wrote a python implementation of both and, with pypy, it is quite fast at encrypting and decrypting. The LLL reduction was rather slow, but impressive that it could be done within a few minutes for some low-rank lattices.
Re:Experimenting with Post-Quantum Cryptography by math_and_stuff on Friday July 08, 2016 @12:47AM (#12053606)
Alternating between tours of BKZ(50) and y-sparse enumeration is much stronger. I have some BSD-d C++ implementations here: https://github.com/elemental/Elemental/tree/master/include/E...
Re:Experimenting with Post-Quantum Cryptography by tptacek on Thursday July 07, 2016 @03:00PM (#12051418)
Are the TLS constructions they're using documented anywhere? Is this a combination of Ring-LWE and, say, ECC, in case there are as-yet-unknown implementation faults in Ring-LWE?
Re:Experimenting with Post-Quantum Cryptography by agl on Thursday July 07, 2016 @03:03PM (#12051438)
We haven't written a spec because we don't intend for this to be widespread. However, the spec would basically be: run both X25519 and NewHope concurrently, concatenate their outputs and feed that into the TLS KDF as normal.

It is indeed a combination of R-LWE and ECC because it doesn't yet seem reasonable to depend on R-LWE alone. Not only because of the possibility of implementation faults in NewHope, but also because of the possibility of significant crypto-analytic advances against R-LWE, even with classical computers.

Re:Experimenting with Post-Quantum Cryptography by NobleSir on Thursday July 07, 2016 @03:41PM (#12051633)
Maybe this is a naive question, not knowing chrome well, but is the source available? Would love to play around with this..
Re:Experimenting with Post-Quantum Cryptography by baby on Thursday July 07, 2016 @04:01PM (#12051746)
Re:Experimenting with Post-Quantum Cryptography by aseipp on Thursday July 07, 2016 @05:28PM (#12052191)
Re:Experimenting with Post-Quantum Cryptography by NobleSir on Thursday July 07, 2016 @06:05PM (#12052371)
cool, thanks
Re:Experimenting with Post-Quantum Cryptography by mkj on Thursday July 07, 2016 @09:49PM (#12053171)
Re:Experimenting with Post-Quantum Cryptography by DenisM on Thursday July 07, 2016 @02:39PM (#12051265)
a hypothetical, future quantum computer would be able to retrospectively decrypt any internet communication that was recorded today, and many types of information need to remain confidential for decades. Thus even the possibility of a future quantum computer is something that we should be thinking about today.

Uh-oh.

Apparently not even Perfect Forward Secrecy can protect against this: https://en.wikipedia.org/wiki/Forward_secrecy#Attacks

Re:Experimenting with Post-Quantum Cryptography by epaulson on Thursday July 07, 2016 @06:32PM (#12052504)
Are any of these algorithms suited for PGP signing replacements?

I'm interested in being able to make long term claims based on web-of-trust models, and I've been nervous about basing it around RSA/DSA key pairs.

In that sort of world, what do the keys actually look like? Is it comparable to being able to distribute a single public root key?

Re:Experimenting with Post-Quantum Cryptography by hannob on Thursday July 07, 2016 @06:42PM (#12052557)
you may want to have a look at sphincs. its security is based on hash-functions, therefore unlike most other postquantum schemes it can be considered very reliable (good hash functions are a solved problem these days). Downside: signatures are big (~40k). For TLS this is unworkable, for a PGP-like system this is doable. https://sphincs.cr.yp.to/
Re:Experimenting with Post-Quantum Cryptography by zmanian on Thursday July 07, 2016 @08:00PM (#12052837)
We do not currently have good options for small Post Quantum signatures.

Hash Based signatures in a web of trust would result in enormous amounts of signature data for each public key.

A stateful hash based signing protocol like XMSS might be more suitable.

Hopefully a Post Quantum small signature alternative appears.

Re:Experimenting with Post-Quantum Cryptography by DyslexicAtheist on Thursday July 07, 2016 @06:27PM (#12052481)
very good talk by Daniel J Bernstein on PQC Hacks at the last 32C3 (certainly separating reality/fiction and one of the best talks I have seen on the subject):

- https://www.youtube.com/watch?v=6XeBvdm8vao

Re:Experimenting with Post-Quantum Cryptography by indolering on Thursday July 07, 2016 @06:50PM (#12052601)
We need a lot more money being poured into PQC. The key sizes are enormous: ECC requires 256 bits and these new schemes range up to 10KB. Say goodbye to single packet key exchanges.
Re:Experimenting with Post-Quantum Cryptography by Poorboyrise on Saturday July 09, 2016 @07:26AM (#12060971)
[weekend-senility.Modus:On] anectodical ?

um... when actual information must be _matched_

via "0" and "1" harrumph's principles... eerie ahem...

and the lever is relativeness... zzz... eh... using

stochastical methods to...zzzz ...strategy... zzz

[slept away]

Re:Experimenting with Post-Quantum Cryptography by theandrewbailey on Thursday July 07, 2016 @12:14PM (#12050235)
Re:Experimenting with Post-Quantum Cryptography by Trufa on Thursday July 07, 2016 @01:29PM (#12050808)
> We explicitly do not wish to make our selected post-quantum algorithm a de-facto standard

Like so many other things in computer science history, that seems like a great way to make it the de-facto standard.

Re:Experimenting with Post-Quantum Cryptography by Frank2312 on Thursday July 07, 2016 @01:44PM (#12050921)
If Google manages to prove it works and there are no better alternatives later on, then it will probably become the de-facto standard.

However, the second condition seems to not be met if Google is right, because they mention there are promising papers published.

­>Since we selected New Hope, we've noted two promising papers in this space, which are welcome.

Re:Experimenting with Post-Quantum Cryptography by baby on Thursday July 07, 2016 @04:03PM (#12051759)
There is also the fact that "as of now" efficient quantum computers capable to break our crypto is fiction.
Re:Experimenting with Post-Quantum Cryptography by serendipitous on Friday July 08, 2016 @05:53AM (#12054474)
Yes, but if you want your sessions that are captured today to remain confidential when quantum computers do become reality then you need to use post-quantum key exchange methods today.
Re:Experimenting with Post-Quantum Cryptography by Retr0spectrum on Thursday July 07, 2016 @01:55PM (#12050994)
Could someone replace the link with the non-mobile version?

https://security.googleblog.com/2016/07/experimenting-with-p...

Re:Experimenting with Post-Quantum Cryptography by sctb on Thursday July 07, 2016 @05:26PM (#12052180)
Thanks! We've updated the link.
Re:Experimenting with Post-Quantum Cryptography by bognition on Thursday July 07, 2016 @03:47PM (#12051664)
just remove ?m=1 from the end of the url
Re:Experimenting with Post-Quantum Cryptography by Retr0spectrum on Thursday July 07, 2016 @03:52PM (#12051687)
If 1000 people need to do that, the few seconds it takes quickly adds up.

It would be much easier if the original link was changed.

Re:Experimenting with Post-Quantum Cryptography by hackaflocka on Thursday July 07, 2016 @01:56PM (#12050999)
Upvote for hearing "post-quantum" for the first time in my life.

I suspect Deepak Chopra is going to appropriate it soon enough.

Re:Experimenting with Post-Quantum Cryptography by smartbit on Thursday July 07, 2016 @05:42PM (#12052260)
Tanja Lange [0] did a talk om post-quantumcrypto @ 32c3 https://media.ccc.de/v/32c3-7210-pqchacks. Last week she organised a 1 day workshop in Utrecht [1]

[0] http://www.hyperelliptic.org/tanja/ [1] https://pqcrypto.eu.org/mini.html

Re:Experimenting with Post-Quantum Cryptography by andrewclunn on Thursday July 07, 2016 @03:01PM (#12051426)
When you realize that your soul is already entangled with existence on a quantum level, your consciousness can achieve post-quantum awareness...
Re:Experimenting with Post-Quantum Cryptography by hackaflocka on Thursday July 07, 2016 @04:12PM (#12051807)
I would have lent a pithy rejoinder, but the I don't want to incur further wrath of the down-voters.