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

Monthly Sponsorship Includes Early Access to elementary OS 8
If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.

DebConf24 to be Held in South Korea
Busan will be the location of the latest DebConf running July 28 through August 4

Fedora Unleashes Atomic Desktops
Fedora has combined its solid distribution with rpmostree system to make it possible to deliver a new family of Fedora spins, called Fedora Atomic Desktops.

Bootloader Vulnerability Affects Nearly All Linux Distributions
The developers of shim have released a version to fix numerous security flaws, including one that could enable remote control execution of malicious code under certain circumstances.

Microsoft Says VS Code Will Work with Ubuntu 18.04
If you're a user of Microsoft's VS Code and you're still using Ubuntu 18.04, you can breathe a sigh of release that the IDE will continue working… for a while.

Purism Crowdfunding Launched
The first public offering on StartEngine crossed the US$ 100,000 mark within 48 hours of launch.

System76 Refreshes Serval WS Laptop
With more and more users turning to AI workloads, System76 decided to raise the bar with its Serval WS laptop by upping the specs on a few key components.

Docker Build Cloud Helps Speed Up Build Time
Docker has announced a new product that directly addresses the time spent waiting on builds to complete.

Firefox 122 Release Includes Official DEB for Ubuntu Distros
Finally, Mozilla has returned to Ubuntu's/Debian's roots to offer an official DEB package for those who prefer to not use the Snap package.

MX Linux 23.2 "Libretto" Released
MX23.2 is a second refresh of the MX23 release and mostly consists of bug fixes and updates, but users will find a couple of new tools in the mix.