s/cipher/hash/
While you can build a stream cipher out of a hash pretty easily, SHA is most certainly not a cipher, it is a cryptographic hash function. "Hash" is what the H stands for.
Although it's reasonable to assume that a world with real quantum computers will ruin traditional asymmetric encryption, perhaps surprisingly hash functions might survive. That's the conclusion of a group of boffins led by Matthew Amy of Canada's University of Waterloo, in a paper at the International Association of …
This post has been deleted by its author
Good encryption is actually not hard - no one is really going about breaking symmetric encryption, they steal the key instead or do some other attack (MITM, TEMPEST, exploiting sloppy plaintext management, long list). Key exchange is the hard part. This has been done to death on forums such as Bruce Schneieir's.
Security is always a tradeoff with convenience (and cost). Asymmetric key exchange is very convenient. The rest is left as an exercise for the student.
The thing is that if quantum decryption becomes real and viable (at the moment, it's just not), then quantum encryption is waiting in the wings anyway. Why worry about how the current algorithms might be obsoleted (like DES, etc.), just ensure you have a replacement you can move to when the inevitable happens instead. Then re-key, re-encrypt and you're good to go for another 10 years until the next flaw (and next algorithm that solves that flaw) appears.
Expecting ONE algorithm to stay around forever and be uncrackable is ridiculously naive. Public key encryption such as we use didn't even exist 100 years ago and in the meantime - apart from literally two or three of the very latest algorithms - everything along the way has been cracked, weakened beyond repair, or was just plain useless to start.
There is absolutely no reason to suggest that in the quantum world it will be any different, although a guarantee of message authenticity is slightly easier, yet still subject to human error - just as even Enigma was.
Every time you find a hole, or a new feature of maths/physics you can make use of, redesign, re-key, re-encrypt. In a thousand years, we'll still be doing exactly that.
@Lee D - Cryptography has been an arms race between the strength the of the encryption and means to break them. Combined with various mistakes and hardware limitations your observation that the current encryption methods will be obsolete in the a few years is spot on.
Also, people need to remember that encryption does not need to protect information forever but for a period long enough for it to become essentially useless. This is time period that can range from a few minutes or hours to a few years.
Why worry?
Because your encrypted data may already be out there. When quantum encryption arrives then sure you can re-encrypt the copy you have. But if someone else has a classically encrypted copy then it's too late for you to do anything about it. That's why you need to worry about quantum proofing your encryption n years ahead of the arrival of quantum decryption, where n is the length of time your data will remain valuable for.
Since quantum computers capable of beginning to attack hash algorithms like SHA-256 don't exist yet, why limit the potential to attack by quantum computers with today's restrictions?
The real question is: what qubit coherence duration is required to solve the problem? As I understand it, at the moment the coherence duration is of the order of milliseconds. What was assumed by the people offering their opinion in this article? If the coherence duration was increased to 1 second, would that do it? 10 seconds?
It seems to me, and I may be wrong, the claim that SHA-256 is quantum attack proof is based on assumptions that may be irrelevant tomorrow. One group in Australia is working on room temperature qubits based on topological properties of quantum states not physical properties like spin because the topological properties are more stable. If this, or other, research comes to fruition, doesn't that make the limitations asserted in the article irrelevant?
Exactly. In fact this was published just four days ago and claims coherence times of a second, with no physical reason it couldn't be indefinite: http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.117.160402.
Archiv version available here: https://arxiv.org/abs/1511.01971
...capable of attacking hash algorithms don't exist. There's no guarantee about what the NSA might have, or what IBM invented in their basement that they decided is too useful to let people know about. Or maybe don't have now but will in five years.
So probably better to stay out in front of this stuff, and give people time to adopt algorithms secure against quantum computing now.
" There's no guarantee about what the NSA might have, or what IBM invented in their basement that they decided is too useful to let people know about."
It is probably being powered by an internal combustion engine that runs on water that is also too important to let people know about as well.
DougS is correct. The NSA etc. are probably five to ten years ahead of what is publicly know. For example GCHQ had developed Public Key Encryption five to six years ahead of Diffie, Hellman et al. Who employs more maths Ph.D. than anyone else in the world? They don't do it for no reason...
Considering IBM used the word "magic" as password to their Pentium 100 MHz PS/2 Aptiva's zipped image back in the 90's, don't expect too much of them.
It took 2 hours on the Pentium 100 MHz itself to crack that. If they trusted on a 3rd party low-level encryption method, and used a dictionary word for password BACK THEN, what makes you think they grew any better?
"The real question is: what qubit coherence duration is required to solve the problem? As I understand it, at the moment the coherence duration is of the order of milliseconds. What was assumed by the people offering their opinion in this article? If the coherence duration was increased to 1 second, would that do it? 10 seconds?""
And almost immediately we have this news:
http://www.theregister.co.uk/2016/10/18/researchers_increase_qubit_stability_tenfold_by_dressing_them_with_em_field/
Well done "that man".
... both SHA-256 and SHA3-256 ...
Technically, that should be "SHA-2/256 and SHA-3/256".
The original Secure Hash Algorithm, now sometimes called SHA-0, was a 160-bit function. It was quickly found to be weak and corrected to give rise to SHA-1, which was also a 160-bit function.
SHA-2 is a family of hash functions introduced when it started to appear that attacks on SHA-1 would eventually render it too weak to recommend. SHA-2 is a family of hash functions based on 256-bit and 512-bit algorithms with the output possibly shortened to give hashes from 224 to 512 bits in length. SHA-2/256 refers to the 256-bit algorithm.
SHA-3 is a new and different family of hash functions, considered stronger than SHA-2 but also giving a range of hash values from 224 to 512 bits in length. SHA-3/256 refers to the 256-bit version of this newer algorithm.
Its not about hash collisions its about the limit of (say) language. You can 'decrypt' a message using a randomly produced incorrect key and get something that looks like real english far too many times to know if you've really cracked the message.
The only way to know is to nick the key!
Only for very very long keys. As the key is re-used, it is unlikely to keep generating normal-looking text unless it was the right key. But sure, for a block the size of the key length you can come up with a key to generate any text you want.
So maybe, for an alibi for the innocent, make sure your message is longer than the key length.
On the other hand, for an alibi for the guilty, make sure your message is shorter than the key length and after the key length pad out with gibberish.
Maybe even have a "wrong" key which reveals the right message + gibberish and the right key reveals an entire other message and no gibberish.
Disclaimer: I don't know what I'm talking about
Clearly quibit coherence time is a critical parameter here.
What happens if that increases 10x? 1000x? 1000 000x? And yes IIRC a small number of physical processes have improved by that much over their initial versions.
Now how many ASICs are you using? 1? A board full? A server room full?
It was only when the EFF developed a DES cracker ASIC and IIRC about 8 of them dropped the worst case crack time to less than 1/2 a week at 20MHz, when the NSA finally admitted a 50 bit cypher was insecure.
I don't think people should stop worrying just yet.
And that's before the kidnapping and wrench option is considered.
Hashes can be attached via Rainbow Tables. See this:
https://emn178.github.io/online-tools/sha3_512.html
Type in "password" it's the same each time, or some random thing. It's "fast" in a JavaScript implementation, which means it should be fast in a GPU or FPGA. I know that the hitting with a dictionary list will be "quick", but the brute force might be slower.
What about hash clashes?
Best is do some password scheme that encode the password with several interval methods. Yes it slows things down. Of course if the "hackers" get hold of the database and the source code which hashes/encrypts the password, it's only time to brute force it.