Provable security and other problems in modern cryptography
Typical Errors
A widespread mantra from the IT security field is that you should never develop your own cryptographic method. But at what point do you construct your own procedure? In fact, this mantra falls short in many places and should instead read: "Never use cryptographic procedures unless you can prove what you are doing." The following example demonstrates that this statement is by no means exaggerated and that even the simple use of two cryptographic procedures can lead to a completely insecure construction.
In this example, assume that Alice wants to store a file m with encryption in the cloud. To do this, she uses the message and a public key. The cloud operator does not want to store duplicates of the same message for efficiency reasons. However, since the file has been encrypted, the operator cannot readily determine whether the message already exists in an encrypted form in the cloud.
For this reason, the ciphertext is extended to include the hash value of the message: c = (Enc(pk,m), H(m)). A hash function is a deterministic function that usually compresses the input. The security of this function is based on collision resistance. This property means that it is (efficiently) impossible to find two different messages m1 and m2 that produce the same output (H(m1) = H(m2)).
Intuitively, you might expect that the hash value does not reveal any information about the message m thanks to the compression properties. However, there is no security property that covers this assumption. In fact, analysis of the construction shows that it is completely insecure. In particular, the output of the hash function can be used to completely override the security properties of the encryption.
This simple example illustrates that a combination of two secure cryptographic methods can lead to an insecure construction. Cryptographic methods should only be used together if you actually need the security properties of each method. It is precisely this relationship between the underlying properties and the properties you want to achieve that is demonstrated by formal proof.
Current Research Topics
There are still countless unsolved problems in the cryptography research field. Thematically, it moves between basic theoretical research and applied practical research. This section presents two areas of current research.
One is password-based cryptography. Passwords are the Achilles' heel of many modern systems because they combine everything a cryptographer usually doesn't want to have: They are short and have little entropy, which means that an attacker can break most passwords by simply trying them out. This type of attack is known as an offline brute force attack. After the invention of public-key cryptography, many speculated that passwords would die out and everyone would exclusively use a private key for authentication. That has not happened to date, and it appears that passwords will remain the most common technique for authentication on the Internet in the long term. In research, this leads to the following question: How can the security of a system be guaranteed even if it uses weak secrets like passwords?
Password hardening and password-hardened encryption (PHE) were developed in this context (Figure 4). The idea is mainly based on the following considerations. First, the user's interface must not change, so they continue to use their username and password for authentication. Second, the user's data must be resistant to offline brute force attacks – even if the database has been stolen. And third, to achieve that, you need an external crypto service that does not have direct access to the data, but only provides operations to encrypt and decrypt the data.
Password-hardened encryption achieves a level of security that was previously unthinkable. For the first time, a user's data can be stored secured against offline brute force attacks, and without the user having to use complicated public key techniques.
A second research focus is on computations on encrypted data. To better understand how computations can be performed on encrypted data, consider how conventional encryption works.
Regardless of the type of encryption method, each method essentially provides key generation, encryption, and decryption. Since key generation does not play a role in the following considerations, I will not go into the details of this operation.
In cryptography, an encryption operation is a procedure that converts a readable text – the plaintext – into a form that no longer reveals any information about the plaintext – ciphertext. Figure 5 visualizes the encryption and decryption operation. The encryption algorithm Enc receives a message m and a public key pk as input. The result of the computation is a ciphertext c. The decryption algorithm Dec is used to decrypt this again. As input, it needs the secret key sk and the ciphertext c.
In order to describe a homomorphic encryption method, you first need to understand the concept of homomorphism. It comes from mathematics and means structure-preserving mapping. Put simply, this means that you can map the execution of a computation in a structure to a computation on another structure. The structure itself is preserved.
The concept of homomorphism is now applied to encryption methods. This means performing a computation on the ciphertext without actually decrypting the ciphertext. The special thing about this operation is that the computation on the plaintext has an effect on the ciphertext, although the plaintext is not available during this computation. Depending on the type of encryption, the combination of the ciphertexts is applied to the plaintext as an addition or multiplication. The addition operation is known as additive homomorphic encryption, and the multiplication operation is called multiplicative homomorphic encryption.
The right half of Figure 5 shows this process. You can see two ciphertexts C1 and C2 on the left. They were computed in the conventional way: that is, C1 is the result of encrypting a message m1 with the public key pk, while C2 is the result of encrypting a message m2 with the public key pk. These two ciphertexts are now combined by a computation x.
By way of an example. I'll first encrypt the number 2 with the public key pk: C1 := Enc(pk,2). The resulting ciphertext is referred to as C1. In the second step, I'll follow the same steps with the number 3: C2 := Enc(pk,3) to generate the ciphertext C2. The third step now concatenates the two ciphertexts by applying the operation x: C3 := C1 x C2. If the encryption method is an additive homomorphic method, then the ciphertext C3 := C1 x C2 := Enc(pk,2) x Enc(pk,3) = Enc(pk,2+3) = Enc(pk,5) contains a value of 5. If the process is multiplicatively homomorphic, then C3 := C1 x C2 := Enc(pk,2) x Enc(pk,3) = Enc(pk,2*3) = Enc(pk,6), contains a value of 6.
In both cases, only the owner of the secret key sk has access to the result of the computation, since only they can decrypt the ciphertext C3. An example of additive homomorphic encryption is provided by the ElGamal method [2], whereas the Paillier method [5] is multiplicatively homomorphic.
In contrast to the previous methods, fully homomorphic encryption allows arbitrary calculations to be performed on the ciphertext. For a better understanding of how it works, Figure 6 shows the individual steps. First, a plaintext m is encrypted with the public key pk (a), resulting in the ciphertext C. Now the computation (b) is performed; the ciphertext C and the public key pk and the description of the program P flow into this. The computation results in a ciphertext CP and the result of the computation is Eval(pk,C,P) = CP = Enc(pk,P(m)).
Just as in the previous examples, anyone can perform the computation on the ciphertext C, since it does not require any secret information. However, only the owner of the associated secret key sk can compute the result. Fully homomorphic encryption is an incredibly powerful tool because there are no constraints on the P program. This means that arbitrary computations can be performed on the encrypted data. Performing computations on encrypted data dramatically reduces the need to trust the party storing the data. For instance, you could outsource the data to a cloud service that holds the data and performs computations without the need to decrypt. The service performing the computations would not need to see the plaintext data or even the result of the computation. The data owner remains in control over the data.
Conclusions
This article has introduced you to provable security, one of the cornerstones of modern cryptography. You also learned about some recent research topics that are exciting cryptographers today.
Cryptography has been around for thousands years, but it still manages to excite, and state-of-art encryption techniques still sound like pure magic. For example, who would have thought that computations on encrypted (genetic) data would work? But cryptography is still in its infancy, and the crypto technologies of the future will no doubt continue to surprise us.
Infos
- Katz, Jonathan and Yehuda Lindell, Introduction to Modern Cryptography: Principles and Protocols, CRC Press, 2007, https://archive.org/details/Introduction_to_Modern_Cryptography
- ElGamal encryption: https://www.geeksforgeeks.org/elgamal-encryption-algorithm/
- Encrypt-then-MAC: https://en.wikipedia.org/wiki/Authenticated_encryption#Encrypt-then-MAC_(EtM)
- CPA: https://en.wikipedia.org/wiki/Chosen-plaintext_attack
- Paillier encryption: https://en.wikipedia.org/wiki/Paillier_cryptosystem
« Previous 1 2 3 4
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you've found an article to be beneficial.
News
-
Fedora 39 Beta is Now Available for Testing
For fans and users of Fedora Linux, the first beta of release 39 is now available, which is a minor upgrade but does include GNOME 45.
-
Fedora Linux 40 to Drop X11 for KDE Plasma
When Fedora 40 arrives in 2024, there will be a few big changes coming, especially for the KDE Plasma option.
-
Real-Time Ubuntu Available in AWS Marketplace
Anyone looking for a Linux distribution for real-time processing could do a whole lot worse than Real-Time Ubuntu.
-
KSMBD Finally Reaches a Stable State
For those who've been looking forward to the first release of KSMBD, after two years it's no longer considered experimental.
-
Nitrux 3.0.0 Has Been Released
The latest version of Nitrux brings plenty of innovation and fresh apps to the table.
-
Linux From Scratch 12.0 Now Available
If you're looking to roll your own Linux distribution, the latest version of Linux From Scratch is now available with plenty of updates.
-
Linux Kernel 6.5 Has Been Released
The newest Linux kernel, version 6.5, now includes initial support for two very exciting features.
-
UbuntuDDE 23.04 Now Available
A new version of the UbuntuDDE remix has finally arrived with all the updates from the Deepin desktop and everything that comes with the Ubuntu 23.04 base.
-
Star Labs Reveals a New Surface-Like Linux Tablet
If you've ever wanted a tablet that rivals the MS Surface, you're in luck as Star Labs has created such a device.
-
SUSE Going Private (Again)
The company behind SUSE Linux Enterprise, Rancher, and NeuVector recently announced that Marcel LUX III SARL (Marcel), its majority shareholder, intends to delist it from the Frankfurt Stock Exchange by way of a merger.