Method and Apparatus to Provide Authentication and Privacy with Low Complexity Devices

• US 20080170695A1
• Filed: 06/11/2007
• Published: 07/17/2008
• Est. Priority Date: 06/09/2006
• Status: Active Grant

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Adler, Joseph A., M'Raihi, David
• Granted Patent: US 8,171,289 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and apparatus to provide a cryptographic protocol for secure authentication, privacy, and anonymity. The protocol, in one embodiment, is designed to be implemented in a small number of logic gates, executed quickly on simple devices, and provide military grade security.

Claims

1. A method to provide a cryptographic protocol comprising:

authentication based on a use of a private key of a low-processing-power system (LPPS);

privacy to protect a tag identifier (tag ID) so that an unauthorized party cannot learn the identifier for the tag; and

untraceability to ensure that a different value is returned in response to a challenge, so a reader cannot identify the LPPS by the response.

2. The method of claim 1, wherein the cryptographic protocol comprises elliptic curve cryptography.

3. The method of claim 1, wherein authentication comprises:

utilizing a private key of the LPPS and calculating a function of the private key and a received challenge in the LPPS.

4. The method of claim 1, wherein the untraceability comprises:

providing an additional cryptographic value concatenated with an authentication value.

5. The method of claim 1, wherein privacy comprises:

encrypting the tag ID with a public key of a reader.

6. The method of claim 1, further comprising:

exchanging initial parameters between a reader and the LPPS.

7. The method of claim 6, wherein the initial parameters include:

a tag ID, and an elliptic curve and a point on the elliptic curve for the authentication, the privacy, and the obfuscation.

8. The method of claim 7, wherein the elliptic curve and the point are the same for the authentication, the privacy, and the obfuscation.

9. The method of claim 6, wherein the reader provides the initial parameters to the LPPS.

10. A method of utilizing an RFID tag

receiving a challenge from a reader;

calculating S=f(s, O_E), U=f(u, O_O), B=E(n, k_E), G=f(A, k_O), where

A is a function of the challenge and a private key of the RFID tag;

s and u are random numbers generated by the RFID tag.

n is the tag ID,

k_E and k_o are functions of a first public key and a second public key of the reader respectively, and

O_E and O_o are originators, provided by the reader; and

returning S, U, B, and G to the reader, the returned data including a challenge response and the tag ID, and being unique for each response even when responding to an identical challenge.

11. The method of claim 10, wherein the originators O_E and O_o are points on an elliptical curve.

12. The method of claim 10, wherein the originators O_E and O_o are generators for large primes.

13. The method of claim 10, further comprising initializing the RFID tag, wherein the initialization comprises receiving from the reader:

the first public key of a first key pair for privacy;

the second public key of a second key pair for obfuscation; and

a tag ID.

14. The method of claim 13, wherein the initialization further comprises:

selecting a third key pair for authentication; and

sending a public key of the third key pair to the reader.

15. The method of claim 13, wherein initialization further comprises:

receiving from the reader a private key of a third key pair for authentication, the private key of the third key pair stored only by the RFID tag.

17. The system of claim 14, further comprising a secured memory to store the private key of the LPPS and an identifier of the LPPS.

16. A low processing power system comprising:

a transceiver to transmit and receive data, the transceiver to receive a challenge from a reader system;

a crypto logic to perform cryptographic calculations, the crypto logic for calculating S=f(s, O_E), U=f(u, O_O), B=E(n, k_E), G=f(A, k_O), where

A is a function of the challenge and a private key of the LPPS,

s and u are random numbers,

n is an identifier of the LPPS,

k_E and k_o are functions of a first public key and a second public key of the reader respectively, and

O_E and O_o are originators, provided by the reader;

the transceiver further to return S, U, B, and G to the reader system, the returned data including a challenge response and the tag ID, and being unique for each response even when responding to an identical challenge.

18. The system of claim 16, wherein the crypto logic is further for generating the random numbers s and u.

19. The system of claim 16, further comprising:

a memory to store initialization data, initialization data including the public keys of the reader, and the tag ID.

20. The system 16, wherein the originators O_E and O_o are points on an elliptical curve, and wherein originators O_E and O_o are the same point on the same elliptical curve.

21. A low processing power system (LPPS) designed to be securely interrogated by a reader system, the LPPS comprising:

a transceiver to receive a challenge from the reader system;

a crypto logic to calculate a response to the challenge, the response comprising a private key of the LPPS;

the crypto logic to calculate a return data for return to the reader system, the return data is a combination of the response to the challenge and encryption key, an authentication key, and obscuration key.

22. The system of claim 21, wherein the cryptographic key is to generate two random numbers, and further to encrypt a first random number with an encryption key, and encrypt the second random number with an obfuscation key, and to encrypt an authentication key with the reader'"'"'s public key.