Cryptanalysis and Brute-force Attacks in Cryptography

Cryptanalysis

• Relies on the nature of the algorithm and knowledge of properties of plain text or even knowledge of sample plaintext-ciphertext pairs
• Types of cryptanalytic attacks:
  • Ciphertext-only attack: only know algorithm and ciphertext, statistical knowledge about plaintext type
  • Known plaintext attack: know/suspect plaintext and ciphertext to attack cipher
  • Chosen plaintext attack: select plaintext and obtain ciphertext to attack cipher
  • Chosen ciphertext attack: select ciphertext and obtain plaintext to attack cipher
  • Chosen text attack: select either plaintext or ciphertext to en/decrypt to attack cipher

Brute Force Search

• Always possible to try every key
• Most basic attack, proportional to key size
• Assume either know or recognize plaintext
• Examples: DES, AES, 3 DES

Classical Substitution Ciphers

• Replace letters of plaintext with other letters, numbers, or symbols
• Example: Caesar Cipher
  • Substitutes each letter by 3rd letter on
  • Can define transformation mathematically
  • Only have 26 possible ciphers, can try each in turn (brute force search)
  • Recognize when have plaintext

Monoalphabetic Cipher

• Shuffle the alphabet arbitrarily
• Single cipher alphabet is used per message
• Key is 26 letters long
• Example: Plain: abcdefghijklmnopqrstuvwxyz, Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN
• Security: total of 26! possibilities
• Use single, double, and triple letter frequencies to cryptanalyze

English Letter Frequencies

• Discovered by Arabian scientists in 9th century
• Calculate letter frequencies for ciphertext
• Compare counts/plots against known values

Example Cryptanalysis

• Given ciphertext, count relative letter frequencies
• Guess P & Z are e and t
• Guess ZW is th and hence ZWP is the
• Proceed with trial and error to get plaintext

Transposition Ciphers

• Hide the message by rearranging the letter order
• Recognize since have the same frequency distribution as the original text
• Example: Rail Fence cipher
  • Write message letters out diagonally over a number of rows
  • Read off cipher row by row
• Example: Row Transposition cipher
  • Write letters of message out in rows over a specified number of columns
  • Reorder the columns according to some key before reading off the rows

Product Ciphers

• Using several ciphers in succession to make harder
• Two substitutions make a more complex substitution
• Two transpositions make a more complex transposition
• A substitution followed by a transposition makes a new much harder cipher

Steganography

• Hides existence of message
• Examples:
  • Use only a subset of letters/words in a longer message marked in some way
  • Invisible ink
  • Hiding in LSB in a graphic image or sound file
• Drawbacks: high overhead to hide relatively few info bits

Symmetric Encryption

• Sender and recipient share a common key
• All classical encryption algorithms are private-key
• Basic terminology:
  • Plaintext: original message
  • Ciphertext: coded message
  • Cipher: algorithm for transforming plaintext to ciphertext
  • Key: info used in cipher known only to sender/receiver
  • Encipher (encrypt): converting plaintext to ciphertext
  • Decipher (decrypt): recovering plaintext from ciphertext
  • Cryptography: study of encryption principles/methods
  • Cryptanalysis (codebreaking): study of principles/methods of deciphering ciphertext without knowing key
  • Cryptology: field of both cryptography and cryptanalysis

Symmetric Cipher Model

• Two requirements for secure use:
  • Strong encryption algorithm
  • Secret key known only to sender/receiver
• Cryptography can be characterized by:
  • Type of encryption operations used (substitution, transposition, product)
  • Number of keys used (single-key or private-key, symmetric; two-key or public, asymmetric)
  • Way in which plaintext is processed (block, stream)

How to Attack Secret-Key Encryption

• Brute force search
• Cryptanalysis
• Other methods