Tag authentication method using rotation, and tag and reader performing the method

• US 8,031,055 B2
• Filed: 02/21/2008
• Issued: 10/04/2011
• Est. Priority Date: 10/18/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Tae Jin, Kim, Eunah, Yi, Jeong Hyun, Kwon, Taekyoung
• Primary Examiner(s): Lee; Benjamin C
• Assistant Examiner(s): MEHRAVARI, PETER CYRUS
• Application Number:
  US12/034,740
• Publication Number:
  US 20090102606A1
• Time in Patent Office: 1,321 Days
• Field of Search: 340/10.1, 340/10.51, 340/572.1, 340/5.8, 380/258, 380/46, 380262-268, 713168-169, 708/250, 708/256
• US Class Current: 340/10.51
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A tag authentication method, and a tag and reader performing the method are provided. The tag authentication method, including: a reader generating a first random number and transmitting the first random number to a tag; the reader receiving a second random number and a first verification value from the tag; the reader computing a second verification value based on the first random number and the second random number; and the reader comparing the first verification value and the second verification value.

Claims

1. A tag authentication method of a reader, the method comprising:

generating a first random number and transmitting the first random number to a tag;

receiving a second random number and a first verification value from the tag;

generating a rotation factor using the second random number and a first secret value;

computing a second verification value based on the first random number, a second secret value, and the rotation factor; and

comparing the first verification value and the second verification value.

2. The tag authentication method of claim 1, wherein the generating the rotation factor comprises:

separating a first computation result of the second random number and the first secret value, or separating a second computation result of the first random number, the second random number, and the first secret value, to generate a first rotation factor and a second rotation factor.

3. The tag authentication method of claim 1, wherein the rotation factor includes a first rotation factor and a second rotation factor, and

the computing of the second verification value comprises:

shifting one bit of the first random number by a first rotation factor;

shifting one bit of the second secret value by a second rotation factor; and

computing the second verification value based on the bit-shifted first random number and the bit-shifted second secret value.

4. The tag authentication method of claim 1, wherein the reader and the tag share a first secret value, a second secret value, and a predetermined random variable.

5. The tag authentication method of claim 4, wherein the predetermined random variable includes a probability of noise that occurs during the authentication of the tag.

6. A tag authentication method of a tag, the method comprising:

generating a second random number;

receiving a first random number from a reader;

generating a rotation factor using the second random number and a first secret value;

computing a first verification value based on the first random number, a second secret value, and the rotation factor; and

transmitting the second random number and the first verification value to the reader.

7. The tag authentication method of claim 6, wherein the rotation factor includes a first rotation factor and a second rotation factor,

wherein the computing of the first verification value comprises:

shifting one bit of the first random number by the first rotation factor;

shifting one bit of the second secret value by the second rotation factor; and

computing the first verification value based on the bit-shifted first random number, the bit-shifted second secret value, and noise.

8. The tag authentication method of claim 6, wherein the generating of the rotation factor comprises:

separating a first computation result of the second random number and the first secret value, or separating a second computation result of the first random number, the second random number, and the first secret value, to generate a first rotation factor and a second rotation factor.

9. The tag authentication method of claim 8, wherein the first rotation factor corresponds to a bit sequence from k^th to k/2^th bit of the first computation result or the second computation result, and the second rotation factor corresponds to a bit sequence from k/2−

1^th to 1^st bit of the first computation result or the second computation result.

10. The tag authentication method of claim 6, wherein the reader and the tag share a first secret value, a second secret value, and a predetermined random variable.

11. A reader for authenticating a tag, the reader comprising:

a first random number unit to generate a first random number and to transmit the first random number to the tag;

a receiving unit to receive a second random number and a first verification value from the tag;

a second verification value computation unit to generate a rotation factor using the second random number and a first secret value, and to compute a second verification value based on the first random number, a second secret value, and the rotation factor; and

a comparison unit to compare the first verification value and the second verification value.

12. The reader of claim 11, wherein the second verification value computation unit comprises:

a rotation factor generation unit to generate the rotation factor using the second random number and the first secret value.

13. The reader of claim 12, wherein the rotation factor includes a first rotation factor and a second rotation factor, and the second verification value computation unit computes the second verification value based on the first random number with one bit being shifted by the first rotation factor, and computes the second secret value with one bit being shifted by the second rotation factor.

14. The reader of claim 12, wherein the rotation factor generation unit separates a first computation result of the second random number and the first secret value, or separates a second computation result of the first random number, the second random number, and the first secret value, to generate a first rotation factor and a second rotation factor.

15. A tag to be authenticated by a reader, the tag comprising:

a second random number generation unit to generate a second random number;

a first random number receiving unit to receive a first random number from the reader;

a first verification value computation unit to generate a rotation factor using the second random number and a first secret value, and to compute a first verification value based on the first random number, a second secret value, and the rotation factor; and

a transmission unit to transmit the second random number and the first verification value to the reader.

16. The tag of claim 15, wherein the first verification value computation unit comprises:

a rotation factor generation unit to generate the rotation factor using the second random number and the first secret value.

17. The tag of claim 16, wherein the rotation factor includes a first rotation factor and a second rotation factor, and the first verification value computation unit computes the first verification value based on the first random number with one bit being shifted by the first rotation factor, and computes the second secret value with one bit being shifted by the second rotation factor, and noise.

18. The tag of claim 15, wherein the reader and the tag share a first secret value, a second secret value, and a predetermined random variable, and the random variable includes a probability of noise that occurs during the authentication of the tag.