Using the Elliptic Curve Digital Signature Algorithm effectively

Manufacturers of nearly all equipment types need to protect their products against the counterfeit components that aftermarket companies will attempt to introduce into the OEM supply chain. Secure authentication provides a strong electronic solution to address this threat.

Traditionally, authentication systems have relied on symmetric algorithms such as secure hash algorithms [1] that require secret keys. The management and protection of the secret keys, however, can be challenging. A welcome alternative to this logistics problem is elliptic curve cryptography (ECC), where all participating devices have a pair of keys called “private key” and “public key.”

The private key is used by the originator to sign a message, and the recipient uses the originator’s public key to verify the authenticity of the signature. If a message is modified on its way to the recipient, the signature verification fails because the original signature is not valid for the modified message. The Digital Signature Standard (DSS), issued by the National Institute of Standards and Technology (NIST), specifies suitable elliptic curves, the computation of key pairs, and digital signatures.[2]

This article discusses the Elliptic Curve Digital Signature Algorithm (ECDSA) and shows how the method can be used in practice.

Elliptic curves
Many readers will associate the term “elliptic” with conic sections from distant school days. An ellipsis is a special case of the general second-degree equation ax² + bxy + cy² + dx + ey + f = 0. Depending on the values of the parameters a to f, the resulting graph could as well be a circle, hyperbola, or parabola. Elliptic curve cryptography uses third-degree equations.

The DSS defines two kinds of elliptic curves for use with ECC: pseudo-random curves , whose coefficients are generated from the output of a seeded cryptographic hash function; and special curves , whose coefficients and underlying field have been selected to optimize the efficiency of the elliptic curve operations. Pseudo-random curves can be defined over prime fields GF(p) as well as binary fields GF(2m) .

A prime field is the field GF(p) , which contains a prime number p of elements. The elements of this field are the integers modulo p ; the field arithmetic is implemented in terms of the arithmetic of integers modulo p . The applicable elliptic curve has the form y² = x³ +ax + b. Figure 1 shows an example of an elliptic curve in the real domain and over a prime field modulo 23. A common characteristic is the vertical symmetry.

Figure 1: Third-degree elliptic curves, real domain (left), over prime field (right)

A binary field is the field GF( 2m) , which contains 2m elements for some m (called the degree of the field). The elements of this field are the bit strings of length m ; the field arithmetic is implemented in terms of operations on the bits. The applicable elliptic curve has the form y² + xy = x³ + ax² + b.

Although there is a virtually unlimited number of possible curves that meet the equation, only a small number of curves is relevant for ECC. These curves are referenced as NIST Recommended Elliptic Curves in FIPS publication 186 . Each curve is defined by its name and domain parameters set, which consists of the Prime Modulus p, the Prime Order n, the Coefficient a, the Coefficient b, and the x and y coordinates of the Base Point G(x,y) on the curve. Table 1 , for example, shows the domain parameters of curve P-192, which is a pseudo-random curve over a prime field. For more examples, see Reference 2. The numeric portion of the curve’s name indicates the length of the private key in bits. The size of public key and the digital signature is twice the length of the private key.

Table 1: Domain parameters of Curve P-192

Mathematical background
Elliptic curve cryptography involves scalars and points. Typically, scalars are represented with lower-case letters, while points are represented as upper-case letters, as in Table 1. Three numerical operations are defined for scalars: addition (+), multiplication (*) and inversion (-1). There are two numerical operations for points: addition (+) and multiplication (×). Although the symbol “+” is used for scalars and points, a point addition follows different rules than the scalar addition. These operations apply to curves over prime fields, as well as curves over binary fields. Algebraic formulae to perform these computations are found in Reference 3.

Computations needed for ECDSA authentication are the generation of a key pair (private key, public key), the computation of a signature, and the verification of a signature. The corresponding equations are found in public literature.[2] [3] [4] Unfortunately, different authors use their own conventions, which makes it difficult to follow their explanations. To bridge this gap, the equations are included here, strictly adhering to the conventions above.

Key pair generation
Before an ECDSA authenticator can function, it needs to know its private key. The public key is derived from the private key and the domain parameters. The key pair must reside in the authenticator’s memory. As the name implies, the private key is not accessible from the outside world. The public key, in contrast, must be openly read accessible. Figure 2 illustrates the generation of the key pair.

Figure 2: Key pair generation process

A random number generator is started and, when its operation is completed, delivers the numeric value that becomes the private key d (a scalar). Next, the public key Q(x,y) is computed according to Equation 1 through point multiplication:

Signature computation
A digital signature allows the recipient of a message to verify the message’s authenticity using the authenticator’s public key. First, the variable-length message is converted to a fixed-length message digest h(m) using a secure hash algorithm.[1] A secure hash has the following distinctive properties:

  • irreversibility—it is computationally infeasible to determine the message from its digest;
  • collision resistance—it is impractical to find more than one message that produces a given digest; and
  • high avalanche effect—any change in the message produces a significant change in the digest. After the message digest is computed, a random number generator is activated to provide a value k for the elliptic curve computations. Figure 3 illustrates the process.

Figure 3: Signature computation process

The signature consists of two integer numbers, r and s. Equation 2 shows the computation of r from the random number k and the base point G(x,y):

To be valid, r must be different from zero. In the rare case when r is 0, a new random number, k, must be generated and r needs to be computed again.

After r is successfully computed, s is computed according to Equation 3 using scalar operations. Inputs are the message digest h(m); the private key d; r; and the random number k:

To be valid, s must be different from zero. If s is 0, a new random number k must be generated and both r and s need to be computed again.

Signature verification
The signature verification is thecounterpart of the signature computation. Its purpose is to verify themessage’s authenticity using the authenticator’s public key. Using thesame secure hash algorithm as in the signature step, the message digestsigned by the authenticator is computed which, together with the publickey Q(x,y) and the digital signature components r and s, leads to theresult. Figure 4 illustrates the process.

Figure 4: Signature verification process

Equation 4 shows the individual steps of the verification process. Inputs are themessage digest h(m), the public key Q(x,y), the signature components rand s, and the base point G(x,y):

Theverification is successful (“passes”), if x2 is equal to r, thusconfirming that the signature was indeed computed using the private key.

Hardware configuration
Check subscript: Implementing asecure authentication system requires linking a host system with aperipheral module (Figure 5). The host controller communicates with theauthenticator over a serial bus. Any bus type could be chosen. Thesingle pin of the 1-Wire interface plus ground reference (no clock, noVCC) is particularly attractive since it minimizes interconnectcomplexity, simplifies designs, and thus reduces cost. New in Figure 5are the System Public Key and the System Constant on the host side, andthe Device ID# and the Public Key Certificate on the peripheral side.

Figure 5: Hardware configuration of an ECDSA authentication system

Authenticator setup
Beforean authenticator can be used in an application, it must be set up. Thefirst step is the computation and installation of a key pair (see Figure 2 ).The key pair can be computed externally and then be written to theauthenticator. Alternatively, the authenticator may include a functionblock that performs this step upon external command. To preventunauthorized changes, the key pair must be write protected.

Anapplication can choose between two usage scenarios. In scenario 1 allauthenticators are programmed with the same key pair. In this case, allhosts in the system know the valid public key. Any authenticator withthat public key is considered a member of the application. No furthermeans are needed to verify the authenticator itself.

In scenario2 each authenticator has its own unique key pair. In this case,successful signature verification does not provide evidence that aspecific authenticator device is also a member of a particularapplication, i.e., the “system.” Linking an authenticator to a systemrequires the introduction of a certificate, which is computed like asignature from the authenticator’s public key, the authenticator’sunique device ID#, a system constant, and the system private key. Figure6 shows the computation of the certificate, as it could be performed bya key-management system, also known as “certification authority.” Thetwo components of the certificate, cr and cs, are then stored in theauthenticator’s memory and write protected. This concludes theauthenticator setup. Note that in scenario 2 the host system must knowboth the system public key and the system constant to verify thevalidity of the authenticator’s public key in the application.

Figure 6: Certificate generation by a key-management system

Theinfrastructure supporting the management of certificates is called aPublic Key Infrastructure. Through such an infrastructure one cangenerate certificates and provide means for their verification. Anotherbenefit of such infrastructure is the ability to support goodsmanufactured by third parties or subcontractors. Assuming that asubcontractor has manufactured goods with embedded ECDSA authenticatorsand that each authenticator has its own statistically unique key pair,then signing their public key to generate the certificate makes themjoin the system.

Authentication of a deployed peripheral
Figure 7 shows the typical sequence of steps. First, the authenticator ispowered up (Steps 1, 2). Then the host obtains the authenticator’sDevice ID#, and reads the public key and the certificate (Steps 3 to 7).Now the host performs the signature verification algorithm for thecertificate (Step 8, Figure 8). If the result is “pass,” the public keyis valid in the system. If the result is “fail,” the authenticator doesnot belong to the system; the host can skip Steps 9 to 12 andimmediately deactivate the authenticator (Steps 13-15).

Figure 7: Typical transaction flow to authenticate a deployed peripheral

Figure 8: Verifying the authenticator’s public key using the certificate

Knowingthat an authenticator’s public key is valid in the system does notguarantee that the host is communicating with a genuine authenticator.The data used so far could also have come from an emulator that tries toperform a replay attack.

To determine whether the authenticatorin the peripheral is genuine, the host reads one of the authenticator’smemory pages (Step 9), sends a random challenge to the authenticator(Step 10), and instructs it to compute a signature. The message consistsof the memory page data, the challenge, the device ID#, page # pluspadding and formatting. Figure 9 shows how an ECDSA authenticatorcomputes a signature. The signature is computed in real time using theauthenticator’s hardware ECDSA engine. The signature’s two components rand s are sent to the host (Step 11) for verification. Note that thesignature computation involves the authenticator’s private key and arandom number. Consequently, even if the challenge stays the same,subsequent signature computations deliver different signature values.

Figure 9: Signature computation performed by the authenticator

Figure 10: Verifying the signature computed by the authenticator

Nowwith all the necessary data including the signature, the host computesthe message digest and performs the signature verification algorithm forthe signature (Step 12, Figure 10 ). If the result is “pass,” theauthenticator is verified as genuine. If the result is “fail,” the keypair in the authenticator is not valid and the host rejects theperipheral.

Affordable Elliptic-curve public-key authentication security
TheDigital Signature Standard was originally released in 1994 and for along time ECDSA authentication was mostly a subject of theoreticalresearch. This situation changed recently with products such as theDeepCover Secure Authenticator DS28E35, the first ECDSA authenticatorwith 1-Wire interface and 1Kbit user EEPROM. DeepCover-embedded securitysolutions cloak sensitive data under multiple layers of advancedphysical security to provide the most secure key storage possible.

Itimplements ECC using a pseudo-random curve over a prime field accordingto equation y² = x³ +ax + b using the domain parameters of curve P-192 (Table 1 ).The device can compute, install, and lock the private/public key pairon its own; it does not need any outside help. Separate memory space isset aside to store and lock a public-key certificate.

The devicealso features a one-time-settable, nonvolatile, 17-bitdecrement-on-command counter. This counter can be used to track thelifetime of the peripheral in which the secure authenticator isembedded. Each device has its own guaranteed unique 64-bit device ID#factory programmed into the chip. As shown above, the device ID# is afundamental input parameter for cryptographic operations.

The simplicity of the 1-Wire interface (using only I/O and GND in Figure 5 )facilitates the use of the secure authenticator in a broad array ofapplications. As a value-added service option, device setup (key pair,certificate) including user-memory programming and counterinitialization can be performed by Maxim’s secure factorypersonalization service. This service is a secure method for configuringparts prior to shipment into the OEM supply chain. It thus eliminatesthe possibility of exposure of sensitive data and offloads the necessarykey management systems and efforts.

Summary
The mainbenefit of ECDSA is that the party authenticating the peripheral isrelieved from the constraint to securely store a secret. Theauthenticating party can authenticate thanks to a public key that can befreely distributed. Authentication ICs, such as those among Maxim'sDeepCover embedded security solutions, help simplify implementation ofrobust challenge-response authentication methods that form thefoundation of more effective application security. The ECDSAauthenticators also enable easier authentication of goods from thirdparties or subcontractors.

References
1. Secure Hash Standard (SHS) , National Institute of Standards and Technology (NIST), March 2012.

2. Digital Signature Standard (DSS) , National Institute of Standards and Technology (NIST), 2013.

3. An Elliptic Curve Cryptography based Authentication and Key Agreement Protocol for Wireless Communication, Oregon State University, 1998.

4. Implementation of Elliptic Curve Digital Signature Algorithm , International Journal of Computer Applications, May 2010.

Bernhard Linke is a Principal Member of the Technical Staff working on securesolutions for Maxim Integrated. He was with Dallas Semiconductor from1993 until that company merged with Maxim in 2001. He previously workedfor Astek Elektronik Vertriebs GmbH, a distributor in Kaltenkirchen,Germany, and in various positions at Valvo Röhren und Halbleiterwerkeder Philips GmbH in Hamburg, Germany. He received a Diplom-Ingenieurdegree in Allgemeine Elektrotechnik from the Rheinisch-WestfälischeTechnische Hochschule in Aachen, Germany.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.