Computer Networking › Section H · Security in computer networks › Topic H.3
Message integrity and digital signatures
Hiding a message is only half of security. Bob also needs to know that a message really came from Alice and was not changed on the way, and sometimes he needs to prove it to someone else. Hash functions, message authentication codes and digital signatures do that work.
Did Alice really send this?
Suppose a router receives a routing update claiming to come from a neighbour, or a bank receives an instruction to transfer money. The content may not be secret, but the receiver must check that it came from the claimed sender and was not altered on the way. Encryption alone guarantees neither, because Trudy may change ciphertext blindly or replace it. This topic builds the tools: cryptographic hash functions, message authentication codes for parties who share a secret, and digital signatures for anyone with a public key.
Cryptographic hash functions
A hash function H takes a message of any length and returns a short fixed-length digest \(H(m)\). For security it must be a cryptographic hash, meaning three things are computationally infeasible. Preimage resistance: given a digest, find any message with that digest. Second-preimage resistance: given a message, find a different one with the same digest. Collision resistance: find any two different messages with the same digest. Collisions must exist, since there are endless messages but finitely many digests; the point is that nobody can find one. Then the digest can stand in for the whole message.
Worked example: fooling a checksum
The Internet checksum from "Error detection and correction" is a hash, but not a cryptographic one. 1. Take the four-character amount 9001. In ASCII its 16-bit words are 0x3930 ("90") and 0x3031 ("01"). 2. Their sum is 0x6961, and the one's complement gives the checksum 0x969E. 3. Swap the two words to get 0190, a very different amount. 4. Addition does not care about order, so the sum is still 0x6961 and the checksum is still 0x969E. Check: two messages share a checksum, found with no effort at all, so the checksum fails collision resistance. It catches random noise but not a deliberate opponent.
MD5, SHA-1 and SHA-2
Hash functions age as attacks improve. MD5, published in 1992 with a 128-bit digest, has had practical collisions since 2004 and must not be used for security. SHA-1, with a 160-bit digest, suffered the first public collision in 2017; browsers stopped trusting SHA-1 certificates that year, and NIST plans to retire it entirely by the end of 2030. Current choices are the SHA-2 family, such as SHA-256 and SHA-384, and SHA-3, standardised in 2015. Digest length matters because of the birthday effect: collisions can be found in roughly \(2^{n/2}\) tries for an n-bit digest, so SHA-256 gives about 128-bit collision strength.
Message authentication codes
A hash alone cannot prove origin. If Alice sends \(m\) with \(H(m)\), Trudy can send her own \(m'\) with \(H(m')\), and Bob cannot tell the difference. The fix is a shared secret s, the authentication key. Alice computes a tag from the message and the key, in simplified form \(H(m + s)\), the hash of the message with the key appended, and sends \(m\) with the tag. Bob, who also knows s, recomputes the tag and compares. Without s, Trudy cannot make a valid tag for a changed message. This is a message authentication code (MAC). The real standard construction, HMAC, instead hashes the key and message in two nested passes and is used throughout TLS and IPsec. A MAC needs no encryption at all.
Worked example: checking a MAC
Alice and Bob share the key tulip and use HMAC with SHA-256, keeping the first 8 hex digits of the tag to make it readable. 1. Alice computes the tag of pay Bob 100 and gets 56f7f658. 2. She sends the message and the tag. 3. Trudy changes the amount to pay Bob 900 but cannot compute a new tag without the key, so she leaves 56f7f658 in place. 4. Bob computes the tag of what arrived and gets 00b2c78d, which does not match, so he rejects it. Check: with the key rose instead, the original message gives 33a202af, so the tag depends on the key as well as the message. Real systems keep at least 128 bits of the tag.
Digital signatures
A handwritten signature should be verifiable, unforgeable and undeniable. A digital signature achieves this with a key pair. Bob signs by applying his private key, producing \(K_B^-(m)\); anyone with his public key checks that \(K_B^+(K_B^-(m)) = m\). Only Bob holds \(K_B^-\), so a valid signature shows Bob signed and the message has not changed since. Signing a long message directly would be slow, so Bob signs its hash instead, \(K_B^-(H(m))\). A verifier hashes the message, applies the public key to the signature, and compares the two digests. Because the hash is collision resistant, signing the digest is as good as signing the message.
Worked example: a toy RSA signature
Bob's RSA key uses p = 7 and q = 23, so n = 161 and \(\varphi = 6 \times 22 = 132\). 1. With e = 7, the private exponent is d = 19, since \(7 \times 19 = 133 = 132 + 1\). 2. Bob's message hashes, in this toy, to h = 30. He signs: pow(30, 19, 161) = 149. 3. He sends the message and s = 149. 4. Alice hashes the message herself, gets 30, and computes pow(149, 7, 161), which returns 30. They match, so she accepts. Check: had Trudy changed the message so that it hashed to 31, Alice's two values, 31 and 30, would differ. To forge s for 31, Trudy would need d.
MACs versus signatures
Both detect tampering, but they differ in who can make and check them. A MAC uses one shared key, so either party can create a valid tag. That is fast and suits an ongoing session, but Bob cannot prove to a judge that Alice, not he, made the tag. A signature uses a key pair: only the private-key holder can create it, and anyone with the public key can check it. That gives non-repudiation, the signer cannot later deny signing, and suits software updates, certificates and documents. Signatures are much slower, which is why sessions sign once and then use MACs.
Certifying public keys
A signature check is only as good as the public key used. If Trudy sends Alice a message signed with Trudy's private key, along with Trudy's public key labelled as Bob's, the check succeeds and proves nothing. A certificate authority (CA) closes the gap: it verifies an identity and issues a certificate, in the X.509 format, binding a name such as a domain to a public key, with validity dates, all signed by the CA. Browsers and operating systems hold root CA keys; roots usually sign intermediate CAs, which sign servers' certificates, forming a chain.
Common mistakes to avoid
First, treating a checksum or CRC as protection against tampering; an opponent can make a matching one. Second, sending a plain hash with a message as proof of origin; Trudy can replace both. Third, thinking a MAC proves to outsiders who made it; either key holder could have. Fourth, signing with the public key or verifying with the private key; it is the reverse. Fifth, still accepting MD5 or SHA-1 for signatures or certificates. Sixth, verifying a signature without checking that the public key is certified for the claimed signer.
Key takeaways
A cryptographic hash gives a short digest and must resist preimages, second preimages and collisions; checksums do not. MD5 and SHA-1 are broken for collisions; use SHA-2 or SHA-3. A MAC, such as HMAC, combines the message with a shared key so that only key holders can create or check tags. A digital signature applies the signer's private key to a message's hash, and anyone verifies it with the public key, giving non-repudiation. A certificate, signed by a CA and chained to a trusted root, binds a public key to an identity, which makes signature checks meaningful.
Flashcards
Flashcard
A short fixed-length value computed from any message
Test your understanding
Question 1 of 5
Alice sends Bob a message m together with its SHA-256 digest H(m), with no key involved. What can Trudy, on the path, do?
Question 2 of 5
Alice and Bob share an HMAC key. Bob receives a message with a valid tag. What can he conclude?
Question 3 of 5
A toy RSA key has n = 161, e = 7 and d = 19. A signed message arrives with s = 149, and the message hashes to 30. How does the receiver verify it?
Question 4 of 5
Why do signers apply their private key to H(m) rather than to the whole message m?
Question 5 of 5
Trudy signs a file with her own private key and sends her public key labelled as Bob's. What stops Alice being fooled?
