Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 11 / Issue 1 / Abstract

available in:   PDF (137 kB) PS (118 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-011-01-0175

RSA-based Certified Delivery of E-Goods Using Verifiable and Recoverable Signature Encryption1

Aleksandra Nenadic, Ning Zhang, Barry Cheetham, Carole Goble
School of Computer Science, University of Manchester,
Oxford Road, M13 9PL, UK
{anenadic, nzhang, barry, carole}@cs.man.ac.uk

Abstract: Delivering electronic goods over the Internet is one of the e-commerce applications that will proliferate in the coming years. Certified e-goods delivery is a process where valuable e-goods are exchanged for an acknowledgement of their reception. This paper proposes an efficient security protocol for certified e-goods delivery with the following features: (1) it ensures strong fairness for the exchange of e-goods and proof of reception, (2) it ensures non-repudiation of origin and non-repudiation of receipt for the delivered e-goods, (3) it allows the receiver of e-goods to verify, during the exchange process, that the e-goods to be received are the one he is signing the receipt for, (4) it uses an off-line and transparent semi-trusted third party (STTP) only in cases when disputes arise, (5) it provides the confidentiality protection for the exchanged items from the STTP, and (6) achieves these features with less computational and communicational overheads than related protocols.

Keywords: certified delivery, non-repudiation, fair exchange, security protocols

Category: C.2.2 [Computer-Communication Networks]: Network Protocols, D.4.6 [Software]: Security and Protection, K.6.5 [Management of Computing and Information Systems]: Security and Protection.

1 Introduction

E-goods refer to commercial products that can be represented in electronic form and transmitted over the Internet. Examples of such e-goods are video/audio content, software, e-newspapers, e-magazines, etc. E-goods delivery over the Internet is a business process where a piece of e-goods from a merchant is exchanged for its e-payment or an acknowledgement of its receipt (should a conventional payment method such as credit cards be used) from a customer. There are other items of value that, strictly speaking, cannot be considered as commercial products, such as payments, invoices, financial reports, utility bills, but can also be represented in the electronic form and should enjoy the certified delivery as well. Therefore, throughout the paper, by e-goods we consider any e-item of value.

1This paper is an extended version of the paper "An RSA-based Security Protocol for Certified E-goods Delivery", Proc. IEEE International Conference on Information Technology ITCC 2004, Las Vegas, NV, USA, IEEE Computer Society (2004), 22-28.

Page 175

Industry analysts have predicted that the process of goods being delivered in electronic form will explode in the coming years due to advantages such as low cost and high product penetration that the Internet brings [InfoWorld 2002]. E-goods delivery is particularly beneficial to certain business sectors such as software development, publishing, financial services and entertainment industry. Software, for example, has been sold for years in shops in the form of CDs. Converting to a digital method of distribution will not only save time and money, but also expedite the process of software updates and bug fixes. Electronic versions of newspapers can be bought and sold over the Internet unless they are available on the Web for free. On-line invoicing can cut printing, shipping and postage costs, reduce billing errors, and, consequently, companies can reach out to more customers. Licensed retailers can distribute entertainment e-goods, such as music or films, instead of mailing them to customers or selling them in shops.

E-goods delivery involves several security concerns. In addition to authenticity and integrity assurance of the contents of e-goods and their confidentiality protection while in transit, there is another security service that is important in this context and that is certified e-goods delivery. This security service ensures that e-goods is delivered to its intended recipient if and only if the sender can obtain a receipt proving that the recipient has indeed received the e-goods. The receipt is normally a digital signature signed by the recipient on the received e-goods, and the sender can use this receipt as a proof of delivery, should any dispute arise (for example, if the recipient falsely claims that the e-goods have never arrived). The sender typically also attaches his signature on the e-goods and transmits it together with the e-goods to ensure the receiver of the authenticity and origin of the e-goods.

Certified e-goods delivery requires two important security properties: fairness and content/quality assurance. Fairness guarantees that a recipient will receive the e-goods together with a proof of its origin from the sender if and only if the sender receives a non-repudiable proof of the reception from the recipient. Content/quality assurance ensures that the received e-goods indeed match the expected description/quality.

Achieving fairness over the Internet can prove to be a problem since the Internet, as a serial communication network, cannot support simultaneous message exchange. Back in 1980, Even and Yacobi [Even and Yacobi 1980] showed that there is no deterministic protocol by which two parties can fairly exchange their items over the Internet (see also [Pagnia and Gärter 1999]). Business partners established through the Internet may not have previous business relationships and there is a potential lack of mutual trust. For this reason, neither of the parties involved in an exchange is willing to release his item first and thereby get into a disadvantageous position. Therefore, specialised security protocols are needed to ensure fairness - either all the parties get their expected items or none of them gets anything useful.

The problem of content/quality assurance is even subtler. Parties may engage in a certified delivery process to fairly exchange an e-goods item for a receipt. However, without the content/quality assurance, the receiver may discover at the end of an exchange process that the received e-goods are not of the promised or expected quality. For example, a customer has paid for a piece of software (or a high-quality film), but the software he has received does not have the full set of features as promised (or the film copy is of low quality).

Page 176

The objective of this paper is to present an efficient Certified E-Good Delivery (RSA-CEGD) protocol to support a fair exchange of e-goods for an RSA-based receipt. The protocol is designed based upon a novel scheme enabling verification and recovery of encrypted signatures (VRES) and joint e-goods and key certification. The protocol achieves both fairness and content/quality assurance.

The VRES scheme represents an encryption of an RSA signature such that its recipient can verify the correctness of the signature without obtaining the signature itself. If the verification is positive, the recipient is guaranteed that an agreed STTP can recover the original signature from the VRES, should any dispute arise. In this way, the STTP can stay off-line, i.e. the parties can execute the exchange protocol without any involvement of the STTP. If the parties cannot reach a fair completion of the exchange themselves, the recovery service offered by the STTP is invoked and the dispute is resolved electronically. If the STTP has no on-line presence, the parties can submit the transaction evidence, for example using CDs, and the dispute can be resolved using a conventional method such as snail post and a court of law. In addition, the involvement of the STTP in the signature recovery process is transparent - the signature recovered by the STTP is indistinguishable from that generated by the original signer. Both the signature and the e-goods enjoy confidentiality protection against unauthorized access by any third party, including the STTP.

The joint e-goods and key certification concept is used in the protocol design to allow the recipient of e-goods to verify the correctness of the encrypted e-goods and its decryption key during a protocol execution. In this way, content/quality assurance of the e-goods can be achieved guaranteeing the recipient that the e-goods obtained after decryption at the end of the exchange will indeed match with what is expected. The linkage between the original e-goods, e-goods' encryption and the corresponding encryption/decryption key is validated and certified by a certification authority (CA) prior to the exchange. Although the concept of digital content validation/certification is not entirely new in the Internet arena [see Microsoft Authenticode] and has been utilised in fair e-purchase protocols [Franklin and Reiter 1997, Ray and Ray 2000] and fair document exchange protocols [Shi et al. 2003, Zhang et al. 2000], this paper is the first, to our best knowledge, to have incorporated the concept of joint e-goods and key certification to achieve certified e-goods delivery.

The rest of the paper is organised as follows. [Section 2] critically analyses recent work on fair exchange and certified delivery. [Section 3] gives the assumptions on which our protocol is designed and the security requirements it aims to satisfy. [Section 4] presents the VRES scheme, before the detailed description of the protocol is given in [Section 5]. The analysis and evaluation of the protocol, and comparison with related work are provided in [Section 6] and [Section 7], respectively. Finally, [Section 8] outlines our conclusions.

2 Background

Over the past few years, researchers have been working on the design of fair non-repudiation protocols for achieving certified delivery [Asokan et al. 1998, Ateniese and Nita-Rotaru 2002, Ateniese 2004, Deng 1996, Ferrer-Gomila et al. 2000, Kremer and Markowitch 2001, Markowitch and Roggeman 1999, Markowitch and Saeednia 2001, Schneier and Riordan 1998, Zhang and Shi 1996, Zhou et al. 1999, Zhou et al. 2000, etc.].

Page 177

These works have mainly been focused on certified delivery of e-mails, for which certification of contents is not so much an issue. With certified e-mail delivery, the emphasis is on the generation of a piece of evidence that can prove the receipt of a specific e-mail by the recipient, and whether or not the content of the e-mail matches with the recipient's expectation is not important. For certified e-goods delivery, on the other hand, a signed receipt should guarantee not only the reception, but also the content/quality of the e-goods delivered. A mismatch between the expected and actual contents of the e-goods may have financial implications to the recipient and should be detected before the exchange process is over.

Certified delivery protocols most relevant to ours are those designed by [Asokan et al. 2000, Ateniese and Nita-Rotaru 2001, Ateniese 2004, Markowitch and Saeednia 2001, Nenadic et al. 2004]. These protocols are all based on the concept of verifiable and recoverable signature encryption and make the use of an off-line and transparent TTP for signature recovery. However, the verifiable and recoverable signature encryption schemes proposed in [Ateniese and Nita-Rotaru 2002, Asokan et al. 2000] are interactive, i.e. the verification of an encrypted signature is performed using a zero-knowledge (ZK) protocol that requires several srounds of on-line interactions between the sender and the recipient, which makes the solution computationally expensive. On the contrary, our protocol employs a non-interactive VRES scheme by which the verification can be performed efficiently off-line without any on-line interactions between the two exchanging parties.

The protocols by [Ateniese and Nita-Rotaru 2002, Markowitch and Saeednia 2001] do not protect the confidentiality of the exchanged items from the TTP. In addition, they impose higher security and storage requirements on the TTP. These protocols, unlike the protocol proposed in this paper, require the third party to be fully trustworthy. The e-goods delivery protocol by [Markowitch and Saeednia 2001] requires the TTP to verify the contents of the e-goods during protocol execution allowing the disclosure of the e-goods' contents to the TTP. In addition, sometimes it may be difficult for a third party to automatically validate the content, quality or features of the e-goods, as the TTP may not be specialized to do this. Therefore, there may be limitations in the practical application of this solution. In our protocol, a specialised CA (which may be different from the STTP) performs the e-goods validation prior to an exchange and issues a special certificate for the encrypted e-goods as well as its decryption key. The only task expected from the STTP is to recover an encrypted signature to ensure fairness, should a dispute arise.

3 Preliminaries

This section outlines notation used in the protocol description and the assumptions used in the protocol design. It also summarizes the security requirements the protocol is designed to satisfy.

3.1 Notation and Assumptions

The following notation has been used in the remaining part of the paper.

Page 178

  • h(x) denotes a strong-collision-resistant one-way hash function, such as MD5 [Rivest 1992].
  • Ek(x) is used to express the ciphertext of a data item x encrypted with a key k. Ek(x) is computed using a symmetric cryptosystem if the corresponding decryption key is the same as k, or RSA public-key cryptosystem [Rivest et al. 1978] otherwise.
  • pk = (e, n) and sk = (d, n) denote RSA public and private key, respectively, where n is a public RSA modulus, and e and d are public and private key exponents.
  • Epk(x) = xe mod n = c is used to express RSA encryption of a data item x using public key pk = (e, n), and Esk (c) = cd mod n = x is used to express RSA decryption of ciphertext c using private key sk = (d, n).
  • Sign(x) = Esk (h(x)) = (h(x))d mod n denotes RSA signature on a data item x generated with private key sk = (d, n).
  • Notation (x, y) denotes the concatenation of data items x and y.

Party Pa has valuable e-goods, denoted as Da and a symmetric key ka for the encryption and decryption of Da. Pa is to send Da to party Pb in exchange for party Pb's receipt for Da. They have agreed to employ an off-line STTP Pt to help them with the exchange process if they cannot reach a fair completion themselves. It is assumed that Pt may misbehave on its own, e.g. trying to access the e-goods or receipt unfairly, but Pt does not conspire with either of Pa and Pb.

A CA has certified the content of the e-goods Da and has issued certificate CertDa to Pa. This certificate is defined as follows:

    CertDa = (desca, hea, hda, hka, signCA), where
    desca is the content summary of Da,
    hea = h((Da)) is the hash value of the encryption of Da with the key ka,
    hda = h(Da) is the hash value of Da,
    hka = h(ka) is the hash value of the key ka, and
    signCA is the CA's signature on the items (desca, hda, hda, hka).

Certificate CertDa links the encrypted Da, Da's description desca and the decryption key ka. The CA's signature signCA represents its guarantee that if the encrypted e-goods (Da) and the key ka meet the conditions h((Da)) = hea and h(ka) = hka, then decrypting (Da) using the key ka will recover Da with its contents matching the description in desca. A single certificate CertDa for e-goods Da can be used by party Pa for multiple exchanges.

The e-goods certification allows Pb to verify the correctness of the encrypted e-goods and the decryption key during an exchange. Without this certification, Pb cannot get content/quality assurance, as nothing would stop a dishonest Pa from using a worthless data in exchange for Pb's receipt, and this dishonesty could not be detected until the exchange is over. The CA can be a trusted independent entity or an entity closely associated to the product chain, e.g. the producer of the e-goods.

Page 179

To illustrate this, consider an example of on-line film purchase. Let Da represent a film produced and certified by a film producer and Pa an on-line merchant contracted by the producer to sell the film over the Internet. The film producer plays the role of the CA and issues the certificate CertDa to Pa, who can then sell it as many times as he can. A customer Pb, who represents a major cinema chain, is to purchase the film over the Internet. The customer and the merchant negotiate the deal and then fairly exchange the film for the receipt. The receipt proves that the customer has received the film. The certificate from the producer guarantees that the film is indeed an original copy that meets the description desca.

It is assumed that each party Pi (i {a, b, t}) has an RSA public and private key pair, expressed as pki = (ei, ni) and ski = (di, ni). Public key pki (i {a, b, t}) had been certified by a recognised certification authority and is known by all the other parties. Party Pb's receipt for Da, denoted as recb, is represented by Pb's RSA signature on Da. That is,

recb = mod nb.

Party Pb has an additional certificate Cbt for his special RSA public key pkbt = (ebt, nbt), issued by Pt prior to the exchange. nbt is public RSA modulus chosen by Pt and ebt is required to be the same as eb in Pb's public key pkb, i.e. eb = ebt. The private key corresponding to pkbt is denoted as skbt = (dbt, nbt) and is shared by Pb and Pt. Certificate Cbt is defined as:

    Cbt = (pkbt, wbt, sbt), where
    wbt = (h(skt, pkbt)-1 x dbt) mod nbt, and skt is Pt's own private key, and
    sbt is Pt's RSA signature on the items (pkbt, wbt).

Figure 1: An example implementation of Pb's special public key certificate Cbt

By including wbt in the certificate Pt has no need to store or safe-keep the shared private key skbt, as it can be computed from wbt as dbt = (h(skt, pkbt) x wbt) mod nbt. Certificate Cbt can be issued when party Pb registers with Pt initially, and can be reused by Pb for multiple exchanges.

Page 180

The key pair (pkbt, skbt) will be used in the design of the VRES scheme that is to be described in [Section 4] next. Certificate Cbt can be implemented using standard X.509 Version 3 certificate [X.509], which allows the use of extension field for e.g. wbt, as shown in [Fig. 1].

Party Pa initiates the RSA-CEGD protocol. Communication channels to/from Pt are resilient, i.e. all messages inserted into such channels will eventually reach the intended recipients. No reliability assumptions are made about the channel between Pa and Pb. In other words, the channel may be unreliable and messages may be lost. Channels between all the parties are authenticated and confidential.

An overview of the RSA-CEGD protocol is as follows. The e-goods Da is first encrypted with the symmetric key ka and the CA certifies the content/quality of Da together with the key ka by issuing certificate CertDa. The sender Pa transmits the encrypted e-goods and certificate CertDa to the recipient Pb. Upon verifying these items, Pb responds by sending his VRES containing his encrypted RSA signature (i.e. his receipt). If Pa is satisfied with the outcome of the VRES verification, it is secure for Pa to release the e-goods first by letting Pb have the decryption key ka. If satisfied with the key received, Pb sends Pa an item needed for decrypting the VRES so Pa can obtain the receipt inside. Should this item fail to arrive, e.g. due to Pb's misbehaviour or a network failure, Pa may initiate the recovery process with the STTP Pt. Pt recovers this item for Pa from Pb's VRES using the shared private key skbt, thereby achieving the fair completion of the exchange.

3.2 Security Requirements

Before formally describing the RSA-CEGD protocol, its security requirements are first specified as follows:

(S1) Non-repudiation of origin - Pb is provided with a proof that Pa is indeed the originator of the e-goods.

(S2) Non-repudiation of receipt - Pa is provided with a proof that Pb has indeed received the e-goods.

(S3) Strong fairness - Pb has obtained Pa's e-goods or can obtain it with the assistance of Pt if and only if Pa has obtained Pb's receipt or can obtain it with the assistance of Pt.

(S4) E-goods content/quality assurance - Pb can verify, during the protocol execution, that the e-goods to be received are the same one he is signing the receipt for.

(S5) E-goods and receipt confidentiality - the e-goods to be delivered and the corresponding receipt are not disclosed to any external party, including Pt.

(S6) Transparency of the STTP - the participation of Pt in the protocol is transparent, i.e. the signature recovered by Pt is indistinguishable from the one sent by Pb.

4 Verifiable and Recoverable Encrypted Signature (VRES)

In this section we describe the generation, verification and recovery of the VRES. As previously explained, the VRES represents an encryption of an RSA signature that allows its recipient to verify the correctness of the signature inside without having the plaintext signature, and is recoverable by a designated third party. The VRES scheme is designed based on the following theorem (for the proof the reader is referred to [Ray and Ray 2000]).

Page 181

Theorem of cross-decryption. Let n1 and n2 be relatively prime moduli of two RSA cryptosystems, and e1 = e2 = e the corresponding public-key exponents. For any two messages m and m', such that m < min (n1, n2) and m' < min (n1, n2), the following holds:

    (me mod (n1 x n2)) mod n1 = (m')e mod n1 if and only if m = m',
    (me mod (n1 x n2)) mod n2 = (m')e mod n2 if and only if m = m'.

This theorem states that, for two RSA cryptosystems with the same public exponents (e1 = e2 = e), either of the private exponents d1 or d2 can be used to decrypt the number me mod (n1 x n2) to obtain m.

4.1 VRES Generation

To generate verifiable and recoverable encryption of his signature recb, denoted as (yb, xb, xxb), party Pb chooses a random prime number 0 < rb < nb and computes:

Here, eb and dbt are public and private exponents of Pb's public key pkb and private key skbt, respectively, yb is a slightly modified RSA encryption of random number rb, xb represents the "encryption" of signature recb with random number rb, and (h(yb)) is RSA encryption of h(yb) with the key skbt. Note that according to the theorem of cross-decryption we have:

. Similarly,
yb mod nbt =.

So, the number rb can be recovered from yb using either of the private keys skb or skbt.

4.2 VRES Verification

In order to verify Pb's VRES (yb, xb, xxb), Pa does the following:

(a) Checks the correctness of Pt's signature sbt in certificate Cbt.
(b) Confirms that mod nb] = (yb ( h(Da)) mod nb.
(c) Confirms that mod nbt] = (yb x h(yb)) mod nbt.

In detail, verification (a) makes sure that Cbt is a valid certificate issued by Pt. This guarantees the correctness of Pb's public key pkbt and that Pt can recover private key skbt related to the public key pkbt in Cbt. Verification (b) confirms that item xb contains Pb's correct signature recb on e-goods Da. Verification (c) together with (b) ensures that the same number rb is used in the computations of yb, xb and xxb, and the modulus operation in yb is based on nb x nbt, so that Pt can decrypt yb with key skbt to obtain rb for the recovery of Pb's signature recb from xb.

Page 182

4.3 VRES Recovery

To recover recb from the VRES (yb, xb, xxb), Pt first derives the private key skbt from certificate Cbt using its private key skt (as described in [Section 3.1]). Pt then uses the derived skbt to decrypt yb mod nbt = to recover rb. Number rb can then be used to compute Pb's signature from xb. That is:

recb = (rb-1 x  xb) mod nb.

5 The RSA-CEGD Protocol

In this section we formally present the protocol designed based on the VRES scheme described in [Section 4]. The protocol comprises 2 sub-protocols: the exchange sub-protocol and the recovery sub-protocol. Parties Pa and Pb execute the exchange sub-protocol in an attempt to exchange the items fairly without any involvement of Pt. If this attempt is not successful, the recovery sub-protocol is invoked during which Pt recovers the disputed signature. Definitions of all the items used in the protocol are given in [Tab. 1].

ka: symmetric key for encryption/decryption of e-goods Da generated by Pa;
CertDa = (desca, hea, hda, hka, signCA): certificate for Da issued by the CA, where
hea = h((Da)) is the hash value of the encryption of Da with the key ka,
hda = h(Da) is the hash value of Da,
hka = h(ka) is the hash value of the key ka;
(hda): Pa's RSA signature on Da serving as a proof of origin of Da;
recb = mod nb: Pb's receipt for Pa's e-goods Da, i.e. Pb's RSA signature on Da;
rb: random prime generated by Pb for the generation of the VRES (yb, xb, xxb);
(yb, xb, xxb): Pb's VRES, where
yb = mod (nbxnbt) encryption of rb with Pb's public key pkb, also recoverable by Pt,
xb = (rb x mod nb = (rb x recb) mod nb is encryption of recb with rb,
xxb = (rb x (h(yb))) mod nbt is a control number that confirms the correct use of rb;
Cbt: Pb's RSA public-key certificate issued by Pt,
pkbt = (ebt, nbt), skbt = (dbt, nbt): public and private RSA keys related to Cbt with ebt = eb;
sb = (h(Cbt, yb, hka, Pa)): Pb's recovery authorisation token;

Table 1: Definitions of the protocol's items

Page 183

5.1 The Exchange Sub-Protocol

The exchange sub-protocol comprises steps (E1)-(E4), as shown in [Fig. 2], and is executed as follows.

Figure 2: The exchange sub-protocol

Pa initiates the exchange by transmitting the encrypted e-goods Ek(Da), the e-goods' certificate CertDa and Pa's signature (hda) on Da to Pb. The signature will serve as a non-repudiable proof of origin of Da.

Pa -> Pb: (Da), CertDa, (hda)

Pb verifies the correctness of CertDa and (Da). Pb also verifies Pa's signature (hda) by decrypting it with Pa's public key pka to obtain a hash value hda' and comparing it with the hash value hda contained in certificate CertDa. If the two hash values do not match, Pb may ask Pa to re-send message (E1) or terminate the protocol execution. Otherwise, Pb generates the VRES for his signature recb, i.e. (yb, xb, xxb). Pb also produces a recovery authorisation token sb that is defined as Pb's RSA signature on the items (Cbt, yb, hka, Pa). The authorization token sb authorises Pa to invoke the recovery process with Pt under certain conditions (controlled by Pb). Actually, sb states that "Pt can recover rb for Pa from yb, if and only if Pa provides Pt with a key ka, such that h(ka) = hka". Pb then transfers the items, xb, xxb, yb, sb, Cbt, to Pa.

Pb -> Pa: xb, xxb, yb, sb, Cbt

(E3): Pa verifies the correctness of Pb's VRES (yb, xb, xxb) as explained in [Section 4.2], and the correctness of Pb's recovery authorisation token sb by verifying Pb's signature in sb. If both of these verifications are positive, Pa sends the key ka to Pb.

Pa -> Pb: ka

Otherwise, Pa may ask Pb to re-send message (E2) or abort the protocol run.

Pb verifies the correctness of the received key ka by confirming that h(ka) = hka. If this verification fails, Pb may ask Pa to re-send message (E3) or abort the protocol run.

Pb -> Pa: rb

Page 184

Otherwise, Pb uses ka to decrypt (Da) to obtain Da, and sends the random number rb to Pa.

Having received rb from Pb, Pa uses rb to compute the signature recb from xb as recb = (rb-1 ( xb) mod nb and verifies its correctness by confirming that (recb) = hda. If this verification is positive, the exchange process is completed successfully. If this verification is negative or Pa fails to receive rb from Pb, Pa may initiate the recovery sub-protocol with Pt.

5.2 The Recovery Sub-Protocol

The recovery sub-protocol comprises steps (R1)-(R3), as shown in [Fig. 3], and is executed as follows.

Figure 3: The recovery sub-protocol

(R1): Pa transfers the items Cbt, yb, sb and ka to Pt to request the receipt (i.e. signature) recovery.

Pa -> Pt: Cbt, yb, sb, ka

(R2): Pt verifies the correctness of Pa's recovery request by verifying Pb's authorisation token sb to ensure that Pa has presented the correct key ka. If this verification fails, Pt rejects Pa's request. Otherwise, Pt recovers rb from yb and sends it to Pa.

Pt -> Pa: rb

(R3): Pt also forwards the key ka to Pb.

Pt -> Pb: ka

6 Security Analysis

In this section, we analyse the security of the cryptographic building blocks used in the protocol design, discuss possible ways in which the protocol can be attacked and justify that the protocol satisfies the requirements specified in [Section 3.2].

6.1 VRES Security

The security of the protocol is dependent on the security of the cryptographic primitive, namely, Pb's VRES (yb, xb, xxb). The security of the VRES can be analysed in relation to two issues.

Page 185

Firstly, is it sufficiently difficult to convert the VRES into the original signature recb without knowing random number rb, and, secondly, is it sufficiently difficult for Pb to forge his VRES and trick Pa into accepting it?

yb (= mod (nb x nbt)) represents a minor variation of an RSA encryption, so it is hard for any other party Po {Pb, Pt}) to decrypt yb to obtain rb without knowing private key skb or skbt. In order to obtain recb from xb (= (rb ( recb) mod nb), party Po ( {Pb}) has to guess the random number rb or to factor xb, which is considered computationally difficult provided that rb and nb are sufficiently large. With the current state-of-the-art in factoring algorithms [Stern 2001], rb and nb should be at least 1024 bits each. Similar discussion can be applied to xxb (= rb x mod nbt). Therefore, it is difficult for Po to illegitimately obtain recb from the VRES.

In an attempt to cheat Pa, Pb may send a forged VRES (yb', xb', xxb') to trick Pa to release the e-goods Da. For example, Pb may try to generate a false signature recb' ? recb on a different Da' and then use it to generate the VRES (yb', xb', xxb'), i.e.

    yb' = mod (nb x nbt),
    xb' = (rb' x mod nb,
    xxb'= (rb' x mod nbt.

For the forgery to be successful the VRES (yb', xb', xxb') must pass the VRES verification, which means that the following must hold:

    mod nb = (yb' x h(Da)) mod nb,
    mod nbt = (yb' x h(yb')) mod nbt.

This can, however, be truth if and only if h(Da) = h(Da'). As long as h(x) is a strong collision-resistant hash function, this cheating is unlikely to succeed.

6.2 Attack Analysis

Cheating by party Pa. Pa may attempt to cheat Pb by sending an incorrect e-goods encryption (Da) or an incorrect certificate CertDa in step (E1). However, Pb can detect these deception attempts through certificate verification, and, consequently, Pb may terminate the protocol after step (E1). Therefore Pa gains no benefit from this misbehaviour.

Pa may attempt to send an incorrect key ka to Pb in step (E3). This deception can easily be detected by comparing the computed hash value of the key received and the one contained in the certificate CertDa, so Pa cannot gain any advantage over Pb.

Pa may also attempt to cheat by requesting Pt to recover Pb's signature prior to step (E3), or by sending an incorrect ka to Pt in step (R1). In both cases, for Pt to recover rb, Pa must provide the correct key ka (i.e. the one that can pass verification performed by Pt). If the key ka cannot pass this verification, Pt will reject Pa's request. Once the request is accepted, Pt recovers Pb's rb for Pa, but also forwards Pa's ka to Pb. Therefore, Pa cannot gain any advantage over Pb, as the correct key ka will ultimately reach Pb through Pt.

Cheating by party Pb. Pb may attempt to cheat Pa by using different random numbers instead of a single number rb or an incorrect signature recb' to generate the VRES (yb, xb, xxb).

Page 186

As previously discussed, the VRES verification (b) will fail if an incorrect signature is used to produce xb, and verification (c) or (b) will fail if different numbers are used to generate the VRES. Consequently, Pa may terminate the exchange process after step (E2), so Pb gains no benefit from this misbehaviour.

Pb may also attempt to cheat Pa by refusing to send rb or sending an incorrect rb in step (E4). Pb cannot benefit from this misbehaviour because, by step (E4), Pa must have already received Pb's correct VRES that guarantees the recovery of rb, and consequently recb, by Pt.

Cheating by party Pt. Pt may attempt to obtain the signature recb or e-goods Da during the recovery process. Without colluding with either Pa or Pb, it is difficult for Pt to be successful in these attacks. Pt only deals with yb and the random number rb, which are not sufficient for the disclosure of the signature recb. Also, e-goods Da is not sent to Pt during the recovery process. Therefore, Pt cannot obtain any information about the exchanged items.

6.3 Satisfaction of Security Requirements

Non-repudiation and fairness. Suppose that Pb has obtained Pa's Da, i.e. Pb has received the key ka for the decryption of (Da) in step (E3) or in step (R3). In this case, Pa has certainly got the correct items from Pb in step (E2). Consequently, Pa can obtain rb from Pb in step (E4), or from Pt in step (R2). After obtaining rb, Pa can use it to derive Pb's receipt from xb.

Similarly, suppose that Pa has obtained recb, i.e. Pa has received the correct items from Pb in step (E2), and rb in step (E4) or from Pt in step (R2). This implies that Pb has received the correct key ka from Pa in step (E3) or from Pt in step (R3). Therefore, at the end of a protocol execution, either party Pb will receive Da and party Pa will receive recb, or neither of them will receive anything useful. Party Pa must also provide the correct signature on Da in step (E1), as a proof of origin of Da. Therefore the protocol meets the non-repudiation of origin (S1), non-repudiation of receipt (S2), and the strong fairness (S3) requirements.

E-goods content/quality assurance: Based on the certificate CertDa issued by a CA, party Pb can verify the correctness of the decryption key ka during the protocol execution, and he trusts the CA to perform the certification correctly. In this way, Pb is assured that the e-goods Da, to be obtained at the end of the protocol execution (by decryption with the key ka) will indeed match with the description given in CertDa (S4).

E-goods and receipt confidentiality: During the recovery process Pt deals only with the random number rb and key ka, while e-goods Da, recb, and the numbeer xb (which can be used to derive recb) are not disclosed to Pt. Thus, the privacy of the exchanged e-goods and the corresponding receipt is preserved (S5).

Transparency of the STTP: It is evident that the structure of the receipt received from Pb in the exchange protocol is identical to that recovered by Pt during the recovery protocol, i.e. the received receipt does not reveal whether or not Pt has been involved in the exchange process (S6).

Page 187

7 Comparisons and Performance Evaluation

In this section, we compare our RSA-CEGD protocol with the related proposals seen in literature. To the best of authors' knowledge, this paper presents the first protocol for certified e-goods delivery with an embedded e-goods content/quality assurance. As off-line TTP-based certified delivery protocols are the most related to ours, so we focus our comparison to this class of protocols. For a more extensive survey of fair non-repudiation protocols see [Kremer et al. 2002].

In certified e-mail protocols [Asokan et al. 1998, Ferrer-Gomila et al. 2000, Kremer and Markowitch 2001, Zhou et al. 1999, Zhou et al. 2000], a proof of receipt is represented by a token consisted of several items, i.e. it is not a standard signature on the e-mail. In addition, in these protocols, a signature recovered by the TTP is structurally different from the one produced by the original signer. This means that the third party in these protocols is not transparent and that these receipts always have to be interpreted in the context of the protocol that has generated it. In contrast to this, receipts received in the RSA-CEGD protocol are standard RSA-based signatures, and the STTP's participation is transparent.

The RSA-CEGD protocol is designed in such a way that only the sender is actively involved in the receipt recovery, while the recipient only takes a passive role in the process. This reduces communication load on the recipient and safeguards him from potential denial-of-service attacks from malicious senders. Protocols [Asokan et al. 1998, Ferrer-Gomila et al. 2000, Kremer and Markowitch 2001, Markowitch and Saeednia 2001, Zhou et al. 1999, Zhou et al. 2000] require both the sender and the recipient to actively participate in dispute resolution, and, in order to prematurely terminate the normal exchange protocol they have to contact the third party and execute an abort protocol. In other words, these protocols comprise 3 or 4 sub-protocols, which increases the communication overheads.

Verifiable and recoverable signature encryptions have been so far mainly utilised in fair signature exchange protocols [see Asokan et al. 2000, Ateniese 1999, Bao et al. 1998, Chen 1998], and have only recently been applied in certified delivery. Here, we compare the RSA-CEGD protocol with certified delivery protocols based on VRES-like schemes, namely, the Ateniese and Nita-Rotaru's protocol [Ateniese and Nita-Rotaru 2002], denoted as A-NR (for an extended version see [Ateniese 2004]), the Markowitch and Saeednia's protocol [Markowitch and Saeednia 2001], denoted as M-S, and the Nenadic et al.'s protocols [Nenadic et al. 2004], denoted as N-Z-B. The comparisons are performed in terms of the computational costs incurred for the generation, verification and recovery of the respective VRES schemes and for the protocol executions, and the results are shown in [Tab. 2]. Computational costs refer to the number of modular exponentiations used, as they are the most expensive computations.

A-NR is a certified e-mail delivery protocol where no quality/content assurance is required, whereas RSA-CEGD protocol is designed for certified e-goods delivery and therefore needs to meet this additional security requirement. A-NR employs an interactive verifiable and recoverable signature encryption scheme based on RSA signatures, which is less efficient than our non-interactive VRES scheme. Both RSA-CEGD and A-NR protocols have an initialisation stage for parties Pb and Pt to agree on a shared secret that is subsequently used in the verifiable and recoverable encrypted signature schemes.

Page 188

However, in A-NR, the third party is required to store and safe-keep this secret, whereas in our protocol it can be computed from Pb's certificate Cbt and the third party need not store anything. Therefore, the security and storage requirements placed on the third party in RSA-CEGD are reduced. In addition, no confidentiality protection is provided for the e-mail and the receipt in A-NR, as they have to be disclosed to the third party to allow correct recovery.

M-S is a certified e-goods delivery protocol with a non-interactive verifiable and recoverable signature encryption scheme based on Girault-Poupard-Stern signatures [Girault 1991, Poupard and Stern 1998]. However, these signatures are not very often used in practise. Also, during the recovery process in M-S, the third party has to verify the contents of the e-goods, but the authors do not fully clarify how this verification is performed, which would additionally increase the computational cost for this protocol. In RSA-CEGD protocol, this is done by joint e-goods and key certification though certificate CertDa. RSA-CEGD protocol also satisfies the confidentiality requirement for the exchanged items, whereas M-S does not.

The N-Z-B protocol uses the same VRES scheme as the RSA-CEGD protocol. However, the former is slightly more efficient than RSA-CEGD, as no e-goods certification and verification is necessary for certified e-email delivery applications that are aimed at by N-Z-B.

Table 2: Comparison of computational costs

8 Conclusions

This paper has presented a fair non-repudiation protocol for achieving certified e-goods delivery in e-commerce. The protocol is based on two important concepts - the VRES scheme, which enables the protocol to achieve strong fairness, and the joint e-goods and key certification, which prevents a dishonest party from using some junk data in exchange for a receipt. The e-goods and the receipt exchanged enjoy the confidentiality protection against any third party including the STTP. The protocol places weak security requirements on the STTP, which simplifies its implementation and management.

Page 189

Our protocol has been compared against related work in the field and we have demonstrated that it achieves more security properties that related protocols and with less computational costs. Our future work will include the formal verification and prototyping of the protocol presented.


The work presented in this paper is part of the FIDES project (LINK, GR/R55177/01) funded jointly by the UK Engineering and Physical Sciences Research Council (EPSRC) and the Department of Trade and Industry (DTI).


[Asokan et al. 1998] Asokan, N., Shoup, V., Waidner, M.: "Asynchronous Protocols for Optimistic Fair Exchange", Proc. IEEE Symposium on Security and Privacy, Oakland, CA (1998), 86-100.

[Asokan et al. 2000] Asokan, N., Schunter, M., Waidner, M.: "Optimistic Fair Exchange of Digital Signatures", IEEE Journal on Selected Areas in Communications, 18 (2000), 593-610.

[Ateniese 1999] Ateniese, G.: "Efficient Verifiable Encryption (and Fair Exchange) of Digital Signatures", Proc. ACM Conference on Computer and Communications Security, ACM Press, New York, USA (1999), 138-146.

[Ateniese and Nita-Rotaru 2002] Ateniese, G., Nita-Rotaru, C.: "Stateless-recipient Certified E-mail System Based on Verifiable Encryption", Proc. RSA Conference 2002, LNCS, 2271 (2002), Springer-Verlag, Berlin, Germany, 182-199.

[Ateniese 2004] Ateniese G.: "Verifiable Encryption of Digital Signatures and Applications", ACM Transactions on Information and System Security, 7, 1 (2004), 1-20.

[Bao et al. 1998] Bao, F., Deng, R., Mao, W.: "Efficient and Practical Fair Exchange Protocols with Off-line TTP", Proc. IEEE Symposium on Security and Privacy, Oakland, USA (1998), 77-85.

[Chen 1998] Chen, L.: "Efficient Fair Exchange with Verifiable Confirmation of Signatures", Proc. Advances in Cryptology - ASIACRYPT '98, LNCS, 1514 (1998), Springer-Verlag, Berlin, Germany, 286-299.

[Deng et al. 1996] Deng, R. H., Gong, L., Lazar, A.A., Wang, W.: "Practical Protocols for Certified Electronic Mail", Journal of Network and System Management, 4, 3 (1996), 279-297.

[Even and Yacobi 1980] Even, S., Yacobi Y.: "Relations Among Public-Key Signature Systems", Technical Report 175, Technion, Haifa, Israel (1980).

[Franklin and Reiter 1997] Franklin, M. K., Reiter, M.: "Fair Exchange with a Semi-trusted Third Party" (extended abstract), Proc. ACM Conference on Computer and Communications Security, Zurich, Switzerland (1997), 1-5.

[Ferrer-Gomila et al. 2000][9] Ferrer-Gomila, J. L., Payeras-Capella, M., Huguet i Rotger, L.: "An Efficient Protocol for Certified Electronic Mail", Proc. International Information Security Workshop 2000, LNCS, 1975 (2000), Springer-Verlag, Germany, 237-248.

[Girault 1991] Girault, M.: "Self-certified Public Keys", Proc. of Advances in Cryptology - EUROCRYPT '91, LNCS, 547 (1991), Springer-Verlag, 490-497.

Page 190

[InfoWorld 2002] April, Carolyn A.: "Delivering the goods - digitally", InfoWorld (2002), available on-line at http://www.infoworld.com/article/02/11/08/021111ctdigital_1.html.

[Kremer and Markowitch 2001] Kremer, S. Markowitch, O.: "Selective Receipt in Certified E-mail", Proc. INDOCRYPT 2001, LNCS, 2247 (2001), Springer-Verlag, 136-149.

[Kremer et al. 2002] Kremer, S., Markowitch, O., Zhou, J.: "An Intensive Survey of Fair Non-Repudiation Protocols", Computer Communications, 25, 17 (2002), Elsevier, 1606-1621.

[Markowitch and Roggeman 1999] Markowitch, O., Roggeman, Y.: "Probabilistic Non-repudiation without Trusted Third Party", Proc. Conference on Security in Communication Networks (1999).

[Markowitch and Saeednia 2001] Markowitch, O. Saeednia, S.: "Optimistic Fair Exchange with Transparent Signature Recovery", Proc. International Conference on Financial Cryptography, LNCS, 2339 (2001), Springer-Verlag, 339-350.

[Microsoft Authenticode] Microsoft Authenticode, available at http://msdn.microsoft.com/library/default.asp?url=/workshop/security/authcode/authenticode_node_entry.asp

[Nenadic et al. 2004] Nenadic A., Zhang N., Barton S.: "Fair Certified E-mail Delivery", Proc. ACM Symposium on Applied Computing - SAC 2004, Nicosia, Cyprus (2004), 391-396.

[Pagnia and Gärtner 1999] Pagnia, H., Gärtner, F.: "On the Impossibility of Fair Exchange without a Trusted Third Party", Technical Report TUD-BS-1999-02, University of Darmstadt, Germany (1999).

[Poupard and Stern 1998] Poupard, G., Stern, J.: "Security Analysis of a Practical 'On the Fly' Authentication and Signature Generation", Proc. of Advances in Cryptology - EUROCRYPT '98, LNCS, 1403 (1998), Springer-Verlag, 422-436.

[Ray and Ray 2000] Ray, I., and Ray, I.: "An Optimistic Fair Exchange E-commerce Protocol with Automated Dispute Resolution", Proc. International Conference on E-Commerce and Web Technologies EC-Web 2000, LNCS, 1875 (2000), Springer-Verlag, Berlin, Germany, 84-93.

[Rivest et al. 1978] Rivest, R., Shamir, A., Adleman, L.: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, ACM Press, 21, 2 (1978), 120-126.

[Rivest 1992] Rivest R.: "RFC 1321 - The MD5 Message-Digest Algorithm", MIT Laboratory for Computer Science and RSA Data Security, Inc. (1992), www.faqs.org/rfcs/rfc1321.html.

[Schneier and Riordan 1998] Schneier B., Riordan J.: "A Certified E-Mail Protocol", Proc. Annual Computer Security Applications Conference, ACM Press (1998), 347-352.

[Shi et al. 2003] Shi, Q., Zhang, N., Merabti, M.: "Signature-based Approach to Fair Document Exchange", Communications, IEE Proceedings, 150, 1 (2003), 21-27.

[Stern 2001] Stern, J.: "Evaluation Report on the Factoring Problem", (2001), 1-18.

[X.509] X.509 Certificate Specification, The Internet Engineering Task Force (IETF) - The PKIX Working Group, available at http://www.ietf.org/html.charters/pkix-charter.html.

[Zhang and Shi 1996] Zhang, N., Shi, Q.: "Achieving Non-Repudiation of Receipt", The Computer Journal, 39, 10 (1996), 844-853.

Page 191

[Zhang et al. 2000] Zhang N., Shi Q., Merabti M.: "Anonymous Public-Key Certificates for Anonymous and Fair Document Exchange", Communications, IEE Proceedings, 147, 6 (2000), 345-350.

[Zhou et al. 1999] Zhou J., Deng R., Bao F.: "Evolution of Fair Non-repudiation with TTP", Proc. Australasian Conference on Information Security and Privacy ACISP '99, LNCS, 1587 (1999), Springer-Verlag, Berlin, Germany, 258-269.

[Zhou et al. 2000] Zhou J., Deng R., Bao F.: "Some Remarks on a Fair Exchange Protocol", Proc. International Workshop on Practice and Theory in Public Key Cryptography 2000, LNCS, 1751 (2000), Springer-Verlag, 46-57.

Page 192