Numerical Method for Evaluating E-cash Security

Security evaluations of electronic cash (e-cash) schemes usually produce an abstract result in the form of a logical proof. This paper proposes a new method of security evaluation that produces a quantitative result. The evaluation is done by analyzing the protocol in the scheme using the Markov chain technique. This method calculates the probability of an attack that could be executed perfectly in the scheme’s protocol. As proof of the effectiveness of our evaluation method, we evaluated the security of Chaum’s untraceable electronic cash scheme. The result of our evaluation was compared to the evaluation result from the pi-calculus method. Both methods produced comparable results; and thus, both could be used as alternative methods for evaluating e-cash security.

schemes rely on a variation of Diffie-Hellman problem as the assumption of its security model. Since the difficulty of Diffie-Hellman problem is quite well-known, then it is quite difficult to break the e-cash scheme that implement Diffie-Hellman problem as its main security mechanism. Another approach is to evaluate the security of cryptographic primitive used in the e-cash scheme, such as the digital signature scheme. As we can see in various works in digital signature [13][14][15][16], the process to evaluate the security is using logical proof. The result provides a strong basis to determine the security of the cryptographic primitive, and in the end ensure the security of the e-cash scheme that using the primitive. Dreier et al., [17] propose another method of e-cash security evaluation using pi-calculus. Rather than evaluating the cryptographic scheme using the random oracle model, their method evaluates the protocol, which represents the operational step-by-step procedure of the e-cash scheme. As such, the pi-calculus method can simulate the implementation condition more closely than the random oracle model can. In their paper, Dreier et al., use an implementation of this method, ProVerif, to analyze the implementation of Chaum's scheme [1].
Both the random oracle model and the pi-calculus method produce qualitative results as proofs of security. The results of these evaluation methods do not provide a number which could be used as a basis of measurement or comparison of security levels. Instead, they only provide logical reasoning that states why the scheme is secure. These logical proofs can be difficult to understand for someone without a background in computer science or mathematics. This paper proposes a method for evaluating the security of e-cash which produces a numerical result. This method uses a similar approach to the method in [17], by evaluating the protocol. Our method calculates the probability of a security risk using a Markov chain technique. This method provides a quantitative result that is indicative of the implementation conditions. In this paper, we also provide a sample calculation for this evaluation method by measuring the security of Chaum's untraceable e-cash scheme [1]. The evaluation result is then compared to the results of Dreier et al.'s pi-calculus evaluation of the same e-cash scheme.

Proposed Method
The proposed method of evaluation consists of four phases: redefining the protocol into its formal description, constructing the attack scenario, constructing the transition matrix, and calculating the Markov chain probability. This method assumes that it is possible to calculate the probability of an attack on the cryptographic scheme used in an e-cash scheme. The phases of our evaluation method can be seen in Figure 1.

Redefinition of Formal Description
The first phase of the evaluation is to redefine the protocol in the e-cash scheme to make it suitable for evaluation using Markov chain techniques. The Markov chain evaluates the probability of transition between states, while e-cash protocols are usually in the form of step-by-step algorithms which do not describe the protocol state. Therefore, the common description of e-cash protocol cannot be used as a basis for protocol evaluation using Markov chain techniques. For our method, we use a finite state model as the formal description model. The protocol is modelled as a state diagram which shows states and the transitions between them. The state diagram provides the basis for forming the transition matrix. Since e-cash protocols are usually not state-oriented, determining the states from the protocol is often not a straightforward process. One possible approach is to evaluate the purpose of each data transaction in a protocol to determine the state involved and its transitions.

Constructing Attack Scenarios
This phase aims to generate the success probability of an attack on the cryptographic scheme used in an e-cash scheme. Most e-cash schemes rely on one or more cryptographic schemes for their basic security. The strength of a cryptographic scheme depends on the kind of adversary it is protected from. The success probability of an attack might differ depending on which party involved in the process is honest. Even if the calculation shows that the probability of a successful attack on a cryptographic scheme is unacceptable, the e-cash scheme can remain secure. It may have some other mechanism in its protocol to reduce or mitigate the risk associated with the attack.

Constructing the Transition Matrix
In this phase, we build transition matrices based on the results of the first and the second phase. A transition matrix is built for each attack scenario generated from the second phase. This matrix will be used as the base tool for calculations in the next phase. A state in an e-cash protocol can usually only change into two other states. If the output of the state complies with the rule of the protocol, it changes into the next correct state. If the output does not comply with the rule, it changes into the "ABORT" state and ends the protocol. As such, the transition matrix can be represented as follows: The equation above involves three states: 1 , 2 , and . States 1 , 2 are the proper state that the protocol should follow. State is the "ABORT" state which becomes the end state if the proper condition is not met during the protocol run. The variables , represent the probabilities that a state will change into the next state following the proper protocol. The values of and are the same as the probabilities of an attack on the cryptographic scheme calculated in the previous phase. This also depends on which attack scenario is being evaluated. For example, if all entities involved in this protocol are honest, then the = 1, = 1. If there is a dishonest entity, then the values of , become the probability of that entity breaking the cryptographic scheme.

Calculation of Markov Chain Probability
The Markov chain probability determines the security of an e-cash scheme against certain attack scenarios. The security relates to the probability of an e-cash scheme completing its protocol (not ending in "ABORT" state) in every attack scenario. The probability is calculated using a general Markov chain, as follows: where denotes the number of steps needed to complete the protocol normally. The calculation only sees the probability of a transition from the protocol's start state ( ) to its end state ( ) in steps. The resulting probability is used as a quantitative basis to determine the security of the scheme.

Application in Evaluating Chaum's E-cash Scheme
In this section, we evaluate the security of Chaum's offline e-cash scheme [1] using our method. The results of this evaluation are then compared to the evaluation done by Dreier et al., using the pi-calculus method [17] to gauge the effectiveness of our method.
The analysis focuses only on the payment protocol of Chaum's e-cash scheme. The scheme has another protocol, the withdrawal protocol, which is used in creating new e-cash data. The security of the withdrawal protocol does not contribute directly to the security of the scheme since the presence of a dishonest entity in this protocol results in neither gain nor loss.

Redefining the Formal Description
Although the payment protocol involves three entities (user, merchant, and bank), our evaluation sees the whole protocol as a single system, as the state diagram describes how the whole protocol works rather than how each entity behaves. The flow of the payment protocol in Chaum's scheme is as follows: a. User sends e-cash data to Merchant. Otherwise, the protocol proceeds to next step. e. Merchant sends and User's proof to Bank. f.
If Bank verifies the correctness of , it settles the transaction. Otherwise, it aborts and traces the User.
The result of redefinition of this protocol can be seen in Figure 2; it has five states and five transitions.
Step (a) is described as the start of the protocol in the form of the REQUEST state. Steps (b to d) verify the validity of . These steps are represented as the CHALLENGE state of the protocol.
Step (e) describes the state that verifies the signature of Bank and checks for double spending.

Constructing Attack Scenarios
To construct the attack scenario, we needed to choose some implementation details for the e-cash scheme. In Chaum's scheme, a digital signature is needed to create the e-cash data. This digital signature protects the scheme from forgery. For our evaluation, we chose to use the RSA signature scheme with modulus of order 10 80 and security parameter = 50. Both values are secure enough to be chosen as implementation values. This determines the length of e-cash data and the number of random binary string needed during the CHALLENGE state. We considered three attack scenarios: double spending, forgery, and exculpability. When calculating the success probability of each scenario, we also considered the entities that perform the attack.

Double Spending
The success probability of double spending depends on two things. First, the time elapsed between two VERIFY state that uses the same e-cash data. The longer the time, the smaller the success probability. Second, the probability of the merchants in both transactions using the same permutation of binary string in the CHALLENGE state. If this happens, the Bank still can determine that the data has been used during the VERIFY state in the second transaction occurs. However, since the Bank only possesses half of the proof-of-ownership for each due the nature of the blind signature used in the Withdrawal protocol, the Bank cannot determine the perpetrator of the double spending.
Steps e and f in the payment protocol can be conducted much later than the actual transaction (due to the scheme being offline), so the user could still get away with double spending.
The probability of this attack can be formulated as follow: with , denoting the two-different payment protocol involved in double spending and denoting the time elapsed between the two protocols. The first part of equation ( ( = )) represents the probability of combination of both proof , are the same. The second part ( ( )) represents the probability due to elapsed time.
In our evaluation, we did not consider the scenario where the User and Merchant collude to cheat the honest Bank by creating two different transactions and processes, both VERIFY states at the same time. In this scenario, although the probability of success is ≈ 1 and the Bank would not be able to determine which User is involved in this double spending, the Bank could still detect the existence of double spending. It might not credit the Merchant account with settlement, leaving only the User with the benefit. As such, this scenario is unlikely.
As such, we consider only the attack scenario where only the User is dishonest. The probability of both Merchants using the same binary string array corresponds to 2 = 25, which results in ( = ) = 2.98 × 10 −7 . The time elapsed component of (3) can be approximated as ( ) ≈ 0, since the time needed to change Merchant is likely to be relatively large. However, for our calculation we will use ( ) = 10 −6 , to represent a number that is practically zero but still large enough to be used in the calculation. The success probability of double spending by the User then becomes = 2.98 × 10 −13 .

Forgery
Forgery can only be initiated by the User. To forge the e-cash data, the User needs to falsify the Bank signature. The probability of breaking the RSA signature is the same as the probability of factoring [18]. Given sufficiently long amount of time, the factoring theoretically can always succeed [19]. However, if we ignore the time needed to factor the number, the probability of breaking RSA is: The process of verifying the signature happens in the VERIFY state by the Bank. In the CHALLENGE state, the Merchant only checks for the proper form of .

Exculpability
The exculpability scenario could happen if the Bank was dishonest. To accuse an honest User for double spending, the Bank needs to break the blind signature. In common double-spending scenarios, the Bank could determine the User from the User's response in the CHALLENGE state, which is transferred to the Bank in the VERIFY state. The proof-of-ownership for any e-cash data in [1] consists of two parts: and ⊕ ( ∥ ( + )), where is a random string/number chosen in withdrawal by User. The identity of the User is stored in as an account number, and denotes the counter associated with it. If the Bank has both pieces of information, it can extract to identify the User. To accuse an honest user of double spending, the Bank must acquire u from the second part of the proof without knowing . The probability of successfully doing such an operation is proportional to the bit length of . For the purpose of this evaluation, let 0 ≤ ≤ 1024, which makes the length of = 2 10 . The probability of successfully extracting the User identity without having is: where denotes the length of . Having the Merchant collude with the Bank does not change this probability. To provide both parts of proof to the Bank, the Merchant needs to force the User to double spend the e-cash data, which is unlikely to be done by the user under normal circumstances.

Constructing the Transition Matrix
The transition matrix for Chaum's payment protocol can be generated using the state diagram in Figure 2, together with the attack scenarios and their probabilities in section 4.2 the general transition matrix can be expressed in Table 1.
As stated in (1), the values of a and b depend on the attack scenarios. The probability of each scenario becoming the value of either a or b, depends on where the cryptographic attack is evaluated. The value of a and b for this evaluation is shown in Table 2.

Calculation of the Markov Chain
For each attack scenario in Table 1, we calculated the probability that the protocol will end in the proper state using several normal steps. The start state of the evaluated protocol is "PAYMENT" state, as can be seen in Figure 2. The protocol should end its process in "SETTLE" state after three steps in the normal condition. Should an attack occur, the probability of this protocol ending in "SETTLE" state should be low; and the probability that it will end in the "ABORT" state should be high.
By using (2), the probability of success for each attack can be seen in Table 3. Double spending has the probability of 2.646 × 10 -38 to succeed. Forgery has lower probability ≈ 10 −120 . The exculpability scenario has the highest probability among the three scenarios, but it is still low. It can be concluded that it is improbable that any of the three attack scenarios would be carried out successfully.  Table 4 shows a comparison of results from the method used by Drier et al., and our method. Dreier et al., evaluated Chaum's scheme with security properties defined [20]; whereas, our evaluation does not strictly follow those definitions. However, the results of the two evaluation methods should still be comparable. The results from Drier et al. are shown as "hold" (where the scheme meets the security criterion for that particular scenario) and "fail" (where the scheme does not meet the security criterion). Our results state whether the success of the attack scenario is probable, based on the probabilities calculated earlier. The evaluation results of double spending and exculpability are similar in both methods. It is useful to note that Dreier et al., evaluate the process of double spending only at the interaction between User and Merchant. The Merchant cannot determine whether e-cash data has been spent before. In our method, we evaluate the probability of double spending not only at the interaction of User and Merchant, but also at the interaction of Merchant and Bank.

Comparison of Result with Pi-calculus Method
It can be seen from Table 4, that the two methods seem to differ in their results for forgery. Our method indicates that forgery is improbable, but Dreier et al., fails the scheme in this criterion. This is due to the different definitions of forgery used in these two evaluations. Dreier et al., define forgery as the double spending of e-cash data, while we use the standard definition of forgery: the creation of e-cash data by the User without using the Withdrawal protocol. The definition used by Dreier et al., only covers the first half of the process that is defined in our definition of forgery.
Our method cannot evaluate the anonymity properties of an e-cash scheme. Our method only evaluates the scheme's protocol, as the anonymity attack is usually conducted outside the protocol of e-cash by evaluating the receipt data or the e-cash data itself.

Conclusion
We have presented a numerical method for the security evaluation of an e-cash scheme. We have shown that this method can produce a quantitative result to evaluate the security level. The usage of a Markov chain for evaluation is effective as it can be used to evaluate the security of the e-cash scheme. From the comparison made with the pi-calculus method in evaluating Chaum's e-cash scheme, the results are similar. However, there is a difference in the result of forgery evaluation between our method and the pi-calculus method. The difference comes from the different definitions of forgery used by the two methods. Intrinsically, the results do not contradict each other.
Yet, our method is unable to evaluate the anonymity property of the e-cash scheme. This limitation comes from the fact that our method only evaluates the protocol and the events directly related to it. Attacks on anonymity lie outside the boundary of the protocol. Anonymity is dependent on how the scheme stores its user identities; thus, it is only related to the cryptographic scheme and not to the protocol that is used in the e-cash scheme.