http://www.seclab.com/freeserv/mbox/mbox1998/Dec/msg00018.html -----Forwarded message from Dan Geer----- To: cryptography@c2.net Cc: dtd@world.std.com Subject: Re: DCSB: Risk Management is Where the Money Is; Trust in Digital Comm Date: Wed, 11 Nov 1998 23:25:16 -0500 From: Dan Geer Dear Annoymous , I refer you to a paper by Don Davis, "Compliance Defects in Public-Key Cryptography", Proc. 6th Usenix Security Symp, (San Jose, CA, 1996), pp. 171-178 which you can retrieve from http://world.std.com/~dtd/compliance/compliance.ps After some further discussion with Don, a long time colleague of mine, I forward to you his rejoinder in lieu of my own. --dan -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- >> The full cost of revocation testing is proportional to the square of >> the depth of the issuance hierarchy. > >The first statement is false. Revocation testing is not proportional to >the square of the depth of the issuance hierarchy. If you had, say, a 5 >level deep issuance chain, you do not need to check 25 revocation lists. >You only need to check 5. i'm sorry, gentle reader, but you are mistaken. you see, we are making an obvious assumption that you, like most of the industry, have missed: revocations will not, in general, be handled by CAs. this is an obvious assumption for several reasons: * large-scale financial applications demand prompt revocations; * no CA yet offers prompt revocations; * no available CA software supports prompt revocations; * CAs are inherently off-line by design, while revocation authorities must be highly-available; * as scaling problems, certificate issuance and prompt revocation are inherently and radically different. so, there's no reason to expect a single organization necessarily to fulfill both tasks. we assume that when revocation-checking service becomes generally available, it will be provided by a plethora of revocation-authorities, just as many CAs propose to issue certificates now. we expect to see a wide variety of revocation authorities for the same reasons that inspired the creation of the various "root" CAs: * any software vendor who solves the "prompt revocation" problem will want to sell their solution repeatedly; * some organizations will want to run their own revocation authorities in-house; * other organizations will prefer to hire the problem out; * still other organizations will take up the business of selling up-to-date revocation information; * the problem of delivering timely revocation information to the whole network is probably too big for one company, for social, financial, and scaling reasons. in such a multi-rooted environment, we can reasonably expect to see several revocation-authorities handling revocations that pertain to a single root-CA's certificate tree. further, we should assume that these various revocation-authorities will sign their revocation-info with public keys that have been signed into certs by any of various CAs. the resulting heterogenous PKI is not the pretty picture that CCITT painted in the X.509 standard, but it seems inevitable. thus, to check that _one_ level of a certificate-issuance chain has not recently been revoked, you must either: * examine a revocation-list (if you don't need promptness), or * ask a revocation-list managing service. either way, each level gives you a new signature to check (from the revocation-list author), and thus a new certificate-chain to validate. these 5 new certificate chains for the pertinent revocation-services can all be outside your original 5-deep issuance chain. further, each link in these 5 revocation-related issuance chains must, in turn, be validated and revocation-checked. when the validation of revocation- authority certs is taken into account, one immediately finds that a certificate _chain_ becomes a binary tree of certificates, and that revocation-checking is indeed an explosively recursive problem: RA7 CA7 RA6 CA6 RA4 CA4 RA1 CA1 <-- Root-level \ / \ | | / | / \ / \ / \ / \ / RA5 CA5 RA2 CA2 \ / \ / \ / \ / RA3 CA3 \ / \ / \ / \ / \ / \ / user-cert for each edge in this graph, the validator must check one signature. for a 2-link chain, like "CA1 signs CA2's cert," 2 signatures must be checked. for a 3-link chain, like "CA1 signs CA2's cert, who signs CA3's cert," 6 signatures must be checked; for 4 links, as in the picture, 14 signatures must be checked; and for 5 links, 30 sigs must be checked. in reality, the revocation-problem will be sub-exponential in its growth, as dan says, because the number of higher-level authorities drops as we ascend the issuance and revocation hierarchies. when a certificate issuance-chain involves only one CA hierarchy and only one revocation hierarchy, as PEM's and X.509's designers originally envisioned, then this messy validation can be limited to linear growth, more or less as you observe. however, even Entrust's CA services offer only periodic revocation-lists, per X.509, which is not timely enough for fast/large transactions. neither Entrust nor its various competitors claim to offer fully timely verification that a certificate hasn't recently been revoked. as hard as the CRL-mgt problems are, they're dwarfed by the scaling problems raised by prompt revocation, and these scaling problems, as i mentioned above, will drive the net away from monolithic revocation-service. afaik, none of the pki vendors has acknowledged these complications that will ensue when several CA/ revocation hierarchies operate simultaneously. heterogenous certificate- chains, involving a variety of revocation-authorities and root-CAs, will be commonplace, and their validation will be complicated. >> this exceeds the intellectual capacity of most certificate recipients. > The second statement is nonsensical. Intellectual capacity is not at > issue. what exceeds their capacity is the real-time, seat-of-the-pants problem of deciding on the fly when/whether to stop checking the higher levels of the revocation-related certificate-tree, so as to check a certificate in real time. > Obviously checking for certificate revocations can be automated, > as can the recursive process of walking the certificate chain > and verifying each step. in the presence of heterogenous cert-chains, the ease of automating recursive revocation checks should not be taken for granted. >> ...threat to strong security apparati of having them undermined by >> key escrow. > > ...No proposal for key escrow asks for signature keys to be escrowed. > Only encryption keys are escrowed. Key escrow threatens secrecy but > not authorization. It is not an issue for electronic commerce. some very large commercial customers for authorization software _do_ want effective secrecy for authorization-certificates. it is important in those markets to keep a customer's access-rights confidential. similarly, some financial and securities transactions will legitimately involve parties who want strong privacy, or who even may legally be required to remain unidentified, at least temporarily. these kinds of confidentiality would be threatened by the escrow of encryption-keys. - don davis, boston -----End of forwarded message-----