Applications of Cryptography

Vet Proprietary Cryptography & Design Testable Cryptographic Systems

When it comes to the design and implementation of cryptographic systems, the main school of thought is that if the system is going to be designed for use commercially, then it cannot be a proprietary system, as the ability to test it and probe for weaknesses would be a problem. There are many issues associated with the ability to successfully vet proprietary cryptographic systems and the requirements inherent in designing testable cryptographic systems. The main issue is that the algorithm(s) used must be made available publically so that they can be tested by cryptanalysis, to establish a benchmark for the relative security of the system. There is no specific series of tests that can be performed against an algorithm to accurately evaluate its security per se; instead, what has to be done is that the algorithm needs to be vetted publically for an extended period of time through the rigorous application of cryptanalysis by experts in order to potentially discover any flaws or vulnerabilities inherent in the cryptography. If an algorithm is kept secret, then there is no vetting of it by experts, and as a result, its true strength, or potential weakness, is unknown by its users, which presents many issues for the security architect.

A practical example of this thought process can be seen by looking at some of the history surrounding DES, the unusual circumstances of its creation and the uniqueness of one architectural element of its implementation. DES was created as the result of a partnership between the NSA and IBM in the 1970’s. Due to the involvement of the NSA in the creation of DES, there have always been rumors of some sort of backdoor, or hidden element(s) within DES that could be exploited by the NSA if it needed to break the confidentiality of the data encrypted with DES. There has never been any proof of this found, despite glaring scrutiny of the algorithm for years, with one exception. The interesting thing that was found regarding DES was the unique way that the algorithm implemented S-Boxes, which are used to break up the plaintext as input in order to encrypt it as it is run through the algorithm. When the new attack methods discovered through differential cryptanalysis were applied to DES over 20 years after it was first released, the version built by NSA and IBM was found to be immune to these attack methods due to the unique bit shift that the S-Boxes utilized. The fact that DES was able to withstand an attack that had not even been invented until more than 20 years after its release has served to perpetuate the myths and legends surrounding the NSA’s involvement with DES, but it also serves to illustrate another important lesson, which is that no amount of vetting and scrutiny of an algorithm can discover all potential vulnerabilities, nor can it expose all potential defense mechanisms either. The need to allow algorithms to be vetted by communities of experts is a critical success factor in the construction of testable cryptographic systems.

There have been many more recent examples of the use of proprietary, or hidden, architectural elements to carry out attacks against infrastructure all over the world. The creation, deployment, and use of malware such as Flame, Stuxnet, and Duqu among others should focus the attention of security architects on the potential impact of the Advanced Persistent Threat (APT) category of attack vectors and their potential impact⁴⁷. The issue, which is at the heart of these specific APT attacks, is the proprietary nature of their architecture and design, and their ability to operate undetected for years in some cases. This is just an extension of the same issues faced by the security architect with regards to the use of proprietary cryptographic systems and algorithms, and the inability to properly vet and understand the risks associated with operating them.

Computational Overhead & Useful Life

The computational overhead of encryption systems and algorithms is an issue that is not well understood by many security architects. We have always been told that encryption imposes computational overhead on a system, and that this overhead, or “crypto-tax “, is just the price of using the encryption in the first place. The challenge that most security architects, and indeed most IT professionals at large, face with regards to an issue such as computational overhead is that it is not something that is explained by those who understand it in such a way that it can be addressed easily. In the area of cryptography for instance, the discussions with regards to computational overhead are highly technical affairs that involve complex mathematics and cutting edge research by leading experts in the fields of mathematics and systems engineering and design ⁴⁸. A good example of one of the more approachable research papers on this subject is “A generic characterization of the overheads imposed by IPsec and associated cryptographic algorithms“⁴⁹. This paper presents an assessment of the communication overheads of IPsec and evaluates the feasibility of deploying it on handheld devices for the UMTS architecture. A wide range of different cryptographic algorithms are used in conjunction with IPsec, such as Data Encryption Standard (DES), Advanced Encryption Standard (AES), Message Digest (MD5) and Secure Hash Algorithm 1 (SHA-1). The paper considers the processing and packetization overheads introduced by these algorithms and quantifies their impact in terms of communication quality (added delay for the end-user) and resource consumption (additional bandwidth on the radio interface).

The security architect needs to be aware of these solutions and the research that supports them in order to be able to make informed decisions with regards to implementation of the best possible elements within the security architecture to align the needs of the business with the architecture. It is hard however for the security architect to stay informed about this kind of research and to consume and utilize it in an effective manner, as it is often presented in academic journals, and does not always make its way out to the security community in ways that allow for it to be readily available to practitioners.

The security architect also needs to stay informed regarding useful life concepts in their security architectures. The algorithms that the security architect chooses to deploy all have a useful life, and just like any other metric that indicates something of importance with regards to the health of a system under management, monitoring is the key to successful usage and consumption. Publically available algorithms are all subject to constant scrutiny and cryptanalysis in order to ensure that weaknesses and vulnerabilities are discovered before they can lead to compromise and data loss if at all possible. One of the key outcomes of this exhaustive vetting process is an eventual end of life milestone for the algorithm, if it is found to be vulnerable for any number of reasons.

For instance, the announcement by NIST with regards to the approval of the withdrawal of DES in 2005, and the subsequent announcement just over one year later by the MIT Kerberos Team to end of life Kerberos Version 4 as a result of the issues associated with DES that NIST reacted to, as well as serious protocol flaws with the implementation of Kerberos v4, are both examples of algorithms and protocols that reached the end of their useful life. The security architect that had deployed either DES, or DES in support of a Kerberos v4 implementation would need to change the effected elements of the systems in question to address the loss of DES and Kerberos.

Security architects need to ensure that they stay informed with regards to useful life concerns in all areas of their system architectures in order to ensure that they are not operating systems past their useful life, and in so doing, putting the users of those systems, and the data in those systems at unnecessary risk.

Purpose of the Keys and Key Types

Either as a stand-alone service or as a supporting part of another system, cryptography supports one or several security services or properties: confidentiality, authentication, integrity, non-repudiation, and authorization. The important characteristics of the cryptographic keys, such as key size and life span, are defined by the security services and type of cryptography these keys should support. One of the cryptographic principles is a preferred use of each key type for one designated purpose, although issuing and using a multipurpose key in real life is common.

Confidentiality

Confidentiality is protection of information against unauthorized disclosure, and it is achieved by data encryption. Data to be protected may be either a human-readable text, or any type of binary, including other crypto keys. Both symmetric and asymmetric cryptography can be used. An unauthorized party should not be able to deduce or obtain the key for decryption. Keys for data at rest encryption may have a long crypto period; thus, they need to have a sufficient length and to be supported by a sophisticated and robust key management system (KMS). On the other hand, the keys for data in transit encryption may have a short life span, sometimes limited to one session. Their key length may be shorter and, thus, the KMS for this purpose may need to simply include a key generating and distributing mechanism.

The following key types support confidentiality:

   Symmetric data encryption key

   Symmetric key wrapping key; aka key encrypting key

   Public and private key transport keys

   Symmetric key agreement key

   Public and private static key agreement keys

   Public and private ephemeral key agreement keys

Authentication

Broadly, authentication is a way to verify the origin of information. If the information is just data or an executable, authentication would verify its integrity as well as the identity of the person or system that created the information. If authentication is part of an access control system and the information consists of user or system identity, authentication will verify that identity in order to allow authorization services to make access control decisions. Both symmetric and asymmetric cryptography techniques may be used, such as digital signature and MAC. The main idea is that possession of the key proves the authenticity of an information originator. Both data at rest and in transit may employ key-based authentication.

The following key types support authentication:

   Private signature key

   Public signature verification key

   Symmetric authentication key

   Public and private authentication keys

Data Integrity

Data integrity is a security feature that protects data against unauthorized alteration either in transmission or in storage. An unauthorized alteration may include substitution, insertion, or deletion and may be intentional or unintentional. None of these can happen unnoticed if data integrity control is in place. Both symmetric and asymmetric cryptography techniques, such as digital signature and MAC, may be used. The following key types support data integrity:

   Private signature key

   Public signature verification key

   Symmetric authentication key

   Public and private authentication keys

Non-Repudiation

Non-repudiation is concerned with providing data integrity and authentication in a special way that allows a third party to verify and prove it. It is provided by asymmetric key cryptography and a digital signature relying on a signer’s private key. This security feature requires an especially rigid control of the keys, because it should prevent a signing party from successfully denying its signature. The following keys may be found when non-repudiation is supported:

   Private signature key

   Public signature verification key

Authorization

Authorization is the component of access control that is responsible for granting an object access to a particular resource after that object has already proved its identity (authenticated). A Kerberos ticket-granting service is a typical example of a key used for authorization. In more general terms, the following keys may be used for authorization:

   Symmetric authorization key

   Private authorization key

   Public authorization (verification) key

Cryptographic Strength and Key Size

The strength of cryptography depends on the strength of the algorithms, protocols, and keys and the strength of the security around the keys. In cryptographic applications that require key generation, key distribution, and encryption, whole suites of algorithms are used. For example, the first phases of IPSec and SSL include key negotiation and exchange, which may employ RSA cryptography. The following phases include generating a symmetric session key and using that key for encrypting data in transit with 3DES or AES. The strength of cryptography in this case is defined by the weakest link in this chain, so if in this example the key exchange employs very short public and private keys, the symmetric encryption key can be successfully intercepted and the transmitted data can be decrypted. Many factors should be considered, including the data and key’s life span, volume of the data to be encrypted with the same key, the key size, and the way the keys are generated. For example, if a key is generated straight from a password, the entropy in the key is significantly reduced, because a smart brute force attack can generate just the keys deriving from ASCII characters that meet password policy requirements.

The difficulty of breaking a key using brute force grows exponentially with key length (i.e., number of bits), because each bit doubles a number of possible combinations for brute force. A long key gives better security but worse performance, so figuring an optimal key size is important. It should also depend on the projected key’s lifetime. Temporary, or so-called ephemeral, keys generated for one session or one connection, may be shorter. The long-life keys protecting data at rest for years should be as long as possible.

One of the important characteristics of the keys is a crypto period. It is defined [NISTSP800-57-1] as the time span during which a specific key is authorized for use by legitimate entities, or during which the keys for a given system will remain in effect ⁵⁰. Duration of a crypto period limits a “window of opportunity” for successful cryptanalytic or any other attacks and volume of information that can be exposed if the keys are compromised. Generally, the shorter the crypto period, the better security, although more frequent key generation, revocation, and replacement may be costly and may create additional risk. Many factors should be taken into consideration when the crypto period for each key type is defined. NIST recommendations [NISTSP800-57-1] regarding crypto period, which assume usage of the environment with the goal of achieving better operational efficiency, are in Table 3.2.

Originator Usage Period (OUP) is a period of time in the crypto period of a symmetric key during which cryptographic protection may be applied to data.

As was mentioned earlier in this chapter, both the continuous progress in cryptanalysis techniques and increasing computer power available for breaking the keys, should be considered. By Moore’s law, computer speed doubles every 18 months, so the key size should be selected accordingly to protect the encrypted data against a brute force attack⁵¹. If a computer is N time faster, the key size should increase by log₂ N bits.

A successful brute force attack on a symmetric key algorithm, which in the case of perfect key entropy essentially consists of an exhaustive search of all the keys, would require on 2^N, divided by 2, where N is a size of the key in bits cycles. In addition to the key length, there is an effective key length factor. In the case of 3DES, which assumes total 3 * 56 = 168 bit key encryption, the effective key size is 80 bits if the first and third encryption rounds are performed using the same 56-bit key, and it is 112 bits if all three rounds employ unique 56-bit keys. As already discussed in the example of the keys derived from an ASCII or EBCDIC password, and as will be demonstrated in the example of asymmetric key strength, there is another factor which impacts the strength in addition to the effective key length. This factor is a key space.

Breaking asymmetric key cryptography may need much less resources than breaking symmetric key cryptography. This stems from the nature of asymmetric key cryptography. For example, an RSA private key, which is a target of asymmetric cryptography attack, should be generated to meet certain RSA criteria. When this key is generated, as well as its counterpart public key, it is being derived from the space of large prime numbers. It means the key space for an exhaustive search is much smaller. Also, some advances in research of factoring large numbers indicates that increasing the size of public/private keys is required. RSA indicated that if an easy solution to the factoring problem is found and further increase of RSA key size beyond 2048 bits is required, then using the RSA algorithm may become impractical. Elliptic curve cryptography (ECC) is based on the elliptic curve discrete logarithm problem, which may take a full exponential time to solve. It is comparable with symmetric encryption strength. That is why ECC is considered the most likely successor of the RSA algorithm in the asymmetric cryptography area.

Comparison of symmetric, RSA, and ECC asymmetric cryptography and the corresponding key lengths are shown in Table 3.3 [NISTSP800-57-1].

Some observations regarding comments in this table [NISTSP800-57-1]

1. Column 1 indicates the number of bits of security provided by the algorithms and key sizes in a particular row. Note that the bits of security are not necessarily the same as the key sizes for the algorithms in the other columns, due to attacks on those algorithms that provide computational advantages. Because some combinations of 0 and 1 for 2TDES and 3TDES keys can be predicted, it takes less computational power to guess the key value, which is equivalent to a shorter key.

2. Column 2 identifies the symmetric key algorithms that provide the indicated level of security (at a minimum), where 2TDEA and 3TDEA are specified in [SP800-67], and AES is specified in [FIPS197]. 2TDEA is TDEA with two different keys; 3TDEA is TDEA with three different keys.

3. Column 3 indicates the minimum size of the parameters associated with the standards that use finite field cryptography (FFC). Examples of such algorithms include DSA as defined in [FIPS186-3] for digital signatures, and Diffie–Hellman (DH) and MQV key agreement as defined in [SP800-56A]), where L is the size of the public key, and N is the size of the private key.

4. Column 4 indicates the value for k (the size of the modulus n) for algorithms based on integer factorization cryptography (IFC). The predominant algorithm of this type is the RSA algorithm. RSA is specified in [ANSX9.31] and [RSA PKCS#1]. These specifications are referenced in [FIPS186] for digital signatures. The value of k is commonly considered to be the key size.

5. Column 5 indicates the size of the key for algorithms based on elliptic curve cryptography (ECC)

Key Creation

A key generation process is a part of the key establishment function of the key management preoperation phase [NISTSP800-57-1].

The security of cryptography is based on the secrecy of the keys and the virtual impossibility of deducing the keys from the cipher or other sources. Another principle of cryptography that relates specifically to key generation is to avoid weak keys and make a key space “flat,” deriving from random numbers. Theoretically, any n-bit key’s key space, based on the random number generator, is a 2^N. In reality, in many cases, it is significantly smaller, which translates into lower resources required to break the key by specialized brute force. The older basic encryption tools generated keys from ASCII characters [SCHNEIER], which reduced the key space at least by half and also invited dictionary attacks. In 1995, two PhD students found that a release of Netscape’s SSL implementation chose the key from a recognizable subspace (bound to the clock) of the total key space. It significantly simplified attacks on SSL traffic. Another key generation weakness was discovered in one open source system that used a “predictable random” number generator [TECHREV-OPENSSL]. Originating the keys only from true random numbers may help to avoid this flaw. Another potential weakness of keys stems from a specific algorithm and its implementation, when knowledge of just one portion of a key is enough to decrypt a cipher and deduce the whole key. As in the previous discussion about key size, we need to look at the process of key generation in context: type of the keys, purpose of the keys, crypto application, and operation environment. It may be difficult to evaluate these factors because some of them may be proprietary. For crypto systems that support applications for the federal government, the FIPS 140-2 [FIPS 140-2 ] and the second draft of FIPS 140-3 [FIPS 140-3] are clearly defining requirements for key generation ⁵². These standards give a good benchmark for commercial systems as well and help to avoid the crypto system design flaws as described earlier. As FIPS 140-2 defines [FIPS 140-2]:

Random Number Generators (RNGs) used for cryptographic applications typically produce a sequence of zero and one bits that may be combined into sub-sequences or blocks of random numbers. There are two basic classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control.

A seed key, in its turn, is defined as “a secret value used to initialize a cryptographic function or operation.” NIST has documented approved methods of producing random numbers [ANNEXC-FIPS 140-2]. It also has certain criteria of entering the seed during a key generation process, both for the case when the keys are generated inside a crypto module or outside. Entering the keys into the crypto module may be manual (e.g., keyboard) or electronic (e.g., smart cards, tokens, etc.). A seed key, if entered during key generation, may be entered in the same manner as cryptographic keys. Physical security requirements for the crypto modules that generate the keys are also described in FIPS 140-2 and 140-3 (draft) and include temper-resistant measures.

Although crypto key generation both for symmetric and asymmetric cryptography is based on RNG, the process is different for generating symmetric keys and asymmetric key pairs.

   For asymmetric cryptography, the key pairs are generated according to the approved algorithms and standards. A static key pair can be generated by the end entity or by a facility that securely distributes the key pairs or by both the end entity and the facility in concert. A private signing key supporting the non-repudiation property should be generated on the end entity site and never leave that site. Ephemeral asymmetric keys are usually generated for the establishment of other keys, have a short life, and may be generated by the end entities and key distribution facilities. The following is a brief description of the RSA key pair, as one of the asymmetric key pair generation processes.

   An RSA key pair consists of an RSA private key, which in digital signature applications is used to compute a digital signature, and an RSA public key, which in the digital signature applications is used to verify the digital signature. In encryption and decryption applications, the RSA private key is used to decrypt data and the RSA public key is used to encrypt the data. As described in [FIPS 186-3] ⁵³:

An RSA public key consists of a modulus n, which is the product of two positive prime integers p and q (i.e., n = pq), and a public key exponent e. Thus, the RSA public key is the pair of values (n, e) and is used to verify digital signatures. The size of an RSA key pair is commonly considered to be the length of the modulus n in bits (nlen). The corresponding RSA private key consists of the same modulus n and a private key exponent d that depends on n and the public key exponent e. Thus, the RSA private key is the pair of values (n, d) and is used to generate digital signatures. Note that an alternative method for representing (n, d) using the Chinese Remainder Theorem (CRT) is allowed as specified in PKCS #1. In order to provide security for the digital signature process, the two integers p and q, and the private key exponent d shall be kept secret. The modulus n and the public key exponent e may be made known to anyone. Guidance on the protection of these values is provided in SP 800-57. This Standard specifies three choices for the length of the modulus (i.e., nlen): 1024, 2048 and 3072 bits.

A CA for signing certificates should use a modulus whose length nlen is equal to or greater than the moduli used by its subscribers. For example, if the subscribers are using an nlen = 2048, then the CA should use nlen ≥ 2048. RSA keys shall be generated with respect to a security strength S.

Parameters p and q are randomly generated and should be produced from seeds from a random or pseudorandom generator [NIST SP 800-90]. These prime numbers’ seeds should be kept secret or destroyed after the modulus n is computed.

   For symmetric cryptography, the keys may be generated from a random number generation method or regenerated from the previous key during a key update procedure. Another way is to derive the key from a master key using approved FIPS140-2 derivation functions, but eventually they are also coming from a random number. For secure key distribution purposes, split knowledge procedures can be used, and in that case, different components of the key may be generated in different locations, or may be created at one location and then split into components. Each key component will provide no knowledge of the entire key value (e.g., each key component must appear to be generated randomly). The principle of split knowledge is that if knowledge of k (where n is a total number of components and k is less than or equal to n) components is required to construct the original key, then knowledge of any k − 1 key components will not provide any information about the original key other than, possibly, its length. In addition, a simple concatenation of key components should not produce a key.

Key Distribution and Crypto Information in Transit

Key distribution mainly belongs to the key establishment function of the preproduction phase of key life cycle. By the NIST definition [NISTSP800-57-1], “it is the process of transporting a key and other keying material from an entity that either owns the key or generates the key to another entity that is intended to use the key.” In many cases, it is a hard problem, which is solved differently for different types of keys. For example, data encryption keys are originated and distributed differently compared with signature verification keys, and public keys are distributed differently from secret keys. This problem is more difficult for symmetric key applications, which need to protect the keys from disclosure. In any case, key distribution should use certain protection mechanisms to meet the following requirements, either the business dictates manual distribution or automated or a combination of both:

1. Availability of the keys for a recipient after transmission by a sender (redundant channels, “store and forward” systems, and retransmission as a last resort).

2. Integrity, which should detect modification of keys in transit. MAC, CRC, and digital signature can be used. Physical protection is required as well.

3. Confidentiality. It may be achieved by key encryption or by splitting the key and distributing its components via separate channels (“split knowledge”). Physical protection should apply as well.

4. Association of the keys with the intended application usage and related information may be achieved by appropriate configuration of the distribution process.

Symmetric Keys Distribution

Symmetric keys may be distributed manually or electronically, by using a public key transport mechanism, or they may be previously distributed for transport using other encryption keys. Keys used only for encrypting data in storage should not be distributed at all, except for backup or other specially authorized entities. A description of methods of symmetric keys distribution follows.

Splitting the keys. It is formally defined in FIPS 140-2 as a process by which a cryptographic key is split into multiple key components that individually share no knowledge of the original key. These components can be subsequently input into, or output from, a cryptographic module by separate entities and combined to recreate the original cryptographic key. Thus, FIPS 140-2 Level 3 requires

   A cryptographic module that separately authenticates the operator entering or outputting each key component.

   Cryptographic key components must be directly entered into or output from the cryptographic module without traveling through any enclosing or intervening systems where the key components may inadvertently be stored, combined, or otherwise processed.

   At least two key components must be required to reconstruct the original cryptographic key.

In practical examples, several components of the key can be stored on devices with different ports and network connections, as well as on different crypto tokens that require individual authentication by designated security officers.

Manual Key Distribution

The process should ensure that the keys are coming from an authorized source and are received by the intended recipient. Also, the entity delivering the key should be trusted by both the sender and the receiver. A key in transit should be encrypted with a key intended for key wrapping.

Electronic Distribution of Wrapped Keys (Key Transport)

It requires a preliminary distribution of key-wrapping keys. In many implementations, a public key of an asymmetric key pair is used as a key-wrapping key; therefore, a recipient in possession of the private key will be able to “unwrap” the symmetric key. If symmetric cryptography is used for wrapping the keys, those key-wrapping keys should be distributed via a separate channel of communication.

Public and Private Keys Distribution

As was discussed in the review of the methods of cryptography, one of the main advantages of using public and private key cryptography is easier key distribution of public keys. A party in possession of private keys can sign its message, and any receiving party who obtains the sender’s public key can verify the signature. Likewise, any sender can obtain an encryption public key of a recipient, and only the recipient in possession of the counterpart private key can decrypt the encrypted data. While confidentiality of the public key is not needed, authenticity is. That is why public keys are usually distributed wrapped in public key certificates, issued and signed by a trusted certificate authority. The certificate, along with a public key, contains the subject’s name and other attributes that indicate how the public key can be used. For easy access by relying parties, the certificates are either delivered with a signed message or made available in the directories and other publicly accessible distribution points.

Private keys are managed and distributed differently. If a signing private key must support non-repudiation, it should be generated and remain only in possession of the owner of this key, so no distribution applies. Although generating of public/private key pairs often takes place on a subject’s node and the keys are placed in the crypto store on its hard drive or a hardware module, in some applications this is not the case. As described in the “Key Creation” section of this chapter, sometimes asymmetric key pairs, which do not have to support digital signatures with non-repudiation, may be generated on one of the servers of the public key infrastructure (either registration or distribution server), in cooperation between the servers and the subscriber, who is the owner of the keys. In such applications, private keys should be delivered to a subscriber via a secure encrypted channel with mutual authentication. Depending on policy, private decryption keys are also put in escrow, so that data may be decrypted if a subscriber leaves the organization or loses access to the keys.

When the public/private key pair is generated on the subscriber’s site, there is no need to distribute the private key—it stays where it was generated and where it belongs.

A private key of a key pair generated on a central facility will be distributed only to the intended owner of that key, using either secure manual distribution or electronic distribution with security measures similar to those for symmetric key distribution, for example, authentication, encrypted channel, split knowledge, etc.

As was mentioned earlier, distributing static public keys does not require encrypted channels or split knowledge techniques, but it has its own specifics. A relying party, who obtains the keys either for verifying an owner’s signature or for encrypting a message for the key owner, should have a high level of assurance that,

1. The key really belongs to the subject.

2. The key is associated with certain attributes belonging to the subject.

3. The key is valid.

4. The key is allowed by its policy to be used for the intended purpose.

All of these issues are addressed by using Public Key Infrastructure (PKI) and issuing X.509 certificates containing the subject’s public keys and attributes. The certificates are digitally signed by a PKI Certificate Authority and can be distributed via open channels, manually, or via e-mail or published by LDAP, HTTP, and FTP servers. Because each subject’s certificate is signed by a CA, a relying party should treat that CA’s certificate itself as an anchor of trust. Distribution of the trusted CA’s certificate is usually done via other channels. It can be preinstalled by a software manufacturer or obtained from other distribution points. More details about asymmetric key management are provided in a separate PKI section later in this chapter.

Key Storage

The ultimate goal of key management is to prevent any unsanctioned access without impeding legitimate use of the keys by crypto applications and service and key life cycle management processes. Key storage should meet several requirements, which may be different for different type of keys [NISTSP800-57-1]. Generally, these requirements are broken into several categories.

Keys may be maintained within a crypto module when they are in active use, or they may be stored externally under proper protection and recalled when needed. The protection of the keys in storage should provide

   Integrity (by CRC, MAC, digital signature, checksums, parity check, etc.): In addition to logical integrity, the keys stored in HSM may be physically protected by the storage mechanism itself. For example, a crypto store may be designed so that once the key is installed, it cannot be observed from outside. Some key-storage devices (specifically those that meet FIPS 140-2 level 3) are designed to self-destruct when threatened with key disclosure or when there is evidence that the key device is being tampered with.

   Confidentiality (by encryption, wrapping, and logical access control). Also, physical security is important (see earlier comments related to integrity).

   Association with Application and Objects (making sure that the key belongs to a designated object; e. g., encapsulating public keys with the object DN in a signed certificate or storing private signing keys in the object’s protected key store).

   Assurance of Domain Parameters (making sure that domain parameters used in the PKI keys exchange are correct). Domain parameters are used in conjunction with some public key algorithms such as DSA and ECDSA (called p, g, and q parameter) to generate key pairs, to create digital signatures, or when generating shared secrets that are subsequently used to derive keying material.

In addition to key protection, the key store should also provide availability. Keys should be available for authorized users and applications for as long as data is protected by these keys. A secure key and escrow is usually used for this. After the crypto period expires, the keys should be placed in an archive, which can be combined with backup storage.

Overall security requirements and business reasons may define the type of crypto store. Keys stored in the computer files may be more easily accessible than those that are stored in the hardware such as smart cards, external token devices, or PCMCIA. Usually the vendors of crypto applications such as PKI CA or application gateways, which perform signing and decrypting of SOAP messages, provide the users with the choice, so the implementer may decide to either use a hardware security module as a key store or to store the keys in the files. An application’s independence from hardware crypto device vendors is achieved by using standard RSA PKCS#11 compliant interfaces ⁵⁴. A key file store is usually protected with an additional level of access control, so even a root user may not be able to access the key database if he or she does not have permissions and credentials for it.

Symmetric and private keys must be destroyed if they have been compromised or when their archive period (according to the policy) expires. Through the crypto period, when copies of the keys are made, these events should be documented; therefore, the keys’ destruction should apply to all the copies. Specific methods used for key destruction are warranted by application and business requirements and acceptable risk. There are no specific requirements for destroying public keys. More specifically, processes for key destruction are described in NIST SP800-57 Part 2 [(“Recommendation for Key Management—Part 2: Best Practices for Key Management Organization”)] ⁵⁵. Zeroization is a technical term for destroying the keys by causing the storage medium to reset to all zeroes [NIST SP800-21] ⁵⁶. Automatic zeroization is required when an attempt is made to access the maintenance interface or tamper with a device meeting FIPS 140-2 level 3 requirements [FIPS 140-2]. The key management policy should describe in detail the process of zeroization in a specific key management system.

If it is believed that an encryption key of data at rest was compromised, this data should be reencrypted with a new key. This whole process is called key rotation, and it includes decrypting data with the old encryption key (which is believed to be compromised) and rekeying this data with the new encryption key. With large volumes of data, data availability may be affected. That is why a lot of efforts are made to limit the need to rekey data. It is achieved by using a randomly generated value as an encryption key and making it unavailable directly for any user, including administrators. The application administrator may control encryption and decryption processes, but the key contents will never be disclosed.

Key Update

Modern key management is highly automated. For most phases of the key life cycle, manual steps are not required. Although creating a seed sometimes may require users to move a mouse or enter a long sequence of random key strokes, users do not manually select, communicate, or transcribe real crypto keys. Modern key management makes a periodic key update in accordance with key policies easier. One example is an automatic key and certificates rollover in the PKI. When a key or certificate is approaching the “valid to” date and time, an automated key update will kick off. Another example is session encryption keys. When an encrypted connection just starts, an initial key is negotiated and exchanged between parties using the key encryption key. When a session duration or volume of transferred data exceeds the limits, a new session is established between the same parties, and a new session key will be renegotiated and used for transactions. More frequent key updates will reduce the chance of a successful cryptoanalytic attack and the volume of confidential data at risk. On the other hand, it may reduce system performance and increase the chance of key compromise in the case of misconfiguration. All the pros and cons should be evaluated, and keys’ life span and frequency of key updates should be reflected in the policy.

Change of keys in the operational phase of the key life cycle may be caused by several reasons, as was alluded to earlier: key compromise, crypto period approaching the expiration date, or just a desire to reduce the volume of data encrypted with the same key.

A new key may be produced by auto rekeying or by an automated function updating an existing key. Rekeying is producing a key that is completely independent on the key it replaces. Rekeying is applicable when an old key is compromised, the key approaches its expiration date, or a new session key must be established according to the requirements.

Another way of changing the keys is by applying a nonreversible function to an existing key. Updating an old key in this manner does not require new key distribution or exchange between parties, so it may be less expensive. Parties may agree to exchange the keys on a particular day and time or upon exchanging a certain volume of encrypted data or on other conditions. This method does not apply in the case of key compromise.

Key Revocation

Whenever a key is compromised, it cannot be trusted to provide required security, cannot serve its purpose, and should be revoked. Generally, the key is considered to be compromised if it is released to or discovered by an unauthorized entity or this event is suspected to have happened. A key may enter the compromised state from any state except the destroyed state. Although the compromised key cannot be used for protection, in some cases it still may be used to process cryptographically protected information, with reasonable caution and suspicion. For example, a digital signature may be validated if it can be proved that the data was signed before the signing key was compromised and that the signed data has been adequately protected.

Key revocation applies both to symmetric and asymmetric keys and the process should be formally described in the Key Management Policy. In the asymmetric key management systems and PKI, technically, a public key is revoked (or most often, a public key certificate, containing that key), but as a result, its counterpart private key is also getting automatically revoked.

Information about key revocation may be sent as a notification to the involved parties, which would indicate that the continued use of the key is not recommended. This notification should include complete information about the revoked key, the date and time of revocation, and the reason. Based on the revocation information provided, other entities could then make a determination of how they would treat information protected by the revoked keying material.

Another method is to provide the participating entities (i.e., relying parties) with the access point for obtaining the status of the key material. For example, if a signature verification public key is revoked because an entity left the company, the information may be published in the Certificate Revocation List (CRL). But an application may still honor the signature if it was created before the certificate was published in the CRL ⁵⁷. At the same time, if a signing private key was compromised in an unknown time frame, but eventually the public key certificate was revoked, the situation should be assessed more carefully. Certificate revocation in more detail will be reviewed in the section titled “Public Key Infrastructure.”

A symmetric key that is used to generate a MAC may be revoked so that it is not used to generate a new MAC for new information. However, the key may be retained so that archived documents can be verified.

The recommended approach to the key revocation policy is to reflect it in the life cycle for each particular key. Thus, when a key is used in communication between just two parties, the entity revoking the key just informs another entity. On the other hand, if the key is used within an infrastructure with multiple relying parties, the revoking entity should inform the infrastructure, which should make the information about key revocation available to all relying parties.

Key Escrow

Generally, escrow is defined as something delivered to a third person (usually called an “escrow agent”) to keep, and to be returned to the delivering entity under certain proof and conditions. This “something” may be a document, money, or a key.

In cryptography applications, a key escrow system operates with two components of one key, and these two components are entrusted to two independent escrow agents. For government applications [FIPS 185], these key components will be presented by the escrow agent to a requester, which may be an entity related to the owner of the key or a law enforcement organization, upon certain conditions, authorizations, and authentication ⁵⁸.

This approach is implemented in electronic surveillance of encrypted telecommunications involving specific electronic devices. The key components obtained by the requester are entered into this device and enable decryption. Neither of the escrow agents can perform decryption, because it has just one component of the key. In applications for the private sector, the key components may be kept by two officers; therefore, if a key owner entity is not available, its encrypted information may be decrypted upon directions to the escrow officers from a higher official. Two types of risk exist in this schema: (1) collusion and (2) failure of reassembling and using the key for its intended purpose.

In order to support escrow capabilities in telecommunication, the U.S. government adopted the symmetric encryption algorithm SKIPJACK and a Law Enforcement Access Field (LEAF) method, which presents one part of a key escrow system enabling decryption of encrypted telecommunications. Both the SKIPJACK and the LEAF creation method are implemented in electronic devices. The devices may be incorporated in security equipment used to encrypt (and decrypt) telecommunications data ⁵⁹.

Decryption of lawfully intercepted telecommunications may be achieved through the acquisition and use of the LEAF, the decryption algorithm, and the two escrowed key components.

Backup and Recovery

Backup

According to 800-57-2 [NISTSP800-57-2], key recovery is a stage in the life cycle of keying material; mechanisms and processes that allow authorized entities to retrieve keying material from key backup or archive ⁶⁰. Key backup and recovery is a part of the KMS contingency plan, which according to 800-57-1 [NISTSP800-57-1],... “is a plan that is maintained for disaster response, backup operations, and post-disaster recovery to ensure the availability of critical resources and to facilitate the continuity of operations in an emergency situation.”

As in the life cycle of any system, data can become unusable because of many reasons such as file corruption, hardware failure, configuration errors, etc. But in the case of cryptosystems management, backup should be considered only if there are no other ways (such as rekeying or key derivation) to provide continuity. These specific recommendations apply because of the risk associated with key backup, and the fact that key and other crypto information backup compromise is detrimental to the KMS operations. When planning key backup, the following questions should be answered: what key material needs to be backed up, where and how will the backup be stored, how will the backup and recovery procedures be performed, and who is responsible.

Not all the keys and cryptographic information should be backed up. For instance, private signing keys should not be backed up, to avoid any questionable situation with non-repudiation. However, in the specific case of the CA’s signing key, this does not apply, because unrecoverable loss of this key would prevent new certificates from being issued until the CA was rekeyed. Special security measures apply for the backup of this key, such as storing it on a removable hardware crypto token protected by multiple keys and passwords that is stored in a safe under administrative control. Separation of duties in this schema prevents collusions and key compromise. Ephemeral keys and shared secrets, which are generated during key negotiations and used for one session for data in transit, do not need to be backed up. An RNG seed should not be backed up either, because it is not used immediately for data encryption and is needed only for key generation.

It is important to mention that the life span of the key backup should be equal to or longer than the life span of the encrypted or signed data. Another specific feature that makes key backup and recovery different compared with similar processes for other data is the criticality of a key’s availability and, thus, backup redundancy. Both competing requirements for minimizing risk of the backed-up keys’ disclosure and redundant storage for robust key recovery should be considered.

Key Recovery

Keys may not be available for cryptographic operations when the key material stored as a file in the system or on a hardware device/token is corrupted, the key owner either loses access to the key material (i.e., forgotten/lost password) or is not available when the organization needs access to the data, and some other situations. Keys may need to be recovered to enable decryption of data previously encrypted with a lost key or to verify the integrity and authenticity of previously signed data if a signature verification key is lost. The key recovery process acquires a key from backup storage and makes it available for the decryption or verification process.

Key Distribution

The main reason why asymmetric cryptography and public certificates gained popularity is the manner in which they address the key distribution problem. In order to support authentication and confidentiality, each party needs to have its own symmetric keys dedicated for data exchange with one correspondent. If A is going to encrypt for B, C, and D, it would have to have individual keys for B, C, and D and send the keys to those parties in a secure manner. Each of B, C, and D would have to do the same. In sum, the two main problems of symmetric cryptography are the number of the required keys and the problem of their secure distribution. Public key cryptography solves both problems because of its nature. Keys come in pairs, and only the private key should be kept secret and should not be distributed. Its counterpart public key may be available to all parties, and hence may be published for public access on any server; that is, file server, LDAP, or Web server.

For encryption, a recipient’s public key may be used by any party wanting to encrypt data for that recipient, who is in possession of the counterpart private key. It guarantees that only this recipient in possession of that private key will be able to decrypt the data.

For digital signature verification, each recipient may obtain a public verification key of the sender and be confident in the authenticity of the signature, because only the sender holds the private key that is used to produce the digital signature being verified.

The main problem that exists with public key distribution is to guarantee the key’s integrity and binding to the identifier of the holder of the counterpart private key. This problem is solved by using X.509 public key certificates, which bind the subject name to a public key, and this binding is sealed by the signature of the PKI Certificate Authority. Because the CA signature is trusted by all parties, the integrity of the public key and its binding with the subject are trusted too.

Public key distribution, which is implemented via certificate distribution, boils down to publishing these certificates on a server accessible by relying parties or just attaching the certificate to an encrypted or signed message. Private keys should not be distributed at all.

Certificate and Key Storage

When talking about PKI certificates and the keys, we should always remember the guidance provided in CP and CPS documents. The purpose of the certificates and their keys will dictate how they should be handled and stored.

For two-key-pair applications, where the encryption key pair and the corresponding public key certificate are created by the CA, the encryption public key certificates are most often placed in the subscriber’s Directory entry and also in the PKI/CA database. Copies of the decryption private key and the encryption public key certificate will be securely sent to the subscriber and will be stored on the subscriber’s machine on the disk or HSM. Decryption private keys should never be published, but they should be backed up. In a two-key-pair PKI, the subscriber generates the signing key on its machine and securely stores the signing private key on the disk or HSM. It sends only the verification public key to the CA in a secure manner. The signing private key is not sent to the CA, and it is never backed up in the CA’s database. When the CA receives the verification public key, it generates a verification public key certificate. A copy of this certificate is stored in the CA database, and is also sent to the subscriber. Often, when the PKI subscriber sends a signed message to any recipient, it attaches the verification certificate to it. So, a relying party does not have to access the directory to retrieve this certificate, which is required for signature verification.

For one-key-pair applications, a dual-usage key pair is generated on the subscriber’s machine and stored on the disk or HSM. A copy of the dual-usage private and public key will be sent to the CA. The private key will be stored in the CA database. The CA will use the public key to generate a dual-usage public key certificate and will put it in the user’s Directory entry. A copy of this certificate will be stored in the CA database. It will be also sent to the subscriber and will be stored on its machine on the disk or HSM.

In summary, there are several places where certificates and public and private keys are stored: PKI/CA database, Directory server, and subscriber’s machine. The specifics are highly dependent on PKI implementation and CPS directives.

PKI Registration

PKI consists of many components: Technical Infrastructure, Policies, Procedures, and People [PKIREGAG]. Initial registration of subscribers (either users, or organizations, or hardware, or software) for a PKI service has many facets, pertaining to almost every one of the PKI components. There are many steps between the moment when a subscriber applies for a PKI certificate and the final state, when keys have been generated and certificates have been signed and placed in the appropriate locations in the system. These steps are described either explicitly or implicitly in the PKI CPS.

Reference to the CP and CPS associated with a certificate may be presented in the X.509.V3 certificates extension called “Certificate Policies.” This extension may give to a relying party a great deal of information, identified by attributes “Policy Identifier” and “Policy Qualifier” in the form of Abstract Syntax Notation One object IDs (ASN.1 OID).

One type of Policy Qualifier is a reference to CPF, which describes the practice employed by the issuer when registering the subscriber (the subject of the certificate). Here we focus on the following:

1. How the subject proves its organizational entity.

2. How the person, acting on behalf of the subject, authenticates himself in the process of requesting a certificate.

3. How the certificate issuer can be sure that the subject, whose name is in the certificate request, is really in possession of the private key, to which the public key is presented in the certificate request along with the subject’s name.

How the Subject Proves Its Organizational Entity

Authentication requirements in the process of registration with PKI depend on relations between the CA and the organization, the nature of an applying End Entity (EE) and CP, which is stating the purpose of the certificate. Thus, the organization may have its internal CA or may use a commercial CA to serve its all certificates needs. It may issue certificates of low assurance, which support just internal e-mail digital signature, or issue high assurance certificates, which encrypt and authenticate high value transactions between the organization and external financial institutions. Among end entities, there can be individuals, organizations, applications, elements of infrastructure, etc.

Organizational certificates are usually issued to the subscribing organization’s devices, services, or individuals within the organization. These certificates support authentication, encryption, data integrity, and other PKI-enabled functionality when relying parties communicate. Among organizational devices and services may be,

   Web servers with enabled TLS, which support the server’s authentication and encryption

   Web services security gateways, which support SOAP messages’ authentication and signatures’ verification, encryption, and decryption

   Services and devices, signing content (software codes, documents, etc.) on behalf of the organization

   VPN gateways

   Devices, services, and applications supporting authentication, integrity, and encryption of Electronic Data Interchange (EDI), B2B, or B2C transactions

   Smart cards for end user authentication

Among procedures enforced within applying organizations (before a certificate request to an external CA is issued) are the following:

   An authority inside the organization should approve the certificate request.

   The authority should verify that the subject is who he or she claims to be.

   After that, an authorized person (authorized submitter) within the organization will submit a certificate application on behalf of the organization.

   The organizational certificate application will be submitted for authentication of the organizational identity.

   Depending on the purpose of the certificate, an external certificate issuer will try to authenticate the applying organization, which may include some but not all of the following steps, as in the following example [VeriSignCPS]:

   Verify that the organization exists.

   Verify that the certificate applicant is the owner of the domain name, which is the subject of the certificate.

   Verify employment of the certificate applicant and if the organization authorized the applicant to represent the organization.

A correlation between the level of assurance provided by the certificate and the strength of the process of validation and authentication of the EE registering with PKI and obtaining that certificate is always taking place.

How a Person, Acting on Behalf of the Subject, Authenticates to Request a Certificate (Case Studies)

Individual certificates may serve different purposes, for example: for e-mail signing and encryption, and for user authentication when they are connecting to servers (Web, directory, etc.) to obtain information or for establishing a VPN encryption channel. These kinds of certificates, according to their policy, may be issued to anybody who is listed as a member of a group (for example, an employee of an organization) in the group’s directory and who can authenticate itself. An additional authorization for an organizational person may or may not be required for PKI registration.

An individual who does not belong to any organization can register with some commercial CAs with or without direct authentication and with or without presenting personal information. As a result, an individual receives his or her general use certificates. Different cases are now briefly described.

Online Certificate Request without Explicit Authentication

As in the example with VeriSign certificate of Class 1, a CA can issue an individual certificate (aka Digital ID) to any EE with an unambiguous name and e-mail address. In the process of submitting the certificate request to the CA, the keys are generated on the user’s computer, and initial data for a certificate request, entered by the user (user name and e-mail address) is encrypted with a newly generated private key. It is all sent to the CA. Soon the user receives by e-mail his or her PIN number and the URL of a secure Web page to enter that PIN in order to complete the process of issuing the user’s certificate. As a consequence, the person’s e-mail address and ability to log into this e-mail account may serve as an indirect minimal proof of authenticity. However, nothing prevents person A from registering in the public Internet e-mail as person B and requesting, receiving, and using person B’s certificate.

Authentication of an Organizational Person

The ability of the EE to authenticate in the organization’s network (e.g., e-mail, domain) or with an organization’s authentication databases may provide an acceptable level of authentication for PKI registration. Even just the person’s organizational e-mail authentication is much stronger from a PKI registration perspective than authentication with public e-mail. In this case, user authentication for PKI registration is basically delegated to e-mail or domain user authentication. In addition to corporate e-mail and domain controllers, an organization’s HR database, directory servers, or databases can be used for the user’s authentication and authorization for PKI registration. In each case, an integration of the PKI registration process and the process of user authentication with corporate resources needs to be done (see Figure 3.9).

A simplified case occurs when a certificate request is initiated by a Registration Authority upon management authorization. In this case, no initial user authentication is involved.

Individual Authentication

In the broader case, a PKI registration will require a person to authenticate potentially with any authentication databases defined in accordance with CPS. For example, to obtain a purchasing certificate from the CA, which is integrated into a B2C system, a person will have to authenticate with financial institutions, which participate in the Internet purchasing transactions. In many cases, an authentication gateway or server will do it, using a user’s credentials (see Figure 3.10).

Dedicated Authentication Bases

In rare cases, when a PKI CPS requires user authentication that cannot be satisfied by the existing authentication bases, a dedicated authentication database may be created to meet all CPS requirements. For example, for this purpose a prepopulated PKI Directory may be created, where each person eligible for PKI registration will be challenged with his or her password or personal data attributes. Among possible authentication schemes with dedicated or existing authentication databases may be a password with additional personal challenge-response data, such as mother’s maiden name, make and year of a first car, biometrics, and others.

Face-to-Face

The most reliable, but most expensive method to authenticate an EE for PKI registration is face-to-face authentication. It is applied when the issued certificate will secure either high risk and responsibility transactions (certificates for VPN gateways, CA and RA administrators) or transactions of high value, especially when the subscriber will authenticate and sign transactions on behalf of an organization. To obtain this type of certificate, the individual must personally present and show his or her government-issued ID or badge and other valid identifications to the dedicated corporate registration security office and sign a document, obliging use of the certificate only for assigned purposes. All the procedures and sets of ID and documents that must be presented before an authentication authority are described in CPS.

Proof of Possession

A group of the key PKIX-CMP messages, sent by the EE in the process of initial registration, includes “Initialization Request,” “Certification Request,” and “PKCS10 Certification Request” messages. The full structure of these messages is described in [CRMF] ⁶² and [PKCS10] ⁶³. Certificate request messages, among other information, include “Public Key” and “Subject” name attributes.

The EE has authenticated itself out-of-band with the registration authority (RA) on the initialization phase of initial registration. Now an additional proof, that the EE, or the “subject,” is in possession of a private key, which is a counterpart of the “public key” in the certificate request message, is required. It is a proof of binding, or so-called “Proof of Possession”, or POP, which the EE submits to the RA.

Depending on the types of requested certificates and public/private key pairs, different POP mechanisms may be implemented:

   For encryption certificates, the EE can just provide a private key to RA/CA, or the EE can be required to decrypt with its private key a value of the following data, which is sent back by RA/CA:

   In the direct method, it will be a challenge value, generated and encrypted and sent to the EE by the RA. The EE is expected to decrypt and send the value back.

   In the indirect method, the CA will issue the certificate, encrypt it with the given public encryption key, and send it to the EE. The subsequent use of the certificate by the EE will demonstrate its ability to decrypt it, and hence the possession of the private key.

   For signing certificates, the EE just signs a value with its private key and sends it to RA/CA.

Certificate Issuance

A certificate can be looked at as an electronic equivalent of a subject’s ID document, which is issued for particular purposes in accordance with the organization’s policy. Technically, the sanctioned and expected usage of the certificate is represented in the X.509 certificate “Key Usage” attribute. A relying party application is capable of verifying this attribute; therefore, the certificate will be used only within the scope of its key usage. For example, encryption certificates are issued for encrypting data for a recipient whose name is in the certificate, and verification certificates are issued to verify a signature of the sender who signed the message. Very often, one certificate is issued to serve many purposes. In any case, a relying party has information to help decide how much security the certificate can support, provided that the issuance and management of this certificate is trustworthy. Two main issues relating to this question are: Is an issuing CA trustworthy and how is the information in the certificate secured?

   A certificate is digitally signed by an issuing CA, and it can be trusted only if the CA is trusted. A guard verifying a person’s ID first looks to see what organization or country issued that ID and if the issuing authority is in the trusted list. In the same way, a relying party that verifies a certificate will verify if an issuing CA is in the trusted list. Technically, the application checks if that CA’s certificate is installed in a designated storage and if it is not in the revocation list.

Information in the certificate is secured by a digital signature of the issuing CA. Anybody can view and browse the certificate and each of its attributes, including the subscriber (“subject”) name with its public key and the CA (“issuer”) name with its key identifier and the thumbprint. The certificate binds together all the attributes, including the most important: the subject’s name and its public key. The integrity of this binding is preserved by the signature of the trusted issuing CA. Some details of this process already have been mentioned in the previous section, “PKI Registration.” Before signing that binding, the CA has to receive evidence that a subscriber public key is associated with the subscriber. One of the ways to obtain it is a proof of possession of the private key. The subscriber, who generated a key pair, signs a message containing its public key and its common name with its private key. The message is sent to the CA directly or via the registration authority (RA) and is used as material for the public certificate. Other certificate attributes and extensions are defined by certificates’ templates. The format of the X509.V3 certificate is presented in Figure 3.11.

   Once all the attributes are filled in, the certificate is digitally signed by the CA and sent to the subscriber or published in the Directory.

Trust Models

One fundamental purpose of PKI is to represent the trust relationship between participating parties. When a verifying party verifies another participant’s certificate, generally it verifies a chain of trust between that participant’s certificate and the verifier’s anchor of trust. If that party’s certificate was issued by a CA that is directly trusted by the verifier, then that CA is an anchor of trust. Otherwise, there are one or more intermediate CAs that constitutes a chain between the anchor of trust and the party’s certificate to be verified. In both cases, the anchor of trust is based on a preconfigured certificate, in most cases provided out of band or as a configuration process. Several models described in the following text are available to provide chains of trust for PKI applications supporting multiple communities.

Subordinate Hierarchy

Very often, the current and long-term business reasons suggest putting two or more CAs into a hierarchical trust relationship. The CA hierarchy contains one root CA on top of the hierarchical tree and one or more levels of CA hierarchy of subordinate CAs (Figure 3.12). Each of the subordinate CAs has one immediate superior and may have one or more subordinates (the root CA is a top superior). A superior CA issues and signs CA certificates for its immediate subordinates. Only the root CA can issue and sign its own certificate. For crypto application operations, a subordinate issuing CA does not need to certify its superior. Each participant should know and trust a root CA, which establishes an anchor of trust. A relying party that trusts the root CA needs to validate a path from the root CA to the sender’s certificate.

This model is good for internal enterprise applications, but the hierarchy may be hard to implement between enterprises because it must have in place the shared cross-enterprise certificate policies and one shared root of trust. For more details about certificate chains issued by hierarchical PKI, see the section titled “Certificate Chains” later in this chapter.

Cross-Certified Mesh

Cross-certified mesh is probably the most general model of trust between CAs and participating PKIs. The hierarchical model described earlier may be interpreted as a mesh with some constraints. The mesh model is good for intercommunity and dynamically changing enterprise PKI applications, especially for nonhierarchical organizations. When organizations need to establish trust relations, they cross-certify their CAs, which does not require a change of anchors of trust or other elements of existing PKIs. This model is also good for merging previously implemented PKIs into one PKI. Cross-certification includes an exchange of participating PKIs’ public verification keys and having each participating PKI sign the received key by its internal root CA. When more than two PKIs participate in the mesh, they create a web of trust by mutually cross-certifying each to each. Although no changes to each participating PKI are required, certificate verification in this model of trust is more difficult to implement because there may be multiple certificate paths. More details are given in the section titled “Cross-Certification” later in the chapter.

Bridge CA

When a cross-certified mesh is too dynamic and grows too fast to include n CAs, it may not scale well because it is supposed to include and support n(n − 1) cross-certifications and also because of potentially ambiguous verification paths. A bridge CA model may be helpful in this case. A large and very comprehensive implementation of this model is Federal Bridge Certification Authority (FBCA), which is well described in [FBCACP] and [FPKIATO]⁶⁴. As in the FBCA example, any bridge CA issues and manages cross-certificates for participating PKIs. By creating a mesh of participating root CAs, the bridge CA model allows participating parties to mutually validate each other’s certificate paths. More details are given in the section titled “Cross-Certification” later in this chapter.

Trusted List

The most well-known example of a Trusted List model is a set of publicly trusted root certificates embedded in the Internet browsers. When a client system verifies another party’s certificate, it tries to chain that certificate to one of the certificates in the list of trusted roots. A fundamental difference between this model and the previously discussed hierarchical, mesh, and bridge models is in the fact that the parties to be verified have to accommodate the relying parties’ trusted roots. It moves management overheads from PKI CAs to the clients and in an environment with many CAs, may require a large number of root certificates to be included in the list of trusted CAs.

Certificate Chains

Each CA’s certificate is located in the certificate chain, which starts at the root CA certificate and includes the certificates of all superior subordinate CAs. Certificates of the issuing CAs that issue certificates for end entities are at the end of this chain (see Figure 3.12). Several considerations should be taken into account:

   The validity of an issuing CA’s certificate depends on the validity and life span of the whole certificate chain. If a root or an intermediate certificate at a higher level of hierarchy expires, validation of the end entity certificate issued by the issuing CA down the hierarchy should show negative. If any certificate in the chain is revoked, validation should show negative also. That is why the higher CA’s certificates and certificate revocation lists (CRLs) usually have a life span that is significantly longer. The decreasing life span of the certificates in the chain is presented in Figure 3.13.

   The higher hierarchical CAs require higher security, because a compromise means revoking of all the subordinate and issuing CAs on lower levels as well as all the end entities’ certificates. As a result, more certificates will be compromised and will require revocation. It is a common practice in PKI to take a root CA offline and lock its key storing medium in a secured safe store. It needs to be returned online only when its root certificate and immediate subordinate CA’s certificates are approaching the end of life and need to be reissued to maintain validity of all subordinate chains or when a new immediate subordinate CA certificate should be issued or when one of the existing subordinate CAs is compromised and its certificate must be revoked. Another reason to put the root CA online is to let it update and publish the CRL when approaching the CRL expiration or when the CRL must be updated.

   The main purpose of the CA hierarchy and the use of certificate chains is to establish an anchor of trust (based on the root CA) and create a hierarchical model of trust. Distributing only a root CA certificate among all the relying parties is easier than distributing multiple CA’s certificates. A relying party that needs to validate a certificate issued by an issuing CA in the hierarchical PKI starts walking up the chain until it reaches a root certificate, which is expected to be installed as a trusted CA certificate.

Certificate Revocation

When the private key of a subscriber is compromised or is suspected to be compromised, when an attribute of the certificate (e.g., rank) changes, or when trust between the CA and the subscriber is changed (for example, the employee holder of the certificate leaves the company), the issued certificate should be revoked immediately. The revocation process, from its origination to execution, should be described in the CPS. To inform relying parties, the revoked certificate is placed on a CRL, and the CA reissues, signs, and publishes the updated CRL. Regularly, or immediately after the revocation event, the latest CRL is published in a commonly available space (such as the directory server).

When a relying party (an application) receives a signed message, it should try to verify the signature. First, it checks to make sure the associated certificate has not expired, and second, it checks to make sure the certificate is still valid. Depending on business requirements, there can be two scenarios:

   A relying party is required to validate the certificate with the instantaneous revocation data. This is a real-time validation, and the relying party does not use any cache CRL.

   A relying party is only required to use a valid nonexpired CRL. A CRL is considered valid if a trusted CA has signed it and the current time is between the “this Update” and “next Update” CRL attributes. So any caching mechanisms can be used to store the CRL on the validating site.

Traditional CRL Model

A relying party checks a certificate against the latest published CRL. If the certificate is not in the CRL, it is assumed valid. Two cases are possible when the application is making this check:

   It does not have the current CRL in cache and has to retrieve it from a directory or other repository. This may also be the case if the real instantaneous certificate status is required. Requesting the CRL, the application will try to obtain the most current one.

   It does have the current CRL in cache. In this case, no instantaneous status is required, and, therefore, certificate validation can be done without retrieving the CRL from a repository.

In applications with a large number of subscribers and relying parties and with a high revocation rate, the CRL request rate can be very high, and CRLs themselves can be very long. This may introduce network and CRL-repository performance problems.

Modified CRL-Based Models

Several methods described in [CRMOD] and in [DCRL] attempt to address the aforementioned problems ⁶⁵.

Overissued CRLs Reduce Peak Request Rate

Importantly, when the cache CRL is acceptable, the CRL requests’ distribution peaks exponentially at the moment when all relying parties try to request the CRL the first time or when they try to do it after their cached CRLs expire.

As described in [CRMOD], one remedy for reducing the peak of CRL requests may be to issue the CRLs before they expire or to overissue CRLs. Because the CRL validity time remains the same, new overissued CRLs will have a shifted “next update” expiration time. Hence, relying parties will request replacement of their expired CRLs at different times. In other words, this method will spread out CRL requests. As shown in [CRMOD], if a CRL is valid for 24 hours and is reissued every 6 hours instead of every 24 hours, the peak request rate is reduced almost four times. This method can be recommended for applications that allow CRL cache and for which the expected revocation rate is low.

Segmented CRLs Reduce CRL Size

The idea is to reduce the size of the CRL or the portion of the CRL that a relying party needs to download, although this measure cannot reduce the peak request rate. Certificates may be allocated to different CRLs, based on some criteria or at random. This method was implemented in CRL distribution points (CRLDP), as in [RFC2459] ⁶⁶. X.509v3 certificates have a standard extension attribute called “CRLDistributionPoints” that provides the URI for the CRL, which is designated to the certificate if this certificate is revoked. When a relying party needs to validate the certificate, it requests this particular CRL. Designation of a particular CRL segment (CRLDP) to certificates is supported by CAs.

This method is recommended for applications that allow CRL caching and that have a high certificate-revocation rate. If instantaneous revocation data is required, it is also better than the method suggested earlier in traditional CRL or in the earlier section of this chapter titled “Over-Issued CRLs Reduce Peak Request Rate.”

Delta CRLs

As was described earlier DCRL, the idea of using delta CRL was introduced to reduce the peak bandwidth in PKI applications, allowing caching but also requiring fresh certificate revocation information. A delta CRL provides only certificate revocation information changes since the full base CRL was issued. Base CRL is a traditional CRL containing all nonexpired revoked certificates. Its validity is much longer-lived than delta CRL, and a relying party does not request it frequently. Delta CRL validity is short. Hence, a relying party has to request it often. Because it contains only certificates revoked since the latest base CRL was issued, its size is supposed to be small. With delta CRL, an average request rate for the base CRL drops significantly, although the peak rate does not.

In DCRL, Cooper describes a further modification of delta CRL, which should allow a significant reduction of the base CRL request peak rate as well. It is a so-called sliding window delta CRL, which combines delta CRL with the CRL over-issuing method. Every time a delta CRL is issued, a full CRL is reissued as well. As described in the section titled “Over-Issued CRLs Reduce Peak Request Rate,” it spreads out CRL requests from relying parties and reduces peak base CRL requests.

This sliding window delta CRL method promises the ability to supply very fresh CRL data combined with relatively low values for CRL-based validation methods, peak request rate, and bandwidth. Choosing an optimal window size is crucial.

Online Certificate Status Protocol

The Online Certificate Status Protocol (OCSP) is presented in [OCSP]⁶⁷. A relying party sends to the validation server its request on the status of the certificate in question. The server returns its signed response. The request/respond formats are presented in the following text. Because the OCSP request and response data chunks are significantly smaller than with all CRL-based ones, the bandwidth required for OCSP is lower compared with the CRL models for the same validation rate. On the other hand, the need to sign all OCSP responses implies higher power requirements on the validation server.

The following three items are data structures. These represent OCSP transactions.

OCSP Request

   Protocol version

   Service request

   Target certificate identifier

   Optional extensions

OCSP Response

   Version of the response syntax

-   Name of the responder

-   Responses for each certificate in a request

-   Optional extensions

-   Signature algorithm OID

-   Signature computed across hash of the response

   Response for Each Certificate in a Request

-   Certificate identifier

-   Certificate status value (GOOD, REVOKED, UNKNOWN)

-   Response validity interval

-   Optional extensions

Unlike CRL-based models, an OCSP model is designed to provide instantaneous certificate status upon the certificate status request. Also, unlike CRL-based models, OCSP provides only the status of requested certificates, and it cannot be used by offline clients; for example, wireless devices wishing to authenticate the network to which they are attaching.

Cross-Certification

Cross-certification is a way of establishing trust between entities that are subscribers for different PKI certificates services and which have been issued certificates by different nonrelated CAs. In other words, it is a way of establishing a third-party trust. To make this happen, two CAs need to establish trust between each other, which is implemented via CA cross-certification. Cross-certification has a lot of implications. Complete understanding of Certificate Policy and Practice of each CA is required, because each party needs to know how much it can trust to the certificates issued by another CA, what are the enrollment, issuing, and revocation procedures of another CA, and what is the liability. Legal agreements and documents may be required as well.

How Applications Use Cross-Certification

If company A wants to trust company B, it should receive from company B its verification key, then issue a cross-certificate containing this verification key, and sign this certificate with company A’s signing key. If an entity in company A receives a message signed by company B, it will trust the signature because A certified its verification key with its signature. Trust does not necessarily have to be mutual. If company B does not want to trust A, it does not have to cross-certify A, although A cross-certified B; that is why we should also be specific if cross-certification is one-way or two-way (or mutual) trust. In addition to cross-certification, the companies should provide each other access to the end users’ certificates.

Consider two cases when users of two companies that cross-certified their CAs will exchange secure messages (see Figure 3.14).

   An employee of A is going to send a signed and encrypted message to an employee of company B. He needs to find that employee and his certificate in the search base or through directory lookup.

   The employee of A verifies the cross-certificate issued by company A, to make sure that company B is still trusted. This is done by verification of its signature and validity dates and also checking if that certificate is not in the authority revocation list (ARL) of company A.

   Now the employee of A can verify if the encryption certificate of the recipient in company B is valid. It is done by checking integrity, validity dates, and presence in the CRL of company B. Also, the certificate should be signed by a key associated with the public key of the CA of company B, which is available in the cross-certificate.

   If all the foregoing verifications are successful, then a user in company A will send the message with its signature and will encrypt this message with the public key from the certificate of the user of company B.

   Recipient B, after decrypting the message, will try to verify the signature of sender A.

   It validates the issuer of the verification certificate attached to the message by comparing the signature with a public key of the CA of company A, which is available in the cross-certificate issued by company B. It also verifies if the cross-certificate is valid and is not in company B’s ARL.

   The user of company B also validates the verification certificate’s integrity, its validity dates, and presence in company A’s CRL.

How Cross-Certification Is Set Up

With all the considerations mentioned at the beginning of this section, both mutual and unilateral cross-certification may be done online and offline.

Online Cross-Certification

Online cross-certification requires TCP/IP connectivity between both CAs as well as their Directories. A company A, which wants to trust company B, has to give company B special access credentials (one time password, generated by CA A) to access A. A CA administrator of company B enters these credentials and connects to A to complete cross-certification. It securely sends online the CA B verification public key. CA A generates and signs a cross-certificate containing the public key of B. Depending on implementation and the PKI vendor, the process may be automated, and the new cross-certificate issued by A may be sent over to B and imported into its database and Directory.

Offline Cross-Certification

Offline cross-certification is the only method for CAs that does not have network connectivity. Nevertheless, the Directories should have connectivity for cross-certification as well as for online cross-certification. As in the case of online cross-certification, we assume that CA A wants to trust CA B, and CA B wants to be trusted by A. However, unlike in the online case, the offline cross-certification process is started by B generating its PKCS#10 certificate request with its verification public key and sending it to company A. After A verifies the request, it issues and signs the cross-certificate, stores it, and also sends it to B. The administrator of trusted CA B will import the cross-certificate issued by CA A into its database and Directory.

Once unilateral cross-certification is complete, the process may be repeated in the opposite direction if mutual cross-certification is required for business needs.

Cross-Certificates’ Revocation

In order to break the trust between CAs, the cross-certified parties revoke the cross-certificates they issued. For example, if company A revokes the cross-certificate for company B, users of A will not be able to verify messages signed by users of B and will not be able to encrypt messages for users of B. Cross-certificates may need to be revoked for one of the following reasons:

   Partnership between companies A and B is terminated and their users do not need to use each other’s certificates.

   The cross-certified CA is not trusted anymore.

   The cross-certified CA reissued its certificate and regenerated keys; thus, a new public key should be used for the cross-certificate.

Revoked cross-certificates are added to the ARL, which is used for any certificate verification as was mentioned earlier.

How Cross-Certification with a Bridge CA Is Implemented in Practice

The preceding example just described how cross-certification between two CAs works. With more than two CAs participating in this model and the CAs’ mesh growing, certificate verification difficulties will start increasing. The bridge CA model helps to resolve these problems. Diagrams representing a cross-certified mesh and bridge CA are presented in Figure 3.15. Let us use FBCA [FBCACP] as an example for the Bridge CA case study:

   FBCA can be looked at as a nonhierarchical hub that would allow trust paths between participating PKIs to be created.

   The FBCA would issue certificates to Principal CAs, which are CAs within participating PKIs, designated to cross-certify those PKIs directly with FBCA through the exchange of cross-certificates. The number of cross-certificates to support n PKIs is n * 2.

   Each PKI participating in FBCA, should be represented to FBCA by a single Principal CA. If a participating PKI is a hierarchical PKI, the Principal CA is typically its root CA. If a participating PKI is a mesh PKI, the Principal CA may be any designated CA within that PKI.

   The issued certificate will be posted in the FBCA directory. All cross-certified entities are notified by FBCA when the certificates are issued.

   Now, the subscribers of PKIs registered with FBCA may exchange signed and encrypted messages. The certificate’s verification path will span FBCA and a sender’s certificates.

   The certificate trust path between one participating PKI and all others can be discontinued by revoking its FBCA cross-certificate. A new CRL will be published in the FBCA directory.

Review of Cryptanalytic Attacks

Attacking a cryptosystem reveals its weaknesses and flaws. Cryptanalysis can be used to improve the design of a cryptosystem and may result in the discarding of a cryptographic algorithm altogether. The security architect should understand how cryptanalytic attacks can be used in validating cryptographic design as part of an architecture.

Attack Models

The following basic types of attacks are based on having some knowledge of the algorithm used. These attacks are characterized by the degree of plaintext and ciphertext the cryptanalyst has access to:

   Ciphertext-only attack: A sample of ciphertext, and preferably a large volume of ciphertext encrypted with the same algorithm, is required. While this is one of the most difficult attacks to execute, a successful attack reveals plaintext, and if completely successful, the key. This type of attack can reveal flaws in the algorithm. While cryptographic algorithms used in real-world applications must be vetted for weaknesses against ciphertext-only attacks, some protocols such as WEP have been found vulnerable to this type of attack.

   Known-plaintext attack: Having some plaintext and the corresponding ciphertext is necessary. An objective of this type of attack is to determine the key and decipher all messages encrypted by it. This type of attack can be very practical when the corresponding plaintext is discoverable or can be deduced. Users of ZIP file archive encryption are very susceptible to this type of attack when a small portion of their archive is decrypted and becomes available for use in a known-plaintext attack.

   Chosen-plaintext attack: This attack involves choosing the plaintext with the corresponding ciphertext.

   Chosen-ciphertext attack: This attack involves choosing the ciphertext to be decrypted and gaining access to the resulting plaintext.

Symmetric Attacks

Variations on the attack models can be used in a controlled environment to reveal weaknesses in a cryptosystem and analyze an algorithm’s strength. Two common attacks applied to the testing of symmetric ciphers are the techniques of differential cryptanalysis and linear cryptanalysis:

   Differential cryptanalysis: These techniques involve a chosen plaintext attack with the aim of recovering the secret key. The basic method of differential cryptanalysis involves investigating the differences in ciphertext produced from pairs of chosen plaintext having specific differences. While this type of attack was used for determining a theoretical weakness in DES, the amount of chosen plaintext necessary (in excess of 10¹⁵ bytes) makes it impractical. DES was designed to resist differential cryptanalysis [Coppersmith].

   Linear cryptanalysis: These techniques are based on a known-plaintext attack using pairs of known block-cipher plaintext and corresponding ciphertext in order to generate a linear approximation of a portion of the key. Instead of trying to keep track of differences propagated by chosen plaintext, linear cryptanalysis seeks to keep track of Boolean information in pairs of known plaintext and corresponding ciphertext to generate a probability in the confidence level of a specific key value. This method of attack is also commonly used to test block algorithms. While a theoretical attack against DES using linear cryptanalysis exists, it is considered impractical due to the amount of known plaintext–ciphertext required (2⁴³ plaintexts) [Matsui].

Asymmetric Attacks

The algorithm in asymmetric cryptosystems is often based on solving some sort of mathematical problem such as the difficulty of integer factorization. As a result, applying the attack models to asymmetric cryptosystems can involve finding improved or faster methods of solving the various mathematical problems. Designing or integrating with a particular asymmetric scheme must take into account mathematical discoveries such as more efficient methods of finding discrete logarithms or integer factorization.

Hash Function Attacks

The principle applied in determining the collision resistance of hash functions is based on the birthday problem in probability theory. This type of attack is known as the Birthday attack. The term birthday pertains to the probability that in a set of randomly chosen people some pair of them will have the same birthday ⁶⁸.

Many cryptographic hash algorithms such as MD5 and SHA-1 are built from one-way functions, which are limited in their ability to provide collision resistance. When validating security in cryptosystems, one must consider that hash functions are applied in digital signature schemes and used as building blocks in MAC construction.

Network-Based Cryptanalytic Attacks

Cryptanalytic attacks can be facilitated by network communications such as protocols involved in the transmission of data or in operations such as key exchange. The following network-based attacks target more than just the cryptographic algorithm and exploit weaknesses in areas such as communication protocols or transmission methods:

   Man-in-the-Middle attack: This technique involves intercepting and forwarding a modified version of a transmission between two parties. In this type of attack, the transmission is modified before it arrives at the receiving party. Safeguarding a protocol against this attack usually involves making sure authentication occurs at each endpoint in the communication. For example, in a Web service design, it may be necessary to require mutual SSL authentication involving use of a mutually trusted certification authority.

   Replay attack: This attack involves capturing and retransmitting a legitimate transmission between two parties. Using this technique, impersonation or key compromise and unauthorized access to information assets may be possible. Protecting a protocol against this attack usually involves use of session tokens, time-stamping of data, or synchronization of transmission. For instance, IPSec provides an antireplay service using verification of sequence numbers, and the AH protocol in IPSec employs one-way hash functions to protect against impersonation.

   Traffic Analysis attacks: Observing traffic flow in encrypted communications can reveal information based on message volume or communication patterns, or show which parties are communicating. Protection against traffic analysis is a concern not only in the design of military signals intelligence systems, but in the design of commercial systems as well. For instance, SSH, when operating in interactive mode, transmits every key stroke as a packet. Packet analysis can therefore reveal information about the password lengths. A general countermeasure to protect against traffic analysis is to use traffic padding where feasible. Another approach to protecting messages traversing untrusted networks from traffic analysis involves anonymizing the message sender. This can be done by using a chain of proxy servers where the message is encrypted separately at each proxy in order to make the source and destination of the communicating parties more difficult to determine.

Attacks against Keys

An ideal goal for cryptanalysis is to extract the secret key. Observing how keys are used is important in validating a cryptographic design. Using the same key to encrypt larger volumes of data increases the success of a cryptanalytic attack. Also, the use of an appropriate key length is important, as noted earlier in the chapter.

Testing for weak keys during generation is another basic element of validating a cryptosystem. Understanding the ability of a random number generator to introduce entropy during key generation is an important factor in this, because greater randomness makes determining the key more difficult.

Secret keys must also be protected from unauthorized access and should remain encrypted when stored. In a cryptographic system where multiple secret keys are necessary, for example, with a tape encryption appliance device, it is common to encrypt individual working keys with a top-level master key. The storage of the top-level secret key used in such a cryptosystem can be done using key shares, a technique also known as split-knowledge. This involves splitting the key into multiple pieces and granting access to each share to separate individuals. This ensures that no one individual has access to the stored master key. To ensure security of this master secret key when it is in use within the cryptosystem, logical access controls and physical controls such as tamper-proof enclosures are used. In validating cryptosystems, it is essential to check that the subsystem components and processes that protect the secret key are functioning as intended. The following attacks against keys are variations on the cryptanalytic attack models and are also important in validating cryptosystems:

   Meet-in-the-Middle attack: This attack applies to double encryption schemes such as 2DES and 3DES; it works by encrypting known plaintext using each possible key and comparing results obtained “in the middle” from decrypting the corresponding ciphertext using each possible key. This known plaintext attack was used against DES to show that encrypting plaintext with one DES key followed by encrypting it with a second DES key is no more secure than using a single DES key, and it reduces the strength of 3DES to only 112 bits.

   Related-Key attacks: These forms of attack involve relationships between keys that become known or are chosen while observing differences in plaintext and ciphertext when a different key is used. For instance, two keys that transform all plaintexts identically can be considered equivalent, a simple relation. It is beneficial to employ a related-key attack against stream ciphers because they typically employ a common key in combination with some varying nonsecret initialization vector (IV). An example of using a related-key attack to demonstrate that an encryption scheme is insecure is with WEP, in which the RC4 stream cipher uses a keystream comprising a WEP secret key and an exposed IV.

Brute Force Attacks

For a cryptosystem to be considered secure, a successful brute force attack must be computationally infeasible. For symmetric key ciphers, this involves an exhaustive search of the key space in order to determine plaintext. The result of the brute force is the secret key used for encrypting the ciphertext. Besides providing an indication of the security of the cryptosystem, a successful brute force attack involving a particular secret key would mean that any ciphertext encrypted with that particular key and potentially all future derived keys would become readable via the attack.

A brute force attack against asymmetric key ciphers involves applying computing resources to solving the underlying mathematical problem the algorithm is based on, such as in factoring large integers for RSA public-key encryption. The computational feasibility of solving a particular problem such as factoring an integer of a particular size gives an indication of the strength of the algorithm.

Side-Channel Cryptanalysis

Side-channel attacks are based on information gained from the physical implementation of the cryptosystem. These attacks mainly deal with obtaining and analyzing information that originates from the cryptosystem hardware rather than weaknesses in the cryptographic algorithm. Side-channel attacks can be based on the execution time of a cryptographic algorithm, power consumption within a cryptographic module, or electromagnetic emanations from a computer. Side-channel cryptanalysis requires substantial technical knowledge of the underlying hardware.

Susceptibility to side-channel cryptanalytic attack is an important consideration for any architecture where cryptography is applied. The following are some of these types of attacks:

   Timing attacks: This attack requires the ability to accurately measure the time required to perform a particular operation within a cryptosystem. Timing attacks are based on detailed hardware performance characteristics such as memory cache hits and CPU instruction time for a given key and input data (plaintext or ciphertext). By using the baseline performance characteristics for a specific piece of hardware where the cryptosystem is implemented, successful attacks against protocols and algorithms such as Diffie–Hellman, RSA, DSS, and others can be executed [Kocher].

   Differential Fault Analysis: This method involves introducing hardware faults into the cryptosystem in order to determine the state of internal data. This type of attack can be used to read the state of memory in order to determine a secret key. The technique can be applied to various types of semiconductor memory, including integrated circuits that are frozen and removed or to smart card memory that is read nondestructively [Samyde et al.].

   Differential Power Analysis: In this method, power consumption measurements in a hardware device such as a smart card are made during encryption operations while ciphertext is recorded. The attack can be used to reveal a secret key [Kocher et al.].

Risk-Based Cryptographic Architecture

Computing power, which grows by Moore’s law; new developments in cryptanalysis; virtually borderless enterprise network topologies; wider than ever exposure to targeted attacks from different domestic and foreign entities—all these factors are constantly moving cryptographic standards higher. At the same time, the main purpose of cryptography—supporting confidentiality, integrity, and availability—should be served in the most productive and cost-effective manner. We move from DES to AES, from a key size of 56 bits to 256 bits, but as was stated in the section titled “Key Management,” the strength of any crypto system or application is more than just strength of the algorithms and key size.

More often, crypto systems are compromised because of weaknesses in key management and processes around it. A risk-based approach to the crypto systems and applications design should help to architect a balanced and cost-effective solution that meets business requirements. Many areas of cryptographic architecture for government agencies are driven by regulatory compliance with appropriate prescriptive guidance documented in the NIST FIPS publications referred to earlier. Designing cryptography for private sector industries, where regulatory compliance is less strict or not required at all, leaves more room for the security architect making design decisions. But it may still be a good idea to follow a risk-based approach. The security architect can use either qualitative or quantitative measures when assessing the risk. If quantitative risk assessment data is available, each design option may be assessed based on the cost, benefits, and the risk. Otherwise, qualitative methods should be used. Risk is assessed to determine the impact of given losses and the probability that these losses will occur.

The process of designing a cryptographic system is similar to the process used for any other IT system. The architecture should include appropriate crypto modules, components, and methods, and should be integrated with the surrounding infrastructure and supported applications in order to address the organization’s needs and meet the requirements. Based on the requirements, several cryptographic methods may be needed. For example, both symmetric and asymmetric cryptography may be needed in a system, each performing different functions (e.g., symmetric encryption, asymmetric digital signature, and key establishment). It is important to be able to demonstrate traceability from the requirements back to the policies, goals, and risks to be mitigated. The following areas may be considered for a cryptographic system high-level design:

   Hardware- and software-based components

   Security of cryptographic modules

   What cryptography should be used for a network environment

   What approved algorithms will be used, and key lengths

   Key management infrastructure

   Integration with hosting infrastructure and supported applications

   Interoperation with external organizations

   User interface

   User acceptance

   User training

It is important for the security architect to develop confidentiality, integrity, and availability objectives. These objectives are at a high level and should address security, in general, and cryptography, specifically. The design should include software and hardware, procedures, physical security considerations, environmental requirements, etc.

After preliminary high-level and requirements-based architecture design is done, a preliminary risk assessment should be performed, and specific unique requirements associated with each component should be finalized. After the risk assessment has been performed, policies should be developed regarding the use of evaluated systems and cryptographic modules operating within the designed system.

Identifying Risk and Requirements by Cryptographic Areas

Risk management includes two components: assessing the risk and selecting and implementing appropriate countermeasures. The largest areas of risk addressed by cryptography are unauthorized disclosure and data modification, or confidentiality and integrity. Although the risks cannot be completely eliminated, they can be reduced to an acceptable level by using cryptographic controls. The risk management process ensures that the threats are known, as well as their impact, and that cost-effective countermeasures are applied. Risk assessment includes assessment of the assets and current protecting mechanisms, identification and assessment of the threats, assessment of potential losses and their likelihood, and their classification by criticality and sensitivity, and, finally, identification of potential mitigating controls and cost-benefit analysis.

Most often, the type of risk assessment that is performed is a qualitative analysis, rather than a formal quantitative analysis, and the results are used in developing the system requirements and specifications. The scope of risk analysis varies depending on the sensitivity of the information and the number and types of risks that need to be addressed. The next task is to identify categories of cryptographic methods and techniques that meet the requirements and mitigate the specific risks. There may be more than one method that can mitigate each risk.

Traceability from the requirements back to the policies and associated risk assessment is important. The following table is based on the data presented in the NIST SP800-21-1 [SP800-21-1] and demonstrates logical dependencies between risk and requirements for different cryptographic areas.

Note that the risk of each cryptographic area should be assessed for each individual system and application. If the risk is higher than an acceptable level, technical requirements should be strengthened.

Case Study

To clarify how all this information fits together, walk through the following use case and the process of defining requirements, identifying risks, and then proposing cryptographic methods that meet those requirements and mitigate the risks.

The use case involves secure communications for a device management function. Cryptography for communication between a management console and management server and between the management server and managed devices should support confidentiality, authentication, authorization, and integrity. In this scenario, the business function being performed is firewall rule changes. So the management console will be a firewall administrator’s workstation, the management server will be the system that affects firewall rulebase changes, and the managed devices will be firewalls. For simplicity’s sake, the scope will exclude firewall monitoring, audit logging, and device network configuration functions, and the design will be vendor neutral (refer to Figure 3.16).

Information flow in this use case is represented by flow “1” between the management console and management server, and by flow “2” between the management server and the managed devices. For the rulebase management scenario:

   Managed devices may receive and store very sensitive configuration and corporate information, and its unauthorized disclosure may be detrimental.

   Integrity of the management data in transit and in store is crucial.

   Availability of these encrypted communication channels is important, but lost connectivity for a short time will not lead to major losses.

The functional requirements will be:

   Provide secure communication between the manager’s console and the management server.

   Provide secure communication between the management server and managed devices.

The following risks are defined:

   Unauthorized disclosure of data in transit between the console and server and server and managed devices.

   Unauthorized and undetected modification of data in transit between the console and server and server and managed devices.

   An unauthenticated or unauthorized console gets access to the server.

   An unauthenticated or unauthorized server gets access to a managed device.

   Data in transit is modified in a nonauthorized manner (man-in-the-middle attack).

   Unauthorized disclosure, modification, and substitution of secret/private keys.

   Unauthorized substitution and modification of public keys.

The intent is to apply cryptography as the means to meet the requirements and address the risks. For the use case, a security architect would recommend the following:

1. The management server includes an internal CA, which issues certificates for every console and managed device.

2. Key pairs are generated on each new console and device added to the system. After that, the keys are sent to the management server’s CA for issuing certificates.

3. TLS tunnels with Mutual Authentication (MTLS) between the management server, and devices and console provide required access control, integrity, and confidentiality of the data in transit.

4. A FIPS 140-2-compliant hardware cryptographic module provides required physical and logical security, including protection of the private and secret keys, RNG, and AES 128 encryption for TLS sessions. Keys never appear in cleartext. These measures ensure mandatory key management.

5. Access to the consoles and management server with an internal CA requires 2-factor authentication. All data flows between the management server and console and devices goes encrypted via MTLS tunnels.

The recommendations we propose for our scenario fall into the following cryptographic areas. For a sound design, they should meet the following requirements:

Cryptographic Area:

   Cryptographic algorithms (identify FIPS-approved algorithms and other cryptographic algorithms): Encryption.

   Cryptographic algorithms: Digital signatures.

   Cryptographic key management: Specify random number generation, key generation, key establishment, key entry and output, key storage, and key destruction.

Technical and Assurance Requirement:

   FIPS-approved AES algorithm or three key TDEA algorithm; conformance tests.

   Digital Signature Algorithm (DSA), RSA, ECDSA, digital signature generation/verification; message digest; random/pseudorandom number generation; hash function. Algorithms for generating primes p and q; private key generation; conformance tests. Cryptographic requirements addressed in overall system/product requirements.

   Key entry/output: Levels 1, 2—plaintext. Levels 3, 4—encrypted keys or split knowledge for manual distribution.

   Key Destruction: Zeroize all plaintext cryptographic keys and other unprotected CSPs.

   Specification of the FIPS-approved key generation algorithm; documentation of the key distribution techniques.

   NIST-approved key generation algorithms.

   Use of error detection code (message authentication code).

   Encrypted IVs.

   Key naming.

   Key encrypting key pairs.

   Random number generation.

   Cryptographic requirements addressed in overall system/product requirements.

It is important to look at the cryptographic areas and requirements both individually and as a whole. The following are some common design flaws that might be found in this or other scenarios:

1. Using a strong cryptographic algorithm when the RNG supporting key generation is weak does not protect against key weaknesses and potential compromise.

2. The RNG may be very strong, but key management has a flaw and does not provide sufficient protection for private and secret keys.

3. Remote access control to the system incorporates strong two-factor authentication, but local access and physical access control are very weak.

4. Bulk data encryption is performed on the management server data store using the wrong block cipher mode; for example, ECB for bulk data encryption.

5. Encryption is implemented without any integrity checking; for example, HMAC.

6. Key exchange is performed with weak or no authentication.

7. Faulty key distribution methods; for example, sending the key in cleartext!

8. Symmetric key is not changed when the IV or the counter space is exhausted.

An unbalanced architecture design will produce a weak crypto system in which properly selected and designed components cannot compensate for the weak ones that introduce additional risks.

Cryptographic Compliance Monitoring

A risk-based cryptographic architecture will employ components in a manner that meets business requirements while allowing for a business-defined acceptable level of risk. To manage this risk effectively, there must be control over the risk-impacting factors in designs of solutions employing cryptography. For instance, a digital signature scheme must employ an acceptable cryptographic hashing function, such as those specified in NIST FIPS 180-4, the Secure Hash Standard [FIPS 180-4]⁶⁹. So, cryptographic compliance monitoring in the context of design of a cryptosystem would mean assessing conformity to cryptographic standards.

Security requirements for an IT solution can include confidentiality, integrity, or one of the other benefits of cryptography. The source of these requirements can be regulations or standards specified by legal frameworks, corporate governance, or policies. For instance, corporate standards requiring confidentiality of personal information may require encrypting the information. So, cryptographic compliance monitoring in the design of an IT solution would mean measuring adherence to regulations in a larger context, where cryptographic controls are used to satisfy a regulatory requirement.

Cryptographic Standards Compliance

Cryptographic standards provide for assurance that a particular security level that is required can be maintained. An example is NSA Suite B, which includes FIPS-197 (AES) and complements encryption algorithms for hashing, digital signature, and key exchange that U.S. federal agencies must adhere to. Making certain that products follow the same standards such as NSA Suite B will also help ensure compatibility.

The Computer Security Division at NIST coordinates test suites for many of the NIST cryptographic standards. The Cryptographic Algorithm Validation Program (CAVP)⁷⁰, established by NIST and the Communications Security Establishment Canada (CSEC)⁷¹, provide validation testing via accredited third-party laboratories for a number of cryptographic algorithms. CAVP validation of an algorithm used in a cryptosystem is a prerequisite for another validation program established by NIST, the Cryptographic Module Validation Program (CMVP)⁷². CMVP validates adherence of cryptographic modules to Federal Information Processing Standards (FIPS)140-2 Security Requirements for Cryptographic Modules, and other FIPS cryptography-based standards. CAVP and CMVP programs maintain and publish validation lists for algorithms and cryptographic modules. The CAVP list provides validated implementations of cryptographic algorithms showing vendor, validation date and certification number, operational environment, and other information such as key sizes and block cipher mode. The CMVP list shows FIPS-140-2 validated modules by vendor, validation date and certification number, and other details related to FIPS-140-2.

Cryptographic standards will also appear in corporate security policies and standards such as those indicating when to use encryption or specifying the level and strength of encryption to use, including key lengths and crypto periods.

Determining if cryptographic controls meet governmental or corporate standards is a function of compliance monitoring. Determining compliance with such cryptographic standards should be performed as part of an assessment of an IT system’s design. It is important that this be completed during the requirements phase of an IT project, so that a given solution is developed to meet these standards.

Compliance with security standards for cryptography can also occur at the user level. For example, an organization may require that its personnel use encryption when sending certain types of data via e-mail. It should be noted that monitoring user-level actions such as these may be difficult, and require specialized services such as those provided by data leak protection solutions.

An additional area where compliance is associated with a cryptosystem is the notion of a compliance defect that may exist within a cryptosystem. A compliance defect may be thought of as the inability of a cryptosystem to securely perform one of its functions, and is a noncompliance in a more general sense. Don Davis defines a compliance defect in a cryptosystem as a rule of operation that is both difficult to follow and unenforceable [Davis]. According to Davis, public key cryptography has five unrealistic rules of use corresponding with the crucial moments in a key pair’s life cycle. Davis calls these compliance defects and specifies them as follows:

1. Authenticating the user (issuance): How does a CA authenticate a distant user when issuing an initial certificate?

2. Authenticating the CA (validation): Public key cryptography cannot secure the distribution and validation of the root CA’s public key.

3. Certificate revocation lists (revocation): Timely and secure revocation presents enormous scaling and performance problems. As a result, public key deployment is proceeding without a revocation infrastructure.

4. Private key management (single-sign on): The user must keep his long-lived private key in memory throughout his login session.

5. Passphrase quality (PW-Change): There is no way to force a public key user to choose a good passphrase.

Industry- and Application-Specific Cryptographic Standards Compliance

It is important that cryptographic controls themselves be compliant with standards. It is likewise important to satisfy the requirements of standards that specify how a cryptographic benefit must be employed. For instance, the California Information Practice Act (SB1386) ⁷³ specifies that if customer information is encrypted when it is stored and transmitted, it is exempt from costly notification procedures in the event of a breach. Regulations applying to information systems that include cryptographic requirements will often specify use of a cryptographic control in a general sense, such as needing “encryption” or requiring a “key management system.”

Payment Card Industry Data Security Standard

One industry standard involving encryption is the Payment Card Industry Data Security Standard (PCI DSS), which requires protection and encryption of cardholder data. In the PCI standard, the essential requirement in protecting cardholder data is to not store it at all if possible. When it must be stored, the PCI standard specifies general attributes for cryptographic controls while enumerating the operational methods that must be employed. For instance, hash functions, cryptography, and key generation must be “strong.” In relation to cryptographic requirements, PCI focuses on operational procedures and administrative controls such as key-custodian acceptance of responsibilities.

So, auditing a system for PCI compliance will include these types of cryptographic requirements. To see the PCI DSS 2.0 requirements relating specifically to encryption, refer to the portions of the standard that describe key management as well as protection and encryption of cardholder data at the PCI Security Standards Council Web site: https://www.pcisecuritystandards.org/security_standards/index.php

Health Insurance Portability and Accountability Act

A governmental regulation that includes requirements for the benefits that cryptography can provide are the provisions of the Health Insurance Portability and Accountability Act of 1996 (HIPAA) enacted by the U.S. Congress. These requirements are found in the Administrative Simplification provisions of the act (HIPAA, Title II), which among other things addresses the security and privacy of health data.

Requirements relating to cryptography are found in the Final Rule on Security Standards [Final Rule]. The Final Rule is where the U.S. Department of Health and Human Services stipulates three types of security safeguards required for compliance: administrative, physical, and technical. Within the technical safeguards, the Final Rule provides a set of security standards as follows:

   Access Control

   Audit Controls

   Integrity

   Person or Entity Authentication

   Transmission Security

These standards support the Final Rule by providing a minimum security baseline intended to help prevent unauthorized use and disclosure of Protected Health Information (PHI). Within each standard, policies, procedures, and technologies are either required and must be adopted, or are subject to individual evaluation (known as “addressable implementation specifications”).

Encryption for data at rest falls under the Access Control standard, because encryption used with an appropriate key management scheme can be used to deny access to PHI, except for authorized individuals. The standards in the Final Rule state that encryption of data at rest is an addressable implementation specification, leaving it up to the system owner to determine whether it is required.

While the use of specific cryptographic technologies is not stipulated in the Audit Controls and the Integrity standards, meeting these standards is required by HIPAA. Thus, cryptographic hashing algorithms and digital signatures can be used as a basis for supporting the Integrity standard. The same cryptographic controls can support Audit Controls by ensuring that a change to a transaction log’s integrity can be detected.

The Final Rule makes person or entity authentication a mandatory requirement without providing specifics. The Person or Entity Authentication standard does not specify use of any particular technology, allowing “covered entities to use whatever is reasonable and appropriate.”

Transmission Security is required in the Final Rule, which stipulates

The covered entity must implement technical security mechanisms to guard against unauthorized access to electronic protected health information that is transmitted over an electronic communication network.

The Transmission Security standard includes integrity controls to ensure that electronically transmitted PHI is not improperly modified. The standard also specifies encryption as a mechanism to protect electronic PHI being transmitted over open network such as the Internet. Both of these controls, integrity and encryption, are addressable implementation specifications and hence can be optional.

So, when considering HIPAA compliance, one will certainly need to address whether or not cryptographic controls are required ⁷⁴. Auditing a system for HIPAA compliance must take into account the basis for a decision when cryptographic controls are deemed unnecessary in meeting a HIPAA standard. In order to monitor cryptographic compliance for a system that processes, transmits, or stores data subject to HIPAA standards, these system-specific cryptography requirements must be defined.

International Privacy Laws

Not all industry or government regulations explicitly stipulate use of particular cryptographic controls such as encryption or digital signatures. Privacy laws, in particular, deal with confidentiality of data but generally do not stipulate that encryption be used as the means of control. Use of encryption to protect confidentiality is left to the detailed security requirements defined for a particular solution, based on the security risk present.

An example of a privacy law where confidentiality is required is Article 17 of the European Union Data Protection Directive [EU Data Protection] which states:

Member States shall provide that the controller must implement appropriate technical and organizational measures to protect personal data against accidental or unlawful destruction or accidental loss, alteration, unauthorized disclosure or access, in particular where the processing involves the transmission of data over a network, and against all other unlawful forms of processing⁷⁵.

Audit Readiness and Compliance

Audit readiness and compliance oversight must take into account the requirements for cryptographic controls when addressing cryptographic compliance. In general, the need for cryptographic compliance with industry and government regulations is dependent upon criticality of data and security risk. For a given solution, the business requirements, type of data, and how the data will be accessed stored and transmitted all contribute to the need for compliance with such standards. The security architect should be prepared to engage in an audit and explain complex systems, such as an organization’s implementation of PKI, and why specific design decisions were chosen.