Hardware Security for eXtended Merkle Signature Scheme Using SRAM-based PUFs and TRNGs

Depósito de investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of an article published by IEEE in Proceedings of the International Conference on Microelectronics, ICM on 18 December 2020, available at: https://doi.org/10.1109/ICM50269.2020.9331821 “© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other Works” Hardware Security for eXtended Merkle Signature Scheme Using SRAM-based PUFs and TRNGs Roberto Román, Rosario Arjona, Javier Arcenegui , Iluminada Baturone Instituto de Microelectrónica de Sevilla (IMSE-CNM) University of Seville, CSIC Seville, Spain {roman, arjona, arcenegui, lumi}@imse-cnm.csic.es Abstract— Due to the expansion of the Internet of Things (IoT), there is an increasing number of interconnected devices around us. Integrity, authentication and non-repudiation of data exchanged between them is becoming a must. This can be achieved by means of digital signatures. In recent years, the eXtended Merkle Signature Scheme (XMSS) has gained popularity in embedded systems because of its simple implementation, post-quantum security, and minimal security assumptions. From a hardware point of view, the security of digital signatures strongly depends on how the private keys are generated and stored. In this work, we propose the use of SRAMs as True Random Generators (TRNGs) and Physically Unclonable Functions (PUFs) to generate and reconstruct XMSS keys in a trusted way. We achieve a low-cost solution that only adds lightweight operations to the signature itself, such as repetition decoding and XORing, and does not require additional hardware (like secure non-volatile memories) since the manufacturing variations of the SRAM inside the IoT device are exploited. As a proof of concept, the solution was implemented in an IoT board based on the ESP32 microcontroller. Keywords— XMSS, hash-based signatures, post-quantum cryptography, hardware security, SRAMs, PUFs, TRNGs. I. I NTRODUCTION Digital signatures are basic primitives of asymmetric cryptography and, hence, they use pairs of private and public keys. The signer device uses the signature generation algorithm along with its associated private key to sign a message, and the message verifier uses the signature verification algorithm along with the public key associated to the private key to verify the signature. The private key must be kept secret but the public key can be known by anyone, including an attacker, without compromising the security of the scheme. Digital signatures provide integrity (the signed message is proven to be non-altered), authentication (the signature corresponds to the signer device associated to the private key), and non-repudiation (the signer device cannot successfully claim it did not sign the message, while also claiming its private key remains secret). The most common digital signature schemes used nowadays are ECDSA (Elliptic Curve Digital Signature Algorithm) and RSA (Rivest, Shamir and Adleman). However, since they are vulnerable to quantum attacks, post-quantum resistant solutions are being investigated [1]. Among them, this paper focuses on stateful hash-based signature schemes, particularly on the XMSS (eXtended Merkle Signature Scheme) [2][3]. Hash-based signatures are said to have minimal security requirements because, unlike ECDSA and RSA, their security does not reside on computational hard problems but only on the second-preimage resistance of hash functions. This is an advantage for many applications because, if once implemented, the used hash function is discovered to be vulnerable, only the hash function is needed to be replaced. Besides, stateful hash-based signatures, unlike other postquantum digital signatures, do not require hardware accelerators for achieving acceptable execution runtimes. Therefore, they can be implemented in even low-cost microcontroller-based devices [4]. Another advantage of stateful hash-based signatures is their resistance to sidechannel attacks [5]. Other issues to consider with digital signatures are: (a) the secure generation of the pair (private key, public key), which is carried out in a registration phase, and (b) the secure storage or reconstruction of the private key. It is more secure that the device generates its private and public keys instead of receiving them from outside. This requires the device has a TRNG (True Random Number Generator) to generate the true random seeds required by the digital signature algorithm. The secure storage of the private key requires the use of secure non-volatile memories. This is provided by solutions based on Trusted Computing Architectures such as Trusted Platform Modules (TPMs), Software Guard Extensions (SGX), Iso-X, etc. [6]. However, these solutions do not provide postquantum digital signatures. The reconstruction of the private key with a PUF (Physically Unclonable Function) is better to link the physical device to the private key and to avoid the use of secure non-volatile memories [7]. The proposal of this work is to use SRAM-based PUFs and TRNGs to achieve a complete and lightweight solution for stateful hash-based digital signatures, particularly the XMSS scheme. As detailed in [7], the manufacture process variations occurred when the memory was fabricated determine the startup values of many cells in a SRAM. Those start-up values are used herein to generate PUF responses. In the other side, the start-up values of a few cells in a SRAM are determined by the semiconductor noise. Those start-up values are used herein to generate the needed true random seeds. Since SRAMs are found in many devices, special hardware is not required, neither secure non-volatile memories nor Trusted Computing Architectures. To the knowledge of the authors, there is no solution in the literature combining SRAM-based PUFs and TRNGs with hash-based signatures. The work is structured as follows. Section II summarizes the main features of the XMSS scheme according to the specifications provided in [8]. Section III describes our proposal to use SRAM-based PUFs and TRNGs in the XMSS scheme. A proof of concept performed in a low-cost IoT platform based on the ESP32 microcontroller is shown in Section IV. Finally, conclusions are given in Section V. II. T HE E X TENDED M ERKLE S IGNATURE S CHEME A. Winternitz One-Time Signatures The Winternitz One-Time Signature (OTS) and its variants are parametrized by the security parameter and by the Winternitz parameter . Subsequently, four subparameters are defined as =  (), 1 = 󰇳   󰇴,2 = 󰇳     󰇴 and  = 1+2, where  is the ceil of . A hash function ℎ and a  (Pseudo Random Function) are also needed. The PRF function is defined from ℎ as (,)=ℎ(||) , where || is the concatenation operator. The OTS secret key   is composed of  strings () of size  generated from a uniform random seed  , as ()=( , ,). Thus,   = ((0)||…||( −1)). This form of generating the OTS secret key relaxes the memory consumption requirements since only the seed  , has to be stored. The OTS public key   is computed by applying the hash function ℎ −1 times to each secret string () , ()= ℎ  (()) and concatenating each one as   = ((0)||…||( −1)). For the signature generation, the selected hash function ℎ is applied to the message m to be signed, obtaining a message digest   . The message digest is encoded as a base-w value, being thus divided in 1 strings  , () of length ,   =( , (0)||…|| , (1−1)). Later, a checksum C is computed as =∑−1− , ()    and the result is encoded as a base-w value having as a result 2 strings   ()of size ,   =(  (0)||…||  (2−1)). The concatenation of the  , () and   () strings forms  blocks () that are used to create the signature strings as ()=ℎ () (()). The signature is the concatenation of each signature string,  = ((0)||…||( −1)) . The verification of the signature  󰆒 = ( 󰆒 (0)||…|| 󰆒 (−1)) of a message ′ is carried out by applying to each signature string the hash function − 1−′() times, where the blocks ′() are obtained from ′ as explained for the blocks (). Verification is successful if the result matches the corresponding public key string, ℎ  󰆓 ()  󰆒 ()=(), that is, if the OTS public key is reconstructed from the received signature. B. Many-Time Signatures and Merkle Signature Scheme A Many-Time Signature scheme can be created by concatenating  OTS key pairs and looking out that the keys are not reused by using an index . The drawback of this simple solution is that the resulting public key is too large and, hence, the cost of its storage and distribution is unacceptable. This can be mitigated by compressing the  OTS public keys into one public key, using a data structure called Merkle tree. A Merkle tree is a binary tree that uses the hash of each of the OTS public keys as leaves, and computes the parent nodes of each level by hashing the concatenation of its two children nodes. The root of the tree is the Merkle Signature Scheme (MSS) public key. The height  of the Merkle tree determines the total number  of signatures that can be verified using the same MSS public key as =2  . A toy example is shown in Fig. 1, where a tree of height 2 is used to compress 4 OTS public keys. In the Merkle Signature Scheme, the -th OTS secret seed is generated as  , ()=(  ,). The signer must update securely the index  every time an OTS signature () is generated. The verifier should know the index  that indicates which of the  secret keys was used for the OTS signature. Besides, the verifier needs the array of nodes required to reconstruct the MSS public key from the reconstructed OTS public keys. This array of nodes is called the authentication path, ℎ(), and must be generated by the signer every time a message is signed. The authentication path for the previous toy example is highlighted in Fig. 1. Its computation is not a trivial task since a trade-off between speed and memory consumption needs to be satisfied. In fact, it is the most expensive operation in the MSS. The most balanced algorithm found in literature is [9]. In this algorithm, the signer must keep track a state   () that must be updated in each signature. Part of this state is the authentication path of the next signature itself. This is why these signatures are called stateful hash-based signatures. C. Strengthen the security: the XMSS The eXtended Merkle Signature Scheme (XMSS) includes additional steps to make the MSS scheme more robust. First, the leaves of the Merkle tree are not directly the hash of the OTS public keys. Instead,  Merkle trees called -trees are used. The -th -tree is a Merkle tree that uses the  OTS public key strings of the -th OTS public key   () as leaves. The remaining nodes have the same structure shown in Fig. 1. Second, the message is not hashed alone to form the message digest. Instead, the message is concatenated with the XMSS public key   , the index s and a nonce R computed as =(  ,). The seed   must be uniformly random and must be kept secret. Finally, the most important difference in terms of security is that the hash functions are never used alone. Each time a hash function is called, the value  to hash is XORed with a bitmask   and a key   is appended as a prefix before the hash is applied itself. For example, a hash chain of length 3 is ℎ(  ||ℎ(  ||ℎ(  ||⨁  )⨁  )⨁  ). In the hash functions used for the -trees and the main Merkle tree, two bitmasks are used (one for each child node). The keys and bitmasks should not be repeated, are public, and must be known by the verifier. Since they represent a large bunch of data to be stored and transmitted, they are generated pseudo- Fig. 1 A Merkle tree of height H=2. The authentication path for a signature with s=0 is highlighted. randomly using a public seed   , a PRF function and two address structures   and   , which change to satisfy that no key or bitmask are repeated. III. U SING SRAMBASED PUF S AND TRNG S IN XMSS The method described in [7] is employed to use the startup values of SRAM cells to generate PUF responses or true random bits. First, a characterization step is carried out to identify the stable (STB) cells, which maintain the start-up value when the SRAM is powered on and off a certain number of times, and the random (RND) cells, which provide a startup value of ‘1’ half of the times and ‘0’ the other half. Later, a subset of the STB cells, named ID cells, is selected to provide a PUF response without bias, which is used to obfuscate sensitive data. To cope with the low bit flipping of ID cells, a simple repetition Error Correction Code is employed to turn the encoded version of the sensitive data into public ones known as Helper Data. These data result from the bitwise XOR between the encoded sensitive data of length ⋅ , where r is the length of the repetition encoder, and the startup values of ⋅ ID cells (PUF response). The sensitive data are reconstructed from XORing the Helper Data with a new PUF response and decoding the result. True random data are obtained by applying a hash function to the concatenation of the start-up values of RND cells. The uniformly random data required by the XMSS are: (1) the secret seed   used to generate the OTS secret seeds, (2) the secret PRF key   used to generate the nonces R for the message digest generation, and (3) the public seed   used for the keys and bitmasks generation. All of them are obtained from the RND cells as commented above. Since the first two ones should be secret, they are obfuscated by the ID cells as commented above. The registration phase has the following steps: 1. The RND and ID cells of the SRAM are identified. The RND and ID masks, which identify them, are stored in a non-volatile memory. 2. The SRAM is powered off and on and the random values {  ,  ,  } are generated, using the RND mask. The non-sensitive   is stored in a non-volatile memory. 3. The sensitive data {  ,  } are encoded and obfuscated, using the ID mask, thus resulting the Helper Data   , which are stored in a non-volatile memory. 4. The public key   is computed using   and   , as the root of the Merkle tree, and then is transmitted to the verifier and stored in a non-volatile memory. 5. The index s is initialized to 0, and both the authentication path ℎ(0) and state   (0) for the first signature are computed. They are stored in a non-volatile memory. 6. The RND mask is erased from the non-volatile memory since it is not needed in the signature generation step. Note that the party that makes the registration phase (for example a manufacturer) does not need to provide any information to generate the sensitive data so this phase is highly secure. The s-th signature is generated as follows: 1. The ID mask and Helper Data   are read from the non-volatile memory and the sensitive data {  ,  } are reconstructed. 2. The index s and the public key   are retrieved from the non-volatile memory, the nonce R is calculated, and the message digest   is computed. 3. The s-th OTS secret seed is generated and the message digest is signed using the Winternitz OTS scheme, having as a result (). 4. The authentication path ℎ() is retrieved from the non-volatile memory and the data to send are computed as {  ,,,(),ℎ()}. 5. The index  is updated to +1, the   () to   ( +1), and the ℎ() to ℎ(+1). Then, the old values in the non-volatile memory are replaced by the updated ones. IV. P ROOF OF C ONCEPT AND E XPERIMENTAL R ESULTS A Pycom WiPy 3.0 board was employed to develop the proof of concept into a low-cost IoT-oriented board. It is based on the ESP32 microcontroller, which has 520 KB of internal SRAM that can be powered off and on through a firmware (as required to extract PUF responses). This is a common feature of most microcontrollers with available low-power modes. The constant data are stored in an 8 MB flash memory available on the board. The chosen frequency was 160 MHz. The XMSS reference implementation that accompanies the RFC8391 specification is employed for the signature, concretely the xmss_core_fast option [2]. The chosen security is  = 256 and the Winternitz parameter is =16 as they complain the NIST recommendation [8]. The chosen tree height is =16, which is recommended for standard use [2]. The selected hash function is SHA-256 implemented in the mbedtls library. In this work, we completed the characterization of the SRAM PUFs performed in [10] by determining the probability of errors in a 256-bit sensitive value, the PUF uniqueness and the generation of 256-bit random values. Three different boards and the same 237,320 bits of each SRAM were considered. For the generation of STB and RND masks, 20 measurements were performed. For evaluation purposes other 100 measurements were performed. For the total of cells evaluated in each SRAM, the minimum percentage of STB cells was 84.07 %. Since the STB start-up values did not show bias, the STB cells were the same as ID cells. In [10], the Wipy board is employed to show results based on the PUF reproducibility. The PUF reproducibility was evaluated by the average intra fractional Hamming distance. Intra fractional Hamming distance computes the normalized number of bits that are different in two PUF responses from the same SRAM cells. 1,440,450 (100·99·291/2) intra Hamming distances were calculated for the measurements performed. The resulting average intra Hamming distance was 0.0025 (with 0 being the ideal value). Since the reproducibility in PUF responses from the same SRAM cells is not exactly 0, an Error Correcting Code is applied to obtain the secret seeds from the Helper Data without errors. The capability of the Error Correcting Code is determined by the average intra Hamming distance by considering that the bit error probability can be modeled by a Binomial distribution [7]. In [10], an 8-bit repetition Error Correcting Code was selected since the probability of failure in reconstructing a bit of the secret seed was 2.71⋅10  (which was the resulting value of the operation 1-binocdf(3, 8, 0.0025) in Matlab). In this way, the probability to find some error in a 256-bit sensitive value was 6.94⋅10  (1- binocdf(0, 256, 2.71e-09)), which is lower than an error rate of 10  to satisfy the requirements of most of typical security applications [7]. Therefore, 305 bytes (256/0.8407) of the SRAM are needed to obfuscate a 256-bit sensitive value. PUF uniqueness was evaluated by the average inter fractional Hamming distance. Inter fractional Hamming distance computes the normalized number of bits that are different in two PUF responses from different SRAM cells. 421,959,000 (100·100·291·290/2) inter Hamming distances were calculated for the measurements performed. The resulting average inter fractional Hamming distance was 0.4921 (with 0.5 being the ideal value). We can conclude that the start-up values of the ID cells are unique for different sets of cells, independently of belonging to the same SRAM or not. Since the RND masks of the boards were created with 20 measurements, the RND cells were the cells taking ‘0’ ten times and ‘1’ the other ten. The minimum number of RND cells found was 0.305 % of the total SRAM cells evaluated. The minimum entropy [7] obtained for 100 sequences of the start-up values of RND cells was 69.52 %. Therefore, in order to obtain a 100 % of entropy in a 256-bit random value (such as the   ,   or   ) after applying a PRF function, 369 RND cells were required (256/0.6952). This means 14,7 KB (369/0.00305) of the SRAM. The flash memory employed was 1,122 bytes of Helper Data and ID_mask (0.014% of the flash memory), and 2,400 bytes of XMSS related variables (  ,   , and   ). It is noted that 2,304 bytes of these 2,400 are for the   . The ESP32 microcontroller has a Harvard architecture where 328 KB of the internal SRAM are used for data storage. Only 610 bytes (2·305) of them (a 0.18 %) have to be reserved for acting as SRAM PUF in the signature operation. Regarding timing, we focus on the OTS signature operation because, in contrast to the registration operation, it should satisfy real-time execution and the BDS state update can be done offline. The execution time of the WOTS+ signature is 157.94 ms. The   and   reconstruction from   for the signature operation only increases the execution time in 3.20 ms (an increase of 2.03%). The solution proposed was compared to solutions based on Trusted Computing Architectures that include digital signatures. These architectures are: Trusted Platform Module (TPM), TrustZone, Software Guard Extensions (SGX) and Iso-X [6]. As viewed in Table I, none of these solutions includes post-quantum digital signatures, the architectural features required are complex, and only TPM has a TRNG. V. C ONCLUSIONS In this work, we propose the addition of hardware security to the generation and reconstruction of XMSS keys using SRAM as PUF and TRNG. The solution is more lightweight than other solutions proposed in the literature that do not use post-quantum signatures. A proof of concept was developed to evaluate the suitability of the proposal in a microcontrollerbased IoT device. During signature operation, the solution uses only a 0.18% of the available SRAM and consequently does not affect the device performance. The additional execution time needed to recover the secret values increases only a 2.03% the signing time, and the additional non-volatile memory required is not significant. A CKNOWLEDGMENT This work was supported in part by the Projects TEC2017- 83557-R and RTC-2017-6595-7 (AEI/FEDER UE), and AT17_5926_USE and US-1265146 (FEDER UE/ Consejería de Economía, Conocimiento, Empresas y Universidad de la Junta de Andalucía). The work of R. Arjona was supported by a Post-Doc Fellowship from the Spanish National Cybersecurity Institute (INCIBE). R EFERENCES [1] NIST, Computer Security Resource Centre, "Post-quantum cryptography" [Online]. Available: https://csrc.nist.gov/projects/postquantum-cryptography. [2] RFC8391. XMSS: eXtended Merkle Signature Scheme, Internet Research Task Force, 2018. [3] J. Buchmann, E. Dahmen, A. Hülsing, “XMSS — A practical forward secure signature scheme based on minimal security assumptions,” in PQCrypto 2011. Lecture Notes in Computer Science, vol. 7071, pp. 117–129. Springer, 2011. [4] X. Liu, R. Misoczki, M. R. Sastry, “Remote attestation for low-end prover devices with post-quantum capabilities,” presented at CODASPY'18, Tempe, AZ, USA, 2018. [5] M. J. Kannwischer, A. Genêt, D. Butin, J. Krämer, J. Buchmann, “Differential power analysis of XMSS and SPHINCS”, presented at 9th Int. Workshop, COSADE 2018. LNCS, vol. 10815, pp. 168–188. Springer, 2018. [6] P. Maene, J. Gotzfried, R. de Clercq, T. Müller, F. C. Freiling, I. Verbauwhede, “Hardware-based trusted computing architectures for isolation and attestation,” IEEE Trans. Computers, vol. 67, pp. 361– 374, 2018. [7] I. Baturone, M. A. Prada-Delgado, S. Eiroa, “Improved generation of identifiers, secret keys, and random numbers from SRAMs,” IEEE Trans. Inf. Forensics Secur., vol. 10, pp. 2653–2668, 2015. [8] D. Cooper, D. Apon, Q. Dang, M. Davidson, M. Dworkin, C. Miller, “Recommendation for stateful hash-based signature schemes,” Tech. rep., National Institute of Standards and Technology, 2019. [9] J. Buchmann, E. Dahmen, M. Schneider, “Merkle tree traversal revisited,” in J. Buchmann, J. Ding (eds.) Post-Quantum Cryptography - PQCrypto 2008. Lecture Notes in Computer Science, vol. 5299, pp. 63-78. Springer, 2008. [10] J. Arcenegui, R. Arjona, I. Baturone, “Secure management of IoT devices based on blockchain non-fungible tokens and physical unclonable functions,” in Applied Cryptography and Network Security Workshops (ACNS). Lecture Notes in Computer Science, vol 12418, pp. 1-17. Springer, Cham, 2020. TABLE I. C OMPARISON T O S OLUTIONS B ASED O N T RUSTED C OMPUTING A RCHITECTURES D ETAILED I N [6] Solution Digital Signature (Post-quantum resistance) Architectural Features Required TRNG Included TPM 2.0 RSA/ECDSA (No) Complex Yes TrustZone RSA (No) Complex No SGX ECDSA (No) Complex No Iso-X Not specified Complex No Ours XMSS (Yes) Lightweight Yes