Technical Questions about Digital ID Certificates
On this page:
- Who issues Digital ID Certificates and how?
- What is a key pair and how is it used?
- How are the keys associated with a Digital ID Certificate managed?
- Where does my computer store my private key?
- Who needs a key pair?
- What happens when a key expires?
- Should a public key or private key be shared among users?
- What is a message digest?
- What is a hash function?
- What are MD2, MD4, and MD5?
- Why are there multiple trust hierarchies?
- What is a Digital ID Certificate revocation list?
Who issues Digital ID Certificates and how?
Digital ID certificates are issued by a Certification Authority (CA), which can be any trusted central administration willing to vouch for the identities of those to whom it issues digital ID certificates. A company may issue digital ID certificates to its employees, a university to its students, a town to its citizens. In order to prevent forged digital ID certificates, the CA's public key must be trustworthy: a CA must either publicize its public key or provide a digital ID certificate from a higher level CA attesting to the validity of its public key. The latter solution gives rise to hierarchies of CAs.
Digital ID certificate issuance proceeds as follows: Alice generates her own key pair and sends the public key to an appropriate CA with some proof of her identification. The CA checks the identification and takes any other steps necessary to assure itself that the request really did come from Alice, and then sends her a digital ID certificate attesting to the binding between Alice and her public key, along with a hierarchy of digital ID certificates verifying the CA's public key. Alice can present this digital ID chain whenever desired in order to demonstrate the legitimacy of her public key.
Since the CA must check for proper identification, organizations will find it convenient to act as a CA for its own members and employees. There will also be CAs that issue digital ID certificates to unaffiliated individuals.
Different CAs may issue digital ID certificates with varying levels of identification requirements. One CA may insist on seeing a driver's license, another may want the digital ID certificate request form to be notarized, yet another may want fingerprints of anyone requesting a digital ID certificate. Each CA should publish its own identification requirements and standards, so that verifiers can attach the appropriate level of confidence in the certified name-key bindings.
An example of a digital ID-issuing protocol is Apple Computer's Open Collaborative Environment (AOCE). AOCE users can generate a key pair and then request and receive a digital ID certificate for the public key; the digital ID certificate request must be notarized.
What is a key pair and how is it used?
Rather than using the same key to both encrypt and decrypt the data, public key encryption uses a matched pair of encryption and decryption keys. Each key performs a one-way transformation on the data. Each key is the inverse function of the other; what one does, only the other can undo.
A Public Key is made publicly available by its owner, while the Private Key is kept secret. To send a private message, an author scrambles the message with the intended recipient's Public Key. Once so encrypted, the message can only be decoded with the recipient's Private Key.
Inversely, the user can also scramble data using their Private Key; in other words, key pairs work in either direction. This provides the basis for the "digital signature," for if the user can unscramble a message with someone's Public Key, the other user must have used their Private Key to scramble it in the first place. Since only the owner can utilize their own private key, the scrambled message becomes a kind of electronic signature -- a document that nobody else can produce.
A digital ID certificate binds an identity to a public key, assuring the identity of the person or entity who owns the public key and the associated private key.
How are the keys associated with a Digital ID Certificate managed?
Secure methods of key management are extremely important. In practice, most attacks on public-key systems will probably be aimed at the key management levels, rather than at the cryptographic algorithm itself.
Users must be able to securely obtain a key pair suited to their efficiency and security needs. There must be a way to look up other people's public keys and to publicize one's own key. Users must have confidence in the legitimacy of others' public keys; otherwise an intruder can either change public keys listed in a directory, or impersonate another user. Digital certificates provide this assurance and must not be forgeable, obtainable in a secure manner, and processed in such a way that an intruder cannot misuse them. Digital ID certificates must be issued in a secure way, impervious to attack.
If someone's private key is lost or compromised, others must be made aware of this, so that they will no longer encrypt messages under the invalid public key nor accept messages signed with the invalid private key. Users must be able to store their private keys securely, so that no intruder can find it, yet the keys must be readily accessible for legitimate use. Keys need to be valid only until a specified expiration date. The expiration date must be chosen properly and publicized securely.
Where does my computer store my private key?
Your private key is typically stored in encrypted format in a Preferences or Configuration file that can only be unlocked (decrypted) using your private key password. For example, for Netscape version 3.0 for Macintosh, it is stored in the Security sub-folder of the Netscape folder (in the Mac Preferences folder) in a file named "Key Database." Different programs may store your private key in different places.
Who needs a key pair?
Anyone who wants to sign messages or receive encrypted messages must have a key pair. Individuals might have more than one key. For example, you might have a key affiliated with your work and a separate key for personal use. Other entities will also have keys, including electronic entities such as modems, workstations, and printers, as well as organizational entities such as a corporate department, a hotel registration desk, or a university registrar's office.
What happens when a key expires?
In order to guard against a long-term factoring attack, every key must have an expiration date after which it is no longer valid. The time to expiration must therefore be much shorter than the expected factoring time, or equivalently, the key length must be long enough to make the chances of factoring before expiration extremely small. The validity period for a key pair may also depend on the circumstances in which the key will be used, although there will also be a standard period. The validity period, together with the value of the key and the estimated strength of an expected attacker, then determines the appropriate key size.
The expiration date of a key accompanies the public key in a digital ID certificate or a directory listing. The signature verification program should check for expiration and should not accept a message signed with an expired key. This means that when one's own key expires, everything signed with it will no longer be considered valid. Where it is important that a signed document be considered valid for a longer period of time, the document should be time-stamped.
After expiration, the user chooses a new key, which should be longer than the old key, perhaps by several digits, to reflect both the performance increase of computer hardware and any recent improvements in factoring algorithms. Recommended key length schedules will likely be published. A user may recertify a key that has expired, if it is sufficiently long and has not been compromised. The Certification Authority would then issue a new digital ID certificate for the same key, and all new signatures would point to the new digital ID certificate instead of the old certificate. However, the fact that computer hardware continues to improve argues for replacing expired keys with new, longer keys every few years. Key replacement enables one to take advantage of the hardware improvements to increase the security of the cryptosystem. Faster hardware has the effect of increasing security, perhaps vastly, but only if key lengths are increased regularly.
Should a public key or private key be shared among users?
In a public-key cryptosystem, each person should have a unique private key, in other words, a unique modulus and private exponent. The public exponent, on the other hand, can be common to a group of users without security being compromised. Some public exponents in common use today are 3 and 216+1; because these numbers are relatively small, the public-key operations (encryption and signature verification) are fast relative to the private key operations (decryption and signing). If one public exponent becomes a standard, software and hardware can be optimized for that value.
In public-key systems based on discrete logarithms, such as ElGamal, Diffie-Hellman, or DSS (Digital Signature Standard), it has often been suggested that a group of people should share a modulus. This would make breaking a key more attractive to an attacker, however, because one could break every key with only slightly more effort than it would take to break a single key. To an attacker, therefore, the average cost to break a key is much lower with a common modulus than if every key has a distinct modulus. Thus one should be very cautious about using a common modulus; if a common modulus is chosen, it should be very large.
What is a message digest?
A message digest concisely represents a longer message or document from which it was computed; one can think of a message digest as the "digital fingerprint" of a larger document. A message digest is used to create a digital signature that's unique to a particular document.
A message digest can be made public without revealing the contents of the document from which it derives. This is important in digital time-stamping, where, using hash functions, one can get a document time-stamped without revealing its contents to the time-stamping service.
What is a hash function?
A hash function is a computation that takes a variable-size input and returns a fixed-size string, which is called the hash value. One-way hash functions (hash functions that are hard to invert) are used to generate a message digest. Examples of well-known hash functions are MD4, MD5, and SHS (Secure Hash Standard).
Since the hash functions are faster than the signing functions, it is much more efficient to compute a digital signature using a document's message digest, which is small, than using the arbitrarily large document itself.
A hash function used for digital authentication must have certain properties that make it secure enough for cryptographic use. Specifically, it must be infeasible to find:
- A message that hashes to a given value
- Two distinct messages that hash to the same value
The ability to find a message hashing to a given value would enable an attacker to substitute a fake message for a real message that was signed. It would also enable someone to falsely disown a message by claiming that he or she actually signed a different message hashing to the same value, thus violating the non-repudiation property of digital signatures.
The ability to find two distinct messages hashing to the same value could enable an attack whereby someone is tricked into signing a message which hashes to the same value as another message with a quite different meaning. The digest must therefore be long enough to prevent an attacker from doing an exhaustive search for a collision. For example, if a hash function produces 100-bit strings, exhaustive search would take 2^100 attempts on average to match a given value, and approximately 2^50 attempts on average to find two inputs producing the same digest.
What are MD2, MD4, and MD5?
MD2, MD4 and MD5 (MD stands for Message Digest) are widely used hash functions designed by Ron Rivest specifically for cryptographic use. They produce 128-bit digests and there is no known attack faster than exhaustive search.
Why are there multiple trust hierarchies?
Several digital ID hierarchies (domains) have been established to ensure a common level of identity and confidence for all digital ID certificates within the domains. Two of the most popular domains, with thousands of existing customers, are the Commercial Hierarchy (digital ID certificates for users) and the Secure Server Hierarchy (digital ID certificates for specific servers used in Electronic Data Interchange and Electronic Commerce). Universities, corporations, and other entities may find it useful to establish their own hierarchies.
What is a Digital ID Certificate revocation list?
A Certificate Revocation List (CRL) is a list of digital ID certificates that have been revoked before their scheduled expiration date. There are several reasons why a certificate might need to be revoked and placed on a CRL. A certificate might have been compromised. A certificate might be used professionally by an individual for a company; for example, the official name associated with a certificate might be "Alice Avery, Vice President, Argo Corp." If Alice were fired, her company would not want her to be able to sign messages with that certificate and therefore the company would place the certificate on the CRL.
When verifying a signature, you can check the relevant CRL to make sure the signer's certificate has not been revoked if the signed document is important enough to justify the time it takes to perform this check.
Certification Authorities (CAs) maintained CRLs and provide information about revoked certificates originally certified by the CA. CRLs only list current certificate, since expired certificates should not be accepted in any case; when a revoked certificate is past its original expiration date it is removed from the CRL. Although CRLs are maintained in a distributed manner, there may be central repositories for CRLs, that is, sites on networks containing the latest CRLs from many organizations. An institution like a bank might want an in-house CRL repository to make CRL searches feasible on every transaction.