Light-weight Public Key - ELLI
[Back] Our normal public key methods do not quite work on RFID devices, so let's look at the proposed method for proving that a RFID device is real. The method proposed within [paper] is standardised as ELLI (Elliptic Light) within ISO/IEC 29192-4:2013/Amd 1.
Our normal public key methods do not quite work on RFID devices, so let's look at the proposed method for proving that a RFID device is real.
The 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:
from os import urandom from eccsnacks.curve25519 import scalarmult, scalarmult_base import binascii lamb = urandom(32) a = scalarmult_base(lamb) eps = urandom(32) b = scalarmult_base(eps) c = scalarmult(eps, a) d = scalarmult(lamb, b) print "RFID private key: ",binascii.hexlify(eps) print "Reader private key: ",binascii.hexlify(lamb) print print "A value: ",binascii.hexlify(a) print "B value: ",binascii.hexlify(b) print "C value: ",binascii.hexlify(c) print "D value: ",binascii.hexlify(d) print print "Check that C is equal to D" print "Press blue button for another example!"
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: