CPS 214 Computer Networks and Distributed SystemsBasic DefinitionsWhat does it mean to be secure?Primitives: One-Way FunctionsOne-way functions: possible definitionOne-way functions: better definitionSome examples (conjectures)One-way functions in private-key protocolsSlide 9One-way functions in public-key protocolsOne-Way Trapdoor FunctionsOne-way Hash FunctionsProtocols: Digital SignaturesUsing Public KeysKey ExchangePrivate Key AlgorithmsSlide 17Private Key: Block CiphersIterated Block CiphersIterated Block Ciphers: DecryptionFeistel NetworksProduct CiphersRijndaelPublic Key CryptosystemsOne-way trapdoor functionsExample of SSL (3.0)Diffie-Hellman Key ExchangePerson-in-the-middle attackRSARSA Public-key CryptosystemRSA continuedRSA computationsSecurity of RSARSA PerformanceRSA in the “Real World”Factoring in the Real WorldSSH v2KerberosKerberos (kinit)Kerberos V Message FormatsKerberos Notes15-853 Page 1CPS 214 Computer Networks and Distributed SystemsCryptography BasicsRSASSLSSHKerberos15-853 Page 2Basic DefinitionsPrivate Key or Symmetric: Key1 = Key2Public Key or Asymmetric: Key1  Key2Key1 or Key2 is public depending on the protocolEncryptionDecryptionKey1Key2CyphertextEkey1(M) = CDkey2(C) = MOriginal PlaintextPlaintext15-853 Page 3What does it mean to be secure?Unconditionally Secure: Encrypted message cannot be decoded without the keyShannon showed in 1943 that key must be as long as the message to be unconditionally secure – this is based on information theoryA one time pad – xor a random key with a message (Used in 2nd world war)Security based on computational cost: it is computationally “infeasible” to decode a message without the key.No (probabilistic) polynomial time algorithm can decode the message.15-853 Page 4Primitives: One-Way Functions(Informally): A function Y = f(x)is one-way if it is easy to compute y from x but “hard” to compute x from yBuilding block of most cryptographic protocolsAnd, the security of most protocols rely on their existence.Unfortunately, not known to exist. This is true even if we assume P  NP.15-853 Page 5One-way functions: possible definition1. F(x) is polynomial time2. F-1(x) is NP-hardWhat is wrong with this definition?15-853 Page 6One-way functions:better definitionFor most y no single PPT (probabilistic polynomial time) algorithm can compute xRoughly: at most a fraction 1/|x|k instances x are easy for any k and as |x| -> This definition can be used to make the probability of hitting an easy instance arbitrarily small.15-853 Page 7Some examples (conjectures)Factoring: x = (u,v)y = f(u,v) = u*v If u and v are prime it is hard to generate them from y.Discrete Log: y = gx mod pwhere p is prime and g is a “generator” (i.e., g1, g2, g3, … generates all values < p).DES with fixed message: y = DESx(m)This would assume a family of DES functions of increasing key size (for asymptotics)15-853 Page 8One-way functions in private-key protocols y = ciphertext m = plaintext k = keyIs y = Ek(m) (i.e. f = Ek)a one-way function with respect to y and m?What do one-way functions have to do with private-key protocols?15-853 Page 9One-way functions in private-key protocols y = ciphertext m = plaintext k = keyHow about y = Ek(m) = E(k,m) = Em(k) (i.e. f = Em)should this be a one-way function?In a known-plaintext attack we know a (y,m) pair.The m along with E defines f Em(k) needs to be easy Em-1(y) should be hardOtherwise we could extract the key k.15-853 Page 10One-way functions in public-key protocols y = ciphertext m = plaintext k = public keyConsider: y = Ek(m) (i.e., f = Ek)We know k and thus f Ek(m) needs to be easy Ek-1(y) should be hardOtherwise we could decrypt y.But what about the intended recipient, who should be able to decrypt y?15-853 Page 11One-Way Trapdoor FunctionsA one-way function with a “trapdoor”The trapdoor is a key that makes it easy to invert the function y = f(x)Example: RSA (conjecture)y = xe mod nWhere n = pq (p, q are prime)p or q or d (where ed = 1 mod (p-1)(q-1)) can be used as trapdoorsIn public-key algorithmsf(x) = public key (e.g., e and n in RSA)Trapdoor = private key (e.g., d in RSA)15-853 Page 12One-way Hash FunctionsY = h(x) where–y is a fixed length independent of the size of x. In general this means h is not invertible since it is many to one.–Calculating y from x is easy–Calculating any x such that y = h(x) give y is hardUsed in digital signatures and other protocols.15-853 Page 13Protocols: Digital SignaturesGoals:1. Convince recipient that message was actually sent by a trusted source2. Do not allow repudiation, i.e., that’s not my signature.3. Do not allow tampering with the message without invalidating the signatureItem 2 turns out to be really hard to do15-853 Page 14Using Public KeysMore EfficientlyAlice BobDk1(m)Alice BobDk1(h(m)) + mK1 = Alice’s private keyBob decrypts it with her public keyh(m) is a one-way hash of m15-853 Page 15Key ExchangePrivate Key methodPublic Key methodTrentAlice BobEka(k) Ekb(k)Generates kAliceBobGenerates kEk1(k)k1 = Bob’s public keyOr we can use a direct protocol, such as Diffie-Hellman (discussed later)15-853 Page 16Private Key AlgorithmsEncryptionDecryptionKey1Key1CyphertextEk(M) = CDk(C) = MOriginal PlaintextPlaintextWhat granularity of the message does Ek encrypt?15-853 Page 17Private Key AlgorithmsBlock Ciphers: blocks of bits at a time–DES (Data Encryption Standard)Banks, linux passwords (almost), SSL, kerberos, …–Blowfish (SSL as option)–IDEA (used in PGP, SSL as option)–Rijndael (AES) – the new standardStream Ciphers: one bit (or a few bits) at a time–RC4 (SSL as option)–PKZip–Sober, Leviathan, Panama, …15-853 Page 18Private Key: Block CiphersEncrypt one block at a time (e.g. 64 bits) ci = f(k,mi) mi = f’(k,ci)Keys and blocks are often about the same size.Equal message blocks will encrypt to equal codeblocks–Why is this a problem?Various ways to avoid this:–E.g. ci = f(k,ci-1  mi) “Cipher block chaining” (CBC)Why could this still be a problem?Solution: attach random block to the front of the message15-853 Page 19Iterated Block CiphersConsists of n roundsR = the “round” functionsi = state after round iki = the ith round keyRRRs1...mc...keyk1k2kns215-853 Page 20Iterated Block Ciphers: DecryptionRun the rounds in reverse.Requires that R has an inverse.R-1R-1R-1s1...mc...keyk2kns2k115-853 Page 21Feistel NetworksIf function is not