Performance Evaluation of Primitives for Privacy-Enhancing Cryptography on Current Smart-Cards and Smart-Phones

Abstract

The paper deals with the implementation and benchmarking of cryptographic primitives on contemporary smart-cards and smart-phones. The goal of the paper is to analyze the demands of today’s common theoretical cryptographic constructions used in privacy-enhancing schemes and to find out whether they can be practically implemented on off-the-shelf hardware. We evaluate the performance of all major platforms of programmable smart-cards (JavaCards, .NET cards and MultOS cards) and three reference Android devices (a tablet and two smart-phones). The fundamental cryptographic primitives frequently used in advanced cryptographic constructions, such as user-centric attribute-based protocols and anonymous credential systems, are evaluated. In addition, we show how our results can be used for the estimation of the performance of existing and future cryptographic protocols. Therefore, we provide not only benchmarks of all modern programmable smart-card platforms but also a tool for the performance estimation of privacy-enhancing schemes which are based on popular zero-knowledge proof of knowledge protocols.

1 Introduction

With the increasing number and complexity of electronic services and transactions, the role of cryptography becomes more and more important. While the classical cryptographic algorithms for ensuring data confidentiality, authenticity and integrity are mostly well analyzed [1, 2], the modern cryptographic primitives which are used as the building blocks of many advanced privacy-enhancing schemes remain theoretical and without any evaluation on real-world devices. Therefore, the goal of this paper is to identify the most frequent cryptographic primitives, which are being used in, e.g., digital identity protection schemes, attribute-based authentication schemes and credential schemes, and analyze these primitives on commercially available devices.

For our benchmarks, we chose mobile and personal devices. The reason is that these devices are becoming the most popular ones for personal electronic transactions. For user authentication, eIDs and access control, the smart-cards are already the most preferred devices. For Internet transactions, the mobile phones and tablets are becoming the best choice for many users today. Thus, we chose smart-cards, mobile phones and tablets as the platforms for our benchmarks. We ran the benchmarks on all major programmable smart-card platforms, namely on JavaCards [3], .NET cards [4] and MultOS cards [5]. We chose Android as the platform for the smart-phone and tablet benchmarks because Android, together with Apple iOS, is the preferred operating system for mobile devices worldwide [6].

1.1 Related Work

We consider classical cryptographic constructions, such as RSA signatures, DSA signatures, hashes and symmetric block ciphers, to be well analyzed according to their speed on low-performance devices. A complex analysis of modern symmetric encryption algorithms is provided in [1]. Here, a selection of 12 block ciphers is evaluated on 8-bit microcontrollers. Furthermore, the paper [2] deals with the benchmarking of modern hash functions. A selection of 15 hashes (some of them in more versions) was evaluated on 8-bit microcontrollers. These rigorous benchmarks can be taken as a rich source of information when implementing the classical cryptographic systems.

On the other hand, there is a lack of information when someone needs to implement advanced privacy-enhancing schemes which employ provably secure protocols such as $\varSigma$-protocols [7], proof of knowledge ($PK$) protocols [8] or cryptographic commitments [9]. In fact, there are many theoretical cryptographic schemes which use these constructions without any analysis of implementability. The most well-known examples are group signature schemes [10], verifiable encryption schemes [11], anonymous credential systems [12] and Vehicular Ad-hoc Networks (VANETs). Unfortunately, only little information about the performance of these protocols can be inferred from the implementation papers [14, 15]. These papers usually provide information about the overall performance of the schemes, but little about the performance of the building blocks used. Other papers [13, 16] present only partial information. Since the building blocks are usually shared among many privacy-enhancing schemes, the information about their performance would be very useful for the evaluation of many unimplemented schemes and newly emerging theoretical constructions.

1.2 Our Contribution

In this paper, we provide benchmarks of selected cryptographic primitives on all major smart-card platforms and three Android devices. We chose the cryptographic primitives which are commonly used in modern privacy-enhancing schemes and which have not been evaluated on resource-limited devices yet. These primitives are described in Sect. 2. The testing environment is described in Sect. 3. The actual benchmarks are included in Sect. 4. Finally, short analysis of results and the examples of how to use our results for the performance estimation of novel schemes is provided in Sects. 4.3 and 4.4.

2 Cryptographic Constructions

We briefly introduce the cryptographic constructions selected for benchmarking in this section. We chose the constructions and protocols which are often used in privacy-enhancing schemes. These constructions work as the building blocks and are modularly used in many today’s schemes (such as IBM’s Idemix [17], Microsoft’s U-Prove [18], HM12 [19], etc.). These and similar schemes are further used in many privacy-enhancing applications (such as access control services, inter-vehicular communication, electronic IDs, e-cash) whose description is out of scope of this paper.

2.1 Classical Algorithms

We call well-known cryptographic algorithms, such as block ciphers, digital signatures and hash functions, the classical algorithms. These algorithms are usually provided directly by the API (Application Programming Interface) of almost all smart-cards and smart-phones. The examples of most common classical algorithms are DES [20], 3DES, AES [21] block ciphers and RSA [22], DSA [23] digital signatures and MD5 [24], SHA-1, SHA-2 [25] hash functions.

2.2 Commitment Schemes

A cryptographic commitment scheme can be used in scenarios where a user is required to bind to a number (e.g., a secret key) without disclosing it. There are two properties which must be fulfilled. They are the hiding property and the binding property.

• Hiding property: it is difficult¹ to learn the secret number from the knowledge of the commitment.

• Binding property: once committed to a number, the user cannot change it without changing the commitment.

Discrete Logarithm Commitment Scheme. Mostly, the DL commitment scheme works with the subgroup $\mathbb {Z}_q^*$ of a multiplicative group $\mathbb {Z}_p^*$. The subgroup $\mathbb {Z}_q^*$ is defined by a generator $g$ of order $q$ in $\mathrm{{mod}}\,{p}$, where $q$ and $p$ are large primes and $q$ divides $p-1$. The same group is used in the Digital Signature Algorithm (DSA) [23]. Numbers $g, q, p$ are system parameters which are made public. To commit to a number $w<q$, a user computes $c=g^w \,\mathrm{{mod}}\, p$. The user can later decide to open the commitment by making $w$ public.

Pedersen Commitment Scheme. The systems parameters $g, q, p$, used in the DL commitment scheme, can be also used in the Pedersen scheme [9]. Additionally, one more generator $h$ is used. It is important that $\log _gh\,\mathrm{{mod}}\, p$ is unknown to the user. The commitment to a secret number $w$ is computed as $c=g^wh^r\,\mathrm{{mod}}\, p$ where $r$ is a random number smaller than $q$ chosen by the user. The user can later decide to open the commitment by making $(w, r)$ public.

2.3 Proof of Knowledge of Discrete Logarithm Protocols

The proof of knowledge ($PK$) protocols can be used by a Prover to give a proof of knowledge of discrete logarithm ($PKDL$). Using the proof of knowledge protocol, the Prover is able to convince a Verifier that he knows $w=\log _{g}c \,\mathrm{{mod}}\, p$ from the aforementioned DL commitment without actually disclosing the secret value $w$. In the CS notation [8], which we use throughout the paper, the protocol is denoted as $PK\{w: c=g^w \,\mathrm{{mod}}\, p\}$. The most used practical $PKDL$ protocol for general groups, called Schnorr protocol [26], is recalled in Fig. 15 in Appendix.

2.4 Proof of Discrete Logarithm Equivalence

Using the proof of knowledge protocols, it is easy to give a proof that two different DL commitments $c_1, c_2$ were constructed using the same exponent $w$, so that $w=\log _{g_1}c_1=\log _{g_2}c_2 \,\mathrm{{mod}}\, p$. For this type of proof, the proof of discrete logarithm equivalence ($PDLE$) protocols can be used. The protocol is then denoted as $PK\{w: c_1=g_1^w \,\mathrm{{mod}}\, p \wedge c_2=g_2^w \,\mathrm{{mod}}\, p\}$. A practical example based on the Schnorr protocol is recalled in Fig. 16 in Appendix.

2.5 Signatures and Other Derived $PK$ Protocols

In the last three sections, we introduced simple cryptographic primitives which are very often used as the building blocks in more advanced schemes. In our examples, we described very simple protocols only. Nevertheless, these protocols can be modularly combined in much more complex systems. For example, the proof of knowledge protocols can be adapted to the proofs of knowledge of DL representation of a public value $c$ with respect to multiple generators $g_1, g_2, \dots , g_i$. Such a protocol is described in CS notation as $PK\{(w_1, w_2, \dots , w_i): c=g_1^{w_1} g_2^{w_2} \dots g_i^{w_i} \,\mathrm{{mod}}\, p\}$. Also, $PK$ protocols can be used for proving the knowledge and equivalence of discrete logarithms of different representations. The protocol $PK\{(w_1, w_3): c_1=g_1^{w_1} g_2^{w_2} g_3^{w_3} \wedge c_2=g_1^{w_2} g_3^{w_3 } \,\mathrm{{mod}}\, p\}$ is a simple example in CS notation. The number of possible variations is unlimited. The work [8] can be taken as a fundamental reference for the construction of $PK$ protocols.

By using the Fiat-Shamir heuristic [27], all the $PK$ protocols can run non-interactively. Then, a hash $\mathcal {H}$ of all protocol parameters is used. All protocols shown in the Appendix are non-interactive. This adaptation leads to signature schemes. By taking our simple $PKDL$ protocol from Sect. 2, we can get a digital signature protocol where $w$ works as a private key. The protocol uses a hash function $\mathcal {H}$ of the message and all protocol parameters. For reference, the signature proof of knowledge protocol ($SPK$) is depicted in Fig. 17 in Appendix. All $PK$ protocols can be easily adapted to signatures using this approach [27].

In previous sections, we considered only examples based on the simple DSA group [23]. But also different groups can be used in $PK$ protocols (e.g., RSA group [22], Okamoto-Uchiyama (OU) group [28], etc.). Still, the atomic operations of these protocols remain the same. Namely, modular arithmetic, random number generation and hash functions are used. That is the reason why we implemented these atomic operations in our benchmarks. Based on their performance, we can compute the actual performance of $PK$ protocols and subsequently the performance of advanced systems based on $PK$ protocols.

Table 1. The specification of the JavaCards used in our benchmarks.

3 Selected Devices and Benchmark Settings

This chapter contains the information about the benchmark settings and about the software/hardware we used.

3.1 Selected Devices

The evaluation of cryptographic primitives was carried out using all major smart-card platforms, namely JavaCards [3], .NET cards [4] and MultOS cards [5]. Furthermore, we implemented the benchmark tests on the Android platform, namely on Android smart-phones and an Android tablet.

JavaCards. JavaCard platform [3] provides a development and runtime environment for applications (called applets) written in Java. In our benchmarks, we used Oberthur Technologies ID-One Cosmo V7.0-A [29, 30] and Gemalto TOP IM GX4 [31] cards. The hardware specification of these cards is described in Table 1.

.NET Smart-Cards. .NET smart-card platform [4] provides very similar features as JavaCards for applications developed using any language of the .NET framework. In our benchmarks, we used the Gemalto .NET V2+ cards. The hardware specification of these cards is described in Table 2.

MultOS Smart-cards. The last smart-card platform we used for benchmarking is the MultOS platform [5]. In comparison to JavaCard and .NET cards, MultOS allows the development of applications in both high level languages (Java and C) and assembly language. This provides developers with much wider opportunities and better access to hardware. In particular, only the MultOS cards allow the direct big-integer modular operations through the default API. The hardware specification of MultOS ML2-80K-65 and ML3-36K-R1 cards is described in Table 2.

Table 2. The specification of the .NET cards and the MultOS cards used in benchmarks.

Mobile Devices. The Android devices form a different group which is incomparable to smart-cards. While smart-cards are very resource-limited devices with extremely low RAM and slow CPUs, the mobile phones and tablets resemble more classical PCs. They have strong CPUs with frequency over 1 GHz and enough RAM (hundreds of megabytes). Still, these devices are extremely mobile and very popular for personal electronic transactions. Due to this reason, we included them to our benchmarks. The hardware of selected Android devices is described in Table 3.

Table 3. The specification of the Android devices used in our benchmarks.

3.2 Measured Operations and Keylengths

In the Sect. 2, we showed the cryptographic commitments and proof of knowledge protocols. We included only simple examples to illustrate these primitives. Nevertheless, these basic constructions can be modularly compiled into advanced systems. The discrete logarithm commitments, proof of knowledge of discrete logarithm protocols and proofs of discrete logarithm equivalence protocols are the building blocks of many complex modern systems [17–19]. But still, even the complex systems are based on the same atomic operations as the primitives selected by us. It can be observed from Sect. 2 that only random number generation, hash functions and big-integer modular arithmetic operations are needed for all selected protocols. Namely, the following operations are required.

• RNG - Random Number Generation: on all platforms and devices, we measured the time of generation of large random numbers of length 160 bits (RNG_160 operation) and 560  bits (RNG_560 operation).

• Hash Functions: on all platforms and devices, we measured the time of computation of following hash functions.

  • SHA1_4256: SHA1 of 4256 bit random data²

  • SHA1_7328: SHA1 of 7328  bit random data

  • SHA1_20000: SHA1 of 20000  bit random data

  • SHA2_8448: SHA2 of 8448  bit random data

  • SHA2_14592: SHA2 of 14592  bit random data

  • SHA2_20000: SHA2 of 20000  bit random data

• Big-Integer Modular Arithmetic Operations: it can be observed from our cryptographic overview in Sect. 2 that the proof of knowledge protocols heavily rely on arithmetic operations in groups where the discrete logarithm operation is hard to compute. Namely, modular operations with moduli in orders of thousand bits are required. These operations are usually available on the PC platform in the form of BigInt libraries (such as OpenSSL, Bouncy Castle, etc.). Unfortunately, these libraries are missing on smart-cards. Only the MultOS platform supports direct modular operations. Thus, the following operations were implemented and measured on all selected platforms and devices. The bit-lengths of moduli and operands were selected according to the most popular group sizes in cryptography (1024 and 2048  bit modulus).

  • MExp1024_160: Modular Exponentiation with 1024 b modulus and 160 b exponent

  • MExp1024_368: Modular Exponentiation with 1024 b modulus and 368 b exponent

  • MExp2048_160: Modular Exponentiation with 2048 b modulus and 160 b exponent

  • MExp2048_560: Modular Exponentiation with 2048 b modulus and 560 b exponent

  • MMult1024: Modular Multiplication with 1024 b modulus and operands

  • MMult2048: Modular Multiplication with 2048 b modulus and operands

• Big-Integer Arithmetic Operations: additionally to modular operations, some non-modular (plain) big-integer operations were implemented as they are contained in $PK$ protocols which operate in hidden order groups.

  • Mult320: Multiplication of two 320 b numbers

  • Sub400: Subtraction of two 400 b numbers

Although the above selected bit-length combinations do not include all the variants used in today’s cryptographic schemes, they represent a sample which can be further interpolated to get the estimation of other bit-lengths. Thus, an estimate of smart-card performance of any new protocol, which is based on above operations, can be created.

3.3 Benchmark Environment

The hardware selected for our benchmarks is described in Sect. 3. The operations measured on the hardware are listed in the previous Sect. 3.2. We measured the time necessary for the computation of each operation 25  times. We present the arithmetic mean of these values. The resulting time does not include the time of communication with the device (sending inputs and receiving results). The code was implemented by a single person on smart-cards and by a single person on Android devices. Thus, the influence of different programming styles is eliminated. We tried to use the default API of our cards as much as possible. To increase the speed of computation, we used the RSA encryption method to implement modular exponentiation. For many operations (e.g., for modular arithmetic), only some cards, namely those running MultOS, were providing the necessary interface. On the rest, we had to implement our methods.

4 Benchmark Results

We divided our results into a smart-card section and an Android section. The graphs in the next two sections show the time in milliseconds of the operations specified in the Sect. 3.2 above.

4.1 Benchmarks on Smart-card Devices

Figures 1, 2, 3, 4, 5, 6 and 7 show the time in milliseconds of operations specified in captions.

Fig. 1.

RNG_160 (blue) and RNG_560 (red)

Fig. 2.

SHA1_4256 (blue), SHA1_7328 (red) and SHA1_20000 (green)

Fig. 3.

SHA2_8448 (blue), SHA2_14592 (red) and SHA2_20000 (green)

Fig. 4.

MExp1024_160 (blue) and MExp1024_368 (red)

Fig. 5.

MExp2048_160 (blue) and MExp2048_560 (red)

Fig. 6.

MMult1024 (blue), MMult2048 (red)

Fig. 7.

Mult320 (blue) and Sub400 (red)

4.2 Benchmarks on Android Mobile Devices

Figures 8, 9, 10, 11, 12, 13 and 14 show the time in milliseconds of operations specified in captions.

Fig. 8.

RNG_160 (blue) and RNG_560 (red)

Fig. 9.

SHA1_4256 (blue), SHA1_7328 (red) and SHA1_20000 (green)

Fig. 10.

SHA2_8448 (blue), SHA2_14592 (red) and SHA2_20000 (green)

Fig. 11.

MExp1024_160 (blue) and MExp1024_368 (red)

Fig. 12.

MExp2048_160 (blue) and MExp2048_560 (red)

Fig. 13.

MMult1024 (blue), MMult2048 (red)

Fig. 14.

Mult320 (blue) and Sub400 (red)

4.3 Results Analysis

Smart-Cards. It was possible to implement all required operations on all selected cards with the exception of MultOS ML2-80K-65 card which is lacking the support of SHA2 and 2048 b modular exponentiation. In many operations, the JavaCard Oberthur ID-one v7.0a is very fast (in particular, in random number generation and 1024 b modular exponentiation). Often, the bit-length of inputs (cryptographic group size) does play a significant role, for example in the case of modular exponentiation. Thus, we recommend to plan ahead before implementing and choose the right balance between speed and security (group size). Even with modern smart-cards, operations in 2048 b groups might be too demanding. When implementing complex privacy-enhancing schemes, operations in 2048 b groups would be probably too slow. Also, a big difference among cards appears when the modular multiplication and non-modular operations are needed. This is the case of all $PK$ protocols where a group with unknown order is used (such as RSA group [22], OU group [28]). Then, the MultOS cards are much faster than the rest due to their direct support of these operations in API, in particular due to their built-in support of accelerated modular multiplication.

Android Devices. It is no surprise that most operations are several hundred times faster on Android devices than on smart-cards. All primitives can be easily implemented on Android. Due to the high performance, we recommend using larger (and safer) 2048-bit groups and more recent primitives (e.g., SHA-2 instead of SHA-1 or MD5).

4.4 Performance Estimation of Selected Protocols and Schemes

Using the results of our benchmarks, we estimated the theoretical performance of the protocols introduced in the Sect. 2 and of some well-known privacy-enhancing schemes like Idemix of IBM [13], U-Prove of Microsoft [18] and HM12 [19]. All protocols are evaluated using 1024  bit groups and 160  bit secrets. All the scheme estimates include only the time of operations needed for proving the ownership of an anonymous token (we use the same approach as in [13]) and do not include any communication/management overhead. Furthermore, we used the closest bit-length of inputs. Thus, the numbers in Table 4 should be considered estimates only.

We created the estimates using our implementation of atomic operations. From the knowledge of the construction of the advanced protocols and the knowledge of performance of underlying operations, we were able to predict the performance of protocols. To find out the correctness of our estimates, we compared our results with existing, real implementations. Since they use smart-cards of different specifications, the comparison is rough only. The IBM’s Idemix has been previously implemented on JavaCards [13]. The proving protocol of the 1280  bit version took 7.5  s. Our estimates of the 1024 b version are 4.5 and 9.4  s, depending on the concrete type of our JavaCard. The Microsoft’s U-Prove scheme has been implemented on the MultOS platform [5]. The proving protocol took 0.55  son an unspecified MultOS-family card. Our estimates on our MultOS cards are 0.63 and 0.82  s, depending on the concrete type of the MultOS card. Based on these results, we consider our estimates highly accurate. Using our benchmarks, it is possible to easily predict the approximate time of newly designed protocols or cryptographic schemes.

Table 4. Performance estimation based on benchmarks.

5 Conclusion

In this paper, we provide the performance evaluation of modern cryptographic primitives on smart-cards and mobile devices. In particular, selected atomic operations which are the core of many privacy-enhancing protocols and schemes are implemented on all major programmable smart-card platforms and on the Android platform. The results can be used for the evaluation of many existing and newly appearing schemes. Using the results of implementation of all operations used in $PK$ protocols, it is possible to predict the performance of any protocol or scheme which is composed of DL-based commitments and/or DL-based proof of knowledge protocols. In particular, it is possible to predict the performance of very popular computational zero-knowledge protocols.

Even with the fastest smart-cards on the market, it is quite difficult to achieve reasonable execution times. Though, with the right choice of hardware, in particular, with hardware-accelerated cards, it is possible.

We showed our performance estimates of today’s most preferred privacy-enhancing anonymous credential schemes on all 8 devices. When compared to existing implementations, we almost match the real performance when similar hardware is used. Thus, our benchmarks can be used by cryptography designers to easily predict the performance of their protocols and schemes before implementing on smart-cards and Android devices.

Appendix

Simple examples of Proof of Knowledge ($PK$) protocols. All operations are in a group $\mathbb {Z}^*_p$ of order $q$ where discrete logarithm is hard to compute and $l_1, l_2$ are security parameters. More information about $PK$ protocols in [8].

Fig. 15.

Schnorr’s proof of knowledge of discrete logarithm protocol $PK\{w: c=g^w\}$.

Fig. 16.

Proof of discrete logarithm equivalence $PK\{w: c_1=g_1^w \wedge c_2=g_2^w\}$.

Fig. 17.

Schnorr’s signature $SPK\{w: c=g^w\}(message)$.