State of Symmetric & Hash Algorithms after Quantum Computing

The recent trends in information technology and communications have emerged as one of the main technological pillars of the modern age. The importance of cryptography has gained importance due to the requirement of security services (confidentiality, integrity, authenticity, and non-repudiation) in data storage/transmission.

Quantum computing, first introduced as a concept in 1982, has now become a nightmare for the currently deployed cryptographic mechanism. Extensive research has been done on quantum platforms to resolve complex mathematical problems, which are intractable for traditional computing platforms. The formalization of such quantum computing platforms poses serious threats to the cryptographic algorithms. This article informs the reader about the implications/repercussions of quantum computing on the present cryptography in detail.

Types of Cryptographic Algorithms

Three categories of cryptographic algorithms exist based on the number of cryptographic keys required as input for the algorithm.

• No Key - Hash Functions
• One Key - Symmetric Algorithms
• Two Keys - Asymmetric Algorithms

Hash Algorithms

Hash algorithms transform a large random size input to a small fixed size output. The output calculated by the hash algorithm is referred to as a digest or hash value. Operation of the hash algorithms does not require any cryptographic key and securely operates in a one-way manner. The one-way process means that it is cryptographically and technically impossible to compute the input data from output data. There are two categories of hash algorithms based on their design:

• Hash algorithms based on Mathematical Problems: In the first category are those functions whose designs are based on a mathematical problem, and thus their security follows from rigorous mathematical proofs, complexity theory, and formal reduction. These functions are called Provably Secure Cryptographic Hash Functions. However, this does not mean that such a function could not be broken. Constructing them is very difficult, and only a few examples were introduced. Therefore, their practical use is limited.
• Hash Algorithms based on Confusion/Diffusion: In the second category are functions that are not based on mathematical problems, but on an ad hoc basis, where the bits of the message are mixed to produce the hash. They are then believed to be hard to break, but no such formal proof is given. Almost all widely spread hash functions fall in this category. Some of these functions are already broken and are no longer in use.

Symmetric Algorithms

Symmetric algorithms are also known as secret key algorithms that employ one single cryptographic key for encryption/decryption mechanisms. Only the sender and receiver know the symmetric key. The further categorization of symmetric algorithms includes:

• Block Algorithms:  A block algorithm breaks the input into fixed-size blocks and then process the crypto operations. Popular block algorithms are the Advanced Encryption Standard (AES) and the Data Encryption Standard (3DES).
• Stream Algorithms: Stream algorithms perform “bit-by-bit” crypto operations. The most commonly used stream algorithms are RC4, A5/1, A5/2, and Chameleon, etc.

Current Security of Symmetric & Hash Algorithms

The security of the symmetric and hash algorithms is based on the fact that the key range is extensive and a brute force attack (attempting all the possible/potential keys) is not possible because of limited computational power and time constraints.

The Advent of Quantum Computing

Quantum computers have threatened the cryptographic mechanisms behind the current secure communication standards and protocols because quantum computers can perform calculations/computations at a rate that cannot be achieved through conventional/traditional computing systems. Traditional computing systems are based on the vital blocks known as bits and can have only two states, 0 and 1. Quantum computing platforms are based on quantum bits, also known as qubits. Qubits can hold the state 0, 1, and both simultaneously. This property is known as superposition. The effect of quantum computing can be calculated in two directions:

• The solution of Complex/Hard problems: Due to the advantage of the superposition property, quantum computing platforms can solve hard and complex mathematical problems that are the security standpoints of various cryptographic algorithms.
• The exponential increase in Calculations: Some cryptographic algorithms, such as symmetric and hash are based on the fact that a brute-force attack is infeasible. Quantum computers can definitely affect these algorithms by exhaustively searching for all secret keys.

Quantum Platforms & Grover’s Algorithm

The main threat to the security of symmetric and hash algorithms is Grover’s algorithm. This algorithm utilizes the quantum computing platform to search through unsorted databases to find a particular entry in √N searches from an unsorted DB of N entries. Meanwhile, traditional computing platforms search for the same in N/2 searches. 

Threats to Symmetric Algorithms from Quantum Computing

The Grover’s algorithm implementation on quantum platforms poses a serious threat to symmetric key algorithms by accelerating the speed of an exhaustive key search attack or brute force attack on symmetric algorithms so that the cryptographic key length is reduced by 50%. For an n-bit symmetric cryptographic algorithm, 2n possible keys exist. For the 128-bit AES algorithm, the key range is 2128, which is unbreakable using current computing platforms. After the formalization of a quantum platform and the implementation of Grover’s algorithm, the AES 128-bit key size will be reduced to an insecure 64-bit equivalent key length just like the 64-bit DES algorithm. Luckily, AES supports two other key lengths, and the applications would have to switch to the 192-bit and 256-bit versions of AES algorithms.

Threats to Hash Algorithms from Quantum Computing

Hash algorithms will also suffer from Grover’s Algorithm because they produce a fixed-size output of any random-sized input. The augmented speed of Grover’s algorithm can be used to expedite the collision-attack, which means finding two inputs with the same output. Similarly, the implementation of quantum-based platforms will be a problem for the Hash algorithms. However, because SHA-2 (256-bits) and SHA-3 (384-bits) have quite longer outputs, they appear to remain quantum-resistant.