titre de la présentation

Size: px

Start display at page:

Download "titre de la présentation"

ぜんまもてぎ
4 years ago
Views:

1 Low Cost Cryptography Matt Robshaw Orange Labs France Orange Labs

2 Cryptography in a Nutshell Cryptography provides the foundation to many security solutions Algorithms can be divided into two classes Symmetric: participants share the same key material Asymmetric: participants use different key material You can (almost) do everything you want with either The important differences are in the supporting infrastructure This can make one type more suitable than another Low Cost Cryptogrpahy Matt Robshaw (2) Orange Labs

3 Low Cost Applications There is much interest in low cost cryptography RFID tags, sensor networks, ubiquitous computing We might want to authenticate a device; e.g. anti-cloning in an RFID tag We might want to authenticate information between devices; e.g. information sent from sensor tags We are probably less interested in encryption There may be specific issues; e.g. re-keying Low Cost Cryptogrpahy Matt Robshaw (3) Orange Labs

4 Cryptographic Performance In general we rarely care about performance But it is important for restricted hardware applications What do we mean by performance? Speed of operation? Speed of operation with different keys? Physical space in hardware? Power consumption? "Is this algorithm the best?" not a good question A better question is "Is this algorithm good enough?" e.g. 12% faster than the AES is probably not that interesting Low Cost Cryptogrpahy Matt Robshaw (4) Orange Labs

5 Requirements For low-cost applications we're interested in a small footprint in hardware a low average and peak power consumption Often we are willing to make some compromises we might be willing to sacrifice speed up to some limit we might be willing to trade security e.g operations is probably reasonable Low Cost Cryptogrpahy Matt Robshaw (5) Orange Labs

6 Space Requirements The space depends on the "state" and the "operations" The size of the state depends on the security level Block cipher: n-bit block leads to 2 n/2 distinguishing attack Stream cipher: n-bit state leads to 2 n/2 state recovery attack There are various Time/Memory/Data trade-offs Operations (and hence algorithm implementations) can be compared using the notion of gate equivalents (GE) Low Cost Cryptogrpahy Matt Robshaw (6) Orange Labs

7 Disclaimer Performance figures in this presentation are indicative! Hardware implementations can explore many trade-offs Implementations may use different technologies and be optimised with regards to different metrics However, the general capabilities of an algorithm (and its class/type) should be reasonably apparent Low Cost Cryptogrpahy Matt Robshaw (7) Orange Labs

8 Block Ciphers Can be used for authentication or encryption Device authentication via a challenge-response protocol Data authentication via a MAC Data encryption in some encryption mode The state-of-the-art is very advanced Low Cost Cryptogrpahy Matt Robshaw (8) Orange Labs

9 Relative Sizes (encrypt-only) GE Key Size Block Size KASUMI AES HIGHT mcrypton DES SEA DESXL TEA XTEA PRESENT Low Cost Cryptogrpahy Matt Robshaw (9) Orange Labs

10 PRESENT (CHES 2007) Collaborative design between FTRD, DTU, and Bochum Designed from scratch to be hardware-efficient Based on the design of Serpent The most hardware efficient of the AES finalists SPN (substitution-permutation-network) Very simple design that allows Good implementation trade-offs Basic, but sound, security assessment Low Cost Cryptogrpahy Matt Robshaw (10) Orange Labs

11 PRESENT (CHES 2007) Low Cost Cryptogrpahy Matt Robshaw (11) Orange Labs

12 PRESENT (CHES 2007) The breakdown of space requirements is as follows GE % GE % Data state KS state S-layer KS S-box P-layer 0 0 KS Rotation 0 0 Counter: state KS Counter xor Counter: combin Other Key xor Low Cost Cryptogrpahy Matt Robshaw (12) Orange Labs

13 PRESENT (CHES 2007) The 4-bit S-box can be implemented in 28 GE Satisfies good cryptographic properties Compare to 4-bit S-box in mcrypton which requires 107 GE AES S-box requires 395 GE (Anubis S-box requires 120 GE) Basic differential or linear cryptanalysis needs > 2 64 text Algebraic attacks a potential concern PRESENT consists of 11,067 quadratic equations in 4,216 variables Small-scale experiments quickly run out of memory and time Low Cost Cryptogrpahy Matt Robshaw (13) Orange Labs

14 Block / Stream Ciphers Are stream ciphers necessarily more compact than block ciphers? Low Cost Cryptogrpahy Matt Robshaw (14) Orange Labs

15 Stream Ciphers The reputation of stream ciphers is that they are faster and lighter than block ciphers Commercially, stream ciphers are widely used Many proprietary designs consist of shift register arrays These can lend themselves to efficient implementation However the stream ciphers in general use are large The estream project is attempting to address this Low Cost Cryptogrpahy Matt Robshaw (15) Orange Labs

16 estream estream is a multi-year project to promote stream cipher research Submissions were invited for two profiles 1. Fast performance in software 2. Resource-efficient in constrained hardware environments We are now in the last year with the 34 original entries reduced to eight in each profile Low Cost Cryptogrpahy Matt Robshaw (16) Orange Labs

17 estream The final eight Profile 2 (hardware) candidates are DECIM v2 Edon-80 F-FCSR-H v2 Grain v1 MICKEY v2 MOUSTIQUE POMARANCH v3 Trivium Low Cost Cryptogrpahy Matt Robshaw (17) Orange Labs

18 Relative Sizes (rough guide in GE) GE Notes SNOW ISO standardised RC Widely used (e.g. TLS) A5/ Ill-fated GSM encryption algorithm QUAD 3700 Some element of provable security DECIM v estream (Profile II) Edon estream (Profile II) F-FCSR-H 3200 estream (Profile II) Grain v estream (Profile II) MICKEY v estream (Profile II) POMARANCH v estream (Profile II) Trivium 1500 estream (Profile II) Low Cost Cryptogrpahy Matt Robshaw (18) Orange Labs

19 Asymmetric Algorithms Generally speaking asymmetric cryptography is heavier than symmetric cryptography "Anyway, public-key cryptography is too heavy to be implemented within low cost tags. Thus we only deal with tags [ ] capable of using symmetric cryptography." [Avoine, 2005] However the GPS identification scheme shows that this is not necessarily the case Low Cost Cryptogrpahy Matt Robshaw (19) Orange Labs

20 Relative Sizes (rough guide in GE) GE Cycles Notes ECC (p 166 ) ECC ( p 192 ) ECC (p 100 ) ECC (2 67 ) For use in EC Schnorr ID NTRU (encrypt) GPS ID scheme Uses coupons Excellent article at Complete on-tag GPS has been realised in 2000 GE Low Cost Cryptogrpahy Matt Robshaw (20) Orange Labs

21 GPS Identification Scheme Due to Girault, Poupard, and Stern ISO Standardised Also listed in the final NESSIE portfolio Can be based on RSA-like moduli or ECC There is a wide range of optimisations In the most interesting embodiment we use coupons With coupons the on-tag computation is an integer addition Low Cost Cryptogrpahy Matt Robshaw (21) Orange Labs

22 GPS in Practice Secret key s TAG READER Public key V = -sg Choose r Compute x = hash(rg) x c Choose c Compute y = r + sc verify x = hash( yg + cv) Low Cost Cryptogrpahy Matt Robshaw (22) Orange Labs

23 GPS in Practice Choose r i Compute x i = hash(r i G) Store coupon (r i, x i ) Secret key s TAG READER Public key V = -sg Choose coupon (r i, x i ) x i c Choose c Compute y = r i + sc verify x i = hash( yg + cv) Low Cost Cryptogrpahy Matt Robshaw (23) Orange Labs

24 GPS Computation Use Advanced Encryption Standard (AES) as a benchmark Space Current Time Time (Gates) (μamps) (Clock cycles) (Seconds) AES ms GPS ms GPS (LHW) ms GPS (LHW) ms change the clock frequency Low Cost Cryptogrpahy Matt Robshaw (24) Orange Labs

25 GPS Ongoing Work Implementation requires additional memory and logic Fully-functioning variants require around 2000 GE The use of coupons has an impact on the applications This requires a limited number of uses per tag Compatible with many RFID-applications: use infrequently and throw away Low Cost Cryptogrpahy Matt Robshaw (25) Orange Labs

26 Fundamental Issues (1) Do we need security? Do we need cryptographic security? EPCglobal develops industry standards The kill command renders the tag inoperable Many security threats are prevented; e.g. tracking a tag Other security features include strong audit trails For many applications basic solutions are sufficient! But not all Low Cost Cryptogrpahy Matt Robshaw (26) Orange Labs

27 Fundamental Issues (2) What about Moore's Law? The number of transistors at minimum component cost doubles roughly every 18 months A relaxed version might be every two years Will Moore's Law come to our aid? Low Cost Cryptogrpahy Matt Robshaw (27) Orange Labs

28 Fundamental Issues (2) GE Threshold GE for most crypto Target GE today Year Moore's Law Relaxed Moore's Law Low Cost Cryptogrpahy Matt Robshaw (28) Orange Labs

29 Fundamental Issues (2) There are two schools of thought #1: There will always be a need for the cheapest, smallest solution #2: Provided the price / functionality of a "large" solution is acceptable, there will be no need to take a smaller one Low Cost Cryptogrpahy Matt Robshaw (29) Orange Labs

30 Summary (rough guide in GE) SNOW 2.0 AES RC4 DES Established Stream Ciphers Established Block Ciphers Dedicated stream ciphers estream Dedicated block ciphers Various sources SHA WPI SHA MD5 [MD4] 8001 [7350] TU Graz ECC k Various sources GPS 2000 FTRD Low Cost Cryptogrpahy Matt Robshaw (30) Orange Labs

31 Conclusions New application areas bring new security challenges Low cost cryptography is a very active research area Contrary to popular belief, stream ciphers are not intrinsically better-suited than block ciphers Contrary to popular belief, there are public key techniques that are suitable for constrained environments Low Cost Cryptogrpahy Matt Robshaw (31) Orange Labs

(Requirements in communication) (efficiently) (Information Theory) (certainly) (Coding Theory) (safely) (Cryptography) I 1

(Requirements in communication) (efficiently) (Information Theory) (certainly) (oding Theory) (safely) (ryptography) I 1 (Requirements in communication) (efficiently) (Information Theory) (certainly) (oding