Electronic Payment Systems 20-763 Lecture 4 ePayment Security I 20-763

Electronic Payment Systems 20-763 Lecture 4 ePayment Security I 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

ePayment Security ePayments are impossible without security Keep financial data secret from unauthorized parties (privacy) – CRYPTOGRAPHY Verify that messages have not been altered in transit (integrity) – HASH FUNCTIONS Prove that a party engaged in a transaction (nonrepudiation) – DIGITAL SIGNATURES Verify identity of users (authentication) – PASSWORDS, DIGITAL CERTIFICATES 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Cryptography and Hash Functions Message digest (hash) algorithms – Secure Hash Algorithm – Passwords Defending against attacks Lecture 4 Security I – Salting, nonces Symmetric encryption – DES and variations – AES: Rijndael Public-key algorithms – RSA – Elliptic curve cryptography (ECC) Digital signatures 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT Lecture 5 Security II

Hash Functions A “HASH” IS A SHORT FUNCTION OF A MESSAGE (USUALLY 160 BITS) MESSAGE SPACE (ALL POSSIBLE PLAINTEXT MESSAGES) “TRANSFER 5000 TO MY SAVINGS ACCOUNT” HASH SPACE (ALL POSSIBLE HASHED MESSAGES) ? MUST NOT BE REVERSIBLE 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT “AF0E891B293”

Hash Functions MESSAGE SPACE (ALL POSSIBLE PLAINTEXT MESSAGES) “TRANSFER 5000 TO MY SAVINGS ACCOUNT” “IT’S MONDAY” “THE SKY IS BLUE” HASH FUNCTIONS ARE NOT ONE-TO-ONE AND NOT REVERSIBLE MANY MESSAGES HAVE THE SAME HASH HASH SPACE (ALL POSSIBLE HASHED MESSAGES) “AF0E891B293” 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

One-Way Hash Functions For any string s, H(s), the hash of s, is of fixed length (shorter than s), sometimes called a message digest Easy to compute “One-way”: computationally difficult to invert: can’t find any message corresponding to a given hash Diffusion property: Altering any bit of the message changes many bits of the hash 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Uses of One-Way Hash Functions Password verification Message authentication (message digests) Prevention of replay attack Digital signatures 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Secure Hash Algorithm SHA-1 Federal Information Processing Standard 180-1 (NIST) For any message shorter than 2 64 10 19 bits, produces a 160-bit message digest Uses exclusive-OR operation A 0011011110001 B 1101001101011 A B 1110010011010 Exclusive-OR is lossy; knowing A B does not reveal even one bit of either A or B Regular OR: If a bit of A B is zero, then both corresponding bits of both A and B were zero 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Information Hiding with Exclusive-OR x y 1 if either x or y is 1 but not both: y x x y 0 1 0 0 1 1 1 0 If x y 1 we can’t tell which one is a 1 Can’t trace backwards to determine values If x y 1 then BOTH x and y are 1 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Secure Hash Algorithm Flow LONG MESSAGE TO BE HASHED TAKE FIRST 16 WORDS (512 BITS) STARTING HASH FIVE 32-BIT WORDS (160 BITS) REPEAT FOR EACH 512-BIT BLOCK EXPAND TO 80 WORDS (2560 BITS) REPEAT 79 MORE TIMES FINAL HASH (160 BITS) 111011 010111 100010 000110 110110 011110 011001 100101 110010 111011 010111 100010 011101 110101 101011 001111 101100 100011 000110 110110 011110 111011 010111 100010 001111 101100 100011 011101 110101 101011 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Hashed Passwords A system must be able to verify that a password is correct Store the plaintext passwords. TERRIBLE IDEA Store hashed passwords. BETTER IDEA – – – – – – User SHAMOS has password “MAGIC”; hash is “341JY” System stores (SHAMOS, 341JY) Shamos logs in by typing SHAMOS, MAGIC System hashes “MAGIC” to form “341JY” Looks up hash of SHAMOS password 341JY USER is authenticated System never stores the passwords Passwords can’t be hacked or stolen Someone who finds “341JY” cannot recover “MAGIC” 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Weakness of Hashed Passwords Passwords come from a small universe ( 50,000 words). Possible to compare all possible hashes against the hashed file to discover passwords For example, take each word in the English dictionary and hash it. This will reveal “MAGIC” and “341JY” Hash each password differently. NOT SO BAD – Defends against dictionary attack Want to be sure that two people who have the same password have different hashes, so compromise of one password does not reveal others Don’t store H (P), the hash of the password Store S and H (P S), where S, called salt, is different for each user 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Salting Example A’s password is “13524”; B’s password is “13524” A’s salt is “ABC”; B’s salt is “DEF” The hash of A’s salted password is “1663az78fz” System stores “A, ABC, 1663az78fz” The hash of B’s salted password is “v134c27a8” System stores “B, DEF, v134c27a8” A logs on. Sends user “A”, password “13524” System looks up A’s salt, hashes salted password, compares with stored salted password Someone who discovers A’s salted password can’t use it Can’t tell that A and B have the same password 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Nonce to Prevent Replay Attack Time-dependent value used in challenge-response protocols to prevent replay attack Random numbers, timestamps System sends a nonce, e.g. “1992884665” User sends a hash of username password nonce System computes what the hash should be, verifies user Replay fails since the nonce will be different when the attacker tries to gain access Nonce: “for the nonce” means “for the time being,” “just for now” 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Cryptography CODE SPACE (ALL POSSIBLE ENCRYPTED MESSAGES) MESSAGE SPACE (ALL POSSIBLE PLAINTEXT MESSAGES) “TRANSFER 5000 TO MY SAVINGS ACCOUNT” MUST BE REVERSIBLE (BUT ONLY IF YOU KNOW THE SECRET) 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT “1822UX S4HHG7 803TG 0J71D2 MK8A36 18PN1”

Cryptography MESSAGE SPACE (ALL POSSIBLE PLAINTEXT MESSAGES) “TRANSFER 5000 TO MY SAVINGS ACCOUNT” ENCRYPTION IS SECURE IF ONLY AUTHORIZED PEOPLE KNOW HOW TO REVERSE IT CODE SPACE (ALL POSSIBLE ENCRYPTED MESSAGES) ENCRYPTION IS ONE-TO-ONE AND REVERSIBLE EVERY CODE CORRESPONDS TO EXACTLY ONE MESSAGE 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT “1822UX S4HHG7 803TG 0J71D2 MK8A36 18PN1”

The Encryption Process OBJECT: HIDE A MESSAGE (PLAINTEXT) BY MAKING IT UNREADABLE (CIPHERTEXT) UNREADABLE VERSION OF PLAINTEXT MATERIAL WE WANT TO KEEP SECRET MIGHT BE: TEXT DATA GRAPHICS AUDIO VIDEO SPREADSHEET . DATA TO THE ENCRYPTION ALGORITHM (TELLS HOW TO MATHEMATICAL SCRAMBLING PROCEDURE SCRAMBLE THIS PARTICULAR MESSAGE) SOURCE:20-763 STEIN, WEB SECURITY ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Role of the Key in Cryptography The key is a parameter to an encryption procedure Procedure stays the same, but produces different results based on a given key S P E C I A L T Y B D F G H J K M N O Q R U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z EXAMPLE: C O N S U L T I N G D S R A V G H E R M NOTE: THIS METHOD IS NOT USED IN ANY REAL CRYPTOGRAPHY SYSTEM. IT IS AN EXAMPLE INTENDED ONLY TO ILLUSTRATE THE USE OF KEYS. 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Symmetric Encryption SAME KEY USED FOR BOTH ENRCYPTION AND DECRYPTION SENDER AND RECIPIENT MUST BOTH KNOW THE KEY THIS IS A WEAKNESS 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: STEIN, WEB SECURITY

Symmetric Encryption “Symmetric”: same key for both encryption and decryption SENDER AND RECIPIENT MUST BOTH KNOW THE KEY THIS IS A WEAKNESS 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: WILLIAM STALLINGS

Data Encryption Standard (DES) Symmetric, key-based encryption-decryption standard. No public keys Block cipher: operates on 64-bit blocks Uses 56-bit key 16 “rounds” -- key for each round is a 48-bit function of the original 56-bit key. Each key bit participates in an average of 14 rounds Completely symmetric. Same algorithm decrypts. Fast implementation in hardware: 1 gigabit/second 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Encryption “Rounds” Key Round Keys X KE Key Expansion K k1 k2 k3 kn-2 kn-1 kn r1 r2 r3 rn-2 rn-1 rn Y Encryption Rounds r1 rn Key K is expanded to a set of n round keys k i Input block X undergoes n rounds of operations (each operation is based on value of the nth round key), until it reaches the final round rn Strength of algorithm: difficulty of going backwards from the intermediate result of round m 1 to round m without knowing the round key rm. 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: MEL TSAI

Classical Feistel Encryption Network 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: WILLIAM STALLINGS

DES Encryption 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: WILLIAM STALLINGS

One Round of DES 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: WILLIAM STALLINGS

Years To Crack Symmetric Encryption Key Length 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: WILLIAM STALLINGS

Cipher Block Chaining Example In ECB mode, the same input text always produces the same output. This creates risk of partial decryption. INITIALIZATION STRING PLAINTEXT BLOCK 1 PLAINTEXT BLOCK 2 DES DES CIPHERTEXT BLOCK 1 CIPHERTEXT BLOCK 2 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT etc.

Triple DES Security can be increased by encrypting multiple times with different keys Double DES is not much more secure than single DES because of a “meet-in-the-middle” attack K1 PLAINTEXT BLOCK 1 DES ENCRYPT K2 K3 DES DES DECRYPT ENCRYPT If K1 K2 K3 this is just single DES 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT CIPHERTEXT BLOCK 1

AES, the DES Replacement AES Advanced Encryption Standard DES has weaknesses: – slow (by modern standards) – weak (can be broken by fast computers) NIST ran a competition to replace DES Winner: Rijndael, invented by Vincent Rijmen and Joan Daeman No patenting allowed Round block cipher of similar structure to DES but faster, more secure 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Rijndael kn ByteSub ShiftRow MixColumn AddRoundKey Result from round n-1 Pass to round n 1 Detailed view of round n Each round consists of: ByteSub: each 8 bits of input is replaced with a different 8 bits ShiftRow: each row of the block matrix is cyclically shifted MixColumn AddRoundKey 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT SOURCE: MEL TSAI

Rijndael Allows 128, 192, and 256-bit key sizes Variable block length: 128, 192, or 256 bits. All nine combinations of key/block length possible. – A block is the smallest data size the algorithm will encrypt VERY FAST, much faster than DES – Software: 8416 bytes/sec on a 20MHz 8051 – Software: 53 Mbytes/sec on a 800MHz Pentium – Hardware: currently up to 25 Gbps 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Major Ideas SHA is the most important hash function SHA has not been cracked (reversed) Encryption algorithms are complex – must be studied carefully (by cryptographers) – subject to sophisticated attacks Symmetric encryption is fast – DES is not secure – DES family being replaced with Rijndael Salting defends against dictionary attacks Nonces defend against replay attacks 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Q&A 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT

Meet-in-the-Middle Attack Exhaustive search for keys to crack 2DES would seem to require testing 2112 keys Start with (m, c), a plaintext/ciphertext pair Encrypt a two-block plaintext m with all possible 2 56 single DES keys k1; sort the resulting pairs (k1, cmiddle) Decrypt the 2-block ciphertext c with all possible 2 56 single DES keys k2; for each result cmiddle, check to see whether it occurs in the sorted list If so, (k1, k2) is a possible key. enc2DES((k1, k2),m) encDES(k2, encDES(k1,m)) encDES(k2, cmiddle1) c This only requires testing 256 keys (and sorting them) 20-763 ELECTRONIC PAYMENT SYSTEMS FALL 2002 COPYRIGHT