In this Advent Calendar post, Inpsyder Dario describes cryptography and encryption methods. First, he explains what is cryptography and what is not cryptography. Then he focuses on symmetric and asymmetric keys. To explain how they work, he gives examples and lists their benefits and disadvantages.
When the time comes to rest, we must be able to give up all worries. We make sure that the door is well closed, so we feel protected. And then we have the feeling our loved ones and our things are protected, too. In the physical world a solid door, a good burglar alarm make us feel protected. In the physical world.
And in the digital one? Did we close the door well? Are our data and communications secure?
Now, maybe, we cannot sleep anymore.
And, coming along with that, do we have adequate security mechanisms in the digital world?
The answer is yes. The word is Cryptography. And it is the science that allows us to secure our data.
What is not Cryptography
How to secure our information? The first approach, used in the past, was based on hiding the object we want to keep safe. This approach is based exclusively on secrecy.
This method has several drawbacks. It is as if, for example, to live safe from thieves, we decided to build our home away in some secret location. Rather uncomfortable I would say. And then when someone wants to visit us we have to share this secret. And what about, if by sharing this secret, a thief could find out where our house is? We would have to move to another secret location.
In the same way, building an algorithm to hide our information, whose strength lies exclusively in the secrecy of its implementation, has a short life and can hardly guarantee high levels of security. A short life because when you share it with someone else you risk its secrecy is broken. Moreover, it is not really safe because it was probably built by a small bunch of people. So it was not analyzed and tested widely.
What is Cryptography
Let’s consider a completely different solution. We build an algorithm freely accessible to everyone. However, with that algorithm, you can hide your data and make them accessible only to authorized users.
A process that can be accessed, analyzed and tested by everyone, because it is not kept secret. A process that does not base its strength exclusively on secrecy. Actually it requires just a small component to be kept secret.
This component should be created quickly and easily. Knowledge of this component will make it possible to access the protected information.
It sounds like a complicated thing. Do we really need it?
The problem lies in the fact that communication channels are not secure. Information ride on routes that we cannot protect. Anyone listening on the channel can access such data, read it, edit it, and more. there are many illicit practices.
Trying to make the channel safe is burdensome and difficult. The solution is to protect the information, turn it into something that is not understandable for an eavesdropper. This task is performed by cryptographic techniques. These are divided into two main families: Symmetric Algorithms and Asymmetric (Public Key) Algorithms.
In the previous paragraph, we referred to a component whose secrecy allows us to protect our information. This component is called Key. The key k is a small piece of information that, together with the symmetric algorithm S, allows us to transform plaintext p into an encrypted text c that cannot be read.
Or rather: it has been transformed into a type of random information that does not have anymore the form and the sense of the original one and that, in most cases, does not make any sense for those who access it.
We have a situation of the following type:
Sk(p) = c
That is, by applying the algorithm S, using the key k, on my package of information p, it gives me a new information c.
Therefore, if I want to communicate this information with a legitimate recipient on the network, I can send c. And the recipient will have to apply the same algorithm S again with the key k on the encrypted information c, thus obtaining p:
Sk(c) = p
Our information, while traveling on the net, is in encrypted form, therefore protected.
What is the security of this process based on? On two factors:
- The reliability of the S algorithm
- The secrecy of the key k that must be known only to the sender and the recipient
The reliability of the algorithm is proven. Mathematical experts and cryptanalysts have contributed to the implementation. The secrecy of k is entrusted to the sender and the recipient. An eavesdropper listening on the channel can only see c, maybe has also S, but without the key k, he cannot get the plaintext p.
Example Symmetric Algorithms
Like in the following picture, where Bob and Alice can communicate safely sharing the same key.What if the intruder could steal the key? Would the algorithm be compromised? Absolutely not: only the key and the data encrypted with that key are compromised. But if we create a new key, we can encrypt the same information with the same algorithm S again. And the eavesdropper will not have access to the plaintext again.
Symmetric Algorithms: Pros and Cons
The main advantage of symmetric algorithms is speed: the encryption and decryption process is fast enough.
The main disadvantage is due to the fact that the sender and the recipient must exchange the key. The passage is delicate. If the key is intercepted, an eavesdropper could be able to access the information and read the content.
But he could also be able to do the worst: modifying the content, encrypting it again and sending it to the recipient who doesn’t realize that the content is actually altered.
The key: additional considerations
There is another weak point concerning cryptographic algorithms, and it is due to the possibility of using a weak key. A key is a random string used to encrypt information.
Is it possible to calculate its value starting from the encrypted content? That is: knowing algorithm S and encrypted message c, is it possible to identify a “hacking” function H such that H(S, c) = k?
It depends on the key. The robustness of the system is determined by the length of the key and by its actual randomization. A sufficiently long and genuinely random key makes it impossible to derive its value from the algorithm and the encrypted text.
Often, however, the keys are generated by pseudo-random algorithms. This means that there is a certain degree of repeatability in the creation of these keys. Identifying such repetition patterns helps to force the encryption mechanism. Furthermore, a key that is not sufficiently long makes it possible, by means of an adequate calculation power, to force the system and calculate the key itself.
One Time Pad
Now consider a key whose length is at least equal to the content to be encrypted. Suppose that the key was generated in a genuinely random way and that once the encrypted message is created, it is hidden or destroyed, and therefore never used again.
In this case, regaining the plaintext is impossible. This hypothesis just illustrated is known as One Time Pad.
In such a case no technology will be able to restore the original message, neither today nor in the future, even if aliens from outer space, with some kind of special technology powers would try.
It is important to understand not only how the secrecy of a key must be kept to prevent our data from being accessed illegitimately. But also to understand how dangerous the loss of the key is. Without it the legitimate owner will no longer be able to restore the original data, making the encrypted content unusable for him and for anyone else.
Asymmetric (Public Key) Algorithms
In the previous section, regarding the symmetric encryption, we have seen how the weakness of the system is due to the use of a key that must be shared between the parties. During the sharing process, the key could be intercepted by an eavesdropper, making encryption useless.
This problem can be overcome by using Asymmetric Algorithms. In this case, we have two different keys: one to encrypt, which is called Public Key and one to decrypt which is called Private Key.
Given the asymmetric algorithm A, a pair of keys (k-public and k-private) and a plaintext p, we have:
Ak-public(p) = c
Ak-private(c) = p
So, through the public key, we can encrypt the message. But to get the plaintext back, we will have to use the corresponding private key again.
We have a significant advantage now: if we assign a pair of keys to each user, then the public key can be shared with anyone without any problem. That’s because it is used only to encrypt. Instead, the private key, which is used to decrypt messages that have been encrypted with the corresponding public key, is not shared, making it possible to decrypt only the legitimate owner.
Example Asymmetric Algorithm
Bob and Alice want to communicate. Each has a generated pair of keys, and each shares his/her public key with the other.
In the first sequence:
- Bob uses Alice’s public key, crypts a message, and sends it.
- The package travels encrypted on the net, the eavesdropper can see it, but can neither read nor modify it, even if he has the public keys of both, Bob and Alice.
- The encrypted package reaches Alice. Now Alice can use her private key to decrypt the message correctly.
At this point, Alice wants to send an answer. The second sequence describes the steps:
- Alice uses Bob’s public key, crypts the message, and sends it.
- The package travels encrypted on the net, the interceptor can see it, but can neither read nor modify it, even if he has the public keys of both, Bob and Alice.
- The encrypted package reaches Bob, now Bob can use his private key to properly decrypt the message.
Asymmetric Algorithms: Pros and Cons
The main advantage of asymmetric cryptography is the possibility to avoid sharing the key used to decrypt. In the symmetrical case, this had to be exchanged between the parts; now, the private key is not shared. So it remains secret, preventing an eavesdropper from trying to get hold of it and then decrypt messages.
The disadvantage is due to increased processing complexity. Public key algorithms are slower than symmetric ones.
The keys: additional considerations
The process of generating pairs of keys, as in the symmetrical case, requires that you select the length of the keys properly.
If we have a message encrypted with short keys, then it could be possible to calculate the private key through the public key.
To avoid this situation, we need to generate appropriate long keys: in this way, trying to calculate the private key would require much more computational power, and/or excessively long processing times. Also in this case, the length of the key is fundamental.
Chosen plaintext attack
One type of attack that can be implemented in the case of asymmetric encryption is the chosen plaintext attack. If the eavesdropper knows that the domain of the possible messages being exchanged is limited, he may try to implement this technique.
So, if the plaintext space is P = [p1, p2, …, pn], it is possible to use the sender’s public key and calculate the corresponding encrypted messages space C = [c1, c2, …, cn].
Now the eavesdropper can listen on the channel and every time it succeeds in intercepting an encrypted cx message, it can compare it with the previously calculated C space, find the corresponding value, and then obtain the plaintext px.
Please note: This way the private key continues to be secret. This type of attack is applicable to an appropriately limited space of messages.
For example, if the communication concerned numerical values of money, ranging from 0 to a million dollars, a similar procedure would lead us to unveil the transmitted values.
We conclude by mentioning a technique that combines the two previous ones, trying to capture its benefits.
As the asymmetric cryptography is slower than symmetric, a widely used approach is to use it only during the initialization phase of a communication protocol to perform the secure exchange of a symmetric key.
In this way the main disadvantage of the symmetric algorithm is overcome: the key is shared between the sender and the receiver in a secure way. This key is called “session key”, as a new one is generated for each communication session, increasing the level of security of the protocol.
The transmission then proceeds using a symmetric algorithm: in this way we overcome the disadvantage linked to the slowness of asymmetric algorithms.
Encryption techniques are sophisticated and complex methods that allow us to communicate securely and protect our data from unauthorized access.
Both the main techniques Symmetric or Asymmetric cryptography still require accurate key management. Excessive sharing or loss of such information nullify the effectiveness of these techniques or even make them harmful to our data.
A conscious use, on the contrary, provides us with an impenetrable defense and, finally, can allow us to sleep peacefully.
* Many thanks to Markus Spiske for the photo we are using in this blogpost header.