E. Gerck, Ph.D.
Copyright © by the author, 1997
All rights reserved. Copying and partial citation allowed, with source citation.
This presents serious risks for commercial applications such as banking and sales, and for confidential data exchange between companies, lawyers and clients, technical development teams, parties in e-mail communication, etc. What is needed is a way to verify if an attribute really belongs to the other party -- such as a public-key -- so that two previously unknown parties could safely communicate for the first time. This is beyond the usual concept of user authentication, because the parties are considered previously unknown. Rather, it is a primary step called certification -- where specific procedures which compare references with measurements may allow a party to bind an attribute to an unknown party.
Certification is similar to the measurement of distance -- it cannot be absolute, one always needs a reference. If the reference is wrong, spoofed or falsified, the result will also be wrong. Of course, for distance one always has the Earth as a standard and easy reference for any measurement of height or length. But in the Internet, there is no equally free, independently accessed, common, faithful and worldwide reference for certification, available to all parties that wish to communicate. The reference problem in the Internet is thus void of a standard reference.
However, this paper shows that even though certification must depend on a reference, such reference can be either extrinsic or intrinsic, in the same way that geometry (i.e., the measurement of distances) can also be extrinsic or intrinsic.
This paper calls "extrinsic certification" all methods that are based on references that are extrinsic to the dialogue between the parties in communication. The extraneous factor can be a third-party (space-like dependency, such as the root-key from a trusted entity) or a previous event (time-like dependency, such as previous trust). All current and proposed certification methods are extrinsic, such as X.509, PGP, etc. It is shown that so-called "self-certification", with self-signed certificates, is also extrinsic.
To allow extrinsic references to be eliminated, a new definition of certification is derived from first principles -- where a third-party and trust are not involved. The paper proves that the new definition allows attributes to be assigned to entities, so that entities can be distinguished by their attributes. The new definition can be applied both extrinsically as well as intrinsically, allowing for a seamless connection between both cases, which leads to a combined case of certification. It is also shown that the new definition can be used for extrinsic certification in exactly the same way as the current definition -- which means that both definitions are equivalent for extrinsic certification.
This paper calls "intrinsic certification" the first new security design, which is based on references that are intrinsic to the dialogue between the parties in communication. Because they are intrinsic, such references must be verifiable or measurable by a party independently of the will or control of the other party or of any other party. Using concepts from Information Theory, this paper defines Secure Multiple Channels or SMC, which allow intrinsic references to be measured with an arbitrarily high degree of reliance, providing for intrinsic proofs.
In either case, a reference can also be objective (e.g., a public-key) or subjective (e.g., trust) -- the difference being not what the reference is but, rather, its dependence outside the realm of the dialogue.
This paper calls "combined certification" the second new security design, which contains all methods that use both intrinsic and extrinsic references. Here, the extraneous factors can be "learned" attributes, obtained from past events that were certified exclusively by intrinsic certification. This allows intrinsic certification to "bootstrap" extrinsic certification, with zeroth-order (i.e., without external dependency) extrinsic references being provided by memory channels in the SMC and by gauge-functions which allow for interoperation between different trust models.
The unique advantages of the two new security designs are also discussed, as well as their independence from any PKI (Public-Key Infrastructure) or CRLs (Certificate Revocation Lists). For example, intrinsic certification can provide a solution for Distinguished Names in the Internet, also a problem that has no standard reference and cannot be solved extrinsically.
The results are obtained as generally as possible, without reference to any actual protocol or implementation, for extrinsic, intrinsic and combined certification. However, the Meta-Certificate Proposal being reviewed by the MCG (Meta-Certificate Group) [MCG97] is indicated as an example of intrinsic certification when used as Asymmetric Meta-Certification. Also, Meta-Certificates provide examples of combined certification.
This is the second on a series of papers that deals with intrinsic certification
and its unique characteristics, after the first paper [Ger97a] presented
an overview of current certification procedures and pointed out the different
problems caused by external references that are always relative. Upcoming
papers will address questions such as the extension of accountability to
certification and the corresponding causal classification of entities,
different views on the intrinsic certification procedures, the implementation
of intrinsic certification as Meta-Certificates [MCG97], and other issues.
This paper is presented with an Introduction and eight Sections. Section
2 deals with extrinsic certification, so as to provide a perspective for
the presentation of intrinsic certification and, also, to allow a combined
mode to be better defined. Section 3 deals with a least set of basic definitions
-- defining various terms such as subject, verifier and enemies -- using
care so as to guarantee that the definitions are intrinsic. The definitions
are applied in Section 4 to arrive at a new definition of certification,
which is proved to be intrinsic, also showing that the new definition is
equivalent to the usual extrinsic definition, that depends on a trusted
entity and past events. Section 4 also presents an enhanced-extrinsic certification
mode, based on an evaluation of all certification decisions expressed as
a probability level that the certificate is true. Section 5 uses Information
Theory to advance the concept of Secure Multiple Channels (SMC) and their
use in intrinsic certification, showing also that SMC cannot be used in
extrinsic certification but can be used in combined certification. Section
6 uses the previous results, together with the definition of inheritance
in subclassing and the conceptual separation of the subject in a witness-object
(observable entity) and a reader-object (observer entity), in order to
arrive at an operational procedure of intrinsic certification. Section
6 also references the Meta-Certificate proposal, as providing an implementation
of the intrinsic certification design. Section 7 discusses the cases of
enhanced-extrinsic and combined certification and also cites the Meta-Certificate
proposal, as providing implementations of both certification designs. The
last Section presents a summary of the conclusions.
2. Extrinsic Certification
Certification is usually defined as "endorsement of information by a trusted entity" [e.g., MOV97] and as such is used in the Internet to provide certificates, which can be defined as a "machine-readable secure confirmation of certification". Here, secure should be understood as "free from tampering" -- e.g., guaranteed by cryptographic techniques -- and thus certification is strongly reflected in certificates, which can be publicly verified using the public-key received from the trusted entity [MOV97].
The word "endorsement" is employed in this paper in its "weak" form, with the meaning "copying as received" as used in the praxis [Ger97a], , .
In the usual terminology, the "trusted entity" is called the issuer and the information originates from the subject, being verified by the verifier. The information is received and signed by the issuer, with the certificate itself being delivered by the issuer to the verifier. Usually, the issuer makes no representation as to the validity or completeness of the information itself . The information may be any number of items, such as a public-key, a name, an e-mail, an authorization, a delegation, etc. and the endorsement may carry a limitation such as the usual validity period of the certificate. An overview of current methods can be found in [Ger97a].
Clearly, this allows users (the verifiers) to:
(1) verify the identity of the issuer (depends on previous knowledge
of the issuer's "root-key") and,
(2) accept or reject to trust the issuer (depends on previous trust),
and so, users are usually considered to be central in the process. In the majority of applications, if the issuer's signature is already in the file system, the certificate is accepted without user intervention. It is the user's responsibility to decide how trust was established and is maintained. If the user is more sophisticated, he may also recognize that it is his responsibility to verify the conditionals on such trust, as given in [Ger97a],  and .
However, even though users are recognized as "central" in the process of certification, we recognize in the above definition a world-view or an extrinsic view of certification -- which also depends on previous knowledge as given by (1) and (2) above. This extrinsic view materializes itself as a third-party entity that receives information from a subject, endorses it and then cryptographically signs and issues that information to a verifier. Reading this phrase makes it apparent that the central role in current certification procedures is not played by the verifier but by the third-party, that "receives, endorses, signs and issues" -- the verifier plays only a side role which is "central" only as the acceptance of the fait-accompli is regarded, essentially based on past trust on the third-party. Here, the world-view is relative or extrinsic in two important ways: in space (third-party) and in time (past trust).
Thus, "endorsement of information by a trusted entity" needs knowledge of two different types of relative references, the first quantitative and space-like, the second qualitative and time-like: (i) the issuer's "root-key" and, (ii) trust on the issuer, as represented by acceptance of the issuer's endorsement on the information, even if restricted [1, 2]. However, how are these two references established, in the first place? Previously and outside the realm of the certificate itself. This is called "extrinsic certification" because it depends on references which are extrinsic to the dialogue between subject and verifier. Examples of extrinsic certification are methods such as X.509, PGP, SKIP, etc. and protocols that depend on such methods, as S/MIME, SET, SSL, etc.
Extrinsic certification introduces obvious problems. First, it is almost impossible that any two unknown parties in the world (say, one in Asia and the other in America) will have certificates from trusted parties that both equally trust. This has led to very complicated hierarchical relative reference systems that are being planned worldwide, called PKI (Public-Key Infrastructure) [MOV97], which could allow two unknown parties to certify each other by providing mutually acceptable certificate chains to each other, based on trusting an unknown party if that party is trusted by a party one trusts. Yet, it is known [MOV97] that a PKI will never be objectively safe because of the basic limitation of being based on trust, which is, of course, subjective and differently evaluated by different persons. Also, a PKI depends on CRLs (Certificate Revocation Lists) [MOV97], which may present considerable and unpredictable delays when a certificate needs to be revoked [Ger97a], allowing invalid certificates to be unknowingly accepted.
Further, as stressed by the "web-of-trust" of PGP [PGP97], trust is not transitive -- if you trust one person it does not mean you must trust everyone that person trusts -- which casts serious doubts on any relative reference system based on trust, such as a worldwide PKI. Worse, the reader can easily see that trust is also not distributive [Ger97d] -- you may trust one person before she trusts your competitor but not afterwards -- which makes relative reference systems based on trust almost useless as they expand. Of course, for a small circle of friends or for a small community it works but it is not scalable beyond a limited (i.e., numberwise) and localized (i.e., spacewise and timewise) number of entries [Ger97a]. This is not an implementation limit, but a systemic limit of extrinsic certification [Ger97c] as a function of domain-size.
Besides, as recently reviewed [Ger97a], the certificates themselves can be locally revoked (i.e., canceled by the trusted party) but not revoked at the same time worldwide, can be spoofed (i.e., obtained with false data that seems correct), can be falsified (e.g., by collusion or by a fraud scheme), may not be accepted in another country or by competing businesses, have no legal warranty, etc.
When the issuer is the subject and self-signs the certificate-- which corresponds to self-signed certificates or "self-certification", one also needs two different types of relative references, the first quantitative and space-like, the second qualitative and time-like: (i) previous knowledge such as the subject's "root-key" or address and, (ii) trust on the subject, as represented by acceptance of the information form the subject. So, self-certification is also extrinsic. Solutions that are based on self-certification are thus by no means safer than certificates issued by a third-party.
Also, of course, no one can vouch for himself. If the parties are unknown to each other, such self-references have no logical base and imply a leap-of-faith.
2.1. A Deeper View of Extrinsic Certification, Part I
In order to better understand the concepts of intrinsic and combined certification, it is instructive to consider a deeper view of extrinsic certification. This Section will consider the influence of the external references, as part I of the study. Part II will be presented in Section 4.1, discussing the actual procedures and introducing methods that can be used to enhance extrinsic certification, after several needed concepts are formally defined in Section 3.
Extrinsic certification is called extrinsic because it depends on another person, a third-party, trust, or a root-key, or, in other words, because it depends on extrinsic references that are relative to events or data that have no relationship to the dialogue between the parties.
As already explained, the references may be space-like and objective such as a public-key or an address, or time-like and subjective such as past trust. Either way, this means that extrinsic references are relative in first-order (i.e., one step of relativity) to a third-party. However, the references themselves are not like "physical constants" that are just being copied by the third-party and can be independently verified, but they are also relative to actions taken, or not taken, by that third-party and by any other party in a chain of events or in a key hierarchy [Ger97a]. Thus, they must also be relative in second-order, and possibly in higher-order. The extrinsic references are thus always relative to second- or higher-order events, which are of course unknown to the parties in the dialogue -- which only observe zeroth-order events (i.e., zero steps of relativity or, their own) or first-order events.
As a consequence, the knowledge gained from extrinsic references is of such a nature that:
For example, suppose that Alice trusts 100% a CA -- this means that Alice knows the CA's public-key and trusts 100% the CA to correctly provide public-keys in certificates signed by that CA. If Alice receives a valid certificate for Skywalker signed by that trusted CA, and the signature is confirmed by her copy of the CA's public-key, still she does not know if: (i) the CA's private-key is compromised and the certificate was issued by someone else using the CA's key and name, (ii) Skywalker was impersonated by someone else to the CA and the public-key is not Skywalker's, (iii) the certificate has been revoked since it was issued, (iv) even if Alice checks with the CA before each use of the certificate in order to make sure that it was not revoked, Skywalker's certificate might have been revoked but the Certificate Revocation List did not arrive yet at the CA and, (v) several other cases as given in [Ger97a].
In consequence, the security design offered by extrinsic certification always depends on relative references that are based on ultimately unreachable assumptions -- which means that extrinsic certification between two parties cannot be objectively secure.
2.2. Can External References be Eliminated?
Thus, to avoid the extrinsic dependence -- which necessarily leads to unreachable assumptions -- an alternative would be to look for an intrinsic view of certification, which would not include external references in such a central role. In the quest for intrinsic versus extrinsic certification, as will be presented in this paper, we can profit from a close and direct comparison with intrinsic and extrinsic geometry in order to conceptually map our path, as first studied by Gauss almost 150 years ago [Sto69]. For example, intrinsic geometry allows the intuitive result of being able to recognize a sphere as such, and actually measuring its radius, without any need for an external reference frame.
The comparison between intrinsic/extrinsic geometry and intrinsic/extrinsic certification is more than a coincidence on names but is based on the fact that distance and certification are both relative measurements in metric spaces [Ger97e]. In the same way that there is no absolute distance, there is also no absolute certification. The parallels between extrinsic certification and extrinsic geometry allow us to think of key distribution (or certificate distribution) as providing a "metric space" for certification, as explained by the author of the following excerpt taken from mailings to the mcg-talk list:
"The systemic purpose of key distribution is to provide a "metric space" whereby many procedures, which handle certification chain(s), may be (multiply) used to measure whether a given asymmetric key pertaining to an end-user is indeed useful, or not. The metric is an expression of relative certainty for a specific security problem, and application context, given all available knowledge of the operational vulnerabilities." [173447/97].
This commentary, however, would not apply in the case of intrinsic certification, because -- like intrinsic geometry -- intrinsic certification would not depend on an extrinsic "metric space" to identify itself. In the same way that a surface can be measured and identified intrinsically, without an external reference frame, this should also be possible for certification.
This phrase, by itself, is the basis of a mathematical proof that intrinsic certification exists and is pursued elsewhere [Ger97c]. Here, the demonstration that intrinsic certification exists will follow a derivation based on first principles of Information Theory, which allows an easier comparison with implementations.
To look for the possibility of intrinsic certification, it is necessary first to arrive at a different definition of certification, which must be world-independent. This means that we need to cast a fresh look into the complete set of hypothesis, objectives and definitions.
Finally, it is important to note that extrinsic certification procedures
by themselves, such as using cryptography to verify a signature, are reliable
and secure if correctly designed (i.e., proper key-lengths [MOV97], proper
validity ranges [Ger97a], etc. ) as analyzed in Section 4.1. The problem,
that cannot be solved extrinsically as proved, is the reference or, the
This paper deals with machine-readable certificates, which means that the subject or the verifier are provided as machine-executable entities, defined by:
subject or verifier: general sets of objects, which can contain anything that may be computationally processed and are themselves provided with computational resources that allow them to process data and to communicate between themselves and with other objects. They can read and write files, can read certificates, use cryptographic keys for encryption and decryption, calculate signatures, etc.
The definition of "secure" was already advanced in Section 2 and plays a central role in certification. However, secure must not be confused with private, because they address different aspects of certification. Certification always begins in the "open" (i.e., in clear text) because the two parties are unknown by hypothesis and cannot rely upon shared knowledge -- as will be further defined in this Section. Thus, certification must begin as a process that is not private (i.e., the data exchange is or can be public) but must be secure, so an attacker could not influence that certification event or even future events, by impersonation or other attacks . The full definition to be used in this paper is [cf. MOV97]:
secure: free from tampering, within the limits of Complexity Theory.
It is important to analyze this definition. If a process or message is "free from tampering", it does not mean that it is "free from any external actions" but means that it is not possible to penetrate, interact, influence or change the process or message in any way that is not allowed. Here, the words "not allowed" mean that the protection against tampering is specific and depends upon the threat model used in the security design, as dictated by the design goals. This means that attacks might still be possible if not prevented by the security design. For example, reading a message or replaying a message might not be relevant for a process -- such as the implosion of a building. On the other hand, if the process must be secure also against a replay attack, such as the opening of a vault door, then the process could be designed with a timestamp or a serial number that are cryptographically signed, which signature is always checked at the receiver end. A good security design must use algorithms that prevent all attacks that could jeopardize the design goals, according to a conservative threat model, without incurring the cost of preventing attacks that are clearly impossible or unimportant.
Further, the definition does not include absolute barriers that imply 100% security -- which is not possible [MOV97]. The words "free from tampering" do not mean an absolute warranty but, as usual [MOV97], within Complexity Theory limits. This means that even if the attacker has very large computational resources, that increase asymptotically according to a polynomial law, still it would not be possible to tamper with the secure process. Finally, "free from tampering" also means "according to the design goals" as already explained, so the process or message is secure within the presumed threat model -- but may fail to be secure if the threat model or the choice of algorithms are wrong or unsuspectedly weak, or if the threat changes.
It is also important to define "private", so as to have a clear distinction between private and secure. Here, private means the usual concept of "free from eavesdropping" [MOV97] or "free from unauthorized reading". This, of course, does not mean that the message cannot be copied, compared or listened to, but that it cannot be deciphered or understood. Also, this does not mean that it cannot be spoofed, forged, deleted, influenced, replayed, changed, written to, etc. For example, if an attacker would repeat a private message that opens a door, even though the message is not understood by the attacker it could open the door a second time. This would also be spoofing if the attacker uses the granted access. Also, an attacker could change a message by adding a part of a former message. In these cases, if such attacks are important and may compromise the design goals, the security design cannot rely on private messages alone but must use secure processes that will protect the system against such attacks. Again, "free" is used in the context of Complexity theory, as usually provided by cryptography. The definition is:
private: free from eavesdropping, within the limits of Complexity Theory.
On the implementation level, cryptographic techniques -- when applied with well-designed parameters (e.g., key-length, validity date, timestamps, nonces, etc.) in a security design that takes into account a suitable threat model -- can make a process secure within Complexity Theory limits [MOV97]. In the same way, cryptographic techniques can also make a process private within Complexity Theory limits [MOV97].
This paper will extensively use concepts from Information Theory [Sha48], which will be defined as they are used. The first concept is information itself. In Information Theory, information has nothing to do with knowledge or meaning. In the context of Information Theory, information is simply that which is transferred from a source to a destination, using a communication channel. If, before transmission, the information is available at the destination then the transfer is zero. Information received by a party is that what the party does not expect -- as measured by the uncertainty of the party as to what the message will be. Thus, messages "with no surprises" carry no information. For example, the same message "name N has public-key K" may carry information if it was not expected, or no information otherwise. Thus, the definition of information to be used in this paper is:
information: a message received by a party and which was unexpected by the party
Now, it is important to note that information, or the amount of information, depends only on the message uncertainty, rather than on its actual content, possible interpretation or, even if it is already known or not to the party. So, the phrase "information received by a party is that what the party does not expect" does not mean that the party does not believe or has no knowledge about the content of the message. For example, the message "name N has public-key K" may carry information to a party even if the party knows with certainty that N has public-key K, as given in a large directory of names and public-keys, because after the message the party knows that the other party also has the same data. Further, the message "45AB65", which has no meaning for a receiving party, may still carry information because after the message the party knows that there is another party on the communication channel. Thus, we must next allow for a classification of the message's content, because if the message carries information then we may act differently whether we believe on this information or not.
In relationship to the information received by a party in a dialogue, we will use the words "assumption" or "knowledge" in order to classify the message's content in relationship to the degree of belief that the receiving party assigns to it:
assumption: the message has a degree of belief that is not acceptable to the party.
knowledge: the message has a degree of belief that is acceptable to the party.
Note that such classification does not depend on trust but, rather, on a quantitative degree of belief similar to the belief function of Dempster-Schafer [DS97], which will be defined here as:
belief: the probability that the evidence supports the claim.
For example, the message "name N has public-key K" may be an assumption even if the party has that entry in a directory, because he does not know if N changed her public-key K after that directory entry was entered and so has no evidence to support the claim -- which leads to zero belief. But, if the message "name N has public-key K" is the correct decryption from a message, using the public-key K, then that message conveys knowledge (within cryptographic limits of near 100% belief) that the other party has the corresponding private-key K' and an assumption that the other party is N (because there is no evidence that K' is in the possession of N, which leads to zero belief).
The basic hypothesis of intrinsic certification is that it must allow the "verifier" (which is the party that gathers assumptions, e.g., a program) and the "subject" (which is the party that issues the assumptions, e.g., also a program) to conduct their information exchange without any knowledge common to each other -- which may represent a set of root-keys, mutual trust, trust on the same third-party, or any relative reference that is known in common. Further, we must not allow any dependence on previous knowledge that is not common to each other but which may provide links between verifier and subject -- e.g., something that one does not know but knows the other knows, such as the subject knowing that the verifier trusts a specific third-party that he does not know.
As a consequence, trust or mutual trust must be considered non-existent if certification is intrinsic. Again, that is why so-called self-certification or self-signed certificates are extrinsic.
Note also that we only have two parties in the dialogue: the subject and the verifier. There is no "issuer" involved -- because the declarations are jointly-issued by the subject and verifier (see Section 3.1.2, on shared liabilities, and Section 6 on Intrinsic Certificates) -- otherwise an external dependence would be introduced at the start. Thus, intrinsic certificates are considered "jointly-issued" because they depend on a cooperative effort between subject and verifier. Here, it is important not to confuse such "jointly-issued intrinsic certificates", which do not depend on trust on the issuer or on any previous knowledge from the issuer such as a public-key, with "self-issued extrinsic certificates" which depend on previous trusted knowledge on the issuer, as already discussed.
We must, of course, allow a party to have previous assumptions in two cases: (i) if it is an assumption for any party or, (ii) if it is not knowledge to the party. For example, the verifier may have an IP address and an e-mail address which it wishes to use to test, in order to see if they belong to the subject. To the verifier, this is an assumption but it needs it in order to have a starting point. Therefore, such assumptions constitute questions -- not answers. Also, the verifier may know (i.e., have knowledge about) its own e-mail address with certainty but the subject does not know it even though it may have assumptions on it.
The important point here is that both verifier and subject are generally assumed to be unknown to each other and they will have no firm knowledge known to each other as such -- even though a common body of assumptions and knowledge may unsuspectedly exist and, even though each one must have their own body of assumptions and knowledge that each one is aware of by itself.
The above exposition can be easily visualized using set theory, using general objects as members of the set, where knows is used in the sense of "have knowledge of". Suppose: (here, it is assumed that V and S may also exchange roles so that S may certify V)
Thus, verifier and subject are respectively represented by the ordered sets of objects V:(A,B,X) and S:(C,D,Y).
It is easy to see that the basic hypothesis above do not establish any
link between V and S, implicit or otherwise. This is expressed by the fact
that X and Y are empty.
This Section will allow the basic definitions to be used for direct specification of the concepts needed in this paper, such as Certification, Certificates and Distinguished Names. These concepts will be defined without any external references -- which will allow their application to any type of certification procedure: extrinsic, intrinsic or combined.
When V enters in a dialogue with a subject and the subject claims to be S, there are two questions that V must answer: (i) who is S? and, (ii) is S the subject? Of course, these questions are in a logical sequence but they are otherwise independent. To answer these two questions, is the objective of certification.
First, however, we must observe that neither question can be answered with 100% certainty for two unknown parties. Clearly, 100% security does not exist. Thus, both questions must be answered with a pragmatical attitude, i.e., with a degree of belief that is acceptable to V and according to her risk/cost analysis and available resources.
Certification, thus, must proceed in two steps:
As discussed elsewhere [Ger97c], this leads to the notion of certification as a "cognition process" followed by a "recognition process", rather than the two steps as a "recognition process" . If certification would be based exclusively on recognition, it would always depend on extrinsic references.
Thus, using the terminology of the former Section, we can understand certification as divided in two steps:
These two uniqueness requirements can be expressed by a single "if and only if" condition: X is a reference for S if and only if X allows S to be distinguished from any S'.
Several requirements must now be introduced to guarantee such uniqueness, mainly as a function of malicious interference which can jeopardize the communication channels in several ways, from the beginning of the dialogue .
3.1.1. The Enemies
We will assume that there are any number of malicious subjects, henceforth called "enemies" -- Ei -- that will also have the same structure and capabilities as V and S, being defined by the sets Ei :(Fi , Gi, Zi).
The enemies will actively try to influence both steps of certification, i.e., the set X and its use, in any number of different ways, such as: (i) will try to be perceived as S, but producing a different set X, (ii) will try to be undistinguishable from S and produce the same set X, (iii) will try to deny certification to S so that X remains empty, (iv) will try to eavesdrop on the communication channel between S and V and will try to use that information in an unauthorized way, etc. The reader is referenced to [MOV97] for a list of possible attacks.
The next study of certification in general will suppose that the enemies must be accounted for. Effective tools to deal with any type of enemy, affording an arbitrary degree of reliance, will be discussed in Section 5.
3.1.2. Distinguished Names
The first question of Section 3.1. was "who is S?", which has to be answered with a name-like attribute. Of course, if we use natural names we will not go very far before a similar name is found in the world population. Thus, to allow for programs (i.e., verifiers, subjects, etc.) to deal with entities in the Internet, it is necessary to have a "naming convention" that may allow a unique and singular name to be used for each entity -- which is usually called a "Distinguished Name" or DN. With DNs, it would be possible to uniquely associate entities to contract numbers, accounts, etc., without requiring the account numbers, etc. to be also unique. The problem is that there is no naturally found DN for each member of the human race, computer, machine, etc. Of course, if such a DN existed, then the reference problem in the Internet would also not exist. But since the Internet is void of a standard reference as we saw in Section 1, this means that the DN question has also no extrinsic solution.
Various standards, e.g., X.500, X.509v3, have proposed different schemes to generate unique names for entities in the worldwide Internet, also using e-mails, SSNs, etc., with various difficulties [Ger97a] and all dependent from extrinsic references -- of course, repeating the general problems already discussed in Section 2 and which have no general solution. This Section presents an intrinsic solution for a worldwide DN, which can be applied without hierarchy or central control of any kind and which has the further benefit of being automatically accepted by the parties in the dialogue -- which can be authenticated in a proper non-repudiation [MOV97] protocol as shown here.
Given V:(A,B,X) and S:(C,D,Y), V knows nothing about S and this is represented by an empty set X. If S wants to be certifiable he must communicate -- which means that he must make himself at least partially known to V. Thus, S allows a subset of S to be measured by V and V performs the first step of certification as in Section 3.1. -- i.e., S is certified by V. Afterwards, the set X is no longer empty. The set X now contains objects that V knows by herself (i.e., are contained in B) and that V knows are contained in D, the set that S knows. Thus X is the set of knowledge that V knows is common with S.
However, this is not enough to distinguish S from other subjects (e.g., the enemies) which may provide to V the same set X, and also does not allow X to be unique. Thus, the two uniqueness requirements of Section (3.1.) are not yet fulfilled. Here, V and S must also agree that X should provide a one-to-one relationship with S that can be measured by V without any influence of other subjects, even for repeated events. This means that V and S accept that any subject that has the same set X will be equally certified by V, i.e., they are equivalent to both V and S.
The above statement implies that a shared liability exists, because S is responsible to provide a "good enough" set X to V as representing his view of equivalency, while V is responsible for accepting a second and possibly differently evaluated "good enough" appraisal of X as representing her view of equivalency. Of course, such shared liability must be expressible, taking into account that V and S are unknown to each other.
This paper will express this shared liability by the expression "designation of X to S":
designation of X to S: S will bind X to S, and V will accept such binding, in a such a way that V can distinguish all assignment possibilities of X in relationship to any subject and always assign X to S.
This definition is equivalent to the proposition "S will bind X to S, and V will accept such binding if and only if V can always assign X to S".
Here, to perform the designation of X to S, subject and verifier must independently apply the law of Requisite Variety [Krip97], i.e. "the amount of appropriate selection that can be performed is limited by the amount of information available" -- which implies that if X is too large then information might be wasted but if X is too small then the lack of information results in arbitrary decisions when distinguishing the subject from other subjects. Of course, the question of "what is like versus what is unlike" depends on V, S and the other subjects, but the objective of the designation is: "designation must make it possible to accept like subjects and reject unlike subjects".
The designation of X to S must also be secure, so that another subject might not influence its outcome or even future designations, with the following main requirements: (i) S must not allow X to increase until X = D, but care must be exercised so that X < D even in accumulated and unrelated events, otherwise an enemy that certifies S or eavesdrop on the communication channels would obtain the complete set of knowledge of S -- i.e., D -- and could easily impersonate S, (ii) information from D - X must necessarily be used in the certification, otherwise an enemy that has only X (i.e., any subject) could easily impersonate S. Further requirements depend on specific threat models and may be more restrictive. Note that the above security requirements do not depend on cryptography, but are enforceable by design.
However, the designation of X to S can never be obtained with 100% certainty for two unknown parties, as remarked in Section (3.1.). Thus, a pragmatical attitude must be sought, i.e., which provides a degree of belief that is acceptable to V and according to her risk/cost analysis and available resources. Here, it is important to introduce the concept of "process", as an intuitive notion that allows the output of a system to be defined as a function of its input, i.e., the process receives inputs and produces outputs. The process can have memory, which is a special type of output that serves as input at a later point in time. Memory allows a process to produce different sets of outputs when presented with the same set of inputs at different times, because the outputs will depend on the historical sequence of inputs. In any case, the outputs of a process depend only on its inputs and its memory. So, the outputs are 100% repeatable for the same set of inputs and memory, at any time and place.
Viewing the "designation of X to S" as a process, it is easy to recognize that it must occur within a "process boundary", accepted by the verifier. Thus, the verifier controls the execution of the process and defines its termination, when the outputs are computed. The process boundary is limited either by available resources, by available cost or by any other limit such as time, effort, etc. This introduces a type of "practical limit" defined by the verifier, which must be followed in any real case, of course. For example, this limit could be the desired degree of belief -- which must be reached before the process is terminated by the break-even point between cost and risk. It does need to concern us here, i.e. what the limit is, but we must include in the statements the recognition that the process has to obey a "process boundary", which can be extrinsic or intrinsic as needed.
As a secure process that allows a degree of belief to be reached, the designation of X to S can now be viewed as the certification of S by V. This completes the first step, the cognition of S, starting from an empty X:
Certification of S: a secure process for the designation of X to S, within a process boundary
and the certificate itself can be defined as a "secure wrapper" or "protection" for the transport and use of X, using standard cryptographic methods:
Certificate of S: a secure wrapper for X, after certification of S by V
Now, we recognize that the definition of the "designation of X to S" -- which is "S will bind X to S, and V will accept such binding if and only if V can always assign X to S" -- means that X is like a "Distinguished Name" for S, i.e., a unique and singular name that identifies S to V. Better still, proposed by S and accepted as such by V in the certification process. This affords an intrinsic definition of a DN, explicitly accepted by the parties in the dialogue -- i.e., V and S:
Distinguished Name (DN): X, after certification of S by V
This definition of DN is independent of the certification method for S and may easily allow the use of a guaranteed general unique DN in applications such as databases, bank accounts, purchase orders, etc. As a more compact general DN, a subset of the DN can also be used (e.g., a hash) if so agreed between the parties. This means that the DN is not just a field in a certificate, that is presumably unique, but is the content of such certificate -- which is explicitly accepted as unique.
To allow this acceptance by V to be expressible to S (since it is already accepted by V, it is already expressible to V), the set Y of S may store a signature of V or any other protocol requirement, in specific procedures.
3.1.3. First Step Of Certification: Cognition
The first step of certification of S is the step of cognition, which begins with no previous knowledge about S. It is when "S is certified by the verifier" and a unique reference to S is obtained. This reference is the set X, the Distinguished Name for S as accepted by V and already defined in Section (3.1.2.).
The first question is thus answered. Who is S? S is X.
3.1.4. Second Step Of Certification: Recognition
The second step of certification is the step of recognition, when V uses X in a measurement procedure with a trial subject and verifies if she can recognize S. The second step is based on the question: Is S the subject?
This can happen in several different ways. Of course, the least interesting way would be to repeat the first step and check to see if the same set X is obtained. Such a procedure would neither leverage on the knowledge gained on the first step, nor would it allow a "learning process" that could benefit from experiment.
Instead, cryptographic techniques [MOV97] can be used by V with X, to allow for a secure direct answer to the second question. For example, if S has a private-key K' and sends within the set X the corresponding public-key K, then it is easy for V and S to establish a protocol that proves whether S has K' or not.
This means that the Distinguished Name of S -- X -- allows S to be uniquely recognized.
3.1.5. Generalized Certification: Cognition and Recognition
The first step of certification allows the certificate X of S to obtained by V. The second step allows V to use X and directly verify if a trial subject is S. Both steps can be implemented as secure processes, as discussed.
To summarize the results of the previous section, the main set of definitions is:
Certification of S: a secure process for the designation of X to S, within a process boundary
Certificate of S: a secure wrapper for X, after certification of S by V
Distinguished Name of S: X, after certification of S by V
These new definitions are the central result of this Section, which purposely leaves open how or who executes the process, which can lead to extrinsic, intrinsic or combined certification -- as will be dealt with in the next Sections.
The new definition of certification is equivalent to the definition "endorsement of information by a trusted entity" because the "secure process" in the new definition is executed by the issuer and by the verifier in the current definition -- when the issuer receives, endorses, signs and distributes, while the verifier checks the signature and trusts the issuer -- which leads to the designation of the information to the subject, or the binding between X and S. The certificate itself is also equivalently defined, because the new definition provides for a secure materialization of certification -- as a secure wrapper for X.
It is important to note that the above definitions include -- also for extrinsic, intrinsic and combined -- the so-called "attribute certificates" or "role certificates", where neither V nor S attempt to uniquely distinguish S in contrast to other subjects, which means that the attribute X may not be unique to one subject . Without loss of generality, this paper will not consider this case further, because it is contained in the definitions above, if V and S so agree.
The definitions are neither extrinsic nor intrinsic. The next Section
will illustrate the different possibilities and show that the new definition
of certification is equivalent to the usual definition for extrinsic certification.
In all cases, the subject has to allow herself to be known. Let us suppose that the subject has previously made available public communication channels that allow a verifier to obtain information on the set X, which the subject has prepared with a satisfactory (to her needs) degree of belief that such set X will allow a verifier to distinguish between herself (i.e. the subject) and any other subjects (e.g., enemies). Also, the subject will use X < D in such a way that possession of X or continuous eavesdropping of the public communication channel will not allow any subject to impersonate S, with a degree of belief that is satisfactory to the subject. The communication channels can be: a CD-ROM published by the subject and which contains her public-key, the subject's personal Home-Page on the Internet with her public-key and e-mail, her e-mail footer with the address of her Home-Page where her public-key is available, the subject's PGP public-key with a series of signatures chosen by her and which is available in many sites in the Internet, a X.509 certificate issued by a CA with the subject's public-key and available at the subject's Internet site, etc. Further, special objects called witnesses and which will be used for intrinsic certification can also be publicly available: at her Internet site, at a CA, in a CD-ROM, in a book, in an e-mail, by fax call-back, etc.
4.1. A Deeper View of Extrinsic Certification, Part II: Enhanced Extrinsic Certification
This Section deals with enhanced procedures for extrinsic certification. Because several applications in use today have serious implementation flaws [Ger97a], which may be confused with conceptual problems which also exist as reviewed elsewhere [Ger97a, Ger97c] and here (Sections 2 and 2.1.), it is important to distinguish between both so that extrinsic certification can be safely used in enhanced-extrinsic or combined certification procedures. By "enhanced-extrinsic certification" we mean extrinsic certification based on a "quality level", which may be very low for a certificate that affords low security or very high otherwise. This is in contrast with current "take it or leave it" certificates such as X.509, which omit the intermediate trust evaluations to reach the final result -- which is simply a "yes/no" decision.
To begin, subject, verifier and certificate must be considered as unitary in their immediate environment. In X.509, for example, the certificate is embedded in an application that provides computational resources and communication capabilities -- i.e., the verifier, which is an object. This paper considers such unity important, because certification and security depend on both, of course. If a certificate is false but the verifier is (or, uses) an application that does not conduct the needed explicit and implicit verifications of the certificate in a correct way, then the certificate may be accepted as true.
The discussion will accommodate both cases of extrinsic certification, i.e., certificates that are self-issued or certificates that are issued by a third-party. All problems already discussed in Sections 2 and 2.1. (e.g., assignment of trust, second-order references, lack of transitive and distributive properties of trust, CRLs, etc.) -- and which may have very strong influences on the outcome of certification -- will be ignored at first.
The two steps will need a total of 9 procedures. Each procedure may involve multiple tasks, but all in the same level of execution. There are a total of eleven variables -- as a minimum. Other assertions are ignored for simplicity, such as whether "the issuer's root-key has not been revoked".
In the first step of certification, the verifier has to obtain X and designate it to S. This will need the following least number of procedures, where we note that procedure (5) is unfortunately ignored by several applications [Ger97a]:
With the successful completion of procedure 8, the verifier has received and verified the certificate as acceptable. Now, with the second step the verifier will use the certificate to actually certify the subject:
To answer these questions, instead of following the above procedures taking immediate decisions in each procedure and absorbing the uncertainties in each procedure, we may recognize the procedures above as providing a conditional decision chain. This chain is based on two external references and nine assumptions -- with a total of eleven decision elements which are all considered independent (i.e., they can be independently modified), equally important and equally relevant (i.e., the elements are connected in series in a such a way that failure of one element represents failure of the chain). Belief (i.e., a probability measure as defined in Section 3) on the whole chain (i.e., the subject S' is certified as S) is therefore the product of the degree of belief in each element. Unless each degree of belief is 100%, the total degree of belief will be smaller than 100%, of course.
The importance of this fact cannot be overstated. For example, consider a best case: (i) V trusts a third-party 100%, (ii) that third-party is the same issuer that S has chosen to trust 100% and, (iii) the issuer also provides address certification. Then, the number of decision elements is reduced to seven (a best case example, with several further hypothesis) and there are no decision elements that do not depend on the trusted third-party. Still, because S' can be 100% untrustworthy and in the normal course of events the third-party may make more than 0% of mistakes, V must take into account that the following decision elements are still important:
Of course, if the trusted issuer is not the same for V and S (which, of course, has a higher probability for two unknown parties in a large community such as the Internet), then the total belief can be much smaller. In fact, it can be zero if we accept that trust is neither transitive nor distributive as pointed out in Section 2.
However, it is important to realize that such low degrees of belief depend on the fact that the eleven decision elements depend on first- and higher-order relative references, evidenced by the expressions "S' says ...". It has nothing to do with the process of extrinsic certification itself, which did not add other uncertainties to the ones already described in Sections 2 and 2.1. So, if we are able to assign a high degree of belief to less decision elements connected in series, or if we can add parallel-connected elements, then a higher total result is possible.
The procedure outlined in this Section allows enhanced-extrinsic certification to be defined, where different certificates may be ranked by their total beliefs as evaluated by a verifier as a function of risk/cost -- instead of the current "yes/no" result.
4.2. Generalized Certification: The Seven Phases of The Certification Process
Certification is always based on measurements, whether extrinsic or intrinsic. The difference between both types is the reference dependence in relationship to the parties in the dialogue. This Section will apply the new definition of certification presented in Section 3.1.5. and introduce a conceptual model for the certification process in general. The model will expand upon the two steps of certification already discussed in Section 4 and used in Section 4.1., presenting seven phases, where the first step is divided in six phases and the last step is one phase.
In step one, the verifier has to obtain X and designate it to S:
Before intrinsic certification can be defined, measurement and communication
tools are needed for all phases above, as the next Section will provide.
With extrinsic certification, the solution is to ask a trusted third-party for references (extrinsic, such as keys, trust, etc.) that may help solve the problem, for (i) and (ii). With intrinsic certification, the problems (i) and (ii) must be solved intrinsically, of course.
To solve the problems (i) and (ii) we note first that X is, in Information Theory, a signal -- because it is wanted and unknown. We also note that the Ei are, in Information Theory, noise -- because they are random, unpredictable and they interfere with the signal [Car75], [Krip97], so we have:
Also, from Information Theory we need the concept of channel, as that part of a communication chain in which signals are transmitted from a sender to a receiver. A channel involves a single physical medium that spans the difference in time and in space which separates senders from receivers. A memory is that special case of a channel in which the sender transmits signals to itself at a later point in time. Memory channels can be used to provide for "learning" capabilities in certification.
And now, to reduce noise and thus increase the signal to noise ratio -- so that the reliability is increased -- we need different channels of information, as intentional redundancy. To paraphrase Krippendorff [ cf. Krip97]:
Redundancy: The variety in a channel that exceeds the amount of information actually transmitted. Its most common forms: (1) repetitive transmission of the same message over one channel, (2) duplication of channels, of which each could handle the transmission by itself, (3) restrictions on the use of characters or on the combinations of characters from an alphabet, in order to form proper words or expressions, (4) communicating something already known to its addressee. In the process of communication, redundancy is essential to combat noise, to assure reliability and to keep a communication process in operation in spite of interference. English writing is estimated to be 50% redundant which accounts for the ability of native speakers to detect and correct typing errors. Parity checks, which are common in communication within computers, enhance reliability at the expense of using additional channel capacity. Similarly, Hindu governments of the Mogul period are known to have used at least three parallel reporting channels to survey their provinces with some degree of reliability, notwithstanding the additional efforts.
This means that with the addition of redundant channels (independent real-time sources of information) we may expect to reduce noise. In fact, this is Shannon's Tenth Theorem, which we quote here in the form described by Krippendorff [Krip97]:
"With the addition of a correction channel equal to or exceeding in capacity the amount of noise in the original channel, it is possible to so encode the correction data sent over this channel that all but an arbitrarily small fraction of the errors contributing to the noise are corrected. This is not possible if the capacity of the correction channel is less than the noise."
In order to make this concept useful for certification, some constraints must be introduced -- represented by the words "a correction channel equal to or exceeding in capacity", "to so encode" and "data sent over this channel".
Of course, the channel needs to be secure -- otherwise a series of attacks such as man-in-the-middle , replay, etc. could be easily set-up -- but may not be private.
Also, the channel must be chosen in an independent way and may be multiple, otherwise it would not be possible to guarantee that it can correct any error, nor would it be possible to guarantee adequate capacity -- which may be provided by several channels.
The data sent over the channel must also have a "time quality" so that it is neither old nor out of synchronism with the expected correction. Here, the concept of "real-time" must be introduced and exemplified. It is important to note that real-time does not mean immediate, but can be defined as:
real-time: an attribute that pertains to a data collecting system which controls or measures an on-going process and delivers its outputs (or controls its inputs) not later than the time when these are needed for effective control or measurement.
Alternatively, real-time is: two events are called in "real-time" if the passing of time cannot be perceived by the system that depends on or controls the two events. So, if a channel has information that represents the current headline of a daily newspaper then an update period of 24 hours would be "real-time". Also, if a channel has information derived from access to data processed by a smart-card, then an update time of a fraction of a millisecond would be "real-time". Regarding memory channels, note that "real-time" is still a valid restriction, enforced by validity periods of the memory.
Therefore, the concept of real-time is an essential feature, because "noise" (spoofing, collusion, forgery, error, etc.) is a function of time and, thus, a fixed-statement or fixed-arrangement of data sources may be subject to "adaptive noise" -- which would mean that "noise" could contaminate the measurement by adapting to its fixed defenses, either automatically by itself or driven by an outside system (human or otherwise).
Also, predictable delay is important -- which means that the real-time channel is being supervised, as by a faster timing mechanism, so as not to be fooled by a faster attack (a "flash" attack), by a replay (a "midnight" attack) or simply outdated by a wrong update cycle. For example, in the first example of real-time given above, it is important that the real-time update on a 24-hour period does not happen 30 minutes before the newspaper is regularly issued.
With these concepts and those from Section 3, Shannon's Tenth Theorem can be applied to define the concept of "Secure Multiple Channels" or SMC:
Secure Multiple Channels (SMC): independent multiple channels that provide resources for secure communication, with predictable delay on real-time
Thus, SMC provides resources for the exchange of data, methods or their binding, allowing for dynamic content, information processing and communication with outside sources of information.
Therefore, to reduce the influence of enemies -- i.e. noise -- the solution is not to increase the number or type of information from the same source or channel (i.e., it would not help to get the same wrong result many times over or, many different wrong results from the same compromised source) but to increase the number of independent real-time information channels that can be chosen as SMC.
Any type of information channel can be used by SMC, even channels that are not machine-readable (allowing for different purposes of certification, such as simple, one-time, secret, specialized or high-security operations). SMC can also use real channels (such as a http connection), abstract channels (such as trust), virtual channels (such as time-hop channels in a single http connection) or memory channels (such as "learned" experiences from former events and results). The number and type of channels is open-ended, so that any number of custom channels can be implemented. One such channel can be a public channel such as AltaVista [AV97]. Another such channel can be the "slow authentication" or the accumulation of identifiers over a period of time, as provided by a type of "web-of-trust" -- also involving memory channels. Other channels can be e-mail responses, cgi-bin scripts, Java applets, smart-cards, key floppy-disks, fixed passwords, one-time passwords, kerberos-type tickets, fax responses, phone calls with automatic or human response, caller-ID verifier, pager passwords, CCD video identification, CD-ROM, phone directory, business cards, bar-code, magnetic stripes, digital photos, biometrics, challenge-response, satellite signals, GPS (Global Positioning System) data, radio wave data, steganography, etc.
It must be noted that memory channels such as a "web-of-trust" must also be restricted to be "real-time", which can be enforced by other supervision mechanisms and by a validity period.
The task of evaluating all outputs from the channels (real, abstract, virtual or memory), with their proper weights and statistics to arrive at a set of estimators, can be executed by a "metric-function" which allows "distance" to be calculated -- in this case, the "distance" that represents a difference between the set of outputs and the set of expected values. The final "distance" will allow certification to be expressed as a measurement value based on intrinsic data. If the "distance" is in a previously defined neighborhood of zero, then certification has succeeded.
It is interesting to note that, using SMC, difficult attacks such as spoofing and man-in-the-middle are made practically impossible even for two previously unknown end-points -- which is novel in cryptographic certification.
5.1. SMC not Possible for Extrinsic Certification
But, could also extrinsic certification systems use SMC? The answer is negative, because extrinsic certification, by definition, depends on "endorsement of information by a trusted entity". Thus, there is no direct clean access to the source of information itself, the subject, unless the issuer path is followed. If the issuer is the subject, as in self-signed certificates, then there is no access either to the two basic assumptions of public-key (or address, etc.) and past trust. This negates the principles inherent in the definition of SMC -- for example, direct and independent. For example, the difficulties of revocation lists, which may introduce "phantom-paths" -- i.e., certificates which were revoked but are still alive somewhere. Further, SMC needs dynamic behavior, which is not possible at will within a key-hierarchy as needed by extrinsic certification. The problem, thus, is not on the implementation level, but from the two extrinsic dependencies on space (third-party) and time (past trust) which do not allow the channels to be independent and on real-time.
Further, in the case of self-signed certificates the channels would be always gathering information from one source -- the issuer.
Intrinsic certification will rely upon SMC for communication and data acquisition. Of course, any system can fail and SMC depend on a variety of resources which may fail either completely or partially. The failure may be localized but can also be a systemic failure such as traffic congestion. Thus, this Section considers that faults are occasionally going to happen, discussing the influence of faults on SMC and how this influence could be reduced or even eliminated with a desired degree of belief.
Usually, the term fault-tolerance is used to designate that quality of a system, such that the system may continue to operate in the event of a failure, allowing for a transient period (where service may even be briefly unavailable or seriously degraded) and for a reduced performance when steady-state is reached, until the failure is cleared.
If we consider a fault as "noise" (because it is unpredictable and interferes with the signal) then, by the same arguments of the former Section and regarding fault-tolerance as a signal to noise ratio that we want to maximize, the solution to provide for a higher fault-tolerance is to increase redundancy.
It is interesting to note that SMC by themselves already offer a fault-tolerant design because they are already redundant. Thus, the failure, either partial or total of one channel may either have no impact (e.g., when there are more channels than the verifier needs) or reduce the noise discrimination properties of SMC (e.g., when the verifier needs to use a high-belief channel that is not available).
However, Shannon's Tenth Theorem proves that an implementation of SMC can use a number of additional channels in order to guarantee an arbitrarily high level of fault-tolerance. Of course, the same concepts of risk/cost analysis also apply here. The design must define a fault-tolerance level to be guaranteed with a desired degree of belief, as a function of the possible threats or acts of Nature.
Of course, fault-tolerance is also available for extrinsic certification (e.g., using a PKI architecture to allow a certificate or a CRL to be referenced when the trusted-party is not available due to a fault) but one may recognize the same problems mentioned in Section 5.1. plus the questions of transitive and distributive trust in a PKI, which will severely limit the fault-tolerant design as compared with the use of SMC.
Finally, the occurrence of partial faults will have less impact on intrinsic
certification procedures, as compared with extrinsic, because intrinsic
certification does not critically depend on any one reference (e.g., as
provided by one channel in SMC) whereas such reference could be a critical
link in a PKI path.
The first step of intrinsic certification is a "cognition process". Here, a subject S must allow its intrinsic references to be measured by any verifier, independently of the will, influence or control of the subject or of any other party. Besides, S must not allow any other party to impersonate or interfere with such references, or use them for purposes other than those desired by S. To satisfy these requirements, SMC will be used to provide the needed tools for such measurements and for "noise" (i.e., enemies) discrimination, with a high reliance.
The second step of intrinsic certification is a "recognition process". Here, an unknown subject wishes to be certified as S. This step needs to use only one SMC channel and proceeds directly between the unknown subject and the verifier, because there are no third-parties involved.
Therefore, after a subject is certified once, repeated certification events on the same subject can proceed directly between subject and verifier only, using only one SMC channel between both. This can result in large cost savings, and much less risk, as compared to extrinsic certification.
To represent S and his intrinsic references, as well as to allow SMC to be securely used, this paper will postulate a model based on observables (i.e., faithful witnesses or references for the subject's properties) and observers (i.e., faithful readers of the witnesses), which are related by strict inheritance to the subject. These objects form what is called a family, i.e., all subclasses of the subject, allowing for intrinsic certification as will be proved in the the Sections.
Witnesses are public references that can be independently accessed. The witnesses are obtained by subclassing the subject itself -- so that each witness contains a subset of S:(C,D,Y). All witnesses must of course be recognizable (e.g., using cryptographic techniques) as subclasses of the parent subject, either by the parent subject itself or by proper subclasses of the parent subject. This means that the witnesses must carry secure information, that cannot be tampered with, and which allows them to be recognized, intrinsically, either by S or by proper subclasses of S. A witness may also recognize proper subclasses of the same parent subject or the parent subject itself, but must not recognize any other party (such as a verifier, another subject or an enemy) or subclasses thereof. A witness may use SMC as needed.
For example, a witness W may contain the e-mail address of the subject and a cryptographic signature of such address. The subject can verify that the signature and the e-mail correspond to data in its set S:(C,D,Y). A subclass R of the subject (a reader), that contains only its public-key, can also verify that the e-mail and the signature as read from the witness W are coherent with each other and thus must have been originated from the parent subject -- who owns the private-key that matches the public-key [MOV97].
It is interesting to note that witnesses are different from extrinsic certificates in several properties: (i) are free of charge to the subject, (ii) are independent from an issuer, (iii) are mobile -- can be distributed and redistributed at will, (iv) are executable -- can contain objects as data and methods, (v) do not depend on trust or previous events, (vi) do not need CRLs, (vii) can use any media -- e.g., fax, e-mail, www, phone, pager, CD-ROM, paper, etc., (viii) can communicate and exchange data, (ix) can recognize members of their own family, etc.
A reader allows the information contained in the witnesses to be properly used by any verifier. A reader is also a subset of S:(C,D,Y). The reader must be made available to any party (i.e., may be a verifier or an enemy) that wants to certify the subject, either by the subject or a public-service (see the first paragraphs of Section 4). As a rule, a reader has the same attributes as the witnesses.
A reader must include "self-calibration" procedures, that may allow the verifier to independently test the reader and measure its fairness and accuracy. This means that self-calibration must allow communication with objects not issued by the parent subject. The self-calibration procedures and the reader itself must be accepted and are controlled by the party that receives the reader. A reader may also include memory, which will hold the set X, or pass the set X over for storage at the verifier.
For example, the subclass R given in the example above is a reader. That reader could check e-mail and signatures from any object and indicate their coherence, given a proper public-key, but would only positively identify W as a subset of S. A self-calibration procedure would be to choose a random but known set of data (e.g., an e-mail, the signature of the e-mail and the corresponding public-key), which must yield a positive result. If the self-calibration procedure is successfully completed, then the verifier may accept the reader or decide to conduct further tests.
To allow memory channels to be used, the reader may change state -- either permanently or temporarily -- after the certificate is accepted for the first time. This would correspond to a transition from the "green" to the "certified" state described at the end of Section 4, phase (vi). This change of state may also be done in a memory register at the verifier, which receives data from the reader, as well as in gradual steps through a range of degrees of belief. When R is in a green state, it is indicated by R or (R,0). When R is certified, it is indicated by (R, X).
It is interesting to note that either a reader and/or a set X can be issued "on the fly", i.e., customized for each verifier. The case of customized readers is discussed in the next Section. However the case of customized X is simpler and allows a subject to have the same set X of publicly known properties plus a secondary set of customized properties CX. This may allow S to distribute customized certificates -- e.g., with different authorizations included in CX -- for different verifiers. This may afford the easy customization of database query-spaces, for example
6.2.1. Reader: General or Customized
We must distinguish between a general reader (i.e., the same for all verifiers) and a customized reader (i.e., which may be different even for each verifier).
A general reader (GR) may offer security as a function of standardization because a GR constitutes the independent body of knowledge of V -- e.g., like the number pi -- and is independent of S or the enemies. This means that V has a high degree of belief on a general R, with a least effort. Therefore, use of a GR would be the preferred choice.
On the other hand, a customized reader (CR) offers security as a function of specialization. However, it requires a series of tests and a more elaborate SMC structure, in order for a CR to achieve a high degree of belief for a given V. Of course, for secret protocols or specialized applications where the parties are previously known, a CR may offer both a high degree of belief and the effort is not an issue.
Now, it is important to note that the readers will "compete" with rogue readers (e.g., from the enemies) in order to be certified. The outcome of this competition will decide whether V will certify S (i.e., correct) or S' (i.e., false). We recognize that there are six cases:
6.2.2. Intrinsic Certificate and Distinguished Name
If S uses either a GR or a CR, the intrinsic Certificate of the subject can be either a secure wrapper for X or for (R,X).
However, as a usual case, GR is used for S and the Certificate is a secure wrapper for X.
Respectively, if a GR or a CR is used by S , the intrinsic Distinguished Name for S is either X or (R,X), similar to the case in Section (3.1.). This offers interesting possibilities, because a party may have a general DN and several customized DNs.
The general DN is independent of the certification process for S and may easily allow the use of a guaranteed general unique DN in applications such as databases, bank accounts, purchase orders, etc. As a more compact general DN, a subset of the DN can also be used (e.g., a hash) if so agreed between the parties.
However, as a usual case, GR is used for S and the DN is X.
The customized DN can also be of use, especially in secret applications, as a pseudonym or, in anonymous certified applications. Also, with a possible compact version being calculated by a hash-funtion [MOV97].
The collection of a parent subject and all its derived witnesses and readers is called a family, because they all inherit from the same subject. The origin of a family is the parent subject. The family is composed of objects, of three types: subject (only one set), witness (any number of sets) or reader (any number of sets).
Thus, witnesses, readers and the parent subject are objects which may recognize each other as belonging to the same family and may reject members of different families, intrinsically. The relationships are summarized as follows:
6.4 A Process For Intrinsic Certification
To obtain intrinsic certification, a process can now be constructed with the tools provided so far, mainly supplied by the new intrinsic definition of certification of Section 3.1.5, the generalized model of certification given in Section 4.2., Information Theory, the definition of inheritance in subclassing and by the conceptual separation of the subject in a witness-object (observable entity) and a reader-object (observer entity). Here, the main hypothesis are:
For the first certification of a subject that claims to be S, the complete set of seven phases (Section 4.2) must be followed. However, for subsequent certification events only the last phase needs to be used -- because intrinsic certificates do not need CRLs, resulting in large cost savings and low risk.
Hereafter, we will consider R to be GR, as already explained in Section 6.2.1., but R' can be either GR or CR.
Thus, first, the verifier has to obtain R in a green state and designate it to S, in a certified state: (this corresponds to a cognition process )
Finally, it is important to note that in intrinsic certification the
subject is the issuer, being in total control of the witnesses as well
as the reader -- also, possibly, after the certification, by using "life-lines"
. Further, in any dialogue after the first certification, the parent
subject and a certified reader will always be in contact and the parent
subject can inform the reader on-line if the certificate needs to be renewed
or modified. Thus, intrinsic certification does not need so-called Certificate
Revocation Lists (CRLs), an impossible problem by itself [Ger97a] and which
are needed in extrinsic certification because the issuer is not the subject,
the certificates and the CRLs cannot be redistributed at will, there is
no "life-line", etc.
6.5. Implementation of Intrinsic Certification
The theoretical background of this paper has been applied to an actual proposal that is being developed today, called Meta-Certificate or MC [MCG97], and which implements intrinsic certification. MCs also use multiple real-time secure channels of information. The MC proposal allows for various certification modes, of which Asymmetric Meta-Certification (AMC) is an exact representation of the sequence in the previous Section. The concepts of family and subclassing, as used in this paper, are naturally carried over to Object-Oriented concepts in the MC proposal -- such as class, objects and inheritance.
In the MC terminology, the parent subject is the MCC (the Meta-Certificate Class), the witnesses are public-MCs, the reader is a private-MC. Further, the public-MCs and private-MCs are subclasses of the MCC, which is subclassed from a standard and unique MCAC (i.e., the Meta-Certificate Abstract Class). The MCAC guarantees that all readers are either a standard reader , i.e. a standardized private-MC or GR, or a customized reader, i.e. a standardized public-MC or CR, as desired by the subject.
MCs use X as the DN for S but can also use a subset of (R, X) as a second DN, called MC-DN, with the special property that a MC-DN can be kept constant when the public-key is changed [MCG97]. More compact DNs could also be defined by hash-functions of (R, X) and so agreed by the parties.
MCs have the same properties as intrinsic certification using SMC and, therefore, can make certification arbitrarily reliable without hierarchy or central control of any kind. This means that a PKI or TTPs [TTP97] are not needed.
The basic idea of the combined certification is that extrinsic certification is correct and cryptographically secure by itself and could have a high degree of belief if a "standard" reference could be found, i.e., "standard" understood as free, independently accessed, common, faithful and worldwide. The "if" is however an absolute negative. In fact, this paper proves that there is no worldwide standard reference (or even a local standard reference) that could provide an objective base for extrinsic certification -- as given in Section 2. However, if intrinsic certification can provide such an anchor, then the intrinsic reference would be the "standard" reference needed in extrinsic certification.
For example, America was discovered by sailors that used the fixed stars (a standard reference frame) for navigation on the ocean surface of the Earth (a relative reference frame) in order to chart their course into the unknown -- with several course corrections done at night when precise measurements were available. Nowadays, commercial planes use laser gyroscopes that allow worldwide navigation without any reference to the fixed stars, using as relative references the coordinates as provided by the gyroscope (a relative reference frame), that may start from a given coordinate provided by satellites in the GPS --Global Positioning System (a standard reference frame).
Comparing this situation with "reference frames" in the Internet, the relative references provided by the laser gyroscopes could be perfectly correct and yet the plane might crash in the Amazon forest if the initial coordinate is wrong, which is the case of extrinsic certification. However, using the GPS signals, reliance on a second-order reference (subject for example, to human error) for the initial coordinate is avoided and the laser gyroscope can also be monitored in route.
Thus, combined systems have been used for centuries and prove their value by the increased options offered. For example, when the GPS signal is not available for all channels or at all, then the laser gyroscope can keep the course.
As discussed in phases (v) and (vi) in the former Section, once the certification process has been achieved, it is indeed possible to use "memory" as a channel in the SMC (note that "real-time" is still a valid restriction, enforced by life-lines  and by the validity period), allowing a type of "learned certification" to depend on trust or other qualities that defy a precise direct measurement. One can say that trust can be measured implicitly as a learned degree of belief, by the controlled use of resources and by feedback from the results. Thus, trust ceases to be such a difficult concept to use in an objective sense (being replaced by a degree of belief, which is a probability as defined in Section 3) and the dynamic qualities of trust can also be represented. This allows "learned certification" to closely match the human behavior as pointed out by Bohm [Boh97].
The combination of intrinsic and extrinsic certification, hereafter called combined, is therefore very useful. The main point is that intrinsic certification provides the "standard" reference that extrinsic certification needs -- i.e., providing a degree of belief on an entity or a root-key from an unknown CA. This is a "bootstrap" mechanism for extrinsic certification, allowing further certification procedures to be executed purely extrinsically, because the set X of V:(A,B,X) is already known -- i.e., the memory channel of SMC.
Combined certification allows therefore extrinsic certification to completely avoid second-order relative references, as in a security design that coherently uses intrinsic certification whenever needed in order to provide a standard reference-- as the sailors did centuries ago.
This leads to an evident application of intrinsic certification -- based on learning -- namely, the initial root-key distribution problem for a CA . This may allow a security design to solve the current PKI problems, allowing extrinsic certification to be used with objective reliance -- where a degree of belief could be calculated as in the "best case" example given in Section 4.1., but for unrelated CAs
7.1. Implementation of Combined and Enhanced-Extrinsic Certification
As discussed in the Meta-Certificate proposal [MCG97], some modes of Meta-Certification offer various types of enhanced-extrinsic and combined certification, using gauge-functions [Ger97e] to accept and adequately weigh results from different certification procedures, for example allowing interoperation between dissimilar trust models such as X.509, PGP, etc.
The use of "learned certification" by intrinsic modes of MCs allows
MCs to "bootstrap" enhanced-extrinsic modes of Meta-Certification -- so
that extrinsic certification ceases to depend on previous trust or knowledge
( the weak point, introducing second- and higher-order relative references
as has been discussed in this paper).
This paper investigated the possibility of using intrinsic references, from a direct comparison between certification and geometrical distance -- as measurement processes in metric-spaces.
This paper shows that certification can be either extrinsic or intrinsic, also with a combined mode. The extrinsic model depends on previous knowledge such as a "root-key" and trust, certifying by measurements based on relative references -- which are always relative to other references and so on. If the references are evaluated as probabilities that the referred claim is true, then an enhanced-extrinsic mode may allow certification to be evaluated as a range of values that can be accepted by a verifier as a function of risk/cost and not simply as a "yes/no" decision -- as in the current standards X.509 and PGP. The case of self-issued or self-signed certificates is shown to be extrinsic, because they also depend on previous information and trust. The intrinsic model does not depend on previous knowledge, trust or pre-assigned root-keys and certifies by measurements based on intrinsic proofs. The combined mode uses both models in interoperation, and, for example, allows intrinsic certification to "bootstrap" extrinsic certification. Intrinsic and combined certificates are considered to be "jointly-issued" because they depend on a cooperative effort between subject and verifier.
Also, certification is divided in two steps, which
allows the following table to be presented as a summary of results:
where "recognition 0" means recognition in zeroth-order (as when one recognizes a name to be correct because it was directly seen and heard several times in several places that one has freely chosen), "recognition 1" means recognition in first-order (as when one recognizes a name to be correct because a friend said it was correct), and "recognition n>1" means recognition in higher-order (as when one recognizes a X.509 certificate for an entity because CA1 said it was correct and even though CA1 is not known, CA2 is trusted and CA2 has said in the past that CA1 was trusted by CA2). Here, "recognition 1" can also be called "direct reference", while "recognition >1" means "indirect reference".
It is important to note that even if one trusts
the first step completely, so as to allow a local and isolated reference
frame (i.e., a small-scale and friendly PKI), it is not possible even in
this case to go reliably beyond "recognition 1", i.e. to use an indirect
reference. As shown in Section 2, indirect references would depend
on very questionable properties of trust, which do not exist in the general
case (e.g., if you trust your friend it does not mean that you must trust
your friend's choice of friends). Of course, extrinsic certification also
introduces the questions of CRLs and the corresponding unknown time-lag
to revocation -- unsolvable problems by themselves.
This paper also proves, using Information Theory, that multiple independent real-time channels of information can allow an arbitrarily high level of reliability to be reached in intrinsic certification procedures, when binding certificates to objects -- which may represent public-keys, persons, e-mail addresses, authorizations, etc. The same is not possible for extrinsic certification.
Intrinsic or combined certification are free from current PKI (Public-Key Infrastructure) problems of certification, distribution, redistribution, revocation and control of cryptographic keys and certificates, but allows the user to be totally independent of any key infrastructure, reference frames or "root-keys". Thus, the current issues that technically justify the need for TTPs [TTP97] are also not present in intrinsic or combined certification.
Also, repeated certification events on the same subject can proceed directly between subject and verifier only, using only one SMC channel between both, because intrinsic certificates do not use CRLs. This can result in a large cost savings, and much less risk, as compared to extrinsic certification.
Intrinsic and combined certification allow also for the intrinsic definition of a Distinguished Name (DS) for the subject, which is explictly accepted by the parties in the dialogue as a valid DN for the subject, which can be registered at each side. This may allow for the use of a guaranteed unique DN in applications such as databases, bank accounts, purchase orders, etc. The intrinsic certificate itself is the DN, but a subset can also be used (e.g., a hash, a mapping to a phrase, etc.) if so agreed between the parties.
The actual implementation of intrinsic, enhanced-extrinsic and combined certification concepts are indicated in the Meta-Certificate proposal -- currently being reviewed by the MCG [MCG97] -- using Asymmetric Meta-Certification and other MC modes.
Last but not least, intrinsic certification eliminates the sine qua
non and immaterial figure of "trust", as needed in extrinsic certification
-- allowing it, though, to be introduced as a learned quality accumulated
over time and under control of the user after an initial level of certification
is reached by intrinsic measurements.
 Endorsement in any form does not mean that the whole content of the certificate is endorsed, normally only the public-key is endorsed -- even though this is not usually stated in the certificate itself [Ger97a].
 A series of malicious acts can unsuspectedly influence the first transfer of a public-key, or its further use. For example, a man-in-the-middle attack in which an attacker positions itself as an active relay station between both parties since the onset of the dialogue. The attacker can then unsuspectedly change messages at will, so that both parties are always talking to him but have the firm impression they are talking to each other. For example, he could send his public-key to both parties, as if it would be each other's key. For further references, the reader is referred to [MOV97].
 Cognition is usually defined as "the process of knowing, including aspects such as awareness, perception, reasoning, and judgment". Recognition, on the other hand, is "to identify from past experience, cognition, or knowledge".
 This may be useful in some cases, such as certifying that a public-key belongs to the purchasing department of a company and that whoever sends a buying order signed by that key is authorized to request quotations and buy goods up to an amount defined in the certificate. This allows the digital counterpart of a company stamp and letterhead, but with much higher security, so the company can easily allow for transparent (i.e., to the customer) auditing and decrease the chance of bribery, collusion, etc.[Ger97c]
 E.g., as provided by an implementation of "predictable delay" or information feedback, using SMC.
 Legally, also, a CA could extend the current non-existent [Ger97a], ,  warranty protections if and when the subscribers accept the obligation to determine the veracity of a CA extrinsic certificate prior to routinely relying upon it -- thereafter exposing the CA to direct and consequential liability. In this case, certification phase number two would also include information flow from the verifier to the subject, informing that the verifier has certified the subject -- which was left as an optional step in phase two and three. This would also solve the current lack of accountability [Ger97a] of CAs.
[173447/97] "173447", Exposition, In MCG Web Page, http://mcwg/mcg/exposition.txt, April1997.
[Boh97] N. Bohm, Identity, In MCG Web Page, http://mcwg/mcg/identity.txt, April1997.
[DS97] The objective here is not to apply Dempster-Schafer Theory or
the Dempster Rule, but, to point out that the definition of degree of belief
is similar to the DS Theory. For a review of concepts and difficulties
with DS Theory, see
[Ger97a] E. Gerck. Overview of Certification Systems: X.509, CA, PGP and SKIP. In MCG Web Page, http://mcwg/cert.htm, April, 1997.
[Ger97b] E. Gerck. Documentations on the Meta-Certificate Proposal. In MCG Web Page, http://mcwg/mcg.htm, April/May, 1997.
[Ger97c] E. Gerck. The Intrinsic and Meta-Certification Primer. In MCG Web Page, http://mcwg/intrinsic.htm, July, 1997.
[Ger97d] E. Gerck. Trust Properties. In MCG Web Page, http://mcwg/trustprop.txt, July, 1997.
[Ger97e] E. Gerck. Is Certification a Metric? In MCG Web Page, http://mcwg/certmt.txt, July, 1997.
[Krip97] K. Krippendorff, Web Dictionary of Cybernetics and Systems, ASC, http://pespmc1.vub.ac.be/ASC/indexASC.html
[MCG97] MCG Web Page, http://mcwg/mcg/
[MOV97] A. Menezes et al., Handook of Applied Cryptography, CRC Press, New York, 1997.
[Sha48] C. E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J., vol. 27, pp. 379-423, July 1948.
[Sto69] J. J. Stoker, Differential Geometry, Wiley-Interscience, New York, 1969.
[TTP97] LICENSING OF TRUSTED THIRD PARTIES FOR THE PROVISION OF ENCRYPTION
SERVICES, in http://www.cl.cam.ac.uk/users/rja14/dti.html
All rights reserved.