1 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Servicios de seguridad en ambientes computacionales altamente restringidos Francisco Rodríguez-Henríquez CINVESTAV-IPN Depto. de Ingeniería Eléctrica Sección de Computación

2 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Antecedents and Motivation

3 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Security Systems by layers Computer Arithmetic : Addition, Squaring, multiplication, inversion and exponentiation Public Key Crypto Algorithms: RSA, ECC Symmetric Crypto Algorithms: AES, DES, RC4, etc. Public Key Crypto Algorithms: RSA, ECC Symmetric Crypto Algorithms: AES, DES, RC4, etc. Crypto User Functions: Encrypt/Decrypt, Sign/verify Crypto User Functions: Encrypt/Decrypt, Sign/verify Security Services: Confidentiality, Data Integrity, Data Authentication, Non-Repudiation Communication Protocols : SSL, TLS, WTLS, WAP, etc. Applications: Secure e-mail, Digital Money, Smart Cards, Firewalls, etc.

4 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Security Services Confidentiality- protect info value Authentication- protect info origin (sender) Identification- ensure identity of users Integrity- protect info accuracy Non-repudiation - protect from deniability Access control - access to info/resources Availability - ensure info delivery

5 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Some Practical Applications "Any sufficiently advanced technology is indistinguishable from magic.” Arthur C. Clarke. secure mail secure communications network authentication electronic voting electronic notary digital money (digital wallet) data distribution

6 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Characteristics of Traditional IT Applications Mostly based on interactive (= traditional) computers „One user – one computer“ paradigm Static networks Large number of users per network Q: How will the IT future look?

7 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez The IT Future Bridge sensors Cleaning robots Car with various IT services Networked robots Smart street lamps Pets with electronic sensors Smart windows

8 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Characteristics of Ubiquitous Computing Systems Embedded nodes (no traditional computers) Connected through wireless, close-range network (“Pervasive networks”)! Ad-hoc networks: Dynamic addition and deletion of nodes Power/computation/memory constrained! Vulnerable

9 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Examples for Ubiquitous Computing PDAs, 3G cell phones,... Living spaces will be stuffed with nodes So will cars Wearable computers (clothes, eye glasses, etc.) Household appliances Smart sensors in infrastructure (windows, roads, bridges, etc.) Smart bar codes (autoID) “Smart Dust”...

10 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Security and Economics of Ubiquitous Computing „One-user many-nodes“ paradigm (e.g. 10 2 -10 3 processors per human) Many new applications we don‘t know yet Very high volume applications Very cost sensitive People won‘t be willing to pay for security per se People won‘t buy products without security

11 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Where are the challenges for embedded security? Designers worry about IT functionality, security is ignored or an afterthought Attacker has easy access to nodes Security infrastructure (PKI etc.) is missing: Protocols??? Side-channel and tamper attacks Computation/memory/power constrained

12 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Will that ever become reality?? We don’t know, but: CPUs sold in 2000

13 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Implementation Platforms

14 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Platforms Cryptographic algorithms can be implemented through  Software  ASIC  FPGAs Choice of platform depends upon  Algorithm performance  Cost  Flexibility

15 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Platform Implementation for Cryptographic Algorithms Software General purpose  Procs, Embedded  Procs, etc. General purpose  Procs, Embedded  Procs, etc. Cryptographic Algorithms Classic HardwareReconfigurable HW FPGAs VLSI ASIC chips

16 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Platform Comparison ASIC Processor Reconfigurable Hardware Performance Flexibility Unit Cost Development Cost

17 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Platform Features  Software  Maximum flexibility  Low Performance  Low cost  ASIC  High performance  No flexibility at all  High cost  FPGAs  Reasonable flexibility  Low cost  High performance

18 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Why Crypto-algorithms in Hardware Two main reasons: 1.Software implementations are too slow for some applications (symmetric alg: encryption rates 100 Mbit/sec public-key alg: > 10 msec) 2.Hardware implementations are intrinsically more physically secure: Key access and algorithm modication is considerably harder.

19 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez But why reconfigurable hardware? Potential advantages of crypto algorithms implemented on reconfigurable platforms: 1.Algorithm Agility 2.Algorithm Upgrade 3.Architecture Efficiency 4.Resource Efficient 5.Algorithm Modification 6.(Throughput relative to software) 7.(Cost Efficiency relative to ASICs)

20 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Crypto and FPGAs: Algorithm Agility Observation: Modern security protocols are defined to be algorithm independent: Encryption algorithm is negotiated on a per-session basis. Wide variety of ciphers can be required. Ex: IPsec- allowed algorithms: DES, 3DES, Blow-Fish, CAST, IDEA, RC4 and RC6, & future extensions! Same holds for public-key algorithms, e.g., Diffie- Hellman and ECDH. Recall that: ASIC solutions can provide algorithm agility only at high costs.

21 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Crypto and FPGAs: Algorithm Upgrade Applications may need upgrade to a new algorithm because: Current algorithms was broken (DES) Standard expired (again DES) New standard was created (AES) Algorithm list of algorithm independent protocol was extended Upgrade of ASIC-implemented algorithm is practically infeasible if many devices are affected or in applications such as satellite communications.

22 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Crypto and FPGAs: Architecture Efficiency In certain cases a hardware architecture can be much more efficient if it is designed for a specific set of parameters. Parameters for cryptographic algorithms can be for example the key, the underlying finite field, the coefficient used (e.g., the specific curve of an ECC system), and so on. Generally speaking, the more specific an algorithm is implemented the more efficient it can become.

23 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Crypto and FPGAs: Resource Efficiency Observation: The majority of security protocols uses private-key as well as public-key algorithms during one session, but not simultaneous. Same FPGA device can be used for both through run time reconguration.

24 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Crypto and FPGAs: Algorithm Modification Some applications require Public algorithms (such as AES candidates) with proprietary modules, e.g., proprietary S-boxes or permutations. Change of modes of operations (feedback modes, counter mode, etc.) Crypto-analytical implementation, such as key-search machines, may use slightly altered version of the algorithms. With FPGAs, these changes can readily be implemented.

25 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez FPGA: Field programmable Gate Arrays

26 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Configurable Logic Block Logic Mode Combinational Logic Combinational Logic 1-bit reg 1-bit reg 16x1 RAM 4 16x1 RAM 4 1-bit reg 1-bit reg Memory Mode 4 4

27 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Virtex-II Pro Feature/Product XC 2VP2 XC 2VP4 XC 2VP7 XC 2VP20 XC 2VP30 XC 2VP40 XC 2VP50 XC 2VP70 XC 2VP100 XC 2VP125 EasyPath cost reduction---- XCE 2VP30 XCE 2VP40 XCE 2VP50 XCE 2VP70 XCE 2VP100 XCE 2VP125 Logic Cells3,1686,76811,08820,88030,81643,63253,13674,44899,216 125,136 Slices1,4083,0084,9289,28013,69619,39223,61633,08844,096 55,616 BRAM (Kbits)2165047921,5842,4483,4564,1765,9047,992 10,008 18x18 Multipliers12284488136192232328444 556 Digital Clock Management Blocks 4448888812 Config (Mbits)1.313.014.498.2111.3615.5619.0225.633.6542.78 PowerPC Processors 011222222 4 Max Available Multi-Gigabit Transceivers* 4488812*16*2020*24* Max Available User I/O*2043483965646448048529961164 1200 http://www.xilinx.com/products/tables/fpga.htm#v2p 1 Logic Cell = (1) 4-input LUT + (1) FF + (1) Carry Logic 1 CLB = (4) Slices

28 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Wireless Ad-Hoc Network

29 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Smart Cards

30 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Smart Cards

31 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Smart Cards

32 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Smart Cards

33 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez S D Multi-hop cellular Set of base stations connected to a backbone (like in cellular) Potentially, multi-hop communication between the mobile station and the base station (unlike in cellular)

34 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Advantages: –Energy consumption of the mobile stations can be reduced –Immediate side effect: Reduced interference –Number of base stations (fixed antennas) can be reduced –Coverage of the network can be increased –Closely located mobile stations can communicate independently from the infrastructure (ad hoc networking) Disadvantages: –Routing? –Synchronization? Multi-hop cellular

35 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez A model Multi-hop up-link Single-hop down-link Problem: How to encourage the nodes to relay packets for the benefit of other nodes? S D

36 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Where are the challenges for embedded security? Designers worry about IT functionality, security is ignored or an afterthought Attacker has easy access to nodes Security infrastructure (PKI etc.) is missing: Protocols??? Side-channel and tamper attacks Computation/memory/power constrained

37 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Why do constraints matter? Almost all ad-hoc protocols (even routing!) require crypto ops for every hop At least symmetric alg. are needed Asymmetric alg. allow fancier protocols Question: What type of crypto can we do?

38 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Security on Different Embedded Processors

39 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Classification by Processor Power Very rough classification of embedded processors Class speed : high-end Intel Class 0: few 1000 gates ? Class 1: 8 bit  P,  10MHz  1: 10 3 Class 2: 16 bit  P,  50MHz  1: 10 2 Class 3: 32 bit  P,  200MHz  1: 10

40 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Case Study Class 0: RFID

41 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Case Study Class 0: RFID Recall: Class 0 = no  P, few 1000 gates Goal: RFID as bar code replacement Cost goal 5 cent (!) allegedly 500 x 10 9 bar code scans worldwide per day (!!) AutoID tag: security “with 1000 gates” [CHES 02] –Ell. curves (asymmetric alg.) need > 20,000 gates –DES (symmetric alg.) needs > 5,000 gates –Lightweight stream ciphers might work

42 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez RFIDs Applications Expired Milk Reported Within two decades, the minuscule transmitters are expected to replace the familiar product bar codes Alerting consumers help you manage your inventory a lot better tell you that a prescription is in the waiting bin provide details to marketers about a family's eating the technology raises privacy concerns

43 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Status Quo: Crypto for Class 1 Recall: Class 1 = 8 bit  P,  10MHz Symmetric alg: possible at low data rates Asymm.alg: very difficult without coprocessor

44 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Status Quo: Crypto for Class 2 Recall: Class 2 = 16 bit  P,  50MHz Symmetric alg: possible Asymm.alg: possible if carefully implemented, and algorithms carefully selected (ECC feasible; RSA & DL still hard)

45 Seguridad en Sistemas de Información Verano 2004 Francisco Rodríguez Henríquez Status Quo: Crypto for Class 3 Recall: Class 3 = 32 bit  P,  200MHz Symmetric alg: possible Asymm.alg: full range (ECC, RSA, DL) possible, some care needed for implementation