Root Causes 114: Is Quantum Computing a Threat to SHA-2?

Hosted by

Tim Callan

Chief Compliance Officer

Jason Soroko

Fellow

Original broadcast date

August 21, 2020

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 SHA-2? 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.

Podcast Transcript

Lightly edited for flow and brevity.

Tim CallanSo, 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 Pre-imaging Attacks on SHA-2 and SHA-3. 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 SHA-2?

Jason SorokoI think we absolutely need to worry about SHA-2 but not necessarily because of quantum computing.

Tim CallanOk. 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 SorokoIf 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 CallanYeah 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 SorokoYes. 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 CallanSure. 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 SorokoCorrect, Tim. And that’s why there’s an enormous effort to come up with quantum-resistant 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 CallanA little aside here, I do want to get back to SHA-2, so, and it’s just a coincidence right. Like the fact that quantum computers are gonna break SHA-2 – - 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 SorokoFair 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 quantum-resistant 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 CallanYeah. 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 SorokoOh, 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 CallanSure. 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 SorokoRight.

Tim CallanThat makes great sense. But let’s get back to SHA-1. 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 SHA-1 isn’t it?

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

Tim CallanSure.

Jason SorokoWhich 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 CallanSure. Ok.

Jason SorokoAnd 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 CallanYeah, 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 SorokoThat’s a very important point, Tim. So in other words, the properties of hashing algorithms are that in order to reverse it, right, that one-way 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 CallanAnd this is true of all hashing algorithms? Not just SHA-2?

Jason SorokoWell, the thing is, what was the problem with SHA-1? 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 SHA-2 not necessarily because of quantum but because there may be some ah-ha moment down the road and there definitely have been some good attack modes that are more traditional against SHA-2, let’s say SHA-256 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 CallanRight. In which case quantum computers are neither here nor there, right?

Jason SorokoThat's right.

Tim CallanI 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 SorokoThat’s right, Tim. Because remember when we talked about SHA-1 deprecation one of the things we may not have highlighted enough but the amount of thinking that went into hey, you know, original SHA-1 failed spectacularly because of X, Y and Z in the math and a lot of that thinking went into SHA-2 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 high-level talk of what’s out there in the community. It is at the moment considered, you know, SHA-2, SHA-256, 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 CallanYeah. 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 ah-ha 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 SHA-2 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, SHA-2 and quantum computers?

Jason SorokoTim, 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 SHA-2 and thinking about hashing algorithms, that really is a different beast, Tim.

Tim CallanRight. 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 SorokoExactly Tim.

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

Stay informed with expert insights

Subscribe to Root Causes for engaging discussions on PKI, digital security, and best practices for protecting your organization's critical assets. Don’t miss an episode!