INS Module 2
5.2 What is a Cryptographic Hash Function?
A cryptographic hash function h(x) is a special type of function that takes an input (of any size) and produces a
fixed-size output, called a hash or digest, with the following important properties:
1. Compression: No matter how large the input is, the output is always a fixed length (e.g., 160 bits). For any size
input x, the output length of y = h(x) is small.
2. Efficiency: It must be easy to compute h(x) for any input x. The computational effort required to compute h{x)
will, of course, grow with the length of x, but it cannot grow too fast.
3. One-way property: Given any value y, it's computationally infeasible to find a value a such that h{x) = y.
Another way to say this is that there is no feasible way to invert the hash.
4. Weak collision resistance
Given an input and its hash, it is hard to find a different input with the same hash.
This prevents someone from modifying a message without changing its hash.
5. Strong collision resistance: It's infeasible to find any x and y, such that x φ y and h(x) = h(y). That is, we
cannot find any two inputs that hash to the same output.
Difference from weak collision resistance
Weak: One input is fixed
Strong: Both inputs are attacker-chosen
Why Hash Functions Are Useful
Hashes act like a fingerprint of a message: even a tiny change in the input produces a very different hash.
They are widely used in digital signatures: instead of signing a large message, a sender signs its hash.
Example:
1. Alice computes h(M) for her message M .
2. She signs the hash: S = [h(M)]_Alice .
3. Bob receives M and S and verifies the signature by checking that h(M) = {S}_Alice .
This makes signing efficient and secure, assuming the hash function and the signature system are both
strong.
Q11. How is a digital signature computed and verified?
Definition:
A digital signature is a cryptographic technique that allows a sender to prove that a message is authentic and
unaltered.
Computation (Signing):
1. Alice has a message M .
INS Module 2 1
2. She applies a hash function → h(M) (this makes the process efficient and fixed-length).
3. Alice encrypts the hash with her private key:
S = [h(M)]Alice .
4. She sends (M, S) to Bob.
Verification:
1. Bob receives (M, S) .
2. He computes his own h(M) from the received message.
3. He decrypts S with Alice’s public key to get h(M) (as signed by Alice).
4. If both match → the message is authentic.
Example:
If Alice signed a contract message, Bob can verify she was the one who signed it (since only Alice’s private
key could have generated it).
Any tampering (even a single bit) in M makes the signature invalid.
Conclusion:
Digital signatures = hashing + public key cryptography → they provide authenticity and efficiency.
Q12. Show that a digital signature provides integrity protection and non-repudiation.
1. Integrity Protection:
A message’s integrity means “it has not been changed.”
Since Alice signs h(M), if M is modified, Bob’s computed h(M') ≠ decrypted h(M) .
Even the smallest alteration (e.g., changing one letter) is detected.
2. Non-repudiation:
Only Alice knows her private key.
If the signature verifies correctly with Alice’s public key, it must have come from Alice.
Therefore, she cannot deny (“repudiate”) having signed it.
Example:
If Alice signed a payment authorization, she cannot later deny it, and no one can alter the payment details
without detection.
5.3 The Birthday Problem
The birthday problem is a fundamental concept in cryptography and is especially important in understanding the
security of cryptographic hash functions.
Warm-up: Matching a Given Birthday
Suppose you are in a room with N other people. We want to find how large N must be so that the probability is
greater than 1/2 that at least one person has the same birthday as you.
Instead of computing this probability directly, we compute the complement, i.e., the probability that none of the N
people shares your birthday.
Since there are 365 days in a year and birthdays are assumed to be equally likely, the probability that a randomly
selected person does not share your birthday is:
INS Module 2 2
This result is reasonable since the answer is on the order of 365 days.
The Actual Birthday Problem
Now consider the real birthday problem. Suppose there are N people in a room. We want to determine how large
N must be so that the probability is greater than 1/2 that two or more people share the same birthday.
Again, we compute the complement, which is the probability that all N people have different birthdays.
Person 1 can have any of the 365 birthdays
Person 2 must have one of the remaining 364 birthdays
Person 3 must have one of the remaining 363 birthdays
Person N must have one of the remaining 365−N+1 birthdays
INS Module 2 3
Relevance to Cryptographic Hash Functions
Security Implication
A symmetric cipher with an N-bit key requires about 2N2^N2N operations to break.
A hash function with an N-bit output can be broken using about 2N/22^{N/2}2N/2 operations.
Hence, to achieve comparable security, a hash function must have an output size roughly twice the key length
of a symmetric cipher, assuming no shortcut attacks exist.
5.4 A Birthday Attack
A birthday attack is a practical attack on digital signatures that use cryptographic hash functions. It is based on
the birthday problem, which shows that collisions can be found much faster than expected.
Background: Hashing in Digital Signatures
When Alice wants to sign a message M, she does not sign the message directly.
Instead, she:
Idea of the Birthday Attack
The attacker does not break the public key system.
Instead, the attacker finds two different messages with the same hash value.
INS Module 2 4
Why the Attack Works
Digital signatures sign the hash, not the message
Hash collisions are possible in 2n/22^{n/2}2n/2 attempts
Same hash ⇒ same signature
5.5 Non-Cryptographic Hashes
Non-cryptographic hashes are hash functions not designed for security.
They are useful for compression, error detection, or data indexing, but cannot resist attacks by a malicious
adversary.
1. Simple Sum Hash
Definition:
Given data as bytes:
Properties:
Compresses input of any size into 8-bit output
Easy to compute
Weaknesses:
Output too small → only 256 possible values
Birthday problem applies → collision expected after ~16 random inputs
Algebraic structure weak → easy to construct collisions manually
Example: swapping bytes gives the same hash
h(10101010,00001111) =h(00001111,10101010)
Conclusion:
Not secure for cryptography
Only suitable for very basic, non-security applications
INS Module 2 5
2. Weighted Sum Hash
Definition:
Properties:
Takes byte order into account → swapping bytes changes hash
Still simple to compute
Weaknesses:
Birthday problem still applies → collisions likely with ~2^(n/2) inputs
Collisions still easy to construct manually
Example:
h(00000001,00001111) =h(00000000,00010001)
Conclusion:
Slightly stronger than simple sum hash
Still not cryptographically secure
Can be used in non-crypto applications like Rsync
3. CRC (Cyclic Redundancy Check)
What is CRC?
A checksum used for error detection
Based on binary long division
Uses XOR instead of subtraction
Remainder = CRC value
Example
Divisor: 10011
Data: 10101011
Append 4 zeros
Perform XOR-based division
Remainder = CRC checksum
Why CRC is insecure
1. Collisions are easy
2. Adversary can modify data and adjust CRC
3. Designed for random errors, not attacks
INS Module 2 6
Q3. Consider a CRC that uses the divisor 10011. Find two collisions with 10101011, that is,
find two other data values that produce the same CRC checksum as 10101011.
INS Module 2 7
5.6 Tiger Hash
Explain Tiger Hash Algorithm with Diagram
Tiger basics
Cryptographic hash function, fast and strong, optimized for 64-bit processors.
Input split into 512-bit blocks (padded if needed).
Output = 192 bits = three 64-bit words (a, b, c) .
Initial values (a, b, c) are fixed constants, with a = 0123456789ABCDEF, b = FEDCBA9876543210, and c
= another predefined constant.
INS Module 2 8
Structure:
Total of 24 rounds arranged as 3 outer rounds, each containing 8 inner rounds.
Works on three 64-bit variables (a, b, c) .
The message block is expanded into words W , which feed into the rounds.
Outer rounds:
Each outer round applies functions (F5, F7, F9) that transform (a, b, c) using W .
After each stage, the values are rotated (a,b,c) → (c,a,b) → (b,c,a) to improve mixing.
Inner rounds:
Each outer function consists of 8 inner rounds.
In every inner round:
Bytes of c are passed through large S-boxes (nonlinear lookups).
Combined with a word wi using XOR, addition, subtraction, and multiplication.
(a, b, c) are updated nonlinearly.
Key features:
Output size: 192 bits.
Four large S-boxes provide confusion.
Mathematical operations + rotations provide diffusion.
Based on Shannon’s principles of confusion and diffusion.
Designed to be both secure and fast on 64-bit CPUs.
Summary (one-liner): Tiger = 24-round hash with outer and inner structure, producing a 192-bit digest;
designed for speed and strong avalanche effect on 64-bit CPUs.
Explain cryptographic hash functions MD5 and SHA-1.
MD5
Stands for Message Digest 5, successor to MD2, MD4.
Produces a 128-bit hash.
Invented by Ron Rivest.
No longer secure because collisions are easy to find.
SHA-1
Stands for Secure Hash Algorithm 1, a U.S. government standard.
INS Module 2 9
Produces a 160-bit hash, slightly stronger than MD5.
Similar in design to MD5, hashes messages in blocks with multiple rounds.
Collisions have been found; not considered fully secure today.
Common features
Both use block-based processing like block ciphers.
Designed for efficiency and to exhibit the avalanche effect: a small change in input produces a large,
unpredictable change in output.
5.7 HMAC
Q4. Write a short note on HMAC.
Purpose: HMAC is used to verify the integrity and authenticity of a message using a secret key and a
cryptographic hash function. It ensures that:
1. The message hasn’t been tampered with.
2. The message comes from someone who knows the secret key.
Key components:
Hash function: Any cryptographic hash like MD5, SHA-1, SHA-256.
Key (K): Secret shared between sender and receiver.
ipad (inner pad): Constant 0x36 repeated to fill the block size.
opad (outer pad): Constant 0x5C repeated to fill the block size.
Formula:
HMAC(M, K) = Hash( (K ⊕ opad) || Hash((K ⊕ ipad) || M) )
Where ⊕ is XOR, and || means concatenation.
Step by step:
1. K ⊕ ipad → XOR the key K with the inner pad (ipad, 0x36 repeated).
2. (K ⊕ ipad) || M → Concatenate this result with the message M .
3. Hash((K ⊕ ipad) || M) → Compute the hash of the inner combination (inner hash).
4. K ⊕ opad → XOR the key K with the outer pad (opad, 0x5C repeated).
5. (K ⊕ opad) || inner_hash → Concatenate this with the inner hash.
6. Hash(...) → Compute the final hash. This is the HMAC.
Why it’s secure:
Even if an attacker sees the HMAC, they cannot forge it without knowing the key.
Prevents simple attacks that might work if you just hashed M || K or K || M .
Works with any secure hash function, providing strong integrity verification.
Use cases:
Authenticating API requests.
Ensuring message integrity in communication protocols.
Digital signatures and secure data storage.
Q13. Does a MAC satisfy the same properties that an HMAC satisfies?
Definition:
MAC (Message Authentication Code): Uses a symmetric key (e.g., CBC mode of block cipher).
HMAC (Hashed MAC): Uses a hash function with a secret key mixed in, defined by RFC 2104.
MAC Properties:
INS Module 2 10
Provides integrity and authentication.
But may be vulnerable to attacks (e.g., extension or collisions if hash is weak).
HMAC Properties:
Defined as:
HMAC(M, K) = H((K ⊕ opad), H((K ⊕ ipad), M)) .
Double hashing ensures:
Resistant to length extension attacks.
Key is strongly mixed into the hash.
Even if some weaknesses exist in H , HMAC remains secure.
Comparison:
A plain MAC ≠ as strong as HMAC.
HMAC was specifically designed to fix vulnerabilities in naive keyed hashes.
5.8 Uses of Hash Functions
Standard Uses
Authentication – Verify sender identity.
Message integrity – Detect tampering (e.g., using HMAC).
Message fingerprinting – Unique identifier for a message.
Error detection – Identify accidental changes.
Efficiency in digital signatures – Sign small hash instead of full message.
1. Online Sealed Bidding Using Hashes
In online auctions, bidders (e.g., Alice, Bob, Charlie) want their bids to remain secret until all bids are placed.
How it works:
1. Commitment Phase: Each bidder computes a hash of their bid ( h(Bid) ) and submits only the hash.
2. Reveal Phase: After all hashes are submitted, bidders reveal their actual bids. The system verifies each
bid by checking h(Bid) matches the previously submitted hash.
Why it’s secure:
The hash is one-way, so the bid cannot be deduced from the hash.
Collision resistance prevents changing a bid after submission.
Binding property ensures the bid is fixed once the hash is submitted.
Enhancement: To prevent attackers from guessing common bid values (forward search attack), a random
nonce is added: h(Bid || nonce) . The nonce is revealed along with the bid to verify integrity.
2. Spam Reduction Using Hashes (Proof-of-Work)
Goal: Make sending spam expensive in terms of computational effort.
How it works:
1. Sender’s Task (expensive):
Before sending an email message M , the sender must find a random value R such that the hash
h(M || R || T)
(where T is a timestamp or unique value) starts with N leading zeros.
The only way to find such an R is by repeated guessing and hashing (trial and error).
On average, this requires about 2^N hash computations.
2. Recipient’s Task (cheap):
The recipient only needs to perform one hash to check whether the condition (leading zeros) is satisfied.
INS Module 2 11
Effect:
For legitimate users, this adds a small computational delay.
For spammers sending millions of emails, the work becomes exponentially expensive, deterring bulk
spam.
Adjustable difficulty: Users can choose N according to how strict they want the spam filter to be (e.g., Alice
N=40 for strict, Bob N=10 for lenient).
5.9.1 Secret Sharing
Secret sharing is a cryptographic technique where a secret SSS is divided among multiple participants so that:
No single participant can determine the secret alone.
A specific number of participants working together can reconstruct the secret.
The idea is simple: use polynomials.
A polynomial of degree m−1 is uniquely determined by m.
The secret is encoded as the constant term of the polynomial, and each participant receives a point (share) on
the polynomial.
Arithmetic is usually performed modulo a prime ppp for digital implementation.
This provides information-theoretic security, meaning fewer than the required number of shares give no
information about the secret.
Types of Secret Sharing
1. 2-out-of-2 Scheme
Definition: Both participants must cooperate to recover the secret.
How it works:
The secret SSS is the y-intercept of a line LLL.
Alice receives a point AAA on the line; Bob receives a point BBB on the line.
Alone, each sees only one point → infinite possible lines → secret cannot be determined.
Together, two points uniquely define the line → y-intercept reveals the secret.
2. m-out-of-n Scheme
Definition: Any mmm out of nnn participants can reconstruct the secret.
How it works:
INS Module 2 12
A polynomial of degree m−1m-1m−1 is constructed with the secret as the constant term.
Each participant receives a point on this polynomial.
Any mmm participants can solve the polynomial to find the secret. Fewer than mmm cannot.
Example: In a 3-out-of-5 scheme, a quadratic polynomial is used; any 3 points reconstruct the secret.
3. Threshold schemes
Definition: A general form of m-out-of-n secret sharing, often used in practical applications.
Applications:
Distributed key storage for cryptocurrency wallets.
Cloud storage where only a threshold number of servers can access the secret.
Security: Ensures that fewer than the threshold number of shares reveal no information.
4. Hierarchical secret sharing
Definition: Shares are distributed with different access levels.
Example: A CEO and any 2 managers can reconstruct the secret, but managers alone cannot.
Application: Corporate secrets where decision power varies by rank.
5. Key Escrow
Definition: A practical application of secret sharing where a secret key is divided among escrow agencies.
How it works:
The user splits their key among nnn agencies using an mmm-out-of-nnn scheme.
At least mmm agencies must cooperate to recover the key.
Example: Alice’s key is split among three agencies; at least two must collaborate to retrieve it.
Purpose: Governments once considered this to allow lawful access to encrypted data, though it has been
largely abandoned due to trust and security concerns.
6. Visual Cryptography
Definition: A secret sharing scheme applied to images where no computation is needed to reconstruct the
secret.
How it works:
Each pixel of a black-and-white image is split into “shares” distributed to participants.
Alone, each share appears as random noise → reveals nothing.
Overlaying the shares reconstructs the original image, though with some loss of contrast.
Example: Alice and Bob each get a transparency; overlaying their transparencies reveals the original image.
Extensions: Can be generalized to mmm-out-of-nnn schemes.
Key Points:
Secret sharing ensures security even if some shares are compromised.
Polynomial-based schemes are mathematically secure (information-theoretic security).
Works in practice using modular arithmetic for computer storage.
Visual cryptography is an intuitive, computation-free variant.
Applications include key management, secure voting, and image protection.
5.9.2 RANDOM NUMBERS
Q8. What are random numbers? Why is it required to generate symmetric keys?
What are random numbers?
Random numbers are values generated without any predictable pattern.
INS Module 2 13
In general applications (e.g., simulations, statistics), they only need to be statistically random—they should
"look random."
In cryptography, random numbers must be both:
1. Statistically random – indistinguishable from true randomness.
2. Unpredictable – no one should be able to guess future values, even if they know past values.
Why are random numbers required for symmetric keys?
Symmetric keys (used in AES, DES, etc.) must be chosen randomly to ensure that no attacker can guess or
derive them.
If keys are predictable (e.g., generated from a weak or predictable random number generator), attackers can
guess or calculate them.
Example: If multiple users get keys from the same predictable generator, knowledge of one user’s key could
help attackers deduce another user’s key, completely breaking security.
9. Where are random numbers used in symmetric key cryptography?
Random numbers are essential in symmetric key cryptography to ensure security and unpredictability. They are
used in:
1. Key generation – Symmetric keys must be random so attackers cannot guess them.
2. Initialization vectors (IVs) – Random IVs prevent the same plaintext from producing the same ciphertext.
3. Nonces – Random values used once to prevent replay attacks in communication.
4. Salts – Random data added before hashing passwords or keys to resist dictionary and rainbow table attacks.
Q14. Why are statistically random numbers not sufficient for cryptographic applications?
Statistical Randomness:
Numbers that “look random” (pass randomness tests).
Used in simulations, gaming, statistics.
But often generated by predictable algorithms (PRNGs).
Weakness of PRNGs (Pseudo Random Number Generaotors)
PRNGs are algorithmic and deterministic.
Given enough outputs, attackers can predict future values.
Hence, insecure for cryptography unless enhanced with secure entropy sources.
Cryptographically Secure PRNGs (CSPRNGs)
Designed for security applications.
Provide unpredictable output, backtracking resistance, and state-compromise resistance.
Example (Texas Hold ’Em Poker software):
Used a 32-bit PRNG seeded with system time (milliseconds since midnight).
Since there were only ~2^27 possibilities, attackers could quickly reconstruct the shuffle.
Result: Cheaters could see all players’ cards.
Requirement in Crypto:
Random numbers must be both statistically random AND unpredictable.
Sources include physical entropy (e.g., mouse movements, hardware RNGs, lava lamps).
5.9.3 INFORMATION HIDING
Information hiding in cryptography and security primarily has two aspects: steganography and digital
watermarking. Both involve concealing information, but their goals and applications differ.
1. Steganography
INS Module 2 14
Definition: Steganography (meaning “hidden writing”) is the practice of concealing the very existence of
information. Unlike cryptography, which hides the content, steganography hides the fact that a message is
being sent at all.
Historical Example: In ancient times, a Greek general shaved a slave’s head, wrote a secret message on it,
and waited for the hair to grow back before sending the slave across enemy lines. The hidden message
warned of an invasion.
Modern Example:
Digital steganography hides information inside media such as images, audio, or HTML files.
A common method is using the least significant bits (LSBs) of image pixels or color codes to store hidden
data. For example, an entire PDF of Alice in Wonderland could be embedded in the low-order RGB bits of a
photo without affecting how the image looks to the human eye.
Weakness: If an attacker knows the scheme, they can easily extract or destroy the hidden data (e.g., by
randomizing the LSBs). Thus, robust steganography remains a difficult challenge.
2. Digital Watermarking
Definition: Digital watermarking also hides information, but with a different purpose—typically to prove
ownership, ensure integrity, or trace copies.
Uses: Widely applied in media (music, images, video, software) and physical items like currency.
Types of Watermarks:
Visible: Intentionally noticeable, like “TOP SECRET” on a document or watermarks in paper currency.
Invisible: Hidden within the digital content and not perceptible to users.
Robustness Categories:
Robust watermarks: Survive tampering or transformations and remain readable (e.g., tracking pirated
music).
Fragile watermarks: Break when tampering occurs, thus serving as an integrity check.
Challenges:
If attackers know the watermarking scheme, they can often damage or remove it.
Collusion attacks (comparing original and watermarked versions) can reveal watermarking bits.
Many schemes fail when tested against Kerckhoffs’ Principle (security should not rely on secrecy of the
method).
Q6. Forward Search Attack on Public Key Encryption
Definition:
A forward search attack occurs when an attacker tries all likely plaintexts, encrypts each one with the public
key, and compares the result to a captured ciphertext to determine the original message.
Why it’s possible:
The message space is small or predictable.
The attacker can efficiently test all possibilities.
Prevention:
Use randomized encryption or padding schemes (e.g., OAEP in RSA) to make each encryption output
unique, even for the same plaintext.
This ensures that guessing a message and comparing ciphertexts becomes infeasible.
Q7. Preventing Forward Search on Hash Functions
Scenario: In online bidding, an attacker could precompute hashes of all likely bid values and compare them to
submitted hashes.
Prevention:
Add randomness (nonce or salt): Hash h(Bid || R) instead of just h(Bid) , where R is a random value.
INS Module 2 15
The server verifies the bid by checking h(Bid || R) after the reveal.
This makes precomputation or guessing attacks impractical because the attacker does not know the
random value in advance.
Key Idea: Forward search attacks exploit predictability. Adding randomness in hashes or encryption outputs
prevents attackers from efficiently guessing the original message.
INS Module 2 16