Quantum Safe Cryptography Based on Hash Functions: A Survey

Quantum Safe Cryptography Based on Hash Functions: A Survey

Mateusz Zych

Master’s Thesis Autumn 2018

Abstract

The use of public key cryptosystems range from securely encrypting emails and files to creating digital signatures for non-repudiation. The security of public key cryp- tosystems is based on computationally "unsolvable" complex mathematical problems.

This tends to change with the introduction of quantum computers that undoubtedly pose a threat to the current schemes. In response to that extensive research has been conducted that resulted in several cryptosystems that are believed to be quantum resistant. This thesis presents a concise overview of multiple hash-based signature schemes and provides a comparative description and analysis of them. The compar- isons are based on different signature scheme properties, such as key sizes, signature sizes and security level provided. The proposed quantum resistant schemes are also compared to the standard schemes used today, such as RSA and ECDSA.

Acknowledgements

I would like to thank my supervisor, Leif Nilsen, for the help I got from him during the thesis. I have been fortunate to make many new friends during my time at the University of Oslo. There are too many to mention, you know who you are, and you people are great. Additionally, I would like to thank my family for believing in me during the tough time of writing this thesis. Finally, I would like to express a special appreciation to my Mom, who always encouraged me through the process and supported me with great conversations when there was nobody to respond to my queries.

Contents

List of Figures 6

List of Tables 7

I Introduction and Background 8

1 Introduction 9

1.1 Motivation . . . 9

1.2 Description of the problem . . . 10

1.3 Methodology . . . 11

1.4 Structure . . . 11

2 Theoretical background 12 2.1 Security Concepts . . . 12

2.1.1 Confidentiality . . . 13

2.1.2 Integrity . . . 13

2.1.3 Availability . . . 13

2.1.4 Accountability . . . 13

2.1.5 Non-Repudiation . . . 14

2.1.6 Identity and Access Management . . . 14

2.2 Conventional cryptography . . . 15

2.2.1 Cryptographic Notions . . . 15

2.2.2 Symmetric cryptography . . . 16

2.2.3 Asymmetric cryptography . . . 19

2.2.4 Hash functions . . . 26

2.2.5 Attacks on Hash Functions . . . 28

2.3 Digital signatures in current protocols . . . 32 2

2.3.1 PKI . . . 32

2.3.2 TLS . . . 34

2.3.3 IPsec . . . 34

2.3.4 DNSSEC . . . 36

2.3.5 S/MIME . . . 38

3 The Impact of Quantum Computing 39 3.1 Quantum Computing . . . 39

3.1.1 Quantum Phenomena . . . 39

3.1.2 Shor’s Algorithm . . . 40

3.1.3 Grover’s Algorithm . . . 41

3.1.4 Quantum Computing . . . 42

3.1.5 Challenges in Quantum Computing . . . 43

3.2 Consequences of quantum computing . . . 44

3.2.1 Symmetric cryptography . . . 45

3.2.2 Asymmetric cryptography . . . 46

3.2.3 Hash functions . . . 47

II Survey of Hash Based Signatures 48

4.1.1 Parameters and Key Generation . . . 50

4.1.2 Signing . . . 50

4.1.3 Verifying . . . 51

4.1.4 Security of L-OTS . . . 51

4.1.5 Reducing the Private Key Size . . . 52

4.2 Merkle One-Time Signature . . . 53

4.2.1 Parameters . . . 53

4.2.2 Signing . . . 53

4.2.3 Verifying . . . 54

4.2.4 Security . . . 54

4.2.5 Improvement of Merkle OTS . . . 55

4.3 Winternitz signature . . . 57

4.3.1 Winternitz parameter . . . 57

4.3.2 Key generation . . . 58

4.3.3 Signing . . . 59

4.3.4 Verifying . . . 61

4.3.5 Security of W-OTS . . . 62

4.4 Variants of Winternitz Signature Scheme . . . 63

4.4.1 W-OTS^{P RF} . . . 63

4.4.2 W-OTS⁺ . . . 66

4.4.3 WOTS-T . . . 69

4.4.4 LM-OTS . . . 71

4.4.5 WSS-N W-OTS Using Nonadjacent Forms . . . 73

5 Few Time Signatures 75 5.1 Bins and Balls . . . 75

5.1.1 Key Generation . . . 76

5.1.2 Signing . . . 77

5.1.3 Verifying . . . 77

5.1.4 Security . . . 78

5.2 Hash to Obtain Random Subset . . . 81

5.2.1 Key Generation . . . 81

5.2.2 Signing . . . 81

5.2.3 Verifying . . . 82

5.2.4 Security . . . 82

III Many Times Signatures 84

6.1.1 Reducing the Public Key Size . . . 85

6.1.2 Structure . . . 86

6.1.3 Key Generation . . . 86

6.1.4 Signing . . . 88

6.1.5 Verifying . . . 89

6.1.6 Security . . . 91

6.2 Making MSS More Practical . . . 91

6.2.1 Traversal algorithm . . . 91

6.2.2 CMSS . . . 92

6.2.3 GMSS . . . 93

6.2.4 Merkle Tree Traversal Revisited . . . 94

6.2.5 Reducing Security Assumptions in Merkle Trees . . . 94

6.3 XMSS Family . . . 95

6.3.1 XMSS . . . 95 4

6.3.2 XMSS⁺ . . . 96

6.3.3 XMSS^{M T} . . . 98

6.3.4 XMSS-T . . . 99

7 Stateless Signature Schemes 101 7.1 SPHINCS . . . 101

7.2 SPHINCS⁺ . . . 103

7.2.1 FORS . . . 103

7.3 Gravity-SPHINCS . . . 104

7.3.1 PORS . . . 105

8 Analysis and Discussion 107 8.1 Standardization of hash based signatures . . . 107

8.2 Stateful versus Stateless . . . 107

8.3 Comparison of Hash-based Signatures . . . 108

IV Summary 112

9.2 Further Work . . . 114

Bibliography 115

Appendix A 126

List of Figures

2.1 Example of classical symmetric cryptography [114]. . . 17

2.2 Presents AES Encryption in different modes [106]. . . 20

2.3 An overview of asymmetric cryptography [107]. . . 21

2.4 Presents 3 versions of X.509 certificate structure [109]. . . 32

2.5 The flow of getting an X.509 certificate in Public Key Infrastructure [108]. . . 33

2.6 TLS handshake protocol [103]. . . 35

2.7 AH and ESP presented in both transport and tunnel mode [14]. . . . 36

2.8 Presents a DNSSEC query to www.example.com . . . 37

4.1 Calculation of checksum in W-OTS, wherew= 3 andb_i’s are parts of the message digest to sign. . . 61

5.1 The probability of finding a signature when having x SEALs [88]. . . 79

6.1 Binary tree from Merkle signature scheme with height h= 3. . . 87

6.2 Authentication path and verification of signature from index i = 5 with tree height h= 3. . . 90

6.3 Structure of XMSS^{M T} many-time signature scheme [55]. . . 99

7.1 Structure of SPHINCS stateless many-time signature scheme [9]. . . . 102

7.2 Structure of FORS few-time signature scheme [8]. . . 104

7.3 Comparison of the structures of HORS and PORS few-time signature scheme [2]. . . 106

6

List of Tables

2.1 This table shows generic security for hash function in classical cryp- tography. . . 29 3.1 Result of x raised to the powers of the 4-qubit register values and

second results are remainders of dividing these numbers by 15. . . 41 3.2 Generic security for hash function in both classical and quantum world

[59]. . . 47 4.1 Dependence between w, private key elements and evaluations of F

when n= 256 . . . 59 5.1 Security parameters of BiBa signature scheme when t=1024 [88]. . . . 76 8.1 Comparison of hash-based signature schemes with current standards.

The sizes are provided in bytes. . . 110 8.2 Instances of SPHINCS⁺ providing 128-bit quantum security [8]. Pro-

vided values are the number of CPU cycles. . . 111 8.3 CPU cycles for Gravity-SPHINCS sub algorithms [2]. . . 111 8.4 Instances of XMSS^{M T} signature scheme. Size in bytes and times in

hash function iteration [51]. . . 111

Part I

Introduction and Background

8

Chapter 1 Introduction

1.1 Motivation

The advancements in technology and particularly in digital communications is one of the technological foundations of the modern society. Confidentiality, integrity, au- thenticity, and non-repudiation in data transmission and data storage are properties that have made cryptography an essential discipline within information technology.

In recent years, quantum computing has become attractive as a research topic due to the acceleration of technology. This development has led to the increased ex- posure of quantum computers, which make use of quantum physical phenomena to perform calculations. Two types of quantum computers exist are universal and non- universal. Their difference is that universal quantum computers are developed to perform any given task, whereas non-universal quantum computers are limited to a specific purpose.

Quantum computers pose a significant risk to both present public key algorithms (such as RSA, Diffie-Hellman, and DSA) and symmetric key algorithms (like 3DES, AES). Each year it seems that we are getting closer to create a fully operational universal quantum computer that can utilize strong quantum algorithms, such as Shor’s and Grover’s. In conventional cryptography the public key algorithms are used for key exchange and digital signatures. The consequence of the technological advancement is the absolute collapse of the present public key algorithms that are considered secure (e.g, RSA and Elliptic Curve Cryptosystems). Consequently, all protocols using either key exchange or digital signatures will be broken resulting to

insecure network communications.

In August 2016, the National Institute of Standards and Technology (NIST) pub- lished the following information [24]: "The advent of practical quantum computing will break all commonly used public key cryptographic algorithms. In response, NIST is researching cryptographic algorithms for the public key - based key agreement and digital signatures that are not susceptible to cryptanalysis by quantum algorithms."

The goal of post-quantum cryptography (also known as quantum-resistant cryptog- raphy) is to develop cryptographic systems that are secure against both conventional and quantum computers and can inter-operate with existing communication proto- cols [26]. Many post-quantum public key candidates have been actively investigated during the last few years that are believed to be resistant to quantum-based at- tacks. There are several ways to perform post-quantum secure cryptography, such as lattice-based, multivariate, hash-based, code-based, super-singular elliptic curve isogeny cryptography and symmetric key quantum resistance [23]. Not all of the aforementioned provide key encapsulation mechanisms and digital signatures. How- ever, if a given algorithm covers at least one of these two properties, it would be valuable for post-quantum cryptography. This thesis will focus on hash-based digital signature schemes.

1.2 Description of the problem

Hash-based signatures have been investigated and researched since the late 70s. In- formation about hash-based signatures is scattered around the world. This makes it difficult to find a reasonable source with a good overview of this field. The last overview of this topic has been provided in 2009 by ETSI which covered only the ba- sic of post-quantum cryptography, including hash-based signatures. There has been a lot of changes since ETSI’s overview of the Post Quantum Cryptography (PQC) field. Over time, new algorithms have been introduced, and existing algorithms have been modified and improved.

This thesis will investigate and address the following question:

1. What kind of hash-based post-quantum digital signatures schemes do exist?

This thesis can also be considered an up-to-date concise "encyclopedia" of post- quantum hash-based algorithms for digital signatures.

10

1.3 Methodology

This thesis intends to describe hash-based signatures schemes and provide a compar- ative description and analysis of some of the proposed schemes. The description will be based on the aspect of the signature schemes such as key sizes, signature size and security level. The proposed schemes will also be compared to the standard schemes used today, such as RSA and DSA. Also, by describing and comparing hash-based signatures. The thesis aims to make hash-based signatures a bit more accessible, as a lot of the information on this topic is not aggregated and the history of hash-based signatures stretches back to 1978.

The work in this master thesis has also resulted in a publication in the International Journal of Advanced Computer Science and Applications (IJACSA) in March 2018.

The paper entitled "The impact of quantum computing in present cryptography" is attached as an appendix at the end of this thesis.

1.4 Structure

The thesis will first, chapter 2, describe basic security concept, conventional cryp- tography and the usage of digital signatures in standardized protocols. Chapter 3 covers information about quantum computing and its impact on conventional cryp- tography. Chapter 4 will then present the first appearance of One-time hash-based signatures and its evolution. Chapter 5 describe some of the most important Few- time hash-based signatures. Chapter 6 describes stateful Many-Time hash-based signatures. Chapter 7 describes stateless Many-Times hash-based signatures which are proposed for the standardization process. All chapters 4, 5, 6 and 7 describe hash-based signatures by first presenting the protocols of key generation, signing and verifying process, then describes the security of the system. Chapter 8 discus the difference between stateful and stateless signature schemes. Chapter 9 concludes the thesis with a summary and possible ideas for future work in this field. At the end of this thesis, there is an appendix to find with the published paper derived from this work.

Chapter 2

Theoretical background

This chapter is meant to be a comprehensive collection of information which should provide the reader with the basic definitions needed to understand the second part of the thesis. Definitions which seem relevant to security, conventional cryptography, quantum computing, and protocols will be described in their entirety in this chapter.

2.1 Security Concepts

Security is a wide field of study with many concepts, principles, services, and mecha- nisms. However, the term itself has no single definition. In computer science, security strongly depends on security objectives and in which degree the security services with the help of security mechanism can fulfill them. For instance, a system might provide or need secure communication, which would be an objective. The latter is dependent on services like TLS that encrypts, which is a mechanism, the communication. How secure a system is, strongly depends on proper security requirements and the security measures that fulfill these under all proper circumstances.

The CIA (Confidentiality - Integrity - Availability) principle is often used when de- scribing the system security. However, it does not cover the whole specter of security.

Thus, more concepts like accountability, authentications and other are added to pro- vide better security. Subsections below presents these security concepts.

12

2.1.1 Confidentiality

Confidentiality (privacy, secrecy) says that the information should be secure and only accessed by the authorized parties. Privacy refers to protection of personal data, whereas secrecy refers to protection of data belonging to an organization. Ad- ditionally, confidentiality possesses properties such as unlinkability and anonymity.

Here, the former means that two or more items of interest cannot sufficiently be dis- tinguished whether they are related or not. The latter term ensures that a subject cannot be identified within a set of subjects [46, 34-35].

2.1.2 Integrity

Integrity is to prevent unauthorized modifications or destruction of data. In other words, to secure that the data has not been tampered with. Two types of integrity exist data and system integrity. Data integrity refer to the integrity of all digi- tal information. Whereas, system integrity refers to a state of a system where it is performing its intended functions without being degraded by disruptions in its environments [46].

2.1.3 Availability

Availability ensures that resources, services or data are accessible and usable upon demand by authorized entities. The importance of availability is illustrated by for instance in a DoS (Denial of Service) attack, which hinders legitimate users from using a system [90].

2.1.4 Accountability

Accountability ensures that the actions of an entity can be traced uniquely to that entity. In other words, all actions affecting security are traceable back to the respon- sible party. Accountability depends on identification, authentication, and auditing of a user [46].

2.1.5 Non-Repudiation

The security term non-repudiation is strongly related to accountability. Non- repudiation provide undeniable evidence that an action has occurred. This term is usually divided in non-repudiation of [46]:

• origin - an entity cannot deny to having send a message,

• delivery - an entity cannot deny to have received a message.

2.1.6 Identity and Access Management

Identity and access management (IAM) is a framework which denotes the security technologies that enables the intended authorized individuals to access the right resources at the right times for the right reasons. This framework consists of three phases: configuration-, operation- and termination- phase [61].

Configuration phase contains:

1. Registration: Creation of an identity and new account.

2. Provision: Issuing credentials and unique name.

3. Authorization: Granting of rights by the authority.

Operation phase contains:

1. Identification: Identification is an assertion of who or what something is. This information is used to recognize an individual user. In computer systems, where log in appears, the username corresponds to the identity, where it claims to be a known entity. D.Gollman in his book [46, 60], says that identification is a 1 :n comparison that tries to identify the user from a database of n person.

2. Authentication: The entity has to prove that the claims about the identity are correct by providing some credential to the system. The system has then to compare the credential with the information stored in the database for that specific entity. This process is called verification and is an 1 : 1 comparison [46, 60]. The entity is authenticated only when the passwords for that entity matches.

3. Access control: Grating access by the system. Access control determines poli- cies for which information and computing services can be accessed, by whom,

14

under which conditions and which actions they are allowed to perform [46, 66-68].

Termination phase contains:

1. Authorization revocation: Removing of rights by the authority.

2. Credentials deactivation: Disabling the possibility of getting the resources by providing the credentials.

3. Account deactivation: The account deactivated and not deleted to maintain the user information.

2.2 Conventional cryptography

Cryptography is the science of providing information security. It can be referred as the process of securing data in transit or stored, against third-party adversaries.

Cryptography is etymologically derived from Greek words "kryptós" and "graphein"

which means hidden and writing respectively. Cryptography possesses of two impor- tant properties; encryption and decryption. Where encryption is a transformation of any plaintext to ciphertext. Whereas, decryption is the opposite process. Both encryption and decryption have to be performed under control of a key. Cryptog- raphy has been known and used for thousands of years for securing a message from illegitimate third parties. Nowadays, cryptography has become a fundamental part of modern security systems. In this section, we are going to explain cryptographic primitives like symmetric and asymmetric cryptography as well as hash functions since they are crucial for topic considered in this thesis.

2.2.1 Cryptographic Notions

Cryptographic notations are important to be familiar with since these are crucial for the full understanding of the meaning in particular descriptions. Therefore, it is necessary to emphasize which notations will be consistently used from now of and to the end of this thesis.

Algorithmic Notations

Following are frequently used in this thesis, this important to be familiar with:

• m - message of arbitrary length in form of a bit string {0,1}^∗,

• i - index,

• sk - secret/private key containing all sk_i’s,

• ski - part of secret/private key sk at indexi,

• pk - public key containing allpk_i’s,

• pk_i - part of public key pk at index i,

• σ - signature containing allσ_i’s,

• σ_i - part of signature σ at index i,

• H - hash function with collision resistance H :{0,1}^∗ −→ {0,1}ⁿ,

• F - pseudo random functionF :{0,1}ⁿ −→ {0,1}ⁿ,

• F_k - pseudo random function from functions family with key k, F : {0,1}ⁿx{0,1}^k −→ {0,1}ⁿ,

• d - message digest, result of d=H(m).

• n - security level in bit, meaning that it is necessary with 2ⁿ operations to break the security.

• logn - log₂n

These notations are common for most of algorithms described in this work. Algo- rithm specific notation will be additionally described in particular subsections.

2.2.2 Symmetric cryptography

In symmetric cryptography, when to parties want to securely communicate with each other they have to share a secret key. That secret key will be used for both encryption and decryption. So, the sender can encrypt a plaintext message using the shared secret key and the receiver can decrypt the message by using the same cryptographic algorithm the sender used and the same shared secret key. The secret key should only be known by the two parties that are communicating with each other. Therefore, an

16

efficient way for exchanging secret keys over public networks was demanded. These are described in Subsection 2.2.3 below. Furthermore, symmetric cryptography is divided into two groups; stream ciphers and block ciphers. These are covered in this Subsection.

Figure 2.1: Example of classical symmetric cryptography [114].

Stream Cipher

A stream cipher is an encryption method where plaintext message is encrypted bit- wise with a random or pseudo random key stream, normally by an XOR operation.

An example of stream cipher is One-Time Pad, and it is known to be theoretically se- cure. This means that even source of unlimited computing power is not able to break this encryption. Particularly, "theoretical secure" is known to be crypt-analytically unbreakable [98]. However, One-Time Pad does not guarantee integrity and gets insecure if secret keys are reused.

The advantage of stream ciphers is that both encryption and decryption are the same operations which are easy and fast to compute. However, there are some disadvantages as well. Since each bit from plaintext consumes one bit from key stream, it turns out that key streams have to be at least as long as the plaintext.

Additionally, the key should also be truly random, this is complex and expensive in large quantities. A stream cipher is Pseudo Random Number Generator (PRNG) which takes a short truly random secrete seed and expand it into a long sequence which looks random. Moreover, key communication is another obstacle. The secret key can be very big, and it has to be transmitted securely [62].

Block Cipher

Block cipher is an alternative to the stream cipher. In a block cipher, the encryption happens on a bigger bulk of data, typically on 128-bit blocks. The procedure of secure communication looks similar to stream ciphers. However, the secret key size is much smaller, so the biggest disadvantages of stream ciphers are eliminated.

In a usual case, where the sender wants to send an encrypted message to the receiver with a block cipher. The sender first has to choose a cryptographic secure algorithm and then establish a secret key shared with the receiver only. Then, the sender may encrypt the message with this cryptographic algorithm by providing both the plaintext message and the secret key to it. The chosen algorithm will slice the message into blocks and encrypt it with the secret key. This procedure happens automatically and creates a secure ciphertext. Now, the ciphertext can be safely sent to the receiver over an insecure channel. The receiver, knowing the secret key can decrypt the ciphertext using the same cryptographic algorithm that the sender used to encrypt the message.

There are mainly two ways for an attacker to decrypt the ciphertext. Namely, have the knowledge of the secret key or break the encryption algorithm, so that one is able to revert the encryption. However, breaking the current standardized symmetric algorithms is still infeasible. Therefore, an attacker willing to steal the information that is encrypted is trying to get the knowledge of the secret key to be able to decrypt it. In block ciphers, the size of keys determinates the security level of the encryption.

Nowadays, in symmetric cryptography, standardized block ciphers are 3DES and AES. Data Encryption Standard (DES) is an older standard from 1977 [43]. DES encrypts plaintext blocks of 64-bit with 56-bit keys. This gives the security level of56- bit which nowadays is considerate as insecure. In 1978, a more secure variant of DES called 3DES, pronounced triple DES, or TDEA (Triple Data Encryption Algorithm, was introduced. 3DES use 56∗3 = 168-bit keys, providing higher security level than original DES. However, the security level of 3DES is not 168-bit as one may think.

This is due toMeet-in-the-middle attack, which decreases the security level of 3DES to 112-bit.

More recently, in 2001, NIST standardized another block cipher called AES [40].

Advanced Encryption Standard has the advantages that it fast in both hardware and software. This makes the algorithm speed up in different applications. Additionally, AES is even more secure than 3DES. This algorithm comes in three different key sizes:

128, 192 and 256 bit, which is adequate to their security level. The recommendation 18

from NIST is that AES-128 is good enough for daily use. However, for top secret information AES-256 should be used [87].

Recently published paper from 2016 [10] shows the insecurity of 3DES. This is done by performing extended versions of meet-in-the-middle attack, which decrease the security level of 3DES from 112-bit to only 90-bit.

The threshold of what is considered as secure is increasing from year to year. In the last years, a security level of 80-bit is considered as the minimum for being secure enough to use. Consequently, both standardized block ciphers 3DES and AES are considered secure. In November 2017, NIST published an update with a recommendation of 3DES usage [41], where they among other says that 3DES "may be used by federal organizations to protect sensitive unclassified data".

Although, block cipher in its standard ECB (Electronic Codebook) mode is not secure for nowadays purposes. It is recommended to uses block ciphers in other modes like:

• CBC (Cipher Block Chaining),

• CFB (Cipher Feedback),

• OFB (Output Feedback),

• CTR (Counter),

• GCM (Galois/Counter Mode).

Figure 2.2 illustrate the tremendous difference in encrypting a picture with a block cipher in ECB mode versus block cipher in any other modes listed above. The difference comes from the fact that ECB modes encrypt block by block independently with the same key. Whereas, other modes provide some additional data into the next block when encrypted. This emphasizes the importance of choosing the proper mode when using block ciphers. Nowadays, the most commonly used mode is the GCM (Galois Counter Mode) mode which provides both integrity and confidentiality [84].

This mode is most often used in combination with AES.

2.2.3 Asymmetric cryptography

Asymmetric cryptography or Public Key Cryptography (PKC) is a form of encryp- tion where the keys come in pairs. This pair consists of a private key and a public key which are mathematically connected. The private key should be kept secret, and

Figure 2.2: Presents AES Encryption in different modes [106].

public key may be exposed to the public. Each party should have its own private and public key. Asymmetric cryptography can be used for encryption, key exchange, and digital signatures.

Security Assumptions

RSA, Diffie-Hellman (DH) and Elliptic Curve Cryptography (ECC) are asymmetric cryptography algorithms that are primarily used today. Their security relies on mathematical problems, which are considered hard for conventional computers to solve. In current conventional standardized algorithms, discrete logarithmic problem and factorization problem are used. Such kind of algorithms are called one-way functions because they are easy to compute in one direction, but the inversion is difficult [39].

Asymmetric cryptographic algorithms such as Diffie-Hellman (DH), ElGamal encryp- tion and Digital Signature Algorithm (DSA) are based on the Discrete logarithmic problem (DLP). The difficulty of breaking these cryptosystems is based on the diffi- culty in determining the integer r such that g^r = x modp. The integer r is called the discrete logarithm problem of x to the base g, and it can written as r = log_gx mod p. The calculations in DLP are executed in algebraic groups. This problem is known to be very hard solved especially if the parameters are large enough since there are no logarithmic operations in algebraic groups. Recently, in 2017, keys equal or larger than 2048 bits are recommended for secure key exchange [87].

Elliptic Curve cryptosystem (ECC) uses a generalization of the discrete logarithm problem [23]. ECC uses a pair (x, y) that fits into the equation y² = x³ +ax+b mod p together with an imaginary point Σ (sigma) at infinity, where a, b∈ Z_p and

20

4a³+ 27b² 6= 0 mod p. ECC needs a cyclic Group G and the primitive elements to be of order G [87].

Factorization problem relies on the hardness of big integers factorization. Given one 2000-bit product of two primes, there are computationally infeasible to find the origin two primes of this product. There are many algorithms that use the hardness of factorization problem, the most known is RSA [87, 169].

Encryption

Figure 2.3: An overview of asymmetric cryptography [107].

RSA is a standardized algorithm for asymmetric cryptography that among other provides encryption. As mentioned before and shown in Figure 2.3 on Page 21 two different keys are used for encryption and decryption of a message. Since the keys have a mathematical connection between them, it means that decryption is possible to perform with receivers private key only if the message was encrypted with the receivers corresponding public key.

For instance, if the sender wants to encrypt a message to the receiver. The sender would ask the receiver about his public key or get the public key from the receiver’s public repository. Then, the sender would use his public key to encrypt the message.

Next, the sender would transmit the encrypted message to the receiver who is able to decrypt the message with his private key.

RSA was invented in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adleman [93].

This algorithm became one of the most important public-key schemes. Its security is based on the difficulty of factorizing product of two primes, and the scheme goes as follows.

Before any encrypted message sending may happen, the receiver has to compute a public key (n, e) and a private key (d). To do so the receiver has to:

1. Choose two large primes p and q, nowadays they should be at least of 1024- bit each. These should also be tested with primality test for example Miller - Rabin [1].

2. Computen =p·q, which usually is bigger than 2048 bits.

3. Use Euler’s Phi function: ϕ(n) = (p−1)·(q−1) to select a public exponent e∈ {1,2, ..., ϕ(n)−1} such that gcd(e, ϕ(n)) = 1.

4. Compute the private key d by d·e = 1·(mod ϕ(n)) which can be computed with the Extended Euclidean Algorithm.

After these steps the encryption can be perform using public key with following equation

y=x^e (mod n). (2.1)

Whereas, the message can be decrypted with equation

x=y^d (mod n). (2.2)

Where x is a plaintext message and y is the ciphertext. However, these calculations are computationally costly.

Key Exchange

According to Paar and Pelzl [87], RSA and asymmetric algorithms, in general, are not meant to replace symmetric algorithms since they are computationally costly.

Therefore, RSA is mainly used for secure key exchange between two parties and often used together with symmetric algorithms such as AES, where the symmetric algorithm does the actual data encryption and decryption. Another widely used standardized algorithm in asymmetric cryptography is the Diffie-Hellman key ex- change. With Both mentioned scheme, the sender and the receiver are able to agree on a secret key although the long distance between them. In addition, another family

22

of public key algorithms known as Elliptic Curve Cryptography is extensively used.

ECC provides the same level of security as RSA and DLP systems with shorter key operands which makes it convenient to be used in systems with low computational resources [87].

The Diffie-Hellman algorithm was developed particularly for the purpose of key ex- change. Here, the sender and the receiver can agree on a common secret without a leak of information and without the need of meeting each other. Some parts of this scheme were already described above in the paragraph about Security Assumptions.

However, the full algorithm will be presented for better understanding. In Diffie- Hellman, there are two public parameters called domain parameters. They arepand α, where p is a big prime and α is a generator in the multiplicative group modulo p. Then, each party has to generate a secret number such that only the generated parties have the knowledge of it. Let’s assume that the sender generates number a and the receiver generates numberb. Next, they both take the generator g and raise it to their generated number and send it to each other. Particularly, the sender cal- culatesg^amodp=Key_A and the receiver calculatesg^bmodp=Key_B. Then,Key_A is send over to the receiver, andKeyB is sent over to the sender, both over the insecure public network. Last, the sender raises the value received from the receiver with her generated number and the receiver does the same with the value received from the sender. So that they both come to the same answer which will become their secret key. Mathematically it look like this, the sender calculate Key^a_B = Secret key and the receiver calculate Key_A^b = Secret key [34]. A potential adversary will only get the values ofg, p, KeyA, KeyB. However, from this information, the adversary is not able to obtain the shared secret key of the sender and the receiver.

A small example with real numbers will give a better understanding.

Domain parameters:p= 23 (prime) and g= 11(generator) (2.3) sender: generates a= 6 −−−−−→^calculates g^a mod p= 11⁶ mod 23 = 9 (2.4) receiver: generates b= 5 −−−−−→^calculates g^b mod p= 11⁵ mod 23 = 5 (2.5) Eve’s knowledge: g = 11, p= 23, g^a mod p= 9 and g^b mod p= 5 (2.6) sender−−−−−−−→^{ga mod p=9} receiver, receiver−−−−−−−→^{gb mod p=5} sender (2.7) sender:5⁶ mod 23 = 8, receiver: 9⁵ mod 23 = 8 (2.8) These generated numbersaandbare private keys of sender and receiver respectively.

Whereas,

g^ab mod p=g^ba mod p (2.9)

is their shared secret key, which can be used as key in for example AES encryption.

Digital Signature

Digital signatures may be compared to handwritten signatures. However, they are more secure. Digital signatures provide authentication, non-repudiation, and in- tegrity. For instance, the sender can sign a document digitally by hashing the docu- ment and encrypt it with her private key. Then, to verify the signature, the receiver has to decrypt the received document with the sender’s public key (authentication and non-repudiation) and hash the original document. Whenever these two hash values match (integrity), then the signature is to trust. Current Digital Signature Standard (DSS) is Digital Signature Algorithm (DSA) which was standardized by NIST in 1993 adopted from FIPS 186 [44]. DSA is a variant of El-Gamal signature scheme [42]. The last update on DSA was provided by NIST in 2013 [66].

Structurally, a digital signature scheme is divided into tree sub algorithms: key generation Kg, signing Sign and verification V rf y - algorithm.

1. Kg: takes as input a security parameter n and generates both secret key and public key (sk, pk).

2. Sign: provided with a private key and a message(sk, m)generates a signature σ of given message.

3. Vrfy: Takes a signature, message and public key (σ, m, pk) as input and returns "accept"/"reject" or 1/0 in boolean value. A valid signature need to hold the following equation:

Vrfy(pk, Sign(sk, m), m) = 1 (2.10)

Security of Digital Signatures

In 1988, Goldwasser et al. [45] provided with a hierarchy of attack models against digital signature schemes. The authors, describes two kinds of attacks, whereas the second consist of four variants.

• Key-only attacks: where the adversary knows only the public key of a signature scheme.

24

• Message attacks: where the adversary possesses a signature of a known or chosen message.

– Known-message attack: the adversary possess the information of a set of messages along whit their signatures. However, the messages were not chosen by the adversary.

– Generic chosen-message attack: is an attack which does not depend on the public key of the signature scheme. The adversary may choose a fixed number of messages to be signed by the signature scheme. However, the adversary will not be able to change any message after he sees the signatures.

– Directed chosen-message attack: the adversary has knowledge of the pub- lic key of the signature scheme and can decide a list of messages to be signed. A message cannot be changed after seeing the first signature.

– Adaptive chosen-message attack: the adversary knows the public key of the signature scheme, he also has the possibility to ask for the signature of any messages and can adapt the messages to already seeing signatures.

This is the strongest attack an adversary can mount to a signature scheme.

The authors of [45], have also provided the definitions of breaking a signature scheme.

They said that a signature scheme is broken when the adversary is able to perform one of the following attacks in a non-negligible probability

• A total break: the adversary learns the secret trap-door of the scheme. (Ex.

in RSA it would be the information about the primes p and q.)

• Universal forgery: when the adversary finds functionally similar signing algo- rithm with the same trap-door and is able to forge a signature.

• Selective forgery: when the adversary can forge a signature of the message decided by him.

• Existential forgery: when the adversary is able to forge a signature of at least one message. The message is not known to the adversary, and it may be a random string.

The strongest security property of these above for a signature scheme is the last one. It is desired to a signature scheme to be immune for existential forgery of an adversary. Then, the signature scheme is Existential Unforgeable (EU).

However, combining the notions of both "breaking the system" and known attacks listen above. The desired security of a digital signature scheme is to be Existen- tially Unforgeable under Chosen-Message Attacks (EU-CMA) in the standard model.

Where the security in the standard model is based on the fact that the adversary is limited by the computational power and the amount of time.

When a signature scheme is proven to be secure using only complexity assump- tions (like for example preimage-resistance, second preimage-resistance or collision- resistance), then the scheme is secure in the standard model. Nevertheless, there is difficult to prove the security in the standard model. Therefore an idealized version is used, where the cryptographic function is replaced with a random function. When such a changed scheme is proved secure, then it is said that the scheme is secure in the random oracle model. The random oracle model was first described in 1993 by Beralle et al. [6].

In addition, a property of a good signature scheme is to be forward secure [5]. This means, that when such a scheme gets compromised, for example by leaking the private key, the signatures that already was signed with this key remains secure. To fulfill this criterion, the signature scheme should be a key evolving scheme. This means that the private key of that signature scheme should change after a period of time.

2.2.4 Hash functions

Hash functions are one of most important cryptographic primitives. Hash functions are divided into two main branches, keyed and unkeyed. These have many appli- cations in real wold usage. For instance, one of most popular keyed hash functions applications is MAC or Message Authentications Code. This provides a crypto- graphic checksum based on secret symmetric keys, as well as authentication and integrity of the message. On the other hand, the unkeyed hash functions are used as MDC or Manipulation Detection Codes.

Hash functions which possess these six properties provide a good standard and se- curity [87].

1. A hash function compress a message of arbitrary length to a fixed length bit string. In practice, it brakes the message into blocks with padding in the last block if needed, and then hash these blocks with the concatenation of previous hashed block. The result of such hash function can be seen as the fingerprint

26

or a digest of the given message. The output of a hash function may also be called a hash value or a checksum.

2. Hash functions have to be easy to compute. However, this property should not be applied to all hash functions. Hash functions used for password storing should be a bit slower so that brute force attack would not become practical.

3. Fixed length output, hashing a messagem with a hash functionh then a hash valuez =h(m) need to have a specific length.

4. Preimage resistance also known as one-wayness. It has to be computationally infeasible to find x whenz =h(x)and z is the output of a hash function when hashing message x.

5. Second preimage resistance or weak collision resistance. This requirement says that given h(m₁) it should be computationally infeasible to find another mes- sage m₂ which maps to the same hash value. Thereby it should be computa- tionally infeasible to find message m₂ which maps to the same hash value as the given message m₁.

6. Collision resistance means that there are computationally infeasible to find two different messages that maps to the same hash value. This property is more difficult to achieve than the previous one, since the attacker has access to both variables which can be modified.

These are the most important requirements. When all of them are satisfied, then the security of a hash algorithm depends on its output length. Where longer output yields better security level.

In 1989, both Ralph Merkle and Ivan Damgård proved that whenever a one-way compression function is collision resistant, then the whole hash function will be col- lision resistance as well. This led to a well known and widely used construction of hash functions called Merkle-Damgård construction [80]. In more detail, to be able to compress messages of any length, the hash function has to slice the messages in fixed length blocks. Then, for each iteration a function f is taking two inputs, an initialization vector (IV) and a block from the message. In the first round, the IV is given, then in the following round the functions f takes the output of the previous iteration of f as an IV in the current round. In the last round off iterations, when the sliced message is computed, the padding is added. The padding starts with an 1 follows with the necessary amount of 0’s and ends with the length of the origin mes- sage. The result of all these internal f function iterations is fed into the finalization function that may compress the internal, bigger, state to expected smaller output.

For instance, compressing1024-bit internal state into 256-bit output. All hash func- tions from MD family and hash functions from SHA family up to SHA-2 including, are based on Merkle-Damgård construction. Nevertheless, this is not the only cryp- tographically secure construction. The last standardized hash function SHA-3 from 2015 does not use the construction of Merkle-Damgård. SHA-3, originally Keccack, is using a sponge construction [69].

There are many applications where hash functions are useful, one of them are digital signature schemes. When using hash functions in hash-based digital signatures, there is a need for two more properties as pseudorandomness and undetectability [59]. Undetectability gives the property where an attacker cannot detect whenever a bit is an output from a hash function itself or if it is just a random value. Whereas, pseudorandomness gives a property that random oracles posses. The requester gets a value from a black box based on an input value and an initialization bit. The black box generate a outputg(x)from an inputxand an initialization bit b. When the bit b is equal to 1, then the black box choose a value from the hash function. Otherwise, it generates a random value (for instance from lazy sampling). The black box needs to remember the previous answers such that it is consistent.

In 2006, Halevi and Krawczyk [49] presented a method to "Strengthening Digital Signatures via Randomized Hashing". The authors, says that by performing bitwise exclusive OR operation on the message with salt before hashing, will free practical digital signature from relying on strong collision resistance. Consequently, yielding better security on lower (second pre-image resistance) security assumption. The same year, the authors had a short presentation of this topic in NIST hash workshop [48]. Three years later, NIST published a recommendation for using randomized hashing in digital signatures [33]. In 2012, NIST published an updated version with recommendations for using randomized hash in different applications [32].

The current standard in the hash function is SHA-3, which was announced in August 2015 [69]. SHA-3 offers arbitrary output length in order to fit to any applications needs. However, SHA-2 family is not outdated and is still secure for use, especially these variants with longer outputs. Both SHA-2 and SHA-3 family provide good and lasting security.

2.2.5 Attacks on Hash Functions

Important to emphasize is to be aware of different attacks on a hash function, espe- cially when using these in security applications. In this subsection, some of the most

28

common attacks on hash functions are briefly described.

Generic Security

The security of hash functions, is often analyzed as a black box testing. It is because in black box testing there is no need to look at the internals, such that many different hash functions may be tested. The results are often expressed in query complexity, namely the number of queries that was needed to break a specific property. The Table 2.1 shows the generic security for hash functions in classical cryptography [59]. As well as, the number of queries needed to break a certain property of a hash function, where n represents the output length of given function.

One wayness Second Image Resistnace

Collision

Resistance Untraceability Pseudo Random Function Classical O(2ⁿ) O(2ⁿ) O(2^n/2) O(2ⁿ) O(2ⁿ)

Table 2.1: This table shows generic security for hash function in classical cryptogra- phy.

A hash function that does not meet the generic security is considered as insecure and should not be used in security applications.

Brute Force

Brute force attack is one of the oldest existing attacks. It can be seen more like an exhaustive search in a database. With brute force attack, an attacker tries all possi- bilities inputs until he gets expected output. This kind of attack is very unpractical and time-consuming due to the enormous amount of possibilities [87]. Taking into consideration a hash function with an output of 256-bit and the task to break a sec- ond pre-image resistance. It will take 2²⁵⁶+ 1tries to do so. To set the number into a perspective and give it more meaning, it has to be said that the known observable universe consists of 10⁸⁰≈2²⁶⁸ particles.

Birthday (Collision) Attack

Birthday problem or birthday paradox is often explained with a riddle which goes as follows: How many people need to be in a room so that at least two people have

birthday exactly on the same day? Of course, since it is 365 (or 366) days in a year, the safe answer to this question will be 367 people. This gives 100% chance that at least two people have the birthday on the same day. However, taking into consideration the probability theory from math, every answer that has the probability above 50%is correct. Since then it is more likely that given answer is accurate than the opposite case. Consequently, following this logic and probability calculations, leads to the answer of 23 people. This yield the probability of 50.7% of being true.

In other words, given 23 people in a room, it is more likely that there are two of those who share their birthday than there is no one that is sharing a birthday with any other in the room. As it can be observed the answer is roughly above the square root of days in a year√

365 = 19.1−→1.17∗√

365 ≈23[87, 301]. Moreover, slightly increasing the number of people to 30 or 50, rises the probability to70.6%and97.0%

respectively.

Birthday paradox is also used in the cryptographic attack called the birthday attack, which is a real threat to hash functions. Birthday attack reduces the complexity of finding a collision in a cryptographic hash function by a square root. Meaning that a cryptographic hash function withb-bit output length, have the security level of only b/2-bit. Since the security drops by a square root. So with a hash function having 80-bit output, there is need of only2⁴⁰ tries for a collision to occur [87, 293-314].

Having in mind that digital signatures make use of hash functions with collision resistance, this attack may cause a forgery of a signature.

Chosen Prefix Collisions Attack

Collisions attacks are divided into two kinds of attack. First is a plain finding of collision by applying birthday paradox as described above. Second is to find prefixes for two different messages such that they map to the same hash value. In other words, find p1 and p2 for messagesm1 and m2 so thatp1||m1 maps to the same hash value as p₂||m₂.

This attack was used by Stevens et al. [100] to find a collision in SHA-1. SHA-1 was standardized by NIST in 1993 and has been widely used since then. Unfortunately, in many years it has been known that SHA-1 has some weaknesses. In 2011, NIST has officially announced that SHA-1 should not be used anymore due to theoretical attacks. However, SHA-1 is still widely used and creates a threat, since the collisions are now practical. The authors was able to find a prefix to colliding messages in such way that makes a user have two arbitrarily chosen distinct visual contents. They

30

concluded that this attack was 100 000 times faster than a brute force attack.

Any applications relying on collision resistance hash functions are threatened by this attack. However, applications that requires second-preimage resistance will not suffer from this attack.

Length extension attack

In this attack, an attacker is trying to determinate the hash value of the concatenation of two messages H(m₁||m₂) [105]. By having the knowledge of both the hash value H(m1) and length |m1| of the first message and having control over the second concatenated message m₂. The attacker may be able to extend the origin message m₁and compute a new hash value yielding a valid signature. Important to emphasize is that the attacker does not have the knowledge of the actual content of the origin message m₁.

In practice, this attack utilizes the way Merkle-Damgård construction [80] is build up. The attack works in following way. When Merkle-Damgård construction is used to hash a secret concatenated with a message H(secret||message). The secret will appear in the first block(s) of a sliced message. Therefore, the internal state after the final iteration of function f will yield a valid signature of given message. However, having the internal state of the Merkle-Damgård construction after the last iteration of function f. Then, adding a second message to the construction and making it iterate through the second as well, will also yield a valid signature. Consequently, as aforementioned, an attacker having knowledge of the length of a message, its hash value, and having control over the second concatenated message is able to create a valid signature.

All hash functions based on Merkle-Damgård constructions like MD0-MD5 and SHA- 0-SHA-2 algorithms are exposed to this attack. Nevertheless, both SHA-3 and HMAC are immune to length extension attack, since they do not use the construction of H(secret||message). One of the prevention technique for this attack is to flip the order of these messages to H(message||secret) [38].

2.3 Digital signatures in current protocols

In the time of internet expanse, the use of current standardized protocols as well as creating new protocols grows continuously. Most of the protocols need to be secure and may have to provide a sort of authentication. Nowadays, digital signatures are used to fulfill such security requirements. In a post-quantum world, all of the digital signatures need to be replaced, since they will be directly or indirectly affected by a quantum computer. Therefore it is important to have an overview of what role does a digital signature have in these protocols as well as in which way the signatures are used. In this section, some of most commonly used internet protocols that are containing a digital signature are presented.

2.3.1 PKI

PKI is a framework used to distribute, administrate and use public keys over a network. PKI issues X.509 certificates to authenticate the relationship between a public key and an entity on a network.

Figure 2.4: Presents 3 versions of X.509 certificate structure [109].

To trust an entity over a network, it is necessary to verify its certificate, by ver- ifying the certification path. The certifi- cation path starts with the end entity’s certificate and proceeds through some intermediate CAs up to a trust anchor or root CA (certificate authority). A trust anchor is a part which trust is assumed and not derived from other sources. The trust anchor is a root CA or a CA which can derive its trust to an underlying in- termediate (subordinate) CA or end en- tity (subscriber) [73].

A variation of this structure exists, where there are several root CAs, in a trust list. In this structure, a subscriber can be verified by any of these root CAs.

This structure is used in web browsers, 32

where they are initialized with hundreds of root CAs from the beginning.

Figure 2.4, presents a X.509 certificate and data fields it consist of in different versions [63]. There are 3 versions of X.509 certificate available, where version

3 is the last version of the standard which provides the most information about the end entity and the purpose of the certificate.

Figure 2.5: The flow of getting an X.509 certificate in Public Key Infrastructure [108].

To get a certificate, the end entity has generated a Certificate Signing Request (CSR) containing information about the end entity, signed by entity’s private key. There- after the CA will validate the request by verifying the signature and will generate a new X.509 certificate for the end entity if validation was succeeded [74].

A PKI structure also consists of a Certificate Revocation List (CRL). CRL is a signed data structure which continuously keeps control over invalid certificates. Each CA

posses a CRL list which keeps track of issued certificates that are revoked. This is an append-only list and is available to the public [28]. However, due to the problem of big CRL list, the OCSP was taken to use. OCSP is an Online Certificate Status Protocol which returns one line digitally signed response instead of CRL list. OCSP creates less overhead on the network while checking the certificate, and have the advantage of requesting the status of a single certificate [96].

A good example of public key infrastructure in Norway is BankID, Buypass, and ID-porten.

2.3.2 TLS

TLS is a widely used protocol to secure data traffic through the internet. A good example of TLS usage is HTTPS protocol used by web browsers. HTTPS protocol is a secure version of HTTP, namely by securing the communication by TLS. The TLS protocol encrypts all traffic between a server and the client with a symmetric cipher due to the performance.

To provide the security, TLS always starts with a handshake between the client and the server. The handshake protocol consists of four alternating messages between the parties, where the client start the conversation. Among other information, a certifi- cation exchange message, containing X.509 certificates, is sent. The purpose of this message is to authenticate both parties so that they can trust each other. However, most of TLS implementations often use server authentication only, called one-way authentication. Furthermore, the secret key is established through a key agreement exchange. When both parties share the secret key, then the TLS handshake protocol is completed, and both parties may freely and securely send the application data between them.

Figure 2.6 present entirely handshake protocol of TLS, where fields labeled with * are not required [104]. However, then no authentication is provided and an anonymous session is established.

2.3.3 IPsec

IPsec is a network protocol suite that provides with authentication of an entity, key management, and confidentiality. This protocol uses IKE to perform mutual

34

Figure 2.6: TLS handshake protocol [103].

authentication, establishment and maintaining of Security Associations (SA) to use it with Authentication Header (AH) or Encapsulation Security Payload (ESP) [22].

IKE was originally built on three old protocols namely SKEME(1996), OAK- LEY(1998) and ISAKMP(1998). SKEME is a simple and compact protocol which provide key exchange mechanism. SKEME have some flexible tradeoffs between secu- rity and performance without increasing complexity of the protocol. As key exchange mechanism, it uses Diffie-Hellmann with fast and frequent key refreshment [68].

OAKLEY protocol is also a key agreement protocol that use Diffie-Hellmann key exchange algorithm to exchange keys across an insecure network connection securely.

This protocol supports Perfect Forward Secrecy, key updates and is compatible with ISAKMP [86].

ISAKMP is a protocol for establishing SA and cryptographic keys on a network but does not define the actual key exchange technique [29].

IKE protocol has been updated over time to be more simple and reliable and in 2014 IKEv2 became an internet standard. To establish SA, there is a need for four IKE initial exchanges messages [22].

In IKE_SA_INIT messages, a Diffie-Hellman exchange is performed for establishing

the common secret key. This key is used to derive all further keys for IKE SA.

Then IKE_AUTH messages ensures that messages are authentication and encrypted expect the headers. It will also authenticate the previous message that was sent.

When IKE is done with establishing the SA, IPsec can be executed in AH or ESP mode.

Figure 2.7: AH and ESP presented in both transport and tunnel mode [14].

IPsec in AH mode provides message authentication of payload and immutable header fields by extending IP header [64]. While IPSEC in ESP mode provide encryption and optionally authentication of the payload by extending header and trailer of the originally IP [65]. Both AH and ESP mode can be used in transport or tunnel mode.

The tunnel mode adds extra protection of the origin IP header datagram by adding a new IP header in front of the datagram.

2.3.4 DNSSEC

DNSSEC provides a security extension to DNS queries on an IP network. However, DNSSEC is not an internet standard and can be added to servers as an additional security layer. DNSSEC has been invented in 2005 but first in 2014 was allowed to use in .no domains. DNSSEC provides origin authentication and data integrity but

36

does not provide confidentiality or availability. The security in DNSSEC based on public key cryptography and chain of trust.

Chain of trust makes it easier to use an unknown server based on the fact that the server trusts another server which again trusts the root server. Since everybody trusts the root server, then the unknown server can now, based on this fact, be trusted by validation chain. DNS root server is the starting point of the chain and is also known as the trust anchor. This is identical to the PKI infrastructure. First in 15. july 2010 the root anchor was created by ICANN and its "DNSSEC Root Signing Ceremony" [60, 101].

Figure 2.8: Presents a DNSSEC query to www.example.com

When an end user sends a DNSSEC request to a web page with URL www.example.com (step 1). The query goes to ISP recursive resolver which has to find out the A or AAAA record/IP address for given URL. ISP sends then a request to DNS root name sever and ask about the IP address of TLD of the URL which is the .com name server (step 2). Since, DNSSEC flags in on, the DNS root name server answers with a bigger data pack that to regular DNS query. The response contains five parts (step 3):

1. Non secure referral to .com name server.

2. RRset of DNSKEYs: DNS rootZSKpub and KSKpub keys.

3. RRsig of RRset from 2., which is digitally signed by roots KSK_pvt.

4. DS record for the .com name server, which is a digest of .com KSKpubkey.

5. RRsig of DS from 4., signed by roots ZSKpvtkey.

The ISP recursive resolver can now access the .com name server and validate its authentication. For validation it have to verify the root zones records and the root zone it self (step 4).

1. Record verifying

(a) Root zonesKSK_pub is used to verify the signature of DNSKEY RRset.

(b) Root zonesZSKpubis used to verify root zones DS record for .com zone.

2. Zone verifying

(a) ISP recursive resolver has already a copy of DNS root zonesKSK_pub key from another source that the DNS root name server itself. Now the root zone can be verified by comparing the local copy ofKSK_pub key with the KSK_pub key send by DNS root zone.

Once again, it can be mentioned that digital signatures are essential for secure usage of a public network.

2.3.5 S/MIME

S/MIME standing for Secure/Multipurpose Internet Mail Extension is an important protocol for signing and encrypting data from MIME protocol. This protocol is able to transmit different types of data between two distinct systems which uses different formats. Formats like: text, audio, images, videos, applications and many others are supported by S/MIME [50].

S/MIME provides with authentication, message integrity and non-repudiation of origin by using digital signatures. As well as, privacy and data security by using encryption. In S/MIME, the certificates are required to protect the authenticity and integrity of public key, thus protecting against man in the middle attack.

38

Chapter 3

The Impact of Quantum Computing

3.1 Quantum Computing

Quantum computing theory firstly introduced as a concept in 1982 by Richard Feyn- man. Bone and Castro [12] stated that a quantum computer is completely different in design than a classical computer that uses the traditional transistors and diodes.

Researchers have experimented with many different designs such as quantum dots which are basically electrons being in a superposition state, and computing liquids.

Besides, they remarked that quantum computers could show their superiority over the classical computers only when used with algorithms that exploit the power of quantum parallelism. For example, a quantum computer would not be any faster than a traditional computer in multiplication. It can be concluded that a quantum computer is a computer that uses the effects of quantum mechanics to its advantage.

3.1.1 Quantum Phenomena

Quantum mechanics is related to microscopic physical phenomena and their specific behavior. In a traditional computer, the fundamental blocks are called bits and can be observed only in two states; 0 and 1. Quantum computers instead use quantum bits also usually referred as qubits. In a sentence, qubits are particles that can exist not only in the 0 and 1 state but both simultaneously, known as superposition. A particle collapses into one of these states when it is measured. Quantum computers take advantage of this property mentioned to solve complex problems. An operation

on a qubit in superposition acts on both values at the same time. Another physi- cal phenomenon used in quantum computing is quantum entanglement. When two qubits are entangled, their quantum state can no longer be described independently of each other, but as a single object with four different states. In addition, if one of the two qubits states changes the entangled qubit will change too regardless of the distance between them. This leads to true parallel processing power. The com- bination of the phenomena mentioned above results in an exponential increase in the number of values that can be processed in one operation when the number of entanglement qubits increases. Therefore, a n-qubit quantum computer can process 2ⁿ operations in parallel [75].

3.1.2 Shor’s Algorithm

In 1994, the mathematician Peter Shor in his paper “Algorithms for Quantum Com- putation: Discrete Logarithms and Factoring” [99], proved that the complexity of factoring large integers would be changed fundamentally with a quantum computer.

The following example will provide a better understanding of how Shor’s algorithm factorizes large numbers. In this example, the prime origin factor of number 15 will be found by Shor’s algorithm. To do so, there is in need a 4-qubit register. A 4- qubit register can be visualized as a normal 4-bit register of a traditional computer.

Number 15 can be represented as1111in binary, therefore a 4-qubit register is enough to calculate the prime factor of this number.

According to Bone and Castro [12], a calculation performed on the register can be thought as computations done in parallel for every possible value that the register can take values between 0 and 15. This is also the only step needed to be performed on a quantum computer.

The algorithm does the following:

• n = 15, is the number we want to factorize

• x is a random number such as 1< x < n−1

• x is raised to the power contained in the register (every possible state) and then divided by n. The remainder of this operation is stored in a second 4-qubit register. The second register now contains the superposition results. Let’s assume that x= 2 which is larger than 1 and smaller than 14.

40