Kerckhoffs’s Principle

In 1883, Kerckhoffs published a paper and stated the security of a system should be based upon the key instead of the algorithm. The algorithm should be public. The key should be the only secret.

Today, most cryptographers agree with Kerckhoffs’s principle. They believe that we should publish the algorithm and open source the implementation so that more people can have the chance to review and find the vulnerability earlier.

On the other hand, hiding the algorithm may have some advantages. Because the enemy does not know the design, they need to spend more time and more resources to break the system.

Taking firmware as an example, most of the firmware binaries are write protected but not encrypted. Once the attacker dumps the binary, they can do reverse engineering. We also observed some firmware binaries are encrypted. Even if an attacker gets the binary, the binary analysis is not feasible. Maybe this is valuable for intellectual property protection, but it also raises the bar of attacking the system.

Random Number and One-Time Pad

A random number may be required in the firmware, such as a salt for the password hash or a random number in the TLS handshake. Fundamentally, there are two ways to generate a random number:

     1)     To generate a random number based upon an unpredictable physical source, such as noise: This is named as a non-deterministic random number generator (NDRNG) or true random number generator (TRNG).

     2)     To generate a random number based upon a predefined algorithm: This is called a deterministic random number generator (DRNG) or pseudo random number generator (PRNG).

Because the TRNG is slow while the PRNG is comparatively fast, a typical implementation combines them together. As John von Neumann quipped, “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” As such, the TRNG is used to generate the first random number as a seed. Then the PRNG is used to create the rest of the random numbers. See Figure 19-5.

The random number generator can be supported by software or hardware. NIST SP800-90 provides the detailed requirements on the random number generation. The software implementation for the pseudo random generation shall follow NIST SP800-90 recommendations, such as hash-based PRNG, HMAC-based PRNG, or block cipher counter (CTR) mode–based RRNG. Currently the Intel X86 architecture defines two random number instructions: RDSEED and RDRNG. RDSEED returns random numbers that are supplied by a cryptographically secure, enhanced non-deterministic random bit generator (NDRBG). RDRAND returns random numbers that are supplied by a cryptographically secure, deterministic random bit generator (DRBG). ARMv8.5 also defines the RNDR and RNDRRS instruction. If possible, the software needs to use the hardware instructions as the TRNG.

The random number may be used in a one-time pad (OTP). The one-time pad is an example of perfect security or unconditional security. It cannot be broken if it is implemented correctly. The gist of OTP is 1) the key is generated with TRNG, 2) the key is only known by the sender and receiver, 3) the key must be only used once, and 4) the key must be as long as the message.

However, it is impractical in most situations because of those hard requirements. The one-time key distribution and storage is a big problem for the firmware usage.

Block Cipher and Modes of Operation

Block cipher may be used in firmware to encrypt and decrypt the messages between two entities. It is required in secure communication protocols such as Transport Layer Security (TLS) in the network stack or Secure Protocol and Data Model (SPDM) in device communication.

NIST SP800-38 provides the detailed recommendations for each mode. The deterministic encryption has a weakness that the identical plain text results in identical ciphertext block. Also, the reordering of a valid plain text cannot be detected.

In general, if there is only a confidentiality requirement, a probabilistic encryption method should be used. The randomness in the probabilistic encryption is based upon the initialization vector (IV). They must be random at each encryption.

If there is a requirement for both data confidentiality and data authenticity, we need to include both encryption and message authentication code (MAC). Because we have seen issues in Encrypt-and-MAC (E&M), Encrypt-then-MAC (EtM), and MAC-then-Encrypt (MtE), the general recommendation is to use the existing standard Authenticated Encryption with Associated Data (AEAD) algorithm, such as GCM or ChaCha20Poly1305.

The different modes may require different input. The IV, which stands for initialization vector, must be uniformly generated in a random fashion. The nonce, which means “number used once,” must be unrepeatable and unpredictable. The counter is incremented in each message, and it is predictable. Semantically, an IV is different from a nonce. If an IV is not uniformly random, the solution may have a vulnerability.

Digital Signature and Signature Scheme

The digital signature is probably the most popular usage of cryptography in the firmware. The NIST SP800-193 standard requires firmware resiliency. Both update protection and detection rely upon the digital signature.

NIST FIPS-186 describes the approved digital signature standards, including RSA (Rivest-Shamir-Adleman), Elliptic Curve Digital Signature Algorithm (ECDSA), and Edwards-Curve Digital Signature Algorithm (EdDSA).

In general, the RSA signature method is faster than the ECDSA. For RSA, the signing scheme includes a padding for the message. With the padding, the final signature might be deterministic or non-deterministic. The RSASSA-PKCS1-v1_5 is deterministic, where the identical plain text results in the identical signature. The RSASSA Probabilistic Signature Scheme (RSASSA-PSS) adds a random salt value in the signature. As such, the identical plain text results in a different signature. Currently RSASSA-PSS is recommended. In RSASSA-PSS, the salt length is between 0 and the hash length. In practice, the salt length should be same as the hash length.

The ECDSA is used by the device usually because the key size is smaller. If the device has the capability to generate the random numbers for the per-message secret number, the ECDSA should be used. The use of deterministic ECDSA may be desirable for devices that do not have a good source of the random numbers. The per-message secret number is derived from the message and private key. As such, the final signature result is deterministic.

The Edwards curves offer high performance for elliptic curve calculations and protection against side channel attacks, because it is easier to write branch-free, constant time code to implement Edwards curves. However, care must be taken to implement the deterministic signatures. The secrecy of the private key in the EdDSA calculation is critical.

Similar to symmetric authenticated encryption, some solution may require asymmetric encryption and signing. A naïve asymmetric sign-and-encrypt has different security properties from symmetric encryption. From the sender perspective, they are the same. The sender is sure that 1) the recipient knows who wrote the message and 2) only the recipient can decrypt the message. From the recipient perspective, they are different. The recipient of the symmetric encrypted message knows who sent it to them. The recipient of the naïve asymmetric signed-and-encrypted message only knows who wrote the message but does not know who encrypted it. This naïve sign-and-encrypt vulnerability is known as “surreptitious forwarding.” The solution for this problem includes 1) adding the sender and/or recipient name, 2) using sign-encrypt-sign, and 3) using encrypt-sign-encrypt.

RFC 8017 defines the encryption scheme (RSAES-OAEP and RSAES-PKCS1-v1_5) and signature scheme (RSASSA-PSS and RSASSA-PKCS1-v1_5).

Key Establishment and Forward Secrecy

Key exchange may be used in firmware to exchange a pre-master key or shared secret between two entities. It is required in the secure communication handshake, such Transport Layer Security (TLS) in the network stack or Secure Protocol and Data Model (SPDM) in the device communication.

From the cryptography perspective, the key establishment can use the symmetric algorithm. For example, a trusted key distribution center (KDC) can be set up to share the secret key with each user. The key is named as the key encryption key (KEK) and used to encrypt the session key. In practice, there are lots of problems in the solution, such as establishing a secure channel during initialization, a single point of failure, and no forward security. As such, the practical key establishment usages employ the asymmetric algorithm.

NIST SP800-56 provides the recommendations for the discrete logarithm-based key establishment, such as Diffie-Hellman (DH), Elliptic Curve Diffie-Hellman (ECDH), and so on, and integer factorization–based key establishment such as RSA.

If a long-term public/private key pair is involved in the pre-master secret generation, this is not a forward secrecy solution because once the long-term key is compromised, the attacker can calculate the secret (S).

In forward secrecy, an ephemeral key (EK) pair is generated as a random number, and the only usage of this ephemeral key pair is to establish a secret (S). The long-term public/private key pairs should never be involved in the secret calculation.

The client/server long-term public/private key pairs are still important for user identity and authentication purposes. Without the authentication step, the communication channel may be vulnerable to a man-in-the-middle attack.

If forward secrecy is required, please make sure you choose the right cipher suites to support generation of the ephemeral key. The ECDHE is much faster than DHE. But just in case the elliptic curve cryptography (ECC) is not well supported on the other side, then DHE can be used instead.

Hash, Message Authentication Code, and Key Deviation

Hash is another popular usage in the firmware. The trusted boot process needs to measure the hash of a firmware image and data into the Trusted Platform Module (TPM) Platform Configuration Register (PCR) to establish the static root-of-trust for measurement (SRTM).

SHA2 is the classic hash algorithm and widely used today. The core of the SHA3 family is the new KECCAK algorithm. The SHA3 also supports the extendable-output function (XOF), which means the hash output can be extended to any desired length. For the XOF function, the suffix 128 or 256 means the security strengths, instead of digest length.

Two typical usages of the hash function are digital signature and message authentication code. The message authentication code (MAC) is also known as a cryptography checksum. Similar to the hash, the MAC function accepts an arbitrary-length message and creates a fixed-length authentication tag. MAC can provide the message integrity and authentication. The fundamental difference between MAC and digital signature is that MAC does not provide non-repudiation. The reason is that the key used in the MAC function is a symmetric key shared between two entities, whereas the key used in the digital signing function is a private key and only known by the sender.

NIST FIPS-198 defines the HMAC, and NIST SP800-38B and SP800-38D provide recommendations for CMAC and GMAC.

If there is a requirement for an authentication code, we need to use the MAC function. Because we have seen issues in secret-prefix MAC or secret-suffix MAC, the general recommendation is to use the existing standard MAC function, such as HMAC, KMAC, or CMAC.

Beyond message integrity and authentication, one important usage of HMAC is to help derive the key. This might be a use case in the firmware. The firmware may include the user authentication with the password and use the password to derive the key to protect the user data. Or the firmware may get a master secret from a hardware engine and derive the key to protect the platform data.

RFC 8018 PKCS#5 defines the password-based key derivation functions (PBKDFs). Usually the password is chosen from a relatively small space. It cannot be used directly as a key for encryption. We need a key derivation function to convert the password into a key. First, we need to add a random salt to resist the password rainbow table attack. As such, the pre-build hash table by the attacker is useless. The length of the salt should be the same as the digest length chosen in the KDF. Second, we need to include an iteration count of processing to increase time of brute force attack. The minimal iteration count is 1000.

RFC 5869 defines a HMAC-Based Extract-and-Expand Key Derivation Function (HKDF). The typical usage of HKDF is to derive a session key from a master shared secret from the key establishment or derive a subkey from a root key. HKDF includes two phases: HKDF_Extract and HKDF_Expand. HKDF_Extract adds a random salt to derive a pseudorandom key (PRK). HKDF_Expand adds a fixed context info to derive the final output key. A solution may choose to include both phases or only include the HKDF_Expand to derive a key deterministically.

Digital Certificate and Certificate Chain

In the previous section, we introduced the digital signature. An entity may generate a public and private key pair, sign the message with the private key, and publish the public key to let other entities verify the signature. In practice, a single public key is not enough to describe the identity of the entity. We need more information such as the key owner’s information. To combine the information together, we can generate a certificate.

A certificate should include the validity period; the information of the subject such as country, organization, name, and so on; and the public key of the subject. Similar to a driver’s license or a passport, there must be a trusted authority to issue the certificate. This issuer is called Certificate Authority (CA) . The subject needs to create a certificate signing request including all of the preceding information and send it to the CA. Then the CA adds the issuer information, signs the certificate with the CA’s private key as the signing key, and appends the key ID and the signature. That becomes the final valid certificate for the subject. The format of the public certificate is defined in the X.509 standard. Figure 19-6 shows the flow on how to create a certificate from a public/private key pair.

In order to verify if a certificate of the subject is valid, the verifier can check the digital signature of the certificate with the CA’s public certificate. Because the CA itself is always trusted, the certificate of the CA is a self-signed certificate. The subject and issuer are the same. This is called root CA. In practice, we cannot have a root CA to sign every certificate. The root CA can sign an intermediate CA and let the intermediate CA to do the rest of the signing work. Now we create a certificate chain. See Figure 19-7.

Once the certificate chain is created, the verification process needs additional steps. The verifier needs to discover the issuer of the certificate – the intermediate CA – and verify if the certificate of the subject is valid based upon the certificate of the intermediate CA. Then the verifier needs to find out the issuer of the intermediate CA’s certificate – the root CA – and verify if the certificate of the intermediate CA is valid based upon the certificate of the root CA.

We have created the subject certificate and the certificate chain. Now we can sign the data with the private key. The RFC2315 PKCS#7 defines cryptographic message syntax for the digital signature and digital envelopes. The signer needs to add certificates in the certificate chain and use the private key as the signing key to generate the digital signature. The final PKCS#7 signed data may include the original data as the content information, the certificates and the signer information such as the issuer info, the signing time, and the signature. See Figure 19-8. The final PKCS#7 signature can be sent to the receiver for verification. Please be aware that the PKCS#7 signature might be a detached one if the data is excluded and sent to a receiver in another way.

Once the receiver gets the data and the PKCS#7 signature, they can use the root CA certificate to verify the whole PKCS#7 signature. The root CA certificate is used to verify the certificate chain. The signer’s certificate is used to verify the data. See Figure 19-9.

Today the X.509 public certificate format is widely used in the industry, such as by network Transport Layer Security (TLS). PKCS#7 is also widely used as the cryptographic message syntax for the signature, such as the executable image signing. But they are not the only one. For example, in the Internet of Things (IoT) environment, people are considering using Concise Binary Object Representation (CBOR) Object Signing and Encryption (COSE) syntax to replace the complicated ASN.1 format used in X.509 and PKCS#7.

Certificate Management

Saving a public certificate in the firmware requires the non-volatile (NV) storage. The typical firmware only has limited NV storage, such as an 8M-byte Serial Peripheral Interface (SPI) NOR flash. The NAND flash Replay Protected Memory Block (RPMB) area is bigger, but not all platforms include the RPMB flash. System partition of an operating system (OS) disk is another option available for non-volatile storage for the firmware. Unfortunately, it is unprotected. The attack may update the content there directly.

The certificate revocation is also a challenge. For the OS that has network capability, the Online Certificate Status Protocol (OCSP) can be used. However, it is not practical for the standalone firmware solution if the firmware does not have network support. The firmware may expose an interface to update the certificate with the help of another authorized entity. The UEFI specification defines UEFI authenticated variables as the UEFI image signature database. Any user may read it, but only an authenticated user can write it. The OS can update the allowed certificate or add the revoked certificate to the forbidden signature database if it has an entry in the KEK. The Cerberus specification defines a set of root-of-trust (RoT) commands to update the platform manifest and the component manifest. Some of them became part of the Secure Protocol and Data Model (SPDM) specification for the device management.

One reminder is that when the final production image is generated, the pre-production certificate or test certificate must be removed from the production image. Otherwise, any developer can generate a new signed image. The firmware may implement a built-in self-detection mechanism. We can standardize the pre-production certificate and test certificate and let firmware display a warning message to tell people that this firmware is only for test purpose and should not be released, in hopes that the validation engineers will report issues in case that they see this message.

Not all firmware has confidentiality support. In that case, the firmware may not include a private certificate for the data signing purpose. This might become a limitation for the mutual authentication use case, such as the handshake phase of the Transport Layer Security (TLS) or Secure Protocol and Data Model (SPDM). In order to achieve that, we can use some other mechanisms. For example, we can let the firmware get the private certificate from another security coprocessor such as the management engine (ME) and use it once and discard it afterward. With this solution, the security coprocessor should implement an interface to lock down the private certificate retrieving. Another solution is to leverage the hardware to generate the certificate such as Software Guard Extension (SGX).

Cryptographic Algorithm Agility

There are lots of cryptographic algorithms in the world, and there is no need to support all of them in a single firmware. Taking the Trusted Platform Module (TPM) as an example, a TPM chip may support three different hash algorithms – SHA1 for the legacy system, SHA256 for the current system, and SM3 for the Chinese market. The final platform may just choose one of them. On the one hand, the system firmware should only enable one hash algorithm for the firmware hash calculation to save the system boot time. On the other hand, the system firmware should be designed with multiple hash capabilities. This is important because it will help to migrate from one hash algorithm to the other. For example, SHA1 was used in the old system. After it has been proved to be insecure, we can migrate to SHA256. The current system configurations use the RSA2048 and SHA256. NSA gives the recommendation that we should move to RSA3072 and SHA384 for future production.

Performance and Size

Most cryptographic algorithms might be complicated and need lots of calculation. It may bring firmware code size impacts and runtime performance impacts. For example, the OpenSSL is a good choice for the cryptographic algorithm implementation, but it is big because it is designed for OS applications. For the embedded system, we need to find a smaller one, such as mbed TLS or wolfSSL.

The hardware may also add instructions to support the algorithms. Besides true random number generation, the Intel X86 architecture defines Advanced Encryption Standard new instructions (AES-NIs) such as AESENC, AESDEC, AESIMC, AESKEYGEN, and so on and SHA extensions such as SHA256MSG1, SHA256MSG2, and so on. The ARMv8.0 architecture also defines cryptographic extension for AES such as AESD, AESE, AESIMC, AESMC, and so on and SHA such as SHA256H, SHA256H2, and so on. The firmware may leverage these hardware capabilities.

A Hardware Security Module (HSM) is another possible implementation for the cryptographic algorithms. It might be hard for the firmware to leverage because it is a vendor-specific solution.

Cryptanalysis

Last but not least of importance, please do not try to invent a cryptographic algorithm or protocol without a review with a cryptography expert. For example, if there is encryption and authentication requirement, the standard AEAD should be used instead of a customized E&M, EtM, or MtE.

Implementation Attack

Implementation attack means there is no problem with the cryptographic algorithm and the usage, but a coding error caused the security claims to be broken.

Shor’s Algorithm

Grover’s Algorithm

Symmetric Algorithm

The symmetric cryptography is not impacted too much. AES is presumed to be quantum safe because Grover’s algorithm just aids the brute force search. What we need to do is to double the key size from AES-128 to AES-256.

Asymmetric Algorithm

The asymmetric cryptography is heavily impacted, though. RSA/ECC/DH and their derivatives are not quantum safe because of Shor’s algorithm. As such, we have to figure out the replacement. Fortunately, there are some other asymmetric algorithms that are presumed to be quantum safe, such as hash-based digital signature, lattice-based cryptography, code-based cryptography, Multivariate Public Key Cryptography, and so on. Before a new asymmetric algorithm is used, the RSA and DH are preferred than the ECDSA and ECDH, because the ECC uses a smaller key size and is considered to be an easier target for quantum computers.

Because the majority of cryptographic algorithm usage in firmware is the digital signature, it is important to know the basic principle of the quantum safe algorithms. In the following sections, we will give a brief introduction to the hash-based signature.

Hash-Based Signature

In 1979, Lamport published “Constructing digital signatures from a one-way function” and invented the hash-based signature. The gist of the digital signature is to provide evidence that the message data is created by the known sender and the message is not modified in transit. Because the hash is a one-way function, we can create the digital signature only with the hash function. The security of the hash-based signature is based upon the collision resistance of the hash function.

Lamport One-Time Signature Scheme

Let’s see how to sign a 256-bit message in Lamport’s paper in Figure 19-10.

1. 1)
   First, we need to generate the key. In order to sign the 256-bit message, we need to generate 512 bit strings. Each bit string has 256 bits. The private key is SK where

   SK = SK[0] || SK[1]

   SK[0] = SK[0][0] || SK[0][1] || SK[0][2] || ... || SK[0][255]

   SK[1] = SK[1][0] || SK[0][1] || SK[0][2] || ... || SK[0][255]

   SK[x][y] = Random, (x=0,1; y=0,1,2,...,255)

   Each SK[x][y] is a 256-bit random data. The total private key length is 512*256 bits =128K bits = 16K bytes.

   The public key is PK where

   PK = PK[0] || PK[1]

   PK[0] = PK[0][0] || PK[0][1] || PK[0][2] || ... || PK[0][255]

   PK[1] = PK[1][0] || PK[0][1] || PK[0][2] || ... || PK[0][255]

   PK[x][y] = HASH (SK[x][y]), (x=0,1; y=0,1,2,...,255)

   Each PK[x][y] is the hash of the SK[x][y]. Assuming we are using SHA256 as the hash function, then each PK[x][y] is 256 bits. The total public key size is also 16K bytes.

    
2. 2)
   Second, we need to sign the message. Assuming the 256-bit message is M where

   M=m[0] || m[1] || m[2] || ... || m[255]

   m[i] (i=0,1,2,...,255) = 0 or 1.

   then the message signature is Sig(M) where

   Sig(M) = s[0] || s[1] || s[2] || ... || s[255]

   s[i] = SK[m[i]][i], (i=0,1,2,...,255)
    

Each s[i] is SK[0][i] or SK[1][i] based upon the m[i] value 0 or 1. As such, the total signature length is 256 * 256 bits = 64K bits = 8K bytes.

Now, the sender transmits the message M, with the signature Sig(M). How does the receiver verify the message?

1. 1)
   First, the receiver needs to generate the verification data Ver(M) with the message Sig(M):

   Sig(M) = s[0] || s[1] || s[2] || ... || s[255]

   Ver(M) = v[0] || v[1] || v[2] || ... || v[255]

   v[i] = HASH(s[i]), (i=0,1,2,...,255)

   Each v[i] is the hash of the s[i]. The verification data is also 256 * 256 bits = 8K bytes.

    
2. 2)
   Second, the receiver can verify the message M with PK:

   M=m[0] || m[1] || m[2] || ... || m[255]

   PK = PK[0] || PK[1]

   PK[0] = PK[0][0] || PK[0][1] || PK[0][2] || ... || PK[0][255]

   PK[1] = PK[1][0] || PK[0][1] || PK[0][2] || ... || PK[0][255]

   VerificationResult = (v[i] == PK[m[i]][i]), (i=0,1,2,...,255)
    

Each v[i] should be checked with PK[0][i] or PK[1][i] based upon the m[i] value 0 or 1. If all v[i] are the same as the corresponding PK[][i] value, then the verification passes. Otherwise, the verification fails.

The security of this hash-based signature is based upon the hash function. Because of preimage resistance and collision resistance properties, the attacker cannot calculate the SK and cannot calculate the Sig(M).

The Lamport OTS scheme is simple and beautiful. There are two limitations:

1. 1)

   The key size and signature size are big. In the preceding example, the private key and public key size are 16K bytes. The signature is 8K bytes. Comparing to RSA2048, the signature is 2048 bits = 256 bytes.

    
2. 2)

   The signature can only be used once. Once you sign a message, you expose half of the private key. If you sign the second message, you may expose the other half of the private key based upon how many bits are the same as the first message. In the worst case, if the bits in the two messages are totally different, then you expose the whole private key.

    

Winternitz One-Time Signature Scheme

In order to resolve the Lamport OTS limitation on large signature sizes, Winternitz proposed an idea based upon time-space trade-off. The signature size can be reduced at the cost of more hash operations. The gist of the Winternitz one-time signature (WOTS) scheme is to sign multiple bits at one time, instead of 1 bit at one time. This number of bits that can be signed at one time is named as the Winternitz parameter (w).

Let’s see how to sign a 256-bit message with w being 4 in Figure 19-11.

1. 1)
   First, we need to generate the key. If we divide the 256-bit message by 4 bits, we can get 64 chunk messages. In order to sign the 64 chunk messages, we need to generate 64 bit strings. Each bit string has 256 bits. The private key is SK where

   SK = SK[0]

   SK[0] = SK[0][0] || SK[0][1] || SK[0][2] || ... || SK[0][63]

   SK[0][y] = Random, (y=0,1,2,...,63)

   Each SK[0][y] is a 256-bit random data. The total key size is reduced to 64*256 bits =16K bits = 2K bytes.

   Because each chunk message is 4 bits, we need 2^4 = 16 possible signing keys. Instead of generating other random bit strings, we can hash the SK[0] and use the result as SK[1]. Then we can hash the SK[1] and use the result as SK[2]. Finally we can hash SK[14] and use the result as SK[15]. The public key PK is SK[15]:

   SK[x] = SK[x][0] || SK[x][1] || SK[x][2] || ... || SK[x][63], (x=1,2,...,15)

   SK[x][y] = HASH (SK[x-1][y]), (x=1,2,...,15; y=0,1,2,...,63)

   PK = SK[15]

   PK[y] = SK[15][y], (y=0,1,2,...,63)

   With this method, all the signing keys can be derived from the original SK.

    
2. 2)
   Second, we need to sign the message. Assuming the 256-bit message is M where

   M=m[0] || m[1] || m[2] || ... || m[63]

   m[i] (i=0,1,2,...,63) = 0,1,2,...15.

   then the message signature is Sig(M) where

   Sig(M) = s[0] || s[1] || s[2] || ... || s[63]

   s[i] = SK[m[i]][i], (i=0,1,2,...,63)
    

Each s[i] is SK[x][i] based upon the m[i] value. As such, the total signature length is 2K bytes.

Now, the sender transmits the message M, with the signature Sig(M). How does the receiver verify the message?

1. 1)
   First, the receiver needs to generate the verification data Ver(M) with the message Sig(M):

   M=m[0] || m[1] || m[2] || ... || m[63]

   Sig(M) = s[0] || s[1] || s[2] || ... || s[63]

   Ver(M) = v[0] || v[1] || v[2] || ... || v[63]

   v[i] = HASH (2^w – 1 – m[i], s[i]), (i=0,1,2,...,63)

   Each v[i] is the hash of the s[i]. Given a message chunk m[i], the hash operation should be repeated with (2^w – 1 – m[i]) times. For example, if m[i] is 1, then we need to call the hash function 14 times. If the m[i] is 10, then we need to call the hash function 5 times. If m[i] is 15, then we don’t need to call the hash function because the SK[15] is PK itself.

    
2. 2)
   Second, the receiver can verify the message M with PK:

   PK = PK[0] || PK[1] || PK[2] || ... || PK[63]

   VerificationResult = (v[i] == PK[i]), (i=0,1,2,...,63)
    

Each v[i] should be checked with PK[i]. If all v[i] are the same as the corresponding PK[][i] value, then the verification passes. Otherwise, the verification fails.

The preceding method looks like a good way to reduce the key size and signature size. However, there is a vulnerability. An attacker may change the message chunk to a bigger value and calculate the next derived key SK with the hash function. In order to detect such a modification, we need to calculate the checksum of the original message and append the signature for the checksum as additional verification data. The checksum is C where

C = (16 – m[0]) + (16 – m[1]) + (16 – m[2]) + ... + (16 – m[63])

Then we need to add an additional SK for the checksum – SK[64], SK[65], SK[66]. In the verification phase, the receiver needs to reconstruct the checksum and verify the signature of the checksum. The right side of Figure 19-6 shows the checksum signing and verification. Even with the additional signing key for the checksum, the final key size in Winternitz OTS is still much smaller than the key size in Lamport OTS.

Merkle Signature Scheme

The second limitation of Lamport OTS is the one-time usage. This is an even bigger problem because of the key management requirements. Exchanging a public key is complicated. If a new public key is always required for a new signature, the OTS scheme is hard to be used in practice. In order to make OTS feasible, Merkle introduced the Merkle Signature Scheme (MSS). With MSS, one public key can be used to verify many messages signed by the private key. The user may choose a height value h, and the MSS can help to generate the private key to sign N = 2^h messages.

Let’s see how to sign a 256-bit message with h being 3.

1. 1)

   First, we need to generate the keys – a Merkle tree. See Figure 19-12.

    

In order to generate the main public key, we need to generate 2^h private/public key pairs. Here h is 3, so we need to generate eight key pairs where

SK[0], SK[1], ..., SK[7]

PK[0], PK[1], ..., PK[7]

Then we start building the leaf nodes of a Merkle tree based upon the PK:

v[0][0], v[0][1], ..., v[0][7]

v[0][i] = HASH (PK[i])

Then we calculate the non-root node at level h based upon the node at level h-1. The parent node is the hash of the concatenation of its left child and right child. The root node of the tree hash is the main public key:

v[h][i] = HASH (v[h - 1][2 * i] || v[h - 1][2 * j + 1])

RootNode = v[3][0]

The main public key is the only public key which needs to be published. The SK/PK pairs and the other parts of the Merkle tree do not need to be published. This single main public key can be used to verify the N = 2^h messages in MSS:

1. 2)

   Second, we need to sign the message. We choose the SK[s] to sign the message M and generate Sig(M). This is same as OTS. Then we need to calculate a Path(s), which is the sequence of nodes in the Merkle tree, from the leaf node to the root node. From the Path(s) we can get an authentication path – AuthPath(s) – which is the sequence of nodes in the Merkle tree to help the node in Path(s) to create the main public key.

    

See Figure 19-13. The s is 3. We choose SK[3] and PK[3] as the signing key and verification key. The arrow indicates the Path[3] - (v[0][3], v[1][1], v[2][0]). The dashed node denotes the AuthPath[3] - (v[0][2], v[1][0], v[2][1]).

The final signature is SigMerkle (M, s) = (s, Sig(M), PK[s], AuthPath[s]). AuthPath adds the additional size of the final signature, and it highly depends upon the h value. Here the h is 3, and then the AuthPath size is 3 * 256 bits = 768 bits. In practice, the h will be much bigger to support signing more messages with one main public key.

Now, the sender transmits the message M, with the signature SigMerkle (M). How does the receiver verify the message?

1. 1)

   First, the receiver uses PK[s] in the SigMerkle to verify the Sig(M). This step is the same as OTS.

    
2. 2)

   Second, the receiver needs to verify the PK[s] with the main public key. This can be achieved to reconstruct the Path[s] with the help of AuthPath[s]. Here, the verifier needs to calculate the following:

    

v[0][3] = HASH(PK[3])

v[1][1] = HASH(v[0][2] || v[0][3]), where v[0][2] is from AuthPath[3]

v[2][0] = HASH(v[1][0] || v[1][1]), where v[1][0] is from AuthPath[3]

v[3][0] = HASH(v[2][0] || v[2][1]), where v[2][1] is from AuthPath[3]

If the final calculated v[3][0] is same as the published main public key, then the verification passes. Otherwise, the verification fails.

Once s = 3 is selected, then Path[3] cannot be used anymore. In the next time, we need to choose another path.

Current Status

The key concept of hash-based signature (HBS) schemes is based upon the one-time signature and hash tree scheme in Figure 19-14. The OTS is used to sign the message, and the hash tree is used to create the main public key. The authentication path is included in the final signature to help the verification. Because those schemes need to record the state of the private keys, they are called stateful hash-based signature schemes.

Today, we have other OTS variants, such as Winternitz OTS+ (WOTS+), Hash to Obtain Random Subset (HORS), Forest of Random Subsets (FORS), and so on, with the purpose to shorten the signature size and accelerate signing and verification. Some of them can be used for more than one time. They are called few-times signature (FTS) schemes. People build other hash-based signature (HBS) schemes, such eXtended Merkle Signature Scheme (XMSS)/Multi-tree XMSS (XMSS-MT) and Leighton-Micali Signatures (LMS). Take XMSS as an example. The big difference is the leaf node. It is not a hash of the OTS public key, but the root node of another tree called L-tree. The L-tree is similar to the Merkle tree. The WOTS+ public key is stored in the leaf node of the L-tree.

Unfortunately, stateful HBS schemes are easy to be misused. Because they are one-time signatures, any private key cannot be used on two or more messages. The implementation must maintain the state to keep track of the one-time private key usage in order to prevent the reuse. The stateful HBS may be used for image signing in the firmware security area. Assuming we choose h to be 10 in a Merkle tree, we can sign 1024 images with one main public key. If the firmware image is released every month, this main public key will cover 85 years.

At the same time, the stateless hash-based signature (HBS) scheme is also created. Take SPHINCS+ as an example. It creates a hyper tree structure in Figure 19-15. Each layer of SPHINCS+ uses a XMSS WOTS+ L-tree as a node. This WOTS+ L-tree is used to sign to its children WOTS+ L-tree in the next level. The leaf node of the SPHINCS+ uses the Forest of Random Subsets (FORS) tree to sign the message.

The benefit of stateless HBS is to eliminate the state maintenance requirement. Since it is also hash based, the security is based upon the hash algorithm. However, the disadvantage of SPHINCS+ is the signature size and speed, because it eliminates the state by using the components from XMSS and working with larger keys and signatures.

For more details of XMSS, LMS, and SPHINCS+, please refer to the RFC 8391, RFC 8554, and the SPHINCS specifications.

Quantum Key Distribution (QKD)

Quantum key distribution (QKD) is an advanced secure communication method for key exchange. With QKD, two parties can produce and share a common secret for encryption and decryption. QKD is tamper-proof naturally because it is based upon the properties of quantum mechanics. If there is a third party trying to eavesdrop upon the communication, this action will disturb the system. If the modification is detected, then the key distribution can be aborted.

In 1984, Bennet and Brassard published “Quantum cryptography: Public key distribution and coin tossing” to describe a quantum key distribution mechanism. This is the first quantum cryptography protocol, and it is provably secure based upon the quantum property. It is also named as the BB84 protocol.

Let’s take a look at how BB84 works. Alice wants to negotiate a secret with Bob. They need to set up two communication channels. One is the quantum channel which is used to transmit photons. The other is the classic channel which is used to transmit digital information. In order to transmit photons in the quantum channel, Alice needs two digital polarizers, and Bob needs two digital beam splitters. We name the rectilinear polarizer/ beam splitter to be R and the diagonal polarizer/ beam splitter to be D. See Figure 19-16.

Alice can send photon from either the R or D polarizer. The photon sent from R could be vertical (bit 1) or horizontal (bit 0). The photon sent from D could be 135 degrees (bit 1) or 45 degrees (bit 0). Bob can choose either the R or D beam splitter and check the photon detector. If Bob chooses the same R or D with Alice, the final result will be correct. If Bob choses the different R or D with Alice, the result is unknown – 50% correct and 50% wrong. Realistically, some photons may be lost in transition because of the limitation of the detector.

Now Alice and Bob can start negotiating the secret. See Figure 19-17.

The QKD process can help to generate the one-time pad (OTP) password. It must be used one time, and its length must be as long as the message itself.

Quantum Random Number Generation (QRNG)

The quantum mechanism can be used to produce a random number. Figure 19-18 uses a Bloch sphere to show the concept. The north pole of the Bloch sphere presents the classic value 0, and the south pole presents the classic value 1. Any other point on the Bloch sphere presents the superposition. The closer point to a pole means the higher probability when the qubit collapses into the classical value. We can use the following steps to get a random bit:

1. 1)

   We initialize the qubit to state 0.

    
2. 2)

   We put the qubit in the superposition in which the probabilities for 0 and 1 are the same.

    
3. 3)

   We measure the value and record the output. Because the output is random – 50% 0 and 50% 1 – we get a random bit.

    
4. 4)

   We can repeat steps 1–3 and get a random bit stream.

    

Mosca’s Theorem

See Figure 19-19. If X+Y>Z, then we have a problem because the secret will be exposed between [Z, X+Y].

The X factor is determined by the product in the organization. The organization needs to decide the update plan and the end-of-life plan for the product carefully. If X is much small, such as two years, that means your product will have its end of life before the quantum age. Then you don’t need to worry. But if the X is big in the Internet of Things (IoT) environment, such as ten years from now, then you probably need think about the transition plan.

The Y factor is the migration time from the existing infrastructure to the quantum safe infrastructure. It is determined by the readiness of the industry development environment. Currently, there are lots of activities on Y. For example, NIST started the call for proposal for the post-quantum algorithm and hopefully will provide recommendations after two or three years.

The Z factor is determined by the companies which are building the quantum computers. According to research, the large-scale quantum computers that can break 2000-bit RSA are likely to be built in 2030.

Post-Quantum Cryptography Project

Currently, there is an open quantum safe (OQS) project created on GitHub. The goal is to provide an open source library for the quantum safe cryptographic algorithms. It includes a set of key establishment algorithms and digital signature algorithms. liboqs is the open source version quantum safe API. Open quantum safe OpenSSL (OQS-OpenSSL) is a fork of the OpenSSL and adds quantum safe key exchange and authentication algorithms using liboqs for the network Transport Layer Security (TLS) protocol. This prototype can help people understand the quantum safe cryptography and prepare for the migration.

Care must be taken when we include a quantum safe algorithm implementation in the firmware. Most firmware only has limited stack and heap, while we observed that some quantum safe implementations use a large stack during runtime, which may cause the program crash. It is recommended to enable the stack guard feature to detect such stack overrun issue.

Quantum Cryptography Project

At the same time, the industry companies are creating quantum programming projects. For example, Microsoft introduced a Q# programming language and Microsoft Quantum Development Kit. People can write quantum programming code and run on a quantum platform simulation, such as quantum random number generation, BB84 protocol, Grover search, and so on. ProjectQ is an open source software framework for quantum computing with the Python language. It includes examples such as Shor’s algorithm, Grover’s algorithm, and so on. Qiskit is a rich open source framework for working with noisy quantum computers at the level of pulses, circuits, and algorithms. It includes four elements: Aer, a high-performance simulator for quantum circuit with noise; Terra, a set of tools to compose a quantum program at the level of circuits and pulses; Ignis, a framework to understand and mitigate noise in quantum circuits and systems; and Aqua, quantum algorithms and applications.