Crypto building blocks

June 4, 2013 by

Dawid Czagan

1. Introduction

This article will explain how crypto building blocks can be used to achieve confidentiality, integrity, authentication and non-repudiation. It introduces symmetric and asymmetric ciphers, hashes, digital signatures and certificates.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

2. Symmetric cipher

To illustrate this, let's assume that Alice wants to talk to Bob. The message is confidential, so Alice uses a key to encrypt the message. The original message is now called a plaintext while the encrypted message is called a ciphertext. The ciphertext is sent to Bob, who knows the key and uses the same symmetric cipher (e.g. AES or 3DES). Thus Bob is able to decrypt the message.

The key space doubles when one bit is added to the key. Longer keys are better, but don't necessarily increase security. Because people tend to use patterns for passwords, the attacker can build a dictionary of commonly used passwords and launch a dictionary attack. This way the attacker can save time, because he doesn't have to brute force the whole key space.

Alice and Bob share the key, which is called symmetric. They are the only ones who know the key and no one else is able to read the encrypted message. This way, confidentiality is achieved.

The symmetric key can be changed every time Alice communicates with Bob. Then it is called a session key (randomly generated and valid only for one session). If an attacker grabs the session key, he can decrypt only the messages from one session. If Alice and Bob always used the same key, the attacker would be able to decrypt all messages encrypted with this key.

There are a few problems with symmetric ciphers. For one, this system is not scalable. If there are 1,000 people who want to communicate with each other, everyone needs 999 different keys to establish separate and confidential communication channels. Another problem is the lack of non-repudiation. Bob can't prove that it was Alice who sent the message. It could have been Alice or Bob, because they share the key. Also, secure key distribution is one more problem. The security of the system is broken if a man-in-the-middle can grab the key while it is being transmitted from Alice to Bob.

3. Hash and HMAC

Bob wants to be sure that the message he has received is exactly the same as the one sent by Alice. For this, Alice might send the message with its hash (also called a message digest) appended at the end. Hashing is used to achieve data integrity and there is no key involved.

The hash of the message M is denoted by H(M) in the article. The ideal hash function is irreversible (one can't get the message from the hash) and there are no two different messages M1 and M2 such that H(M1)=H(M2). MD5 and SHA-1 are exemplary hash functions. The longer the hash, the less probable the occurrence of collision. A collision takes place when the same hash is created for two different messages.

When Bob gets the message from Alice with the appended hash of the message, he calculates the hash of the message and compares it with the appended hash. If they match, Bob can assume that the message was not changed. The problem though is the man-in-the-middle attack. An attacker can grab the message, change it, and append the new hash at the end. That's why the appended hash needs to be authenticated.

Alice and Bob share a key. The HMAC is a hash of the message and the key. Alice calculates HMAC, appends it to the message and sends to Bob. Bob calculates the HMAC (hash of the message he received and the key he shares with Alice). Then he compares this HMAC with the HMAC appended to the message. When they match, Bob knows that it was Alice who sent this message. If the attacker changed the message and HMAC, it would be detected by Bob since the attacker doesn't know the key. This way, message integrity and authentication can be verified by Bob.

4. Asymmetric cipher

Two keys are used in asymmetric cipher (e.g. RSA) – a public and a private one. The public one is available for everyone, but the private one is known only by the owner. When the message is encrypted with the public key, only the corresponding private key can decrypt it. Moreover, the private key can't be learnt from the public one.

Asymmetric cipher solves the problem of secure key distribution. Alice takes Bob's public key and uses it to encrypt the session key. Only Bob can then decrypt the encrypted session key, because he is the only one who knows the corresponding private key. Asymmetric ciphers are quite slow when compared with the symmetric ones, which is why asymmetric ciphers are used only to securely distribute the key. Then, Alice and Bob can use symmetric cipher and the session key to make the communication confidential.

Asymmetric cipher also solves the scalability problem. Everyone will only need one public key and one private key to communicate with other people.

5. Digital signature

HMAC is used to provide message integrity and authentication. The problem is that HMAC doesn't provide non-repudiation, because Alice and Bob share the key.

Digital signature provides non-repudiation. Alice's private key is used to encrypt the hash of the message. This encrypted hash is called a digital signature. Alice sends the message with an appended digital signature to Bob. Bob uses Alice's public key to decrypt the digital signature. Bob then calculates the hash of the message and compares it with the decrypted digital signature of the message, which is the hash of the message. If these hashes match, Bob knows exactly what message exactly was sent and who sent it.

How can Bob know that the public key he got is really the one from Alice? There might be a man-in-the-middle introducing himself as Alice. Digital certificates are used to solve this problem.

6. Digital certificate

Bob gets a digital certificate from Alice. The certificate includes Alice's public key and name. It is digitally signed by a trusted Certificated Authority (CA) so the hash of the certificate is encrypted with their private key. Bob trusts the CA, who carefully verified Alice before issuing her a digital certificate. Thus, Bob knows that the public key belongs to Alice.

Bob's operating system has a list of trusted CAs with their public keys, so Bob can check if the digital certificate is signed by a trusted CA.

Security is again broken if an attacker steals Alice's private key. The attacker can then be able to read the messages that was only intended for Alice to read. Moreover, he can digitally sign the messages as if there were sent by her. Everyone can then verify that it was Alice who sent the message, even though it is not true. The non-repudiation is broken, because Alice is not the only one who knows her private key.

When Alice's private key is stolen, her certificate can be revoked. The Certificate Revocation List (CRL) is used for this purpose. Bob can check if Alice's certificate has been revoked when he gets her certificate.

Malware could also steal Alice's private key from her computer. That's why the private key should be stored on a smart card to minimize its risk of being stolen. The private key doesn't leave the smart card while the digital signature is being performed.

7. Putting the building blocks together

Alice wants to send a message to Bob. She gets Bob's digital certificate and checks if it's signed by a trusted CA and is still valid. If this is a case, she takes Bob's public key and uses it to encrypt the session key. The encrypted session key is denoted as PART1. Then she encrypts the message with the session key. The message encrypted with the session key is denoted as PART2. After that, she uses her private key to encrypt the hash of MESSAGE, where MESSAGE is PART1 plus PART2. Thus the digital signature of the MESSAGE is created (denoted by SIGNATURE). The MESSAGE and the SIGNATURE are sent to Bob.

Bob gets Alice's digital certificate and checks if it's signed by a trusted CA and is still valid. If this is the case, Bob uses Alice's public key to verify the SIGNATURE. If it is fine, he knows that the MESSAGE was sent by Alice. Then Bob uses his private key to decrypt PART1. This way he extracts the session key. Afterwards, Bob uses this session key to decrypt PART2. Finally, Bob can read the message securely.

8. Conclusions

- Symmetric cipher is used to provide confidentiality of the message.

- Asymmetric cipher is used to securely distribute the session key.

- Hash is used to provide the integrity of the message.

- HMAC is used to provide message integrity and authentication.

- Digital signature is used to provide message integrity, authentication and non-repudiation.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

- Digital certificate is used to bind the user with his public key (based on the trusted CAs).