Root Causes 114: Is Quantum Computing a Threat to SHA2?
Quantum computers' threat to standardized encryption algorithms RSA and ECC has been much discussed. But what about our hashing algorithms? Do quantum computers pose a similar threat to SHA2? Join our hosts as they discuss the difference between Shor's Algorithms and Grover's Algorithm, which applies to each part of cryptography, and how significant quantum computing will be for each.
 Original Broadcast Date: August 21, 2020
Episode Transcript
Lightly edited for flow and brevity.

Tim Callan
So, we talk a lot about quantum computers and the fact that they are set to render our common encryption algorithms, RSA, and ECC valueless and we need to get new encryption. We don’t talk so much about hashing algorithms. So, I’m going to pose the question to you today, and this is actually inspired by a paper that you and I recently discovered from a bunch of folks at the University of Waterloo, the name of which is Estimating the Cost of Generic Quantum Preimaging Attacks on SHA2 and SHA3. So, Jay, here’s the question. We talk a lot about quantum computers destroying ECC and RSA. Makes good sense. Do we also need to worry about SHA2?

Jason Soroko
I think we absolutely need to worry about SHA2 but not necessarily because of quantum computing.

Tim Callan
Ok. That’s a great answer. That’s a very provocative answer. Let’s unpack that. Let’s start with   I guess there’s two pieces to that. Why don’t we start with the quantum computing part of it. So why not quantum computing?

Jason Soroko
If you look at what quantum computing is doing with helping up the factorizing of solving prime numbers and solving against things like ECC or elliptic curve cryptography using specifically Shor’s algorithm. Quantum goes a long way to speeding up that process so that what used to take a traditional computer a lot of time a quantum computer can solve it in much less time given enough stable Qbits.

Tim Callan
Yeah and these words like a lot of time and much less time are really not doing it justice. We are talking about – and I don’t have it in front of me, but my recollection is it’s something in the ballpark of 10 or 12 orders of magnitude faster. So, like, something that would have taken thousands of years now takes minutes.

Jason Soroko
Yes. Or even a month, right? Which for very secure communications might not be sufficient. In other words, if it only took 30 days to break a certain amount of SSL stream for example, that was encrypted with ECC, that might be very detrimental to the people who are doing that communication. So it doesn’t have to be seconds. It can sometimes be, you know, at least within the order of magnitude of something reasonable. Within our lifetimes, for example.

Tim Callan
Sure. But the power of Shor’s algorithm is such that this isn’t something you can just solve by throwing a couple more bits in the end. Right? You don’t say, oh well, you know, everything got ten times faster so I’m gonna add three bits and I’m covered. Right? It’s much, much worse than that.

Jason Soroko
Correct, Tim. And that’s why there’s an enormous effort to come up with quantumresistant algorithms, which is something we’ve podcasted on in the past and we will again because the nature of the math, the nature of what quantum computers can and cannot do, a big chunk of what goes into making quantum resistance isn’t just throwing a lot more bits at it. It’s also creating something that’s fundamentally different in the map.

Tim Callan
A little aside here, I do want to get back to SHA2, so, and it’s just a coincidence right. Like the fact that quantum computers are gonna break SHA2 –  sorry, are gonna break ECC and RSA because of the underlying math assumptions that were made, if we had made different underlying math assumptions in the 1970s let’s say, we wouldn’t be having this conversation right now, right? It’s just how it turned out.

Jason Soroko
Fair enough, Tim. However, those algorithms were also chosen for the purposes of efficiency because if you take a look at the current stable, the short list of quantumresistant algorithms there’s been an awful lot of work done to try to speed them up because of the fact that some of them are not inherently quick. So therefore, there is probably reasons why we settled on RSA and ECC in the past.

Tim Callan
Yeah. And yet, probably with the amount of computing power and bandwidth we had in 1994 that was probably considerably more pressure on that than there is today.

Jason Soroko
Oh, I would say so, Tim. However, interestingly, enter the world of IoT and that’s why things like ECC are quite popular within that because it’s such an efficient algorithm.

Tim Callan
Sure. And yeah, you could see where that with your constrained devices, constrained compute, constrained storage, constrained bandwidth, all the sudden you are back to these same problems.

Jason Soroko
Right.

Tim Callan
That makes great sense. But let’s get back to SHA1. So, Shor’s algorithm is the reason that RSA and ECC are in such jeopardy. Now it’s a different situation though for hashing algorithms like SHA1 isn’t it?

Jason Soroko
That’s right, Tim, because if you want to break those hashing algorithms the term that comes up often is Grover’s algorithm.

Tim Callan
Sure.

Jason Soroko
Which is different than Shor’s algorithm. So, people who understand this at a very intimate level, right, that article out of University of Waterloo that you just brought up for example. A very, very thorough, and detailed examination of simply asking the question, would a quantum computer with a sufficient number of stable Qbits be able to with Grover’s algorithm, would that be of an advantage over traditional computing with Grover’s algorithm, for example?

Tim Callan
Sure. Ok.

Jason Soroko
And without getting into it way too much because that’s an enormous article and there’s a lot of really good thinking in there, there really was not a meaningful amount of advantage that a quantum computer happens to give.

Tim Callan
Yeah, and things I’ve read in other places, forgive me if I’m wrong, seem to suggest that you could use Grover’s algorithm to decrease in a quantum computing environment to decrease the time you need to break a popular hashing algorithm to maybe a quarter or an eighth or a tenth of what it is right now. But while that seems important, and it is, it’s not to the point where it’s any kind of problem.

Jason Soroko
That’s a very important point, Tim. So in other words, the properties of hashing algorithms are that in order to reverse it, right, that oneway hashing algorithm – in order to reverse it, it is really difficult and it’s difficult – the way that the math has been set, it’s difficult regardless of whether you have a quantum computer or not, it’s difficult even if you have Grover’s algorithm which is doing something very efficient within the breaking. The amount of time saved is much, much smaller compared to say Shor’s algorithm with quantum. In other words, hashing algorithms are very, very resistant.

Tim Callan
And this is true of all hashing algorithms? Not just SHA2?

Jason Soroko
Well, the thing is, what was the problem with SHA1? Right? What were the problem with some of these deprecated hashing algorithms and part of it was geez, there’s just not enough entropy going on but some of the other problems were, well, some of the math kind of broke down easily, right? And so therefore, this is why I alluded at the very top of the podcast, yes, we do have to worry about SHA2 not necessarily because of quantum but because there may be some ahha moment down the road and there definitely have been some good attack modes that are more traditional against SHA2, let’s say SHA256 as an example of it, that it may come from left field. It might not come from this quantum onslaught that we are continuously talking about. It may come from just some better math.

Tim Callan
Right. In which case quantum computers are neither here nor there, right?

Jason Soroko
That's right.

Tim Callan
I mean you could do the same attack. If this mathematical attack were to emerge you could do the same thing on a traditional computer cause the computing platform is not the issue, the math is the issue.

Jason Soroko
That’s right, Tim. Because remember when we talked about SHA1 deprecation one of the things we may not have highlighted enough but the amount of thinking that went into hey, you know, original SHA1 failed spectacularly because of X, Y and Z in the math and a lot of that thinking went into SHA2 and so therefore, that thinking is bearing it’s fruit. However, however, and the big however is, some people have stated that it might not have gone far enough. I mean this is all just extremely highlevel talk of what’s out there in the community. It is at the moment considered, you know, SHA2, SHA256, considered a very safe hashing algorithm, we use it every single day, you can hang your hat on it and not worry too much but suffice to say that there definitely are some people who are looking very intensively at what are the weaknesses of it and is there a silver bullet that might render it needing to be deprecated down the road.

Tim Callan
Yeah. And this is a bit of a conundrum, right, because on the one hand we recognize that in all walks of life you don’t know what you don’t know. Right? Until somebody has an ahha moment and thinks of a new thing nobody knows about that thing and perhaps somebody is smart with a chalkboard right now is figuring out how to break SHA2 and that could happen, right? At the same time you gotta get on with things so we have to have standards and we have to deploy this stuff very widely and ubiquitously and it has to work with our bandwidth and our computers and so as a consequence we need to make sure that we balance those two things.
So, before we break, any last thoughts on hashing, SHA2 and quantum computers?

Jason Soroko
Tim, it’s interesting how quantum computing has captured a lot of people’s imaginations. I think that it’s a valid question to start asking hey how this affects hashing algorithms. I think the important thing to note is that research in terms of future better hashing algorithms when things eventually get deprecated much further down the road, that’s happening but your hashing algorithms as of right now are, we’re feeling pretty good about it as say compared to RSA and ECC that we definitely know we need to build resistance in our encryption algorithms for the web and for a bunch of other things because quantum is coming and so the timeframe for that is a lot more clear but for those of you thinking about SHA2 and thinking about hashing algorithms, that really is a different beast, Tim.

Tim Callan
Right. So, in the world of crypto nothing is forever. However, RSA and ECC that’s the immediate problem. That’s the thing to focus on.

Jason Soroko
Exactly Tim.

Tim Callan
Exactly right. Great, Jay. Great conversation as always. Thank you, listeners. This has been Root Causes.