# Formal Modeling and Analysis of Fairness Characterization of E-Commerce Protocols

Authors: Chengwei Zhang; Xiaohong Li; Jing Hu; Zhiyong Feng; Jiaojiao Song
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In the past, fairness verification of exchanges between the traders in E-commerce was based on a common assumption,
so-called nonrepudiation property, which says that if the parties involved can deny that they have received or sent some information, then the exchanging protocol is unfair.
So, the nonrepudiation property is not a sufficient condition.
In this paper, we formulate a new notion of fairness verification based on the strand space model and propose a method for fairness verification,
which can potentially determine whether evidences have been forged in transactions. We first present an innovative formal approach not to depend on nonrepudiation,
and then establish a relative trader model and extend the strand space model in accordance with traders’ behaviors of E-commerce.
We present a case study to demonstrate the effectiveness of our verification method.


---

## Body

## 1. Overview

The E-commerce protocol is a special kind of security protocol aiming to coordinate the exchange of valuable information between traders. The fairness of E-commerce protocols is the essential property and has become a research hotspot in recent years. E-commerce protocols are different from traditional cryptographic protocols, and common security analysis methods are invalid to fairness validating. It is common to extend existing methods like Kailar logic [1], SVO logic [2], CSP process algebra [3], and strand space model [4–6] to analyze such protocols. These methods are based on the assumption that the nonrepudiation has been established, and then verify fairness of fair exchange protocols. However, fairness validating of E-commerce protocol needs to verify not only the exchange process of protocols but also the evidences exchanged between traders in transactions.To verify fairness of E-commerce protocols, we present a strand space model based fairness verification method in this paper, which is independent of nonrepudiation. The concept of fairness is decomposed into fair exchange of evidences and fair evidences of exchange, and a formal definition of fairness and fairness evidences is introduced. The trader model is constructed according to trader’s behaviors, which is different from Dolev-Yao penetrator model [7]. The strands, in which no evidences from its opponent are obtained by the entity, are analyzed; thus, the nontermination dilemma caused by the state space explosion problem can be avoided.The paper is organized as follows: related work on fairness verification is discussed in Section2. Some background knowledge about strand space theory and the Dolev-Yao penetrator model is introduced in Section 3. The core body of the paper is followed in Section 4, which consists of definition and analysis of fairness as well as the discussion of trader models and the extended theories of the strand space model. The improved strand space model is tested by using the EMH protocol in Section 5, which proposes an improved protocol. Finally, the paper’s conclusion is offered in Section 6.


## 2. Related Works

The E-commerce protocol has two objectives: the first one enables each protocol participant to seamlessly exchange valuable information. The second one enables each protocol participant to ensure the exchangeable fairness. The fair exchange protocol is a basic protocol of various E-commerce applications. From the perspective of protocol structure, it can be divided into three categories: gradual exchange protocols, on-line TTP exchange protocols, and offline TTP exchange protocols. In the 1980s, the appearance of gradual exchange protocols gradually increases the probability of correctness over several rounds of communication, but these protocols only can do progressive fairness [8]. The third party protocol requires a trusted third party. The third party is on-line which is required to be active in every exchange transaction [9]. These protocols relying heavily on TTP could easily lead to overload of networks and susceptible attacks. Offline fair exchange protocols have two phases: message exchange phase and dispute resolution phase. TTP was used only in the dispute resolution phase. This type of protocol reduces the problem of TTP as a source of bottleneck, because TTP is used very rarely and not involved in every round of exchange. Currently, most E-commerce protocols are based on offline TTP exchange protocols.Formal analysis of security in E-commerce protocols is carried out more frequently than the proposal of traditional security protocols. For this reason, a variety of theories have been proposed, such as Kailar logic, SVO logic, and analysis method based on the CSP process algebra. Kailar proposed the concept “accountability,” and a kind of logic to analyze accountability named Kailar logic. Accountability refers that protocol participants an prove that they have done something. Kailar logic verifies accountability by analyzing whether the parties have obtained the evidence that demonstrates the occurrence of the exchange. Zhou Jianying and Dieter Gollman put forward concepts EOO (nonrepudiation evidences of origin) and EOR (nonrepudiation evidences of receipt), which are used as the evidences of accountability. A nonrepudiation protocol allows two potentially mistrusting parities to exchange an electronic message together with EOO and EOR over the Internet in a fair way, that is, each party gets the other’s term(s) or neither party does. They use SVO logic to verify nonrepudiation protocols. Steve Schneider uses CSP process algebra to analyze nonrepudiation protocols. The method he proposed can be utilized to analyze accountability and fairness. However, the analysis of the exchangeable fairness is based on on-line TTP rather than on offline TTP protocols which own a branched structure.It is a prevailing approach for researchers to extend the strand space model for the analysis of E-commerce protocols in recent years. Yang and Deng [10] extended the strand space model to analyze TLS and IKE protocols. They proposed semiregular entities to denote entities which are different from penetrator and regular entities. Wang et al. [11] employed not only nonrepudiation EOO and EOR as the fairness evidences but also a similar method to prove the fairness of the iKP protocol as well. At the same time, Liu et al. [12] used a similar method to prove the fairness of the IBS protocol. These studies have provided a detailed description and analysis of E-commerce as well as its security properties.All these methods verifying fairness are based on the prerequisite of guaranteeing exchangeable testimony as the satisfied nonrepudiation. They use nonrepudiation evidences as the fairness evidences. Nonrepudiation means that counterparts cannot deny that they have received or sent some information [13]. The E-commerce protocol requires not only fair exchange of evidences, but also the equivalence of exchange evidences.The methods mentioned above are limited in the scope of the analyzed protocol, first of all, not all E-commerce protocols use TTP as an arbitration and fault-tolerant process [14]; in addition, the nonrepudiation evidences are the evidences of participants having sent or received information, while the fairness evidences are the valuable, quantifiable information exchanged by traders such as electronic money, bills, and signatures in running of an E-commerce protocol. These methods must assume that traders cannot forge evidences first and then analyze the fairness of exchange processes. Therefore, the study needs to explore a formal definition of fairness which does not rely on nonrepudiation.In addition, Fröschle [15] put forward the concept branch of the strand space model. Branch describes the different choices of entities in an E-commerce protocol, which helps to traverse all the behaviors of protocol entities. Guttman [16, 17] defined fairness evidences as a collection of valuable information and then tracked all steps of a run to prove the fairness of the exchange protocol. Strand space model uses strands to describe all possible behaviors of protocol participants, and needs more than one strand to describe an entity’s behaviors, making the model complex owing to the fact that participants in E-commerce protocols are possibly dishonest. At the same time, as the analysis of the fairness evidences requires considerable understanding of a protocol, so fairness can’t be verified automatically. In addition, the space of entities’ behaviors may be unlimited because of dishonesty, and the traversal may not be terminated; thus, a fairness verification method not to traverse all possible behaviors of protocol’s entities needs to be explored.Besides, although Guttman [16, 17] and we both extend the strand space model to verify fairness, the details of verification process between us are quite different. Guttman developed a model connecting protocol execution with state and state change and defined a new notation named state synchronization events to synchronize states between protocol participants. The “fair” in “fair exchange” in their definition refers to the balanced evolution of the state. In our method, we define the trader model to restrict traders’ behaviors, and analyse all the possible results of a protocol. Their fairness focus on the transaction process, while we concentrate on the transaction result.By the way, the protocol used as an instance to test our method in Section5 has been proved to be unfair [18]. They analyzed and improved the EMH protocol, while the method they proposed is very purposeful and can only be used in few protocols [19].


## 3. Basic Concepts of Strand Space Model

Strand space model was proposed by Fabrega, Herzog, and Guttma in 1998, which analyzes security protocols in a hybrid analysis method combined to theorem proving and trace. It was proposed to formally analyze authentication and confidentiality of security protocols at first. There are some basic definitions of stand space model as follows.A denotes the set of messages that can be exchanged between principals in a protocol. Terms are the elements of A. In a protocol, principals can either send or receive terms. To strand space model, the positive sign represents sending a term, whereas the negative sign represents receiving a term according to its occurrence.Definition 1.
A signed term is a pair〈
σ
,
a
〉 with a
∈
A and σ
∈
{
+
,
-
}. We will write a signed term as +
t or -
t. (
±
A
)
* is the set of finite sequences of signed terms. We will denote a typical element of (
±
A
)
* by 〈
〈
σ
1
,
a
1
〉
,
…
,
〈
σ
n
,
a
n
〉
〉.We extend the notion term to describe behaviors by traders in E-commerce protocols.Definition 2.
A strand space is a setΣ with a trace mapping tr
⁡
:
Σ
→
(
±
A
)
*, where Σ is the set of strands.Definition 3.
A node is a pair〈
s
,
i
〉, with s
∈
Σ and i, an integer satisfying 1 ≤ i ≤ length(
tr
⁡
(
s
)
). The set of nodes is denoted by N. One will say the node 〈
s
,
i
〉 belongs to the strand s.Definition 4.
E is the set of edges. n
1, n
2
∈
N and n
1
→
n
2
∈
E means term
(
n
1
)
=
+
a and term
(
n
2
)
=
-
a; n
1
⇒
n
2
∈
E means n
1, n
2 occurs on the same strand with index
(
n
1
)
=
index
(
n
2
)
-
1.The actions available to penetrators are encoded in a set of penetrator traces that summarize the ability to discard messages, generate well-known messages, and piece messages together and apply cryptographic operations using keys that become available to him.Definition 5.
Penetrator model is defined by penetrator traces according to Dolve-Yao model assumptions:M: text message: 〈
+
t
〉, where t
∈
T,
F: flushing: 〈
-
g
〉,
T: tee: 〈
-
g
,
+
g
,
+
g
〉,
C: concatenation: 〈
-
g
,
-
h
,
+
g
h
〉,
S: separation into component: 〈
-
g
h
,
+
g
,
+
h
〉,
K: key: 〈
+
K
〉, where K
∈
K
P, K
P is the set of keys initially known to the penetrator,
E: encryption: 〈
-
K
,
-
h
,
+
{
h
}
k
〉,
D: decryption: 〈
-
K
-
1
,
-
{
h
}
K
,
+
h
〉.TraceM means penetrator could send the messages they owned to the channel. While F means that they could obtain every message traveled in channel. T means repetition. C and S, respectively, represent joining and decomposition. E and D are the encryption and decryption. This set of penetrator traces ensures that the values that may be emitted by the penetrator are closed under joining, encryption, and the relevant “inverses” [5]. The trader model we proposed has the same form with penetrator model but models different abilities.


## 4. The Fairness Verification Using Strand Space Model

The paper focuses on E-commerce protocols containing third parties. The referred third party, here, are bank, arbiter, and trusted third party (TTP). Buyers and sellers in transactions exchange evidences, while third party guarantees fairness and effectiveness of the transactions. The model of third party is assumed to be regular and honest. This section is divided into three parts: the first part gives the formal definition of fairness and fairness evidences and then establishes the trader model and extends related concepts of the strand space model and, at last, gives a fair validation process based on those definitions.


### 4.1. The Formal Definition of Fairness

Fairness is one of the basic security properties that E-commerce protocols must meet; the acknowledged definition of fairness can be referred to [8–15]: an exchange is fair means that, at the end of the exchange, either each player receives the terms they expect or none receives any information about the other’s terms. Fairness evidences are those terms that players expect in transaction. Fairness of E-commerce protocols includes the fair exchange of evidences and the fair evidences in exchange. The exchange in an electronic transaction is considered to be equivalent, so evidences exchanged in electronic transaction should be equivalent; otherwise, a trader may benefit from the other by forging unequal exchange evidences. To verify the fairness of the corresponding relation of evidences, the mapping relationship of defining evidences is in the following.Definition 6.
TradersB
1, B
2
∈
N; N is the set of traders’ identification; E
B
1 and E
B
2 are sets of fairness evidences belonging to traders B
1 and B
2, respectively. The evidence-corresponding-relation is a bijective function f
B
1
:
E
B
1
→
E
B
2. Its inverse function is f
B
2
:
E
B
2
→
E
B
1. ∀
e
∈
E
B
1, ∃
!
e
′
=
f
B
1
(
e
)
∈
E
B
2, here, f
B
1
(
e
) means the evidences of B
2 which B
1 expects. The set of functions f
B
1
(
e
) is denoted by F
(
E
B
1
,
E
B
2
). Similarly, the set from B
2 to B
1 is denoted by F
(
E
B
2
,
E
B
1
).Evidences exchanged in electronic transactions need to be mutually corresponded. Each trader has the ability to evaluate evidences, and the corresponding relations of traders’ evidence act as an evaluation tool to measure equivalence of the evidence’s value. We can verify whether traders have forged evidences from the formulae
′
=
f
(
e
). If the formula is not established, it means that someone has forged evidences so that evidences exchanged are not equivalent. In our research, we assume that if a trader receives unequal evidence from others, they would like to ignore this message. This means that if a participant uses forged evidences in transaction, the other participant will refuse to accept the evidence.The fair exchange of evidence, in the point of view of a trader, means that ifA has not obtained the evidence from B, then B could not obtain A’s evidence; else, if A obtained the evidence of B, whether B obtained evidence from A will not be considered anymore. Popular to say, the fairness means each participant of a transaction is not at a disadvantage. Combined with Definition 5, we define fairness as follows.Definition 7.
Given an E-commerce protocolΓ, here, B
1, B
2
∈
N, e
1
∈
E
B
1, e
2
∈
E
B
2, E
B
1, and E
B
2 are sets of evidences of B
1 and B
2. f
1
∈
F
(
E
B
1
,
E
B
2
) andf
2
∈
F
(
E
B
2
,
E
B
1
) are evidence-corresponding-relations between B
1 and B
2, respectively. Protocol Γ is fair, if and only if the following two conditions hold:(1)
at the end of an exchange, if traderB
1 has not obtained f
1
(
e
1
), then B
2 cannot get e
1;
(2)
at the end of an exchange, if traderB
2 has not obtained f
2
(
e
2
), then B
1 cannot get e
2.During the fairness validation process, we first generate a trader’s strand which he has not got at the end of a transaction; the other trader acts as a penetrator to analyze whether the penetrator could obtain the evidence they want through a variety of deceptions or attacks from one of the strands above. The penetrator model here is different from the model used in the classical strand space model. Therefore, we need to model the behaviors of traders and extend related theories of the strand space model to describe E-commerce protocol and its properties.


### 4.2. Extension of Strand Space Model

Traders in E-commerce protocols are dishonest not like regular entities and penetrator entities in general security protocols. Apart from traders, all participants in E-commerce protocols are regular entities and perform in accordance with the agreement provisions. Because their sequence of events and entity model are constant, each of them has only limited numbers of strands. While traders may opt out of the transaction, or repeatedly use outdated evidences, like orders and electronic money, they may use a variety of behaviors to obtain benefits, thus the events sequence of these entities may not be complete in accordance with the protocol. Original strand space model uses the penetrator model to describe behaviors of attackers. A penetrator can intercept, send, forgery, tamper messages, and so forth. They can do almost everything except for resolving cryptographic algorithms, while traders are still bounded by the protocol. If using penetrator model to describe traders’ behaviors, we might make a wrong judgment to a correct protocol. Thus, we need to establish a model to describe the behaviors of transactions between buyers and sellers. The capability of this model is between regular entities and penetrator entities. We call it trader model.The study imitates the penetrator model in original strand space model to build the trader model and describe the behaviors of traders into atomic behaviors and their combinations. E-commerce protocols have little constrains for traders, similarly, traders cannot be completely separated from the protocol, so we use atomic behavior as well as some constraints on these atoms to describe the behaviors of traders. The model assumptions are showed as follows:(1)
traders can encrypt, decrypt, connect, and decompose message;
(2)
traders can forge evidences and messages by using unequal evidences to get the other’s interests;
(3)
traders can send or receive messages belonging to this trader in protocol; only the messages are in specified format of protocol;
(4)
both entities and messages in E-commerce protocols satisfy authentication and confidentiality, which being basic properties of security protocols; the protocol is insecure if these two properties are not met; fairness and nonrepudiation are based on the premise of security of the protocol; we should verify security before analysis fairness;
(5)
the sequence of events in traders model needs not to be the order in accordance with the protocol; this assumption needs to describe the behaviors of traders in the form of atoms.Considering E-commerce, protocols satisfy authentication and confidentiality; we add the identifiers of entities into the concept of the term, and terms in our model are represented as a 3-tuple. This modification eliminates the need for verification of authentication. Term is defined as follows.Definition 8.
Term is a 3-tuple〈
σ
,
a
,
B
〉, where σ
∈
{
+
,
-
,
⨁
}, a
∈
A, and B
∈
N. A is the message set and P is the set of entities’ identifier. 〈
+
,
a
,
B
〉 means entity B sends message a; 〈
-
,
a
,
B
〉 means an entity receives message a from entity B; and 〈
⨁
,
a
,
B
〉 means entity B owns message a. For convenience, abbreviate term 〈
σ
,
a
,
B
〉 as σ
a
.
B; a is the unsigned portion of σ
a
.
B.
We use symbol “⨁” to meet the third assumption. Traders in E-commerce protocols cannot receive or send some messages, but can calculate. In the following, A
B is the set of terms that B could send or receive in protocol, and A
B
* is the set of messages B owns at the time.
Traders’ atomic behaviors can be described by trace.Definition 9.
A trader trace is one of the following:(1)
M
*: text message: 〈
⨁
t
.
B
,
+
t
.
B
〉, where +
t
.
B
∈
A
B, t
∈
A
B
*, and B
∈
N; B is an entity’s identifier; trace M
* expresses entity B sending message t;
(2)
F
*: flushing: 〈
-
t
.
C
,
⨁
t
.
B
〉, where -
t
.
C
∈
A
B and B, C
∈
N; trace F
* means entity B receives message t, and then B owns t;
(3)
P
*: falsifying: 〈
⨁
e
.
B
,
⨁
f
.
B
〉, where e
∈
E
B and f
∈
F
(
E
B
,
E
B
′
); E
B is the set of evidence belonging to entity B, F
(
E
B
,
E
B
′
) which is the set of evidence-corresponding-relations from B to B
′; trace P
* expresses the situation that entity B forges evidence and its descriptions in protocol;
(4)
C
*: concatenation: 〈
⨁
g
.
B
,
⨁
h
.
B
,
⨁
g
h
.
B
〉, where g, h
∈
A
B
* and B
∈
N; trace C
* means that if entity B owns messages g and h, then B owns g
h;
(5)
S
*: separation: 〈
⨁
g
h
.
B
,
⨁
g
.
B
,
⨁
h
.
B
〉, where g
h
∈
A
B
* and B
∈
N; trace S
* means that if entity B owns message g
h, then B owns g and h;
(6)
K
*: key: 〈
⨁
K
.
B
〉, where K
∈
K
B, K
B is the set of keys B owns; trace K
* means entity B owns key K;
(7)
E
*: encryption: 〈
⨁
K
.
B
,
⨁
h
.
B
,
⨁
{
h
}
K
.
B
〉, where K
∈
K
B, h
∈
A
B
*, and B
∈
N; trace E
*expresses the situation that entity B can encrypt h with key K;
(8)
D
*: decryption: 〈
⨁
{
h
}
K
.
B
,
⨁
K
-
1
.
B
,
⨁
h
.
B
〉, where K
∈
K
B, {
h
}
K
∈
A
B
*, and B
∈
N; trace D
* expresses the situation that entity B can decrypt {
h
}
K into h if they own both {
h
}
K and K
-
1.The strand of a trader is composed of nodes in tracesM
* and F
*, expressing a sequence of events of the entity, and the remaining six traces are used to describe the entity’s message space. Here, “+” and “−” denote messages delivered between entities, and “⨁” stands for messages generated inside entities. The classical strand space model does not describe the concept “owned,” because the number of messages sent or received by generators are unlimited. Messages which can be sent or received are owned by penetrators, while traders can only send or receive messages belonging to them. We propose the concept "owns" to describe the ability that a trader can process all the messages that they encountered. In summary, we modify the definition of terms to solve authentication and confidentiality, remove the tee trace T, add trace P
* and symbol “⨁” to limit traders’ abilities, and, finally, build the traders model.Classical strand space model uses edges “→” and “⇒” to describe the causal relationship between terms, where “→” edge expresses delivering message between entities, and “⇒” edge describes an entity’s state transition. Because traders’ entities are semihonest, one may need more than one strand to describe their behaviors. Using atomic behaviors to build the trader model could describe the trader’s behaviors nicely but is not conducive to express the causal relationship between nodes. For this purpose, we define owning set A
B
* and sending-receiving set A
B, where owning set A
B
* is a concept similar to ideal in the classical model and stands for messages that entity B has owned. The set is generated in a recursive way. Sending-receiving set A
B contains messages which B could send or receive and is fixed in a specific protocol. The owning set A
B
* is defined as follows.Definition 10.
A
B
* is an owning set of entity B; if g
∈
A
B
*, then(1)
E
B
⊆
A
B
*, K
B
⊆
A
B
* and F
(
E
B
,
E
B
′
)
⊆
A
B
*, where E
B is the set of B’s evidences, K
B is the set of B’s keys, and F
(
E
B
,
E
B
′
) is the set of evidence-corresponding-relations from B to B
′;
(2)
∀
h
∈
A
B
*, one has g
h
∈
A
B
*;
(3)
∀
K
∈
K
B, one has {
g
}
K
∈
A
B
*;
(4)
Ifg
=
g
1
g
2, then g
1
,
g
2
∈
A
B
*;
(5)
Ifg
=
{
g
1
}
K and K
-
1
∈
K
B, then g
1
∈
A
B
*.Owning setA
B
* is used to describe all messages owned by entity B. The owning set of an entity will change with the state of the entity. When trader B receives messages S
B from their opponent, they could use those messages to obtain information from third party. If a strand of entity B includes flushing trace F
*
:
〈
-
h
.
C
,
⨁
h
.
B
〉, we have h
∈
A
B
*. We stipulate A
B
*
[
h
] as the owning set when entity B receives message h. If S
B is the set of messages entity B received from others at that time, then A
B
*
[
S
B
] will be all messages that entity B owns at the time they receive messages S
B.Definition 11.
Define owning setA
B
*
[
S
B
] as follows, where S
B is the set of messages received by entity B:(1)
S
B
⊆
A
B
*
[
S
B
], E
B
⊆
A
B
*
[
S
B
], K
B
⊆
A
B
*
[
S
B
], and F
(
E
B
,
E
B
′
)
⊆
A
B
*
[
S
B
], where E
B is the evidence set of entity B, K
B is the key set, and F
(
E
B
,
E
B
′
) is the set of evidence-corresponding-relations from B to B
′;
(2)
∀
g
,
h
∈
A
B
*
[
S
B
], one has g
h
∈
A
B
*
[
S
B
];
(3)
∀
g
∈
A
B
*
[
S
B
], ∀
K
∈
K
B, one has {
g
}
K
∈
A
B
*
[
S
B
];
(4)
Ifg
=
g
1
g
2
∈
A
B
*
[
S
B
], then g
1
,
g
2
∈
A
B
*
[
S
B
];
(5)
Ifg
=
{
g
1
}
K
∈
A
B
*
[
S
B
] and K
-
1
∈
K
B, then g
1
∈
A
B
*
[
S
B
];
(6)
If-
a
.
B
∈
A
T
∧
+
a
.
T
∈
A
B
∧
a
∈
A
B
*
[
S
B
], in which there is a sequence 〈
-
a
.
B
,
+
c
.
TTP
〉 in T’s strand, where -
c
.
TTP
∈
A
B, then c
∈
A
B
*
[
S
B
].
The sixth rule expresses the situation in which traderB sends message a to third party T after they received messages S
B, and then T sends message c to B; thus entity B owns c. The third party here refers to all participators except traders in E-commerce protocol, including banks and arbitration institutions, as well as the trusted third party (TTP). Third party in E-commerce protocols is regular entity, and its strands are regular strands. For convenience, we use Definition 7 to define terms of regular strands. Edges between nodes remain unchanged, which are defined by “→” and “⇒” in classical strands space model. In addition, we add a status node [15] at the end of each strand, which does not send or receive messages, only to be used to express the end of a sequence of events. In the description of strands, we follow the way Fröschle did in [15], using hollow circle and solid circle, respectively, to express the node of termination status and normal nodes.


### 4.3. Fairness Validation Process

Based on the fairness definition and the extended strand space model above, we put forward a formal method of fairness verification. The verification process is shown in Figure1.Figure 1
Fairness verification schemes.BuildF
(
E
B
1
,
E
B
2
): each E-commerce protocol contains some description messages. These messages express the relationship of evidences which traders exchange. Therefore, we build evidence-corresponding-relations base on them. Because traders can forge evidences and description messages, we use set F
(
E
B
,
E
B
′
) to express all goods descriptions traders can forge.BuildT strand: all entities except traders in E-commerce protocol are regular entities; thus, we use a regular strand to model those entities. Each T has a fixed number of strands. We need to select T strands according to the implementation of protocols. For convenience, the study defines terms in T strand by Definition 7 and adds a status node in the end of the strand.DefineA
B
1 and A
B
2: sending-receiving sets A
B
1 and A
B
2 of traders B
1 and B
2 are fixed. Sending messages of a trader are all messages that protocol formatted, while receiving messages is not only protocol formatted but also meets the needs of their own interest.Traverse traders’ abnormal-terminated strands: abnormal terminated means a trader has not got the evidences they want at the end of a transaction. We first establish an abnormal-terminated strand of a trader with regular entities model and then detect whether the other trader could obtain the evidences they want. E-commerce protocols may be terminated abnormally in different running stages, and each trader may have more than one abnormal-terminated strand. We use regular strand to model trader’s abnormal-terminated event sequence and detect whether a dishonest trader could gain evidences from an honest trader. Benefiting from assumptions, there will be a finite number of abnormal-terminated strands of each trader, which makes the detection process to be terminated possible.Considerf
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
]: f
1
(
e
1
) stands for the evidence B
1 expected; S
B
2 stands for messages B
1 received from an abnormal-terminated strand of B
2; A
B
1
*
[
S
B
2
] stands for all messages B
1 owned after they receive messages S
B
2. f
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
] means that B
1 got the evidence they want, while B
2 did not; then, the protocol is unfair. The difficulty of this step is how to generate set A
B
1
*
[
S
B
2
]. The recursively defined set A
B
1
*
[
S
B
2
] is an infinite set, and judgments about formula f
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
] need reasoning and induction. The specific process will be given in the next chapter.Based on the strand space model, we use graphs to illustrate the process of an implementation of a protocol. If the protocol is unfair, an unfair execution process will be given by the strand space model in an intuitive way. For this reason, we modify the protocol and then verify the modified protocol again, until it is fair.


## 4.1. The Formal Definition of Fairness

Fairness is one of the basic security properties that E-commerce protocols must meet; the acknowledged definition of fairness can be referred to [8–15]: an exchange is fair means that, at the end of the exchange, either each player receives the terms they expect or none receives any information about the other’s terms. Fairness evidences are those terms that players expect in transaction. Fairness of E-commerce protocols includes the fair exchange of evidences and the fair evidences in exchange. The exchange in an electronic transaction is considered to be equivalent, so evidences exchanged in electronic transaction should be equivalent; otherwise, a trader may benefit from the other by forging unequal exchange evidences. To verify the fairness of the corresponding relation of evidences, the mapping relationship of defining evidences is in the following.Definition 6.
TradersB
1, B
2
∈
N; N is the set of traders’ identification; E
B
1 and E
B
2 are sets of fairness evidences belonging to traders B
1 and B
2, respectively. The evidence-corresponding-relation is a bijective function f
B
1
:
E
B
1
→
E
B
2. Its inverse function is f
B
2
:
E
B
2
→
E
B
1. ∀
e
∈
E
B
1, ∃
!
e
′
=
f
B
1
(
e
)
∈
E
B
2, here, f
B
1
(
e
) means the evidences of B
2 which B
1 expects. The set of functions f
B
1
(
e
) is denoted by F
(
E
B
1
,
E
B
2
). Similarly, the set from B
2 to B
1 is denoted by F
(
E
B
2
,
E
B
1
).Evidences exchanged in electronic transactions need to be mutually corresponded. Each trader has the ability to evaluate evidences, and the corresponding relations of traders’ evidence act as an evaluation tool to measure equivalence of the evidence’s value. We can verify whether traders have forged evidences from the formulae
′
=
f
(
e
). If the formula is not established, it means that someone has forged evidences so that evidences exchanged are not equivalent. In our research, we assume that if a trader receives unequal evidence from others, they would like to ignore this message. This means that if a participant uses forged evidences in transaction, the other participant will refuse to accept the evidence.The fair exchange of evidence, in the point of view of a trader, means that ifA has not obtained the evidence from B, then B could not obtain A’s evidence; else, if A obtained the evidence of B, whether B obtained evidence from A will not be considered anymore. Popular to say, the fairness means each participant of a transaction is not at a disadvantage. Combined with Definition 5, we define fairness as follows.Definition 7.
Given an E-commerce protocolΓ, here, B
1, B
2
∈
N, e
1
∈
E
B
1, e
2
∈
E
B
2, E
B
1, and E
B
2 are sets of evidences of B
1 and B
2. f
1
∈
F
(
E
B
1
,
E
B
2
) andf
2
∈
F
(
E
B
2
,
E
B
1
) are evidence-corresponding-relations between B
1 and B
2, respectively. Protocol Γ is fair, if and only if the following two conditions hold:(1)
at the end of an exchange, if traderB
1 has not obtained f
1
(
e
1
), then B
2 cannot get e
1;
(2)
at the end of an exchange, if traderB
2 has not obtained f
2
(
e
2
), then B
1 cannot get e
2.During the fairness validation process, we first generate a trader’s strand which he has not got at the end of a transaction; the other trader acts as a penetrator to analyze whether the penetrator could obtain the evidence they want through a variety of deceptions or attacks from one of the strands above. The penetrator model here is different from the model used in the classical strand space model. Therefore, we need to model the behaviors of traders and extend related theories of the strand space model to describe E-commerce protocol and its properties.


## 4.2. Extension of Strand Space Model

Traders in E-commerce protocols are dishonest not like regular entities and penetrator entities in general security protocols. Apart from traders, all participants in E-commerce protocols are regular entities and perform in accordance with the agreement provisions. Because their sequence of events and entity model are constant, each of them has only limited numbers of strands. While traders may opt out of the transaction, or repeatedly use outdated evidences, like orders and electronic money, they may use a variety of behaviors to obtain benefits, thus the events sequence of these entities may not be complete in accordance with the protocol. Original strand space model uses the penetrator model to describe behaviors of attackers. A penetrator can intercept, send, forgery, tamper messages, and so forth. They can do almost everything except for resolving cryptographic algorithms, while traders are still bounded by the protocol. If using penetrator model to describe traders’ behaviors, we might make a wrong judgment to a correct protocol. Thus, we need to establish a model to describe the behaviors of transactions between buyers and sellers. The capability of this model is between regular entities and penetrator entities. We call it trader model.The study imitates the penetrator model in original strand space model to build the trader model and describe the behaviors of traders into atomic behaviors and their combinations. E-commerce protocols have little constrains for traders, similarly, traders cannot be completely separated from the protocol, so we use atomic behavior as well as some constraints on these atoms to describe the behaviors of traders. The model assumptions are showed as follows:(1)
traders can encrypt, decrypt, connect, and decompose message;
(2)
traders can forge evidences and messages by using unequal evidences to get the other’s interests;
(3)
traders can send or receive messages belonging to this trader in protocol; only the messages are in specified format of protocol;
(4)
both entities and messages in E-commerce protocols satisfy authentication and confidentiality, which being basic properties of security protocols; the protocol is insecure if these two properties are not met; fairness and nonrepudiation are based on the premise of security of the protocol; we should verify security before analysis fairness;
(5)
the sequence of events in traders model needs not to be the order in accordance with the protocol; this assumption needs to describe the behaviors of traders in the form of atoms.Considering E-commerce, protocols satisfy authentication and confidentiality; we add the identifiers of entities into the concept of the term, and terms in our model are represented as a 3-tuple. This modification eliminates the need for verification of authentication. Term is defined as follows.Definition 8.
Term is a 3-tuple〈
σ
,
a
,
B
〉, where σ
∈
{
+
,
-
,
⨁
}, a
∈
A, and B
∈
N. A is the message set and P is the set of entities’ identifier. 〈
+
,
a
,
B
〉 means entity B sends message a; 〈
-
,
a
,
B
〉 means an entity receives message a from entity B; and 〈
⨁
,
a
,
B
〉 means entity B owns message a. For convenience, abbreviate term 〈
σ
,
a
,
B
〉 as σ
a
.
B; a is the unsigned portion of σ
a
.
B.
We use symbol “⨁” to meet the third assumption. Traders in E-commerce protocols cannot receive or send some messages, but can calculate. In the following, A
B is the set of terms that B could send or receive in protocol, and A
B
* is the set of messages B owns at the time.
Traders’ atomic behaviors can be described by trace.Definition 9.
A trader trace is one of the following:(1)
M
*: text message: 〈
⨁
t
.
B
,
+
t
.
B
〉, where +
t
.
B
∈
A
B, t
∈
A
B
*, and B
∈
N; B is an entity’s identifier; trace M
* expresses entity B sending message t;
(2)
F
*: flushing: 〈
-
t
.
C
,
⨁
t
.
B
〉, where -
t
.
C
∈
A
B and B, C
∈
N; trace F
* means entity B receives message t, and then B owns t;
(3)
P
*: falsifying: 〈
⨁
e
.
B
,
⨁
f
.
B
〉, where e
∈
E
B and f
∈
F
(
E
B
,
E
B
′
); E
B is the set of evidence belonging to entity B, F
(
E
B
,
E
B
′
) which is the set of evidence-corresponding-relations from B to B
′; trace P
* expresses the situation that entity B forges evidence and its descriptions in protocol;
(4)
C
*: concatenation: 〈
⨁
g
.
B
,
⨁
h
.
B
,
⨁
g
h
.
B
〉, where g, h
∈
A
B
* and B
∈
N; trace C
* means that if entity B owns messages g and h, then B owns g
h;
(5)
S
*: separation: 〈
⨁
g
h
.
B
,
⨁
g
.
B
,
⨁
h
.
B
〉, where g
h
∈
A
B
* and B
∈
N; trace S
* means that if entity B owns message g
h, then B owns g and h;
(6)
K
*: key: 〈
⨁
K
.
B
〉, where K
∈
K
B, K
B is the set of keys B owns; trace K
* means entity B owns key K;
(7)
E
*: encryption: 〈
⨁
K
.
B
,
⨁
h
.
B
,
⨁
{
h
}
K
.
B
〉, where K
∈
K
B, h
∈
A
B
*, and B
∈
N; trace E
*expresses the situation that entity B can encrypt h with key K;
(8)
D
*: decryption: 〈
⨁
{
h
}
K
.
B
,
⨁
K
-
1
.
B
,
⨁
h
.
B
〉, where K
∈
K
B, {
h
}
K
∈
A
B
*, and B
∈
N; trace D
* expresses the situation that entity B can decrypt {
h
}
K into h if they own both {
h
}
K and K
-
1.The strand of a trader is composed of nodes in tracesM
* and F
*, expressing a sequence of events of the entity, and the remaining six traces are used to describe the entity’s message space. Here, “+” and “−” denote messages delivered between entities, and “⨁” stands for messages generated inside entities. The classical strand space model does not describe the concept “owned,” because the number of messages sent or received by generators are unlimited. Messages which can be sent or received are owned by penetrators, while traders can only send or receive messages belonging to them. We propose the concept "owns" to describe the ability that a trader can process all the messages that they encountered. In summary, we modify the definition of terms to solve authentication and confidentiality, remove the tee trace T, add trace P
* and symbol “⨁” to limit traders’ abilities, and, finally, build the traders model.Classical strand space model uses edges “→” and “⇒” to describe the causal relationship between terms, where “→” edge expresses delivering message between entities, and “⇒” edge describes an entity’s state transition. Because traders’ entities are semihonest, one may need more than one strand to describe their behaviors. Using atomic behaviors to build the trader model could describe the trader’s behaviors nicely but is not conducive to express the causal relationship between nodes. For this purpose, we define owning set A
B
* and sending-receiving set A
B, where owning set A
B
* is a concept similar to ideal in the classical model and stands for messages that entity B has owned. The set is generated in a recursive way. Sending-receiving set A
B contains messages which B could send or receive and is fixed in a specific protocol. The owning set A
B
* is defined as follows.Definition 10.
A
B
* is an owning set of entity B; if g
∈
A
B
*, then(1)
E
B
⊆
A
B
*, K
B
⊆
A
B
* and F
(
E
B
,
E
B
′
)
⊆
A
B
*, where E
B is the set of B’s evidences, K
B is the set of B’s keys, and F
(
E
B
,
E
B
′
) is the set of evidence-corresponding-relations from B to B
′;
(2)
∀
h
∈
A
B
*, one has g
h
∈
A
B
*;
(3)
∀
K
∈
K
B, one has {
g
}
K
∈
A
B
*;
(4)
Ifg
=
g
1
g
2, then g
1
,
g
2
∈
A
B
*;
(5)
Ifg
=
{
g
1
}
K and K
-
1
∈
K
B, then g
1
∈
A
B
*.Owning setA
B
* is used to describe all messages owned by entity B. The owning set of an entity will change with the state of the entity. When trader B receives messages S
B from their opponent, they could use those messages to obtain information from third party. If a strand of entity B includes flushing trace F
*
:
〈
-
h
.
C
,
⨁
h
.
B
〉, we have h
∈
A
B
*. We stipulate A
B
*
[
h
] as the owning set when entity B receives message h. If S
B is the set of messages entity B received from others at that time, then A
B
*
[
S
B
] will be all messages that entity B owns at the time they receive messages S
B.Definition 11.
Define owning setA
B
*
[
S
B
] as follows, where S
B is the set of messages received by entity B:(1)
S
B
⊆
A
B
*
[
S
B
], E
B
⊆
A
B
*
[
S
B
], K
B
⊆
A
B
*
[
S
B
], and F
(
E
B
,
E
B
′
)
⊆
A
B
*
[
S
B
], where E
B is the evidence set of entity B, K
B is the key set, and F
(
E
B
,
E
B
′
) is the set of evidence-corresponding-relations from B to B
′;
(2)
∀
g
,
h
∈
A
B
*
[
S
B
], one has g
h
∈
A
B
*
[
S
B
];
(3)
∀
g
∈
A
B
*
[
S
B
], ∀
K
∈
K
B, one has {
g
}
K
∈
A
B
*
[
S
B
];
(4)
Ifg
=
g
1
g
2
∈
A
B
*
[
S
B
], then g
1
,
g
2
∈
A
B
*
[
S
B
];
(5)
Ifg
=
{
g
1
}
K
∈
A
B
*
[
S
B
] and K
-
1
∈
K
B, then g
1
∈
A
B
*
[
S
B
];
(6)
If-
a
.
B
∈
A
T
∧
+
a
.
T
∈
A
B
∧
a
∈
A
B
*
[
S
B
], in which there is a sequence 〈
-
a
.
B
,
+
c
.
TTP
〉 in T’s strand, where -
c
.
TTP
∈
A
B, then c
∈
A
B
*
[
S
B
].
The sixth rule expresses the situation in which traderB sends message a to third party T after they received messages S
B, and then T sends message c to B; thus entity B owns c. The third party here refers to all participators except traders in E-commerce protocol, including banks and arbitration institutions, as well as the trusted third party (TTP). Third party in E-commerce protocols is regular entity, and its strands are regular strands. For convenience, we use Definition 7 to define terms of regular strands. Edges between nodes remain unchanged, which are defined by “→” and “⇒” in classical strands space model. In addition, we add a status node [15] at the end of each strand, which does not send or receive messages, only to be used to express the end of a sequence of events. In the description of strands, we follow the way Fröschle did in [15], using hollow circle and solid circle, respectively, to express the node of termination status and normal nodes.


## 4.3. Fairness Validation Process

Based on the fairness definition and the extended strand space model above, we put forward a formal method of fairness verification. The verification process is shown in Figure1.Figure 1
Fairness verification schemes.BuildF
(
E
B
1
,
E
B
2
): each E-commerce protocol contains some description messages. These messages express the relationship of evidences which traders exchange. Therefore, we build evidence-corresponding-relations base on them. Because traders can forge evidences and description messages, we use set F
(
E
B
,
E
B
′
) to express all goods descriptions traders can forge.BuildT strand: all entities except traders in E-commerce protocol are regular entities; thus, we use a regular strand to model those entities. Each T has a fixed number of strands. We need to select T strands according to the implementation of protocols. For convenience, the study defines terms in T strand by Definition 7 and adds a status node in the end of the strand.DefineA
B
1 and A
B
2: sending-receiving sets A
B
1 and A
B
2 of traders B
1 and B
2 are fixed. Sending messages of a trader are all messages that protocol formatted, while receiving messages is not only protocol formatted but also meets the needs of their own interest.Traverse traders’ abnormal-terminated strands: abnormal terminated means a trader has not got the evidences they want at the end of a transaction. We first establish an abnormal-terminated strand of a trader with regular entities model and then detect whether the other trader could obtain the evidences they want. E-commerce protocols may be terminated abnormally in different running stages, and each trader may have more than one abnormal-terminated strand. We use regular strand to model trader’s abnormal-terminated event sequence and detect whether a dishonest trader could gain evidences from an honest trader. Benefiting from assumptions, there will be a finite number of abnormal-terminated strands of each trader, which makes the detection process to be terminated possible.Considerf
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
]: f
1
(
e
1
) stands for the evidence B
1 expected; S
B
2 stands for messages B
1 received from an abnormal-terminated strand of B
2; A
B
1
*
[
S
B
2
] stands for all messages B
1 owned after they receive messages S
B
2. f
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
] means that B
1 got the evidence they want, while B
2 did not; then, the protocol is unfair. The difficulty of this step is how to generate set A
B
1
*
[
S
B
2
]. The recursively defined set A
B
1
*
[
S
B
2
] is an infinite set, and judgments about formula f
1
(
e
1
)
∈
A
B
1
*
[
S
B
2
] need reasoning and induction. The specific process will be given in the next chapter.Based on the strand space model, we use graphs to illustrate the process of an implementation of a protocol. If the protocol is unfair, an unfair execution process will be given by the strand space model in an intuitive way. For this reason, we modify the protocol and then verify the modified protocol again, until it is fair.


## 5. Case Analysis

We use the EMH protocol to test the fairness validation method which we propose. EMH protocol is an offline TTP electronic payment protocol proposed by Alaraj and Munro in 2007 [19]. The purpose of this protocol is to exchange a digital product (D) with a payment (P) between a customer (C) and a merchant (M). When we say that the protocol is fair, it means that, at the end of a transaction, either M gets P and C gets D or both of them do not get any message and vice versa. Using this protocol for the experiment can help to introduce the fairness verification process in detail and can explain the reason why we define fairness and extend the strand space model in such a way vividly.


### 5.1. Protocol Description

Identifier and symbol description includes the following:C: customer,
M: merchant,
TTP: the trusted third party,
CB: the customer’s bank, having the case that while the CB can also be considered as a TTP, TTP and CB are considered as third parties in our verification process and are modeled by regular entity,
D: digital product,
P: buyer’s payment voucher, where D and P are the so-called fairness evidence in our model,
Desc: description of digital product, which is the link between D and P, where we build evidence corresponding relationship based on Desc, where Desc
C
(
P
) and Desc
M
(
D
) represent the evidence corresponding relationship between C and M, respectively,
h
(
x
): a strong collision-resistant one-way hash function, such as MD5,
P
K
a: RSA public key of entity a,
S
K
a: RSA private key of entity a,
P
_
cert: payment’s certificate that is issued by the CB, with the contents of P
_
cert being d, description of payment (the amount), h
p, hash value of payment, h
e
p, hash value of encrypted payment with P
K
a, and SigCB, CB’s signature on P
_
cert,
CertCT: the certificate for the shared public key between C and TTP, which is issued by the TTP,
Enc
P
K
a
(
X
)
=
{
X
}
P
K
a: an RSA encryption of X using the public key P
K
a,
Dec
S
K
a
(
Y
)
=
{
Y
}
S
K
a
=
X: an RSA decryption of Y using the private key S
K
a,
Enc
P
K
a
(
X
)
=
{
X
}
P
K
a: the RSA signature of party A, that is, encryption of the hash value of X using the private key S
K
a,
A
→
B
:
X: A which sends message X to B,
X
∥
Y: concatenation of messages X and Y.
EMH protocol is divided into three phases: the preexchange phase, the exchange phase, and the dispute settlement phase; details are given as follows.(1) The preexchange phase includes the following:mes1:TTP
→
C
:
Cert
CT;
mes2:CB
→
C
:
P
_
cert.(2) The exchange phase includes the following:mes3:C
→
M
:
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
);
mes4:M
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes5:C
→
M
:
S
K
CT.(3) The dispute settlement phase includes the following:mes6:M
→
TTP
:
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes7:TTP
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes8:TTP
→
M
:
S
K
CT.The preexchange phase aims to award certificates fromTTP and CB to C and do nothing between C and M, so we omit this phase in the verification process, considering only the last two stages.


### 5.2. Verification Process

To verify the fairness of EMH protocol, we need to prove thatf
C
(
P
)
∉
A
C
*
[
S
C
] and f
M
(
D
)
∉
A
M
*
[
S
M
] both are true. First, we verify f
C
(
P
)
∉
A
C
*
[
S
C
]; in the following proof, we could get f
C
(
P
)
∈
A
C
*
[
S
C
].


#### 5.2.1. Build the Set of Evidence Corresponding Relations

Define bijective functionsDesc
C
:
E
C
→
E
M and Desc
M
:
E
M
→
E
C, where Desc
C
∈
F
(
E
C
,
E
M
) and Desc
M
∈
F
(
E
M
,
E
C
). F
(
E
C
,
E
M
) and F
(
E
M
,
E
C
) are sets of evidence corresponding relations belonging to M and C, respectively. For P
∈
E
C, D
∈
E
M, and ∃
Desc
∈
F
(
E
C
,
E
M
) and its inverse Desc
-
1
∈
F
(
E
M
,
E
C
), D
=
Desc
(
P
)
∧
P
=
Desc
-
1
(
D
).


#### 5.2.2. TTP Strands

TTP are regular entities, building its strands directly. Figure2 is a regular strand of TTP.Figure 2
Regular strand of TTP.TTP checks whetherD
M
=
Desc
M
(
P
) is established; if so, it sends message {
D
M
}
P
K
CT
∥
Sig
M
(
D
M
) to C and sends S
K
CT to M.


#### 5.2.3. Determine Sending-Receiving Set

Consider(1)
A
C
=
{
+
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
M
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
TTP
,
0
+
S
K
CT
.
M
{
P
}
P
K
CT
}
A
M
=
{
-
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
+
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
+
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
0
×
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
-
S
K
CT
.
C
,
-
S
K
CT
.
TTP
{
P
}
P
K
CT
}
.


#### 5.2.4. Establish Abnormal-Terminated Strands

We first analyze whether traderM could obtain the evidence P when trader C is abnormal-terminated strand (Figure 3).Figure 3
An abnormal-terminated strand of traderC.


#### 5.2.5. Build Traders Model

We buildM’s trader model by the abnormal-terminated strand of C. Assuming that M could obtain P; that is, there exists a flushing trace F
*
:
〈
-
S
K
CT
.
TTP
〉 or 〈
-
S
K
CT
.
C
〉. Because the abnormal-terminated strand of C does not contain node 〈
+
S
K
CT
.
TTP
〉, we ignore the situation F
*
:
〈
-
S
K
CT
.
C
〉.Suppose the situation where there exists a node〈
-
S
K
CT
.
TTP
〉 in M’s strand. Because TTP strand is regular, there exists a node 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉 in M’s strand.And because-
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
∈
A
M, we have S
M
=
{
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
}. Then, we analyze M’s owning set A
M
*
[
S
M
].By Definition11, we have(2)
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∈
A
M
*
[
S
M
]
(3)
D
M
=
Desc
M
(
P
)
,
Desc
M
,
D
M
∈
A
M
*
[
S
M
]
(4)
{
D
M
}
P
K
CT
,
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
(5)
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
.BecauseDesc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
∈
A
M; there exists a text message trace M
* in M’s strand, where M
* is 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉, which means that the assumption holds; trader M can obtain the evidence P. The protocol is unfair. Figure 4 is the unfair execution process described by strand space model.Figure 4
An unfair case of the protocol.


#### 5.2.6. Unfair Analysis and Protocol Improvements

Protocol is unfair because theTTP cannot accurately determine whether M has forged evidence. Trader M can obtain S
K
CT from TTP by forging evidence D and the description message Desc and then get C’s evidence. We modify protocol; thus the TTP could compare description information of the two parties and do a fair judgment.Here is the modified protocol.(1) The preexchange phase includes the following:mes1:TTP
→
C
:
Cert
CT;
mes2:CB
→
C
:
P
_
cert.(2) The exchange phase includes the following:mes3:C
→
M
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
);
mes4:M
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes5:C
→
M
:
S
K
CT.(3) The dispute settlement phase includes the following:mes6:M
→
TTP
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
)
∥
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes7:TTP
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes8:TTP
→
M
:
S
K
CT.Based on the unfair reasons above, we improve message 3 and message 6. TTP will determineDesc
C
=
Desc
M
∧
D
M
=
Desc
M
(
P
) first, when they receive a request message from M. If the formula is true, TTP sends S
K
CT to M and D
M to C.By verifying the fairness of the modified protocol continuously, we then establish abnormal-terminated strands ofM and C, respectively, and judge each of them. The concreted analysis process of improved protocol will not be described here. Figure 5 is the model description of the modified protocol in the same situation. From it, we can know that M has to send their evidence D in order to obtain P, because the TTP has more discrimination capability.Figure 5
Analysis of the modified protocol.The verification steps are the same as mentioned above, so we did not propose the detailed description here.


### 5.3. Analysis of Experimental Results

By using EMH protocol to test the fair authentication method proposed in this paper, we draw some conclusions: first, the method can verify the fairness of E-commerce protocols effectively and give an accurate judgment about the fair exchange of evidences and the fair evidences in exchange; second, the method generates a finite number of abnormal-terminated strands and builds the trader model explicitly by inductive reasoning, which enables the verification process to be terminated; in addition, it has a practical value in design and improvement of E-commerce protocols.


## 5.1. Protocol Description

Identifier and symbol description includes the following:C: customer,
M: merchant,
TTP: the trusted third party,
CB: the customer’s bank, having the case that while the CB can also be considered as a TTP, TTP and CB are considered as third parties in our verification process and are modeled by regular entity,
D: digital product,
P: buyer’s payment voucher, where D and P are the so-called fairness evidence in our model,
Desc: description of digital product, which is the link between D and P, where we build evidence corresponding relationship based on Desc, where Desc
C
(
P
) and Desc
M
(
D
) represent the evidence corresponding relationship between C and M, respectively,
h
(
x
): a strong collision-resistant one-way hash function, such as MD5,
P
K
a: RSA public key of entity a,
S
K
a: RSA private key of entity a,
P
_
cert: payment’s certificate that is issued by the CB, with the contents of P
_
cert being d, description of payment (the amount), h
p, hash value of payment, h
e
p, hash value of encrypted payment with P
K
a, and SigCB, CB’s signature on P
_
cert,
CertCT: the certificate for the shared public key between C and TTP, which is issued by the TTP,
Enc
P
K
a
(
X
)
=
{
X
}
P
K
a: an RSA encryption of X using the public key P
K
a,
Dec
S
K
a
(
Y
)
=
{
Y
}
S
K
a
=
X: an RSA decryption of Y using the private key S
K
a,
Enc
P
K
a
(
X
)
=
{
X
}
P
K
a: the RSA signature of party A, that is, encryption of the hash value of X using the private key S
K
a,
A
→
B
:
X: A which sends message X to B,
X
∥
Y: concatenation of messages X and Y.
EMH protocol is divided into three phases: the preexchange phase, the exchange phase, and the dispute settlement phase; details are given as follows.(1) The preexchange phase includes the following:mes1:TTP
→
C
:
Cert
CT;
mes2:CB
→
C
:
P
_
cert.(2) The exchange phase includes the following:mes3:C
→
M
:
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
);
mes4:M
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes5:C
→
M
:
S
K
CT.(3) The dispute settlement phase includes the following:mes6:M
→
TTP
:
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes7:TTP
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes8:TTP
→
M
:
S
K
CT.The preexchange phase aims to award certificates fromTTP and CB to C and do nothing between C and M, so we omit this phase in the verification process, considering only the last two stages.


## 5.2. Verification Process

To verify the fairness of EMH protocol, we need to prove thatf
C
(
P
)
∉
A
C
*
[
S
C
] and f
M
(
D
)
∉
A
M
*
[
S
M
] both are true. First, we verify f
C
(
P
)
∉
A
C
*
[
S
C
]; in the following proof, we could get f
C
(
P
)
∈
A
C
*
[
S
C
].


### 5.2.1. Build the Set of Evidence Corresponding Relations

Define bijective functionsDesc
C
:
E
C
→
E
M and Desc
M
:
E
M
→
E
C, where Desc
C
∈
F
(
E
C
,
E
M
) and Desc
M
∈
F
(
E
M
,
E
C
). F
(
E
C
,
E
M
) and F
(
E
M
,
E
C
) are sets of evidence corresponding relations belonging to M and C, respectively. For P
∈
E
C, D
∈
E
M, and ∃
Desc
∈
F
(
E
C
,
E
M
) and its inverse Desc
-
1
∈
F
(
E
M
,
E
C
), D
=
Desc
(
P
)
∧
P
=
Desc
-
1
(
D
).


### 5.2.2. TTP Strands

TTP are regular entities, building its strands directly. Figure2 is a regular strand of TTP.Figure 2
Regular strand of TTP.TTP checks whetherD
M
=
Desc
M
(
P
) is established; if so, it sends message {
D
M
}
P
K
CT
∥
Sig
M
(
D
M
) to C and sends S
K
CT to M.


### 5.2.3. Determine Sending-Receiving Set

Consider(1)
A
C
=
{
+
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
M
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
TTP
,
0
+
S
K
CT
.
M
{
P
}
P
K
CT
}
A
M
=
{
-
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
+
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
+
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
0
×
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
-
S
K
CT
.
C
,
-
S
K
CT
.
TTP
{
P
}
P
K
CT
}
.


### 5.2.4. Establish Abnormal-Terminated Strands

We first analyze whether traderM could obtain the evidence P when trader C is abnormal-terminated strand (Figure 3).Figure 3
An abnormal-terminated strand of traderC.


### 5.2.5. Build Traders Model

We buildM’s trader model by the abnormal-terminated strand of C. Assuming that M could obtain P; that is, there exists a flushing trace F
*
:
〈
-
S
K
CT
.
TTP
〉 or 〈
-
S
K
CT
.
C
〉. Because the abnormal-terminated strand of C does not contain node 〈
+
S
K
CT
.
TTP
〉, we ignore the situation F
*
:
〈
-
S
K
CT
.
C
〉.Suppose the situation where there exists a node〈
-
S
K
CT
.
TTP
〉 in M’s strand. Because TTP strand is regular, there exists a node 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉 in M’s strand.And because-
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
∈
A
M, we have S
M
=
{
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
}. Then, we analyze M’s owning set A
M
*
[
S
M
].By Definition11, we have(2)
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∈
A
M
*
[
S
M
]
(3)
D
M
=
Desc
M
(
P
)
,
Desc
M
,
D
M
∈
A
M
*
[
S
M
]
(4)
{
D
M
}
P
K
CT
,
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
(5)
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
.BecauseDesc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
∈
A
M; there exists a text message trace M
* in M’s strand, where M
* is 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉, which means that the assumption holds; trader M can obtain the evidence P. The protocol is unfair. Figure 4 is the unfair execution process described by strand space model.Figure 4
An unfair case of the protocol.


### 5.2.6. Unfair Analysis and Protocol Improvements

Protocol is unfair because theTTP cannot accurately determine whether M has forged evidence. Trader M can obtain S
K
CT from TTP by forging evidence D and the description message Desc and then get C’s evidence. We modify protocol; thus the TTP could compare description information of the two parties and do a fair judgment.Here is the modified protocol.(1) The preexchange phase includes the following:mes1:TTP
→
C
:
Cert
CT;
mes2:CB
→
C
:
P
_
cert.(2) The exchange phase includes the following:mes3:C
→
M
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
);
mes4:M
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes5:C
→
M
:
S
K
CT.(3) The dispute settlement phase includes the following:mes6:M
→
TTP
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
)
∥
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes7:TTP
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes8:TTP
→
M
:
S
K
CT.Based on the unfair reasons above, we improve message 3 and message 6. TTP will determineDesc
C
=
Desc
M
∧
D
M
=
Desc
M
(
P
) first, when they receive a request message from M. If the formula is true, TTP sends S
K
CT to M and D
M to C.By verifying the fairness of the modified protocol continuously, we then establish abnormal-terminated strands ofM and C, respectively, and judge each of them. The concreted analysis process of improved protocol will not be described here. Figure 5 is the model description of the modified protocol in the same situation. From it, we can know that M has to send their evidence D in order to obtain P, because the TTP has more discrimination capability.Figure 5
Analysis of the modified protocol.The verification steps are the same as mentioned above, so we did not propose the detailed description here.


## 5.2.1. Build the Set of Evidence Corresponding Relations

Define bijective functionsDesc
C
:
E
C
→
E
M and Desc
M
:
E
M
→
E
C, where Desc
C
∈
F
(
E
C
,
E
M
) and Desc
M
∈
F
(
E
M
,
E
C
). F
(
E
C
,
E
M
) and F
(
E
M
,
E
C
) are sets of evidence corresponding relations belonging to M and C, respectively. For P
∈
E
C, D
∈
E
M, and ∃
Desc
∈
F
(
E
C
,
E
M
) and its inverse Desc
-
1
∈
F
(
E
M
,
E
C
), D
=
Desc
(
P
)
∧
P
=
Desc
-
1
(
D
).


## 5.2.2. TTP Strands

TTP are regular entities, building its strands directly. Figure2 is a regular strand of TTP.Figure 2
Regular strand of TTP.TTP checks whetherD
M
=
Desc
M
(
P
) is established; if so, it sends message {
D
M
}
P
K
CT
∥
Sig
M
(
D
M
) to C and sends S
K
CT to M.


## 5.2.3. Determine Sending-Receiving Set

Consider(1)
A
C
=
{
+
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
M
,
0
-
{
Desc
C
(
P
)
}
P
K
CT
∥
Sig
M
(
Desc
C
(
P
)
)
.
TTP
,
0
+
S
K
CT
.
M
{
P
}
P
K
CT
}
A
M
=
{
-
Desc
C
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
,
0
+
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
+
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
0
×
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
,
0
-
S
K
CT
.
C
,
-
S
K
CT
.
TTP
{
P
}
P
K
CT
}
.


## 5.2.4. Establish Abnormal-Terminated Strands

We first analyze whether traderM could obtain the evidence P when trader C is abnormal-terminated strand (Figure 3).Figure 3
An abnormal-terminated strand of traderC.


## 5.2.5. Build Traders Model

We buildM’s trader model by the abnormal-terminated strand of C. Assuming that M could obtain P; that is, there exists a flushing trace F
*
:
〈
-
S
K
CT
.
TTP
〉 or 〈
-
S
K
CT
.
C
〉. Because the abnormal-terminated strand of C does not contain node 〈
+
S
K
CT
.
TTP
〉, we ignore the situation F
*
:
〈
-
S
K
CT
.
C
〉.Suppose the situation where there exists a node〈
-
S
K
CT
.
TTP
〉 in M’s strand. Because TTP strand is regular, there exists a node 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉 in M’s strand.And because-
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
∈
A
M, we have S
M
=
{
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
.
C
}. Then, we analyze M’s owning set A
M
*
[
S
M
].By Definition11, we have(2)
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∈
A
M
*
[
S
M
]
(3)
D
M
=
Desc
M
(
P
)
,
Desc
M
,
D
M
∈
A
M
*
[
S
M
]
(4)
{
D
M
}
P
K
CT
,
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
(5)
Desc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
∈
A
M
*
[
S
M
]
.BecauseDesc
M
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
∈
A
M; there exists a text message trace M
* in M’s strand, where M
* is 〈
+
Desc
∥
{
P
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
)
∥
{
D
M
}
P
K
CT
∥
Sig
M
(
D
M
)
.
M
〉, which means that the assumption holds; trader M can obtain the evidence P. The protocol is unfair. Figure 4 is the unfair execution process described by strand space model.Figure 4
An unfair case of the protocol.


## 5.2.6. Unfair Analysis and Protocol Improvements

Protocol is unfair because theTTP cannot accurately determine whether M has forged evidence. Trader M can obtain S
K
CT from TTP by forging evidence D and the description message Desc and then get C’s evidence. We modify protocol; thus the TTP could compare description information of the two parties and do a fair judgment.Here is the modified protocol.(1) The preexchange phase includes the following:mes1:TTP
→
C
:
Cert
CT;
mes2:CB
→
C
:
P
_
cert.(2) The exchange phase includes the following:mes3:C
→
M
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
_
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
);
mes4:M
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes5:C
→
M
:
S
K
CT.(3) The dispute settlement phase includes the following:mes6:M
→
TTP
:
Desc
∥
{
P
∥
Desc
}
P
K
CT
∥
P
cert
∥
Cert
CT
∥
Sig
C
(
P
∥
Desc
)
∥
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes7:TTP
→
C
:
{
D
}
P
K
CT
∥
Sig
M
(
D
);
mes8:TTP
→
M
:
S
K
CT.Based on the unfair reasons above, we improve message 3 and message 6. TTP will determineDesc
C
=
Desc
M
∧
D
M
=
Desc
M
(
P
) first, when they receive a request message from M. If the formula is true, TTP sends S
K
CT to M and D
M to C.By verifying the fairness of the modified protocol continuously, we then establish abnormal-terminated strands ofM and C, respectively, and judge each of them. The concreted analysis process of improved protocol will not be described here. Figure 5 is the model description of the modified protocol in the same situation. From it, we can know that M has to send their evidence D in order to obtain P, because the TTP has more discrimination capability.Figure 5
Analysis of the modified protocol.The verification steps are the same as mentioned above, so we did not propose the detailed description here.


## 5.3. Analysis of Experimental Results

By using EMH protocol to test the fair authentication method proposed in this paper, we draw some conclusions: first, the method can verify the fairness of E-commerce protocols effectively and give an accurate judgment about the fair exchange of evidences and the fair evidences in exchange; second, the method generates a finite number of abnormal-terminated strands and builds the trader model explicitly by inductive reasoning, which enables the verification process to be terminated; in addition, it has a practical value in design and improvement of E-commerce protocols.


## 6. Conclusion

This paper proposes a formal definition of fairness as well as a new method to verify the fairness of E-commerce protocols. The trader model we build here differs from the Dolev-Yao penetrator model. Because it is established according to the E-commerce trading behaviors, it can be better to reflect the behaviors of entities in E-commerce protocols. The evidence-corresponding-relations defined by a bijective function can describe the equivalent relations of traders’ evidences and give a method to determine whether someone has forged evidences in transaction. The formal definition of fairness is defined from the perspective of traders, which helps to reconcile with model assumptions of traders. We use a regular strand to model the third party and trader abnormal-terminated strands, propose the trader model to detect whether a participant can obtain regular entities’ evidences, and thus complete the fairness validation. This method avoids the verification of nonrepudiation, and can verify fairness of E-commerce protocols including third-parties. Besides, it neither needs to track all statuses of protocol execution nor traverses all strands of traders. The current work is limited to manual derivation, and we will strive to the automatic verification in future.



---

*Source: 138370-2014-06-01.xml*