Public-Key Crypto and RFID Tags
Public-Key Crypto and RFID Tags
We live in a world where little around us can be truely trusted. This includes the devices and the products that we use. So can we create devices which can tell us if we are using a fake medicine, or where we can truely trace products through a supply chain? So in these times of isolation, I’ve been turning to all those research papers I never quite was able to read properly, and so when a student asked me why elliptic curve methods for RFID was a light-weight crypto method, I dug out this paper [here]:
Within it, the authors outline that we generally struggle to apply public key encryption into RFID systems, as the complexity of the hardware and the battery drain is too high. The solution is to use an optimized ECC method using 131-bit and 139-bit prime numbers are used to reduce the complexity, and drain on the battery. For Bitcoin, for example, we use Secp256k1, and which uses a 256-bit prime number (2²⁵⁶–2³²–2⁹–2⁸–2⁷–2⁶–2⁴–1) and with Curve 25519 we use a prime number of 2²⁵⁵-19. In the paper, the authors propose a method with around 10,000 gates in order to implement the signing method for a device. Other researchers have implemented a 166-bit prime of to give 30,333 gates. There is thus a strong balance between security an performance.
Meet ELLI
One method proposed by the ISO/IEC as ISO/IEC 29192–4:2013/Amd 1 is named ELLI (Elliptic Light), and uses Elliptic Curves along with a Diffie-Hellman related handshake between the RFID tag and the RFID reader. Within Elliptic Curve we start with a point on a curve (P) which is known. Then we multiply this point with a large number (ε) to produce another point (A) on the curve:
A = ε P
and where A will be the public key, and ε is the private key. If ε is large enough it is then difficult to compute ε even though we have A and P. Now let’s look at the basics of ELLI. For this RFID tag contains a random value of ε (the private key), and the RFID reader generates a random value of λ. On creating the tag we calculate:
B = ε P
along with the signature of B which has been signed by a key that the RFID reader can validate. Thus the tag contains (ε, B, PublicKeySign(B)).
Each time the RFID reader wants to validate the tag it takes its random value (λ) and computes:
A = λ P
Next the RFID reader sends A to the RFID tag. The RFID tag then multiplies the value of A by its private key (ε) to get C:
C = ε A
It then sends back its public key (B), the value of C and the signature of the public key which the reader can verify. The reader then computes D:
D = λ B
and compares C and D. If they are the same we have verified the private key. This is true as:
C = ε A = ε λ P
D = λ B = λ ε P
Here is the basic method:
With this the RFID tag contains the random value (ε), the public key (B) and a signature of B that the reader can verify. Here is my Python code to implement a simple proof-of-concept (note: that it does not use the 131-bit ECC implementation) [here]:
and a sample run:
RFID private key: cdd81ca1f84206664bd9fa0fa8d1d4a6607e5dcf9440f2c340189a8a877981fb
Reader private key: 84cc838135333ce06a6b038040add35732e90f369d6d2b4cf153bcf3f5d01346
A value: 01a81171b6ff1577768da99c310960b433a9613b5f65ef499f2ebb5f13f7a730
B value: d7166ffee897d6d41f8d5c8703740e7e555dffd025691f91a7040eae07dd2d4b
C value: 53dfb1bc9fbd3b50d0e8416adb3efbe593d91881ae7a7796abeabfdbbff0622d
D value: 53dfb1bc9fbd3b50d0e8416adb3efbe593d91881ae7a7796abeabfdbbff0622d
Check that C is equal to D
It is secure as it uses the Elliptic Curve Diffie Hellman Problem (ECDHP). Eve wants to produce a fake RFID tag and receives the challenge of:
A = λ P
and now must return a valid response C, along with a public key which has been signed by an authority. Since Eve only has A and B, she cannot compute a valid response for C as she does not know λ and ε in order to compute:
λ.ε.P
Conclusions
The core application of using public key encryption is counterfit protection, and where devices could identity themselves correctly, and RFID devides provide a particular challenge.