crypto.md (6272B)
1 +++ 2 title = 'Crypto' 3 template = 'page-math.html' 4 +++ 5 # Crypto 6 Allows secure communication between two or more parties in presence of an attacker 7 8 Goals: 9 - confidentiality: Eve can't read Alice's message to Bob 10 - integrity: Eve can't alter Alice's message without Bob finding out 11 - authentication: Eve can't convince Bob she is Alice 12 - non-repudiation: Even can't deny she sent a message to Bob 13 14 Terms: 15 - plaintext: readable text 16 - ciphertext: unreadable text actually sent 17 - encryption: convert plaintext to ciphertext 18 - decryption: convert ciphertext to plaintext 19 20 Kerckhoff's principle: 21 - separate algorithm from key 22 - assume attacker knows algorithm 23 - keep key secret 24 25 Can't make the plaintext space larger ⇒ use a larger key space 26 - instead of shifting by fixed amount, generate random permutation, mapping each letter to an arbitrary other one → 26! possible keys 27 28 Attacks: 29 - brute force 30 - frequency analysis: some letters much more common than others, such as 'e' and 'a' in English 31 32 End-to-end encryption: only sender and recipient have key 33 34 Cryptographic hashes: 35 - hash function maps message (arbitrary length) to hash (fixed length) 36 - computationally hard to reverse -- "one-way function" 37 - pre-image resistance: hard to find message m such that hash(m)=h 38 - second pre-image resistance: given message m1, hard to find another message m2 such that hash(m1)=hash(m2) 39 - collision resistance: hard to find any two messages m1 and m2 that have same hash 40 41 Well-known hashes: 42 - MD5: collision resistance long broken 43 - SHA-1: collision resistance recently broken 44 - SHA-2: collision resistance probably secure for some time 45 - SHA-3: eliminates some theoretical weakness of earlier hashes 46 47 Random numbers 48 - CPUs are deterministic, so can't generate truly random numbers without special hardware 49 - pseudo-random (PRNG): compute from seed, seed updated for every generated number 50 - sequence is often predictable 51 52 Blockchains: 53 - each block of transactions contains hash of previous block 54 - ⇒ can't change past transactions without changing later ones 55 - real chain is what above 50% of users (by compute power) agree on 56 57 ## Symmetric crypto 58 Uses single key to encrypt and decrypt. 59 60 One-time pad: 61 - n-bit message, n-bit key 62 - XOR key with message to encrypt/decrypt 63 64 Perfect encryption 65 - never reuse key 66 - key is perfectly random 67 - e.g.: one-time pad 68 69 Stream ciphers: 70 - use PRNG to generate key 71 - initial seed is now real key 72 73 Block ciphers: 74 - divide data in blocks 75 - compute using key to map each plain block into cipher block 76 - e.g. DES, AES 77 78 Cipher block chaining (CBC) 79 - ECB still reveals repetitions, allows ordering blocks 80 - CBC: make each block depend on previous one 81 - first block: use initialization vector (IV) instead 82 - doesn't need to be secret 83 - shouldn't be reused 84 85 Padding blocks: 86 - message sizes often not multiple of block size 87 - must be padded with extra bytes containing padding length 88 - add block of padding even if multiple of key size 89 90 Padding oracle attack: 91 - assumptions: attacker can send encrypted message, server decrypts message and return error if padding incorrect, server uses block cipher with CBC 92 - under these conditions, attacker can decrypt last block 93 - take: Dk decryption function with key k, n number of ciphertext blocks, Pi and Ci the plaintext and ciphertext block i 94 - $P_{n-1} = D_{k} (C_{n-1}) \oplus C_{n-2}$ 95 - if we modify penultimate block of ciphertext ($C_{n-2}$), we change plaintext that server sees for last block ($P_{n-1}$) 96 - example: 97 1. Write bytes of ciphertext c0-c15, plaintext p0-p15 98 2. send c0..c7 ⨁ b...c15, for each b ∈ [0, 256) 99 - because block size 8, c7 is used to compute p15 100 3. find that only b=0 (unchanged) and b=2 work 101 - so p15 ⨁ 2 = 1 (length 1 padding) 102 - so p15 = 1 ⨁ 2 = 3 103 - so plaintext has 3 bytes of padding 104 - so p13 = p14 = p15 = 3 105 4. Now send c0...c4 ⨁ b, c5 ⨁ 7, c6 ⨁ 7, c7 ⨁ 7...c15 106 - 7 because 3 (plaintext) ⨁ 4 (new padding length) == 7 107 - c4 used to compute p12, because block size 8 108 5. Find thatonly b=0x36 works 109 - so p12 ⨁ 0x36 = 4 (legnth 4 padding) 110 - so p12 = 0x36 ⨁ 4 = 0x32 = ASCII "2" 111 6. Now send c0...c3 ⨁ b, c4 ⨁ 0x37, c5 ⨁ 6, c6 ⨁ 6, c7 ⨁ 6...c15 112 - 6 because 3 (plaintext) ⨁ 5 (padding) == 6 113 - 0x37 because 0x32 (plaintext) ⨁ 5 (padding) == 0x37 114 - c3 used to compute p11 (because block size 8) 115 - only b=0x31 works 116 - so p11 ⨁ 0x31 = 5 (length 5 padding) 117 - so p11 = 0x31 ⨁ 5 = 0x34 = ASCII "4" 118 7. etc. 119 120 Symmetric signatures/message authentication code 121 - if message altered, no longer valid 122 - key needed to generate valid 123 - same key needed to validate 124 125 126 ## Asymmetric crypto 127 Two keys: 128 - anyone can encrypt with Bob's public key 129 - only Bob knows private key, needed to decrypt 130 131 Example is RSA 132 133 ## Key management 134 Cannot trust Bob to tell Alice public key online: 135 - either provide public key through separate trusted channel 136 - or get trusted third party to authenticate keys 137 138 Key distribution center (KDC): 139 - trusted party 140 - shares symmetric keys with all others 141 - verifies identities of key owners 142 143 Certification authority (CA) 144 - asymmetric crypto alternative to KDC 145 - issues certificates to verify identities 146 - keeps revocation list of certificates that may be compromised 147 - we need to trust these companies 148 - X5.09 certificates contain identity, domain name(s), public key, expiration date, signature from CA 149 150 Symmetric encryption key establishment 151 - agree on key e.g. via Diffie-Hellman Key Exchange 152 153 SSL and HTTPS 154 - SSL (also known as TLS) is layer on top of TCP 155 - any TCP protocol can be modified to run on top of SSL (e.g. HTTP ⇒ HTTPS) 156 - end-to-end encryption: Diffie-Hellman to create shared encryption key 157 - authenticate server using X5.09 certificate 158 - typically does not authenticate client (server can do this in application layer) 159 160 Password storage 161 - hash the password 162 - to make brute forcing harder: 163 - salt the hash (concatenate password and salt before hashing, store salt with the hash) 164 - use a slow hash, which slows down brute forcing but not normal use