Provable security and other problems in modern cryptography
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 "encryptthenMAC" is an authenticated encryption scheme with weak security [3]. It is considered secure against a chosenplaintext attack (CPA) [4], and it is also secure against spoofing given that the encryption scheme is CPAsecure 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.
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).
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, RSAbased 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 wellknown 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 wellknown 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.
« Previous 1 2 3 4 Next »
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

Linux Mint 21.1 Enters Beta Status
With a new version of the Cinnamon Desktop, Linux Mint 21.1 has plenty to offer.

4MLinux 41.0 Now Stable and Ready for Use
The developers behind 4MLinux have changed the status of 41.0 to STABLE, which means it's ready for prime time.

Xfce 4.18 Coming Soon and Offers Subtle Improvements
The Xfce team has announced the release date of the next iteration of the desktop, which includes a good number of features to polish the fanfavorite Linux UI.

Orange Pi Board Has ArchBased Linux Distribution in the Works
The developers of the Orange Pi board are planning to release an Archbased Linux distribution available for its hardware as an alternative to Orange Pi OS.

Alpine Linux 3.17 Now Available to the General Public
The developers of Alpine Linux have officially announced the release of the latest version of the securityfocused Linux distribution.

The New StarFighter Linux Laptop Now Available for Preorder
A new, completely customizable Linux laptop is now available to preorder from Star Labs.

Critical Escalation Vulnerability Found in the Linux Kernel
A new local privilege escalation vulnerability has been discovered in the Linux kernel and users are encouraged to upgrade/patch immediately.

AlmaLinux 8.7 Now Available
The developers of AlmaLinux have released the latest version of the OS, named Stone Smilodon, to the general public.

New ArchBased Linux Distribution Aims to be BeginnerFriendly
CachyOS has been created to serve as a Linux distribution for everyone, even while being based on the more complex Arch Linux.

elementary OS 7 Getting Closer to Release
The team behind elementary OS has announced they are now focused on putting the finishing touches on the next major release of the Linux distribution.