Home > Articles > Cryptography > Proposed redesign of PKI Bookmark page
Proposed redesign of PKI
An affordable and scalable PKI model

George Ou
September 2, 2003
Note to the reader,

This is my proposal to redesign PKI such that it may realize it's full potential; PKI everywhere!  I initially wrote it as an original work without the knowledge of other Internet Draft proposals that may address some of my concerns.   It now appears that DNSsec Signing Authority and RFC 3280 Name Constraints already does much of what is proposed in this paper as pointed out by Bryan Olson in USENET.  I'm still trying to research the overlaps, and I'll be modifying this paper to be an advocate of those existing RFCs where I overlap.  At the very least, this paper offers reinforcement of those existing RFCs and may provide some useful ideas for the future of PKI.  Please feel free to critique this paper as you see fit.

Introduction The existing PKI standard, a limited and fragmented deployment
The existing PKI CA model Hierarchical for scalability, but not for delegation
DNS: A parallel universe What if DNS was structured and sold the same way as PKI?
PKI: Modeled on DNS What if PKI was structured and sold the same ways as DNS?
Domain level root CAs CAs authorized to sign for their domain or sub-domains
Security policy for the new PKI How to improve PKI security
The new Certificate structure A new certificate structure for the new PKI model
The new global PKI hierarchy Defining the root CAs for government and country level domains
Redundant root CAs Requiring two signatures for Certificate to be valid
PKI enabled Digital notaries Streamlining and modernizing the public notary process
Final words  

PKC (Public Key Cryptography) was one of the greatest inventions in the history of cryptography dating back before the birth of Christ.  PKI (Public Key Infrastructure) came about as a means to distribute public keys from centralized CAs (certificate authorities) that act as TTP (Trusted Third Parties).  While there are many ways to distribute and verify public keys of a certain entity, PKI is the most elegant and scalable because the CAs can authenticate without actually being involved in the actual authentication transactions.  PKI was envisioned to bring PKC to the masses and revolutionize the world of communications.  Although this has happened to a limited extent with E-Commerce and on a small and fragmented level with large corporations and government organizations, it has not come anywhere close to it's true potential.  Other than E-Commerce sites that have largely standardized on expensive x.509 certificates from companies like Verisign, you have a hodgepodge of private internal Certificate Authorities that facilitate secure communications within their own organizations but stop at the organization's border.  One corporation's private CA is worthless to another corporation and vice versa under the current PKI design because no one wants to give the root authority to some outside entity.  As a result, the current success of PKI is severely hampered because of it's pricing when using public CAs or lack of compatibility with private CAs.  Adding to the confusion is the fact that PKC and PKI are very complex and obscure concepts that even the technically savvy sometimes fail to grasp.  Marketing material is littered with accusations that PKI and PKC is too complex or even weak and the media soak it up like fine wine because they don't know any better.  Even for those of us who realize the importance of PKI are forced to constrain our deployment because of the $200 to $700 price tag per certificate.  Given these challenges, PKI cannot and will never reach it's full potential.

The existing PKI CA model
PKI is a system designed to function on one level, where all trusted Certificate Authorities function as gatekeepers of the entire kingdom.  Although PKI has a hierarchy of root CAs, intermediate CAs, and issuing CAs, that hierarchy was put in for scalability considerations.  Subordinate CAs are only subordinate in name, but they are not subordinate in function.  No matter how far down the chain of command, the CA has the exact same issuing power as the root CA on the top of the pyramid.  This has guaranteed that only a few companies issue all of the public certificates in the world, and they're not about to grant other entities root signing capabilities for financial and for security reasons.  A quick scan at one's own default CTL shows that there are over 20 root CAs, some of which most of us have never even heard of.  The likeness of a compromise in our public CA system grows proportionally to the number of root CAs there are, because any compromise in one root CA is a compromise in the entire system.  At the same time, there are too few CAs to bring any kind of real competition to facilitate reasonable prices.  The challenge is, how do you increase the number of CAs to increase supply but at the same time reduce them to reduce the odds of a compromise.  This is the challenge I seek to answer in the remainder of this paper.

When one really thinks about it, the duty of root CAs is actually much easier than the duty of our global root DNS servers.  This is because CAs only have to issue the certificate to a user once and never need to participate in future authentication transactions.  A root DNS server on the other hand not only has to set up an entry for the domain but also need to field global DNS requests for that entry for the life time of that domain.  The only costly and time consuming thing for a CA to do is to perform the initial verification and maintain CRLs (Certificate Revocation Lists) for miss issued certificates and certificates with compromised private keys.  Even so, initial verification can be done relatively inexpensively by PKI enabled notaries and they shouldn't need to be done every year or even every other year.  Miss issued certificates should be at the expense of the CA, and lost private keys should be charged separately to users who loose them since that would only be fair.

DNS:  A parallel universe
Imagine a world where DNS had evolved the same way as PKI, where each and every DNS server in the world was authoritative for "." any domain, sub-domain, and host name in the entire world.  In this "Twilight Zone", all public DNS records could only be served by root-servers such as "A.GTLD-SERVERS.NET".  If you wanted a DNS record for "www.your-domain.com", or any other host within your domain, you had to pay Verisign $500 to get it registered with the Internic so that they can enter the DNS entry for for you.  For a typical domain with 30 public DNS entries, a company would either decide to go without or fork out $15,000 to Verisign for all 30 public DNS entries.  Sure you can have your own private DNS servers with unlimited free DNS entries, but their dominion won't stretch beyond the corporate LAN and WAN.  No other companies would ever trust your DNS servers because that would empower you to be a root DNS server for their company.

As ridiculous as this sounds, this lack of granularity isn't a joke in our universe for PKI.  We live in this strange world where you buy certificates by the host, where issuing power is root or nothing so nothing is what we're forced to live with.  We learn to do without PKI except where we absolutely must have it for applications such as E-Commerce, and sometimes we even sacrifice security by using pre-shared static keys because PKI costs too much.  The question that I must ask is, how do we get out of this crazy predicament?  There must be a better way!

PKI:  A parallel universe
Meanwhile, in a different parallel universe where events have gone right for both DNS and PKI.  PKI thrives everywhere like DNS and is almost taken for granted.  The familiar scene of my alternate self registering a domain called LANArchitect.net is about to take a surprising turn.  Not only does the InterNIC add an entry in the ".com" DNS root servers that point to his authoritative DNS, a central PKI certificate authority for ".com" issues a certificate for his LANArchitect.net's domain level root CA which can only issue certificates for LANArchitect.net.  To pay for these two services, an online payment of $120 is made for a five year registration in DNS and PKI.  To obtain a medium level rating for LANArchitect.net's domain level root CA, a quick trip to the PKI enabled notary with $60 would suffice for the next 5 years.  Once the medium level rating for his authoritative CA is obtained, he turns around and creates some subordinate Issuing CAs all rated less than or equal to the authoritative CA for LANArchitect.net.  Armed with a PKI that is now trusted to grant globally trusted certificates for LANArchitect.net, certificates are issued for all of his publicly exposed servers to enable SSL or TLS.  He even issues certificates for his DNS servers to enable DNSSEC and SMTP servers for SMTP-TLS and SMTP-AUTH capability.  If this had been an organization with users in it, an unlimited number of certificates can be issued to each member of the organization to enable digital signing and encryption for the entire work force.  These publicly trusted client side certificates can now even be used as credentials for E-Commerce sites or any other website that requires authentication.  A level of PKI deployment never dreamed of in our world is attained here because domain level PKI CAs are now globally trusted to issue certificates for their domain for nothing more than the cost of operating a few CA servers.

Domain level root CAs
A domain level root CA server is just like an authoritative DNS server for a domain.  In the case of DNS, the authoritative DNS server is only authoritative for the domain it was assigned to, whereas the domain level root CA is only authorized to sign certificates for it's corresponding domain.  Under the existing PKI system, signing privilege is root or nothing.  Either the CA is completely trusted to sign for anything under the sun, or it is not trusted sign anything.  Under this new proposal, the root CAs will not be issuing host, code signing, or email certificates.  That function is best handled by an organization's own internal CAs.  Internal IT are the most qualified people to be issuing those certificates because they are the ones most familiar with their own employees, not some external organization thousands of miles away.  Unlike the current situation, a miss issued certificate can only hurt the domain that miss issued a certificate and not some other organization.  Of course PKI can still be outsourced, but I would venture to guess that most companies would prefer to keep that function internal.  The master root CAs should never be issuing email, host, or code signing CAs, just like the global root DNS servers don't issue host level DNS entries.  Verisign should never have been in the position of miss issuing that Microsoft code signing certificate in the first place.

A central authority similar to the InterNIC would simply sign a certificate with the domain name and public key of the domain level root CA using simple email verification.  Such a basic level of certification should only entitle the company to do basic email encryption and signatures, but should not be trusted to sign code, host E-Commerce applications, or run financial transactions.  The basic certification level is for small organizations or personal domains that only need the most common and basic capabilities of PKI.  Additional verification and binding of information such as Business name, License, address, phone, Biometrics of the domain administrator and/or the CIO and other executive officers could boost the trust level of the certificate to a very high level of trust.  Cryptographic modules that are FIPS 140-2 level 2 or above to protect private keys would put the final touch and should be mandated if a company is going to be running E-Commerce or doing code signing.  Since common sense dictates that you wouldn't trust any offspring certificate more than you trusted it's parent's certificate, it is imperative that you get a maximum trust rating for your domain's authoritative CA.  Once a domain level root CA is created, a company or organization can issue as many PKI certificates to their own domain as they please.  ISP's can offer certificates to their subscribers either as a free benefit or they can charge some extra money for the service.

Typically, a PKI is not really expensive to run under any circumstance, even if Intermediate CAs and Issuing CAs are created.  Smart cards are dirt cheap and even Cryptographic Modules aren't expensive for most company to bear.  In the past, building your own PKI meant the "P" really stood for private and it was difficult to make a good business case to have one because of it's limited compatibility outside of the company.  There was just absolutely no way you where going to get your business partners or customers to put your CA in their root CTL (Certificate Trust List) because that would mean they are trusting you to sign everything under the sun.  Under this new PKI proposal, they automatically trust you to sign for your own company just like they currently trust your authoritative DNS server for records within your domain.  All the wonderful technology such as S/MIME, IPSEC, SMTP-TLS, SMTP-AUTH, SSL-SMTP, SSL-IMAP, SSL-POP3, and anything else that needs strong authentication and encryption can now instantly flourish under a uniform PKI environment.  Any number of sub-domain level CAs can be created if the organization is large enough to justify it, and they wouldn't need to go back to the global ".com" root certificate authority.  Sub-domain CAs would only be signing authorities for their particular sub-domain, and it would empower corporate head quarters to delegate limited signing functionality to their smaller sub-divisions.

One of the most heavily criticized components of the current PKI infrastructure is it's lack of a good CRL system.  Under this new distributed and delegated PKI model, root level CAs will not need to worry about distributing CRLs for the end hosts and end users since they wouldn't be issuing those certificates in the first place.  The only thing that the root level CAs should worry about is CRLs for top level domain CAs that were compromised or miss issued.  This instantly makes the new PKI model infinitely more scalable, because CRLs can be a much higher burden than the act of issuing the original certificates.  The host level and end user CRLs would actually be handled by their respective domains, and most organizations would be very prompt about posting CRLs because they are the one's that should be liable for stolen certificates if they don't post the CRL within a reasonable amount of time.  I propose that the CRL process should be simplified by making a more rigid standard.  CRLs should be signed and posted via HTTP at a standardized URL such as http://crl.your-domain.com.  All applications that use this new PKI should check for new CRLs deltas at that standardized URL from their respective domains CRL servers.  The CRL work load would be evenly distributed among the entire Internet, rather than just Verisign and the other 20 or more root CAs.  The new CRL system should be fully dynamic and always up to date, and it should be completely transparent to the end user.

Ultimately, this reduces the number of certificates that need to be registered and purchased from the Internet's root CA to just 1.  Because the bulk of Certificate issuing and CRL work is now delegated to each domain, the number of root CAs can be effectively reduced to just 2 entities and not the current 20 or more.  This not only solves the problem of too many root CAs to have to protect, but it also solves the scarcity problem and virtually removes all cost barriers.  Once this new PKI model is adopted, the only cost of publicly trusted certificates would be the cost of operating a domain level PKI and the cost of a single root certificate.  For a typical company that would issue 1000 certificates to their users, servers, and other devices, they could easily save themselves $200,000 a year!  Obviously, most companies would have simply gone without PKI as they do now and sacrifice strong authentication and encryption for budgetary constraints.  Under this new PKI model, PKI can truly reach it's full potential!

Figure 1:

I had always intuitively wondered about getting your own Certificate Authority to sign for your own domain from the moment I first started learning about CAs and PKI, but I was shocked to find that no such technology exists!  In the SPAM research paper I wrote, I faced extreme opposition from the email administrator community because of my call to use PKI to end SMTP spoofing.  I had no idea that PKI was such a hated technology because of the cost factor.  This is what motivated me to develop my intuition into a proposal to create a new PKI.  If someone else has already submitted a proposal that calls for this very same thing, I hope someone will bring that to my attention and I'll realign my support for that proposal instead if nothing in this paper is original.  I just can't believe it wouldn't have already been adopted.

Security policy for the new PKI
Once a company gets a certain level of a certificate, all future certificates must be issued at the same security level as a matter of policy.  The name space root CAs should not issue some other joker a basic level master certificate when the company has already obtained a maximum level certificate for their domain.  Additionally, a company could opt to lock the domain such that no other master domain certificate could be issued for the next 5 years until their current certificate has expired.  If by chance they loose their domain's master certificate or it was compromised for some reason, an even more extreme verification process should be required to unlock the domain.

To further protect against social engineering attacks, the root CAs should only issue one certificate for the domain level root CA at any given time.  If a high-tech thief comes along to request a new certificate and they manage to falsify their credentials and convince the root CA to grant them someone else's domain level root certificate, the existing certificate for that domain should automatically be revoked.  The rightful owners of the domain level certificate would immediately know someone had stolen their domain level certificate because their own domain level root CA would cease to function within 2 days due to the fact that it had been revoked as a policy of the 1 certificate per domain policy.  In such an event, the name space root CA would have to be insured to pay for all damages for the lost productivity and time it takes to redeploy all of the companies certificates.  The higher the level of certification, the higher the damages.  See the end of this paper titled Digital Notaries for how maximum level certificates are obtained.

Essentially, a system that requires redundant maximum verification to two separate entities just once every 5 years for an entire domain is much more secure than a system that requires low to medium levels of verification for each and every host every year.  It will also be less of a hassle and it will be much cheaper than the current system.

Another concept I would like to implement under this new PKI model is sterile subordinate CAs whether they are peer level domain or sub-domain CAs.  What I mean by sterile is that subordinate CAs of a domain or sub-domain should not have the ability to give birth to other CAs.  Only the domain root level CA which is in a protected offline environment can do that.  A simple generational time bomb value could be granted by the global root CAs as requested from the customer.  A large enough enterprise could request a numeric value of "2", so that their domain level root CA could issue one additional generation of non-sterile subordinate CAs but their time bomb value could be decremented to 1.  That subordinate domain could in turn issue other sub-ordinate issuing CAs who's time bomb value would be "0" so that they cannot reproduce any more CAs.  Only sterile CAs should ever be exposed as issuing CAs, because the last thing you would want is some one to steal a subordinate CA certificate for a rogue CA.  I also think that E-Commerce , code signing, and financial transaction certificates should only be issued from the offline domain level root CA because of their high target value.  Exposed issuing CAs should only be permitted to issue regular host and email certificates.

The new certificate structure
The structure for this new PKI model will include a field that for CA certificates that define what domain the CA is allowed to issue certificates to.  The top level domain CA will only be issued by the root CA responsible for the correlating ICANN domain name space, and sub-domains CAs will be handled by the top level domain root CA.  It will also include the generation time bomb which most organizations will request to be 1, which permits their domain root CA to only create sterile issuing CAs.  Most organizations will only want one offline root level CA to have to guard, and it can create more than enough issuing CAs for just about any size organization.  The other import fields that need to be modified with more strict certification requirements should be for E-Commerce, Code signing, and financial transaction servers.  This is because using these types of certificates should carry legal liabilities if the proper security measures are not taken and CRLs are not posted in a timely manner.

Bryan Olson on Usenet was kind enough to point out that the actual mechanism for enabling this proposal is already in RFC 3280 under "Name Constraints".  Bryan also pointed out that this is already being used in some places, but that it wasn't being used in SSL certificates probably because there wasn't much profit in it.  But that is exactly my point!  The business model of PKI is killing PKI, because if you applied that same model to DNS, it would also be at the same pathetic level of deployment as PKI.  This paper proposes that we eliminate the cost barrier of PKI such that it mirrors DNS at the global level, not only in cost but also in deployment.

The new global PKI hierarchy
The new hierarchy would be vastly superior to the current flat model where everything is root.  We would simply create a hierarchy that follows the ICANN domain name space structure and create a pair of independent root CAs for each domain suffix.  I don't believe there is a need have a master "." root CA and have everything else chain off of that, there is no need for that extra overhead and security risk.  Each entity such as ".com", ".us", ".ca", ".net", ".gov", and all the other domain name spaces would all have their own pair of root CAs organizations, and ".com" would obviously be the largest.  Although this could eventually result in nearly one hundred root CAs (not including subordinate issuing CAs), it would still be a lot more secure than our current set up.  This is because only 2 entities would be responsible for a certain domain.  If some 3rd world countries root CAs are compromised, it will not affect the ".com" space or any other domain name space other than their own.

Example of common root CAs and who controls them  (Not entire list)
.com Two US based entities .edu Two organizations elected by US universities
.org Two US based entities .gov Two US government agencies
.net Two US based entities .mil Branches of the US military
.us Two US based entities .ca Two Canadian based entities
.fr Two French based entities .de Two German based entities
.ru Two Russian based entities .uk Two British based entities
.cn Two Chinese based entities .se Two Sweetish based entities

To handle the disastrous situation where a root CA's private keys are compromised, a panel of the larges name spaces could be formed to handle revocation and redistribution of replacement root certificates to the world.  Since a revocation of a name space root CA is not to be taken lightly, it should require the unanimous digital signatures of all the panel's members.  The panel should be comprised of the major root CAs such as ".com", ".net", ".edu", ".fr", "uk", and all the other major countries.  In the event that a panel member itself suffers a loss of a private key, signatures for the other panel members should suffice.  This would empower each name space to elect and control it's own PKI Certificate Authority infrastructure.

Redundant root CAs
The reason I proposed two independent entities instead of just one per name space is because I want to enable redundant root CAs.  I don't just mean having two root CAs per name space where you can just select one or the other.  I'm proposing that for a maximum level of certification, it should require signatures from both root CA entities to make a valid certificate.  It would require a compromise in both CAs to be able to break the system.  Only the maximum rating level certificates would require dual signatures, along with the most stringent physical verification requirements that must be performed independently by each root CA.  Under the existing PKI system, such extreme measures would be highly impractical because no one would tolerate going to this amount of trouble for each and every host or email certificate once a year.  For a large corporation to have to go through this only once per five years for their domain level root certificate is very reasonable and eminently feasible.  I believe that the maximum level certification should be required if a company wishes to grant themselves certificates for E-Commerce, code signing, and financial transaction websites.  Even without it, the basic level certification that relies on email validation would be vastly superior to anything we have now where no PKI and no certification level is the norm.

PKI enabled Digital notaries
Notaries to this day still use seals that are not fundamentally different from methods used thousands of years ago.  These ancient techniques using difficult to copy symbols is a form of security through obscurity, and has proven to be completely forgeable.  Even the trouble that countries go to make their currency "copy resistant" is all but useless when facing a determined counterfeiter.  Even worse, the contents of a message or contract is susceptible to modification even if the seal is completely legitimate.  It's long over due that notaries take advantage of modern PKC digital signature technologies so that not only are the signatures forge proof, but the messages they bind are tamper proof.  Now the purpose of this paper is not to talk about notaries, but the benefit of modernizing the public notary swings both ways.  Once notaries become PKI enabled, they can serve as the verification method for this new PKI model.  It would be very simple for a notary to take a photo of a domain administrator and/or CIO and their finger prints.  This is not for the purpose of doing automated facial recognition or finger print recognition, but for the purpose of having a database of people's faces and finger prints so that they are physically tied to their digital certificates.  Anyone can purchase an unlimited number of domains and set up corresponding email servers to qualify for basic level certificates.  But would you really want to buy anything from that domain or trust them with your money?  Of course not, you would want a face and finger print attached to their official business name and license, in addition to requiring that they take adequate measures to protect their private keys with strong cryptographic modules.  All of these types of physical validation could be performed, and digitally signed by a digitally enabled notary at a relatively low price.  These notaries themselves would have to undergo even more rigorous verification and identification, and their own faces and finger prints should be on record with the entities that regulate notaries so that they are legally accountable and traceable to anything that they sign.  Any time a finger print or facial photo is untraceable to a domain that commits fraud, the notaries that signed them instantly become suspect.  When processing a request for a maximum level certificate, the two root CAs will each appoint their own notaries in the vicinity of the applicant.  The notaries would visit the actual premise of the applicants and require the applicant to produce the proper credentials.  The fact that the notary actually sees the premise helps confirm the actual location of the business or organization.  All they would need is to bring a digital camera and they can take traditional paper based finger prints that can be scanned in a flatbed at a later time.  Now I know there are lots of people and countries that may have privacy concerns of having their photo and finger print taken, but I have a solution for that as well.  The actual photo and fingerprint digital files could be encrypted against a public key of a government entity.  The photos and fingerprint will be in the root CA's database in an encrypted format that can only be opened by a legal subpoena in a criminal investigation.  That would essentially eliminate any privacy concerns because the photo cannot be viewed short of a court order, and it would give law enforcement a convenient and reliable tool to track down anyone who abuses or commits fraud with their digital certificates.  This may seem a bit extreme and troublesome, but it certainly is a lot simpler than obtaining a driver's license or business license.  I don't believe this is too much to ask if a company wants to code sign or handle customer's money on their websites.  This is just a one time process that cover's an entire domain for five years.  It would be impossible under the current system if you had to do it for each and every host or email address every year.

Final words
To sum it all up, the purpose of this paper is to stimulate thought and initiate a debate on the merits or flaws of my proposed concept for a new PKI standard.  Like I said, this paper is entirely original and was conceived independently, but I cannot guarantee that this is the first time this concept has been proposed.  This proposal is designed to solve the major deployment obstacles with our current PKI System, which is cost, too many root certificates to secure, and a lack of a good CRL system.  I hope those of you who are experts in this field will give me some feedback whether it is positive or negative.

Send me a note