Recently I had the opportunity to educate U.S. legislators on two topics that I'm concerned about: the vulnerability of our encrypted data to - eventually - being cracked by quantum algorithms and why that poses a risk today, and the lack of resiliency in the U.S. Global Positioning System on which so much of our modern infrastructure now depends.
(I continue to correct and amend this article as new information comes to light.)
IEEE-USA Congressional Visits Day
The past few days I've been doing a lot of talking to people - for just a few minutes at a time - about two topics of personal concern: post-quantum cryptography, and GPS resiliency. This was part of IEEE-USA's 2022 Congressional Visits Day. IEEE is the Institute for Electrical and Electronics Engineers, an international professional society to which I belong.
For the CVD, the U.S. arm of IEEE recruits and trains volunteers from its members in congressional districts in every state to meet with legislative aids/assistants (LAs) and other staff of their elected officials in the U.S. Senate and House of Representatives. This year, I was one of these volunteers. At one time this was actually done in person; these days it's done with Zoom - apparently the preferred videoconferencing solution of the U.S. Congress - which is a lot more cost effective considering these meetings last at most half an hour. Be prepared, be brief, be polite, be respectful, be clear, talk fast, or don't talk at all.
Team Colorado (my term) consisted of myself and three other IEEE members from Congressional districts covering municipalities like Boulder, Aurora, Broomfield, Westminster, Arvada, all part of the Denver/Boulder metro area. (IEEE has over 4000 members in Colorado alone, and over 500 in the Congressional district in which I live, CO-7; I live in Arvada, and have worked in Boulder, Westminster, and Broomfield.) All of the teams took more than three hours of Zoom-based training and practice from IEEE-USA's Director of Government Relations, with the assistance of a consulting firm that specializes in helping to plan, schedule, and manage activities just like this.
To be clear, this isn't lobbying. On each team were voting constituents of senators and representatives with whose staff we were meeting. For sure, IEEE-USA hopes at least some of us choose to promote the bills and agendas which which the organization is concerned, like the CHIPS Act, which would promote the rehoming of chip manufacturing back to the United States, and they were careful to let us know what those bills and agendas were. But we're encouraged to talk about whatever we are concerned about (and, hopefully, something our elected officials can do something about), as long as we can do so in just a few short minutes.
After soliciting suggestions from several of my clients and former colleagues in the Boulder, Westminster, and Broomfield areas, post-quantum cryptography and GPS resiliency are the two topics on which I chose to spend my speaking time. Since the President's budget is just now being sent to Congress for debate and compromise, this is an excellent time for such discussions to take place (which I am sure was no accident of scheduling).
Much of my concern has to do with the pressure the currently high rate of inflation has on the actual spending power of those budget dollars. Budget numbers may seem like increases when compared to last year, but are in fact decreases when the effect of inflation is taken into account. This will create incentives to delay or even cancel projects and activities that may seem to be addressing very long term concerns (long term being anything longer than of a term of office), or even that are just hard to understand. Fortunately, explaining stuff is part of my job.
Ultimately Team Colorado met for a half hour each - an extraordinarily generous amount of time, given these people's schedules - with aids and staffers from the offices of
- Senator John Hickenlooper (CO-S),
- Senator Michael Bennet (CO-S),
- Representative Edwin Perlmutter (CO-07, which includes Arvada and Westminster),
- Representative Jason Crow (CO-06, which includes Aurora), and
- Representative Joe Neguse (CO-02, which includes Boulder and Broomfield).
(Rep. Perlmutter is my representative, and I was delighted to meet him in person one day a few years ago as I was doing chores in my front yard and he was canvassing my semi-rural neighborhood.)
Here, in a more verbose form, is what I talked about.
Post-Quantum Cryptography
For sure, this sounds like an extraordinarily esoteric topic. It doesn't help that much of what we hear and read about quantum computing is just hype. Unless there are some unexpected breakthroughs (which is of course possible), we are a decade or maybe two from a quantum computer that isn't at best a research topic.
But once we do, it will be capable of breaking most of the encryption algorithms in common use today. This is because there is already a quantum-based algorithm - Shor's Algorithm - to factor very large numbers. Large number factorization is the basis for most modern encryption algorithms that use public and private keys. There is also a known quantum-based search algorithm - Grover's Algorithm - that can be used to break shared encryption keys.
Why might this be a near-term problem, if we're twenty years away from such a capability? It is believed that hackers are already breaking into commercial and government systems and stealing (I'm told the term of art is exfiltrating) sensitive encrypted data with long-term value, with the expectation that they will eventually be able to decrypt it. They are most likely state sponsored, for example by China, North Korea, Iran, and Russia, and are known as advanced persistent threats. Their sponsors are playing the long game.
The National Institute of Standards and Technology (NIST, part of the Department of Commerce) has already solicited candidates for quantum-resistant encryption algorithms, and the process of evaluating and winnowing down the candidates into just a few is now being done. The next step will be to have working reference implementations that can be tested, so that a handful can be blessed for use. Then to define these algorithms precisely into public standards. Then to implement these new standards into existing cryptographic software products. And finally - the big task - will be to convince everyone to migrate over to them, not just for data "in flight" or "on the wire" but for data "at rest" that has long term value. This could take years, since we're talking about huge existing repositories of stored data that could be compromised. (And it's already too late for the data that has already been exfiltrated, which I am told is the technical term of art).
New cryptographic algorithms are only as good as it takes for someone to find a way to crack them. This is a kind of arms race fought by mathematicians. Adopting quantum-resisted algorithms and migrating our data to them is a big job. The sooner we get started the better off we'll all be.
NIST has requested FY2023 budget to increase their investment in fundamental measurement, quantum science, and measurement dissemination portfolio by $15 million. Providing this budget item remains intact, I'm fairly confident that progress in this area will continue to be made.
Like any threat that is not well understood, this one has brought out a lot of folks claiming to have solved this problem. Some - maybe most - are charlatans, merely taking advantage of FUD: fear, uncertainty, and doubt. Not too long ago, one of my clients asked for my help in evaluating the claims of a start-up pushing its own proprietary cryptographic technology that it claimed to be quantum-resistant. I'll tell you the same thing I told them: don't buy into it. This area is the realm of Ph.D. mathematicians who specialized in it. If the vendor's claims are legitimate, they will submit their algorithm to peer review through the NIST process. Wait for an officially approved suite of rigorously evaluated and tested post-quantum cryptographic algorithms that have been put into a recognized standard and implemented in the widely used software packages. If you're going to have to go through this costly and time consuming encryption migration process, you want to make sure you are better off when you finish than when you started.
GPS Resiliency
I spent some of my brief allotted time talking about the fragility of the U.S. Global Positioning System (GPS) and how dependent the U.S. was on it for Positioning, Navigation, and Timing (PNT). Virtually every telecommunications technology we care about, from our mobile phones to the internet connections to our homes and workplaces, relies, directly or indirectly, on GPS as a precise timing reference. And precision agriculture depends on GPS, with differential corrections, as a geolocation reference with centimeter precision.
Short term outages - hours, days, maybe even weeks - which can be due to ground or space system failures, deliberate jamming, or sunspots (I personally have witnessed the effects of all of these on my own equipment), aren't a problem, as long as telecommunications providers continue to furnish their systems with highly precise holdover clocks - typically cesium or rubidium atomic clocks. Short term outages do, however, disrupt geolocation applications.
It's the long term stuff - over thirty days maybe - that I worry about. Russia and China have each demonstrated anti-satellite weapons. And it only takes one Mad Russian to decide to burn the world. A study sponsored by NIST estimates that after thirty days of GPS outage, the U.S. would be losing about US$1B a day in lost productivity and capability; far more if it occurred during planting season, such is the impact of geolocation technologies on precision agriculture.
I should also mention that the GPS constellation serves a dual purpose: the satellites also carry the space-based portion of the U.S. nuclear detonation detection system.
In 2017, Senator Ted Cruz (R-TX) sponsored Senate bill S.2220, "National Timing Resilience and Security Act of 2017", co-sponsored by Senator Edward J. Markey (D-MA).
"This bill requires the Department of Transportation to provide for the establishment, sustainment, and operation of a complement to and backup for the timing component of the Global Positioning System (GPS). (GPS satellites contain atomic clocks that provide precise time data and allow GPS receivers to synchronize to those clocks.) The system must: (1) reduce critical dependencies on the GPS network; (2) ensure the availability of uncorrupted and non-degraded timing signals for military and civilian users if GPS timing signals are corrupted or otherwise unavailable; and (3) be land-based, operational in 2 years, and capable of operation for 20 years."
President Donald Trump signed this act with its bi-partisan support into law in 2018. The DoT has provided a roadmap for this effort. The DoT FY 2023 "Budget Highlights" doesn't mention it as far as I can tell. Certainly it was not implemented during the two year deadline. (BTW, this is not the "Wide Area Augmentation System for GPS", which is the WAAS system that virtually all of our GPS systems already use, whether we know it or not.)
The RAND Corporation produced a pretty interesting book on the topic, Analyzing a More Resilient National Positioning, Navigation, and Timing Capability, under contract to the Department of Homeland Security; I bought a nice bound copy from Amazon, but the PDF is available online as well. I have come to agree with the authors of the book that GPS backup is a remarkably difficult problem to solve - well, not technically, but economically and politically. It's hard to come up with a satisfactory solution that does not
- put the U.S. government in direct competition with the private sector;
- provide perverse incentives for the private sector to do something you don't want them to do (like eliminate their expensive holdover clocks from their telecommunications systems); or
- micromanage the precise solution in a kinda of classically inefficient Soviet way.
Some of GPS's strengths are also weaknesses: it's globally ubiquitous, it's wireless, it generally works well, and it's virtually free: there are no subscription fees, and the receivers are relatively inexpensive and simple to use. This creates a certain amount of dysfunction in the market for geolocation and precision timing services when you find yourself shopping for a commercial alternative. We are, in some respects, victims of the success of GPS.
I don't find much evidence of progress on this topic, other than the RAND study I cited. Bill S.2220, both explicitly and tangentially, refers to the old LORAN (LOng RAnge Navigation) system - a radio geolocation technology based on hyperbolic navigation that was developed around the close of WWII - by virtue of the fact that it talks about the U.S. Coast Guard, which is responsible for the old LORAN system, turning equipment over to the DoT. The RAND study finds enhanced LORAN (eLORAN) adequate for precision timing, but not for all of the precision geolocation applications for which GPS is used. For example, tests in the U.K. demonstrated that, with differential corrections, eLORAN was capable of a timing precision of 50ns, and a positioning precision of less than 10m. (Differential GPS is capable of positioning precision of a centimeter or less, making it useful for precision agriculture.)
(I have read suggestions of using the emerging 5G cellular system as a PNT system. But IMO that begs the question of how the 5G system derives its own timing. If the 5G base stations are disciplined to GPS, that isn't really helpful.)
Funding for the ground-based GPS resiliency effort described in S.2220 have not materialized. I suspect it's another example of an unfunded mandate. In a discussion on this topic in an internet forum, someone remarked that little progress on this is likely to be made unless a crisis occurs. I tend to agree. I am reduced to saying "I am really concerned about this."
It occurred to me that an interesting fictional - I hope - techno-thriller would feature Russia having clandestinely equipped all of their GLONASS satellites - a Global Navigation Satellite System (GNSS) similar in function to the U.S. GPS - with GPS jamming transmitters. Because of its low power (a mere 44.8 watts at an altitude of 20,200 kilometers/12,500 miles), and its use of code division multiplexing (a technology that makes extremely efficient use of precious radio frequency spectrum), GPS is trivially easy to jam. So equipped, Vladimir Putin could flip a switch to turn the unencrypted GLONASS signals off (while leaving its encrypted signals intact) and deny the use of GPS with jamming. (Commercial geolocation devices these days commonly use both GPS and GLONASS; the more expensive and later ones may also use the E.U. Galileo and PRC BeiDou GNSS satellite constellations as well.) This could deny the use of both GPS and GLONASS to commercial geolocation equipment.
Update 2022-04-16
This isn't really my area, but from a practical perspective - and given the lack of competency and relatively primitive equipment displayed by Russian forces in Ukraine - I can't see Russia destroying all thirty-one satellites in the GPS space segment using anti-satellite weapons, no matter what Vladimir Putin threatens. Russia could perhaps destroy enough to make GPS coverage intermittent, despite the U.S. having spare GPS satellites already in orbit. This would have little or no effect on the use of GPS as a precision timing and frequency reference, thanks to Stratum 0 holdover clocks used by telecom providers. It would however have a serious and long term impact on the use of GPS for geolocation: continuous positioning and navigation would no longer be possible.
The worse case scenario is the destruction of one or more GPS space vehicles in Medium Earth Orbit triggering the Kessler Syndrome: debris from the GPS satellite destroying other space assets in MEO, the debris from which causes yet more destruction of other assets also in MEO, in a cascading failure - including, possibly, destroying Russia's own GLONASS satellites. This might be enough of a deterrent to prevent Russia from using such a strategy.
I would think for sure using anti-satellite weapons against GPS space vehicles would be considered an act of war against the U.S. But GPS satellites may be disabled in other ways, some of which I've already described, such as being jammed from orbit. That would not be as escalating as destroying them, and could be maintained for a long enough time to impact their use as timing and frequency references.
Epilogue
I found the IEEE-USA CVD effort time consuming but enlightening. I fell down a rabbit hole or two while researching these topics to provide follow-up information to questions asked by the legislative aids, which included a legal counsel (i.e. lawyer), and a Brookings Institution fellow who specialized (coincidentally) in GPS and space policy. I would do it again. Thanks so much to the hard-working folks in Washington D.C. for their time.
Sources
116th Congress, "CHIPS for America Act", H.R. 7178, 2020-06-11, https://www.congress.gov/bill/116th-congress/house-bill/7178
The White House, "Biden-Harris Administration Bringing Semiconductor Manufacturing Back to America", fact sheet, 2022-01-21, https://www.whitehouse.gov/briefing-room/statements-releases/2022/01/21/fact-sheet-biden-harris-administration-bringing-semiconductor-manufacturing-back-to-america-2/
OMB, Budget of the U.S. Government Fiscal Year 2023, Office of Management and Budget, ISBN 978-0-16-095232-6, 2022, https://www.whitehouse.gov/wp-content/uploads/2022/03/budget_fy2023.pdf
Post-Quantum Cryptography
Patrick Howell O'Neill, "The quest for quantum-proof encryption just made a leap forward", MIT Technology Review, 2020-08-03, https://www.technologyreview.com/2020/08/03/1005891/search-for-quantum-proof-encryption-computing-nist/
Eric Hysen, "Preparing for Post-Quantum Cryptography", PD 140-15, Department of Homeland Security, 2021-09-17, https://www.dhs.gov/sites/default/files/publications/usm_quantum_memo_0.pdf
DHS, "Preparing for Post-Quantum Cryptography", infographic, Department of Homeland Security, 2021-10, https://www.dhs.gov/sites/default/files/publications/post-quantum_cryptography_infographic_october_2021_508.pdf
The President, "Improving the Nation's Cybersecurity", EO 14028, 2021-05-12, Federal Register 86.93, 2021-05-17, https://www.govinfo.gov/content/pkg/FR-2021-05-17/pdf/2021-10460.pdf
DHS/CISA, DoC/NIST, "Post-Quantum Cryptography Frequently Asked Questions", FAQ, Department of Homeland Security/Cybersecurity and Infrastructure Security Agency, Department of Commerce/National Institute of Standards and Technology, 2021-10, https://www.dhs.gov/sites/default/files/publications/post_quantum_cryptography_faq_3_seals_october_2021_508.pdf
Patrick Howell O'Neill, "The US is worried that hackers are stealing data today so quantum computers can crack it in a decade", MIT Technology Review, 2021-11-03, https://www.technologyreview.com/2021/11/03/1039171/hackers-quantum-computers-us-homeland-security-cryptography/
DHS, "Post-Quantum Cryptography", Department of Homeland Security, 2021-12-14, https://www.dhs.gov/quantum
Sankar Das Sarma, "Quantum computing has a hype problem", MIT Technology Review, 2022-03-28, https://www.technologyreview.com/2022/03/28/1048355/quantum-computing-has-a-hype-problem/
DoC/NIST/CSRC, "Post-Quantum Cryptography", Department of Commerce/National Institute of Standards and Technology/Computer Security Resource Center, 2022-03-10, https://csrc.nist.gov/Projects/post-quantum-cryptography
DoC/NIST, "Post-Quantum Cryptography Standardization", Department of Commerce/National Institute of Standards and Technology, 2022-03-10, https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
Doc/NIST, "FY 2023: Presidential Budget Request Summary", Department of Commerce/National Institute of Standards and Technology, 2022-03-31, https://www.nist.gov/director/congressional-and-legislative-affairs/nist-appropriations-summary-1/fy-2023-presidential
DoC/NIST, "Fiscal Year 2023 Budget Submission to Congress", National Technical Information Service, 2022-03, https://www.commerce.gov/sites/default/files/2022-03/FY2023-NIST-NTIS-Congressional-Budget-Submission.pdf
NCCoE, "Migration to Post-Quantum Cryptography", Department of Commerce/National Institute of Standards and Technology/National Cybersecurity Center of Excellence, https://www.nccoe.nist.gov/crypto-agility-considerations-migrating-post-quantum-cryptographic-algorithms
Wikipedia, "Shor's algorithm", 2022-04-09, https://en.wikipedia.org/wiki/Shor's_algorithm
Wikipedia, "Grover's algorithm", 2022-04-01, https://en.wikipedia.org/wiki/Grover's_algorithm
GPS Resiliency
115th Congress, "National Timing Resilience and Security Act of 2017", S.2220, https://www.congress.gov/bill/115th-congress/senate-bill/2220
Office of Senator Ted Cruz, "President Signs Sens. Cruz, Markey's Bipartisan National Timing Resilience and Security Act Into Law", PR, 2018-12-04, https://www.cruz.senate.gov/newsroom/press-releases/president-signs-sens-cruz-markey-and-rsquos-bipartisan-national-timing-resilience-and-security-act-into-law
Alan C. O'Conner et al., "Economic Benefits of the Global Positioning System (GPS)", RTI International, 0215471, 2019-06, https://www.nist.gov/system/files/documents/2020/02/06/gps_finalreport618.pdf
Michael P. Gallaher, "Economic Benefits of the Global Positioning System (GPS), RTI International, 2019-11-20, https://www.gps.gov/governance/advisory/meetings/2019-11/gallaher.pdf
The President, "Strengthening National Resilience Through Responsible Use of Positioning, Navigation, and Timing Services", EO 13905, 2020-02-12, Federal Register, 85.32, 2020-02-18, https://www.govinfo.gov/content/pkg/FR-2020-02-18/pdf/2020-03337.pdf
Dana A. Goward, "How America is losing the GPS war - and risking everything", Association of Old Crows webinar, Resilient Navigation and Timing Foundation, 2022-03-26, https://rntfnd.org/wp-content/uploads/AOC-Losing-GPS-War.pdf
Dana A. Goward, "How America is losing the GPS war - and risking everything", transcript, Resilient Navigation and Timing Foundation, 2022-03-26, https://rntfnd.org/wp-content/uploads/Goward-AOC-Text-March-2020.pdf
Editor, "Great Questions! Q&A from 'How America is losing the GPS war' (Part 1)", Resilient Navigation and Timing Foundation, 2022-03-29, https://rntfnd.org/2020/03/29/great-questions-q-a-from-how-america-is-losing-the-gps-war-part-1/
Editor, "Great Questions! Q&A from 'How America is losing the GPS war' (Part 2)", Resilient Navigation and Timing Foundation, 2022-03-31, https://rntfnd.org/2020/03/31/great-questions-q-a-from-how-america-is-losing-the-gps-war-part-2/
DHS, "Report on Positioning, Navigation, and Timing (PNT) Backup and Complementary Capabilities to the Global Positioning System (GPS)", Department of Homeland Security, 2020-04-08, https://www.cisa.gov/sites/default/files/publications/report-on-pnt-backup-complementary-capabilities-to-gps_508.pdf
DOT, "National Timing Resilience and Security Act: Roadmap to Implementation", Report to Congress, Department of Transportation, 2021-01, https://www.transportation.gov/sites/dot.gov/files/2021-01/NTRSA%20Report%20to%20Congress_Final_January%202021.pdf
Stefano Ruffini et al., "5G synchronization requirements and solutions", Ericsson Technology Review, #01-2021, pp. 2-13, 2021-01-13, https://www.ericsson.com/48e592/assets/local/reports-papers/ericsson-technology-review/docs/2021/5g-synchronization-requirements-and-solutions.pdf
Matteo Luccio, "Opposite and Complementary - eLORAN is Part of the Solution to GPS Vulnerability", GPS World, 32.11, pp. 24-27, 2021-11, https://cdn.coverstand.com/59713/726592/fb31a974139579735778a7f202a3dbfe67d57f63.1.pdf
Richard Mason et al., "Analyzing a More Resilient National Positioning, Navigation, and Timing Capability", Research Summary, Homeland Security Operational Analysis Center, RAND Corporation, RR2970, 2021, https://www.rand.org/content/dam/rand/pubs/research_reports/RR2900/RR2970/RAND_RR2970.summary.pdf
Richard Mason et al., "Analyzing a More Resilient National Positioning, Navigation, and Timing Capability", National Defense Authorization Act Fiscal Year 2017 Report to Congress: PNT Requirements, and Analysis of Alternatives, Homeland Security Operational Analysis Center, RAND Corporation, RR2970, 2021, https://www.rand.org/content/dam/rand/pubs/research_reports/RR2900/RR2970/RAND_RR2970.pdf
Richard Mason et al., Analyzing a More Resilient National Positioning, Navigation, and Timing Capability, RAND Corporation, 2021, https://amazon.com/dp/197740362X
Matteo Luccio, "10 Questions on eLoran", GPS World, 33.1, pp. 6-8, 2022-01, https://cdn.coverstand.com/59713/734537/8a8ce04baadba3d98c80aceae2e0c5011c4dc55c.2.pdf
Wikipedia, "Anti-satellite weapon", 2022-03-13, https://en.wikipedia.org/wiki/Anti-satellite_weapon
DoT, "U.S. Transportation Secretary Pete Buttigieg Announces the President’s Fiscal Year 2023 Budget for the U.S. Department of Transportation", Department of Transportation, 2022-03-28, https://www.transportation.gov/briefing-room/us-transportation-secretary-pete-buttigieg-announces-presidents-fiscal-year-2023
DoT, "Budget Highlights 2023", Department of Transportation, 2022, https://www.transportation.gov/sites/dot.gov/files/2022-03/Budget_Highlights_FY2023.pdf
Dana A. Goward, Rep. John Garamendi, "Putin is holding GPS hostage - Here's how to get it back", opinion, C4ISRNET, 2022-04-12, https://www.c4isrnet.com/opinion/2022/04/12/putin-is-holding-gps-hostage-heres-how-to-get-it-back/
Matteo Luccio, "Russia's Attack Raises Vulnerability Concerns", GPS World, 33.4, p. 6, 2022-04, https://cdn.coverstand.com/59713/744206/617d13bd681cf9f34129871033fa60662b9121e5.2.pdf
Alan Grant, Dana Goward, "Ten Answers About eLoran", GPS World, 33.4, pp. 28-33, 2022-04, https://cdn.coverstand.com/59713/744206/617d13bd681cf9f34129871033fa60662b9121e5.2.pdf
