Preparing SQL Servers and Data for Quantum Computing

Problem

Just like advances in artificial intelligence, I have heard that quantum computing is going to be a disruptive technology for our future. For instance, there’s the concern that it’s going to break/crack a lot of network encryption and potentially data encryption. What’s going to be affected, how long do we have, and what do I (and my organization) need to do to prepare for it?

Solution

Quantum computing, when fully realized, will have a significant impact on encryption, specifically public-private key (or asymmetric key) encryption based on the RSA and elliptic curve cryptography (ECC) algorithms. At some point, these encryption algorithms will be considered “broken” because quantum computing will permit cracking the private keys, which is not possible with current computing today. Given that quantum computing is beginning to look like a when and not an if, it’s time to plan for a world which uses quantum safe (also called post-quantum) encryption.

Mosca’s Theorem and Timelines

How long do we have until we’re at risk? To answer this question, mathematician Michele Mosca proposed a simple equation dubbed the Mosca Theorem which helps an organization understand whether it is at risk (and when risk starts):

X + Y > Z

Where:

• X = how long data needs to be protected
• Y = how long before the organization will use quantum safe encryption
• Z = when quantum computing becomes available and cheap

Explanation

If X + Y is greater than Z, then the organization is at risk. Admittedly, Z is the current unknown. Current estimates indicate that Z may be as soon as 2032-33, with experts like Mosca predicting that we may first see quantum computing powerful enough to break RSA and ECC as early as 2031.

A typical question is, “If my organization is fully converted before 2032, is it still at risk?” Potentially yes because of the concept of “harvest now, decrypt later.” If an adversary/threat actor can capture encrypted data now (harvest now), and that data would still be valuable/valid once quantum computing becomes available and cheap enough (decrypt later), the organization is still at risk. For instance, consider the case when a threat actor is able to exfiltrate an encrypted database back-up in 2030. The data will still be valuable in 2033. If the threat actor is able to store and wait, that actor can cash in once the technology becomes available.

Alternatively, let’s say that quantum computing has been realized where RSA/ECC is broken and the threat actor is able to get into a system which has older backups that the organization has had to keep around for regulatory or operational reasons. If those older backups haven’t been encrypted with quantum safe algorithms and the data is still valuable, then the organization would be at risk for that possibility.

Shor’s Algorithm and Asymmetric/Certificate-based Encryption

Why do we think that quantum computing will break the encryption underpinning both secure network communications as well as data encryption itself? Another mathematician, Peter Shor, proposed an algorithm making use of quantum computing which computes the prime factors of incredibly large numbers exponentially faster than anything possible under current, classical, computing. Under classical computing, all the computing power in the world would take thousands of years to determine the prime factors, and that’s what makes the use of RSA and ECC algorithms secure so long as one protects the private key. RSA relies on the product of two incredibly large prime numbers and ECC relies on discrete logarithms, which also is solved by factoring the primes. Therefore, both are susceptible to Shor’s algorithm.

How does this impact Microsoft SQL Server? In SQL Server, the generally recommended process to encrypt data uses a chain of algorithms and keys like so:

Note the Asymmetric Algorithm in the middle of the chain. This could either be a certificate or an asymmetric key within SQL Server. This is the link in the chain that will be vulnerable to Shor’s Algorithm. If an adversary can crack it, then the adversary gets access to the key for the symmetric algorithm, and then they will be able to decrypt the data. Code wise, here’s an example of how we’d set up the encryption chain:

USE MyDatabase;
GO 
 
CREATE MASTER KEY ENCRYPTION BY PASSWORD= 'S*meStr*ngP4ssphr4se!';
GO
 
-- If we don't specify ENCRYPTION BY PASSWORD, this will default 
-- to encryption by the database master key
CREATE CERTIFICATE CertToEncrypt
   WITH SUBJECT = 'CertToEncryptSymmKey';  
GO  
 
CREATE SYMMETRIC KEY SymmKeyToEncryptData
    WITH ALGORITHM = AES_256  
    ENCRYPTION BY CERTIFICATE CertToEncrypt;  
GO  

How Do I Replace the Asymmetric Algorithm?

As of the writing of this article, there are no quantum safe algorithms within SQL Server at the asymmetric algorithm level. When it comes to encrypting the symmetric key, we have the following options:

• Certificate
• Asymmetric Key
• Symmetric Key
• Password

The Certificate and Asymmetric Key options are vulnerable, so that leaves us with encryption by symmetric key or password. Encrypting a symmetric key with another symmetric key doesn’t solve the problem because we must encrypt that symmetric key and face the same issue. That basically leaves us with using a password to encrypt the symmetric key. That’s doable, but it means the password will need to be secured and protected outside of SQL Server. Another option is to use quantum safe algorithms outside of SQL Server and simply use SQL Server as the data store for encrypted data.

The Use of Authenticators with Symmetric Keys

The function used to encrypt data via a symmetric key, ENCRYPTBYKEY(), does permit the addition of an “authenticator” to encrypt the data. This “authenticator” must be presented as a parameter in the DECRYPTBYKEY() function for the decryption to succeed.

Using an authenticator may slow down an adversary, especially if there is no indication within the database that there is an authenticator. The Microsoft recommendation if using an authenticator, though, is to use a column which stores a unique and unchanging value. Losing the authenticator means losing the ability to decrypt the data. Therefore, it makes sense from an operational perspective to provide this guidance.

The catch is that should the authenticator be something an adversary can figure out (such as an appropriately named column or using the last 4 digits of a credit card number as the authenticator for encrypting the whole credit card number), then the authenticator only slows down the adversary. The same is true if the size of the authenticator is sufficiently small that an attacker could brute force the decryption by looping through all possible authenticators.

Transparent Data Encryption (TDE)

Another area of concern is Transparent Data Encryption (TDE). A TDE-encrypted database and its backups are encrypted using the Database Encryption Key (DEK) and that key uses a symmetric algorithm. However, TDE follows the recommended encryption model, meaning the DEK is encrypted by a certificate. For instance, here is sample code to set up a database to be encrypted using TDE:

USE master;
GO
 
-- Creating a database master key in the master database
CREATE MASTER KEY ENCRYPTION BY PASSWORD= 'S*meStr*ngP4ssphr4se!';
GO
 
-- This certificate has to be in the master database
CREATE CERTIFICATE MyTDEServerCert
    WITH SUBJECT = 'My DEK Certificate for TDE';
GO
 
USE MyDatabaseToEncrypt;
GO
 
CREATE DATABASE ENCRYPTION KEY WITH ALGORITHM = AES_256
    ENCRYPTION BY SERVER CERTIFICATE MyTDEServerCert;
GO
 
ALTER DATABASE MyDatabaseToEncrypt
    SET ENCRYPTION ON;
GO

Given that the certificate is a part of the chain, just as it is for encrypting data within a table, we have the same weak link to attack in TDE.

Blockchain and SQL Server Ledger

With SQL Server 2022, Microsoft introduced a blockchain-based technology called SQL Server Ledger. While some blockchain solutions are vulnerable to quantum computing, SQL Server Ledger is not. SQL Server Ledger uses SHA-256, a hashing algorithm, for the heavy lifting. This is not vulnerable to Shor’s Algorithm.

How to Prepare for Quantum Computing

To properly prepare, an organization needs to determine its risk. Therefore, here is a high-level method to prepare for a quantum safe future:

1. Inventory data
2. Identify where RSA/ECC encryption is used (even if it’s embedded in a chain).
3. Determine the risk for each data set/type of data.
4. Prioritize converting based on risk.
5. Transition to quantum safe cryptography for each of those at-risk data sets.

If this looks like a typical high-level plan for adapting to any emerging, disruptive technology, it is. Addressing the risk quantum computing poses to encryption is about understanding exposure, prioritizing based on risk, determining appropriate solutions, and executing.

Next Steps

• Understand how to encrypt data within SQL Server using the traditional model.
• Know how to configure a database for transparent data encryption.
• Learn how to use Always Encrypted with SQL Server.
• Read Microsoft’s quantum safe future.

K. Brian Kelley

Brian Kelley is an author, columnist, Certified Information Systems Auditor (CISA), and former Microsoft Data Platform (SQL Server) MVP (2009-2016) focusing primarily on SQL Server and Windows security. Brian currently serves as a data architect as well as an independent infrastructure/security architect concentrating on Active Directory, SQL Server, and Windows Server. He has served in a myriad of other positions including senior database administrator, data warehouse architect, web developer, incident response team lead, and project manager. Brian has spoken at 24 Hours of PASS, IT/Dev Connections, SQLConnections, the Techno Security and Forensics Investigation Conference, the IT GRC Forum, SyntaxCon, and at various SQL Saturdays, Code Camps, and user groups.

• MSSQLTips Awards: Author of the Year Contender – 2015, 2017 | Champion (100+ tips) – 2014