# White-Box Implementation of ECDSA Based on the Cloud Plus Side Mode

Authors: Jie Zhou; Jian Bai; Meng Shan Jiang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

White-box attack context assumes that the running environments of algorithms are visible and modifiable. Algorithms that can resist the white-box attack context are called white-box cryptography. The elliptic curve digital signature algorithm (ECDSA) is one of the most widely used digital signature algorithms which can provide integrity, authenticity, and nonrepudiation. Since the private key in the classical ECDSA is plaintext, it is easy for attackers to obtain the private key. To increase the security of the private key under the white-box attack context, this article presents an algorithm for the white-box implementation of ECDSA. It uses the lookup table technology and the “cloud plus side” mode to protect the private key. The residue number system (RNS) theory is used to reduce the size of storage. Moreover, the article analyzes the security of the proposed algorithm against an exhaustive search attack, a random number attack, a code lifting attack, and so on. The efficiency of the proposed scheme is compared with that of the classical ECDSA through experiments.


---

## Body

## 1. Introduction

### 1.1. Background

With the rapid development of computer and Internet technology, sensitive content containing military, political, economic, and other information is widely transmitted over networks. Because of the openness of the Internet, attackers usually use the Internet to obtain information illegally, which greatly threatens the lives and work of people. Network security has become an important part of network design, construction, and maintenance, and cryptography is the core barrier technology for protecting network information security. Traditional cryptography is based on the black-box model, which assumes that the operating environment of the cryptographic algorithm is safe. That is, the execution of the cryptographic algorithm cannot be observed nor tampered with, and an attacker can only observe and modify the information transmitted in a channel. However, as cryptography is widely used in e-mail, web access, digital rights management, e-government, and so forth, cryptographic algorithms often run in untrusted environments such as mobile phones, flat computers, and wearable electronic devices [1]. Attackers can easily use static analysis or dynamic debugging to obtain the secret key in a cryptographic algorithm, leading to a disclosure of this information. The traditional cryptography model cannot meet the increasingly high-security requirements.In 2002, Chow et al. [2] proposed the white-box attack context, which assumes the following:(1)
A fully privileged attack software shares a host with cryptographic software, having complete access to the implementation of the algorithm.(2)
Dynamic execution can be observed.(3)
Internal algorithm details are completely visible and alterable at will.People always use hardware or software to implement cryptographic algorithms. Regarding hardware, it is costly and has poor universality. Regarding software, the secret key will appear in the memory of the computing platform. It is easy for attackers to obtain this key by injecting malware. At present, there are two ways to prevent secret key leakage during the execution of a cryptographic algorithm. One is cloud collaboration [3], and the other is key decentralized storage [4]. However, cloud collaboration cannot resist local key disclosure, and it also requires solving the problem of identification between the cloud and the terminal. Although key decentralized storage can mitigate the leak risk when the key is in static storage, the key must be composed when the cryptographic algorithm is running. Key decentralized storage will also make the whole key appear in the memory.When the traditional cryptographic algorithms are implemented in software, the keys are easily leaked under the white-box attack context. Thus, it is urgent to design cryptographic algorithms that can resist white-box attacks [5]. The field of cryptography that can resist white-box attacks is called white-box cryptography. At present, the research on white-box cryptography has focused on white-box implementations and constructions. In the white-box implementations, the existing cryptographic algorithms are redesigned by using confusion, perturbation, and other methods to ensure the safeness of algorithms under the white-box attack context, with the original algorithm function kept. White-box construction is carried out to design a new cryptographic algorithm that can resist adversaries’ attacks under the white-box attack context.


### 1.2. Previous Work

An important line of research focused on the white-box implementations of AES and DES. In 2002, Chow et al. proposed the first white-box cryptography algorithm—the white-box AES implementation [2]. However, Billet et al. [6] put forward the BGE (BGE stands for the first letter of each of the authors, Billet, Gilbert, and Ech-Chatbi) attack to extract the AES key from the white-box AES implementation of Chow et al., with a computational complexity of 230. The BGE attack motivated the design of a white-box AES implementation that can provide more resistance against key extraction. In 2006, Bringer et al. [7] proposed a new white-box AES implementation that can resist the BGE attack. Mulder et al. [8] attacked the Bringer’s implementation with a computational complexity of 217. After that, Xiao and Lai [9] proposed another white-box AES implementation that was cryptanalyzed by Mulder et al. [10] with a computational complexity of 232. Recently, Xu et al. [11] proposed an AES-like cipher by replacing the AES S-boxes and MixColumn matrices with key-dependent components while keeping their good cryptographic properties. They claimed that the white-box implementation of their AES-like cipher can resist current known attacks. In 2014, Luo et al. proposed a new WBAC-oriented AES implementation [12], but Bai et al. [13] showed that the secret key of Luo’s implementation can be recovered with time complexity of approximately 244. The earliest white-box DES implementation was proposed by Chow et al. [14] in 2003. A fault injection attack was used to extract the key from Chow’s implementation by Jacob et al. [15]. In 2005, Link and Neumann [16] put forward an improved white-box DES implementation to resist the fault injection attack. However, Goubin et al. [17] and Wyseur et al. [18] both used differential cryptanalysis to extract the key from the implementation in [16]. In 2019, Amadori et al. [19] present a new DFA attack on a class of white-box implementations presented a new DFA attack on a class of white-box implementations of AES. Lin et al. [20] present an overview of the classic methods for constructing white-box solutions.In terms of new white-box cryptographic algorithms, Biryukov et al. [21] proposed a general method for designing white-box cryptography based on the ASASA (Affine-S-box) structure. They put forward two strong white-box variants of the ASASA symmetric scheme: one is based on Daemen’s quadratic S-boxes and the other is based on random expanding S-boxes. Unfortunately, the ASASA construction was broken in [22, 23]. In 2020, Kwon et al. [24] use parallel table lookups to construct a secure white-box block cipher. Alpirez Bock et al. [25] present the security goals of white-box cryptography. Shi et al. [26] use state-dependent selectable random substitutions (SDSRS) to defeat various related white-box cryptanalytic approaches.Currently, there are few studies on public-key white-box cryptography in the public literature. In 2018, Zhang et al. [27] proposed the first white-box implementation of the identity-based signature scheme. In 2019, Feng et al. [28] proposed a white-box implementation for the classical Shamir’s IBS scheme.


### 1.3. Our Contributions

In this paper, we focus on a white-box implementation of the elliptic curve digital signature algorithm (ECDSA) [29]. ECDSA is the elliptic curve analogue of the digital signature algorithm and can provide integrity, authenticity, and nonrepudiation. The details of ECDSA can be found in several approved standards: ISO 14888-3 [30], ANSI X9.62 [31], IEEE Std 1363-2000 [32], and FIPS 186-2 [33]. Since ECDSA has a small key volume, small storage space, and high-security performance, it has become one of the most important digital signature algorithms.The main contributions of this paper can be summarized as follows: (1) a white-box implementation of ECDSA based on the “cloud plus side” mode is proposed. To protect the security of the private key in ECDSA under the white-box attack context, we use lookup tables and permutations to protect the private key. The permutations are used in both the cloud side and the client side. The private key is confused in a series of lookup tables and is thus able to resist the white-box attack. (2) The storage size of the proposed schemes is reduced by the residue number system. The private key is divided into several small parts by the residue number system. The small part of the private key can be hidden by a smaller size of lookup tables. The storage needed by the proposed scheme is feasible. (3) The security of the proposed scheme is analyzed from aspects of an exhaustive search attack, a random number attack, and a code lifting attack. (4) The efficiency of the proposed scheme is compared with that of the classical ECDSA through experiments. Because of the improved security, the proposed scheme runs slower than the classical ECDSA. The operation speed of the proposed scheme is also acceptable.The paper is organized as follows: in Section2, we briefly review the signature and verification of the classical ECDSA and introduce the concept of the residue number system (RNS). In Section 3, we propose a white-box implementation of ECDSA based on the RNS. The security analysis of our scheme is discussed in Section 4. In Section 5, the efficiency of the proposed scheme is compared with that of the classical ECDSA. Finally, we conclude in Section 6.


## 1.1. Background

With the rapid development of computer and Internet technology, sensitive content containing military, political, economic, and other information is widely transmitted over networks. Because of the openness of the Internet, attackers usually use the Internet to obtain information illegally, which greatly threatens the lives and work of people. Network security has become an important part of network design, construction, and maintenance, and cryptography is the core barrier technology for protecting network information security. Traditional cryptography is based on the black-box model, which assumes that the operating environment of the cryptographic algorithm is safe. That is, the execution of the cryptographic algorithm cannot be observed nor tampered with, and an attacker can only observe and modify the information transmitted in a channel. However, as cryptography is widely used in e-mail, web access, digital rights management, e-government, and so forth, cryptographic algorithms often run in untrusted environments such as mobile phones, flat computers, and wearable electronic devices [1]. Attackers can easily use static analysis or dynamic debugging to obtain the secret key in a cryptographic algorithm, leading to a disclosure of this information. The traditional cryptography model cannot meet the increasingly high-security requirements.In 2002, Chow et al. [2] proposed the white-box attack context, which assumes the following:(1)
A fully privileged attack software shares a host with cryptographic software, having complete access to the implementation of the algorithm.(2)
Dynamic execution can be observed.(3)
Internal algorithm details are completely visible and alterable at will.People always use hardware or software to implement cryptographic algorithms. Regarding hardware, it is costly and has poor universality. Regarding software, the secret key will appear in the memory of the computing platform. It is easy for attackers to obtain this key by injecting malware. At present, there are two ways to prevent secret key leakage during the execution of a cryptographic algorithm. One is cloud collaboration [3], and the other is key decentralized storage [4]. However, cloud collaboration cannot resist local key disclosure, and it also requires solving the problem of identification between the cloud and the terminal. Although key decentralized storage can mitigate the leak risk when the key is in static storage, the key must be composed when the cryptographic algorithm is running. Key decentralized storage will also make the whole key appear in the memory.When the traditional cryptographic algorithms are implemented in software, the keys are easily leaked under the white-box attack context. Thus, it is urgent to design cryptographic algorithms that can resist white-box attacks [5]. The field of cryptography that can resist white-box attacks is called white-box cryptography. At present, the research on white-box cryptography has focused on white-box implementations and constructions. In the white-box implementations, the existing cryptographic algorithms are redesigned by using confusion, perturbation, and other methods to ensure the safeness of algorithms under the white-box attack context, with the original algorithm function kept. White-box construction is carried out to design a new cryptographic algorithm that can resist adversaries’ attacks under the white-box attack context.


## 1.2. Previous Work

An important line of research focused on the white-box implementations of AES and DES. In 2002, Chow et al. proposed the first white-box cryptography algorithm—the white-box AES implementation [2]. However, Billet et al. [6] put forward the BGE (BGE stands for the first letter of each of the authors, Billet, Gilbert, and Ech-Chatbi) attack to extract the AES key from the white-box AES implementation of Chow et al., with a computational complexity of 230. The BGE attack motivated the design of a white-box AES implementation that can provide more resistance against key extraction. In 2006, Bringer et al. [7] proposed a new white-box AES implementation that can resist the BGE attack. Mulder et al. [8] attacked the Bringer’s implementation with a computational complexity of 217. After that, Xiao and Lai [9] proposed another white-box AES implementation that was cryptanalyzed by Mulder et al. [10] with a computational complexity of 232. Recently, Xu et al. [11] proposed an AES-like cipher by replacing the AES S-boxes and MixColumn matrices with key-dependent components while keeping their good cryptographic properties. They claimed that the white-box implementation of their AES-like cipher can resist current known attacks. In 2014, Luo et al. proposed a new WBAC-oriented AES implementation [12], but Bai et al. [13] showed that the secret key of Luo’s implementation can be recovered with time complexity of approximately 244. The earliest white-box DES implementation was proposed by Chow et al. [14] in 2003. A fault injection attack was used to extract the key from Chow’s implementation by Jacob et al. [15]. In 2005, Link and Neumann [16] put forward an improved white-box DES implementation to resist the fault injection attack. However, Goubin et al. [17] and Wyseur et al. [18] both used differential cryptanalysis to extract the key from the implementation in [16]. In 2019, Amadori et al. [19] present a new DFA attack on a class of white-box implementations presented a new DFA attack on a class of white-box implementations of AES. Lin et al. [20] present an overview of the classic methods for constructing white-box solutions.In terms of new white-box cryptographic algorithms, Biryukov et al. [21] proposed a general method for designing white-box cryptography based on the ASASA (Affine-S-box) structure. They put forward two strong white-box variants of the ASASA symmetric scheme: one is based on Daemen’s quadratic S-boxes and the other is based on random expanding S-boxes. Unfortunately, the ASASA construction was broken in [22, 23]. In 2020, Kwon et al. [24] use parallel table lookups to construct a secure white-box block cipher. Alpirez Bock et al. [25] present the security goals of white-box cryptography. Shi et al. [26] use state-dependent selectable random substitutions (SDSRS) to defeat various related white-box cryptanalytic approaches.Currently, there are few studies on public-key white-box cryptography in the public literature. In 2018, Zhang et al. [27] proposed the first white-box implementation of the identity-based signature scheme. In 2019, Feng et al. [28] proposed a white-box implementation for the classical Shamir’s IBS scheme.


## 1.3. Our Contributions

In this paper, we focus on a white-box implementation of the elliptic curve digital signature algorithm (ECDSA) [29]. ECDSA is the elliptic curve analogue of the digital signature algorithm and can provide integrity, authenticity, and nonrepudiation. The details of ECDSA can be found in several approved standards: ISO 14888-3 [30], ANSI X9.62 [31], IEEE Std 1363-2000 [32], and FIPS 186-2 [33]. Since ECDSA has a small key volume, small storage space, and high-security performance, it has become one of the most important digital signature algorithms.The main contributions of this paper can be summarized as follows: (1) a white-box implementation of ECDSA based on the “cloud plus side” mode is proposed. To protect the security of the private key in ECDSA under the white-box attack context, we use lookup tables and permutations to protect the private key. The permutations are used in both the cloud side and the client side. The private key is confused in a series of lookup tables and is thus able to resist the white-box attack. (2) The storage size of the proposed schemes is reduced by the residue number system. The private key is divided into several small parts by the residue number system. The small part of the private key can be hidden by a smaller size of lookup tables. The storage needed by the proposed scheme is feasible. (3) The security of the proposed scheme is analyzed from aspects of an exhaustive search attack, a random number attack, and a code lifting attack. (4) The efficiency of the proposed scheme is compared with that of the classical ECDSA through experiments. Because of the improved security, the proposed scheme runs slower than the classical ECDSA. The operation speed of the proposed scheme is also acceptable.The paper is organized as follows: in Section2, we briefly review the signature and verification of the classical ECDSA and introduce the concept of the residue number system (RNS). In Section 3, we propose a white-box implementation of ECDSA based on the RNS. The security analysis of our scheme is discussed in Section 4. In Section 5, the efficiency of the proposed scheme is compared with that of the classical ECDSA. Finally, we conclude in Section 6.


## 2. Preliminaries

### 2.1. Classical ECDSA

ECDSA is a digital signature algorithm over an elliptic curve with the domain parametersD=q,FR,a,b,G,n,h, where q is the order of field Fq, FR is the field representation of elements in Fq, a and b are the two coefficients used in an elliptic curve E over Fq (i.e., y2=x3+ax+b in the case of a prime field, and y2+xy=x3+ax2+b in the case of a binary field), G=xG,yG∈EFq has prime order n, and h=#EFq/n is the cofactor. The user randomly selects an integer d∈1,n−1 as the private key, and the corresponding public key is Q=dG. The signature generation and verification of the classical ECDSA are as follows.(1)
ECDSA signature generationInput: Domain parameters D=q,FR,a,b,G,,n,h, private key d, and message m.Output: Signature r,s.(1)
Randomly select an integerk∈1,n−1.(2)
ComputekG=x1,y1 and convert x1 to an integer x1¯.(3)
Computer=x1¯modn. If r=0 then go to (1).(4)
Computek−1modn, where k−1k=1modn.(5)
Computee=Hm, where Hm is the hash value of the message m.(6)
Computes=k−1e+drmodn. If s=0 then go to (1).(7)
Return the signaturer,s.(2)
ECDSA signature verificationInput: Domain parameters D=q,FR,a,b,G,n,h, public key Q, message m, and the signature r,s.Output: “Reject the signature” or “Accept the signature.”(1)
Verify thatr and s are integers in the interval 1,n−1. If any verification fails, then return “Reject the signature.”(2)
Computee=Hm, where Hm is the hash value of the message m.(3)
Computew=s−1, where s−1s=1modn.(4)
Computeu1=ewmodn and u2=rwmodn.(5)
ComputeX=x1,y1=u1G+u2Q.(6)
IfX=∞, then return “Reject the signature.” Otherwise, convert x1 to an integer x1¯ and compute v=x1modn.(7)
Ifv=r then return “Accept the signature”; Else return “Reject the signature.”


### 2.2. Residue Number System

The residue number system (RNS) [34] has been widely studied and used in many applications, such as digital signal processing, multiple precision arithmetic, and parallel computing [35, 36]. An RNS is defined by a set of pairwise coprime integers β=p1,p2,…,pt. The set β is a basis of the RNS, and the elements in β are called the RNS moduli. Any integer x, 0≤x≤P=∏i=1tpi, can be uniquely represented as x=x1,x2,…,xt, where xi is x modulo pi, denoted as xi=xpi. Note that only when x is not more than P and not less than zero can x be uniquely represented by the RNS with the basis β. The original value of x can be restored from x1,x2,…,xt by using the Chinese Remainder Theorem (CRT):(1)x=∑i=1tPixiPi−1pimodP,where Pi=P/pi and Pi⋅Pi−1=1modpi.Assume that integersx and y can be uniquely represented as x=x1,x2,…,xt and y=y1,y2,…,yt under the basis β; then(2)x⊙y=x1⊙y1p1,x2⊙y2p2,…,xt⊙ytpt,where ⊙∈+,−,×.All the operations of ECDSA are performed on the finite fieldFq. In the following, we transform the formulas on the finite field Fq into the residue number system.(1)
Assume the formulas are computed over the integers, that is, without the modq reduction. Let ϖ be the absolute maximum value generated by these operations.(2)
Choose a basisβ=p1,p2,…,pt of the RNS, where P=p1,p2,…,pt≥ϖ.(3)
Represent every integer in RNS format based on the basisβ.(4)
Compute the formula in RNS format, and lety=y1,…,yt be the result.(5)
Restorey by the Chinese Remainder Theorem:y=∑i=1tPiyiPi−1pimodP.(6)
Computey′=ymodq, and return y′.Example. Compute y′=abmod214−3, where a=15242 and b=11213.(1)
Sincea≤214−3 and b≤214−3, the absolute maximum value of ϖ=ab≤214−32=268337161.(2)
Choose a basisβ=p1,p2,…,p8=3,5,7,13,17,19,23,29 of the RNS, where P=3⋅5⋅7⋅13⋅17⋅19⋅23⋅29=294076965>268337161.(3)
Representa as a=2,2,3,6,10,4,16,17, and represent b as b=2,3,6,7,10,3,12,19.(4)
Computey=ab=1,1,4,3,15,12,8,4=y1,y2,…,y8 by equation (2).(5)
Computey=∑i=18PiyiPi−1pimodP=170908546mod294076965 by equation (1).(6)
Computey=170908546mod214−3=5573mod214−3.


## 2.1. Classical ECDSA

ECDSA is a digital signature algorithm over an elliptic curve with the domain parametersD=q,FR,a,b,G,n,h, where q is the order of field Fq, FR is the field representation of elements in Fq, a and b are the two coefficients used in an elliptic curve E over Fq (i.e., y2=x3+ax+b in the case of a prime field, and y2+xy=x3+ax2+b in the case of a binary field), G=xG,yG∈EFq has prime order n, and h=#EFq/n is the cofactor. The user randomly selects an integer d∈1,n−1 as the private key, and the corresponding public key is Q=dG. The signature generation and verification of the classical ECDSA are as follows.(1)
ECDSA signature generationInput: Domain parameters D=q,FR,a,b,G,,n,h, private key d, and message m.Output: Signature r,s.(1)
Randomly select an integerk∈1,n−1.(2)
ComputekG=x1,y1 and convert x1 to an integer x1¯.(3)
Computer=x1¯modn. If r=0 then go to (1).(4)
Computek−1modn, where k−1k=1modn.(5)
Computee=Hm, where Hm is the hash value of the message m.(6)
Computes=k−1e+drmodn. If s=0 then go to (1).(7)
Return the signaturer,s.(2)
ECDSA signature verificationInput: Domain parameters D=q,FR,a,b,G,n,h, public key Q, message m, and the signature r,s.Output: “Reject the signature” or “Accept the signature.”(1)
Verify thatr and s are integers in the interval 1,n−1. If any verification fails, then return “Reject the signature.”(2)
Computee=Hm, where Hm is the hash value of the message m.(3)
Computew=s−1, where s−1s=1modn.(4)
Computeu1=ewmodn and u2=rwmodn.(5)
ComputeX=x1,y1=u1G+u2Q.(6)
IfX=∞, then return “Reject the signature.” Otherwise, convert x1 to an integer x1¯ and compute v=x1modn.(7)
Ifv=r then return “Accept the signature”; Else return “Reject the signature.”


## 2.2. Residue Number System

The residue number system (RNS) [34] has been widely studied and used in many applications, such as digital signal processing, multiple precision arithmetic, and parallel computing [35, 36]. An RNS is defined by a set of pairwise coprime integers β=p1,p2,…,pt. The set β is a basis of the RNS, and the elements in β are called the RNS moduli. Any integer x, 0≤x≤P=∏i=1tpi, can be uniquely represented as x=x1,x2,…,xt, where xi is x modulo pi, denoted as xi=xpi. Note that only when x is not more than P and not less than zero can x be uniquely represented by the RNS with the basis β. The original value of x can be restored from x1,x2,…,xt by using the Chinese Remainder Theorem (CRT):(1)x=∑i=1tPixiPi−1pimodP,where Pi=P/pi and Pi⋅Pi−1=1modpi.Assume that integersx and y can be uniquely represented as x=x1,x2,…,xt and y=y1,y2,…,yt under the basis β; then(2)x⊙y=x1⊙y1p1,x2⊙y2p2,…,xt⊙ytpt,where ⊙∈+,−,×.All the operations of ECDSA are performed on the finite fieldFq. In the following, we transform the formulas on the finite field Fq into the residue number system.(1)
Assume the formulas are computed over the integers, that is, without the modq reduction. Let ϖ be the absolute maximum value generated by these operations.(2)
Choose a basisβ=p1,p2,…,pt of the RNS, where P=p1,p2,…,pt≥ϖ.(3)
Represent every integer in RNS format based on the basisβ.(4)
Compute the formula in RNS format, and lety=y1,…,yt be the result.(5)
Restorey by the Chinese Remainder Theorem:y=∑i=1tPiyiPi−1pimodP.(6)
Computey′=ymodq, and return y′.Example. Compute y′=abmod214−3, where a=15242 and b=11213.(1)
Sincea≤214−3 and b≤214−3, the absolute maximum value of ϖ=ab≤214−32=268337161.(2)
Choose a basisβ=p1,p2,…,p8=3,5,7,13,17,19,23,29 of the RNS, where P=3⋅5⋅7⋅13⋅17⋅19⋅23⋅29=294076965>268337161.(3)
Representa as a=2,2,3,6,10,4,16,17, and represent b as b=2,3,6,7,10,3,12,19.(4)
Computey=ab=1,1,4,3,15,12,8,4=y1,y2,…,y8 by equation (2).(5)
Computey=∑i=18PiyiPi−1pimodP=170908546mod294076965 by equation (1).(6)
Computey=170908546mod214−3=5573mod214−3.


## 3. White-Box Implementation of ECDSA Based on the Residue Number System

### 3.1. Hide the Private Key

In the white-box attack context, attackers can completely access the implementation of ECDSA and know all the intermediate results of the algorithm. The attacker’s objective is to extract the private key or forge a legitimate signature. From the details of ECDSA above, we know that the user’s private keyd is used only in step (6) of the process of ECDSA signature generation. Hence, to protect the security of ECDSA under the white-box attack context, we need to protect only the security of private key d during the procedure of computing:(3)s=k−1e+drmodn.Similar to most white-box cryptographic schemes, the private keyd in our scheme is hidden in lookup tables T1,T2,…,Tt (see Table 1). Let β=p1,p2,…,pt be a basis of the RNS, let ℤpi be the prime field with order pi, and the private key d can be represented as d=d1,…,dt, where di=dmodpi. Let fi:ℤpi⟶ℤpi and gi:ℤpi⟶ℤpi be two permutations on ℤpi; fi−1 and gi−1 are the inverse mappings of fi and gi, respectively. An example of the table Ti generation pseudocode is as follows:forj=1 to pi dofork=1 to pi doTij,k=fi−1j+gi−1kdimodpi,end for;end for.Table 1
Lookup tableTi, i=1,…,t.
IndexValue1,1Ti1,1=fi−11+gi−11dimodpi1,2Ti1,2=fi−11+gi−12dimodpi1,3Ti1,3=fi−11+gi−13dimodpi⋯⋯1,piTi1,pi=fi−11+gi−1pidimodpi2,1Ti2,1=fi−12+gi−11dimodpi2,2Ti2,2=fi−12+gi−12dimodpi2,3Ti2,3=fi−12+gi−13dimodpi⋯⋯2,piTi2,pi=fi−12+gi−1pidimodpi⋯⋯pi,1Tipi,1=fi−1pi+gi−11dimodpipi,2Tipi,2=fi−1pi+gi−12dimodpipi,3Tipi,3=fi−1pi+gi−13dimodpi⋯⋯pi,piTipi,pi=fi−1pi+gi−1pidimodpiNote that the tableTi hides not only part of the private key di but also the permutations fi−1 and gi−1. If the permutations fi−1 and gi−1 are unknown, the attackers cannot derive the private key di by the input and output of table Ti. Since 1≤j,k,Tij,k≤pi, the storage space of table Ti is less than pi2log2pi bits. Moreover, the whole storage space of T1,…,Tt is less than ∑i=1tpi2log2pi bits.


### 3.2. Protect the Random Numberk

Attackers can obtain the final signaturer,s in the white-box attack context. To protect the private key d, we also need to protect the random number k used in the process of ECDSA signature generation. Otherwise, according to equation (3), the private key d=r−1ks−emodn is easy to calculate by attackers. We use the “cloud plus side” mode to protect it. k is decomposed into two parts, namely, k1 and k2, where k1 is generated by the client and k2 is generated by the cloud server. In the step of signature generation, the inverse of k2 needs to be sent to the client. In order to prevent attackers in the client recovering k=k1⋅k2, we use a series of permutations to protect k2.


### 3.3. Our Scheme

In the following, we always assume that the cloud server is semihonest [37]. That is, (1) the cloud server stores the data without tampering with it; (2) the cloud server honestly executes every operation; and (3) the cloud server tries to learn the underlying information of the user data. In addition, the client is in a white-box attack context.Now, we propose a white-box implementation of ECDSA. Before signing a message, we need an initialization phase to convert the private keyd into a series of lookup tables T1,T2,…,Tt. A trusted third party (TTP) is needed in the initialization phase (see Figure 1). The initialization phase is performed in a secure environment.Figure 1
Initialization.Initialization:Input: Private key d.Output: A basis of the RNS {p1,p2,…,pt}, the permutations {f1,f2,…,ft} and {g1,g2,…,gt}, and the lookup tables {T1,T2,…,Tt}.(1)
Client sends the private keyd to TTP through a secure channel;(2)
TTP randomly selects co-prime integersp1,p2,…,pt as a basis of the RNS, where P=p1p2…pt≥n2+n;(3)
TTP randomly selects permutationsfi and gi on ℤpi, i=1,…,t;(4)
TTP represents the private key asd=d1,d2,…,dt according to the basis β=p1,p2,…,pt, where di=dmodpi;(5)
TTP constructs tableTi as follows:Tij,k=fi−1j+gi−1kdimodpi,wherefi−1 and gi−1 are the inverse mappings of fi and gi, respectively, with j=1,…,pi, k=1,…,pi;(6)
TTP sends tablesT1,…,Tt to client and sends permutations f1,…,ft and g1,…,gt to the cloud server through a secure channel. TTP then publishes the basis β=p1,p2,…,pt.The white-box implementation of ECDSA based on the RNS is as follows (see Figure2).Figure 2
The white-box implementation of ECDSA based on RNS.Signature generation:Input: Domain parameters D=q,FR,a,b,G,n,h, basis β=p1,p2,…,pt, and message m.Output: Signature r^,s^.(1)
Client computese=Hm, where Hm is the hash value of the message m.(2)
Client randomly selects an integerk1∈1,n−1.(3)
Client computesP=k1G.(4)
Client sendse and P to the cloud server.(5)
Cloud server randomly selects an integerk2∈1,n−1.(6)
Cloud server computesR=x1,y1=k2P and converts x1 to an integer x1¯.(7)
Cloud server computes the first part of the signaturer^=x1¯modn. If r^=0, then go to (2).(8)
Cloud server computesk2−1, where k2−1k2=1modn.(9)
Cloud server computesu=k2−1emodn,v=k2−1r^modn.(10)
Cloud server representsu under the basis β as u=u1,…,ut and confuses ui by permutation fi, i.e., fiui. Similarly, cloud server represents v under the basis β as v=v1,…,vt and confuses vi by permutation gi, i.e., givi.(11)
Cloud server sendsr^, f1u1, …, ftut, g1v1, …, gtvt to client.(12)
Client computeswi=fi−1fiui+gi−1gividimodpi by looking up table Ti, where the input of table Ti is fiui,givi and the output of table Ti is wi, where di=dmodpi, i=1,…,t.(13)
Client restoresw by Chinese Remainder Theorem.(14)
Client computesk1−1, where k1−1k1=1modn.(15)
Client computes the second part of the signatures^=k1−1wmodn. If s^=0, then go to (2).(16)
Client returns the signaturer^,s^.From the above steps, the private keyd does not appear in plaintext. If the basis β and permutations f1,…,ft and g1,…,gt are fixed, then tables T1,…,Tt correspond to the private key d are fixed. Tables T1,…,Tt are completely presented by the client, so attackers on the cloud server cannot directly obtain any information about the private key d.Letk=k1k2; then, R=k2P=k2k1G=kG. It is obvious that the first part of the signature is the same in the classical ECDSA and in our scheme.In the classical ECDSA signature generation algorithm, the second part of the signature is(4)s=k−1e+drmodn=k1−1k2−1e+drmodn=k1−1k2−1e+k2−1rdmodn=k1−1u+vdmodn.Letw¯=u+vdmodn. If w¯=w, then s=s^. We claim that w¯=w. Since u,v,d≤n, u+vd≤n2+n. Note that the basis β=p1,…,pt satisfies P=p1…pt≥n2+n. Using RNS theory, we can restore w¯ by w1¯,…,wt¯, where wi¯=ui+vidimodpi, ui=umodpi, vi=vmodpi, and di=dmodpi, with i=1,…,t. Since(5)wi¯=ui+vidimodpi=fi−1fiui+gi−1gividimodpi=wi,then w¯=w.)Thus, the resultr^,s^ of the white-box implementation of ECDSA signature generation is consistent with the result r,s of the classical ECDSA signature generation. One advantage of our scheme is that we can directly use the classical ECDSA signature verification algorithm to verify the signature r^,s^.


## 3.1. Hide the Private Key

In the white-box attack context, attackers can completely access the implementation of ECDSA and know all the intermediate results of the algorithm. The attacker’s objective is to extract the private key or forge a legitimate signature. From the details of ECDSA above, we know that the user’s private keyd is used only in step (6) of the process of ECDSA signature generation. Hence, to protect the security of ECDSA under the white-box attack context, we need to protect only the security of private key d during the procedure of computing:(3)s=k−1e+drmodn.Similar to most white-box cryptographic schemes, the private keyd in our scheme is hidden in lookup tables T1,T2,…,Tt (see Table 1). Let β=p1,p2,…,pt be a basis of the RNS, let ℤpi be the prime field with order pi, and the private key d can be represented as d=d1,…,dt, where di=dmodpi. Let fi:ℤpi⟶ℤpi and gi:ℤpi⟶ℤpi be two permutations on ℤpi; fi−1 and gi−1 are the inverse mappings of fi and gi, respectively. An example of the table Ti generation pseudocode is as follows:forj=1 to pi dofork=1 to pi doTij,k=fi−1j+gi−1kdimodpi,end for;end for.Table 1
Lookup tableTi, i=1,…,t.
IndexValue1,1Ti1,1=fi−11+gi−11dimodpi1,2Ti1,2=fi−11+gi−12dimodpi1,3Ti1,3=fi−11+gi−13dimodpi⋯⋯1,piTi1,pi=fi−11+gi−1pidimodpi2,1Ti2,1=fi−12+gi−11dimodpi2,2Ti2,2=fi−12+gi−12dimodpi2,3Ti2,3=fi−12+gi−13dimodpi⋯⋯2,piTi2,pi=fi−12+gi−1pidimodpi⋯⋯pi,1Tipi,1=fi−1pi+gi−11dimodpipi,2Tipi,2=fi−1pi+gi−12dimodpipi,3Tipi,3=fi−1pi+gi−13dimodpi⋯⋯pi,piTipi,pi=fi−1pi+gi−1pidimodpiNote that the tableTi hides not only part of the private key di but also the permutations fi−1 and gi−1. If the permutations fi−1 and gi−1 are unknown, the attackers cannot derive the private key di by the input and output of table Ti. Since 1≤j,k,Tij,k≤pi, the storage space of table Ti is less than pi2log2pi bits. Moreover, the whole storage space of T1,…,Tt is less than ∑i=1tpi2log2pi bits.


## 3.2. Protect the Random Numberk

Attackers can obtain the final signaturer,s in the white-box attack context. To protect the private key d, we also need to protect the random number k used in the process of ECDSA signature generation. Otherwise, according to equation (3), the private key d=r−1ks−emodn is easy to calculate by attackers. We use the “cloud plus side” mode to protect it. k is decomposed into two parts, namely, k1 and k2, where k1 is generated by the client and k2 is generated by the cloud server. In the step of signature generation, the inverse of k2 needs to be sent to the client. In order to prevent attackers in the client recovering k=k1⋅k2, we use a series of permutations to protect k2.


## 3.3. Our Scheme

In the following, we always assume that the cloud server is semihonest [37]. That is, (1) the cloud server stores the data without tampering with it; (2) the cloud server honestly executes every operation; and (3) the cloud server tries to learn the underlying information of the user data. In addition, the client is in a white-box attack context.Now, we propose a white-box implementation of ECDSA. Before signing a message, we need an initialization phase to convert the private keyd into a series of lookup tables T1,T2,…,Tt. A trusted third party (TTP) is needed in the initialization phase (see Figure 1). The initialization phase is performed in a secure environment.Figure 1
Initialization.Initialization:Input: Private key d.Output: A basis of the RNS {p1,p2,…,pt}, the permutations {f1,f2,…,ft} and {g1,g2,…,gt}, and the lookup tables {T1,T2,…,Tt}.(1)
Client sends the private keyd to TTP through a secure channel;(2)
TTP randomly selects co-prime integersp1,p2,…,pt as a basis of the RNS, where P=p1p2…pt≥n2+n;(3)
TTP randomly selects permutationsfi and gi on ℤpi, i=1,…,t;(4)
TTP represents the private key asd=d1,d2,…,dt according to the basis β=p1,p2,…,pt, where di=dmodpi;(5)
TTP constructs tableTi as follows:Tij,k=fi−1j+gi−1kdimodpi,wherefi−1 and gi−1 are the inverse mappings of fi and gi, respectively, with j=1,…,pi, k=1,…,pi;(6)
TTP sends tablesT1,…,Tt to client and sends permutations f1,…,ft and g1,…,gt to the cloud server through a secure channel. TTP then publishes the basis β=p1,p2,…,pt.The white-box implementation of ECDSA based on the RNS is as follows (see Figure2).Figure 2
The white-box implementation of ECDSA based on RNS.Signature generation:Input: Domain parameters D=q,FR,a,b,G,n,h, basis β=p1,p2,…,pt, and message m.Output: Signature r^,s^.(1)
Client computese=Hm, where Hm is the hash value of the message m.(2)
Client randomly selects an integerk1∈1,n−1.(3)
Client computesP=k1G.(4)
Client sendse and P to the cloud server.(5)
Cloud server randomly selects an integerk2∈1,n−1.(6)
Cloud server computesR=x1,y1=k2P and converts x1 to an integer x1¯.(7)
Cloud server computes the first part of the signaturer^=x1¯modn. If r^=0, then go to (2).(8)
Cloud server computesk2−1, where k2−1k2=1modn.(9)
Cloud server computesu=k2−1emodn,v=k2−1r^modn.(10)
Cloud server representsu under the basis β as u=u1,…,ut and confuses ui by permutation fi, i.e., fiui. Similarly, cloud server represents v under the basis β as v=v1,…,vt and confuses vi by permutation gi, i.e., givi.(11)
Cloud server sendsr^, f1u1, …, ftut, g1v1, …, gtvt to client.(12)
Client computeswi=fi−1fiui+gi−1gividimodpi by looking up table Ti, where the input of table Ti is fiui,givi and the output of table Ti is wi, where di=dmodpi, i=1,…,t.(13)
Client restoresw by Chinese Remainder Theorem.(14)
Client computesk1−1, where k1−1k1=1modn.(15)
Client computes the second part of the signatures^=k1−1wmodn. If s^=0, then go to (2).(16)
Client returns the signaturer^,s^.From the above steps, the private keyd does not appear in plaintext. If the basis β and permutations f1,…,ft and g1,…,gt are fixed, then tables T1,…,Tt correspond to the private key d are fixed. Tables T1,…,Tt are completely presented by the client, so attackers on the cloud server cannot directly obtain any information about the private key d.Letk=k1k2; then, R=k2P=k2k1G=kG. It is obvious that the first part of the signature is the same in the classical ECDSA and in our scheme.In the classical ECDSA signature generation algorithm, the second part of the signature is(4)s=k−1e+drmodn=k1−1k2−1e+drmodn=k1−1k2−1e+k2−1rdmodn=k1−1u+vdmodn.Letw¯=u+vdmodn. If w¯=w, then s=s^. We claim that w¯=w. Since u,v,d≤n, u+vd≤n2+n. Note that the basis β=p1,…,pt satisfies P=p1…pt≥n2+n. Using RNS theory, we can restore w¯ by w1¯,…,wt¯, where wi¯=ui+vidimodpi, ui=umodpi, vi=vmodpi, and di=dmodpi, with i=1,…,t. Since(5)wi¯=ui+vidimodpi=fi−1fiui+gi−1gividimodpi=wi,then w¯=w.)Thus, the resultr^,s^ of the white-box implementation of ECDSA signature generation is consistent with the result r,s of the classical ECDSA signature generation. One advantage of our scheme is that we can directly use the classical ECDSA signature verification algorithm to verify the signature r^,s^.


## 4. Security Analysis

### 4.1. The Security in the Cloud Server and the Client

Firstly, we analyze the security of our scheme from the aspects of the cloud server and the client. We assume that the client is in a white-box attack context and that the cloud server is semihonest. The goal of attackers is to extract the private keyd. The security of our scheme is based on the difficulty of the discrete logarithm problem for elliptic curves (ECDLP) and the diversity of permutations.


#### 4.1.1. The Security in the Cloud Server

From the details of our scheme, attackers in the cloud server can obtain the information ofe, P, k2, r^, and s^. Moreover, the following equation holds:(6)s^=k1−1k2−1e+dr^modn.If attackers can obtain the value ofk1, they can extract the private key d=r^−1k1k2s^−emodn from equation (6). Fortunately, because of the difficulty of the elliptic curve discrete logarithm, attackers cannot calculate k1 by P=k1G.


#### 4.1.2. The Security in the Client

From the details of our scheme, attackers in the client can obtain the information ofT1,…,Tt, e, k1, f1u1, …, ftut, g1v1, …, gtvt, r^, and s^. There seem to be two ways for attackers to compute the private key: (i) from tables T1,…,Tt and (ii) from equation (6).In case (i), tableTi is constructed by(7)Tij,k=fi−1i+gi−1kdimodpi,where i=1,…,t,j=1,…,pi,k=1,…,pi. After the initialization phase, the key di and permutations fi and gi are hidden in Ti. Since the permutations fi and gi are unknown to the client, attackers in the client cannot derive the key di from table Ti directly. The diversity of permutation fi (or gi) is pi!. Hence, the complexity of deriving di is pi!2 through an exhaustive search attack. The computational complexity of extracting the private key d from case (i) is ∏i=1tpi!2.In case (ii), if attackers can obtain the value ofk2, they can extract the private key d from equation (6). For the client, the information of k2 is hidden in f1u1, …, ftut, g1v1, …, gtvt, where u=k2−1e=u1,…,ut and v=k2−1r^=v1,…,vt. Since the permutations are unknown to the client, the complexity of deriving k2 is ∏i=1tpi! through an exhaustive search attack. The computational complexity of extracting the private key d from case (ii) is ∏i=1tpi!.Remark. The proposed scheme is a kind of cloud collaboration. The secret key is stored completely in the client in a form of lookup table. The attackers in the client cannot get the plaintext information of the key from the lookup table. At the same time, even if the cloud is untrusted, the attacker in the cloud cannot obtain any information about the key. So, the proposed scheme alleviates the problems of local key disclosure and identity authentication in general cloud collaboration.


### 4.2. Random Number Attack

In the classical ECDSA, the random integerk must be different for different messages. Assume that, for different messages m′ and m″, we select the same random integer k to sign. Then, we have(8)s′=k−1e′+rdmodn.s″=k−1e″+rdmodn.Thus,d=s′−s″−1r−1s″e′−s′e″modn. Usually, the information of e′, e″, r,s′, and r,s″ is public; thus, attackers can easily obtain the information of the private key d.In the white-box implementation of ECDSA, the random integersk1 and k2 are generated by the client and cloud server, respectively. For two messages m′ and m″, assume that k1′ and k2′ are used to compute the signature r′^,s′^ of m′ and that k1″ and k2″ are used to compute the signature r″^,s″^ of m″. Then, we have(9)s′^=k1′−1k2′−1e′+dr′^modn,s″^=k1″−1k2″−1e″+dr″^modn.Under the white-box attack context, the attackers in the client can obtain the information ofk1′, k1′′, e′, e″, r′^,s′^, and r″^,s″^, and the attackers in the cloud server can obtain the information of k2′, k2′′, e′, e″, r′^,s′^, and r″^,s″^. We analyze the security of private key d in the following four cases:(i)
k1′=k1″, k2′=k2″:From equation (9), we have d=s′^r″^−s″^r′^−1s″^e′−s′^e″modn. Thus, attackers in the client or the cloud server can derive the private key d under the white-box attack context.(ii)
k1′=k1″, k2′≠k2″:From equation (9), we have d=s′^k2′r″^−s″^k2″r′^−1s″^k2″e′−s′^k2′e″modn. Thus, attackers in the cloud server can derive the private key d under the white-box attack context.(iii)
k1′≠k1″, k2′=k2″:From equation (9), we have d=s′^k1′r″^−s″^k1″r′^−1s″^k1″e′−s′^k1′e″modn. Thus, attackers in the client can derive the private key d under the white-box attack context.(iv)
k1′≠k1″, k2′≠k2″:Regardless of whether the attackers are in the client or the cloud server, they cannot simultaneously obtain the information of k1′, k1″, k2′, and k2″. Thus, attackers cannot obtain the information of private key d from equation (9) under the white-box attack context.In summary, the random integersk1 and k2 used in our scheme must be different for different messages.


### 4.3. Code Lifting Attack

One of the main purposes of the white-box cryptography is to protect the security of the algorithm implemented in the software used. It is well known that the algorithm implemented in the software is at risk of a code lifting attack (i.e., the entire code will be extracted and used as an equivalent secret key). To resist the code lifting attack, one common method is to bind the hardware information to the code. The method can also be used in the white-box implementation of ECDSA. Only two steps of our scheme proposed in Section3 need to be modified: (i) the construction of table T1,…,Tt in the initialization phase and (ii) step (13) in the signature generation phase.(i)
The new lookup tablesT1′,…,Tt′ contain not only the private key d=d1,…,dt but also the unique identification information of the device HI=HI1,…,HIt, where HIi=HImodpi. The new lookup table Ti′ is constructed as follows:(10)Ti′j,k=fi−1j+gi−1kdi+HIimodpi,wherei=1,…,t, j=1,…,pi, and k=1,…,pi.(ii)
The new step (13) is as follows: client restoresw by Chinese Remainder Theorem and computes w′=w−HImodn.It is easy to check the correctness of the new scheme. The HI is hidden in lookup tablesT1′,…,Tt′. For each signature, the HI must be correctly extracted from the device. Through the hardware binding method, the code lifting attack can be mitigated in the white-box implementation of ECDSA.


## 4.1. The Security in the Cloud Server and the Client

Firstly, we analyze the security of our scheme from the aspects of the cloud server and the client. We assume that the client is in a white-box attack context and that the cloud server is semihonest. The goal of attackers is to extract the private keyd. The security of our scheme is based on the difficulty of the discrete logarithm problem for elliptic curves (ECDLP) and the diversity of permutations.


### 4.1.1. The Security in the Cloud Server

From the details of our scheme, attackers in the cloud server can obtain the information ofe, P, k2, r^, and s^. Moreover, the following equation holds:(6)s^=k1−1k2−1e+dr^modn.If attackers can obtain the value ofk1, they can extract the private key d=r^−1k1k2s^−emodn from equation (6). Fortunately, because of the difficulty of the elliptic curve discrete logarithm, attackers cannot calculate k1 by P=k1G.


### 4.1.2. The Security in the Client

From the details of our scheme, attackers in the client can obtain the information ofT1,…,Tt, e, k1, f1u1, …, ftut, g1v1, …, gtvt, r^, and s^. There seem to be two ways for attackers to compute the private key: (i) from tables T1,…,Tt and (ii) from equation (6).In case (i), tableTi is constructed by(7)Tij,k=fi−1i+gi−1kdimodpi,where i=1,…,t,j=1,…,pi,k=1,…,pi. After the initialization phase, the key di and permutations fi and gi are hidden in Ti. Since the permutations fi and gi are unknown to the client, attackers in the client cannot derive the key di from table Ti directly. The diversity of permutation fi (or gi) is pi!. Hence, the complexity of deriving di is pi!2 through an exhaustive search attack. The computational complexity of extracting the private key d from case (i) is ∏i=1tpi!2.In case (ii), if attackers can obtain the value ofk2, they can extract the private key d from equation (6). For the client, the information of k2 is hidden in f1u1, …, ftut, g1v1, …, gtvt, where u=k2−1e=u1,…,ut and v=k2−1r^=v1,…,vt. Since the permutations are unknown to the client, the complexity of deriving k2 is ∏i=1tpi! through an exhaustive search attack. The computational complexity of extracting the private key d from case (ii) is ∏i=1tpi!.Remark. The proposed scheme is a kind of cloud collaboration. The secret key is stored completely in the client in a form of lookup table. The attackers in the client cannot get the plaintext information of the key from the lookup table. At the same time, even if the cloud is untrusted, the attacker in the cloud cannot obtain any information about the key. So, the proposed scheme alleviates the problems of local key disclosure and identity authentication in general cloud collaboration.


## 4.1.1. The Security in the Cloud Server

From the details of our scheme, attackers in the cloud server can obtain the information ofe, P, k2, r^, and s^. Moreover, the following equation holds:(6)s^=k1−1k2−1e+dr^modn.If attackers can obtain the value ofk1, they can extract the private key d=r^−1k1k2s^−emodn from equation (6). Fortunately, because of the difficulty of the elliptic curve discrete logarithm, attackers cannot calculate k1 by P=k1G.


## 4.1.2. The Security in the Client

From the details of our scheme, attackers in the client can obtain the information ofT1,…,Tt, e, k1, f1u1, …, ftut, g1v1, …, gtvt, r^, and s^. There seem to be two ways for attackers to compute the private key: (i) from tables T1,…,Tt and (ii) from equation (6).In case (i), tableTi is constructed by(7)Tij,k=fi−1i+gi−1kdimodpi,where i=1,…,t,j=1,…,pi,k=1,…,pi. After the initialization phase, the key di and permutations fi and gi are hidden in Ti. Since the permutations fi and gi are unknown to the client, attackers in the client cannot derive the key di from table Ti directly. The diversity of permutation fi (or gi) is pi!. Hence, the complexity of deriving di is pi!2 through an exhaustive search attack. The computational complexity of extracting the private key d from case (i) is ∏i=1tpi!2.In case (ii), if attackers can obtain the value ofk2, they can extract the private key d from equation (6). For the client, the information of k2 is hidden in f1u1, …, ftut, g1v1, …, gtvt, where u=k2−1e=u1,…,ut and v=k2−1r^=v1,…,vt. Since the permutations are unknown to the client, the complexity of deriving k2 is ∏i=1tpi! through an exhaustive search attack. The computational complexity of extracting the private key d from case (ii) is ∏i=1tpi!.Remark. The proposed scheme is a kind of cloud collaboration. The secret key is stored completely in the client in a form of lookup table. The attackers in the client cannot get the plaintext information of the key from the lookup table. At the same time, even if the cloud is untrusted, the attacker in the cloud cannot obtain any information about the key. So, the proposed scheme alleviates the problems of local key disclosure and identity authentication in general cloud collaboration.


## 4.2. Random Number Attack

In the classical ECDSA, the random integerk must be different for different messages. Assume that, for different messages m′ and m″, we select the same random integer k to sign. Then, we have(8)s′=k−1e′+rdmodn.s″=k−1e″+rdmodn.Thus,d=s′−s″−1r−1s″e′−s′e″modn. Usually, the information of e′, e″, r,s′, and r,s″ is public; thus, attackers can easily obtain the information of the private key d.In the white-box implementation of ECDSA, the random integersk1 and k2 are generated by the client and cloud server, respectively. For two messages m′ and m″, assume that k1′ and k2′ are used to compute the signature r′^,s′^ of m′ and that k1″ and k2″ are used to compute the signature r″^,s″^ of m″. Then, we have(9)s′^=k1′−1k2′−1e′+dr′^modn,s″^=k1″−1k2″−1e″+dr″^modn.Under the white-box attack context, the attackers in the client can obtain the information ofk1′, k1′′, e′, e″, r′^,s′^, and r″^,s″^, and the attackers in the cloud server can obtain the information of k2′, k2′′, e′, e″, r′^,s′^, and r″^,s″^. We analyze the security of private key d in the following four cases:(i)
k1′=k1″, k2′=k2″:From equation (9), we have d=s′^r″^−s″^r′^−1s″^e′−s′^e″modn. Thus, attackers in the client or the cloud server can derive the private key d under the white-box attack context.(ii)
k1′=k1″, k2′≠k2″:From equation (9), we have d=s′^k2′r″^−s″^k2″r′^−1s″^k2″e′−s′^k2′e″modn. Thus, attackers in the cloud server can derive the private key d under the white-box attack context.(iii)
k1′≠k1″, k2′=k2″:From equation (9), we have d=s′^k1′r″^−s″^k1″r′^−1s″^k1″e′−s′^k1′e″modn. Thus, attackers in the client can derive the private key d under the white-box attack context.(iv)
k1′≠k1″, k2′≠k2″:Regardless of whether the attackers are in the client or the cloud server, they cannot simultaneously obtain the information of k1′, k1″, k2′, and k2″. Thus, attackers cannot obtain the information of private key d from equation (9) under the white-box attack context.In summary, the random integersk1 and k2 used in our scheme must be different for different messages.


## 4.3. Code Lifting Attack

One of the main purposes of the white-box cryptography is to protect the security of the algorithm implemented in the software used. It is well known that the algorithm implemented in the software is at risk of a code lifting attack (i.e., the entire code will be extracted and used as an equivalent secret key). To resist the code lifting attack, one common method is to bind the hardware information to the code. The method can also be used in the white-box implementation of ECDSA. Only two steps of our scheme proposed in Section3 need to be modified: (i) the construction of table T1,…,Tt in the initialization phase and (ii) step (13) in the signature generation phase.(i)
The new lookup tablesT1′,…,Tt′ contain not only the private key d=d1,…,dt but also the unique identification information of the device HI=HI1,…,HIt, where HIi=HImodpi. The new lookup table Ti′ is constructed as follows:(10)Ti′j,k=fi−1j+gi−1kdi+HIimodpi,wherei=1,…,t, j=1,…,pi, and k=1,…,pi.(ii)
The new step (13) is as follows: client restoresw by Chinese Remainder Theorem and computes w′=w−HImodn.It is easy to check the correctness of the new scheme. The HI is hidden in lookup tablesT1′,…,Tt′. For each signature, the HI must be correctly extracted from the device. Through the hardware binding method, the code lifting attack can be mitigated in the white-box implementation of ECDSA.


## 5. Performance Evaluation

In this section, we analyze the performance of our proposed scheme and compare it with the classical ECDSA [31]. The simulation is programmed by C language. Visual Studio 2015 is administered on a PC with an Intel Core i7-6700 3.40 GHz CPU and Windows 10 operating system using the MIRACL library. SM3 algorithm is used to calculate the hash values of the messages.The domain parametersD=q,FR,a,b,G,n,h on the elliptic curve y2=x3+ax+b, and the basis β of RNS are shown in Table 2. The size of the lookup table is about 35.4 MB. We run each experiment 100 times and calculate the average. All the times reported in Tables 3 and 4 are averages.Table 2
Domain parametersD=q,FR,a,b,G,n,h and basis β of RNS.
ParametersValueq0x 80000000 00000000 00000000 0000000000000000 00000000 00000000 00001103FRInteger representationa0b3xG0x 2BB687F3 4C71B55A 06E63561 EBE3144EE1AA9C00 3C165107 2EE3631A A2729B88yG0x 13FC9FB0 9308BC19 59B42204 8D81BDA5B6A2183F 1DBCADD8 2C245EC3 3CEB8E60n0x 80000000 00000000 00000000 000000016288AEDF 18093517 F7A3E3CF F023CBFFh1β{97, 113, 127, 131, 137, 139, 149, 151, 157, 163,167, 173, 179, 181, 191, 193, 197, 199, 211, 223,227, 229, 233, 239, 241, 251, 257, 263, 269, 271,277, 281, 283, 293, 307, 311, 313, 317, 331, 337,347, 349, 353, 359, 367, 373, 379, 383, 389, 397,401, 409, 419, 421, 431, 433, 439, 443, 449, 457,461, 463, 467, 479}Table 3
Comparison of computation cost.
SchemeOperationClassical ECDSA(in millisecond)Our scheme (in millisecond)Initialization04881.18Signature generation5.111749.61Signature verification5.986.07Table 4
Comparison of signature generation cost.
The size of message (KB)Classical ECDSA (in millisecond)Our scheme (in millisecond)12.991742.20103.191758.441004.791766.13120.901797.6810195.271980.051001857.293641.08118547.5420430.23In Table3, we compare the computation cost of our scheme with the classical ECDSA, where the size of the message is 100 KB. The classic ECDSA includes two stages: signature generation and signature verification. Compared with the classical ECDSA, our scheme proposed in Section 3 has one more stage: initialization. As shown in Table 3, the time of initialization of our scheme is 4881.18 milliseconds, which is the main cost of our scheme. Fortunately, this stage is usually executed by a TTP who possesses strong processing capability, so the time will be shorten. What is more, the initialization stage needs to be executed again only when the user needs to change the key. The user’s private key is not often replaced in the actual application scenario, so the time of initialization is acceptable. The times of signature generation in classical ECDSA and our scheme are 5.11 milliseconds and 1749.61 milliseconds, respectively. Although the calculation time of our scheme is more, the security of the proposed scheme is higher. Note that the signature verification is the same in two schemes, so the times of signature verification are essentially equal.In Table4, we analyze the signature generation time of the message with different sizes, that is, 1 kB, 10 kB, 100 kB, 1 M, 10 M, 100 M, and 1 GB. The longer the size of the message is, the longer it takes to compute the hash value of the message. So, the time of signature generation is increasing when the size of the message is increasing in two schemes. Generally, our scheme takes an extra 1.7 to 1.9 seconds in the phase of signature generation.


## 6. Conclusions

A white-box implementation of ECDSA based on the RNS in the “cloud plus side” mode is proposed. Not only it can protect the security of the private key under the white-box attack context, but also it has good compatibility, has a low communication cost, and requires a small storage space. The proposed techniques can be extended to Schnorr signatures [38] or other ElGamal-based schemes [39]. The study of the white-box implementation of ECDSA can provide powerful theoretical support for the software implementation of the digital signature algorithm and expand the applied scenario of ECDSA. However, the white-box implementation of public-key cryptography is still in the preliminary stage, and its security analysis method is not complete. Our future work will focus on the definition and the security analysis of white-box public-key cryptography.



---

*Source: 8881116-2020-11-19.xml*