Cryptography, Padding Oracles

Notes

Secret messages

• First, simply hide the message:
  • Herodotus wrote of messages written on wood and covered in wax so that they appeared blank and, more outlandishly, writing a message on someone's head and waiting for their hair to regrow, swallowing balls of silk sealed in wax, invisible ink, etc.
  • Known as Steganography (steganos = covered, graphein = to write)
  • Works quite well but has a fundamental weakness: if the message is discovered, all information is revealed
• So the development of Cryptography (kryptos = hidden), the message is not hidden but its meaning is
• Transposition and substitution:
  • Transposition: where the letters retain their identity but change position, e.g. using a scytale
  • Substitution: where the letters retain their position but change their identity, e.g. the Caesar cipher
• To simplify sharing algorithms (e.g. a substitution alphabet), can introduce the idea of a key which helps generate the substitution, e.g. a key word/phrase for the Caesar cipher
• Attack on substitution cipher if we know the language of the plain text: frequency analysis both of letters and pairs of letters (digrams), trigrams, etc.
• No eavesdropping
• No tampering
• Symmetric encryption
• E(k, m) = c
• D(k, c) = m
• E is the encryption cipher, k is the secret key, m is the plaintext
• D is the decryption cipher, k is the secret key, c is the ciphertext
• Vigenère cipher uses multiple Caesar ciphers
• One-Time Pad: use key as long as message, XOR with the plaintext, produce a ciphertext, it has "perfect secrecy", it gives no information about the plaintext from the ciphertext apart from message length
• Problem is, have to have a long key and how are you going to share that safely?
• Stream ciphers
• Pseudo-random number generators

References

• Simon Singh, "The Code Book"
• Dan Boneh, Stanford University, "Cryptography I"
• Rob Heaton, "The Padding Oracle Attack - why crypto is terrifying"