FIT3173: Cryptographic Pitfalls
Dr Fariha Department of Software Systems and Cybersecurity
Faculty of Information Technology
Copyright By PowCoder代写 加微信 powcoder
Learning Outcomes of This Lecture
• Understand how to use cryptographic hash functions properly in different application contexts
• Know the properties of poor and good random number generator
• Analyse Key/IV re-use vulnerability in stream cipher
• Learn modes of AES (Advanced Encryption Standard) and Padding Oracle Vulnerability
Cryptographic (One-way) Hash Functions
• Essential building block in cryptography
• One-way and collision resistant properties
• Usage example:
• Password authentication • Integrity preservation
• Blockchain
Difference from Hash Function
• Hash function: maps arbitrary size data to data of fixed size • Example: f(x) = x mod 1000
Security Properties
• One-way Hash Properties:
• One-way: hash(m) = h, difficult to find m
• Collision resistant: Difficult to find m1 and m2 s.t. hash(m1) = hash(m2)
MD One-Way Hash Functions • MD stands for Message Digest
• Developed by
• Includes MD2, MD4, MD5, and MD6 • Status of Algorithms:
• MD2, MD4 – severely broken (obsolete)
• MD5 – collision resistance property broken, one-way property not broken • MD6 – developed in response to proposal by NIST
• Published by NIST
• Includes SHA-0, SHA-1, SHA-2, and SHA-3
• Status of Algorithms:
• SHA-0: withdrawn due to flaw
• SHA-1: Designed by NSA; Collision attack found in 2017
• SHA-2: Designed by NSA; Includes SHA-256 and SHA-512; Other truncated versions; No significant attack found yet
• SHA-3: Released in 2015; Has different construction structure (compared to SHA-1 and SHA-2)
How One-Way Hash Algorithm Works
• Construction method called Merkle–Damgard
• Used by algorithms like MD5, SHA-1, and SHA-2
Applications of One-Way Hash Functions
• Integrity Verification
• Committing a Secret Without Telling It • Password Verification
• Trusted Timestamping
Integrity Verification • Changing one bit of the original data changes hash value
• Usage examples:
• Detect change in system files
• Detect if file downloaded from website is corrupted
Committing a Secret Without Telling It One-way property
• Disclosing the hash does not disclose the original message
• Useful to commit secret without disclosing the secret itself
• Usage Example – Stock Market
• Need to make prediction about the stock market about a certain day • Publish the hash of the secret on your website
• On the particular day, release the secret
• Your audience can verify it against the hash
Password Verification
• To login into account, user needs to tell a secret (password)
• Cannot store the secrets in their plaintext
• Need for:
• Password storage where nobody can know what the password is
• If provided with a password, it verified against the stored password
• Solution: one-way hash function
• Example: Linux stores passwords in the /etc/shadow file
Linux Shadow File
• Password field has 3 parts: algorithm used, salt, password hash • Salt and password hash are encoded into printable characters
• Multiple rounds of hash function (slow down brute-force attack)
• Purpose of Salt
• Using salt, same input can result in different hashes
• Password hash = one-way hash rounds (password || random string) • Random string is the salt
• Attacks Prevented by Salt • DictionaryAttack
• Put candidate words in a dictionary
• Try each against the targeted password hash to find a match • RainbowTableAttack
• Precomputed table for reversing cryptographic hash functions
Trusted Timestamping
• Need: How to prove that a document existed prior to certain date ? • Timestamping approaches:
• Approach # 1: Publish one-way hash (instead of document) in a newspaper
• Approach # 2: Time Stamping Authority can sign the document hash using private key • Approach # 3:
• Use Blockchain i.e. a growing list of record (blocks) • Publish document hash in a block
• Blockchain depends on one-way hash
Message Authentication Code (MAC)
• Network communication can encounter MITM attacks • MITM can intercept and modify data
• Receiver needs to verify integrity of data
• Attach tag to data
• Using one-way hash as tag won’t work because MITM can recompute hash • Use a shared secret (key) between sender and receiver in the hash
• MITM cannot compute hash without secret key
Case Study: Mac for Authentication
Case Study: Mac for Authentication
• Alice checks the MAC sent from Bob: identify the sender is : Is it secure in the network environment? If the attacker obtains Bob’s MAC and replays it?
Random Number Generator
• Cryptography algorithms need “good” random numbers for various tasks:
• Generating hard to predict secret keys
• Generating hard to predict random “salts” / randomness, e.g., for password hashing, randomised encryption, digital signatures
• What are “good” random numbers?
• Uniformly (evenly) distributed bits / numbers
• Hard to predict the next random bit / number after observing past bits / numbers
Random Number Generator
• Random numbers are generated in software using a pseudorandom number generator in two phases:
• Initialisation: Initialise state with a short truly random input seed (need initial randomness source)
• Generation: Update state with some fixed (deterministic) function and output part of the state as a pseudorandom number
Random Number Generator
• Initialisation security vulnerabilities:
• Using an easy-to-guess initial seed for pseudorandom numbers
• Devastating consequences: If attacker guesses seed, gets all pseudorandom numbers used in the application (e.g. all secret keys).
• Bad examples
• Generating seed for encryption keys from time of day/seconds/microseconds (220 possibilities for 20 bits), process id (easily obtained from ps command)
Random Number Generator • Generation security vulnerabilities:
• Bad mathematical choices for pseudorandom generator state update function
• Makes it easy to predict the next pseudorandom number given some previous outputs • A good pseudorandom number generator has the following properties:
• It generates “evenly distributed” numbers; • The values are unpredictable;
• Long and complete cycle;
• Linear congruential generators meet the first property but fail the second one. • Xn+1 = (aXn+c) mod m
Good Pseudorandom Numbers
• Use a standard cryptographically-secure (unpredictable) pseudorandom number generator
• Cryptographically strong algorithm based on SHA-2 hash function defined in the NIST standard in standard cryptography libraries, e.g., use CryptGenRandom in Windows
• Make sure pseudorandom generator seed has enough randomness (usually > 128 bits).
• Warning: after the first OS boot, most system parameters are likely to be highly predictable (initial default values)
• Reason for observed predictability of some SSL/TLS user keys: 64,000 TLS hosts used almost identical private keys. https://factorable.net/weakkeys12.extended.pdf
• Hardware True Random bit solution in newer Intel (>~2012) and AMD (>~2015) CPUs: Intel `Secure Key’ (RDRAND/RDSEED) CPU instructions
• Key/IV re-use vulnerability in stream cipher
Symmetric Cryptosystem • Scenario
• Alice wants to send a message (plaintext P) to Bob.
• The communication channel is insecure and can be eavesdropped
• If Alice and Bob have previously agreed on a symmetric encryption scheme and a secret key K, the message can be sent encrypted (ciphertext C)
• What is a good symmetric encryption scheme?
• What is the complexity of encrypting/decrypting?
• What is the size of the ciphertext, relative to the plaintext?
• Consistency
Symmetric Cryptosystem
• Efficiency
• encrypt and decrypt should be efficient
• Decrypting the ciphertext yields the plaintext (plaintext length typically the same as ciphertext length)
One-Time Pad
• There is one type of cipher that is absolutely unbreakable.
• One-time pad was invented in 1917 by and
• We use a block of shift keys, (k1, k2, . . . , kn), to encrypt a plaintext, M, of length n, with each shift key being chosen uniformly at random.
• Since each shift is random, every ciphertext is equally likely for any plaintext.
Key Plaintext
Ciphertext
One Time Pad
Q: Any weaknesses?
Weakness of One-Time Pad
• The key has to be as long as the plaintext • Keys can never be reuse
• Repeated use of one-time pads allowed U.S. to break some of the communications of Soviet spies during the Cold War.
• Problems in generation & safe distribution of keys
Symmetric Cryptosystem
• n: nonce (aka IV)
• Encryption algorithm is publicly known
• Never use a proprietary cipher
• Problem: OTP key is as long the message
• Solution: Pseudo random key – stream ciph ers
• Suitable for plaintext of arbitrary length generated on the fly, e.g., media stream
• Process input elements in parallel
Stream Cipher
Stream ciphers: RC4 (113MB/sec), SEAL (293MB/sec)
Key Reuse Vulnerability
• “Two time pad” is insecure: • c1<-m1⊕PRBG(K)
• c2<-m2⊕PRBG(K)
• Eavesdropper does:
• c1 ⊕ c2 -> m1 ⊕ m2 (enough redundant information in English for message recover)
Case Study: IEEE 802.11b Security WEP
• key: 40 bits
• IV: 24 bits
• seed = IV||key = 64 bits
• ciphertext c = p ⊕ RC4(IV, key)
Security Analysis of WEP • Prevent keystream reuse
• if p1 known,
• then p2 will be known
• per packet IV
• Intercepting Mobile Communications: The Insecurity of 802.11, Boris, Goldberg, Wagner, Mobicom 2001, ACM; http://www.isaac.cs.berkeley.edu/isaac/mobicom.pdf
InSecurity of WEP
• IV by design, very short: 24 bits (possible unique values 224 for 16,777,216 packets)
• Assume that a wireless access point sending • 1500-byte packets at 5Mbps
• 416 packets per second
• 25,000 packets per minute
• 1,500,000 packets per hour • 36,000,000 packets per day
• Modes of AES
• In a block cipher:
Block Ciphers
• Plaintext and ciphertext have fixed length b (e.g., 128 bits)
• A plaintext of length n is partitioned into a sequence of m blocks, P[0], …, P[m-1],wheren