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 passwordbased 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 publickey 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 passwordhardened 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.
Passwordhardened 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 structurepreserving 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 stateofart 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/elgamalencryptionalgorithm/
 EncryptthenMAC: https://en.wikipedia.org/wiki/Authenticated_encryption#EncryptthenMAC_(EtM)
 CPA: https://en.wikipedia.org/wiki/Chosenplaintext_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

Kernel 6.10 Available for General Usage
Linus Torvalds has released the 6.10 kernel and it includes significant performance increases for Intel Core hybrid systems and more.

TUXEDO Computers Releases InfinityBook Pro 14 Gen9 Laptop
Sporting either AMD or Intel CPUs, the TUXEDO InfinityBook Pro 14 is an extremely compact, lightweight, sturdy powerhouse.

Google Extends Support for Linux Kernels Used for Android
Because the LTS Linux kernel releases are so important to Android, Google has decided to extend the support period beyond that offered by the kernel development team.

Linux Mint 22 Stable Delayed
If you're anxious about getting your hands on the stable release of Linux Mint 22, it looks as if you're going to have to wait a bit longer.

Nitrux 3.5.1 Available for Install
The latest version of the immutable, systemdfree distribution includes an updated kernel and NVIDIA driver.

Debian 12.6 Released with Plenty of Bug Fixes and Updates
The sixth update to Debian "Bookworm" is all about security mitigations and making adjustments for some "serious problems."

Canonical Offers 12Year LTS for Open Source Docker Images
Canonical is expanding its LTS offering to reach beyond the DEB packages with a new distroless Docker image.

Plasma Desktop 6.1 Released with Several Enhancements
If you're a fan of Plasma Desktop, you should be excited about this new point release.

SUSE Offers CentOS 7 Support with Liberty Linux Lite
SUSE's Liberty Linux support offering now includes CentOS 7, which means businesses won't be forced to migrate those servers for some time.

Ubuntu's App Center Finally Supports Local Installs Again
If you regularly download .deb files and would prefer a GUI method of installing, Ubuntu has your back.