The authority over certification authorities - a problem with digital signatures.
By Micha³ Ren
New legislation regarding digital signatures will soon allow for many everyday tasks to be performed digitally, rather than on paper. Digital signatures create the problem of certification of identity, and to solve it, certification agencies are needed. Their development and legislation governing them must be closely monitored.
Information and communications technology was often accused of being a snake, eating its own tail - the whole industry producing no more than it is consuming. [Gogo³e
k, 2000] Counting strictly by amount of money produced this may be true, but there remain things not accounted for, parts of everyday life that would not have existed at all without new technologies. In most stores one can pay with a credit card – inconceivable thirty years ago. Of course, this development has given rise to new kinds of fraud – there are many horror stories about credit card numbers used for remote transactions. This is the result of friction between the real world, "brick and mortar" part of the system, and the digital, intangible part. Credit cards are susceptible to fraud because they merely give access to money – they are not the money themselves. It would be possible to devise a system of secure, untraceable, and almost impossible to forge (certainly much harder than traditional bills) digital cash. [Kuty³owski, Strothmann, 1999] But not all aspects of everyday life can exist without their "brick and mortar" parts. The ICT industry is in the stage of figuring out what can be done with technology – what can be transferred from "brick and mortar" to digital, and in what ways can digital do better.The dream of paperless office has remained but a dream for decades. Now, this may change to an extent. The amount of electronic data exchanged in high-tech companies is already high, but for some things, paper is still indispensable. One reason is technological - there is no suitable display medium which is cheap, light, flexible and high-contrast. This obstacle will be surmounted, as it only requires refinement of existing technologies; in fact, this is happening now. [Ditlea, 2001] Another, more interesting reason is that no electronic document carried legal weight (except, perhaps, as evidence) until recently. Now, however, more and more countries create laws which acknowledge electronic signatures. That law is very important for the ICT industry. Some countries, Poland included, went as far as to state that electronic and traditional signatures will be treated equally. [Sejm RP, 2001] This is a very simple statement, but it is said that the devil is in the details, and indeed the most important part of those new laws is laying out the requirements that the digital signature must fulfill in order to be considered valid.
There emerges the most difficult part - that of certification. The digital signature is superior to a normal one - it depends on the document being signed, so it can't be extracted and copied. However, the signature has no connection to the person signing it, contrary to handwriting, which can be recognized as belonging to an individual. A digital signature is just a piece of data, and it is of extreme importance to be able to assert: "that piece of data could only be generated by the individual named ..." - something that can be accomplished by certification. [Menezes, Oorschot, Vanstone ,1996] All digital signatures are created based on a secret, that only the signer possesses. A certification authority must exist which will vouch that a particular secret is indeed in possession of a particular individual - that too, is handled by digital signatures, but the signature of the certification authority is assumed to be well known. There are many ways of organizing certification authorities, some with their own unique problems. And the common problem will be that of trust and compatibility – certainly not trivial to solve, especially when different countries are concerned.
Everybody knows what a signature is. It consists simply of writing one’s name. In this paper, I extend the definition to any signature that may be verified by human senses; thumbprints would qualify, for instance. In any case, such a signature is supposed to be later used as a proof that the signer acknowledged the document. It may seem that pen-and-paper signatures are the lowest common denominator, since they require no complex technological means. However, even the simplest, handwritten signature is inaccessible to illiterate people, and there are many in the world! Workarounds are, of course available, such as using a thumbprint, but taking a thumbprint can easily be done without the signer’s knowledge or consent. An often repeated advice is to be base any security system which identifies users on something that the user knows (a secret), something that the user has (a physical key), and something that the user is (biometric information). Clearly, “normal” signatures fulfill only the last part, and once someone learns to duplicate a signature, the original user cannot simply change it. Also, that kind of signature is not tied to the document it signs – it can be copied onto another, and seem to be just as valid if the process used to copy it was effective enough.
In contrast, digital signatures cannot be verified by human senses. They are also always tied to the document signed in such a way, that they cannot be copied onto another one; this is vital, since all bits look the same, and perfect copying is trivially easy. In the most widely used signature schemes – based on Diffie-Hellman or RSA (Rivest, Shamir, Adleman) problems [Menezes, Oorschot, Vanstone, 1996] – the signer possesses two “halves” of a key – one secret and one public, both of which are necessary to create a signature for a given document. Any interested party can later verify, using the public key, that the signature on a document was generated by somebody with both the secret and public key. Therefore, of the three criteria mentioned above (secret, physical key and biometric information), digital signatures satisfy only the first. As soon as this secret is learned by someone, that person can generate apparently valid signatures at will. Fortunately, the legitimate user can then generate another key. Even if the secret is well-protected in the first place, it is often easy to trick the signer’s computer to sign a different document than the signer sees.
The simplest versions of signature protocols (including such “protocols” as signing one’s name on a piece of paper) have their shortcomings. Some of them can be cleverly circumvented; in fact some solutions are so often used, that they do not even seem clever anymore. One example is the existence of officially appointed notaries. They can serve many roles – one is an additional security. A document signed by someone, and then co-signed by three notaries, each certifying that so-and-so signed that document in their presence carries much more legal weight than a document with one simple signature. It is harder to forge more signatures, and besides, notaries can keep records of documents that they sign, so in case of doubt, the validity of signatures can be verified that way – and it is assumed, that no one but the notaries themselves has access to their records. Naturally, the notaries must be trusted. Notaries are also useful for dating documents – they simply have to write that a particular document was presented to them at a certain date, and sign it. The same principles can be used with digital signatures; in that case it is even easier to devise schemes that make it harder for the notaries to cheat.
As mentioned above, both normal and digital signatures only satisfy one of the three security conditions – that the signer had to use some secret knowledge, some physical, hard to duplicate key, and some biometric information. This limitation is also routinely circumvented – whenever you are asked for a proof of identity, such as a passport or a driver’s license, that is using a physical key; and the key if further tied to an individual using biometric information (a picture, and/or a signature). Similar schemes (without biometric information) are available for digital signatures, for example smart cards, or tokens, often used in bank transactions. It is a bit harder to tie biometric information to a digital signature, but this, too can be done.
With all those clever, complicated ways to assure validity of signatures, why are the certification authorities needed? The reason for this lies in the nature of digital signatures themselves. Where normal signatures are based on biometrics, the digital signatures are based on a secret. When a document is signed with handwriting, it is possible for someone who has access to a sample of a signer’s writing (and, perhaps, an expert on graphology) to verify the signature. How to match handwriting with a person? Simple – ask for that person’s passport, diver’s license, or a national ID, if the signer’s country has one. Such an ID is the government’s way of saying: “We certify that the person named so-and-so, looks like this (a photo), and writes like this (a signature).” (And perhaps also: “And that person was born on a certain date, lives in a certain place, etc.”) When a document is signed digitally, anybody can verify that a given secret was used to generate the signature. But this is not enough; there must be a way to answer the question of whose secret that is.
The certification authorities help with this very problem. They combine the public part of the signer’s key with name, and perhaps other information, such as a photo. Then they sign this document with their key. After signing, this document becomes a “certificate”. Now somebody who signs a document can attach this certificate to it. It is worth noting, that this certificate was created using a digital signature, and so, it only delegates the problem. Now the question becomes: “Whose secret is that used to sign this certificate?” Fortunately, that is all that is needed. Public keys of certificate authorities are assumed to be well-known. Whether that can actually be achieved, depends on how they are organized.
The certificate authorities can be organized in several ways. In order of most to least centralized, some organizational structures could be the following:
One certification authority for several countries
It is not impossible that a few countries could agree on one certification authority. It would require significant level of trust from all participants, since control over such a certification authority would be equivalent to the ability to issue proofs of identity of any participating country. This approach offers advantages in terms of security – it is easier to restrict access to one location. Also, it is easier to host the necessary hardware in one place, instead of spreading it out.
National certification agency, operated by the government
This model is quite likely – the government would simply extend issuing passports and IDs to the digital world, using one certification authority. That certification authority could be divided into several parts, even in remote locations, simply for convenience, but conceptually those parts would still form only one entity.
Commercial certification agencies certified by the government
In this model, governments choose not to build the infrastructure, but only to certify companies which bear the burden of building and maintaining theirs. This is unlikely if the signatures are to be equal by law to normal signatures, because then commercial entities would have control over issuing proofs of identity.
Central “root” certification agency and sub-agencies
For efficiency, there could be one certification authority, which would certify certification agencies, which could in turn certify even more certification agencies, and so on – forming a tree, with the most important certification authority as a root. This model is also likely, because responsibilities for certification authorities can be assigned to already existing entities.
Web of trust
In this model, there are no certification authorities per se; instead, everybody can vouch for anybody else. Then, upon receiving a document signed by an unknown key, there is a chance that this key is already certified by somebody trusted by the verifier. This is the model used by Pretty Good Privacy. [PGP, 2002] It is almost impossible that this model would be adopted – any central authority is unnecessary, so this works well for grassroots organizations. This kind of “certification” in the eyes of government would amount to “these people say that he is who he says he is” – not a great assurance. However, there are precedents – for example voting without proof of identity, in a similar fashion.
Traditional, pen-and-paper methods of signing documents have their faults, but new, digital signing methods introduce new ways in which they can fail. Some of them are discussed below, with special emphasis placed on how they relate to certification authorities.
Tricking the user into divulging the secret key
This attack targets the user itself, not the public key infrastructure, but it is interesting how the certification authority should react in this case. When a user suspects that the secret portion of the key was compromised, the key can be revoked – it is placed on a revocation list. Before accepting the signature as valid, the verifier should check the current list – as is (or should be) done with credit cards. Unfortunately, such a scheme rules out implementations that do not have online access to the revocation list.
Tricking the certification authority into signing a wrong key
Another way of attacking the system is tricking the certification authority into signing a key provided by the attacker, but with a false name. In theory, certification authorities exist solely to check if the name (and all other data, if any) matches the key, so this should be so difficult as to be practically impossible. However, the reality is different. Recently, a company known to anybody who visits secure sites on the web – Verisign, allowed a third party to obtain a certificate with the name “Microsoft Corporation”. [Microsoft, 2002] Fortunately, Verisign quickly realized that security has been compromised, and revoked the certificate – that is, put it on a revocation list. Unfortunately, for a long time afterwards, Microsoft’s own web browser was unable to use the revocation lists (because of the error on Verisign’s side, as Microsoft quickly claimed). The result – the attacker was able to sign and distribute code with the name of “Microsoft Corporation”. Moral – make sure that revocation lists are functional – this is vital for the certification authority to be able to do its job.
Sabotage and denial of service
Since certification authorities have to be online all the time to provide service, they will be targets of cracking attempts. Hopefully, they will be well protected, but that still leaves out the possibility of simply swamping them with requests. The verification of the signature can still be performed if the certification authority goes offline, but without the benefit of revocation lists, greatly decreasing security; of course with the assumption that the certificate was delivered with the signature, and does not need to be downloaded from the certification authority, which does not need to be the case. On a more sinister note, no certification authority can stand a well-placed bomb. Backups and redundancy for certification authorities are vital, especially if all e-commerce in the country relies on one certification authority.
Breaking the signature scheme
It is possible for the signature scheme to be broken. This can happen because of breakthroughs in mathematics – breaking the two most popular signature schemes – ElGamal and RSA is conjectured to be as hard as solving the discrete logarithm problem, or finding large prime factors. First of all, it is not known if those problems are “hard” – merely that nobody has found a good way to solve them. Second of all, the aforementioned equivalence is only conjectured, and not proven; in fact, it is suspected that there is no equivalence in the case of RSA [Boneh, Venkatesan, 1998]; things are looking better for ElGamal [Maurer, 2001]. The ability to uncover secret keys based on their public halves can also be gained by having enough computing power. Breaking those public key signature schemes can be likened to finding to whom a particular phone number belongs – in a normal phone book. Certainly time consuming, but doable; all the information is there, and nothing has to be guessed. Fortunately, for large key sizes, the computing power required far surpasses anything available right now and, likely, in the near future. It seems that really large key sizes will be safe until quantum computers of sufficient size are developed.
In any case, the ability to generate signatures is of less utility than breaking ciphers – eavesdropping is easy to hide, but signing is bound to be discovered sooner or later. Therefore, such attacks are likely to occur where it would be hard for the signer to prove that the document was signed by somebody else; such claims sound much less plausible than in case of pen-and-paper signatures. At first glance this would suggest that documents of no great importance, signed without notaries, would be primary targets, but the fact is, that the resources involved in this kind of attack make it much too expensive to harass ordinary people. On the other hand, generating signatures in the name of a certification authority could be much more profitable, and therefore the keys of the certification authorities should be very hard to break indeed, and be changed on a regular basis. Changing the keys presents the difficulty of distribution – every interested party must be sure that the new key is valid; if the changes are infrequent enough, and the certification authority operates under auspices of the government, the key could be printed in the newspaper, for instance. Although inconvenient, key rotation is vital, since keys of certification agencies will certainly come under attack. It is better to err on the side of caution; what was thought impossible 10 years ago is possible today – one example is breaking of a 512-bit long RSA key. [RSA, 1999], and such keys are still widely used.
Compatibility problems
For e-commerce it would certainly be great if digital signatures from every country were compatible with one another. Some standards already exist right now, but the more formal ones, are only frameworks [Gutmann, 2000], so the individual implementations differ somewhat; only recently efforts are made to make interoperability possible[PKI-Challenge, 2002]. Which one of those standards is going to win? Should there be only one, eventually? If the remote possibility of one of the signature schemes being broken, wouldn’t it be better to have something else to rely on, and the infrastructure already built? Maybe it would be better for every certificate issued by a certification authority to consist of several signatures, every one created with a different algorithm. In that case, if one kind of signatures was compromised, there would still be others. Such an approach, however, puts a heavier burden on certification authorities – the amount of computation, as well as bandwidth required for every signature rises, and the code that implements every one of the signature schemes must be written and rigorously tested.
Trust problems
Earlier, I have said that certification authorities are trusted. In a cryptographic context, “trust” only means that the trusted entity handles its keys well. However, existing commercial certification authorities, and certainly any hypothetical ones operated by governments, issue proofs of identity. How far can those be trusted (in the usual sense of the word)? If the issuing organization is commercial, then I wouldn’t trust them very far. The current state of affairs is that commercial certification authorities issue proofs of identity to companies – that is vouch that a certain secret belongs to somebody within a company of a certain registered name – without having any authority over, or connection with entities authorized to register company names. Also, those companies disclaim all liability for issued certificates, which is not very trust-inspiring. [Ellison, Schneier, 2000] But right now, everybody is aware of this (or should be!) and there is no false expectation of the certificates being official proofs of identity. Also, certification authorities try their best to serve as many customers as they can, and they are not known to block customers from other countries, so even if one certification authority emerged as “standard”, there would be no problem with getting certified (other than dealing with a monopoly). On the other hand, if governments of different countries start to operate their own certification authorities, will they certify only citizens from their country? If they do not, will the certificate from Principality of Sealand be as trusted as a certificate issued by the United States of America? And if they do – where would the authority to do so come from? If one country emerged as a monopoly in issuing certification authorities it would be given great power – analogous to issuing passports for other countries. Such an extreme is unlikely, but to a degree, it is possible; there are precedents, for example just one company in Australia prints polymer money for several countries – Australia, Thailand, Papua New Guinea, Sri Lanka, Malaysia, Singapore, Brunei, Indonesia, Kuwait, Western Samoa, New Zealand and Romania. [NPA, 2002]
Sooner or later, there will be need for individuals to be issued digital proofs of identity, and so, certification agencies with authority to do this, will have to exist. They will most likely be directly controlled by governments, but still, legislation regarding such technicalities as key length, implemented signature algorithms, key rotation schedules, and certificate revocation lists should be introduced. Also, the possibility of a “catastrophic failure” – breaking one of the commonly used algorithms – should be addressed. For now, we can get by with certification agencies being commercial entities, with their responsibilities light, and defined in broad terms, if at all, because right now e-commerce is the only field with real need for certificates. But I am quite convinced that before I throw away my paper passport, we will need much tighter regulations for certification authorities.
Gogo³ek, W., (2000), "Mity i rzeczywistoœæ Internetu." conference materials from "INTERNET - Wroc³aw 2000" (in Polish)
Kuty³owski, M. and Strothmann, W., (1999) "Kryptografia. Teoria i praktyka zabezpieczania systemow
komputerowych.", Read Me (in Polish)Ditlea, S. (2001) "The Electronic Paper Chase", Scientific American 11/2001, also online at http://www.sciam.com/article.cfm?articleID=0004C2D2-B938-1CD6-B4A8809EC588EEDF&pageNumber=1&catID=2 accessed 2002-07-16
Sejm RP, (2001), “Ustawa z dnia 18 wrzeœnia 2001 r. o podpisie elektronicznym”, online at
http://ks.sejm.gov.pl:8009/proc3/ustawy/2594_u.htm (in Polish) accessed 2002-07-16Menezes A., van Oorschot, P. and Vanstone, S. (1996) "Handbook of Applied Cryptography", CRC Press, also online at http://www.cacr.math.uwaterloo.ca/hac/ accessed 2002-07-16
The International PGP home page, online at http://www.pgpi.org/ accessed 2002-07-16
Microsoft Corporation, (2001), online at http://www.microsoft.com/technet/security/bulletin/MS01-017.asp accessed 2002-07-16
Boneh, D. and Venkatesan, R. (1998), “Breaking RSA may not be equivalent to factoring”, Proceedings Eurocrypt '98, Lecture Notes in Computer Science, Vol. 1233, Springer-Verlag, pp. 59–71, also online at http://theory.stanford.edu/~dabo/abstracts/no_rsa_red.html accessed 2002-07-16
Maurer, U. (2001), “Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms”, online at http://link.springer.de/link/service/series/0558/bibs/0839/08390271.htm accessed 2002-07-16
RSA Laboratories (1999), “Factorization of RSA-155”, online at http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html accessed 2002-07-16
Gutmann, P. (2000), “X.509 Style Guide”, online at http://www.cs.auckland.ac.nz/~pgut001/pubs/x509guide.txt accessed 2002-07-16
PKI-Challenge (2002), online at http://www.eema.org/pki-challenge/overview.asp accessed 2002-07-16
Ellison, C. and Schneier, B. (2000), “Ten Risks of PKI: What You're Not Being Told About Public Key Infrastructure”, Computer Security Journal, v 16, n 1, 2000, pp. 1–7, also online at http://www.counterpane.com/pki-risks.html accessed 2002-07-16
Note Printing Australia (NPA), (2002), online at http://www.noteprinting.com/innovation.html accessed 2002-07-16