ICSA Guide to Cryptography Randall Nichols  $69.95  0-07-913759-8
Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10

CHAPTER 10

DIGITAL SIGNATURES

Introduction

Digital signatures are a result of the computer and its influence in our daily lives. Digital signatures can be generated very quickly and can bind a document to its owner to help authenticate the message. The National Institute of Standards and Technology (NIST) defines the Digital Signature Standard (DSS) as a cryptographic method for authenticating the identity of the sender of an electronic communication and for authenticating the integrity of the data contained in that communication. The public-key system was intended for all Federal departments and agencies in the protection of unclassified information. NIST had intended to use the de facto international standard RSA algorithm as their standard for digital signatures. The RSA algorithm is a public-key algorithm that supports a variable key length and variable block size of the text to be encrypted. Public-Key Cryptography Standard (PKCS) & PKCS # 1-12 was RSA's attempt to provide a standard interface for public-key cryptography. PKCS # 1 is the RSA public-key cryptography standard, which defines the method of encrypting and signing data using RSA's public-key cryptosystem. PKCS # 1 describes syntax identical to that of PEM and X.509 for RSA public/private-keys and three signature algorithms for signing certificates.

The ability to "crack" an encrypted message is a function of the key length. The National Security Agency (NSA) insisting on a weaker algorithm, opposed NIST on their RSA choice and along with the FBI put NIST under intense pressure to accept the NSA proposal. The NSA proposed algorithm did not meet the NIST request for secure key exchange in confidential unclassified communications. When all was said and done, NIST publicly proposed the DSS developed by the NSA in August 1991 for unclassified information. DSS approval was announced by the Department of Commerce (DOC) on May 19, 1994 as Federal Information Processing Standard (FIPS) 186, effective December 1, 1994.

What Is A Digital Signature?

A digital signature is an electronic method of signing an electronic document that is reliable, convenient, and secure. An electronic document includes any instrument created or stored on a computer. These include e-mail, letters, contracts, and images. Many states are enacting legislation concerning the use of digital signatures. The most widely used type of electronic signature relies on public/private-key encryption. This asymmetric cryptosystem key pair technology has been available for nearly 20 years. A public/private-key encryption system involves two mathematically related keys that are like large passwords for each user. The private-key, known only by the "signer", can encrypt a message that only their public-key can decrypt. Once the private/public-keys are generated using a valid Certificate Authority (CA), they remain associated with the person who generates the two keys. The certificate authority is a trusted entity that issues certificates to end entities and other CA’s. CA’s also issue Certificate Revocation Lists (CRL) periodically, and post certificates and CRL’s to a database or repository.

Figure 10-1 shows the components of ordinary digital signature schemes. In Figure 10-1, components in the strict sense are the algorithms gen, sign, and test. Gen and sign are probabilistic. The main security requirement on an ordinary digital signature scheme is that one cannot forge signatures although one knows the public key. A necessary but not sufficient condition for this is that one cannot compute the secret key from the public key. Such a scheme can never be information-theoretically, i.e. perfectly, secure. For practicality, there must be an upper bound on the length of the signatures produced with signing keys and messages of a certain length. The security of such digital signature schemes is computational. A consequence of computational security is that signature schemes usually depend on a so-called security parameter, which determines the length of the problem instances that are supposed to be infeasible. Choosing a larger security parameter usually makes keys and signatures longer, and signing and testing more time-consuming. One hopes that it also makes forging signatures significantly more difficult even more quickly, so that the gap between the complexities of the legal algorithms (gen, sign, and test) and of forging widens.

>>INSERT FIGURE 10-1 HERE<<

The public-key can be distributed freely to anyone the public-key owner wishes to communicate with securely. The public-key can not derive the attributes of the

private-key although they are related. The private-key is derived using the asymmetric encryption algorithm providing message origination authentication and non-repudiation. One of the not commonly known features of the private and public-key is that data encrypted by one key can be decrypted by the other.

Second, the sender signs the message using their private-key. This digitally signed message is then sent to the recipient. The recipient generates the message hash from the message itself and then the message is verified using the sender's public-key, which was in the recipient's possession before the message transmission. If the two message hashes are the same, the message can be viewed as genuine and authentic. If the hashes do not match, the message is corrupted or a forgery. An important thing to remember is that the message can still be in clear text. Digital certificates only validate the message origination and integrity.

Signing denotes the process of applying a digital signature to some message or data. This works by appending organizational data to the message and optionally transforming the message so that it will pass mail transfer agents unmodified. Any further change to the contents of the message results in digital signature being corrupted. The recipient can detect this using the sender's public-key. Although the message data may look unreadable after the transfer encoding, there is actually no protection against eavesdropping at this point. The message is just encoded and NOT encrypted.

When the message is intended for recipients, who might not have a compatible system available, any recipient can actually look at the message and read it, although they will not be able to properly verify the signature. The recipient should treat the message with the same caution that he would normally extend to any non-signed messages.

Encryption renders the message unreadable to anyone but the intended recipients. This means that in order to create an encrypted message a set of recipients must be chosen.

This works by selecting a number of aliases from the user’s database. Based on the alias, the program looks up the corresponding certificate in the database and uses their public-key to encrypt the message session key.

Decryption is the reception of a message and the removal of security features. This process is also called the de-enhancement of a message. Where a message is not actually encrypted and only signed, the process is usually just called signature verification. A message should be considered untrustworthy should any steps fail.

Automatic addition of new certificates to the user’s database can be a good feature. Whenever a message is received from an unknown sender. The certificate (which must be embedded in the message for this to work) is checked in the context of the user’s certification hierarchy. If the check is successful, then the message is considered trustworthy and the new certificate can be automatically added to the database.

An alias name can be determined automatically or it can be specified explicitly before the decryption operation is run. When the alias name is determined automatically, a certain sub-component of the distinguished name of the owner of the new certificate is taken.

Once the sender of the message has been put into the user’s database with an alias, messages can be encrypted to this user by selecting the alias. To distribute one’s own certificate, it is appropriate to distribute signed (but not encrypted) messages.

After a message has been decrypted successfully, (i.e. its digital signature has been verified), the so-called certification path is displayed. This certification path, starting with the details of the sender’s certificate, up to and including the root self-signed certificate, can be used to further check the trustworthiness of the message by inspection.

A digital signature should be time stamped to allow the recipient to see when the transaction transpired and to allow the signer the ability invalidate and terminate the digital signature if it were to be compromised.

Certificates

A certificate is a digitally signed data structure defined in the X.509 standard that binds the identity of a certificate holder to their public-key. X.509 is the X.500 directory service standard relevant to public-key infrastructures describing two authentication methods: simple authentication based on password usage and strong authentication based on public-key cryptography. Version 3 added certificate extensions to the X.509 standard.

This standard is relevant to public-key cryptographic infrastructures defining two methods of authentication. Standard authentication relies on password usage and strong authentication is based on public-key cryptography. The operational period of a certificate should be directly linked to the confidentiality and security required. We can look at the use and rules applied to passwords to draw a comparison. The life expectancy of a password is defined in the organization's security policy. As a simple rule of thumb, the more security that is required, the more often it will need to be changed. This will probably be the same for a digital signature certificate. Administrators have learned to expect the worst case when it comes to their users. They will expect that the user may compromise their private-key and as a precaution use key expiration dates to maintain a tight control on security.

The public-key certificate must be obtained to verify a digital signature. A public-key has no identifier with a private-key or person. It is only a string of numbers. This adds to the complexity of the transaction. Each recipient must obtain the signer's public-key in order to verify the message. To insure that each recipient is identified with a particular key pair, a third party that is trusted by both recipients must associate a person to a key pair. This trusted third party is called the 'certification authority'.

Before users can actually sign documents or to encrypt messages, the user must create their key database. When creating this database: an asymmetric key pair is created, the public-key is put in a self-signed certificate, and the certificate and Certificate Revocation List are initialized.

From a cryptographic point of view, the key pair generation is the most important step in this process. Once the database has been created, the user name cannot be changed anymore. If a new database is required, it must be done with a new key.

In a strong cryptosystem, each newly encrypted message is encrypted with a pseudo-randomly generated key, the length of which depends on the selected symmetric encryption algorithm. The randomness of a session key generation is the center of a cryptographically strong one-way hash function.

Certification hierarchies, certificate chains, and the certificate revocation list are what make the asymmetric cryptosystems so powerful. In order to participate in such a hierarchy, any user must obtain a certificate for his public-key. This is achieved by creating and sending a certification request to the user’s certification authority, which in turn creates a proper certificate that is embedded in a certification reply message, which is sent back. This reply is then loaded by the user. The user then becomes a member of the certification hierarchy. The certification process has to be executed only once after the key pair has been generated. A certification request is like a message that only bears a digital signature. The difference is that the message is signed with the user’s newly created private-key, which is not yet certified. To all other users in the system this would be a non-trusted message (since the user’s key is not properly certified yet), but the certification authority detects this as the intended means to forward certification requests. The contents of the certification request’s text data is irrelevant, it can be empty. It is not possible for the user who creates the request to check the signature himself. This check will only be possible after the certification process has been completed.

For each enrolled user, a separate database is maintained. In this database, the (protected) user’s key pair is stored along with the certificates from other users that the user has loaded over time. A database view lets a user look at the database. It lists all certificates stored in the database that have an alias. It is these certificates that are used to send encrypted messages to the respective certificate owners. Certificates can be stored in a database without an alias. These certificates may belong to intermediate certification authorities. These certificates are only used to verify certificate chains, but not to encrypt messages intended for the certification authority. A display of the trust status of the certificates may be misleading. Certificates can be stored in the database as ‘non-trusted’, with the trust only established on demand when sending a message to this recipient or when verifying a signature, which was done with the appropriate public-key. Any certificate in the database that has an alias can be deleted. Certificates should be deleted one by one. There will be certificates in the database that do not have an alias. Generally, these certificates should not be removed from the database.

The input data selected (file or clipboard contents) are hashed with the hash algorithm and the result is displayed. Since neither access to the private-key, neither the public-key nor the user’s database is required, this function can be executed freely. A hash value can be used to check the unmodified transmission of otherwise unprotected data. This is especially suitable to check the correct reception of the certification reply message. This message must not have been tampered with during transit. This is a suitable means to verify that the hash value computed at the sender’s side is identical to the one computed on the recipient’s side. The reference hash value must be transmitted via a different communication method and should be well protected against manipulation. It does not need to be secret. These values are small and it could be read over the telephone or faxed. The exact way method the certification reply is protected against manipulation should be defined in the security policy.

Cryptographic hash functions originally required for email were MD2 and MD5. MD5 is a hashing technique that creates a 128-bit message digest. SHA-1 is the Secure Hash Algorithm designed by NIST and NSA to be used with the DSS to ensure the security of the Digital Signature Algorithm (DSA).

More advanced hashing methods are SHA-1 and RIPEMD-160. Using one of the latter two algorithms is recommended. The security of these algorithms is much better than that of MD2 and MD5. A hash function is used to: specify which hash algorithm is used when signing messages, specify which hash is used inside the certificate when creating the user’s self-signed certificate, specify which hash is used inside the certificate when creating a certification reply, specify which hash is used inside Certificate Revocation List (CRL) and compute the hash value of data. The certificate revocation list is a list of revoked but unexpired certificates issued by a CA.

Institutional overhead is the costs associated with establishing and maintaining a Certificate Authority service center whether it is kept in-house or outsourced. This cost includes professional accreditation, government compliance, auditing, and any legal and financial liabilities that may arise from any errors, omissions, or negligence. Distributed Key Administration is one way to spread the costs, control, and work load of key distribution and management system back into the organization. Establishing subordinate certificate authorities throughout an organization may be viewed as a weak point in the security policy.

Attacks on Digital Signatures

Implicitly, one assumes the following problem: Given the public key and a message, find the corresponding signature. Is it possible that some schemes that seem infeasible to break are vulnerable if one allows stronger attacks and weaker forms of success?

The most important types of attacks, in order of increasing strength, are:

1. Key-only attack: The only information the attacker has to work on is the public key.
2. Known-message attack or a general passive attack: The attacker is given the public key and some signed messages.
3. Chosen plain text or active attack: The attacker can choose some messages that the signer will sign for him before he must forge a signature on another message on his own. In the general case of this attack, the attacker can choose those messages at any time. In effect, he can adapt or apply an adaptive chosen-message attack.

The most important types of success, in decreasing order, are:

1. Total break: The attacker has found the secret key, or the equivalent way of constructing signatures on arbitrary messages efficiently.
2. Selective forgery: The attacker has forged the signature on a message that he could select independently of the public key and before a possible active attack.
3. Existential forgery: The attacker has forged the signature on a message that the signer has not signed, but the attacker could choose what message (or plain text).

Problems

The Rabin and Williams schemes were both examples of weaker forms of breaking. Both are similar to RSA, but constructed so that selective forgery with a passive attack was as hard as the integer factorization problem (IFP). An active attack on these schemes was shown to yield a total break. Rabin devised a signature-like scheme that an attacker with limited resources could find two messages with the same signature, so that by asking the signer to sign one of them, he also obtained a signature on the other.

These attacks were not really noticed until similar attacks were made on RSA. The first attack used the secret RSA operation as a homomorphism. By multiplying the signatures

on two messages m1 and m2, one obtains the signature on the product m1 x m2. Thus if the attacker breaks his message into two factors and gets the signer to sign those, he can derive the signature on the chosen message (plain text). Another researcher used a little trickery and reduced the attackers requirement for two sets of chosen plain text for signature. These are selective forgeries after chosen plain text attacks, or alternatively, exsistential forgeries after known plain text attacks.

Existential forgery is possible with a key-only attack in all signature schemes built from the trap-door one-way permutations decribed in Chapter 7. The attacker chooses a value and calls it a signature, computes the permutation with a public key, and calls the result a message. The El-Gamal scheme was introduced in Chapter 8. Although similar to RSA, it is not directly constructed from trap door one way permutations. Existential forgery is possible with key-only attack. However, no method for selective forgery with an active attack is known.

Assessment of Attacks and Success

A known plain text attack is perfectly realistic. Historically, it has been one of the more successful forms on all types of ciphers. A completely unrestricted adaptive chosen message attack is not. If the signer signed arbitrary messages, there would be no need for forgery. It is reasonable to consider restricted forms of active attacks in practice. Every recipient will have some influence on what messages are signed, and perhaps determines the message almost completely. An example is a notary public whom signs almost everything.

As to types of success, a scheme where selective forgery is possible can not be used in practice. Existential forgery may not always be harmful, because the signed message may have no practical value to the attacker. Many of the PGP signed e-mail messages qualify. One does not know what will be of practical value in all applications of digital signature schemes. This is particularly true if data without inherent redundancy are signed. Hence to be on the safe side, every signed message is assumed to be valuable.

Countermeasures

There are two ad-hoc measures against the aforementioned problems.

One is to add redundancy to messages before signing. In this case, only messages that fulfil a certain predicate are signed; this makes the chosen plain text attacks more complicated. Furthermore, a signature is only valid if the message fulfils the predicate; thus, existential forgery in the original scheme seems unlikely (highly improbable) to yield a valid message.

The second measure is to apply a one way hash function to the messages before they are signed. In this case, it is unlikely that an attacker can find messages for a chosen plain text attack where the hash values actually signed are useful to him. An existential forgery in the original scheme should yield a message whose preimage under the hash function is not known. Applying a hash function has the additional advantage that it makes the complete scheme more efficient, if the hash function is fast; which is one of the original system design parameters.

The choice of good redundancy predicates or hash functions is not easy, especially if one wants to execute a fast hash algorithm. There are significant differences in symmetrical cryptologic schemes like DES and an IFP.

Provably Secure Digital Signature Schemes

Research on proving the security of signature schemes centers on two steps in the process. The first step was to recognize that redundancy or hash functions are not some protocol around a real signature scheme. Instead, the signature scheme must comprise everything that happens within a message, and security must be proved for the complete scheme. A second step was to formalize not only as the unfeasibility of computing the inverse of a function. Instead, the definition must comprise an active attack and exclude existential forgery. Goldwasser accomplished this in his research in 1988. The result was known as the GMR definition. Basically a signature scheme such as that portrayed in Figure 10-1 is defined as a collection of algorithms gen, sign, and test, such that, when the keys are corectly generated with gen , two properties hold:

1. Signatures correctly generated with sign pass the corresponding test.
2. If any polynomial-time attacker first communicates with a signer for a while, and then tries to compute a pair of new message and a signature, the success probability is very small. During the key generation, the maximum number of messages to be signed must be fixed, and sign takes the number of messages as input.

Both properties portend cryptographically strong schemes. GMR is discussed in the literature and reference to it can be found in resources section.

Trusting Digital Signed Documents

A digital signature is reliable when it has been issued by a trusted Certificate Authority (CA), authenticates the sender, guarantees the message integrity, and non-repudiation of the message. A weakness and major concern of using digital signatures involves the notion that digital signatures can properly assure a person's identification over the Internet or some other non-present situation. Digital signatures alone can not identify people. Digital signatures can only assure the recipient that a particular identification process was completed. Likewise, a manual signature not witnessed or notarized can not assure the recipient that the sender was truly the person who signed the document. In fact, a digital signature may have been stolen, or compromised in some way, without the owner even being aware of its theft. Security experts have been essential in defining and detecting the security system holes that digital signatures have created.

Fraud can take place in many ways. On site, a thief can simply use your computer and send a signed message, with your digital signature, without you even being present. They only need to access your computer, maybe an ability to bypass your password, create and send the email, delete the item from the out box, and power the unit down with no one the wiser. Digital signatures require strong security policies in order to be used as a viable method of conducting electronic business.

Other Methods

Biometrics includes fingerprints, iris scans, retinal scans, digitally captured handwriting, speech, DNA, or any digital information, which can be linked to a specific person's biological information. These items have the ability to scientifically separate them from anyone else and are considered the most secure mechanism for authentication. The next method is two-factor authentication. Two-factor authentication involves something I have in my possession in conjunction with something I know. These can be smart cards with encrypted data on the chip and personal identification numbers (PINs), proximity badges that require PINs, or tokens with pins to unlock them in order to operate. The least secure are the single factor authentication devices we use today. The most common of which is the everyday credit card we use to make purchases from a variety of merchants.

The U.S. Government Position

Politicians have added their mark on digital signatures with the Electronic Financial Services Efficiency Act (EFSEA) of 1997 and H.R.2937. The EFSEA promotes industry to establish a uniform digital signature system and other forms of authentication that will be an alternative to existing paper-based methods. A popular position is that "the federal government encourage the private sector development of uniform standards for electronic authentication, while not imposing rigid rules that may stifle innovation." H.R. 2937 establishes a self-regulatory agency and a mandatory registration of all certificate authorities (CA's) providing that service with the National Association of Certification Authorities (NACA). Registration with the NACA will not automatically connect the trusted roots of each CA.

Wrap-Up

The challenge for the implementation and use of Digital Signatures in our daily lives boils down to the perceived service it can provide coupled with its ease of use. Here we are a number of years after the Department of Commerce's approval announcement of the Digital Signature Standard and we are just starting to see its implementation becoming a reality. We still have many problems to solve. One of the most important issues is that all public-key exchange mechanisms can be subject to what is commonly termed a "Man in the Middle Attack." We have commercial Certificate Authorities providing a service for banks and financial institutions in order to facilitate Internet transactions without having a common trusted root. We are deploying systems worldwide with different types of certificates and algorithms. We have not fully identified transaction relationships and the legal aspects. Individual states are enacting legislation concerning Digital Signatures, which could lead to a significant number of different legal standards across the United States. The general public is terrified of "Big Brother" and the ability to track each person by following the digital trails of electronic commerce and the seemingly encrypted contents of email by simply tapping into the Internet.

Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10

Professional Publishing Home | Contact Us | Customer Service | For Authors | International Offices | New Book Alert | Search Catalog/Order | Site Map | What's New