Hash Functions & Digital Signatures: How Data Integrity & Signatures Work

TAKEAWAYS:

• Hash functions convert input data into a fixed-length unique fingerprint (e.g., SHA-256 produces a 256-bit hash) to detect tampering.
• Digital signatures use asymmetric cryptography (private key for signing, public key for verification) to prove authenticity and integrity.
• Collision resistance ensures no two different inputs produce the same hash output, critical for security.
• Applications: Password storage (bcrypt), blockchain (Bitcoin), and secure file transfers (HTTPS).
• Weaknesses: Hash functions like MD5 are vulnerable to collisions; digital signatures require proper key management.
• Exam focus: Compare hash functions, explain digital signature workflows, and solve problems involving hash collisions.

Core Concepts: Hash Functions

Hash functions are mathematical algorithms that take an input (or message) and produce a fixed-size string of bytes, typically a hash value or digest. Their primary purpose is to ensure data integrity—any change in the input, no matter how small, should produce a drastically different hash.

How Hash Functions Work

1. Input: Any size of data (e.g., a file, password, or transaction record).
2. Processing: The algorithm processes the input using a deterministic process (same input → same output).
3. Output: A fixed-length hash value (e.g., 128 bits for MD5, 256 bits for SHA-256).
4. Key Properties:
   • Deterministic: Same input always produces the same hash.
   • Quick Computation: Fast to compute for any input size.
   • Pre-image Resistance: Hard to reverse-engineer the input from the hash.
   • Collision Resistance: Extremely unlikely for two different inputs to produce the same hash.

stateDiagram-v2
    [*] --> Input: Data
    Input --> Processing: Hash Algorithm
    Processing --> Output: Fixed-Length Hash
    Output --> [*]

Common Hash Functions

Worked Example: Detecting File Tampering

Suppose you download a software update from a website. The website provides a SHA-256 hash of the file: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e.

After downloading, you compute the hash of the file on your system. If the computed hash matches the provided hash, the file is untampered. If not, the file has been altered (e.g., malware injected).

Digital Signatures: Securing Authenticity

Digital signatures use public-key cryptography to provide authentication, integrity, and non-repudiation. They work as follows:

sequenceDiagram
    participant Sender as Alice (Private Key)
    participant Receiver as Bob (Public Key)
    participant Hash as SHA-256
    Sender->>Hash: "Transfer 10,000 NPR to Account XYZ" → H
    Sender->>Sender: Encrypt H with Private Key → Signature
    Sender->>Receiver: Message + Signature
    Receiver->>Hash: Compute SHA-256(Message) → H'
    Receiver->>Receiver: Decrypt Signature with Public Key → H''
    alt H' == H''
        Receiver->>Sender: ✅ Authentic (Ncell Transaction)
    else H' != H''
        Receiver->>Sender: ❌ Tampered/Forged
    end

1. Signing:
   • The sender uses their private key to encrypt the hash of the message.
   • The encrypted hash is the digital signature.
2. Verification:
   • The receiver uses the sender’s public key to decrypt the signature.
   • They compute the hash of the received message and compare it to the decrypted signature.
   • If they match, the message is authentic and untampered.

How Digital Signatures Work in Practice

1. Message: "Transfer 10,000 NPR to Account XYZ."
2. Hashing: Compute SHA-256 hash of the message → H.
3. Signing: Encrypt H with the sender’s private key → Signature.
4. Sending: Send Message + Signature to the receiver.
5. Verification:
   • Receiver decrypts Signature with the sender’s public key → H'.
   • Receiver computes SHA-256 hash of the received message → H''.
   • If H' == H'', the message is authentic.

Applications of Digital Signatures

1. eSewa Transactions:
   • When you pay for an electricity bill via eSewa, the platform uses digital signatures to ensure the transaction request is from you (not a hacker) and hasn’t been altered.
2. NEPSE Stock Trades:
   • Stock exchange orders are digitally signed to prevent fraudulent trades. If a trade is disputed, the signature proves who placed the order.
3. Software Updates (e.g., Windows Updates):
   • Microsoft signs updates with its private key. Your system verifies the signature using Microsoft’s public key before installing.

Collision Attacks and Weak Hash Functions

A collision occurs when two different inputs produce the same hash. While hash functions are designed to minimize collisions, weak functions (like MD5 and SHA-1) can be broken.

Example: MD5 Collision Attack

In 2008, researchers created two different PDF files with the same MD5 hash:

Hash of File1.md5 = d131dd02c5e6eec80f96a84e6120f643
Hash of File2.md5 = d131dd02c5e6eec80f96a84e6120f643

This vulnerability allows attackers to:

• Create fake certificates (e.g., impersonating a bank’s website).
• Tamper with software updates without detection.

Why SHA-256 is Preferred

• Larger Output: 256-bit hash makes brute-force attacks impractical.
• No Known Collisions: No practical collisions have been found for SHA-256.
• Used in Bitcoin: Every Bitcoin transaction is verified using SHA-256 hashes.

Digital Signatures vs. Encryption

Real-World Example: Ncell’s Secure App Logins

When you log in to the Ncell app, the following happens:

1. You enter your username and password.
2. The app computes a hash of your password (e.g., using bcrypt) and sends it to Ncell’s servers.
3. Ncell verifies the hash against its stored hashes.
4. For transactions (e.g., mobile top-up), Ncell uses digital signatures to ensure the request is from you and hasn’t been altered in transit.

In the real world

• Ncell App Logins: Uses SHA-256 hashing for password storage (with bcrypt salting) and RSA digital signatures for OTP verification. When you log in, the app hashes your password and compares it to the stored hash (pre-image resistance).
• eSewa Payments: Digital signatures (via ECC or RSA) authenticate transaction requests. If a hacker alters the amount (e.g., 10,000 → 1,000,000 NPR), the signature verification fails, exposing tampering.
• NEPSE Stock Trades: Every trade order is signed with the broker’s private key. If a dispute arises, the exchange verifies the signature using the broker’s public key to confirm the trader’s identity (non-repudiation).

Exam Tip

1. Understand Hash Functions:
   • Know the difference between MD5, SHA-1, SHA-256, and SHA-3.
   • Be able to explain collision resistance and why MD5/SHA-1 are insecure.
2. Digital Signatures Workflow:
   • Memorize the steps: hash → sign (private key) → verify (public key).
   • Practice problems where you’re given a message and asked to verify a signature.
3. Applications:
   • Link hash functions to password storage (bcrypt) and blockchain (Bitcoin).
   • Link digital signatures to e-commerce (eSewa), stock markets (NEPSE), and software updates.
4. Common Pitfalls:
   • Don’t confuse hashing (one-way) with encryption (two-way).
   • Remember: Digital signatures don’t encrypt data; they verify authenticity.

Summary

• Hash functions (SHA-256, bcrypt) ensure data integrity by producing unique fingerprints.
• Digital signatures use asymmetric cryptography to authenticate messages and prevent tampering.
• Weak hash functions (MD5, SHA-1) are vulnerable to collision attacks.
• Real-world uses: eSewa payments, NEPSE trades, Ncell app logins, Bitcoin transactions.