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.