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.

ABCs of ECDSA

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.

TLA

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?”

halt

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.)

filepicker-Gw4aY4VjRsGRCvFqStvm_keep_it_real

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)

Certificate

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.

ECDSA 1

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 ATSHA204AATECC108A 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.

6 thoughts on “The ABCs of ECDSA (Part 1)

  1. Pingback: The ABCs of ECDSA (Part 2) | Bits & Pieces from the Embedded Design World

  2. Pingback: Is the Internet of Things just a toy? | Bits & Pieces from the Embedded Design World

  3. Pingback: Symmetric or asymmetric encryption, that is the question! | Bits & Pieces from the Embedded Design World

  4. Pingback: What’s ahead this year in digital insecurity? | Bits & Pieces from the Embedded Design World

  5. Pingback: Greetings from Digitopia. | Bits & Pieces from the Embedded Design World

  6. Pingback: Greetings from Digitopia! | Bits & Pieces from the Embedded Design World

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s