Step 6: Security Analysis of the Implementation

The sixth and last step calls for security evaluation of the concrete instantiation. This is required because transitioning from an abstract description to a concrete implementation has many pitfalls. For example, the basic cryptographic element used with Internet Protocol Security (IPsec), which is known as "encrypt-then-MAC" is an authenticated encryption scheme with weak security [3]. It is considered secure against a chosen-plaintext attack (CPA) [4], and it is also secure against spoofing given that the encryption scheme is CPA-secure and the message authentication code (MAC) cannot be spoofed. However, the concrete instantiation used in IPsec, for example, was found to be insecure. The security of the implementation can also be proven by penetration tests, which reveal weaknesses in the implementation of the security concept that could allow an attacker to penetrate the system.

Example: Secure Email

To illustrate the principle of provably secure software development, consider the example of an encrypted email message (Figure 2). In this case, Alice wants to send an encrypted message to Bob. Bob needs to be able to decrypt the email and verify the signature.

Figure 2: Secure email communication from Alice to Bob.

Alice has Bob's public key pkB. For simplicity's sake, I will assume that Alice has verified the key and ensured that it is Bob's. Furthermore, Alice has her own private key skA. Similarly, Bob knows Alice's public key pkA and has his own private key skA. In this case, I will also assume that Bob has verified the authenticity of the key pkA.

The first step is to specify the functionality. In this case we are dealing with authenticated email; consequently, I have two tasks: First, I need to compute an encrypted and authenticated email. This interface is designated Enc+Auth. Second – assuming that the authentication is valid – the encrypted email has to be decrypted. Keeping to the same pattern, I will refer to this interface as Vrfy+Dec.

The second step is to determine the (fairly simple) security properties. The attacker knows Alice and Bob's public keys and all the methods used. Nevertheless, the attacker must not be able to obtain information from the email. Furthermore, the attacker must not be able to send emails on behalf of Alice (i.e., messages verified with the pkA public key) to Bob.

Although these features seem to make sense at an intuitive level, they still leave too much scope for interpretation. Can the attacker interact with Bob? Is there a learning phase where the attacker is allowed to use Alice as an interface to forward the encrypted and authenticated emails from Alice to Bob? Is the attacker allowed to impersonate Bob and read encrypted emails for a period of time? How are the messages to Bob generated? In a formal description of the security properties, it is important to eliminate these ambiguities so that a precise and unambiguous description results.

After formalizing the interfaces and the security properties, the third step is to instantiate the individual components using cryptographic methods. The two interfaces Enc+Auth and Vrfy+Dec need to be constructed with cryptographic procedures such that they provide precisely the desired functions. In the case of secure email, this step is relatively simple (Figure 3).

Figure 3: Schema for secure email communication.

To implement the Enc+Auth interface, you first need to encrypt the message with a public key method and then sign the ciphertext with a digital signature method. I'll use c to denote the ciphertext and the lowercase Greek letter sigma (s) to denote the signature. In line with this, you would implement the Vrfy+Dec interface with the following operations. First, the signature procedure's verification algorithm is used to check the validity of the signature on the ciphertext c. If this signature is valid, the public key procedure's decryption algorithm decrypts the ciphertext c and outputs the resulting message m.

In the security validation, I can now assume in the fourth step that both the encryption method and the signature method are secure according to formal definitions. You then formally verify that an attack that breaks the security of Enc+Auth as well as Vrfy+Dec (according to the formal model) can be used to break the security of both the public key and the signature procedure. However, since both procedures were assumed to be secure in the first step, a contradiction arises, from which it follows that such an attack cannot exist.

In the last two steps, you now use concrete procedures, for example, RSA-based encryption, implement them, and prove the security of the implementation through penetration tests.

Strengths and Limitations

Since the discovery of this method, provably secure cryptographic methods such as El Gamal encryption [4] have been virtually unbreakable. Provable security reduces the proof for an encryption method to a simple computational problem, such as the very well-known factorization problem.

In this problem, the attacker is given a number N=p*q calculated as the product of two primes of equal length p and q. The attacker's task is now to compute the two prime factors p and q. To date, no efficient solution algorithm has been discovered for this well-known computational problem. If the security of an encryption scheme is now based on the factorization problem, then the formal proof shows the following. If there is an efficient attacker who breaks the encryption scheme, then there is also an efficient attacker who solves the factorization problem. In other words, the problem of breaking the encryption is as difficult to solve as the factorization problem.

At first glance, the term "provably secure" suggests that there are provably no longer any attacks. However, this is not true. Attacks on systems that are supposedly probably secure repeatedly occur. Where does this contradiction come from, and how can it be resolved? First of all, it is important to note that the security of the proof always refers to a formal model. However, if the model does not truly reflect practice, then it cannot rule out potential attacks because these attacks simply do not occur in the model. Consequently, accurately modeling reality is one of the biggest challenges in this area, and even the smallest errors in modeling can lead to an insecure solution.

The security of the Secure Sockets Layer (SSL) protocol is a great example of incomplete modeling. In practice it was possible for a message not to be decrypted; instead, a Padding Error message appeared. At first glance, this appears harmless, as it does not seem to reveal any direct information about the plaintext. This is why it was not included in the formal model. At second glance, however, researchers were able to show that it was possible to exploit this error message to decrypt the full message – and to do so without breaking the actual security of the encryption scheme.