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.

Figure 4: Flow for password-hardened encryption.

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.

Figure 5: Computations on encrypted data.

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)).

Figure 6: Fully homomorphic encryption.

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.