With the National Institute of Standards and Technology (NIST) set to publish the first Post Quantum Cryptography (PQC) Standards in a few weeks, attention is shifting to how to put the new quantum-resistant algorithms into practice. Indeed, the number of companies with practices to help others implement PQC is mushrooming and contains familiar (IBM, Deloitte, et al.) and unfamiliar names (QuSecure, SandboxAQ, etc.).
The Migration to Post-Quantum Cryptography project, being run out of NISTs National Cybersecurity Center of Excellence (NCCoE), is running at full-tilt and includes on the order of 40 commercial participants.
In its own words, The project will engage industry in demonstrating use of automated discovery tools to identify all instances of public-key algorithm use in an example network infrastructures computer and communications hardware, operating systems, application programs, communications protocols, key infrastructures, and access control mechanisms. The algorithm employed and its purpose would be identified for each affected infrastructure component.
Getting to that goal remains a WIP that started with NISTs PQC program in 2016. NIST scientist Dustin Moody leads the PQC project and talked with HPCwire about the need to take post quantum cryptography seriously now, not later.
The United States government is mandating their agencies to it, but industry as well as going to need to be doing this migration. The migration is not going to be easy [and] its not going to be pain free, said Moody, whose Ph.D. specialized in elliptic curves, a commonly used base for encryption. Very often, youre going to need to use sophisticated tools that are being developed to assist with that. Also talk to your vendors, your CIOs, your CEOs to make sure theyre aware and that theyre planning for budgets to do this. Just because a quantum computer [able to decrypt] isnt going to be built for, who knows, maybe 15 years, they may think I can just put this off, but understanding that threat is coming sooner than than you realize is important.
Estimates vary wildly around the size of the threat but perhaps 20 billion devices will need to be updated with PQC safeguarding. NIST has held four rounds of submissions and the first set of standards will encompass algorithms selected the first three. These are the main weapons against quantum decryption attack. The next round seeks to provide alternatives and, in some instances, somewhat less burdensome computational characteristics.
The discussion with Moody was wide-ranging, if perhaps a little dry. He covers PQC strategy and progress and the need to monitor the constant flow of new quantum algorithms. Shors algorithm is the famous threat but others are percolating. He notes that many submitted algorithms broke down under testing but says not to make much of that as thats the nature of the standards development process. He talks about pursuing cryptoagility and offers a few broad tips on preparation.
Moody also touched on geopolitcal rivalries amid what has been a generally collaborative international effort.
There are some exceptions like China never trusting the United States. Theyre developing their own PQC standards. Theyre actually very, very similar to the algorithms [were using] but they were selected internally. Russia has been doing their own thing, they dont really communicate with the rest of the world very much. I dont have a lot of information on what theyre doing. China, even though they are doing their own standards, did have researchers participate in the process; they hosted one of the workshops in the field a few years back. So the community is small enough that people are very good at working together, even if sometimes the country will develop their own standards, said Moody.
How soon quantum computers will actually be able to decrypt current RSA codes is far from clear, but early confidence that would be many decades has diminished. If youre looking for a good primer on the PQS threat, he recommended the Quantum Treat Timeline Report released in December by the Global Risk Institute (GRI) as one (figures from its study below).
HPCwire: Lets talk a little bit about the threat. How big is it and when do we need to worry
Dustin Moody: Well, cryptographers have known for a few decades that if we are able to build a big enough quantum computer, it will threaten all of the public key crypto systems that which we use today. So its a its a serious threat. We dont know when a quantum computer would be built thats large enough to attack current levels of security. Theres been estimates of 10 to 15 years, but you know, nobody knows for certain. We have seen progress in companies building quantum computers systems from IBM and Google, for example, are getting larger and larger. So this is definitely a threat to take seriously, especially because you cant just wait until the quantum computer is built and then say now well worry about the problem. We need to solve this 10 to 15 years in advance to protect your information for a long time. Theres a threat of harvest-now-decrypt-later that helps you understand that.
HPCwire: Marco Pistoia, who leads quantum research for JPMorgan Chase, said hed seen a study suggesting as few as 1300 or so logical qubits might be able to break conventional RSA code, although it would take six months to do so. That was a year ago. It does seem like our ability to execute Shors algorithm on these systems is improving, not just the brute force, but our cleverness in getting the algorithm to run.
Dustin Moody: Yep, thats true. And itll take a lot of logical qubits. So were not there yet. But yeah, progress has been made. You have to solve the problem solved and migrate to new solutions before we ever get to that point,
HPCwire: We tend to focus on Shors algorithm because its a direct threat to the current encryption techniques. Are there others in the wings that we should be worried about?
Dustin Moody: Theres a large number of quantum algorithms that we are aware of, Shor being one of them, Grovers being another one that has an impact on cryptography. But theres plenty of other quantum algorithms that do interesting things. So whenever anyone is designing the crypto system, they have to take a look at all those and see if they look like they could attack the system in any way? Theres kind of a list of I dont know, maybe around 15 or so that potentially people have to kind of look at him and figure out, do I need to worry about these.
HPCwire: Does NIST have that list someplace?
Dustin Moody: There was a guy at NIST who kept up such a list. I think hes at Microsoft, now. Its been a little while, but he maintained something called the Quantum Algorithms Zoo.
HPCwire: Lets get back to the NIST effort to develop quantum-resistant algorithms. As I understand it, the process began being around 2016 has gone through this iterative process where you invite submissions of potential quantum resistant algorithms from the community, then test them and come up with some selections; there have been three rounds completed and in the process of becoming standards, with an ongoing fourth round. Walk me through the project and progress.
Dustin Moody: So these kinds of cryptographic competitions have been done in the past to select some of the algorithms that we use today. [So far] a widely used block cypher was selected through a competition. More recently a hash function. Back in 2016, we decided to do one of these [competitions] for new post quantum algorithms that we needed standards for. We let the community know about that. Theyre all excited and we got 82 submissions of which 69 met kind of the requirements that wed set out to be involved. Then we had a process that over six or seven years [during which] we evaluated them going through a period of rounds. In each round, we went further down to the most promising to advance the tons of work going on in there, both internally at NIST, and by the cryptographic community, doing research and benchmarks and experiments and everything.
The third round had seven finalists and eight alternate concluded in July of 2022, where we announced items that we would be standardizing as a result, that included one encryption algorithm and three signature algorithms. We did also keep a few encryption algorithms on into a fourth round for further study. They werent quite ready to be selected for standardization. That fourth round is still ongoing and will probably end as this fall, and well pick one or two of those to also standardize. Well have two or three encryption [methods] and three signatures as well.
HPCwire: It sounds like a relatively smooth process?
Dustin Moody: That process got a lot of attention from the community. A lot of the algorithms ended up being broken, some late in the process thats kind of the nature of how this thing works. Thats where we are now. Were just about done writing the standards for the first ones that we selected, our expected date is publishing them this summer. The fourth round will end this fall, and then well write standards for those that will take another year or two.
We also have ongoing work to select a few more digital signature algorithms as well. The reason for that is so many of the algorithms we selected are based on what are called lattices; theyre the most promising family, [with] good performance, good security. And for signatures, we had two based on lattices, and then one not based on lattices. The one that wasnt based on lattices its called SPHINCS+ turns out to be bigger and slower. So if applications needed to use it, it might not be ideal for them. We wanted to have a backup not based on lattices that could get used easily. Thats what this ongoing digital signature process is about [and] were encouraging researchers to try and design new solutions that are not based on lattices that are better performing.
HPCwire: When NIST assesses these algorithms, it must look to see how many computational resources are required to run them?
Dustin Moody: Theres specific evaluation criteria that we look at. Number one is security. Number two is performance. And number three is this laundry list of everything else. But we work internally at NIST, we have a team of experts and try to work with cryptography and industry experts around the world who are independently doing it. But sometimes were doing joint research with them in the field.
Security has a wide number of ways to look at it. Theres the theoretical security, where youre trying to create security proofs where youre trying to say, if you can break my crypto system, then you can break this hard mathematical problem. And we can give a proof for that and because that hard mathematical problem has been studied, that gives us a little bit more confidence. Then it gets complicated because were used to doing this with classical computers and looking at how they can attack things. But now we have to look at how can quantum computers attack things and they dont yet exist. We dont know their performance. capabilities. So we have to extrapolate and do the best that we can. But its all thrown into the mix.
Typically, you dont end up needing supercomputers. Youre able to analyze how long would the attacks take, how many resources they take, if you were to fully tried to break the security parameters at current levels. The parameters are chosen so that its [practically] infeasible to do so. You can figure out, if I were to break this, it would take, you know, 100 years, so theres no use in actually trying to do that unless you kind of find a breakthrough to find a different way. (See descriptive list of NIST strengths categories at end of article)
HPCwire: Do you test on todays NISQ (near-term intermediate scale quantum) computers?
Dustin Moody: Theyre too small right now to really have any impact in looking at how will a larger quantum computer fare against concrete parameters chosen at high enough security levels. So its more theoretical, when youre figuring out how much resources it would take.
HPCwire: So summarizing a little bit, you think in the fall youll finish this last fourth round. Those would all be candidates for standards, which then anyone could use for incorporation into encryption schemes that would be quantum computer resistant.
Dustin Moody: Thats correct. The main ones that we expect to use were already selected in our first batch. So those are kind of the primary ones, most people will use those. But we need to have some backups in case you know, someone comes up with a new breakthrough.
HPCwire: When you select them do you deliberately have a range in terms of computational requirements, knowing that not everyone is going to have supercomputers at their doorstep. Many organizations may need to use more modest resources when running these encryption codes. So people could pick and choose a little bit based on the computational requirements.
Dustin Moody: Yes, theres a range of security categories from one to five. Category Five has the highest security, but performance is impacted. So theres a trade off. We include parameters for categories one, three, a five so people can choose the one thats best suited for their needs.
HPCwire: Can you talk a little bit about the Migration to PQC project, which is also I believe in NIST initiative to develop a variety of tools for implementingPQC Whats your involvement? How is that going?
Dustin Moody: That project is being run by NISTs National Cybersecurity Center of Excellence (NCCoE). Im not one of the managers but I attend all the meetings and Im there to support what goes on. Theyve collaborated withI think the list is up 40 or 50 industry partners and the list is on their website. Its a really strong collaboration. A lot of these companies on their own would typically be competing with each but here, theyre all working for the common good of making the migration as smooth as possible, getting experience developing tools that people are going to need to do cryptographic inventories. Thats kind of one of the first steps that an organization is going to need to do. Trying to make sure everything will be interoperable. What lessons can we learn as we. Some people are further along than others and how can we share that information best? Its really good to have weekly calls, [and] we hold events from time to time. Mostly these industry collaborators are driving it and talking with each other and we just kind of organize them together and help them to keep moving.
HPCwire: Is there any effort to build best practices in this area? Something that that NIST and these collaborators from industry and academia and DOE and DOD could all provide? It would be perhaps have the NIST stamp of authority on best practices for implementing quantum resistant cryptography.
Dustin Moody: Well, the standards that my team is writing, and those are written by NIST and those are the algorithms that people will implement. Then theyll also then get tested and validated by some of our labs at NIST. The migration project is producing documents, in a series (NIST SP 1800-38A, NIST SP 1800-38B, NIST SP 1800-38C) and those are updated from time to time, where theyre sharing what theyve learned and putting best practice in this. They are NIST documents, written jointly with the NIST team and with these collaborators to share what theyve got so far.
HPCwire: What can the potential user community do to be involved? I realize the project is quite mature, its been around for a while, and youve got lots of people who whove been involved already. Are we at the stage where the main participants are working with each other and NIST in developing these algorithms, and its now a matter of sort of monitoring the tools that come out.
Dustin Moody: I would say every organization should be becoming educated on understanding the quantum threat, knowing whats going on with standardization, knowing that youre going to need to migrate, and what thats going to involve your organization. Its not going to be easy and pain free. So planning ahead, and all that. If they want to join that that collaboration (Migration to PQC), people are still joining from time to time and it is still open if they have something that theyve got to share. But for most organizations or groups, its going to be just trying to create your plan preparing for the migration. We want you to wait till the final standards are published, so youre not implementing the something thats 99% the final standard, we want you to wait until thats there, but you can prepare now.
HPCwire: When will they be final?
Dustin Moody: Of the four that we selected, three of them. We put out draft standards a year ago, got public feedback, and have been revising since. The final versions are going to be published this summer. We dont have an exact date, but it will, itll be this summer.
HPCwire: At that point, will a variety of requirements will come around using these algorithms, for example in the U.S. government and perhaps in industry requiring compliance?
Dustin Moody: Technically NIST isnt a regulatory agency. So yes, US government can. I think the OMB says that all agencies need to use our standards. So the federal government has to use the standards that we use for cryptography, but we know that a wider audience industry in the United States and globally tends to use the algorithms that we standardized as well.
HPCwire: Were in a world in which geopolitical tensions are real. Are we worried about rivals from China or Russia, or other competing nations not sharing their advances? Or is the cryptoanalyst community small enough that those kinds of things are not likely to happen because the people know each other?
Dustin Moody: There is a real geopolitical threat in terms of who gets the quantum computer quickest. If China develops that and theyre able to break into our cryptography, thats a thats a real threat. In terms of designing the algorithms and making the standards, its been a very cooperative effort internationally. Industry benefits when a lot of people are using the same algorithms all over the world. And weve seen other countries in global standards organizations say theyre going to use the algorithms that were involved in our process.
There are some exceptions like China never trusting the United States. Theyre developing their own PQC standards. Theyre actually very, very similar to the algorithms [were using] but they were selected internally. Russia has been doing their own thing, they dont really communicate with the rest of the world very much. I dont have a lot of information on what theyre doing. China, even though they are doing their own standards, did have researchers participate in the process; they hosted one of the workshops in the field a few years back. So the community is small enough that people are very good at working together, even if sometimes the country will develop their own standards.
HPCwire: How did you get involved in cryptography? What drew you into this field?
Dustin Moody: Well, I love math and the math I was studying has some applications in cryptography, specifically, something called elliptic curves, and theres crypto systems we use today that are based on the curve, which is this beautiful mathematical object that probably no one ever thought they would be of any use in the in the real world. But it turns out they are for cryptography. So thats kind of my hook into cryptography.
I ended up at NIST because NIST has elliptic curve cryptography standards. I didnt know anything about post quantum cryptography. Around 2014, my boss said, were going to put you in this project dealing with post quantum cryptography and I was like, Whats this? Ive no idea what this is. Within a couple of years, it kind of really took off and grew and has become this high priority for the United States government. Its been a kind of a fun journey to be on.
HPCwire: Will the PQC project just continue or will it wrap up at some point?
Dustin Moody: Well continue for a number of years. We still have the fourth round to finish. Were still doing this additional digital signature process, which will take several more years. But then again, every everything we do in the future needs to protect against quantum computers. So these initial standards will get published, theyll be done at some point, but all future cryptography standards will have to take the quantum threat into account. So its kind of built in that we have to keep going for the future.
HPCwire: When you talk to the vendor community, they all say, Encryption has been implemented in such a haphazard way across systems that its everywhere, and that in simply finding where it exists in all those things is difficult. The real goal, they argue, should be to move to a more modular predictable approach. Is there a way NIST can influence that? Or the selection of the algorithms can influence that?
Dustin Moody: Yes, and no. Its very tricky. That idea youre talking about, sometimes the word cryptoagility gets thrown out there in that direction. A lot of people are talking about, okay, were going to need to migrate these algorithms, this is an opportunity to redesign systems and protocols, maybe we can do it a little bit more intelligently than we did in the past. At the same time, its difficult to do that, because youve got so many interconnected pieces doing so many things. So its tricky to do, but we are encouraging people and having lots of conversations like with the migration and PQC project. Were encouraging people to think about this, to redesign systems and protocols when youre designing your applications. Knowing I need to transition to these algorithms, maybe I can redesign my system so that if I need to upgrade again, at some point, itll be much easier to do. I can keep track of where my cryptography is, what happens when Im using it, what information and protecting. I hope that well get some benefit out of this migration, but its, its certainly going to be very difficult, complicated and painful as well.
HPCwire: Do you have an off the top of your head checklist sort of five things you should be thinking about now to prepare for post quantum cryptography?
Dustin Moody: Id say number one, just know that the migration is coming. The United States government is mandating their agencies to it, but industry as well as going to need to be doing this migration. The migration is not going to be easy, its not going to be pain free. You should be educating yourself as to what PQC is, the whole quantum threat, and starting to figure out, where are you using cryptography, what information is protected with cryptography. As you noted, thats not as easy as it should be. Very often, youre going to need to use sophisticated tools that are being developed to assist with that. Also talk to your vendors, your CIOs, your CEOs to make sure theyre aware and that theyre planning for budgets to do this. Just because a quantum computer [able to decrypt] isnt going to be built for, who knows, maybe 15 years, they may think I can just put this off, but understanding that threat is coming sooner than than you realize is important.
HPCwire: Thank you for your time!
Strength Categories from NIST
In accordance with the second and third goals above (Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process), NIST will base its classification on the range of security strengths offered by the existing NIST standards in symmetric cryptography, which NIST expects to offer significant resistance to quantum cryptanalysis. In particular, NIST will define a separate category for each of the following security requirements (listed in order of increasing strength2 ):
1) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES-128)
2) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA-256/ SHA3-256)
3) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES-192)
4) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA-384/ SHA3-384)
5) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES-256)
Read the original post:
NIST Q&A: Getting Ready for the Post Quantum Cryptography Threat? You Should be. - HPCwire