Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Introduction to modern cryptography

Let's leave aside our paper and pencil algorithms and get into modern cryptography. As most of you already know, modern cryptography is divided into two big blocks, according to the type of keys used.

On one hand, we have symmetric (key) cryptography. As you can imagine, it uses a symmetric key, shared between transmitter and receiver. This means that for each pair of entities communicating in a system, a different secret key is needed.

In this group we have block ciphers like DES/3DES and AES, as well as stream ciphers (for instance, RC4). The former divide the text into several blocks of fixed length, and encrypt block by block. The latter generally start from a key and generate a sequence of bits or bytes (key stream) from it, which will be XORed with the plaintext.

Further, there are the so-called modes of operating of block ciphers, which allow us to convert a block cipher into a stream cipher. These modes exist because for a given block cipher in its elementary mode, two identical blocks would give the same ciphertext under the same key, thus revealing part of the text structure. Later in this series we'll devote a post to these modes of operation.

However, the main problem of symmetric crypto resides in the key management. As I said, for each pair of users a secret key shared between them is needed. This means that for 3 users we would need 3 keys, for 4 users 6 keys, and in general, for n users we'd need n·(n-1)/2 keys.

As can be seen, the number of keys to be managed follows a quadratic order with the number of users to be intercommunicated. Therefore, with as few as 100 users we would need as much as 4950 different keys!

But Asymmetric or Public key Cryptography comes to help and solve this problem. This kind of cryptography works by having a key pair for each user. Each user keeps its private key secret, while its public key is known to the rest of the users ( hence the name 😉 ).

When user A wants to send a message to user B, A simply has to find B's public key, . Then, with it A can encrypt a text for B by means of the encryption operation . To decrypt the message, B simply takes its private key and applies the decryption operation,  .

So far, this seems secure. Further, we just have n public keys, one per user. However, key management is still a problem: how do we make sure that a given public key pertains to a given user? In a closed environment that's easy, we just need to exchange keys in person and we're done. But... what about the Internet?

The solution is a system to determine the trust on public keys. One of the approaches is based on digital certificates, implementing what is known as a Public Key Infrastructure (PKI). Another approach is the one adoptet by PGP, based on so called trust rings. Or in other words, friends of my friends are my friends.

Finally, note that using these concepts (symmetric and asymmetric crypto), mechanisms to protect message authenticity and/or integrity can be implemented: the so called Message Authentication Codes (MAC) use symmetric crypto, while digital signatures are possible thanks to asymmetric crypto.

We'll also devote posts to all these questions in the future.