ECDH key exchange is practical magic

What if you and I want to exchange encrypted messages? It seems like something that will increasingly be desired given all the NSA/Snowden revelations and all the other snooping shenanigans. The joke going around is that the motto of the NSA is really “Yes We Scan,” which sort of sums it up.

Encryption is essentially scrambling a message so only the intended reader can see it after they unscramble it. By definition, scrambling and unscrambling are inverse (i.e. reversible) processes. Doing and undoing mathematical operations in a secret way that outside parties cannot understand or see is the basis of encryption/decryption.

Julius Caesar used encryption to communicate privately. The act of shifting the alphabet by a specific number of places is still called the Caesar cipher. Note that the number of places is kept secret and acts as the key. Before Caesar, the Spartans used a rod of a certain thickness that was wrapped with leather and written upon with the spaces not part of the message being filled with decoy letters so only someone with the right diameter rod could read the message. This was called a skytale. The rod thickness acts as the key.

A modern-day encryption key is a number that is used by an encryption algorithm, such as AES (Advanced Encryption Standard) and others, to encode a message so no one other than the intended reader can see it. Only the intended parties are supposed to have the secret key. The interaction between a key and the algorithm is of fundamental importance in cryptography of all types. That interaction is where the magic happens. An algorithm is simply the formula that tells the processor the exact, step-by-step mathematical functions to perform and the order of those functions. The algorithm is where the magical mathematical spells are kept, but those are not kept secret in modern practice. The key is used with the algorithm to create secrecy.

For example, the magic formula of the AES algorithm is a substitution-permutation network process, meaning that AES uses a series of mathematical operations done upon the message to be encrypted and the cryptographic key (crypto people call the unencrypted message “plaintext“). How that works is that the output of one round of calculations done on the plaintext is substituted by another block of bits and then the output of that is changed (i.e. permutated) by another block of bits and then it happens over and over, again and again. This round-after-round of operations changes the coded text in a very confused manor, which is the whole idea. Decryption is exactly as it sounds, simply reversing the entire process.

That description, although in actual fact very cursory, is probably TMI here, but the point is that highly sophisticated mathematical cryptographic algorithms that have been tested and proven to be difficult to attack are available to everyone. If a secret key is kept secret, the message processed with that algorithm will be secret from unintended parties. This is called Kerckhoffs’ principle and is worth remembering since it is the heart of modern cryptography. What it says is that you need both the mathematical magic and secret keys for strong cryptography.

Another way to look at is that the enemy can know the formula, but it does him or her no good unless they know the secret key. That is, by the way, why it is so darn important to keep the secret key secret. Getting the key is what many attackers try to do by using a wide variety of innovative attacks that typically take advantage of software bugs. So, the best way to keep the secret is to store the key in secure hardware that can protect if from attacks. Software storage of keys is just not as strong as hardware storage. Bugs are endemic, no matter how hard the coders try to eliminate them. Hardware key storage trumping software is another fundamental point worth remembering.

Alright, so now that we have a good algorithm (e.g. AES) and a secret key we can start encrypting and feel confident that we will obtain confidentiality.

Key Agreement

In order for encryption on the sender’s side and decryption on the receiver’s side, both sides must agree to have the same key. That agreement can happen in advance, but that is not practical in many situations. As a result, there needs to be a way to exchange the key during the session where the encrypted message is to be sent. Another powerful cryptographic algorithm will be used to do just that.

There is a process called ECDH key agreement, which is a way to send the secret key without either of the sides actually having to meet each other. ECDH uses a different type of algorithm from AES that is called “EC” to send the secret key from one side to the other. EC stands for elliptic curve, which literally refers to a curve described by an elliptic equation.   A certain set of elliptic curves (defined by the constants in the equation) have the property that given two points on the curve (P and Q) there is a third point, P+Q, on the curve that displays the properties of commutivity, associativity, identity, and inverses when applying elliptic curve point multiplication. Point-multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. Just for fun the shape of such an elliptic curve is shown in the diagram.

The thing that makes this all work is that EC point-multiplication is doable, but the inverse operation is not doable. Cryptographers call this a one-way or trap door function. (Trap doors go only one way, see?)  In regular math, with simple algebra if you know the values of A and A times B you can find the value of B very easily.  With Elliptic curve point-multiply if you know A and A point-multiplied by B you cannot figure out what B is. That is the magic. That irreversibility and the fact that A point-multiplied by B is equal to B point-multiplied by A (i.e. commutative) are what makes this a superb encryption algorithm, especially for use in key exchange.

To best explain key agreement with ECDH, let’s say that everyone agrees in advance on a number called G. Now we will do some point-multiply math. Let’s call the sender’s private key PrivKeySend.  (Note that each party can be a sender or receiver, but for this purpose we will name one the sender and the other the receiver just to be different from using the typical Alice and Bob nomenclature used by most crpyto books.) Each private key has a mathematically related and unique public key that is calculated using the elliptic curve equation.  Uniqueness is another reason why elliptic curves are used. If we point-multiply the number G by PrivKeySend we get PubKeySend. Let’s do the same thing for the receiver who has a different private key called PrivKeyReceive and point-multiply that private key by the same number G to get the receiver’s public key called PubKeyReceive.   The sender and receiver can then exchange their public keys with each other on any network since the public keys do not need to be kept secret. Even an unsecured email is fine.

Now, the sender and receiver can make computations using their respective private keys (which they are securely hiding and will never share) and the public key from the other side. Here is where the commutative law of point-multiply will work its magic. The sender point-multiplies the public key from the other side by his or her stored private key.  This is equates to:

PubKeyReceive point-multiplied by PrivKeySend which = G point-multiplied by PrivKeyReceive point-multiplied by PrivKeySend

The receiver does the same thing using his or her private key and the public key just received. This equates to:

PubKeySend point-multiplied by PrivKeyReceive  = G point-multiplied by PrivKeySend point-multiplied by PrivKeyReceive.

Because point-multiply is commutative these equations have the same value!

And, the rabbit comes out of the hat: The sender and receiver now have the exact same value, which can now be used as the new encryption key for AES, in their possession. No one besides them can get it because they would need to have one of the private keys and they cannot get them. This calculated value can now be used by the AES algorithm to encrypt and decrypt messages. Pretty cool, isn’t it?

Below is a wonderful video explaining the modular mathematics and discrete logarithm problem that creates the one-way, trapdoor function used in Diffie-Hellman key exhange. (Oh yeah, the “DH” in ECDH stands for Diffie-Hellman who were two of the inventors of this process.)

Are you building out for secure devices?  Protect your design investments and prevent compromise of your products? Receive a FREE Atmel CryptoAuthentication™ development tool.

ATECC108 deep dive: Part 2

Yesterday we took our first ATECC108 deep dive, exploring various features and capabilities of the device, including firmware protection, anti-counterfeiting and secure data storage. Today, we will take a closer look at the ATECC108’s advanced cryptographic operation.

As previously discussed on Bits & Pieces, Atmel’s ATECC108 implements a complete asymmetric (public/private) key cryptographic signature solution based on Elliptic Curve Cryptography and the ECDSA signature protocol. The device also features hardware acceleration for the NIST standard P256, B283 and K283 binary curves – while supporting the complete key life cycle from high quality private key generation, ECDSA signature generation and public key signature verification.

It should be noted that the hardware accelerator is capable of implementing asymmetric cryptographic operations 10 to 1,000 times faster than software running on standard microprocessors – without the usual high risk of key exposure.

“In addition, the device is designed to be able to securely store multiple private keys along with their public keys and the signature components of the corresponding certificates. The signature verification command can use any stored or external ECC public key,” an Atmel engineering rep told Bits & Pieces.

“Public keys stored within the device can be configured to require validation via a certificate chain to speed up future device authentication, while random private key generation is supported internally within the device to ensure the private key can never be known outside the device. The public key corresponding to a stored private key is always returned when the key is generated and may optionally be computed at a later time.”

Atmel’s ATECC108 also supports a standard hash-based challenge response protocol to simplify programming for developers and engineers. At its most basic, the system sends a challenge to the device, combining it with a secret key via the MAC command and subsequently returning a response. More specifically, the device employs a SHA-256 cryptographic hash algorithm for the combination such that an observer on the bus cannot derive the value of the secret key – although the recipient can verify that the response is correct by performing the same calculation with a stored copy of the key.

“Due to the flexible command set of the ATECC108, these two basic operation sets (ECDSA signatures and SHA-256 challenge-response) can be expanded in many ways,” the engineering rep continued.

“Using the GenDig command, the values in other slots can be included in the response digest or signature, which provides an effective way of proving that a data read really did originate from the device, as opposed to being inserted by a man-in-the-middle attacker. This same command can be used to combine two keys with the challenge, which is useful when there are multiple layers of authentication to be performed.”

Meanwhile, the DeriveKey command implements a key rolling scheme. Depending on the command mode parameter, the resulting operation can be similar to one implemented in a remote-controlled garage door opener. Meaning, each time the key is used, the current value of the key is cryptographically combined with a value specific to that system, and the result forms the key for the next cryptographic operation. So even if an attacker obtains the value of one key, that key will actually be gone forever with the next use.

As expected, the DeriveKey command can also be used to generate new random keys that may be valid only for a particular Host ID, for a specific time period, or for some other restricted environment. Of course, each generated key is different than any other key ever generated on any device. By activating a Host-Client pair in the field in this manner, a clone of a single client will not work on any other Host.

In a Host-Client configuration, where the Host (for instance a mobile phone) is required to verify a client (for instance an OEM battery), there is a need to store the secret in the Host in order to validate the response from the Client. The ATECC108‘s CheckMac command allows the device to securely store the secret in the Host system, concealing the correct response value from the pins by returning only a yes or no answer to the system. Where a user-entered password is required, the CheckMac command also provides a way to both verify the password without exposing it on the communications bus, as well as mapping the password into a stored value with a much higher entropy.

“The hash combination of a challenge and secret key can be kept on the device and XOR’d with the contents of a slot to implement an encrypted Read command, or it can be XOR’d with encrypted input data to implement an encrypted Write command,” the engineering rep added.

“All hashing functions are implemented using the industry-standard SHA-256 secure hash algorithm, which is part of the latest set of high-security cryptographic algorithms recommended by various governments and cryptographic experts. And yes, the SHA-256 algorithm can also be included in a HMAC sequence, with the ATECC108 employing full-sized 256 bit secret keys to prevent any kind of exhaustive attack.”

Want to learn more about Atmel’s ATECC108? Check out our official product page here.