Report

Cryptanalysis Aaron Willett What is Cryptology? • Cryptography (Encryption) ▫ the practice and study of techniques for secure communication in the presence of third parties • Cryptanalysis (Decryption) ▫ the art of defeating cryptographic security systems, and gaining access to the contents of encrypted messages, without being given the cryptographic key. History Early Cryptology • Scytale • Julius Caesar • Vigenere Square Vigenere Square Cryptology circa WWII • German Enigma • Bombe • Japanese Red, Orange, Purple Types • • • • Ciphertext-only attack Chosen-ciphertext attack Known-plaintext attack Chosen-plaintext attack Ciphertext-Only Attack • Attacker has access to a set of ciphertexts • Guess-and-check • Frequency Analysis Example 1 Plaintext: HEREISANEXAMPLEOFAFREQUENCYANALYSIS Ciphertext: XTJTWICNTDCQLSTMOCOJTKGTNYBCNCSBIWI English Frequency Table Ciphertext Frequency Table Example 2 • Sub1.pdf • Sub2.pdf • Sub3.pdf Chosen-Ciphertext Attack • Tries to discover the key • Uses ciphertext chosen by attacker • Relies on being able to obtain decrypted plaintext • Two variations Lunchtime Attack • Euphemism “Away on Lunch” • Attacker can make queries but only up until a certain point, after which the attacker must demonstrate some improved ability to attack the system. • Attacker cannot adapt queries ▫ Results given after the ability to makes queries expires Adaptive Chosen-Ciphertext • Similar to normal chosen-ciphertext • Ciphertext is chosen based on the result of the previous query Known-Plaintext Attack • Attacker has the ciphertext and some samples of plaintext • Apply the known plaintext to the ciphertext to help decryption • Preferred over ciphertext-only Example 3 • Plaintext: This is encrypted using a ROT3 Caesar Cipher • Ciphertext: Wklv lv hqfubswhg xvlqj d URW3 Fdhvdu Flskhu • Known-Plaintext: Caesar • By knowing ‘Caesar’ one can make educated assessments • Compare length, frequency of letters, patterns ▫ ROT3 pattern Chosen-Plaintext Attack • Chooses plaintext and receives corresponding ciphertext • Not always viable (E.g. Enigma WWII) • Two variations Chosen-Plaintext Attack • Batch Chosen-Plaintext ▫ Attacker chooses a “batch” of plaintexts before any encrypted ciphertext is received • Adaptive chosen-plaintext ▫ Attacker makes n-amounts of interactive queries and alters their plaintext based on the previous query Methods • • • • Classical Cryptanalysis Symmetrical Cryptanalysis Hash Functions External Attacks Classical Cryptanalysis • Frequency Analysis • Index of Coincidence • Kasiski Examination Index of Coincidence • Useful method to find the length of a key for Vigenere or Beaufort ciphers • Shifts the cipher text one position until circled back • Counts the occurrences of letters that are in the same position between the shifted ciphertext and the original • A high index of coincidence shows multiples of the key length Example 4 *Example courtesy of http://www.murky.org/blg/2004/10/index-of-coincidences-a-worked-example/ Ciphertext • VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT ATOUT GLPKO FHNSO KBHMW XKTWX SX Shifts • Original: VKMHGQFVMOIJOIIOHNSNIZXSSCSZEA... Shift 1: KMHGQFVMOIJOIIOHNSNIZXSSCSZEAW... Shift 2: MHGQFVMOIJOIIOHNSNIZXSSCSZEAWW... Shift 3: HGQFVMOIJOIIOHNSNIZXSSCSZEAWWE... Shift 4: GQFVMOIJOIIOHNSNIZXSSCSZEAWWEX... Shift 5: QFVMOIJOIIOHNSNIZXSSCSZEAWWEXU... Shift 6: FVMOIJOIIOHNSNIZXSSCSZEAWWEXUL... Shift 7: VMOIJOIIOHNSNIZXSSCSZEAWWEXULI... Index of Coincidence Shift Coincidences • 1 ________________________ • 2 ________________________ • 3 ________________________ • 4 ________________________ • 5 ________________________ • 6 ________________________ • 7 • 8 ________________________ • 12 ________________________ • 11 ________________________ • 13 ________________________ • 19 ________________________ • 25 ________________________ • 11 Kasiski Examination • Similar to finding the index of coincidence • Searches for repeated sequences of letters greater than 3 • Record the distance between occurrences • Attempt to find a common factor Symmetric Algorithms • • • • • • • • • • Boomerang Attack Brute Force Attack Davies' Attack Differential Cryptanalysis Integral Cryptanalysis Linear Cryptanalysis Meet-in-the-middle Attack Mod-n Cryptanalysis Slide Attack XSL Attack Brute Force Attack • Attacker runs trials against a cryptosystem for all possible keys • Sometimes infeasible • Time consuming Key Length vs Brute Force Combinations Differential Cryptanalysis • Useful against block and stream ciphers ▫ AES, DES, Blowfish, RC4 • Chosen-plaintext attack • Feeds plaintext pairs into the cryptosystem and analyzes the difference defined by the XOR operation • Analyzing the results suggests possible key values Linear Cryptanalysis • Also useful against block and stream ciphers • Develop linear equations that relate the plaintext and the ciphertext to certain key bits • Derive other key bits from these equations • Brute force Hash Functions • Passwords are commonly saved in hash tables • Two methods to crack hash functions ▫ Birthday Attack ▫ Rainbow Table Birthday Attack • Exploits the birthday paradox • Goal is to find two arbitrary inputs that yield the same hash value ▫ Known as a hash collision • Useful when an attacker wants to modify a document with a digital signature Birthday Paradox • As an example, consider the scenario in which a teacher with a class of 30 students asks for everybody's birthday, to determine whether any two students have the same birthday (corresponding to a hash collision as described below; for simplicity, ignore February 29). Intuitively, this chance may seem small. If the teacher picked a specific day (say September 16), then the chance that at least one student was born on that specific day is , about 7.9%. However, the probability that at least one student has the same birthday as any other student is nearly 70% (using the formula Example 5 • Mallory creates two documents X and Y, which have the same hash value. Mallory sends document X to Alice who verifies the document, signs it, and returns it to Mallory. Mallory then copies the digital signature from document X to document Y and sends document Y to Bob. The signature on document Y matches the document hash so Bob's software cannot detect any modifications done to the document. Rainbow Table • Pre-computed table used for reversing hash functions • Typically used for cracking password hashes • Infeasible when a salt is added to a password Rainbow Tables for Ophcrack • Alphanumeric – 388 MB ▫ 80 Billion hashes; 12 septillion passwords • Extended – 7.5 GB ▫ Contains !"#$%&'()*+,-./:;<=>?@[\]^_`{|} ~ ▫ 7 trillion hashes; 5 octillion passwords External Attacks • Crude, non-mathematical methods • Black-bag and rubber-hose • Black-bag is a euphemism for the acquisition of cryptographic secrets through theft ▫ Key-logging, trojan horse, physically stealing • Rubber-hose uses torture and coercion to obtain information ▫ Humans are the weakest link Questions?