Evaluating Security

Security assessment of a given cryptosystem

One of the most difficult aspects of cryptography is making an accurate assessment of the security of a given cryptosystem. We separate this discussion into assessing the security of cryptographic primitives, protocols, and cryptosystems.

Assessing the security of a cryptographic algorithm

Historically, the security of cryptographic algorithms (and protocols) relied on a rather informal approach that considered known attacks on the algorithm, such as an exhaustive key search, and then designed the algorithm to make these attacks ineffective. Often the arguments put forward to justify the resulting ‘security’ were not particularly rigorous, and in many cases, they were experimental. This process resulted from the fact that cryptographic algorithm design is as much about engineering as mathematics.

The problem with such an informal approach is that it does not provide any real notion of ‘proof’ that a cryptographic algorithm is secure. With this in mind, cryptographic researchers have gradually been developing and adopting methodologies that attempt to provide stronger arguments for the security of cryptographic algorithms. This concept of provable security attempts to assess the security of a cryptographic algorithm by starting from some assumptions about the attack environment (captured by a security model) and then showing that the security of the cryptographic algorithm can be formally linked (reduced) to the difficulty of a computational problem, which is better understood.

There are two potential problems with this type of approach:

• The starting assumptions may not be the right ones: For example, there may be attacks that have not been considered in the security model.

• The computational problem might not be as difficult as thought: Provable security arguments are essentially translations from one relatively poorly understood concept (the cryptographic algorithm) into a better-understood concept (the computational problem). However, this does not guarantee any security in the event that the computational problem is not as hard as originally believed.

This is why provable security is not really a ‘proof’ of cryptographic algorithm security. Nonetheless, it is a substantially better approach than the informal one of the past. A security proof within a sensible security model should thus be regarded as important evidence in favor of the overall security of a cryptographic algorithm.

Arguably the best assessment benchmark for a cryptographic algorithm remains exposure and breadth of adoption. As we observed previously, the most highly regarded cryptographic algorithms tend to be those that have been widely scrutinized and implemented. To this end, several standardization bodies, including ISO/IEC, NIST, and IEEE, have standards that identify cryptographic algorithms that have been widely studied by experts and recommended for adoption. Some, but not all, of these cryptographic algorithms have proofs of security within specific security models.

Assessing the security of a cryptographic protocol

As we will discover, cryptographic protocols are very complex objects to analyze. Their security is also assessed using both informal analysis and more rigorous formal methodologies. In addition to provable security techniques for cryptographic protocols, there have been attempts to define logical methods to make a case for the security of a cryptographic protocol. These establish basic logical statements relating to security and attempt to build a cryptographic protocol for which certain security ‘truths’ hold.

One of the main problems with formal approaches to cryptographic protocol analysis is that the cryptographic protocols used in real applications are often quite complex and hard to capture in a formal model. However, even being able to formally analyze part of a cryptographic protocol is arguably a significant improvement on informal analysis techniques.

As well as general standards for specific types of a cryptographic protocol, there are many cryptographic applications whose underlying cryptographic protocols are industry standards that have been approved by committees.

Assessing the security of a cryptosystem

The hardest of all to assess is the security of an entire cryptosystem. Since this involves not just the cryptographic algorithms and protocols but also the wider infrastructure, we have to be realistic about the extent to which this can be rigorously done. There are standards for many cryptosystem components, such as key management, which can be used to benchmark such an assessment.

There are formal evaluation criteria for security products, and there are organizations that are licensed to conduct evaluations against these benchmarks. Researchers are also looking into formal methods for evaluating the security of particular components of the overall infrastructure, such as conducting a formal evaluation of the implementation of a particular cryptographic algorithm or protocol.

We cannot capture the assessment of the security of a cryptosystem in just a few sentences. But by the end of this course, the breadth of what it might mean to assess the security of a cryptosystem should be clear.

Adequate security

One of the points we will keep returning to when considering the security of real cryptosystems is that in many application environments, it’s acceptable to adopt levels of security that are short of ‘ideal.’ This is because the potential benefits of adequate security, for example, in terms of efficiency, may outweigh the benefits of stronger security.

Clearly, the decision to make such a trade-off must be made from an informed viewpoint, which considers the realistic threat environment within which the cryptosystem will be used. As part of this analysis, it’s worth considering exactly what process a potential attacker might have to go through in order to benefit from an attack on the cryptosystem.

• Motivation: The attacker must want to attack the cryptosystem in the first place. There are many applications where, realistically, there are no motivated attackers. For example, the vast majority of email users do not encrypt their emails. Many of these users would probably use a secure email package if they believed in the existence of an attacker who routinely wanted to read their email.

• Knowledge: An attacker with the motivation must also have the knowledge to conduct an attack. Even an attack that can largely be ‘automated,’ for example, by downloading a software attack tool, often still requires an amount of expertise (albeit fairly small) to conduct. There may be many potential attackers with enough knowledge, but this is only a threat if one of them is likely to be motivated to conduct it.

• Action: An attacker must actually proceed with an attack. Even with the motivation and the knowledge, there may be barriers that prevent an attacker from proceeding. These could be logistical. For example, an attacker requires the right opportunity, perhaps access to a specific computer terminal, which might never arise. Or these could be conceptual. For example, an attacker may desire to access a colleague’s files and may have the knowledge of how to do so but knows that this action would be considered a breach of the organization’s computer use policy, which could result in the attacker losing their job.

• Success: An attacker has to succeed with their attack. For many attacks on a cryptosystem, success is far from guaranteed. For example, an attacker with access to a user’s ATM card can usually only make three attempts to guess the PIN before the card account is suspended.

• Benefit: An attacker has to benefit from the attack. Even if the attacker successfully attacks the cryptosystem, the results may not be of great use to the attacker. For example, a plaintext with a short cover time could be encrypted using a fairly weak encryption algorithm. The attacker may be able to conduct an exhaustive key search, but if this takes longer than the cover time, then the plaintext should no longer be of value by the time the attacker finds it. As another example, an attacker might be successful in finding a collision for a hash function, but they will only benefit if this collision is meaningful.

In some application environments, the very idea that there might be a motivated attacker is enough to require that the application be ‘locked down’ using a high-grade cryptosystem. In others, it may suffice to rely on the benefits of a fairly easily conducted attack being quite small. What is vitally important is that this attack process is thought through when making a decision about what level of cryptosystem security is deemed to be adequate.

Towards a notion of practical security

Hopefully, it should be evident that the term practical security describes an abstract idea rather than a concept for which we’ll ever be able to propose a clear definition. There are several fundamental problems with trying to define practical security listed below:

Coverage

It involves too many separate factors to capture in one clear notion. For example, in order to evaluate practical security, we need to conduct activities that include the following:

• Evaluating the existence and abilities of potential attackers.

• Assessing the likely computing power of an attacker.

• Determining the complexity of known attacks.

• Considering the security of cryptographic implementations.

• Evaluating the effectiveness of key management processes.

• Forming a notion of what levels of risk to accept.

Subjectivity

It is a subjective issue. What is regarded as practically secure from one perspective may not be from another. For example:

• Academics publishing research on cryptosystems set such demanding notions of security that it’s not uncommon for academic breaks of cryptosystems to have relatively little impact on security in real environments.

• Different application sectors hold different views of risk. For example, in 1988, the National Security Agency in the United States removed its endorsement of DES, but in the same year, the National Bureau of Standards reaffirmed the use of DES in the financial sector. This suggests that the two organizations may have had different notions of practical security.

Evolution

Hard as it is to formulate practical security at any given moment in time, an additional complication is that most of the inputs, such as attack capability and risk models, vary over time. That’s why practical security needs to be continuously reassessed.

In order to assess practical security, it’s necessary to fully understand the entire security and business requirements of a particular environment. Indeed, the skills this requires have a much wider application than just cryptosystems and require a broad information security education.

As a last observation, even after having formulated a notion of practical security, it may not be possible to provide the determined degree of practical security in a real environment. A more realistic security target might simply be ‘inadequate security, but the best we can afford.’ However, the formulation of a notion of practical security at least allows such a decision to be placed in the appropriate context.