back to article SHA3-256 is quantum-proof, should last billions of years

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 …

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.

12
0
(Written by Reg staff)

Re: s/cipher/hash/

Headline fixed!

6
0
Pint

A watched pot never boils

So, it's unlikely to finish cracking before closing time. Best get to the pub now, then ;)

7
0

This post has been deleted by its author

Silver badge

Re: Hash functions

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.

8
1
Silver badge

Re: Hash functions

This doesn't solve hash collisions. You can't solve hash collisions.

No matter how you do it, mapping data of size > n into a space = n creates collisions.

This paper just illustrates that quantum computing doesn't completely obsolete current hash functions.

9
0
Silver badge
Joke

Re: Hash functions

"... or do some other attack..."

Kneecaps!

And I'm so glad that my password of **** is safe now. It's so nice that the plain text is transfered to the server, then hashed, and compared with the hash of the plain text on the server. So secure and efficient!

:p

7
0
Silver badge

Re: Hash functions

The problem they worry about is not the inevitable collisions in the mind bogglingly vast 2^256 numeric space of the hash function, it is the ease (or otherwise) of engineering such a collision so that you can fake a digital signature for nefarious purposes.

13
0
Alert

Re: Hash functions

Also, don't mistake this work as any sort of endorsement or proof of either algo.

It's an assessment of the hashes' vulnerability to theoretical quantum-assisted implementations of currently-publicly-known attacks. Nothing more.

6
0
Silver badge

Re: Hash functions

or do some other attack

Obligatory XKCD

7
0
Silver badge

Re: Hash functions

Every time someone brings up that XKCD, I have to bring up two possibilities: the masochist and the scaredycat. Masochists would welcome the wrench, scaredycats would faint just at the sight of it.

0
0
Silver badge

Re: Hash functions

> mapping data of size > n into a space = n creates collisions.

Formally known as the Pigeonhole Principle.

1
0
Silver badge

Re: Hash functions

> it is the ease (or otherwise) of engineering such a collision so that you can fake a digital signature for nefarious purposes.

Let's be honest here. Nefarious actors can just tell Wosign that they own github. No collisions necessary.

1
1
Silver badge

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.

12
1
Silver badge

@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.

2
0

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.

2
0
Silver badge

"The calculation still seems to be in the order of 10^29 years"

You see why that Utah data centre's needed? Although by then it might have grown to fill the Orion spiral arm of the Milky Way.

1
0

Turn that one on its head

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?

9
0

Re: Turn that one on its head

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

2
0
Silver badge

You mean PUBLICLY KNOWN quantum computers

...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.

0
0

Re: You mean PUBLICLY KNOWN quantum computers

" 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.

0
2
Silver badge

Re: Turn that one on its head

> If this, or other, research comes to fruition, doesn't that make the limitations asserted in the article irrelevant?

I wouldn't worry too much about our research coming to fruition. "Efficiency dividends" will ensure these sorts of projects get shelved.

0
0
Silver badge

Re: You mean PUBLICLY KNOWN quantum computers

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...

1
0
Pint

Re: Turn that one on its head

"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".

0
0
Anonymous Coward

Re: You mean PUBLICLY KNOWN quantum computers

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?

0
0
Silver badge

Solecism

... 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.

5
0
Silver badge

We passed the infinite monkey stage a long while ago

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!

0
2

Re: We passed the infinite monkey stage a long while ago

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

6
0
pxd

Re: We passed the infinite monkey stage a long while ago

Have an up-vote for your disclaimer; all too often true, so infrequently acknowledged. For the record, I suspect I know considerably less than you! pxd

3
0

Re: We passed the infinite monkey stage a long while ago

Unfortunately in this case it is about collisions, a hashing algorithm only needs to return a matching result (false or otherwise) to validate the password.

0
0
Silver badge
Pint

10^32 Years with some future quantum computer

Or three weeks with a PC... Because the crackers skip around and go in through an unintentional back door or unexpected side channel.

^- Lesson from history. It's been repeated ENDLESSLY.

1
1
Facepalm

And the two best known SHA-3/256 will still be

the hashes for "password" and "123456".

0
0
Thumb Up

Re: And the two best known SHA-3/256 will still be

But programmers will remember to salt them, of course, so "password" and "123456" will be completely secure!

0
0
Silver badge

Re: And the two best known SHA-3/256 will still be

But programmers will remember to salt them, of course

Mmmmm....I loves me some salted hash....

0
0

Good for beelions of years eh? Like my 640K RAM which I was told was all I'd ever need !!!

1
0
Silver badge

Beeelion-year encryption...

...and the password is on a post-it note on the monitor bezel.

3
0
Bronze badge

Grovers is about breaking the function, we don't need to do that, we all know the function, all we need is the key

Shor's algorithm will crack the keys, and that will make a mockery of Keccak (The SHA-3 algorithm)

0
0

So if my servers use the password twice to encrypt their data and the two passwords are pseudo-randomly arranged by a seeded number algorithm known only by a protected 2nd server. Then if the data is stolen, it'll be impossible to decrypt without the algorithm?

0
0

If you're so sure that this 2nd server is secure, just put the data there in plain text.

0
0
Gold badge
Unhappy

Provided their assumpions are correct.

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.

0
0

Rainbow Tables

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.

0
0
Silver badge

Re: Rainbow Tables

You can only use rainbow attacks on non salted hashed dya.

Hence the use of random salt.

0
0
Silver badge
Pint

The Coming of the Quantum Cats

..I read that book years ago :)

0
0

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Forums

Biting the hand that feeds IT © 1998–2018