Last updated on February 13, 2003.


Technical Report

Implementation Problems on PKI

Japan Network Security Association

ISEC, Information Technology Promotion Agency, Japan

@

Executive Summery

We have recognized several implementation problems on PKI specifications.

We have studied both the conformity to each standard specification and the practical interoperability through various connection testings to each other. Through this process, we have found problems using the reference materials based on the original ITU/X.509 and its subset PKIX/RFC2459. This document describes these issues.

Table of Contents

1. Certificate Profile - Problems on DER Encoding
2. Certificate Profile - About comparison of DN
3. Certificate Profile - Problem of DirectoryString order
4. Certificate Profile - serialNumber
5. Certificate Profile - basicConstraints.cA
6. Certificate Profile - basicConstraints.pathLenConstraint
7. Certificate Profile - keyUsage
8. Certificate Profile - Problems on the extension which is not supported
9. Certificate Profile - Problems on policy control
10. Certificate Profile - Problems on CRL/ARL
11. Constructing the Authentication Path - Problems on {subject|suthority}KeyIdentifier
12. Certificate Profile - Problems on critical flags for each extensions
13. Revocation Validation - Problems on obtaining CRL
14. Consideration regarding CRL ret riving method
15. Certificate Validation - CRL Cashing
16. Certificate Validation - Problems on Handling Invalid CRL


1. Certificate Profile - Problems on DER Encoding

X.509 explicitly describes the necessity of DER encoding in order to enable unique signature validation constantly. (Refer to "6.1 Digital signatures" and "7 Public-keys and public-key certificates" in X.509)

RFC2459 also defines the necessity of DER encoding for signature validation.

However, some CAs used BER encoding. In this testings, KeyUsage extension was frequently used as shown bellow.

@

SEQUENCE {

OBJECT IDENTIFIER keyUsage (2 5 29 15)

(X.509 id-ce (2 5 29))

BOOLEAN TRUE

OCTET STRING, encapsulates {

BIT STRING 1 unused bits
'0000011'B
Error: Spurious zero bits in bitstring.

}

}

@

In DER encoding, unnecessary high level bits (Big-endian order is used in ASN.1) should be omitted (the default value is zero for BIT STRING) according to a), c) and g) aforementioned. (Refer to a), c) and g) on "6.1 Digital signatures" in X.509)

However, there is no such limitation in BER encoding, they could implement in the way described above. This will not make big difference since DER is a subset of BER, but it may cause a failure in signature validation.

Only the BOOLEAN value of each bit is checked in keyUsage, there may be little difference between DER and BER encodings. However, if the section, such as keyIdentifyer and DN that accept binary comparison, is BER encoded, it may cause a failure in the validation.


2. Certificate Profile - About comparison of DN

X. 520 defines DirectoryString used for a certificate's DN (issuer, subject). (Refer to "5 Definition of selected attribute type" in X.520)

RFC2459 also defines DirectoryString, similar to X.520. (Refer to "4.1.2.4 Issure" in RFC2459)

X.520 defines the method to compare Name attribute that identifies certificate to be case insensitive. (Refer to "5.2.1 Name" in X.520)

X.520 also defines in detail the method of string comparison. (Refer to "6.1 String matching rules" in X.520)

...

According to this rule, case of the string, white-space before and after the string, and the continuous white-spaces should be processed.

RFC2253 further defines about strings. (Refer to "2.4 Covering an Attribute Value from ASN.1 to a String" in X.520)

In the preliminary phase of this testing, we have found that the process for string comparison had some problems in certain applications.

The first problem is the comparison between UTF8String and PrintableString.

We could not use the certificate whose subject was encoded with UTF8String in a certain application.

There are few applications that implement UTF8String. even if an application implements UTF8String as an encoding type , it rarely implements the comparison logic described above correctly. This may derive from the difficulty of converting UTF8String to PrintableString. The method of decoding UTF8String has been discussing and the criteria of converting and/or comparison are defined in draft-ietf-ldapbis-dn-06.txt by the LDAPbisWG.

The second problem is the string comparison.

In the preliminary testing, an operation miss caused a case mismatch error between the subject of CA certificate and the issuer of EE certificate. In this case, we could not associate the CA certificate to the EE certificate in the application. This indicates that the application performed case-sensitive comparison between the strings.

Case mismatch errors seldom occurs in normal CA operations. However, it is useful to avoid this type of operation miss.

The third problem is the mixture of encoding types. This problem can be divided into two sub-problems. The first is the case where the encoding type between the issuer and the subject are different in the certificate issued by a single CA. This problem is very difficult to solve. When the subject is included in Certificate Request, it is not determined whether to use its encoding type.

For example, assume that a certain CA encodes DN with UTF8String. Which type of the encoding, UTF8String or Printable String, should the CA apply when it accepts CSR encoded with PrintableString? This problem occurs when a CA issues the certificate based on CSR.

The second is the case where encoding types of the issuers are not consistent in the certificates issued by a single CA. For example, one issuer is encoded with UTF8String while the other issuer is encoded with PrintableString. This indicates that the CA can not control the usage of the types of DN encoding.

The problem of DN encoding in issuing certificates belongs to CA while the problem of string comparison belongs to the application.

Currently we recognize that the both sides have some problems that make us reconsider the difficulty to use different types of encoding for connection among multiple domains.


3. Certificate Profile - Problem of DirectoryString order

X.501 defines DirectoryString. (Refer to "9.2 Naming in General" in X.501.)

RFC2253 also defines DirectoryString. (Refer to "2.1 Converting the RDNSequence" in RFC2253.)

In the both definitions, SEQUENCE elements are listed in descending order separated by a comma, starting with the last one first and ending the first one last. On the other hand, RFC1779 defines DirectoryString. (Refer to "2.3 Formal definition" in RFC1779.)

In this testing, we have found two patterns for the arrangement order of DirectoryString and the order of SEQUENCE in ASN.1 is reversed at each pattern.

Basically, each CA issues the certificate with one of the patterns. But some CAs issued the certificate with the same SEQUENCE that of PKCS#10 subject when they received Certificate Request in PKCS#10 format. This caused the difference of the arrangement order between DN and DirectoryString of CA itself. As a result, arrangement patterns on the issuer and the subject were made in reverse order.

The column pattern (a) for DirectoryName

@

SEQUENCE {

SET {

SEQUENCE {

OBJECT IDENTIFIER countryName (2 5 4 6)
(X.520 id-at (2 5 4))
PrintableString eJPf

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER organizationName (2 5 4 10)
(X.520 id-at (2 5 4))
PrintableString eJNSAf

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER organizationalUnitName (2 5 4 11)
(X.520 id-at (2 5 4))
PrintableString eChallengePKI2001f

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER organizationalUnitName (2 5 4 11)
(X.520 id-at (2 5 4))
PrintableString ealicef

}

}

}

@

The column pattern (b) for DirectoryName

@

SEQUENCE {

SET {

SEQUENCE {

OBJECT IDENTIFIER organizationalUnitName (2 5 4 11)
(X.520 id-at (2 5 4))
PrintableString 'alice'

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER organizationalUnitName (2 5 4 11)
(X.520 id-at (2 5 4))
PrintableString 'ChallengePKI2001'

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER organizationName (2 5 4 10)
(X.520 id-at (2 5 4))
PrintableString 'JNSA'

}

}
SET {

SEQUENCE {

OBJECT IDENTIFIER countryName (2 5 4 6)
(X.520 id-at (2 5 4))
PrintableString 'JP'

}

}

}

@

Judging from X.501, RFC1779, and RFC2253, it is correct to combine the notation such as "ou=alice, ou=ChallengePKI2001, o=JNSA, c=JP" with the method in pattern (a).

The order of DirectoryString is described in documents related to the directory server such as X.500 and LDAP instead of documents that are directly related to PKI. This fact makes the implementation of the arrangement order vary among systems. X.509 was inherited originally from X.500, and evolved to be able to implement independently from X.509. We think that this evolution of X.509 may bring these situations.

On the other hand, saving the subject included in Certificate Request directly into the certificate itself is related tightly not only with the order of DirectoryString in this section but also with the type of encoding described in the previous section.

This means how far we respect the content written in Certificate Request as for the subject that is described in the certificate.

The easiest implementation is to transfer it to the certificate as a subject without validating the subject in PKCS#10.

Although this is an attractive approach for a CA that has no limitation with a subject, it may cause inconsistencies in DirectoryString order among certificates that were issued by a single CA or poor validations of encoding in a subject.

If you have enough knowledge about the relevance between X.500 and X.509 and the difference among various encoding types, these problems will not occur. It is important to understand the system of each specification and mutual connection.


4. Certificate Profile - serialNumber

X.509 and RFC2459 define serialNumber only to be INTEGER, without any other limitations.

X.680 defines this INTEGER in ASN.1. According to this description, detailed definitions such as a limitation of length should be defined by each system, apart from the ASN.1 rule. (Refer to "3.8.40 integer type" in X.680)

Some CAs used very large integer value (more than 32 bits) as a serialNumber, and they could not display the correct value in their applications. Fortunately a serialNumber for a certificate is used for collation with Certificate Revocation List to validate revocation and has no need to be compared its value, therefore, there is a little affection to applications and validations with certificates. But, however, if the serialNumberRange field will be used in the cRLScope extension area in a future version, we should consider about its affection. Like serialNumber, using a type that has no definition about its size may cause implementation risks such as BufferOverflow.


5. Certificate Profile - basicConstraints.cA

X.509 defines basicConstraints extension to be the extension that determines the validation of CA certificate for issuing certificate. (Refer to "8.4.2.1 Basic constraints extension" in X.509)

RFC2459 also defines basicConsraints as the extension to verify CA certificate.. But it also strictly defines that this extension should not be included in EE certification. (Refer to "4.2.1.10 Basic Constraints" in RFC2459.)

In this testing, many CAs do not include basicConstraints in EE certificate, but there are some CAs that include the formula, "basicConstraints = FALSE", explicitly in EE certificate.

BasicConstraints should not be included in certificates other than CA certificate in order to conform to both X.509 and RFC2459 criteria.

A purpose of the extension itself might not be to distinguish between CA and EE, but to describe the basic constraints to be a CA.

Therefore, the concept in RFC2459 indicating that the extension should not be included into EE certificate is considered to be more strict and false-positive.

NOTE: The length of serialNumber is newly defined as 20 octets in RFC3280.


6. Certificate Profile - basicConstraints.pathLenConstraint

X.509 defines that this field is valid only if cA flag is set to TRUE. The value 0 indicates that the certification path cannot be lengthened (only EE certificate is allowed to follow).If you do not want to limit the length of a path, you should not include this field. (Refer to "8.4.2.1 Basic constraints extension" in X.509)

If pathLenConstraint is 0, the following path MAY be an EE certificate. On the other hand, if a value is not set to pathLenConstraint, no limit might exist for the length of a path.

pathLenConstraint is enabled when CA is set to TRUE. Definitions in both X.509 and RFC2459 are the same at this point.

basicConstraints extension without pathLenConstraint could not be written in some CAs. In this case, a limited valued should be set since the path length cannot be specified explicitly in pathLenConsraint. There was no actual constraint in this testing, by setting more than adequate value to the path length

The specification itself which needs pathLength is valid as a specification for issuing certificates.

But in the actual operation of issuing certificates, this certification requires to estimate how long a path will extend until the validity of CA certificate expires. Considering about the validity of CA, it is not a practical implementation.


7. Certificate Profile - keyUsage

X.509 defines that digitalSignature must be set in KeyUsage which is used for verifying digital signatures. So when you want to sign with private key, digitalSignature must be set in the public key certificate.

When the symmetric key encryption is performed after authentication with public key encryption as SSL/TLS, keyEncipherment must be set in keyUsage. (Refer to "8.2.2.3 Key usage extension" in X.509)

RFC2459 also defines similar specifications and tells that this extension should be critical.

In applications used in this testing, the certificate where only the bit for digital signature is set can not only be encrypted but also be registered to the application as a certificate for encryption.

In this testing, there where applications where only the bit for digital signature was set. In those applications, we could neither encrypt the certificate nor register it to the application as the certificate which is used for encryption.

On the other hand, RFC2459 tells that critical-flag should be critical, but some CAs have issued certificates whose keyUsages are remained as non-critical. In this situation, the application shown above still worked correctly for key usage.

The meaning of the existence of critical-flag depends on whether it is able to interpret its extension without ignoring it. We have confirmed that applications that have no critical-flag can work correctly as the application with a critical-flag.


8. Certificate Profile - Problems on the extension which is not supported

We have designed the certificate profile which is used in this testing by considering the requirement for extension in each verification and researching each CA's capability. But there are some features that are not implemented actually since it is difficult for all CAs to support all the extensions necessary for testing.


9. Certificate Profile - Problems on policy control

Some CAs did not support extensions relating to the certificate policy;

Some CAs can issue certificates but the critical-flags are not set to critical.

This may be because the critical-flag is not essential in a single domain operation. As the critical flag is essential to identify other domains, it is important to support the critical flag when connecting to other domains.

We performed exceptional settings for these CAs to authenticate with each other in this testing.


10. Certificate Profile - Problems on CRL/ARL

We have found some CAs which do not support extensions about CRL/ARL.

Especially authorityKeyIdentifire and issuingDistributionPoin are not supported because of the same reason above, they are not essential in a single domain operation.

These extensions are not designed only for interoperability with other domains. They are very useful in a single domain.

Features about CRL/ARL are not designed enough to use efficiently. Especially there are a few CAs that implement issuing CRL and ARL independently. We have found that it is difficult to configure the domain which use plural CAs regardless of the number of vendors.


11. Constructing the Authentication Path - Problems on {subject|suthority}KeyIdentifier

Descriptions of each standard specifications, such as RFC2459, X.509.

X.509 takes the following assumptions about key Identifier. (Refer to "8.2.2.1 Authority key identifier extension" in X.509.)

a) Consistency should exist between CRL issuer and certificate issuer

b) key identifier can be used to construct the path

RFC2459 describes two examples about keyIdentifier hash calculation (160bitSHA-1 and 60bit SHA-a) as for Recommendations. (Refer to "4.2.1.2 Subject Key Identifier" in RFC2459.)

Many venders implement (1) 160bit SHA-1 of FRC2459 mentioned above to generate hash values, some other venders take different formulas to calculate hash.

This difference forced some applications that use keyIidentifier as for path construction not being about to construct the path.

The method above is only for recommendations. The minimum specification requires that the calculation method for keyIdentifier hash is consistent throughout a single CA.

At the beginning we expected that the only one identifier for constructing the authentication path could be keyIdentifier. However, this conformity signifies that we need a common hash calculation that can be used all over the world.

We do not think that this approach is appropriate now. Because we need an announcement for the common hash calculation to the whole world all at once if we change hash algorithm for some reason in the future. This is not practical at all.

If the conformity of keyIidentifier is indispensable, it decreases the interoperability.

Among these circumstances, we should consider what can be a clue for an validater to construct the path.


12. Certificate Profile - Problems on critical flags for each extensions

X.509 explicitly defines that the validation engine should reject the certificate if it cannot understand the critical extension. (Refer to "7 Public-keys and public-key certificates" in X.509.)

RFC2459 also describes similar processings, in which it explicitly defines some extensions that must be processed.

(Refer to "4.2 Standard Certificate Extensions" in RFC2459.)

In this testing, some certificates set keyUsage and basicConstraints to be non-critical by mistake.

However, it was processed correctly in applications.

Checking this process with the RFC2459 rule, this behavior is correct.

Yet we found some problems. For example, some applications processed keyUsage, and this could be due to the case that they had known how to process keyUsage as shown aforementioned RFC2459.

....Let's think about the reason why keyUsage to be critical.

The applications (in conformity to RFC2459) we used in this testing could process keyUsage even though they were non-critical.

Even if the application had not process keyUsage and the keyUsage showed only digitalSignature, they could be used as certificates for SSL authentication.

On the other hand, if the keyUsage is critical, the applications that cannot process keyUsage might not handle the certificate. They can be used for neither digital signature nor malicious SSL authentication.

The critical flag may be for the part of "Do not use the certificate in disregard of the items that are described in this extension".


13. Revocation Validation - Problems on obtaining CRL

Only CRL model was checked in this testing and OCSP model was excluded. Thus we call it a revocation list, explicitly combine CRL and ARL.

X.509 defines how to obtain revocation list in detail. There are various methods of distributing revocation information only for CRL. Hence here we only consider the directly related parts to this testing.

Please refer to X.509 for further information ("8.6.2.1 CRL distribution points extension", "8.6.2.2 Issuing distribution point extension", and "Annex B CRL Generation and Processing Rules" in X.509.).


14. Consideration regarding CRL ret riving method

We have examined how to get CRL according to the specifications described above;

a) When the target certificate has a cRLDistributionPoint extension

a-1) When the value of distributionPoint.fullName is directoryName

The application should know how to access its repository (such as host name and IP address) without its certificate (for example, by using the format of setting files).

Then the application has to query certificateRevocation List attribute or authorityRevocationList attribute of the directoryName entry and get the attribute value.

a-2) When the value of distributionPoint.fullName is URI

The application should access to the URI.

To do this, the application has to recognize the scheme of URL. The scheme is HTTP or LDAP in most cases.

b) When the target certificate does not has a cRLDistributionPoint extension

The application should access to the issuer of the target certificate. Therefore, the application has to know how to access its repository in the same way as a)-1).

Then the application has to query certificateRevocation List attribute or authorityRevocationList attribute of its issuer's entry and get the attribute value.

In both cases, which attribute, certificateRevocationList attribute or authorityRevocationList attribute, the application should get from the directory depends on the ca flag or a issuingDistributionPoint extension.

The applications used in this testing can not know the directory servers because they do not have the item that sets the access method to the repository). Therefore, the applications should describe CRLDP with URI format.

The applications can recognize both LDAP and HTTP.

We have found that the application varies its function according to whether it could get CPL online based on the information of CRLDP.

If the application gets CRL based on the information described in CRLDP, it validates the certificate revocation. This indicates that the application can perform the online validation of certificate revocation.. On the other hand, if CRLDP is not included in the target certificate, the application gets CRL and installs it. This indicates that the application can not perform the online validation of certificate revocation.

The above example implies that the way to get CRL affects the result of validation. The application requires explicitly to the CA for the mechanism of providing the certificate revocation information. This will be a good decision for the application that can only get CRL with cRLDistributionPoints.


15. Certificate Validation - CRL Cashing

Though certificate validation should be performed based on the latest information at that moment, it is necessary to consider clients that can not refer to the latest information. The item called nextUpdate is provided in CRL for this purpose. Clients are allowed to use this CRL until the date that is specified in nextUpdate.

An Application can have CRL as local cache based on this specification. Although this is allowed in both X.509 and RFC2459, using cache is passively permitted. (Refer to "Annex B.1.2 CRL processing" in X.509, and "3.1 X.509 Version 3 Certificate" in RFC2459)

It is also necessary to consider how to update cached CRL.

When the application finds cached CRL that is out of date during the certificate validation, it gets CRL based on the items (ex. cRLDistributionPoints extension) described in the certificate. But in the environment where the application can not get validation information such as CRL on-demand, the application may update cache regardless of requirements for validation or cache at the moment it establishes the network connection, for example.

In this case, CRL should only be cached based on the information described in itself. To do this, it is a good way to keep distributionPoint in issuingDistributionPoint.

In every application used in this testing, the CRL that is not overwritten when the due date in nextUpdate is expired and its cache is not cleared.

Although this is an irregular specification, it may be worth considering as well as the way to get CRL mentioned above.

However, viewing from the application design, installing CRL manually my be illegal. In the design of this application, CRL installed manually may be treated as the static value.

This design is similar to the concept of offline ARL.

This is the concept for CRL issued by route CA that issues subordinate CA certificates. Few subordinate CA certificates are listed on CRL issued by the route CA. Therefore, the Route CA sets a too long duration to nextUpdate. It is called offline ARL.

The merit of this practice is to reduce workload for maintaining CA to update CRL which seldom changes.


16. Certificate Validation - Problems on Handling Invalid CRL

X.509 defines the validity check on CRL (Refer to "B.5.3 Validating and currency checks on the base CRL" in X.509.)

....

RFC2459 defines that the critical extension of issuingDistributionPoint is not required to support (Refer to "5.2.5 Issuing Distribution Point). This definition is remained in draft-ietf-pkix-new-part1-12.txt, the revised draft of RFC2459.

In this testing, we have found some behaviors about public keys in CRL and validity duration as a side effect of some errors such as an operation miss. As for validity duration, we have confirmed that validity is checked on both this Update and nextUpdate. The CRL that has invalid validity is not used as appropriate information for validation. The CRL which has the same issue but is signed with the other secret key is not used neither.

One application checked in this testing does not use CRL that has critical extension of issuingDistributionPoin.

On the other hand, when the application gets invalid CRL, it does not inform that the CRL is invalid. We have to discuss on this point. Neither X.509 nor RFC2459 defines the way of error handling when invalid information is included in validation failure or in validation information.

This may be a major factor to make behaviors vary at application level.

For example, we have to consider two types of validation failures, one occurs when the target certificate is actually expired and, and the other occurs when enough information for validation is not provided.

An application may inform the reason why the validation fails to the user. If the reason is the latter one described above, target certificate may not be expired and there may be a trouble in the authentication path. In this case, retrying make the validation succeed.

If the application informs the fact without any reasons to the user, what will happen?

E-commerce with large amount of money could be failed by an unexpected trouble in the authentication path. This is the typical trouble when connecting domains each other. In a single domain environment, information needed for constructing the authentication path is gathered in the limited resources (such as domain repository), it is easy to detect the trouble and inform it to the user immediately. On the other hand, in the environment where many domains are connected each other, it is very difficult to inform the trouble immediately to all the users and it is also difficult to detect a trouble that has occurred at other domain on real time.

Considering these issues, we have to improve the validation engine used in the single domain environment when using it in the environment where many domains are connected each other.