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-----