Professor Sanjay K. Jha
WK01: Crypto Building Blocks
Securing Fixed and Wireless Networks, COMP4337/9337
School of Computer Science and Engineering, UNSW
Copyright By PowCoder代写 加微信 powcoder
Today’s Agenda
• Learn Crypto building blocks for
• Confidentiality and Authentication :Secret Keys
• Integrity: Message Digests (Hash)
• Integrity and Authentication: HMAC, MAC
• Non-Repudiation: Digital Signature
• Block Ciphers
Security Fundamentals (recap)
• confidentiality: only sender, intended receiver should “understand” message contents
• authentication: sender, receiver want to confirm identity of each other
• message integrity: sender, receiver want to ensure message not altered (in transit, or afterwards) without detection
• non-repudiation: no one (including the sender) can deny that message was sent by the sender
• access and availability: services must be accessible and available to users
Public Key Cryptography
KB- Bob’sprivate key
Bob’s public key
plaintext ciphertext
message, m K+(m) B
plaintext message
encryption algorithm
decryption algorithm
m = K B- ( K B+ ( m ) )
Public key encryption algorithms
• Need KB+ (.) and KB- (.) such that
given public key, it should be impossible to compute private key
RSA: Rivest, Shamir, Adelson algorithm More on Public Key in later week
K (K (m)) = m
Symmetric Key Cryptography
plaintext message, m
ciphertext
m = KS(KS(m))
encryption algorithm
decryption algorithm
symmetric key crypto: Bob and Alice share same (symmetric) key: K S
Q: how do Bob and Alice agree on key value?
Session Keys
• Public-keycryptographyiscomputationally intensive as compared to symmetric key crypto
• Exponentiationiscomputationallyintensive
• SymmetricAlgorithmsmuchfasterthanRSA
Session key, KS
• Bob and Alice use RSA to exchange a symmetric key KS
• OncebothhaveKS,theyusesymmetrickey cryptography
Confidentiality vs Integrity
• Confidentiality: message private and secret
• Integrity: protection against message tempering
• Encryption alone may not guarantee integrity
– Attacker can modify message under encryption without learning what it is
• Public Key Crypto Standards (PKCS)
o “RSA encryption is intended primarily to provide confidentiality… It is not intended to provide integrity”
• Both Confidentiality and integrity are needed for security
Example on Integrity
Tmpered File
Hash(Good File)
• Software distribution protection:
– For a Good File and Hash(Good File), it is infeasible to find a Tampered File (containing rootkit or Trojan) such that Hash(Good File) = Hash(Tampered File)
Hash/Message Digests (MD)
• Function H( ) that takes as input an arbitrary length message and outputs a fixed-length string: “message signature”
• The values returned by H( ) are called hash values, hash codes, digests, or simply hashes.
• Note that H( ) is a many-to-1 function
• H( ) is often called a “hash function”
• Desirable properties:
– Easy to calculate
– Irreversibility: Can’t determine m from H(m)
– Collision resistance: Computationally difficult to produce m and m’ such that H(m) = H(m’)
– Seemingly random output 10
large message m
H: Hash Function
MD Randomness
Message digest of a hashing should have a random pattern
• Randomness: any bit in digest is “1” half the time
• Change input only one bit, and the hash will change half of the digest bits
• Diffusion: if hash function does not exhibit the avalanche effect to a slight change of input, then it has poor randomization, and thus a cryptanalyst can make predictions about the input, being given only the output
Poor Crypto Hash Example
Internet checksum has some properties of hash function:
• produces fixed length digest (16-bit sum) of message
• is many-to-one
But given message with given hash value, it is easy to find another message with same hash value:
I O U 1 0 0 . 9 9 B O B
ASCII format
49 4F 55 31 30 30 2E 39 39 42 D2 42
B2 C1 D2 AC
I O U 9 0 0 . 1 9 B O B
different messages but identical checksums!
ASCII format
49 4F 55 39 30 30 2E 31 39 42 D2 42
B2 C1 D2 AC
Standard Hash Function History
MD2 (128), 1989
MD4 (128), 1990
MD5 (128), 1991
No need to memorise thisJ WK 01-03
RIPEMD(160, 256, 320), 2003
SHA-0, 1993
SHA-1 (160), 1995
SHA-2 (224, 256, 384, 512), 2001
SHA-3 (new standard 2015)
Example: SHA-256
• Plaintext
Phishing Explained
Phishing scams are typically fraudulent e-mail messages appearing to come from legitimate sources like your bank, your Internet Service Provider, eBay, or PayPal, for example. These messages usually direct you to a fake web site and ask you for private information (e.g., password, credit card, or other account updates). The perpetrators then use this private information to commit identity theft.
Warning Signs ……….
URLs Don’t Match – Place your mouse over the link in the e-mail message. If the URL displayed in the window of your browser is not exactly the same as the text of the link provided in the message, run. It’s probably a fake. Sometimes the URLs do match and the URL is still a fake.
• Digest in BASE64
Tx9S2IwqlrGI7hhNJ4s5K7qiYt3PjQSD6vWH4QBl7
• The corresponding digest in binary format is listed as follows:
101011000101011001111001110100000011101000011110110111010010100101101111101101000100001 000100110110000101100110101011011001001101111000100110011011001010100110100011101001101 1011110101100000001101100010111010011011111111110100110111100001100101001
Example: Diffusion in SHA-256
• Plaintext: only change the first letter from P to Q Qhishing Explained
Phishing scams are typically fraudulent e-mail messages appearing to come from legitimate sources like your bank, your Internet Service Provider, eBay, or PayPal, for example. These messages usually direct you to a fake web site ……….
URLs Don’t Match – Place your mouse over the link in the e-mail message. If the URL displayed in the window of your browser is not exactly the same as the text of the link provided in the message, run. It’s probably a fake. Sometimes the URLs do match and the URL is still a fake.
• Digest in BASE64 changes from
Tx9S2IwqlrGI7hhNJ4s5K7qiYt3PjQSD6vWH4QBl7yg =
AAHew/sW6W4X39EQq7ctFEb3PyHxka+T3D1UQJhDkw =
• The corresponding digest in binary format is listed as follows:
101001001100101110001011010100010010110011001111101000000100101101101110010 110001011000001001100111001100101100111001000001000010100010101000011011111 010100101101101111111111111110111011111011010011000000100000111100101110110 011001011010111111010000010000
Basic Structure of SHA-1
For illustration, not examinable, details in Wu/Irwin text
Against padding attacks
Message length (K mod 264)
L x 512 bits = n x 32 bits K bits
Split message into 512-bit blocks
(1 to 512 bits)
…. 512 bits
512 bits Y0
512 bits ….
512 bits 1
H….160 . Hi
H….160 . HL-1
H 160 160-bit
160-bit buffer (5 registers) initialized with magic values
Hash function
Applied to each 512-bit block and current 160-bit buffer.
SHA properties
Algorithm Name
Max. Message Size (bits)
Block Size (bits)
Word size (bits)
Digest size (bits)
No need to memorise this J, appreciate and consult table as needed We will see some related practical issues in WEP protocol later.
Note: 160 bit digest is consider unsafe with fast computers.
If interested in crypto maths, read more on speed of execution of various schemes, whic ones can be attacked by Quantum computers.
Attacks on Hash (Self study/no-exam)
• MD5 is one of the most widely used cryptographic hash functions
• Attack on MD5 to find collisions efficiently
– Xiaoyun Wang, : How to Break MD5 and Other Hash Functions. EUROCRYPT 2005: 19- 35
– Xiaoyun Wang, , , , : Cryptanalysis of the Hash Functions MD4 and RIPEMD. EUROCRYPT 2005: 1-18
– Xiaoyun Wang, Yiqun Lisa Yin, : Finding Collisions in the Full SHA-1. CRYPTO 2005: 17-36
– Xiaoyun Wang, , Yiqun Lisa Yin: Efficient Collision Search Attacks on SHA-0. CRYPTO 2005: 1- 16
– , Gaoli Wang, , Xiaoyun Wang: The Second- Preimage Attack on MD4. CANS 2005: 1-12
– About 15 minutes up to an hour computation time
– Finding a collision for MD5 is easily feasible
• This attack is also able to break hash functions efficiently, including HAVAL-128, MD4, RIPEMD, SHA-0 and SHA-1
• SHA-1 near-collision attack needs 257.5 hashes
– : HashClash on 21/2/2019 – https://marc-stevens.nl/p/hashclash/
– SHA-1Chosen-prefixcollisionattack: 277.06
Integrity vs Authentication
• Suppose Alice creates msg m, and calculates hash H(m) using a hash function (e.g. SHA-1)
• Alice send the extended message (m, H(m)) to Bob
• Bob upon receipt of this message independently calculates
H(m’) from the message
• If H(m) = H(m’), message integrity verified.
• What if Trudy intercepts the original message, replaces it with a new message n and its hash H(n) ?
– Keyed-hash message authentication code: a message authentication code that uses a cryptographic key in conjunction with a hash function
oRuns data and authentication key through hash function twice
– Hashing is faster than encryption in software
– Allow the use of any hash function, e.g., SHA-256, or SHA-512
– No US export restrictions on HMAC and hash • Used in TLS and IPSec (later weeks)
• FIPS 198, RFC 2104
Secret key padded to block size
1st Magic mask (flips half of key bits)
2nd Magic mask
(flips different key bits)
Hash function
Src: : figure 20.6
SHA-1 HMACK(M)
hash(key, hash(key, message))
Pad to 512 bits So
For illustration, not examinable, details in Wu/Irwin text
512 bits Y0
512 bits Y1 YL–1
Block size of embedded hash function
HMAC: Integrity and Authentication
(shared secret) s
s • (shared secret) •
public Internet
Authenticates sender
Verifies message integrity
• No encryption ! – Confidentiality not always needed
• Also called “keyed hash”
• Please note that HMAC take both message and key as input, not a simple concatenation.
Integrity of files using HMAC
• UsethefollowingkeyinASCIIformat.
TigersFootballWarEagleBCSChampio
• ThecorrespondingHexformatforthekeyis
546967657273466F6F7462616C6C5761724561676C65424353436 8616D70696F
Example: HMAC-SHA-256
• Plaintext
Phishing Explained
Phishing scams are typically fraudulent e-mail messages appearing to come from legitimate sources like your bank, your Internet Service
• HMACDigestinBASE64
HadCmwGX9EGKBon0C+6XEinXCI8 =
• OnlychangethefirstcharfromTigertoSigerin key, HMAC Digest in BASE64
Ar89wBq+6rxq4Eenho53TMiHvSw =
Hash, MAC and HMAC
• One way Hash Function: Doesn’t take any secret key or its operation
– Easy to compute (both hardware and software solutions possible)
– Concatenation of a Secret Key and Message can be passed through a hash function without any need for encryption/decryption for efficiency.
• Message Authentication Code: MAC
– Can use functions like DES, last bits of the cipher-text can be used as code. However, encryption software is slow, hence may be avoided.
• HMAC: Key is XORed with ipad (part of pad) and then concatenated with the message m. This mix is run through a hash function. The result is then concatenated with XOR of Key and opad (part of pad). Now, this whole mix is run through hash function one more time.
Digital signatures
cryptographic technique analogous to hand-written signatures:
• sender(Bob)digitallysignsdocument, establishing he is document owner/creator.
• verifiable,non-forgeable:recipient(Alice)canprove to someone that Bob, and no one else (including Alice), must have signed document
Digital signatures
simple digital signature for message m: – • Bob signs m by encrypting with his private key K ,
creating “signed” message, KB(m)
Bob’s message, m
KB- Bob’sprivate key
Dear Alice
Oh, how I have missed you. I think of you all the time! …(blah blah blah)
!s message, m, signed (encrypted) with his private key
Public key encryption algorithm
Digital signatures
” vsupposeAlicereceivesmsgm,withsignature:m,to” KB(m)
v Alice verifies m signed by Bob by applying Bob’s public key
K toK (m)thenchecksK (K”(m))=m.
v If KB(KB(m) ) = m, whoever signed m must have used Bob’s private key.
Alice thus verifies that:
• Bob signed m
• no one else signed m
• Bob signed m and not m‘ non-repudiation: ”
ü Alice can take m, and signature KB(m) to court and prove that Bob signed m
Digital signature = signed message digest
Bob sends digitally signed message:
Alice verifies signature, integrity of digitally signed message:
large message m
H: Hash function
encrypted msg digest
K- (H(m)) B
Bob’s private key
Bob’s public key
digital signature (encrypt)
large message m
K- (H(m)) B
digital signature (decrypt)
encrypted msg digest
H: Hash function
Symmetric Key Cryptography (contd)
KS message, m
ciphertext K S (m)
m = KS(KS(m))
encryption algorithm
decryption algorithm
Lets look deeper into symmetric ciphers
Two types of symmetric ciphers
• Block ciphers
– Break plaintext message in equal-size blocks
– Encrypt each block as a unit
– Used in may Internet protocols (PGP-secure email, SSL (secure TCP), IPsec (secure net-transport layer)
• Stream ciphers
– encrypt one bit at time – Used in secure WLAN
Block Cipher
• Ciphertext processed as k bit blocks
• 1-to-1 mapping is used to map k-bit block of
plaintext to k-bit block of ciphertext
• E.g: k=3 (see table)
– 010110001111 => 101000111001
• Possible permutations = 8! (40,320)
• To prevent brute force attacks – Choose large k (64, 128, etc)
• Full-block ciphers not scalable
– E.g., for k = 64, a table with 264 entries required
– instead use function that simulates a randomly permuted table
Cipher Block Chaining
• cipher block: if input block repeated, will produce same cipher text:
t=1 m(1) = “HTTP/1.1” c(1) = “k329aM02” …
t=17 m(17) = “HTTP/1.1” c(17) = “k329aM02” • Sender creates a random k-bit number r(i) for ith block and calculates
• c(i)=KS(m(i)År(i))
• Sends c(1), r(1), c(2), r(2), c(3), r(3)….
• r(i) sent in clear but Ks not known to attackers.
block cipher
block cipher
010 XoR 001 = 011
From table 011 encrypted to -> 100
CBC Example
• Example: sent text 010010010 if no CBC, sent txt = 101101101
• The sent text is result of 1-to-1 mapping used to map k-bit block of
plaintext to k-bit block of ciphertext (see table earlier)
• Lets use the following random bits • r(001), r2(111), r3(100)
• First we XOR the plain text with the above random bits:
• E.g 010 XOR 001 = 011
• Now do table lookup for 011 -> 100
• Use above technique to generate cipher text c(1) = 100, c(2) = 010, c(3) =
000: NOTE all three output different even though same plain text 010.
• Inefficient: twice as many bits sent
• NOTE: Try other bits in the example to make sure you understand how this works.
CBC: Sender
• cipher block chaining: XOR ith input block, m(i), with previous block of cipher text,c(i-1)
• c(0) is an Initialisation Vector transmitted to receiver in clear
• First block: m(i)
c(1) = KS(m(i) Å c(0)) • Subsequent blocks:
c(i) = KS(m(i) Å c(i-1))
block cipher
CBC: Receiver
• How to recover m(i)?
– Decrypt with Ks to get s(i) = Ks(c(i)) = m(i)
– Now the receiver knows c(i-1), it can get
m(i) = s(i) Å c(i-1) – IV sent only once
– Intruder can’t do much with IV since it doesn’t have Ks – CBC has important consequence for designing secure
network protocols
Block Ciphers
• Block cipher needs to wait for one block before processing it
– Suitableforstorage
• Operates on a single block of plaintext
– 64 bits for Data Encryption Standard (DES), 128 bits for Advanced Encryption Standard (AES)
§ AES much (6x) faster than DES
• Computationally infeasible to break block cipher by
brute-force by cracking the key
– Brute force decryption (try each key)
Symmetric key crypto: DES
DES: Data Encryption Standard (US encryption standard [NIST 1993])
• 56-bit symmetric key, 64-bit plaintext input
• Block cipher with cipher block chaining
• How secure is DES?
– DES Challenge: 56-bit-key-encrypted phrase decrypted (brute force) in less than a day
§ DES Challenge III: Distributed. Networked with EFF’s supercomputer and a world- wide network of 100,000 PCs to crack it within 22 hours and 15 minutes, Testing 2.45 billion keys per second
– no known good analytic attack
• Making DES more secure:
– 3DES: encrypt 3 times with 3 different keys
Symmetric key crypto: DES
DES operation
initial permutation
16 identical “rounds” of function application, each using different 48 bits of key
final permutation
No need to memorise this
Feistel (F) function
• Feistel (F) function
– Expansion (E): the 32-bit half-block is expanded to 48 bits using the expansion permutation
– Key mixing:
Half Block (32 bits)
Subkey (48 bits)
Sixteen 48-bit subkeys: one for each round from 56 bit key
Derived from the main key using the key schedule
E is combined with a subkey using an XOR operation
No need to memorise thisJ
– P: permutation function
o P yields a 32-bit output from a 32-bit input by permuting the bits of the input block
– S-box: Substitution
o Transforms input bits using substitution tables to provide diffusion
o Spread plaintext bits throughout ciphertext
o Small change in either the key or the plaintext should cause a drastic change in the ciphertext (avalanche effect)
AES: Advanced Encryption Standard
• Symmetric-key NIST standard, replaced DES (Nov 2001)
• processesdatain128bitblocks
• 128,192,or256bitkeys
• Bruteforcedecryption(tryeachkey)takingfew secs on DES, takes 149 trillion years for AES
oUniverse lifetime: 100 billion years
Repeat 10/12/14 rounds based on key size
AES -Structure
One block of 128-bit plaintext arranged as 4×4 array of 8-bit bytes
128/192/256 bit key
No need to memorise this J
Expand key
Shift rows
Substitute the array
(each byte is replaced with another according to 16×16 substitution table)
Shift array rows
(a transposition step where each row of the state is shifted cyclically 1st unchanged, 2nd left by 1, 3rd left by 2, 4th left by 3)
Mix 4 bytes in each column
(each new byte depends on all bytes in old column)
Add key for this round
each byte of the state is combined with the round key, and
each round key is derived from the cipher key using a key schedule
Mix columns
AES Confidentiality Modes
• Five confidentiality modes of operation for symmetric key block cipher algorithms, such as AES
• Electronic Codebook (ECB),
– Split plaintext into blocks, encrypt each one separately
using the block cipher
• Cipher Block Chaining (CBC) mode
– Split plaintext into blocks, XOR each block with the result of encrypting previous blocks
• Cipher Feedback (
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com