cryptography Cryptanalysis Version: 1.0.2 On this page
Cryptanalysis Process of decryption of ciphers and encrypted text Identifies vulnerabilities in cryptosystems Cryptanalytic techniques Linear cryptanalysis Known as plaintext attack Applicable to block ciphers and stream ciphers. Given enough pairs of plaintext and corresponding ciphertext, key can be obtained Discovered by By Matsui and Yamagishi in 1992 Attacker identifies the linear relation between some bits of the plaintext, some bits of the ciphertext and some bits of the unknown key. Differential cryptanalysis Discovered by Israeli researchers Eli Biham and Adi Shamir in the late 1980s. Applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. Applicable to symmetric key algorithms Comparing differences in the inputs to how each one affects the outcome Working with chosen plaintext originally, also works with known plaintext and ciphertext Integral cryptanalysis Used on block ciphers Discovered by Lars Knudsen in 1997 Input vs Output comparison same as differential, however, runs multiple computations of the same block size input Attacker analyzes outputs of encrypting sets of plaintexts where some of the content is held constant and some of the content is varied through all possibilities Code-breaking methodologies Frequency analysis Study of the frequency of letters or groups of letters in a ciphertext E.g. checking cipher chunks against in languages some letters or combination of letters are used more often Can be used to crack a substitution cipher, like rotation cipher ROT13 Trickery and deceit Requires a high level of mathematical and cryptographic skills Using social engineering techniques to trick someone to encrypt and send a known message One-time pad A shared random key that has to be the same length or longer than the cipher text Each individual bit or character of plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition Assuming to be unbreakable Drawback Key distribution becomes impracticable for large messages as key length is same as as the messages Cryptography attacks Chosen-key Attack 📝 Attacker knows keys that are used or can choose the secret key. May allow breaking the larger system which relies on that cipher Rubber-hose attack Also known as rubber hose or rubberhose attack. 📝 Extraction of cryptographic secrets (e.g. the password to an encrypted file) from a person by coercion or torture E.g. beating that person with a rubber hose until they give up the encryption key. Ciphertext-only attack (COA) Also known as known ciphertext attack 📝 Attacker has only access to cipher texts E.g. using frequency analysis to assume plain text Early ciphers (using pen-and-paper) were cracked this way Modern ciphers have strong protections against ittake years to separate statistical departure from random noise Known-plaintext attack (KPA) Also known as known-plain-text attack 📝 Attacker has access to parts of plaintext and corresponding ciphertext. Can be used to reveal secret keys, code books. Classical ciphers are typically vulnerable Meet-in-the-middle attack Also known as meet in the middle attack . Attack over certain block ciphers by decomposing the problem in two halves and proceeds on each part separately Reduces the effort to perform a brute-force attack 📝 Reason why re-encrypting an ciphertext reduces its securityThe reason that Triple DES or Double DES is considered weak and are no longer used. E.g. transforming an attack that requires 2exp128 time into one that takes 2exp64 time and 2exp64 space Type of known-plaintext attack Chosen-plaintext attack (CPA) 📝 Attacker can choose random plaintexts to be encrypted and obtain the corresponding ciphertexts 📝 Two formsBatch chosen-plaintext attack Cryptanalyst chooses all plaintexts before any of them are encrypted. Not so effective Adaptive chosen-plaintext attack Cryptanalyst makes a series of interactive queries Subsequent plaintexts are chosen based on the information from the previous encryptions. Chosen-ciphertext attack (CCA) Also known as chosen ciphertext attack or chosen-cipher-text attack . Attacker gathers information by obtaining the decryptions of chosen ciphertexts. Early versions of RSA padding used in the SSL protocol were vulnerable. TypesAdaptive chosen-ciphertext (CCA2) Attacker uses the results from prior decryptions to inform their choices of which ciphertexts to have decrypted Non-adaptive chosen-ciphertext Attacker chooses the ciphertexts to have decrypted without seeing any of the resulting plaintexts Lunchtime attack or midnight attack Attacker can have access to system for only a limited amount of time, can access only few plaintext-ciphertext pairs Side-channel attacks Timing attack Execution times are measured to learn more about the system Information to find can include e.g. key, CPU used, algorithms, input, implementation details etc. A type of side-channel attack Brute-force attack Birthday Attack Type of brute-force attack but faster that focuses on collisions Based on collisions where attacker uses own plain texts to match hashes (find collisions) Depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations Exploits birthday problem in probability theoryE.g. 23 people in room, chance of two having same birthday is not 23 / 365 = ≈6% but it's 50%. For 75 people it's 99% chance. Rainbow table attack 📝 Rainbow table contains precomputed hashes to try and find out passwords Faster than brute-force however the trade-off is that it takes a lot of storage (sometimes Terabytes) to hold the Rainbow Tables themselves. Tools Dictionary attack Attacker creates and uses a dictionary of plaintext and its ciphertext. E.g. words in a dictionary E.g. previously used passwords, often from lists obtained from past security breaches Attacker observes the operation of a cipher under several different keys Some relationship connecting the keys is known to attacker while key values are unknown. E.g. attacker knows that last 80 bits of the keys are the same DUHK Attack (Don't Use Hard-Coded Keys) Allowing attackers to access keys and read communications in certain VPN implementations Based on vulnerability affecting devices using ANSI X9.31 Random Number Generator (RNG) with a hard-coded seed key Collision attack Also known as hash collision attack 📝 Tries to find two inputs resulting in same hash value, i.e. a hash collision.Find two different messages m1 and m2 such that hash(m1) = hash(m2). Extended by chosen-prefix collision attack Given two different prefixes p1, p2The attack finds two appendages m1 and m2 such that hash(p1 ∥ m1) = hash(p2 ∥ m2)where ∥ is the concatenation operation. More powerful 💡 The larger the hash value size, the less likely there are for collisions to occur and therefore the more collision resistant the hash algorithm L0phtcrack Password cracking tool Used mainly against Windows SAM files 📝 John the Ripper CrypTool Open-source program for for cryptography and cryptanalysis GUI to experiment with cryptographic procedures and to animate their cascades Cryptobench Encrypt, decrypt, hash using many algorithms Helps in the cryptanalysis process of common cryptographic schemes