Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Lightweight Cryptography

for Passive

RFID Tags

... in Layman's terms!

Mathieu David

Ph.D Candidate

1

PROTOCOL

DESIGNS

PROBLEM

DEFINITION

THE

TOPIC

C'est en forgeant

qu'on devient forgeron

Practice makes perfect

Why are they not secure?

RFID Applications

Higher Cost!

More Transistors

  • Security

Lightweight Cryptography

< 2000 Gates

  • Not Clearly Organized:
  • Still several proprietary protocols
  • No easily accessible information regarding

WHICH security solution to use for a given application?

Lightweight Cryptography

iny

T

E

A

ncryption

lgorithm

No clear Guideline

+

Security is a Necessity!

17 security flaws...

Weight

No Experience

Complexity of calculations

Lenght of the Source Code

=

Ultra Lightweight Protocols

Physical Primitives

ComputationalPrimitives

Protocol vs. Primitives

  • Who cares?

Embedded RFID tag

Terrible Mistakes

  • All human beings are born free and equal in dignity and rights. They are endowed with reason and conscience and should act towards one another in a spirit of brotherhood
  • Everyone has the right to life, liberty and security of person.
  • No one shall be held in slavery or servitude; slavery and the slave trade shall be prohibited in all their forms.

Purpose: Anti-theft

khfoiz8h eoizfam uobgiu m5zegouzehgo auz h oifnlzenf5 ouibgz"uo nbuo7dhf ozng h jpi7nfié'"(y onegf gçéh jgn z7lorh àg&pi hjbg çb " hp5oàj gfà y'" uhe8lzh gàçé"4

Do not drink Coca Cola!

geqoh5* feY7$ RTHR8

erhbse7'_& ugsk,/ 8zsgzoiç& 854ev_=6rt 8ç="1dqf 2g5ite.0d8!

  • Protect the privacy
  • Protect data
  • Prevent counterfeiting

(confidentiality, integrity)

Nowadays

Only few are secured!

Bad idea:

Automatic Gas Station Payment

Cryptographic Protocol

13

Lightweight Cryptography

for Passive RFID Tags

  • Key Agreement/Establishment

  • Entity (Mutual) Authentication

  • Symmetric/Asymmetric Encryption

  • Non-Repudiation methods

Keyed Hash Functions (MAC)

Symmetric Key Ciphers

Re-encryption

Passwords

One-time Pads

12

11

26

How to contribute ?

Block

Ciphers

Stream

Ciphers

8

7

  • A5/1 - A5/2 (GSM)
  • E0 (Bluetooth)
  • Grain
  • ...
  • (Triple) DES
  • AES
  • RC5
  • ...

29

28

25

Engineers

Researchers

1,000+

Applications

100+

Security protocols

24

  • Luggage Monitoring
  • Access Control
  • Ticketing
  • Tolls
  • Citizen Identification
  • Retailing

?

  • Tea
  • Present
  • DESL
  • Print
  • A2U2
  • Grain
  • Squash

adio

Active Tags

1$ to 50$

R

F

ID

requency

entification

  • Battery powered
  • Can initiate communications (long range ~100m)
  • Examples: Valuable Stock monitoring, car parks & highways tolls, building access control, Patient monitoring & localization

Propose a comparison of security primitives

based on applications requirements

A2U2

Ultra Lightweight Protocol

A Stream Cipher for Printed Electronics RFID Tags

15

Results

Motivations

Semi-Active Tags

Methodology

50¢ to 5$

"objects equipped with micro electronics that can process data automatically"

Why A2U2?

Area

in Gates Equivalent

Aim

  • Design a cipher for Printed Electronics RFID Tags

Never done before!

Randomness

Block

Ciphers

Stream

Ciphers

Area

  • KATAN
  • Shrinking Generator
  • Main challenge: Area

Design a Simple & Secure Authentication Protocol

Computer

Security Protocols

20,000+ GE

Low-cost Passive RFID Tag

Security Protocols

> 2,000 GE

  • Simulated in C programming language.

  • The generated Keystream sequences succeed in all the randomness tests of the NIST Suite.

Printed Electronics RFID Tags

Security Protocols

> 200 GE

41

42

Mathematical Properties

40

1,000,000 bits recommended,

10,000,000 bits tested.

43

  • Learning from previous designs and reuse of good concepts

  • Use of maximal lengths primitive polynomial functions

  • Use of well designed nonlinear Boolean functions

  • Use of Shannon's concepts on Confusion and Diffusion

  • Use of short-lenghts elements to optimize area.

30 % less than PRINT.

39 % less than KATAN.

78 % less than GRAIN.

  • Battery powered - often implemented together with sensors
  • Can't initiate communications (long range ~100m)
  • Examples: Cold Chain Monitoring, Military, Environment Monitoring

Against the most

common attacks

Using only basic

logic components

56

Why a Stream Cipher?

Authentication

Server Reader

European Commision

Throughput

Strenghts:

Cryptographic Protocol

  • XOR
  • AND
  • NOT

Background Study

at 100 kHz

Security Protocols applied to RFID tags

Classify Lightweight

Cryptography

Implementation Guideline

  • Faster / "On the fly" Encryption

  • More compact

  • Lack of stream ciphers in the litterature
  • Extremely low area: Implementable in resources-constrained devices.

  • Security improved by the lack of long sequences of ciphertext.
  • Eavesdropping
  • Relay Attack
  • Tracking
  • Replay Attack
  • De-synchronization attack
  • Disclosure attack
  • Forward Secrecy

4

  • Key Agreement/Establishment

  • Entity (Mutual) Authentication

  • Symmetric/Asymmetric Encryption

  • Non-Repudiation methods

Weaknesses:

45

39

300 % faster than KATAN.

700 % faster than PRINT.

  • > 200 GEs
  • Not provably secure

57

Methodology

55

Implementation

Theory

Encryption

&

  • Cryptography is an iterative process

  • Analysis of previous authentication protocols

Decryption

Authentication

Tag Reader

Back to the Future

of A2U2

Passive Tags

1¢ to 2$

  • EMAP, M²AP, LMAP
  • SASI

Encryption

...20¢

Authentication

Reader Tag

33

  • Implementation

(collaboration with Lund University)

Low-cost Passive RFID Tags

Number of transistors on the tag (10,000+ Gates)

130nm low-leakage standard cell library:

Decryption

Power Consumption: 135nW at 100 kHz

Area: 226 Gates Equivalent

Update

~ 2000 Gates for security

Element of measure of electronic implementation size

5

Security Design

A2U2 overview

20% < estimation

(284 GE)

Update

Design an

Authentication

Protocol

Design a

Cipher

  • No Battery
  • Can't initiate communications (Short Range ~ max. 10m)
  • Examples: Everyday items labels, cinema tickets, ePasseport

Conclusions

60

34

A2U2 Improvements

  • Presented in June 2009, with the belief of security.

Key Scheduling Mechanism

  • Cryptanalysis

Reduction to 7 bits to save Gates.

  • Key extended from 56 to 81 bits

+ 7 extra bits reserved for the counter.

  • k1 is updating the counter

instead of the NFSR.

(collaboration with DTU)

7

  • Inspired by the KATAN Cipher.

  • Period of 2 -1 with the polynomial function.

  • 5 bits initialised with 2 Pseudo-Random Numbers and the Secret Key (2 remaining bits set to 1 and 0).

  • Determines when the output sequence starts.

Electronicians

Mathematicians

47

Benefits

Increases the complexity of both Guess-and-determine attack and Master key bit recovery attack

Cipher fully broken

  • The authentication protocol got fully broken in June 2010,

by Hernandez-Castro, Peris-Lopez et al.

Counter

  • Chosen plaintext attack
  • initialized with "1s" instead of the 5 extra key-bits
  • counter value replaced by the 7 extra bits

after initialization

  • k1 added to the feedback function.

Security Check

49

Benefits

  • A guess-and-determine attack

Eliminates the Counter key bit recovery attack

(complexity 2 )

NFSRs

  • initialized only with the key and the tag random number

Extra Cost

  • Counter key bits recovery attack

Reasons

Benefits

  • A few Gates of combinational logic
  • Additional space in memory to store the key bits

Eliminates the Chosen plaintext attack

38

(complexity 2 )

  • 56-bits key.

  • 5 new key-bits loaded to the buffer each clock cycle, with 1 input bit from the NFSR.

  • k1 injected as an irregular bit into the nonlinear Boolean Function

Increases considerably the period of k

1

  • Master key bits recovery attack

62

51

Reduction to 17 and 9 bits NFSR to save Gates.

  • Inspired by the KATAN Cipher.

  • Initialised with 2 Pseudo-Random Numbers and the Secret Key

  • Updated with 2 Boolean Functions,

with algebraic degree 3.

Balanced, High Nonlinear degree

should use non-triangular functions (e.g. Rotation)

49

59

  • Too simple operations

  • Secret values (A, B, D, E and F) are too correlated

Encryption

  • Remove "buffer" and "interleaved sequence" issues.
  • Irregular lenghts of ciphertexts for identical plaintext.

leaking information

  • Inspired by the Shrinking Generator.

Improvements:

  • Input (I) & Selector (S) bits are the result of the nonlinear Boolean functions

  • Approximately half the ciphertext contains relevant information (plaintext)
  • Plaintexts bits uniformly and randomly distributed in ciphertext.

53

Lots of people

working in cryptography

have no deep concern

with real application issues.

They are trying to discover

things clever enough

to write papers about.

  • Eavesdropping
  • Disclosure attack
  • Forward Secrecy

Assumptions

40

Thanks to this work...

This attack requires 2 bits of plaintext/ciphetext and can be performed with time complexity 2 .

38

40

2

~1.1 trillion bits

Whitfield Diffie

72 years

  • New attack against authentication protocols (TANGO)

4

18

Authentication

Compare

the primitives

Propose a

Metric to help

RFID Practitioner

  • Relay Attack
  • Replay Attack
  • De-synchronization attack

Analysis & Innovation

46

A2U2

Updates

Approximations of secret values

transmitted over the radio channel

  • Tracking
  • Forward Secrecy

Tango recovers 95% of the secret values bits in 10 sessions

35

36

17

20

21

16

CONCLUSIONS

PRIMITIVES

COMPARISON

Conclusions

Main contributions

Power Comparison

0,18µm

0,35µm

0,18µm

0,13µm

Tea

Grain

most commonly used process for low-cost passive RFID tags

  • 39 µW
  • 230 kHz
  • 0.35µm
  • 3.3V
  • 3.3 µW
  • 100 kHz
  • 0.13µm
  • 1.2V

?

Comparison Parameters

C'est

la vie!

Two security systems have been broken...

... but this is part of the game.

69

70

@ 1MHz

@ 100kHz

Implementation Parameters

Power dissipation (in CMOS devices)

Technology

dependent

Power dissipation (in CMOS devices)

Publication:

  • Providing strong Security and high privacy in low-cost RFID networks

< 30µW

< 3µW

0.35µm 0.18µm

> 90%

< 10%

< 1%

10 ~ 30%

< 10%

60 ~ 80%

0.13µm 0.18µm

  • TANGO
  • Extremely small cipher for very resources limited devices

Simulation dependant

Process dependant

Operating Frequency

Total leakage current

> 40 kbits/s

> 4 kbits/s

Gate capacitance

Design dependant

Input Voltage

Bubbles size

Switching probability of a gate

  • Ultra-lightweight Authentication Protocol

  • Compact Stream Cipher for Printed Electronics

  • A metric that eases the selection of security protocols for RFID applications integrators.

Throughput

vs.

Quantity of charge carried by the short-circuit current during transitions

Area

=

Efficiency

  • Power

  • Throughput

  • Area

  • Security

Publications:

  • A2U2 : A Stream Cipher for Printed Electronics RFID Tags
  • Cryptanalysis of the Light-Weight Cipher A2U2

Finally a way to compare cipher performances !

71

< 2000 GE

67

Theoretical Parameters

Bubbles size

Power

Area

?

  • hard to compare attacks
  • secure today... but tomorrow?

Metric could really be useful for RFID practitioners

=

Efficiency

+

Publication:

  • Lightweight Cryptography: Classification and Evaluation

66

72

Power vs. Area

Throughput vs. Area

80

81

WOOPT

Power

Area

Throughput

in one single metric

eighted

Cumulative Distribution Function

rmalized

n

[0;1]

c

st

W

O

O

P

T

73

Throughput

ower

value

44.4 kbps for DESL

30 kbps

targeted design value

hroughput

2 kbps vs. 20 kbps

acceptable margin

F(x) = 0.70

F(x) = 0.96

Acknowledgments

74

75

A simple example...

A ticketing application

for bus access

Requirements:

(margin 10 Gates)

the thinner the margin,

the higher the weight.

  • Area: Max. 1500 Gates

  • Throughput: 64 kbps

  • Power: 5 µW

(margin 10 kbps)

76

(margin 4 µW)

  • Prof., Dr., Techn., ... Torben Larsen for believing in me.

  • Dr. Damith Ranasinghe for giving me the best supervision I could imagine.

  • Prof. Gildas Avoine, Dr. Pedro Peris-Lopez and Assoc. Prof. Petar Popovski for accepting to be part of my committee

  • Børge Lindberg, Bernard Fleury, and Søren H. Jensen for giving me a 2nd

chance to finish my PhD.

  • All the colleagues who collaborated with me in this Thesis.

  • All my family and friends who supported me for the past... many years!

real

77

82

Writing a thesis is a bit like running a Marathon.

It is really painful but once you are done, it feels so good.

Learn more about creating dynamic, engaging presentations with Prezi