CHAPTER THREE
CPK Truth Logic

An evidence-based Truth Logic of authentication is introduced in this paper. Truth logic is constructed on the base of an identity-based public key system. In truth logic, an entity is divided into identity and body, and an event is also divided into accepting process and adopting process, and the authenticity of identity or accepting process can be proven before the body event or adopting process occurs, in turn, the hard problem of “Authentication before the event” can be solved.

So far there is three kinds of authentication logic: the first is model-based belief logic, the second is behavior-based trust logic, and the third is evidence-based truth logic. CPK authentication system adopts truth logic.

3.1 Belief Logic

3.1.1 The Model

In 1989, M. Burrows, M. Abadi and R. M. Needhanm put forward belief logic. Belief logic is to prove the believability of object. The proof is always implemented through certain formal proof, which is called authenticating protocol.　Belief logic is expressed as some special symbol strings, known as formula. Some specific logic formula reflect rules of thinking. Thus, the axiomatic trust is regarded as the base of belief logic. Typically, it is used to authenticate certificates, vouchers, private keys and other important data.

In the book of A Logic of Authentication by Michael Burrows et al., the following principles are raised as the premise of object authentication:

（1）If you have sent a number which has never been used for such purpose previously to A, and if later on you received something based on the number from A, then you have to believe that the message from A was in response to your message.

（2）If you believe that only you and A know K, then you have to believe that all things encrypted under K-key that you have received are from A.

（3）If you believe that K is the public key of A, then you have to believe that any messages that can be decrypted by K are from A.

（4）If you believe that only you and A know X, then you have to believe that any encrypted messages containing X are from A.

3.1.2 The Formula

To prove authenticity of the object O (according to BAN logic requirements), it shall satisfy at least readability, nonce and data jurisdiction.

f (O)=(integrity, nonce, jurisdiction)

On the occasion of A sending X to B, assuming that A is trustworthy, then

（1）The rule of readability: If A encrypts and B can decrypt with the key, then B can believe that A has same key parameters that comply with the agreement, and thus B believes that X is written by A.

（2）The rule of nonce: If B believes that X is written by A, and at the same time A provides a nonce valid proof (not valid in the past, which is an effective means for preventing replay attack (copy attack), and is also a logical method to imitate “face-to-face verification”, to realize “on-spot verification” in the physical world), then B believes that A believed X.

（3）The rule of jurisdiction: If B believes that A believes X, and at the same time A provides that X is under jurisdiction of A, and then B believes X.

3.1.3 The Characteristics of Belief Logic

It is not difficult to see the characteristics of belief logic as follows.

（1）In belief logic entities are classified into subject and object, and the inference is undergone in accord with the given model under the presupposition that A is trust. This is directly against the Cyber security principle of “mutual suspicious”. A mathematician has said that all model is wrong though some are useful;

（2）Belief logic is to prove the authenticity of object, the conclusion of the inference is B believes X. But in most cases we draw the conclusion of “B trust A” from “B believes X”, if this conclusion can be established, then it is to say that authenticity of subject is derived from or after the authentication of object. Such proving method is called proof-after-event.

3.2 Trust Logic

3.2.1 Direct Trust

Direct trust is trust of grade one, the prover and the verifier form direct relationship, they are “father and son” in genetic bond, i.e., “parent-child” relationship. Only when it is a direct trust, registration and integration can be established and verified. Therefore, the direct trust is the true basis for identity authentication.

In social life, there are many cases like this. ID Card issued by Ministry of Public Security forms direct trust between the country and individuals, in which the prover and verifier constitute direct affiliation in order to prove the civil status of a person. Direct relationship is established via account number and PIN code between a bank and a customer. The customer can conduct corresponding transaction within the specified scope with the account number and PIN code. The relationship between database and client also belongs to such a relationship.

3.2.2 Axiomatic Trust

Axiomatic trust is established on the basis of common sense, and does not need to prove, this can be defined as no-grade trust. The concept of this trust is very important, but it is often ignored.

When shopping, it seems that only cash or bill is needed to make the purchase, thus the belief logic on the objects can be established, and the transaction can be done. However, in fact such transaction is actually made on the basis of axiomatic trust under the assumption that the bearer should be a normal person. If the bearer is an incapacitated person, such as mental patient, or a child, the transaction may not be made.

Belief logic shall be conducted on the basis of assumption: The verifier (C) believes that the prover (A) is trustworthy. This is an axiomatic trust. Further, authenticity of the object (X) can be proved. Thus, a strange phenomenon is observed that we first assume that A is trustworthy. Upon proving authenticity of X, one can conclude again that A is trustworthy.

It can be explained as follows. At the beginning, the presupposition of C trusting A is an axiomatic trust. The conclusion of C trusting A through proof of belief logic is an inference trust, which elevates the trust level from axiomatic to inference level. Axiomatic trust or inference trust is not truly identity authentication. However, they can be used as an effective means for identity authentication in the electronic transactions, as long as security policy allows, or as long as all parties are involved in the transaction admit. But the belief logic is only the logic of object authentication and is not the real logic of subject authentication.

3.2.3 Inference Trust

Many transactions are conducted between customers. However, there is no registration relationship, administrative superior-subordinate relationship and jurisdiction relationship among the customers. Therefore, registration between customers needs to be proved by a third party. Center C issues certificate to users A and B. With C's certificate, a trust relationship can be established between A and B. Here, Center C is the third party. If Center C and users A, B have administrative superior-subordinate relationship, then C actually is the “party in charge”, Center C and users A and B have “father-son” relationship, and users A and B have “full brother” relationship. If Center C and users A and B have no administrative jurisdiction relationship, then the third-party C and users A and B have “appointed” father-son relationship, just like “adoptive” relationship, and users A and B are “appointed” brothers. Trust relationship is very much like blood relationship.

1. Fuzziness of Inference Trust

Fuzziness exists in trust degree of the subject. Defining interval of trust relationship as [1,0], and using Td to represent trust degree:

• T1: representing the subset of “full trust”.

• T0.8: representing the subset of “highly trust”.

• T0.6: representing the subset of “quite trusted”.

• T0.4: representing the subset of “general trust”.

• T0.2: representing the subset of “a little trust”.

• T0: representing the subset of “no trust”.

2. Gradation and Trust Level of CA

When CA has a multi-level structure, the transfer of certificate will dilute the trust. Assuming that the probability of counterfeits is 1/100, with the increase of gradation, the probability of true will step down accordingly, for example:

First-layer CA: the probability of true is 99%.

Second-layer CA: the probability of true is 98%.



Seventh-layer CA: the probability of true is 51%.

In the hierarchical structure of CA, “layer” is directly related to the degree of inference trust. The first-layer CA and second-layer CA constitute grade one trust, the second-layer CA and second-layer CA constitute grade two trust, the second-layer CA and third-layer CA constitute grade three trust, etc.

3.2.4 Trust Chain

In the last era of 90s, some countries were dissatisfied about the U.S. monopoly of computer operating system, and expressed strong demand to develop their own operating system. Thus some U.S. computer enterprises put forward a concept of trusted platform declaring that if one can control the platform then he can control the operating system, so there is no need to develop operating system by their own selves.

In 2000, Trusted Computing Platform Alliance (TCPA) was established and put forward the conception of trust logic, and released the Design Philosophies and Concepts Version 1.0. The concept of trust is a subjective judgment of a subject to another subject. We will see how the “trust” is working in the below operating flow (see Fig. 3.1). The Trusted Platform Module (TPM) is charged to measure all behavior of software, and judge the degree of trust for software (another subject).

The definition of trust given by TCP is that an entity can be trusted if it always behaves in the expected manner for its intended purpose. Thus the trust is formed on base of behavior. This is the only way to judge the subject.

3.2.5 Characteristics of Trust Logic

Trust logic has the following characteristics:

（1）Entity is classified into subject and object.

（2）Subject is proved by behavior.

（3）The behavior of subject can be measured by another trusted subject.

（4）The proving and judgment can only happen after events.

It is obvious that the trust is still remaining in the old security principle: “mutual trust”, and does not followed up the new security principle based on “mutual suspicion”.

3.3 Truth Logic

PITAC report accurately concluded the changes of security principles, and pointed out: The security principle used for information security is always the belief logic based on “mutual trust”, while the principle for Cyber security must be a new logic based on “mutual suspicion”. In the past, all the security protocols are based on “assuming subject is trust” to prove believability of object, or to prove subject trustability by inferring object believability. This is called Proof-after-Event, i.e., authentication can be made after the object event occurs.

Thus, a new proving logic is needed, that can prove-before-event without any assumption. This is the “truth logic”, truth logic is used to distinguish true or false, the conclusion is objective and not divided. Trust is not a necessary condition for business, such as buyers and sellers do not know each other, and there is no trust relationship, but the transaction can make all the same. Therefore, in the truth logic, the terms of “trust”, and “believe”, are still of the concept of subjectivity.

Truth logic is an evidence-based logic, and can only be built on the identity-based public key system having the function of digital signature. As far, only CPK meets the requirements of truth logic, therefore, truth logic can be called CPK Authentication Logic. CPK truth logic is composed of Entity Authentication Logic and Event Authentication Logic.

3.3.1 Entity Authentication Logic

In truth logic, the authenticity of entity is the intersection of the authenticity of the identity and body of entity.

AUTH (Entity)=AUTH (Identity) or/and AUTH (Body)

Definition 1: The entity's identity authenticity is the signature to the time or to the identity (called identity signature) by identity's private key. In the identity, the time is an objective factor and can universally be understood by any relying party. Because the identity authentication can be processed independently before the body appears, it is called “proof before event”.

Let the entity be Alice, where the function of identity authenticity is a signature to time by Alice,

AUTH (Alice)=SIGalice(time)=sign1=(s1,c1)

and the verification formula is

VERALICE(time, s1)=c'1

Note that ALICE is public key derived from Alice, alice is the private key of Alice that satisfies ALICE=(alice)G.

If c1=c'1, then the identity at this time (Alice) is true.

Definition 2: The entity's body authenticity is a signature to the character (CHR) of Body by identity and the verification of the Body by identity. Because the body authentication always processes before the body appeared, it is called “proof after event”.

Proof:

AUTH (body)=SIGalice(CHK)=sign2=(s2,c2)

or

AUTH (body)=SIGalice(MAC)=sign2=(s2,c2)

Verify:

VERALICE(CHR, s2)=c'2

If c2=c'2 then the Body is true.

Body of entity can be represented by its character. In information system Body is always in a form of data, including the bio-feature. In this case, the Message Authentication code (MAC) or Sampled Data Code (SDC) can be the character of the Body. Because the Body is signed by a private key that derived from its Identity, the integrity of Identity and Body is proved at one time, so no additional proof is needed.

Above method in which entity is divided into identity and body is a theoretical authentication method. In practice, the identity authentication can be omitted, the body authentication can stand for entity authentication, such as person authentication, fake authentication, bill authentication. Because in such case, the identity and body is bound to one, and always takes place simultaneously. The identity authentication can be omitted only under identity-based public key system.

3.3.2 Event Authentication Logic

Event is the movement of entity and exists in a form of processes. The process is composed of accessing process and adopting process. The authenticity of event is the intersection of accessing process and adopting process.

AUTH (Procedure)=AUTH (accessing) or/and AUTH (adopting)

Definition 3: The authenticity of accessing function is the signature to the time of event by the identity of event.

AUTH(access)=SIGidentity(time)=sign1=(s1,c1)

The verifying function is

VERIDENTITY(time, s1)=c'1

if c1=c'1, then the identity is true, and the the procedure is acceptable.

Definition 4: The authenticity of adopting function is the signature to character(CHR) of event by the identity of event.

AUTH (adopting)=SIGidentity(CHR)=sign2=(s2,c2)

The verifying function is

VERIDENTITY(CHR, s2)=c'2

if c2=c'2, then the CHR is true, and the procedure can be adopted.

Any transaction authentication is composed of two proving processes. This is the special feature of truth logic.

In fact, the principle of entity authentication or event authentication is the same, but in event authentication, access process and adopting process don't take place at the same time. It is different from entity authentication. If there is a requirement of “proof before event”, then the access authentication can not be omitted, such as communication authentication and software authentication, else the access authentication can be omitted.

3.4 Authentication Protocols

3.4.1 Communication Authentication

Communication authentication is composed of the authentication of access process and the authentication of receiving process:

AUTH (comm)=AUTH (access) or/and AUTH (adopting)

In comparison with transaction authentication, the access process is the same as accepting process and the receiving process is the same as adopting process.

According to the different communication systems the access authentication is divided mainly into two types of sub-accessing protocols: offline protocol and online protocol, where the offline sub-accessing protocol is further divided into one-way protocol and two-way protocol.

1. Off-line Protocol

One-way protocol is used in non-handshaking system such as e-Mail communication. Suppose that Alice sends data to Bob.

Alice signs to time to prove source address and signs to Bob to prove the destination address.

SIGalice (time)=sign1=(s1,c1)

SIGalice (Bob)=sign2=(s2,c2)

Bob checks the signature

VERALICE (time, s1)=c'1

VERALICE (Bob, s2)=c'2

If c1=c'1 and c2=c'2 then the authenticity of sender and receiver is proven, Bob accepts the data.

SIGbob (MAC)=sign3 =(s3,c3)

Two-way protocol is used in handshaking system. Suppose that the sender's phone number is Alfa, and the receiver's number is Beta then the 2-way protocol is:

Alfa sends his signatures:

SIGalfa(time1)=(s1,c1)

SIGalfa(beta)=(s2,c2)

Beta verifies the signs and sends his signature:

SIGbeta(time2)=(s3,c3)

The sender verifies the signature:

VERBETA(s3,time2) =c'3

Now that the both sides are authenticated each other.

2. On-line Protocol

On line protocol is used between client and portal. The portal includes server. The portal is the target of DOS attack. On-line authentication protocol is composed of the request of user, the challenge of portal, the response of user.

User's request: the signature to time and to the portal :

SIGuser (time)=sign1=(s1,c1)

SIGuser (portal)=sign2=(s2,c2)

Portal's challenge: after the verification of the sender and receiver, Portal signs to time and sends a random number r, and waits for the response.

SIGportal (time)=sign3=(s3,c3)

Portal sends:｛r(s3,c3)}

User's response: User signs to r:

SIGuser (r)=(s4,c4)

User sends:

{(s4,c4)}

3.4.2 Software Authentication

Software authentication has two cases: the first case is software issue; the second case is software invoke. Software issue includes software download and install; Software invoke include software uploading and execution. The two cases have the same authentication process. In spite of this, the two cases were independent of each other, issuing process occurs between the issuer and the user, and the invoking process take place between memory program and user, so it can't be replaced each other.The authenticity of software issue procedure is to control the download and install process and the invoke procedure is to control the upload and execute procedure:

AUTH (issue)=AUTH (download) or/and AUTH (install)

AUTH(invoke)=AUTH (upload) or/and AUTH (execute)

Software download (upload) authenticity: including the authenticity of software issuer and the software name. The authenticity of issuer is the to time by issuer. It is called identity signature:

SIGissuer(time)=(s1,c1)

VERISSUER(s1,time)=c'1

If c1=c'1, then the issuer is true. The authenticity of the software name is the signature to name by the issuer.

SIGissuer(name)=(s2,c2)

VERISSUER(s2,name)=c'2

If c2=c'2, then the software name is true, and the software is available for download (upload).

Software installation (execute) authenticity: the authenticity of software code is the signature to the code by issuer. Generally, data compression or data sample can stand for data.

SIGissuer(mac)=(s3,c3)

VERISSUER(s3,mac)=c'3

If c3=c'3, then the software is allowed to be installed (executed).

There maybe three types of issuers: Manufacturer, Organization, and Individual. The software issued by them will be signed respectively.

Summary

The truth logic is different from trust logic. The trust logic is a kind of subjective assurance, but truth logic is a kind of objective judgment. Trust logic is complicated and the conclusion is obscured, but truth logic is simple and the conclusion is clear.

Trust and belief are sociology terms. When the term of trusted or trusting is used in technical applications, we must define the term first. So far, we haven't seen an appropriate definition. From now on, we use the term authenticated and authenticating to replace the term trusted and trusting, respectively.

（1）The truth logic is to prove the authenticity of any entity making no distinction between subject and object.

（2）Entity authentication is divided into identity and body process, transaction authentication is divided into acceptance and adoption process, communication authentication is divided into access and receive process, and software authentication is divided into download and execution process. All authentication is divided into proof before event or proof after event.

（3）The proof of identity can be done before the proof of body without assumption. It is called the proof before the event. The proof before the event is the foundation of “active management”. If it is used in transaction illegal transaction will be prohibited, if it is used in communication illegal connection will be prohibited, and if it is used in software system, illegal operation will be prohibited,etc.

（4）The truth logic is to identify “friend”. It is different from the logic that identifies “enemy”. The friend identification is active and easy but the enemy identification is passive and hard.

（5）The identity authentication must be realized by digital signature of identity-based public key.

（6）In truth logic, the proving side provides evidence and the verifying side verifies the evidence.

References

[3] Information Assurance Technical Framework, issued by National Security Agency, Information Assurance Solutions Technical Directors, Release 3.0 Sep., 2000.}/pa

[4] President's Information Technology Advisory Committee, Cyber Security: A Crisis of Prioritization, A Report to president, Feb., 2005.}/pa