Imagine you’re waiting in line, queuing to enter a major event. The ticket you have bought online is stored on your smart phone. As you swipe your phone over some designated area, an NFC connection is set up, your ticket is validated and the gates open to let you in. And the good thing is, that it all happened anonymously.
Securing Intelligent Systems
For more about security in embedded systems, be sure to join us on Feb 14, 2013, at 11pm PT, for a special webinar on best practices for secure device development and deployment. For more information, click here
In this kind of applications, your anonymity can be guaranteed by the use of recently developed anonymous credentials protocols like Idemix (IBM) or U-Prove (Microsoft). These protocols rely on Zero-Knowledge Proofs-of-Knowledge (ZKPK); you prove that you have knowledge of a certain attribute without revealing its value. The attribute is bound to a public key in a so-called commitment.
Figure 1 gives a simplified overview of such a ZKPK, in this case the Schnorr protocol. Here, y is the commitment of x. Under the strong RSA assumption, it is very hard to find x from y, even if you know g and m.
If we look at the protocol, we see that x remains hidden. The verifier only learns that y is a correct commitment. We can also see that the protocol mainly consists of communication and arithmetic – this is where our research comes to the fore.
Figure 1. Simplified version of the Schnorr ZKPK protocol.
An example of the time required to compute a simultaneous exponentiation on an embedded platform
On our test setup (discussed later on) we compared execution times for both our hardware crypto core and a software implementation.
Both hardware and software compute:
a simultaneous exponentiation, often used n anonymous credentials protocols.
We let the length of the exponents vary between 32 and 2048 bit. The length of the base operands is fixed; in this case 1024 bit. The software runs on an embedded Linux OS and uses the GMP library for the multi-precision arithmetic.
Both the processor and the IP core run at the same speed (100 MHz). We see that execution times for both approaches increase proportionally with the exponent length. However, the computations with hardware off-load are 10 to 50 times faster.
Figure 2. Execution times for simultaneous exponentiations on an embedded platform with and without hardware off-load
A platform for testing embedded security
It quickly became clear to us that both the communication and the arithmetic would pose a bottleneck when these ZKPKs were implemented on an embedded system (see the example). We wouldn’t want users to keep up the NFC connection more than, let’s say, 5 seconds. That would be in conflict with the NFC concept of “a touch” to exchange data.
To investigate this problem in detail, we constructed a test platform (see Figure 3) so we would be able to change the different aspects of the protocol in an easy way; e.g. what if we speed up the arithmetic by off-loading it to a hardware accelerator or what is the effect of the length of the operands on the speed of both communication and arithmetic?
The platform we developed is presented in the Figure 3. It is based on a Xilinx ML605 evaluation board. We added an NXP PN532 development kit for the NFC communication. A MicroBlaze, running embedded Linux, controls the complete system. Using Linux (in our case the PetaLinux distribution) has the big advantage that standard libraries become available on the embedded system; e.g. GMP for the arithmetic and libnfc for the NFC communication.
Figure 3. Embedded platform to test and evaluate anonymous credentials protocols
Working on an FPGA made it possible to easily add and develop cryptographic hardware accelerators. The rest of this article describes the design of the such an IP core we developed to do our tests.