By: Cheong Wei Chua, System Program Manager, Future Electronics
Hacking, cloning, and counterfeiting are risks which many electronic manufacturers need to contend with. Some manufacturers have implemented mechanical systems or labels to protect their products, but these trivial mechanisms do not deter counterfeiters if the rewards are large. Hence, suppliers of crypto solutions offer embedded security to counter these risks. However, it is a challenge for design engineers to not only understand the applications, but the basic theory of cryptography. This primer serves to explain key cryptography concepts which are the building blocks of embedded security.
There are two basic ideas around security. The first one is authentication which means making sure that the client in question is authentic. The second is data protection; that means data is transmitted confidentially (via encryption) and that the integrity has not been compromised. For example, data can be maliciously replaced or modified during transmission.
Let’s start with a basic problem statement. Bob would like to send a private message to Alice through a channel. However, the channel is not secure; as a consequence Eve could listen in on the channel and get the message.
The solution would be to encrypt the message before sending it though the channel. Once Alice receives the message, she would decrypt the message. No one else can decrypt the message unless they have the key as illustrated below. In crypto language, plaintext refers to the message which Bob wants to share with Alice. He uses a scheme and a key to scramble the message. This encryption process results in a ciphertext which Eve is unable to unscramble. Alice, on the other hand, was privy to the scheme and key, and therefore is able to decrypt the ciphertext to obtain the original plaintext. The next section talks about the different classical ciphers.
The Shift Cipher
One of the earliest ciphers that was used is the Shift Cipher. This cipher was also used by Julius Caesar for his personal correspondence, hence the name Caesar’s cipher. The idea is to shift the plaintext by a fixed amount. In this simple example, “o” becomes “Q”and “n” becomes “P” after shifting by 2 places. So Bob encrypts using Key = 2, and Alice will reverse shift the ciphertext by 2 when she receives it. However this encryption scheme is rather weak. Eve can methodically try shifting all the letters in the alphabet. This brute force approach works as they are only 25 keys to try before breaking the code!
The Substitution Cipher
In order to deter a brute force approach, another scheme based on assigning an arbitrary ciphertext for each plaintext is shown in the following example:
Hence, for Bob to encrypt his message, all he has to do is look up the ciphertext letter in the table. For example, if “cab” is the plaintext, then “PLQ” is the ciphertext. Since Alice also knows the cipher, she could easily decrypt the ciphertext.
However Eve does not have the table, thus she will not be able to decrypt the message easily. And if she wants to endeavor to use a brute force approach there are 26! or 403291461126605635584000000 attempts in order for her to break the code.
The Weakness of the Substitution Cipher
Nevertheless Eve remains undeterred. She has another trick up her sleeve. She can exploit the fact that certain letters in the English language are used more frequently than others. If we look at a ciphertext, we can count the occurrence of each letter, and compare that to the frequency of letters in a regular text.
In the following table, we can see that the most frequent letter in the English language is E, followed by T, A and O.
Thus all Eve needs to do is to match the frequency of letters that occur in the ciphertext with the established frequency of regular English text!
For example, if we calculated the frequency of ciphertext and found that the occurrences of the following in decreasing order is “p, b, a, t and m”, it is likely that these letter correspond to the letters “e, t, a, o and i” respectively as these are the most common letters in English!
Classical to Modern Cryptography
The shift and substitution cipher form the basis of classical cryptography. It can be done by hand to some degree. Modern cryptography is based on the same principles but with the advent of computers, automation allows ciphers to become much more complex.
The two most important ciphers in modern cryptography are:
1. Data Encryption Standard (DES)
2. Advanced Encryption Standard (AES)
DES was developed by IBM in 1976 when the US Government wanted a standardized cipher for their secret documents. The development of DES was actually the origin of modern cryptographic research. But DES was short lived because the key length was too short. For example, if the key was 56-bits long, there are 256 possible keys. With the advent of faster computers, machines were designed to simply apply brute force to crack the code. The response was to increase the key length to 128-bits and to introduce Triple DES. However, in 1990, Biham and Shamir discovered differential cryptanalysis which exploited the fact that DES was not truly random! With DES effectively cracked, a new cipher was required. In an open competition, which saw the world’s best cryptologists, the Rijndael cipher was selected in 2001 to become the Advanced Encryption Standard which is widely known as AES today. Nearly 20 years have passed, and and no one has yet to come up with a practical way to break AES. It was chosen because it can be implemented in software and hardware, and it is fast, flexible and future-proof.
The Drawback of AES: How to Share the Secret Key?
As shown below, both Alice and Bob share a secret key. What if Alice were in India and Bob were in Africa? Just how would they share the key? Bob can’t email the key to Alice as Eve is eavesdropping. Alice and Bob would have to meet physically to agree on a secret key. Obviously this is problematic if we always had to meet in person to establish the secret keys. This is the drawback of symmetric key cryptography. DES and AES use symmetric key cryptography.
The Solution to Symmetric Key Cryptography Drawback: Public Keys
In 1976, Diffie and Hellman published a paper to address this challenge. The approach was to use one key for encryption and different key for decryption. Here is how it works. Bob sends out a public key. Everyone including Alice and Eve would obtain this key freely. Alice then uses Bob’s public key to encrypt her plaintext. Everyone is privy to this ciphertext but only Bob can decrypt the ciphertext because Bob is the only one who has the corresponding private key. The magic happens because of the pairing of public and private keys. The private key must never be shared. This scheme is also known as asymmetric key cryptography.
Asymmetric Key Cryptography: Authentication and Non-repudation
Another use of asymmetric key cryptography is authentication and non-repudation. Alice can use her private key to sign a plaintext. When Bob receives the ciphertext, he uses Alice’s public key to decrypt the message. He can only succesfully decrypt the message if it was truly encrypted/signed by Alice. Eve would not have been able to sign the message as Alice since Eve does not have the private key. Furthermore, Alice cannot deny that the ciphertext orginated from her as her key is her signature. This is known as non-repudation.
RSA Public Key1
One of the most popular public pey ciphers is RSA which is named after the creators: Rivest, Shamir, and Adleman. The idea uses the fact that it is difficult to factor large numbers. Here is the recipe of RSA:
1. Choose two different large random prime numbers p and q
2. Calculate n=pq
• n is the modulus for the public key and the private keys
3. Calculate the totient: φ(n) = (p–1) (q_1)
4. Choose an integer e such that 1 < e < φ(n) is coprime to φ(n)
ie: e and φ(n) share no factors other than 1; gcd(e φ(n)) = 1
• e is released as the public key exponent
5. Compute d to satisfy the congruence relation
de = 1 (mod φ(n)) ie: de = 1 + kφ(n) for some integer k
• d is kept as the private key exponent
The public key is made of the modulus n and the public (or encryption) exponent e The private key is made of the modulus n and the public (or decryption) exponent d which must be kept a secret.
Alice gives her public key (n and e) to Bob and keeps her private key secret. Bob wants to send message M to Alice.
First he turns M into a number m smaller than n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to: c = me mod n. This can be done quickly using the method of exponentiation by squaring. Bob then sends c to Alice.
Alice can recover m from c by using her private key d in the following procedure: m = cd mod n. Given m, she can recover the original message M
Another public key cipher introduced recently is Elliptic Curve Cryptography (ECC). It uses the “dot” function, and it is faster to compute than the RSA. Thus is it gaining popularity.
In Table 1, from NSA, one can see that in order to achieve a security strength of AES-128, ECC only needs a 256-bit public key whereas RSA would need 3072 bits.
Another way to compare RSA and ECC performance is to look at the time it takes to break the security. Clearly, the graph shows that ECC is more efficient as it uses a short key length to achieve the same level of security as RSA.
Symmetric vs Asymmetric Key Cryptography
Asymetic key cryptography is great as Alice and Bob do not need to physically meet to exchange keys. It is also be used to verify and non-repudate the user. So why do we still use AES? The shortcoming of asymmetric key cryptography is that it is too slow to encrypt sizeable messages. Instead, Bob sends the symmetric key to Alice using the public key cryptography, then use the symmetric key to encrypt the bulky messages.
The idea is to take advantage of the:
Speed of symmetric key cryptography and Security of asymmetric key cryptography
The summary of how the asymmetric and symmetric cryptography compare is seen in Table 2.
Suppliers such as NXP, Infineon, Microchip and Renesas provide security solutions like anti-cloning and Secure Boot by employing modern cryptography. In addition to that, they make tamper resistant hardware to ensure keys/data which reside in these devices cannot be read or compromised.
This paper has outlined the basics of classical and modern cryptography. It explains why asymmetric and symmetric cryptography are both needed in modern day security. While AES provides a fast encryption algorithm, it depends on the fact that both parties are privy to the secret key. Hence the introduction of RSA or ECC which enables users to share the AES key. Finally, these encryption algorithms provide the basis of authentication and data integrity.