The ABCs of ECDSA (Part 2)

Part 2 of The ABCs of ECDSA (“Sign-Here”) will describe how digital certificates are made and signed. In the previous article (The ABCs of ECDSA: Part 1), we examined the steps of ECDSA performing asymmetric authentication using digital certificates. You may have noticed that both Part 1 and Part 2 are in reverse chronological order; however, it makes better sense to first understand a bit about the actual authentication process before dissecting the details of making the certificate. (Just trust me on that.) Before we get into the nuances of the certificate, let’s recall that authentication is about keeping something real. Such things would be mobile, medical and consumer accessories; embedded firmware; industrial networks; and soon the new platforms of IoT, home automation, and vehicle-to-vehicle communications. Aside from those, there are several others given the fact that the need for authentication is increasing exponentially as more things communicate with each other, and through the cloud, are creating more opportunities for bad actors to apply their mal-intent.

Especially with the increased use of the Internet and the cloud for financial transactions and transmission of confidential personal/medical information, it’s critical to ensure that the sender of information is exactly who they are supposed to be, as well as that the data has not been tampered with. That is where authentication and hardware key storage come in. Here we will focus on asymmetric authentication. Asymmetric authentication using ECDSA is based upon a digital certificate, which in this case, is stored in the ATECC108A device.

So, now let’s go into the chip factory and see how the ECDSA certificate is made and stored in the device. Remember that ECDSA stands for Elliptic Curve Digital Signature Algorithm. The words “Elliptic Curve” are in the name because Elliptic Curve Cryptography (“ECC”) algorithms are used. No mystery there. The benefit of ECC is that it provides extremely strong security with shorter key lengths than other popular algorithms. Bitcoin, for example uses ECC predominantly for that reason.   (We won’t go into Bitcoin here.) “DSA” points to the fact that digital signatures are the key element of the process, which is also fairly self evident. The digital signing process is what we describe here, step by step. “Certificate” is the name given to the concept of putting certain types of data together in a prescribed format and then signing that data using hashing algorithms and signing algorithms. (Again, the usage of the certificate is covered in Part 1.)

While we are fully immersed here in cryptographic alphabet soup, we might as well add one more thing to it: The prescribed format used in the ECDSA in the ATECC108A is called ASN.1. ASN.1 basically defines what is what in the certificate, including the serial number, the public key and that sort of thing. It also defines the length of those data elements.

Now, back to building the certificate: The certificate is made and loaded in the key storage device in the chip factory. It is made from two main components:

1. The certificate data 
2. The signature

The certificate data is a collection of data from three sources:

1. Static data: Boiler plate type data that does not change, such as the name and address of the manufacturer. (This is the ASN.1 encoded stuff.)
2. Dynamic data: Data from the tester that can change with each device such as time, date, and serial number.
3. Client device’s public key, which has an algorithmic relationship to the client’s private key that will be securely stored in the client device.

The certificate data is formatted according to X.509 specifications (yes, more crypto jargon). X.509 defines the elements and order of the elements in the certificate, such as  serial number, public key, subject’s common name (i.e. the name of the certificate), authority ID (normally a SHA-1 hash of the public key), authority common name (i.e. the name of the authority that signs the certificate data), among other things. We will leave more about X.509 for another day.

The certificate data comprises just half of the certificate, the other half is the signature. What is a little tricky to understand at first is that the certificate data do two things: (1) become part of the certificate as it is, and (2) gets hashed and signed to make the signature. Both the certificate data itself and the signature make up the certificate.

The specific steps in order to make the signature begins with a copy of the certificate data being put through a hash algorithm to create a number called a hash value (or digest). ECDSA specifies a 32 byte digest length and SHA256 as the hashing algorithm. Once created, the digest is ready to be signed by the sign module in the factory.

The sign module is a piece of equipment that securely stores the signer’s private key. No one can get access to that key. The sign module uses the ECC sign algorithm to sign the digest of the certificate data with the signer’s private key. The result of that process becomes the “signature.” The signature then joins the original (i.e. unhashed) certificate data to complete the certificate. Note that the signing key is tied to the OEM’s root key to create the root of trust (the notion of root of trust will be addressed in another article).

The certificate is now finished and can be installed into the crypto device. Once the device is finished, it is then shipped to the customer’s factory to be assembled into an accessory, consumable, board or any number of things, i.e. a consumable water filter that later gets installed into refrigerator. In this scenario, when a new filter is installed by the consumer into the refrigerator when the old filter expires, the new filter will be authenticated by the host processor in the refrigerator according to the ECDSA process as described in The ABCs of ECDSA (Part 1).

Below is a video (sorry, no sound) that will visually help walk you through the steps noted above.

Benefits of asymmetric authentication with ECDSA include:

• Increased security because asymmetric authentication does not need secure key storage on the host (only the client)
• No need to update the host with secrets in the field (can update the public key at any time.)
• Uses the advantages of Elliptic Curve Cryptography (high security, short key, less computation)

Atmel CryptoAuthentication™ products such as Atmel’s ATSHA204A, ATECC108A  and ATAES132 implement hardware-based storage, which is much stronger then software based storage because of the defense mechanisms that only hardware can provide against attacks. Secure storage in hardware beats storage in software every time. Adding secure key storage is an inexpensive, easy, and ultra-secure way to protect firmware, software, and hardware products from cloning, counterfeiting, hacking, and other malicious threats. 

If you have yet to read the first portion of this article, you can find The ABCs of ECDSA (Part 1) here.

 

 

 

The ABCs of ECDSA (Part 1)

One of the major difficulties in explaining anything cryptographic, among many other things, is what I call “Acry-phobia” which is fear of cryptographic acronyms. This is a justified condition.

Acryphobia is far from irrational because in cryptography (since it is math) every little thing and the relationships between them must be defined, specified, examined, theorized, tested, formulated, processed, scrutinized, proved, and…. well, you get the picture. Simply stated, this means there’s a whole lot to it. Therefore, in order to teach cryptographic concepts, it’s imperative to focus on a specific area at a time and then break that down further into its fundamentals: That is sort of like breaking down the works of Shakespeare first into episodes, then into Old English then modern English and finally the ABCs. In pretty much similar fashion, that is what we want to do here. Namely, focus on one type of authentication scheme and break it down into its fundamentals and explain those one step at a time.

The specific fear-inducing cryptographic acronym we will try to overcome during this session (and one more after it) is ECDSA, or Elliptic Curve Digital Signature Algorithm.

To quickly dispel some of the Acryphobia, let’s look at authentication from a less mathematical viewpoint.

The basic idea of authentication (just like the name says) is to authenticate, meaning to confirm that the sender of a message is exactly who they say they are. Confirmation is the key to authentication and it requires using some type of trusted credential from another party to verify a declared identity. As noted in an earlier article, this identity confirmation process is sort of like those scenes in old movies where a guard of some type challenges an approacher by saying, “Halt! Who goes there?”

Once challenged, the approacher must respond by identifying himself (or herself) and produce a document (certificate) with the signature or seal of the king, general, or some other trusted authority to confirm that the bearer is not an impostor.  That seal or signature links the approacher to a recognized, trusted signer/sealer. The signer/sealer can be described therefore as the certificate authority. (Note that “Certificate Authority” is in fact a technical cryptographic term.)

Cryptographic authentication is just the mathematical version of this challenge-response-certificate-signing-verification process. It uses digital processors, rather than people with bayonets or other weapons of choice.

Getting back to the math, the type of authentication we are discussing in this article is asymmetric, meaning that the secret key is not stored on both the host and client (like with symmetric authentication). Asymmetric authentication stores the secret key on the client side only and then the uses certain mathematical algorithms on certain prescribed information that the client sends it for the ultimate purpose of verifying that the client is real. ECDSA is one of the available types of processes, and what we are going to explore throughout the rest of the article, in a step-by-step fashion. Later on, in an upcoming article, we will address the details about how the crypto devices are originally loaded in the chip factory with the important information needed to make ECDSA authentication happen out in the real world.

So, let’s get into the asymmetric authentication process, which  typically begins when a client device is inserted into a host system or the host system wants to know what exactly is connected to it. Examples include a printer ink cartridge being inserted into a printer, a thermostat control block wanting to talk to a remote temperature sensor, a cell phone connecting to a wall charger, among a number of others.

ECDSA (Elliptic Curve Digital Signature Algorithm) is a two-phased process:

• Phase 1 is to verify that the public key on the client
• Phase 2 is to verify the private key on the client.

If both phases pass these two verify calculations then the client is verified as real (i.e. by showing that there is a valid private-public key pair in the client).

(Remember that authentication of any type is meant to keep something real. How the keys are used defines if the process is symmetric or asymmetric.)

The steps of ECDSA are depicted in the diagrams below. In this particular example, the illustrations are based upon a host system that contains a microcontroller and a client (accessory) equipped with an ATECC108A secure key storage device.

Phase 1 starts with the host requesting information to be sent over by the client (accessory). That information comes over to the host as a “certificate.” This certificate is made and then programmed into the crypto device in the chip factory. For now, we’ll start with the already assembled, stored and ready-to-use certificate.

The certificate contains two main things:

1. Certificate data (made up of the client’s public key + static data + dynamic data)
2. Signature (made by hashing that certificate data and the signer’s secret key in the chip factory)

When the host receives the certificate, it extracts the certificate data (static data, dynamic data, and client public key) and the signature (made by the signing module in the chip factory). The host runs the same hashing that was used in the chip factory on the certificate data it just received, creating a 32-byte message digest that will be used in the phase one ECDSA calculation. If the client is real, then this hash function run in the host should have the exact same result (digest) as the one that was run the chip factory to create the signature.

On the host, the message digest made from the received certificate data, the signer’s public key, which also came over from the client (more on how that arrives will be in yet another article), and the signature from the certificate are put into the ECDSA verify calculation. If the ECDSA calculation is successful, the client’s public key is considered to be real. That then starts phase 2 to verify the client’s private key.The whole point of this two-phase process is to verify mathematically that the client’s private key and public key are indeed a valid key pair.

The goal of phase two is to verify the client’s private key. This phase begins with the host generating a random number challenge and sending it to the client. The client device uses the ECDSA signature engine in the ATECC108A to create a new signature using this random number and the client’s (secret) private key stored there. That new signature is then sent to back the host, which uses it along with the random number and the client’s public key (that was verified in phase one) as inputs to another ECDSA verify calculation. If that calculation succeeds, the host has then proven that the accessory (client) is real (i.e. contains a valid private-public key pair)

As you can see, the ATECC108A does all the heavy mathematical lifting, and Atmel provides what users need to make it easy to program the microcontroller to do its part of the process. The engineering and mathematics behind authentication using sophisticated algorithms may not be easy in theory, but that does not matter as Atmel makes it simple to implement cryptography without having to be a cryptography expert…. and that is the “REAL” point here.

The video (now with sound) will step you through the two phases of the ECDSA process described above.

So, in summary, the key aspects of asymmetric authentication with ECDSA include:

• Increased security because asymmetric authentication does not need secure key storage on the host (only the client)
• No need to update the host with secrets in the field. (can update the public key at any time.)
• Uses the advantages of Elliptic Curve Cryptography (high security, short key, less computation)

Atmel CryptoAuthentication™ products such as Atmel’s ATSHA204A, ATECC108A and ATAES132 implement hardware-based storage, which is much stronger then software based storage because of the defense mechanisms that only hardware can provide against attacks. Secure storage in hardware beats storage in software every time. Adding secure key storage is an inexpensive, easy, and ultra-secure way to protect firmware, software, and hardware products from cloning, counterfeiting, hacking, and other malicious threats. For more details on Atmel CryptoAuthentication products, head on over to its introduction page here.

Plese read   The ABCs of ECDSA (Part 2: Sign Here) to see how the certificate is built and signed in the chip factory.

The “Key” to Reality

If we wanted to reduce the definition of authentication to its most Zen-like simplicity, we could say authentication is “keeping things real.” To keep something real you need to have some sort of confirmation of its identity, as confirmation is the key (so to speak).

The equation could be as follows:

Identification + Confirmation = Authentication

Confirming or validating the identity of a document, item, data, etc. is what keeping things real is all about. Some of the “things” that can be authenticated with cryptographic methods are mobile, medical, and consumer accessories; embedded firmware; industrial network nodes; and sensors, among others. Soon IoT and vehicle-to-vehicle communication will join in.

Authentication is far more important than many people realize, especially in our growing hyper-connected world that now links billions of people (and things). In cyber-land, authentication is accomplished by deploying cryptographic keys and algorithms. Keys are fundamental to keeping things real—so that is what we mean by “the key to reality.”

There are two primary types of Authentication: Symmetric and Asymmetric. Atmel offers secure key storage devices for both types. These two important techniques take their names directly from whether the keys on each side (i.e. the host and client sides) are the same or different.

Symmetric Authentication

If the same secret key is used on the client and on the host, then the application is symmetric, just like the name suggests. Both of the symmetric keys must be protected because if either one gets out then the security will be lost. This is perhaps analogous to having two sets of car keys. Meaning, losing either one makes it easy for a thief to drive away with your car. So, the secret keys must stay secret.

Symmetric Keys are the Same

The identical keys on the host and client are used in mathematical calculations to test the reality of client devices. A very common mathematical calculation that is used is a hash function based upon a cryptographic algorithm (such as SHA). A hash operation produces a hash value (also called “digest”), which is a number of a specified length that is usually smaller than the numbers used as the inputs. A hash is a one-way operation, which means that the inputs cannot be recreated from the hash value.

With symmetric authentication a typical process is to challenge the client device to be authenticated by sending it a random number. The client then puts the random number challenge and a secret key into the hash algorithm to create a hash value, which is known as the “response.” Each challenge will generate a unique response.

It should be noted that cryptographers call a hash of a random number with a secret key a “Message Authentication Code” or “MAC.” The diagram below illustrates this process. Because the host key is the same on the host and client sides, the exact same calculation can run on the host. Once that happens, the hash values (“MACs”) from each can be compared. If the hash values match, the client is considered to be real. You can see that symmetric authentication is really a simple process, but it is loaded with mathematical elegance. Now let’s look at asymmetric authentication.

Hashing a Random Number with a Secret Key

 

Asymmetric Authentication.

Asymmetric keys are presented in public-private pairs. More specifically, the public and private keys are related to each other via a mathematical algorithm. An example would be the Elliptic Curve Cryptography (or “ECC”) algorithm. Only the private key has to be securely stored. Because the keys are different, asymmetric authentication cannot use the same calculate-and-compare process as symmetric.

Asymmetric requires more complicated techniques such as making digital signatures that are verified for authenticity (this is called “Sign-Verify”). An example of asymmetric authentication using ECC algorithms is Elliptic Curve Digital Signature Algorithm (or “ECDSA”).  A major benefit of the Atmel ATECC108A device is that it can be used to easily implement ECDSA sign-verify. (The steps of ECDSA are very interesting, but they will be covered in a separate article). Note that an important trade-off between symmetric and asymmetric authentication is the speed of operation. For example, authentication time for the Atmel ATSHA204A is 12ms (typical) for symmetric versus more than a second for many microcontrollers to execute an asymmetric ECDSA operation.

Getting back to the keys:   The secret keys must stay secret. If keys are the keys to authentication (i.e. reality),  then secure storage of the secret keys is the key to SECURE authentication. And that is the real point here.

So the, how is secure storage implemented? The best way is to use hardware key storage devices that can withstand attacks that try to read the key(s). Atmel CryptoAuthentication products such as the ATSHA204A, ATECC108A  and ATAES132 implement hardware-based storage, which is much stronger than software based storage because of the defense mechanisms that only hardware can provide against attacks. Secure storage in hardware beats storage in software every time. Adding secure key storage is an inexpensive, easy, and ultra-secure way to protect firmware, software and hardware products from cloning, counterfeiting, hacking, as well as other malicious threats.

For more details on Atmel CryptoAuthentication products, please view the links above  or the introduction page CryptoAuthentication. Future Bits & Pieces articles will take in an in-depth look at how symmetric and asymmetric authentication is accomplished.         

A closer look at Atmel’s ATECC108

Atmel recently expanded its CryptoAuthentication portfolio with the ATECC108 solution, an elliptical curve cryptography (ECC) product. As Atmel Product Marketing Manager Alex Dean notes, there are two basic encryption methods available on the security market today: symmetric and asymmetric key based algorithms.

“In the context of using cryptography for authentication, symmetric key encryption uses an identical key on both a host and its client, while asymmetric key encryption employs two related keys (public and private),” Dean told Bits & Pieces.

“Perhaps most importantly, asymmetric key encryption eliminates the security risk of key sharing, as the private key is never exposed. Essentially, a message that is signed using the private key can only be verified by applying the same algorithm via a matching public key.”

Symmetric key algorithms are significantly faster computationally than asymmetric algorithms, as the encryption process is less complicated. As such, symmetric key solutions like Atmel’s ATSHA204 are quite versatile for a wide variety of use cases, including mobile items (smartphones, tablets), medical devices, industrial automation and smart energy, as well as any application where host-client authentication is needed. In addition to its asymmetric key attributes, the ATECC108 also performs symmetric key algorithm and is backward compatible to ATSHA204.

So when is an asymmetric key solution most appropriate? According to Dean, a complex medical platform (static) can best illustrate the need for an asymmetric key approach – specifically when such a system does not share the same key with an accessory (dynamic).

“When it comes to medical care, doctors and nurses want to ensure an accessory connected to hospital equipment is legitimate and not a cheap knockoff clone which can potentially endanger the lives of patients under their care. We know static systems are stringently reviewed by the FDA – and a hardware modification to implement security often triggers a lengthy re-approval process. However, their accessories and attachments, such as probes or catheters, are typically manufactured for one-time use and therefore subject to a different and sometimes less stringent regulation,” he explained.

“So an asymmetric key solution such as Atmel’s ATECC108 is most appropriate here. It is not necessary to modify any hardware on the static system to implement a public key, which by definition does not have to be protected. Inserting an ATECC108 to the accessory to protect the private key needed for authentication does not necessarily trigger re-certification due to different regulations that regulate the dynamic system – especially when the modification could be considered administrative (such as authentication), rather than medical. In short, an asymmetric key approach enables a medical equipment manufacture to quickly modify a medical system to ensure a host will only function with a genuine OEM accessory or peripheral manufactured by an authorized third party supplier. Remember, software is quite easy to compromise, so you need to protect the private key in the accessory or peripheral with ironclad hardware like the ATECC108.”

Similarly, since the public key on the static system does not require protection, systems already deployed in the field can be easily retrofitted with such a key via a simple administrative software upgrade involving the host system – a strategy that neatly avoids a time consuming FDA re-certification for a static hospital platform.

“Plus, the ECC algorithm (used by ATECC108) is far more efficient than RSA, which requires 3,000 bits to accomplish what the ECC can do with 256 bits. The RSA is slower, because it has to process such a large key size. That is why we see the industry shifting towards an ECC approach,” added Dean.

Lastly, in addition to the traditional UDFN and SOIC packages, the ATECC108 also offers a three-lead contact package that does not require a PCB and can be laminated directly to an item.