1 Practical Aspects of Modern CryptographyFall 2016 Josh Benaloh Tolga Acar November 8, 2016 Practical Aspects of Modern Cryptography

2 What is Money? 106 billion people lived 94% are deadMost of the world’s wealth made after 1800 Why The Great Divergence of wealth? Reached its Zenith in 1970ies “Because laws and rules invented by reason”, Ibrahim Muteferrika, Rational Bases for the Politics of Nations, 1731 It is not geography, not national character Experiment 1: Germany: Trabant vs. Mercedes Benz Experiment 2: Korea: Even bigger divergence Adam Smith, Wealth of Nations, 1776 November 8, 2016 Practical Aspects of Modern Cryptography

3 EMV www.EMVCo.com: Europay, MasterCard, Visa, first in 1996AmEx, Discover, JCB, and UnionPay became members Over 2B active chips in use (debit + credit) 35M EMV acceptance terminals as of Q4 2013 Payment application in Smart Card (chip) Mobile application Wearables Some other personal device Secure chip provides Perform processing functions Store confidential information Perform cryptographic operations November 8, 2016 Practical Aspects of Modern Cryptography

4 EMV – Why and What Contact or contactless payments Why EMV?Physical contact with the reader Reader proximity, max 4cm Why EMV? Improve security for face-to-face payments by reducing fraud from counterfeit and lost/stolen cards What does it do? Authentication of the chip card to reduce counterfeit fraud (online/offline tx) Risk management parameters to the issuer for online/offline transactions Transaction integrity via signed transactions Cardholder verification methods to protect against lost/stolen card November 8, 2016 Practical Aspects of Modern Cryptography

5 Magnetic Stripe TracksPAN, Name, Expiry Date, Service Code, PVV/CVV, LRC Track 2, developed by ABA PAN, Expiry Date, Service Code, PVV/CVV, LRC Track 3 – Unused LRC - Longitudinal Redundancy Check Parity check to detect errors POS Terminals read track 1 or track 2 – not track 3 November 8, 2016 Practical Aspects of Modern Cryptography

6 Card Skimming Source: arstechnica.com November 8, 2016Practical Aspects of Modern Cryptography

7 EMV - Brief History Plastic Cards 1950 Magnetic Cards 1970 Chip card patent 1974 uP chip card invention 1977 Commercial smart cards 1979 French chip card rollout 1984 EMV 1996 EMVCo established 1999 CCPS: Contactless Comm. Protocol Spec. (L1) 2007 Contactless protocol 2008 Tokenization 2014 November 8, 2016 Practical Aspects of Modern Cryptography

8 EMV Usage ( ) November 8, 2016 Practical Aspects of Modern Cryptography

9 EMV – How It Works? Magnetic Stripe EMVCard is a data store read by the terminal Terminal performs all processing with the issuer/payment system EMV Chip stores and processes payment transaction with the terminal Online data authentication User PIN for cardholder identity verification Online authorization EMV Transactions: contact and contactless Liability Shift From issuers to acquirers and merchants November 8, 2016 Practical Aspects of Modern Cryptography

10 EMV - Cryptograms Application Cryptograms: generated using 2-Key 3DES cryptography (*) ARQC: Authorization Request Cryptogram (online authorization request) TC: Transaction Certificate (chip signature over data for clearing and settlement) AAC: Application Authentication Cryptogram (declined transaction) Online card and issue authentication Chip generates ARQC, sent to the issuer Issuer verifies the ARQC Issuer may generate ARPC (Authorization Response Cryptogram) ARPC may be sent to the chip and verified for approval Data signing for transaction authentication ARQC: Online authorization request ARPC: online authorization response TC: approval message for clearing and settlement AAC: declines transactions TC: Application Cryptogram generated by the card when accepting a transaction. Hash of TDOL (Transaction Data Object List) CDOL: Card Risk Management Data Object List November 8, 2016 Practical Aspects of Modern Cryptography

11 EMV: Up and Coming Next Gen Chip Specifications Mobile techConsolidation across contact and contactless payment solutions ECC for public key cryptography Additional value-add data November 8, 2016 Practical Aspects of Modern Cryptography

12 Token Service ProviderEMV: Actors Cardholder Merchant Acquirer PAN, Token Token Token Token Service Provider Payment Network Issuer PAN, Token PAN, Token November 8, 2016 Practical Aspects of Modern Cryptography

13 EMV: Key Management (Book 2)Static Data Authentication (SDA) Digital signature generated on the terminal Relies on an offline CA that signs issuer public keys CA public keys are stored on terminals Detects unauthorized data alteration Terminals CA public keys per registered application provider identifier Key and algorithm identifiers for future expansion Dynamic Data Authentication ICC generated dynamic signature (unpredictable number) Combined DDA Signature includes AC November 8, 2016 Practical Aspects of Modern Cryptography

14 Card Authentication Done before any transactionSDA: Static Data Authentication Static Data Issuer Public Key Certificate Cleartext PIN DDA: Dynamic Data Authentication Dynamic Data ICC Public Key Certificate Static App Data Cleartext & Encrypted PIN CDA: Combined Data Authentication Combined Data Application Cryptogram Included in the signature Unpredictable number is signed November 8, 2016 Practical Aspects of Modern Cryptography

15 Cardholder VerificationOffline Separate PIN encryption certificate on the card ICC generates a random nonce; 64-bits long Terminal generates a nonce, pads message, encrypts with card’s public key ICC decrypts and validates the nonce ICC verifies the PIN Online Terminal sends encrypted PIN (2-Key 3DES) to the issuer Issuer verifies the PIN Where does the 3DES key come from? (HSMs to the rescue) https://crypto.stanford.edu/~dabo/courses/cs255_winter14/lectures/EMV.pdf November 8, 2016 Practical Aspects of Modern Cryptography

16 EMV: SDA Key Chain Issuer CA Static Application DataIssuer Private Key CA Private Key CA Public Key Signature Issuer Public Key Certificate Sign Sign Acquirer Terminal ICC November 8, 2016 Practical Aspects of Modern Cryptography

17 Cryptogram Data (minimum)Value Comments Source Amount, authorized Terminal Amount, other Terminal country code Terminal verification results Transaction currency code Transaction date 2 bytes Transaction type Unpredictable number 4 bytes Application Interchange Profile ICC Application Transaction Counter 2 byte Issue Application Data November 8, 2016 Practical Aspects of Modern Cryptography

18 A Few Attacks Unpredictable Number – too short? Paper Clip AttackHow about using a counter? 1,2,3,4,5, … Replay attack is easy to pull off Paper Clip Attack Snoop the communication channel between the card and the reader to sniff the PIN Insert a paper clip through a pinhole to tap into the POS board, circa 2008 Compromised card readers PINs were stolen, circa 2006 November 8, 2016 Practical Aspects of Modern Cryptography

19 I’d like to displace CVVCVV/CVC/CVV2/whatever – it is a static number It is a 3 decimal digit number, at most 4 digits for AmEx Calculation has been the same for 30 years from PAN, Expiry Date, Service Code CVV is a stand-in for card present state in online transactions What about good enough or better user authentication protocols? Instead of CVV In addition to CVV November 8, 2016 Practical Aspects of Modern Cryptography

20 EMV Symmetric Encryption AlgorithmsEncryption Mode of Operation: ECB or CBC Padding 𝑋: add ‘80’ and then as many ‘00’ Cryptogram computation with ECB 𝑌 𝑖 =𝐴𝐿𝐺 𝐾 𝑆 , 𝑋 𝑖 Cryptogram computation with CBC 𝑌 𝑖 =𝐴𝐿𝐺 𝐾 𝑆 , 𝑋 𝑖 ⊕ 𝑌 𝑖−1 , 𝑌 0 =00…00 Approved algorithms 3DES with 112-bit key in EDE construction AES, 128/192/256 bit key length SHA-1 November 8, 2016 Practical Aspects of Modern Cryptography

21 EMV Symmetric MAC Algorithms (DES)Use DES or Triple DES in CBC mode, perform CMAC Padding 𝑋: add ‘80’ and then as many ‘00’ Cryptogram computation, use CBC, ALG=3DES with a 112 bit key 𝐾 𝑆 Session key: 𝐾 𝑆 = 𝐾 𝑆𝐿 ││ 𝐾 𝑆𝑅 , 3DES key 𝐾= 𝐾 𝑆𝐿 ││ 𝐾 𝑆𝑅 ││ 𝐾 𝑆𝐿 𝑋= 𝑋 1 , 𝑋 2 ,…, 𝑋 𝐵 𝐻 𝑖 =𝐴𝐿𝐺 𝐾 𝑆𝐿 , 𝑋 𝑖 ⊕ 𝐻 𝑖−1 , 𝐻 0 =00…00 Algorithm 1: 𝐻 𝐵+1 = 𝐻 𝐵 Algorithm 3: 𝐻 𝐵+1 =𝐴𝐿𝐺( 𝐾 𝑆𝐿 , 𝐴𝐿 𝐺 −1 𝐾 𝑆𝑅 , 𝐻 𝐵 ) MAC 𝑆 is the most significant bytes of 𝐻 𝐵+1 X KSR DES-CBC KSL DES-ECB MAC November 8, 2016 Practical Aspects of Modern Cryptography

22 EMV Symmetric MAC Algorithms (AES)Use AES in CBC mode, perform CMAC Padding 𝑋: add ‘80’ and then as many ‘00’ Session Key 𝐾 𝑆 , Algorithm 5 (CMAC), ALG=AES 𝐶=00…87 𝐿=𝐴𝐿𝐺 𝐾 𝑆 , 𝐶 𝐾 1 =𝐿≪1, 𝐾 1 = 𝐾 1 ⊕𝐶 if MSB(L)=1 𝐾 2 = 𝐾 1 ≪1, 𝐾 2 = 𝐾 2 ⊕𝐶, if MSB(K1)=1 Cryptogram computation, use CBC 𝑋= 𝑋 1 , 𝑋 2 ,…, 𝑋 𝐵 𝑋 𝐵 = 𝑋 𝐵 ⊕ 𝐾 1 , if no padding 𝑋 𝐵 = 𝑋 𝐵 ⊕ 𝐾 2 , if padding was added 𝐻 𝑖 =𝐴𝐿𝐺 𝐾 𝑆 , 𝑋 𝑖 ⊕ 𝐻 𝑖−1 , 𝐻 0 =00…00 MAC 𝑆 is the most significant bytes of 𝐻 𝐵 November 8, 2016 Practical Aspects of Modern Cryptography

23 EMV Session Key Session keys 𝐾 𝑆 are derived from a unique master key 𝐾 𝑀 𝑅 is diversification data 𝐾 𝑆 =𝐹 𝐾 𝑀 , 𝑅 Session key derivation function 𝐹 (issuers may define their own) 𝑅= 𝑅 0 ││ 𝑅 1 ││…││ 𝑅 𝑛−1 𝑅 0 can be ATC 𝐾 𝑆 =𝐴𝐿𝐺 𝐾 𝑀 ,𝑅 , if │ 𝐾 𝑆 │is the block length of ALG 𝐾 𝑆 =𝐴𝐿𝐺 𝐾 𝑀 , 𝐹 1 ││𝐴𝐿𝐺( 𝐾 𝑀 , 𝐹 2 ), if │ 𝐾 𝑆 │> block length of ALG 𝐹 1 = 𝑅 0 ││ 𝑅 1 ││𝐹0││…││ 𝑅 𝑛−1 𝐹 2 = 𝑅 0 ││ 𝑅 1 ││0𝐹││…││ 𝑅 𝑛−1 ALG = 3DES or AES November 8, 2016 Practical Aspects of Modern Cryptography

24 EMV Asymmetric Signature AlgorithmsSignature generation 𝑁 is the input/output length of the signature/verification functions ℎ=𝐻(𝑀) 𝑚= 𝑚 1 ││ 𝑚 2 , where 𝑚 1 is the 𝑁−22 leftmost bytes of 𝑚, 𝑚 2 is the rest 𝑠=𝑆( 𝑆 𝐾 , 6𝐴 ││ 𝑚 1 ││ℎ││𝐵𝐶) 𝐻 must be a hash function with 160 bit output; SHA-1 RSA with 𝑒=3 or 𝑒= Mandatory upper bounds for modulus is 248 bytes (1,984 bits) max ( 𝑁 ) =1984 November 8, 2016 Practical Aspects of Modern Cryptography

25 Online Transaction AuthenticationARQC Card Network Acquirer ARQC ARPC ARPC ARQC ARPC ARQC 3DES Cryptogram ARPC Issuer Shared Key November 8, 2016 Practical Aspects of Modern Cryptography

26 Mobile Payments (Apple, Microsoft, Android)Secure Element (SE): certified chip running Java Card NFC Application processor and SE SE and POS Terminal Wallet, the Application Secure Enclave Manages authentication Payment processing Fingerprint storage Apple Pay Servers Payment card state management Device account numbers in SE Device/network communication November 8, 2016 Practical Aspects of Modern Cryptography

27 Mobile Payments: ApplePayInitialization Secure Element is connected to NFC controller NFC controller is also connected to the application processor Secure Enclave and Secure Element has an AES key (manufacturing time) Add Card User enters card information on the device CardInfo, UserInfo, DeviceInfo are sent to the corresponding issuer Issuer performs ID&V (Identification and Verification) PAN is not stored on the device DPAN, Device PAN, is stored on the device (SE or other secure storage) https://www.apple.com/business/docs/iOS_Security_Guide.pdf November 8, 2016 Practical Aspects of Modern Cryptography

28 Mobile Payments: ApplePayPayment Transactions use DPAN: device account number ATC: incrementing counter per transaction (shared with network and issuer) Payment Authorization NFC detection invokes the payment application User is presented for authorization Secure Element receives authorization from Secure Enclave PAN is not used https://support.apple.com/en-us/HT203027 November 8, 2016 Practical Aspects of Modern Cryptography

29 BitCoin Transactions are recorded on a block chainTransactions are published on the BitCoin network Miners compete to solve a cryptographic puzzle (Proof of Work) Fees are paid to the winning miner per transaction BitCoin network data is public Anonymity? Not really https://the-blockchain.net/ November 8, 2016 Practical Aspects of Modern Cryptography

30 BitCoin, Silk Road Silk Road: Online marketplace (since 2/2011)Illegal substance and service trade Run by Dread Pirate Roberts All communications through TOR 13,000 listings as of 9/2013 FBI arrest on 10/1/2013, 29 year old male How to find the person, trace money movement, debunk anonymity claims Data mining techniques for large payment systems Publicly available transaction graphs Revenue of ~9.5 million BitCoins, commission ~600,000 BitCoins November 8, 2016 Practical Aspects of Modern Cryptography

31 Block Chain Layers Application View Consensus Storage NetworkTransactions Smart contracts written in a language (Turing complete or not) Language is run in an execution environment View Summary of the transaction log Consensus Distributed block agreement Storage Distributed storage of transactions and blocks Network New transaction broadcast November 8, 2016 Practical Aspects of Modern Cryptography

32 Block Chain Layers Application TransactionsSmart contracts written in a language (Turing complete or not) Contracts are programs, and error-prone Language is run in an execution environment If CSEP590 is on Election Night on 2016 Then don’t talk about elections and voting, And transfer $10 to NPR What is our track record in correctly codifying the intent? What is our track record in correctly executing the code? What is our track record in securely executing the code? November 8, 2016 Practical Aspects of Modern Cryptography

33 Smart Contract in Block ChainsWhat happens in an unmodifiable block chain when mistakes are found? What happens when malicious mistakes are not found? How do you prove it is a mistake? From Cornell IC3 in May’16, Andrew Miller’s presentation, mistakes by UMD security class students. What happens when a third player joins the contract? November 8, 2016 Practical Aspects of Modern Cryptography

34 Block Chain Layers Perceived Layers Permissioned vs. PermissionlessApplication. Transactions, smart contracts View. Summary of the transaction log Consensus. Distributed block agreement Storage. Distributed storage of transactions and blocks Network. New transaction broadcast Permissioned vs. Permissionless November 8, 2016 Practical Aspects of Modern Cryptography

35 Hash Functions Arbitrary-length input Hash Function Hash FunctionFixed-length output

36 One-Way Hash FunctionsArbitrary-length input Given just an output, it is infeasible to find any input which produces that output. One-Way Hash Function Fixed-length output

37 SHA-256 Arbitrary-length inputGiven just an output, it is infeasible to find any input which produces that output. SHA-256 256-bit output

38 3 Definitions of One-Way HashesNon-invertible: Given a target output, it’s hard to find an input that produces the target output. 2nd pre-image resistant: Given an input, it’s hard to find another input that produces the same output. Collision-intractable: It’s hard to find any two inputs that produce the same output.

39 Birthday Paradox If you pick more than ~ 𝑁 times from a space of 𝑁 items, you will start seeing repetitions. Intuition: After 𝐾 items have been seen, 𝐾(𝐾−1) 2 pairs will have been seen.

40 SHA-256 Mechanics

41 SHA-256 Compression FunctionSHA-256 Mechanics 768-bit input SHA-256 Compression Function 256-bit output

42 SHA-256 Compression FunctionSHA-256 Mechanics 768-bit input 256 bits 512 bits SHA-256 Compression Function 256-bit output

43 SHA-256 Mechanics Full Input

44 SHA-256 Mechanics 512 bits 512 bits 512 bits 512 bits

45 SHA-256 Mechanics SHA-256 Compression Function512 bits 512 bits 512 bits 512 bits 256-bit Initial Value 512 bits 512 bits 512 bits 512 bits SHA-256 Compression Function SHA-256 Compression Function SHA-256 Compression Function SHA-256 Compression Function SHA-256 Compression Function 256 bits 256 bits 256 bits 256 bits 256-bit output

46 SHA-256 Compression FunctionHash Chains Input #1 Input #2 Input #3 Input #4 Initial Value One-Way Hash Function One-Way Hash Function One-Way Hash Function SHA-256 Compression Function One-Way Hash Function Output

47 SHA-256 Compression FunctionHash Chains Initial Value One-Way Hash Function One-Way Hash Function One-Way Hash Function SHA-256 Compression Function One-Way Hash Function Output

48 Merkle Tree 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻

49 Merkle Tree 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻

50 Merkle Tree 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻

51 Merkle Tree 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻

52 Merkle Tree 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻 𝐻

53 One-Way Accumulators Flatten Merkle trees with constant-sized proof of membership. Use a “quasi-commutative” function.

54 One-Way Accumulators When viewed as a two-argument function, the (candidate) one-way function 𝐹 𝑁 (𝑌,𝑋)= 𝑌 𝑋 mod 𝑁 also satisfies a useful additional property which has been termed quasi-commutivity: 𝐹(𝐹(𝑌, 𝑋 1 ), 𝑋 2 )=𝐹(𝐹(𝑌, 𝑋 2 ), 𝑋 1 ) since 𝑌 𝑋 1 𝑋 2 = 𝑌 𝑋 2 𝑋 1 .

55 One-Way Accumulators The “hash” of values 𝑋 1 , 𝑋 2 ,…, 𝑋 𝑚 is 𝑍=𝐹 𝑁 (𝑌, 𝑋 1 , 𝑋 2 ,…, 𝑋 𝑚 )= 𝑌 𝑖=1 𝑚 𝑋 𝑖 mod 𝑁. The value 𝑋 𝑘 can be shown to be one of the hashed values by showing 𝑍 𝑘 =𝑌 𝑖≠𝑘 𝑋 𝑖 mod 𝑁 since 𝑍= 𝑍 𝑘 𝑋 𝑘 mod 𝑛.

56 Historical Use of Hash Chains1979: Merkle-Damgård – Chained Hash Function Construction 1979: Merkle Tree – Tree of Hashes used for Membership 1981: Lamport – Hash Chains for Password Protection 1991: Haber-Stornetta – Time-Stamping with Hash Trees 1994: Benaloh-deMare – One-Way Accumulators 2001: Rivest-Shamir – PayWord & MicroMint micropayments

57 Historical Use of Hash Chains1979: Merkle-Damgård – Chained Hash Function Construction 1979: Merkle Tree – Tree of Hashes used for Membership 1981: Lamport – Hash Chains for Password Protection 1991: Haber-Stornetta – Time-Stamping with Hash Trees 1994: Benaloh-deMare – One-Way Accumulators 1997: Hashcash – Generating “cash” by Repeated Hashing 2001: Rivest-Shamir – PayWord & MicroMint micropayments

58 Finding Distinguished OutputsWith SHA-256 (or any good one-way hash function) … The best way to achieve a specific target output is to repeatedly try different inputs until one succeeds. The best way to achieve a specific output property is to repeatedly try different inputs until one succeeds.

59 Hashcash (1997) To demonstrate work on 𝑥, find 𝑦 such that 𝐻 𝑥,𝑦 <𝑧, for some pre-determined bound 𝑧.

60 Hashcash – Proof of WorkTo demonstrate work on 𝑥, find 𝑦 such that 𝐻 𝑥,𝑦 <𝑧, for some pre-determined bound 𝑧.

61 bitcoin Currency (2008) The next bitcoin(s) are awarded to the first person who can find a value which when hashed with the previous bitcoin produces an output smaller than a pre-defined target.

62 bitcoin Transactions Together with the most recently found coin, a bitcoin miner can optionally include some signed “transactions” in its hashes (for which it may receive transaction fees).

63 bitcoin Transactions The values that are hashed together with the previous coins can contain other stuff: My name My public key Transactions Contracts Etc.

64 bitcoin mining 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧

65 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧 bitcoin miningMost recent prior coin

66 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧 bitcoin miningMost recent prior coin Optional transactions

67 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧 bitcoin miningMost recent prior coin Miner ID info Optional transactions

68 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧 bitcoin miningMost recent prior coin Miner ID info Optional transactions Random variable

69 𝐻 𝑐, 𝑡 1 , 𝑡 2 ,…, 𝑡 𝑛 ,𝑚,𝑟 <𝑧 bitcoin miningMost recent prior coin Miner ID info Target value Optional transactions Random variable

70 bitcoin target value The target value is set so that the blockchain will be extended once every 10 minutes – on average. The target value is adjusted every 2016 blocks (which should happen about every two weeks). November 8, 2016 Practical Aspects of Modern Cryptography

71 Mining new bitcoins When a miner successfully extends the blockchain, it broadcasts its new value to all the other miners and receives a reward. Miners then (are supposed) continue mining on the new, longer chain.

72 Dispute Resolution What if two miners extend the chain (each with their own info) at the same time? There are numerous distributed consensus protocols that have been developed and published by Computer Scientists.

73 Dispute Resolution The longest chain wins.

74 Mining Pools Collaboration offers two principal benefits.Centralized transaction processing Reduced volatility

75 Pooling Details Pools can pay members in proportion to their failed contributions. Large pools threaten integrity of the system.

76 What Do Block Chains Provide?Block chains can achieve distributed consensus without a trusted authority or random source. Block chains can randomly select a leader/winner from a group in a “fair” manner.

77 Block Chain Overreach Block chains are not ideal when a central authority is already part of the system. N.B. Hash chains (now sometimes called private block chains) have numerous good applications.