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
Direct Download
Read full article as PDF:
Price $2.95
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Find SysAdmin Jobs
News

Kubuntu Focus Announces XE Gen 2 Linux Laptop
Another Kubuntubased laptop has arrived to be your next ultraportable powerhouse with a Linux heart.

MNT Seeks Financial Backing for New SevenInch Linux Laptop
MNT Pocket Reform is a tiny laptop that is modular, upgradable, recyclable, reusable, and ships with Debian Linux.

Ubuntu Flatpak Remix Adds Flatpak Support Preinstalled
If you're looking for a version of Ubuntu that includes Flatpak support out of the box, there's one clear option.

Gnome 44 Release Candidate Now Available
The Gnome 44 release candidate has officially arrived and adds a few changes into the mix.

Flathub Vying to Become the Standard Linux App Store
If the Flathub team has any say in the matter, their product will become the default tool for installing Linux apps in 2023.

Debian 12 to Ship with KDE Plasma 5.27
The Debian development team has shifted to the latest version of KDE for their testing branch.

Planet Computers Launches ARMbased Linux Desktop PCs
The firm that originally released a line of mobile keyboards has taken a different direction and has developed a new line of outofthebox mini Linux desktop computers.

Ubuntu No Longer Shipping with Flatpak
In a move that probably won’t come as a shock to many, Ubuntu and all of its official spins will no longer ship with Flatpak installed.

openSUSE Leap 15.5 Beta Now Available
The final version of the Leap 15 series of openSUSE is available for beta testing and offers only new software versions.

Linux Kernel 6.2 Released with New Hardware Support
Find out what's new in the most recent release from Linus Torvalds and the Linux kernel team.