Low Cost Cryptography Matt Robshaw Orange Labs France 13.06.07 Orange Labs
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
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
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
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. 2 80 operations is probably reasonable Low Cost Cryptogrpahy Matt Robshaw (5) Orange Labs
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
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
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
Relative Sizes (encrypt-only) GE Key Size Block Size KASUMI 6000 128 64 AES 3600 128 128 HIGHT 3048 128 64 mcrypton 2500 128 128 DES 2300 56 64 SEA 2280 80 64 DESXL 2168 184 64 TEA 2100 128 64 XTEA 2000 128 64 PRESENT 1570 80 64 Low Cost Cryptogrpahy Matt Robshaw (9) Orange Labs
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
PRESENT (CHES 2007) Low Cost Cryptogrpahy Matt Robshaw (11) Orange Labs
PRESENT (CHES 2007) The breakdown of space requirements is as follows GE % GE % Data state 384 24.5 KS state 480 30.6 S-layer 448 28.6 KS S-box 28 1.8 P-layer 0 0 KS Rotation 0 0 Counter: state 28 1.8 KS Counter xor 13 0.9 Counter: combin Other 12 4 0.8 0.2 Key xor 171 10.9 Low Cost Cryptogrpahy Matt Robshaw (12) Orange Labs
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
Block / Stream Ciphers Are stream ciphers necessarily more compact than block ciphers? Low Cost Cryptogrpahy Matt Robshaw (14) Orange Labs
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
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
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
Relative Sizes (rough guide in GE) GE Notes SNOW 2.0 7000 ISO standardised RC4 12000 Widely used (e.g. TLS) A5/1 1000 Ill-fated GSM encryption algorithm QUAD 3700 Some element of provable security DECIM v2 3000 estream (Profile II) Edon-80 2900 estream (Profile II) F-FCSR-H 3200 estream (Profile II) Grain v1 1300 estream (Profile II) MICKEY v2 3400 estream (Profile II) POMARANCH v3 3300 estream (Profile II) Trivium 1500 estream (Profile II) Low Cost Cryptogrpahy Matt Robshaw (18) Orange Labs
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
Relative Sizes (rough guide in GE) GE Cycles Notes ECC (p 166 ) 30300 638000 ECC (2 191 + p 192 ) 23000 459000 ECC (p 100 ) 18700 205000 ECC (2 67 ) 2 13000 418000 For use in EC Schnorr ID NTRU (encrypt) 3000 30000 GPS ID scheme 300-1000 100 1000 Uses coupons Excellent article at http://eprint.iacr.org/2006/227.pdf Complete on-tag GPS has been realised in 2000 GE Low Cost Cryptogrpahy Matt Robshaw (20) Orange Labs
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
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
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
GPS Computation Use Advanced Encryption Standard (AES) as a benchmark Space Current Time Time (Gates) (μamps) (Clock cycles) (Seconds) AES 3595 8.15 1016 102 ms GPS 1541 3.07 802 80 ms GPS (LHW) 317 0.61 1088 109 ms GPS (LHW) 317 3.05 1088 21 ms change the clock frequency Low Cost Cryptogrpahy Matt Robshaw (24) Orange Labs
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
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
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
Fundamental Issues (2) 35000 30000 25000 20000 GE 15000 10000 5000 0 Threshold GE for most crypto 2006 2007 2008 2009 2010 2011 2012 Target GE today Year Moore's Law Relaxed Moore's Law Low Cost Cryptogrpahy Matt Robshaw (28) Orange Labs
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
Summary (rough guide in GE) SNOW 2.0 AES 7000 3600 RC4 DES 12000 2300 Established Stream Ciphers Established Block Ciphers Dedicated stream ciphers 1300-2500 estream Dedicated block ciphers 1500-2500 Various sources SHA-1 4276 WPI SHA-256 10900 MD5 [MD4] 8001 [7350] TU Graz ECC 12000 30k Various sources GPS 2000 FTRD Low Cost Cryptogrpahy Matt Robshaw (30) Orange Labs
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