A basic premise for any communication is its integrity and authenticity. Put in layman terms, party A receiving a message M from party B, should have the confidence that this is the exact message that party B wanted to share.
For this hypothesis to be valid, the following predicates should hold:
- A (Authenticity) – Party A should be confident that the message M received, was in fact sent by party B
- I (Integrity) – Party A should be able to verify somehow that M is the real message that was sent by B, i.e. the message has not changed in transit
To achieve the above, MAC (message authentication code) is generally used. MAC is based on the hash functions, along with the use of secret key. Before we delve deeper into the matter, let’s revisit some of the key concepts.
Hashing
Hash functions converts an arbitrary length string to a fixed length string. This means that given any string as input, the output will always have a fixed length.
A simple hash function:
H(i) -> X
If length(i) < 10 -> append 0’s at the end to make the output length 10
If length(i) > 10 -> truncate the string beyond the 10th character
The above may be qualified as a hash function as per definitions, but the usability remains questionable. Typically, the hash functions used in message authentication are:
- One way: The input can’t be derived from the output
- Collision free: 2 different inputs do not produce the same output
Encryption
Encryption is a way to achieve confidentiality. It uses a secret key to change the form of the input text. The opposite process, i.e. getting the original text from the encrypted text is called decryption.
A simple encryption:
Change each ‘A’ in the input to ‘B’
Enc(APPLE) -> BPPLE
As you can observe, the above encryption algorithm is not that difficult to break. A typical desirable property of encryption is that it should be computationally very tough to get the original text back from the encrypted text (generally called cipher text), without the knowledge of secret key.
Coming back to our original discussion of message authentication, lets see how can hashing and encryption be applied to achieve the objective.
Let’s first hash the message. This would give us a fixed length string, which can be appended to the message as metadata. The receiver may hash the received data and compare with the hash stored in metadata. If both are same, party A can be sure that this is the actual message sent.
Can you find the catch?
- What if the adversary changed both the message and the metadata
- Is this message coming from party B?
To alleviate the above points, encryption will come to rescue.
Encryption helps because now the adversary can’t change the metadata. Any changes in the message will invalidate the corresponding metadata.
* Note that only the metadata is encrypted and not the whole message
Also since the secret key used to encrypt/decrypt the metadata is only know to party A & party B, the problem of authenticity also gets solved.
The metadata we are referring to is called the MAC (message authetication code).
There are several well know MAC implementations used, for e.g. HMAC, CMAC etc. For a complete understanding of HMAC refer RFC 2104 .
Pingback: Cryptography 2: Digital Signatures – Keep It Simple