Encryption

Encryption

The Problem

  • Using HTTP, anyone with access to your packets can see everything you are doing online
    • This includes your passwords!
  • Who has access to my packets?
    • Your ISP at home
    • UBIT on campus
    • Tier 1 Networks

The Problem

  • Using HTTP, anyone with access to your packets can see everything you are doing online
    • This includes your passwords!
  • Who has access to my packets?
    • Your ISP at home
    • UBIT on campus
    • Tier 1 Networks
    • .. and everyone within wifi range of your device!

The Problem

  • Using HTTP, anyone with access to your packets can see everything you are doing online
    • This includes your passwords!
  • Why does this include passwords? Are they not hashed?
  • --Demo--

The Problem

  • Using HTTP, anyone with access to your packets can see everything you are doing online
    • This includes your passwords!
  • Passwords are sent over the Internet in plain text!
    • Hashing client-side does not add any security.

The Solution

  • We'll just add an S to our protocol and call it HTTPS
    • HTTP over TLS

Encryption

  • Hide communication from attackers/eavesdroppers
  • Want to send a plaintext message
    • Could be HTML, JSON, JavaScript, text, an image, etc
    • Plaintext is a cryptographic term to mean unencrypted
    • We encrypt at the byte level
  • Encrypting the plaintext outputs a random looking cyphertext
  • No one should be able to read this cypher text except the intended recipient
  • Only the intended recipient can decrypt the cyphertext and read the plaintext message

Encryption

The plaintext "Meet us at the stick" is encrypted into a long, random-looking ciphertext. Decrypting the ciphertext gives back the plaintext "Meet us at the stick".

Public Key Encryption

  • How do we ensure that only the intended recipient can decrypt the message?
    • Public Key Encryption
  • Generate a public and private encryption key
    • Private key is kept private
    • Public key is shared with anyone/everyone
  • A message encrypted with the public key can only be decrypted by the corresponding private key
  • If I want to send a message to someone, I can encrypt the message with their public key

Public Key Encryption

  • The public and private key are inherently related
  • An attacker must not be able to determine the private key given the public key [In any reasonable amount of time]
  • An attacker must not be able to decrypt cyphertext without the private key [In any reasonable amount of time]
  • Any public key encryption algorithm must have these properties [And more]
    • Math and theory will help us

Public Key Encryption - RSA

  • RSA - Rivest-Shamir-Adleman
    • A public key crypto system with the desired properties [we hope]
  • Provides algorithms to:
    • Generate a public/private key pair
    • Encrypt with the public key
    • Decrypt with the private key

Public Key Encryption - RSA

  • Key Generation
    • Choose two [large] prime numbers p and q
    • n = p*q
    • λ(n) = lcm(p-1, q-1)
    • Choose e < λ(n) and gcd(e, λ(n)) = 1
    • d = e^{-1} mod λ(n)
  • Share e and n as the public key
  • Keep d as the private key
  • Discard p, q, and λ(n)

Public Key Encryption - RSA

  • Encryption
    • To send a message m
    • Compute c = m^e mod(n)
    • Send c
  • Decryption
    • Receive c
    • Compute m = c^d mod(n)
    • Read m

Public Key Encryption - RSA

  • RSA key generation gives us: m = m^(e*d) mod(n)
  • This means that we can also encrypt with the private key and decrypt with the public key
    • We call this a signature
    • Everyone can decrypt the message so there is no privacy
    • However, there is a guarantee that the author is legitimate (You know I'm the one who sent this message)

Public Key Encryption - RSA

  • What about a brute force attack?
    • Attacker has the public key
    • Keep encrypting "guesses" of the plaintext until the cyphertext matches

Public Key Encryption - RSA

  • What about a brute force attack?
  • Solution: Use a padding algorithm
    • Add random bits to the end of each message
    • Attacker must guess these random bits
    • Adds security!
    • Unlike salting, padding can be kept secret and adds entropy
    • Makes encryption of even short messages secure!

Public Key Encryption - RSA

  • Unlike salting, padding can be kept secret and adds entropy
    • Why?

Public Key Encryption - RSA

  • Unlike salting, padding can be kept secret and adds entropy
  • Cyphertext will be decrypted by the recipient
    • After decrypting, discard the padding and read the message
    • Use a delimiter to indicate the beginning of the padding
  • Hash will never be "unhashed"
    • Cannot identify/discard the salt

Public Key Encryption - RSA

  • Key Generation
    • Choose two [large] prime numbers p and q
    • n = p*q
    • λ(n) = lcm(p-1, q-1)
    • Choose e < λ(n) and gcd(e, λ(n)) = 1
    • d = e^{-1} mod λ(n)
  • Given p, q, and e an attacker can easily compute d (private key)
  • Everyone already has e and n (the public key)
  • So just factor n to get p and q, then compute the private key

Public Key Encryption - RSA

Factoring is hard [We hope]

  • There is no publicly known algorithm that can efficiently factor a number
  • Worst case is factoring the multiplication of two large primes
    • Exactly what RSA relies on for security
  • It has not been proven that factoring is a "hard" problem
    • Quantum computers can factor efficiently
  • We call the factoring problem a cryptographic primitive

Public Key Encryption - RSA

  • Encryption
    • To send a message m
    • Compute c = m^e mod(n)
    • Send c
  • Everyone knows e and n (The public key)
  • An attacker can read c if they are within wifi range
  • Just have to compute the discrete log_e of c mod n

Public Key Encryption - RSA

Computing a Discrete Log is hard [We hope]

  • There is no publicly know algorithm that can efficiently compute discrete logarithms
  • This problem is another cryptographic primitive

Further Reading