182
$\begingroup$

A message may be accompanied with a digital signature, a MAC or a message hash, as a proof of some kind.

Which assurances does each primitive provide to the recipient?

What kind of keys are needed?

$\endgroup$
  • 14
    $\begingroup$ Seems like an attempt to create a canonical question that explains the difference between commonly confused operations. $\endgroup$ – CodesInChaos Dec 10 '12 at 19:01
  • $\begingroup$ Good question indeed $\endgroup$ – Peter Mar 27 '19 at 13:06
208
$\begingroup$

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"):

  • Integrity: Can the recipient be confident that the message has not been accidentally modified?

  • Authentication: Can the recipient be confident that the message originates from the sender?

  • Non-repudiation: If the recipient passes the message and the proof to a third party, can the third party be confident that the message originated from the sender? (Please note that I am talking about non-repudiation in the cryptographic sense, not in the legal sense.)

Also important is this question:

  • Keys: Does the primitive require a shared secret key, or public-private keypairs?

I think the short answer is best explained with a table:

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Please remember that authentication without confidence in the keys used is useless. For digital signatures, a recipient must be confident that the verification key actually belongs to the sender. For MACs, a recipient must be confident that the shared symmetric key has only been shared with the sender.

The longer answer:

A (unkeyed) hash of the message, if appended to the message itself, only protects against accidental changes to the message (or the hash itself), as an attacker who modifies the message can simply calculate a new hash and use it instead of the original one. So this only gives integrity.

If the hash is transmitted over a different, protected channel, it can also protect the message against modifications. This is sometimes be used with hashes of very big files (like ISO-images), where the hash itself is delivered over HTTPS, while the big file can be transmitted over an insecure channel.

A message authentication code (MAC) (sometimes also known as keyed hash) protects against message forgery by anyone who doesn't know the secret key (shared by sender and receiver).

This means that the receiver can forge any message – thus we have both integrity and authentication (as long as the receiver doesn't have a split personality), but not non-repudiation.

Also an attacker could replay earlier messages authenticated with the same key, so a protocol should take measures against this (e.g. by including message numbers or timestamps). (Also, in case of a two-sided conversation, make sure that either both sides have different keys, or by another way make sure that messages from one side can't sent back by an attacker to this side.)

MACs can be created from unkeyed hashes (e.g. with the HMAC construction), or created directly as MAC algorithms.

A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it. Digital signatures don't prevent the replay attack mentioned previously.

There is the special case of designated verifier signature, which only ones with knowledge of another key can verify, but this is not normally meant when saying "signature".

So this provides all of integrity, authentication, and non-repudiation.

Most signature schemes actually are implemented with the help of a hash function. Also, they are usually slower than MACs, and as such used normally only when there is not yet a shared secret, or the non-repudiation property is important.

$\endgroup$
  • 4
    $\begingroup$ One interesting variation is using the result of a DH key exchange as the key for a MAC. That way you can use asymmetric keys, but you avoid non-repudiation. $\endgroup$ – CodesInChaos Dec 11 '12 at 12:04
  • 2
    $\begingroup$ so basically: MAC is a Hash that uses a "symmetric" key, Signature is a Hash that uses an asymetric key. $\endgroup$ – David 天宇 Wong Mar 17 '14 at 3:57
  • 1
    $\begingroup$ A hash and MAC can be truncated to an arbitrary size. A signature cannot. $\endgroup$ – aiao May 3 '16 at 13:25
  • 2
    $\begingroup$ Note that this diagram is not really correct anymore. Some cryptographers say that a MAC provides "integrity", not authentication anymore, since it's clearer. Whereas a hash does not provide integrity, but rather pre-image, second pre-image, collisions resistance. $\endgroup$ – David 天宇 Wong Feb 13 '17 at 17:09
  • 1
    $\begingroup$ @flimm check something like Dan Boneh and Shoup's book on cryptography. i.imgur.com/j0vL8Rw.png $\endgroup$ – David 天宇 Wong Feb 14 '17 at 18:54
-1
$\begingroup$

Hash = A result of a mathmatical function that is difficult to reverse engineer. The result of applying hash to a text is a long code. Examples of hashes: MD5, SHA1. The length of MD5 code is 128 bits, the length of SHA1 code is 160 bits.

With a hash: You cannot revert back to the original message. But the same message will always give the same hash. So if you receive a message along with a hash. You an always calculate your own hash. If the 2 hashes match it means the message is the original one, if not, the message has been tampered with.

The important thing about a hash is that a minor change to the message makes a huge difference to the hash code.

This means that a hash assures the integrity of the message.

Encryption (you didn't ask but it's important in the context) = You replace the text of a message in a way that is impossible or at least very difficult to decrypt, unless you have the key. If you combine the key with the encrypted message you get the original message.

This means that an encryption assures the secrecy of a message.

There are 2 types of encryption: symmetric and assymentric.

The symmetric is faster but less secure. It uses only 1 key for encryption and decryption. Both the sender and the receiver need to know the key and keep it a secret.

The risky part in the symmetric encryption is sending the key from one to another, because there is only one key and if compromised the whole conversation is compromised.

Examples: AES, DES.

The assymentric is slower but more secure. It uses 4 keys, each user has 2 keys, one for encryption and one for decryption, these 2 keys are mathmatically linked. The encryption key is the public key while the decryption key is the private key. A public key can only be decrypted by it's matching private key.

The public key, as the name suggests, is not a secret, the owner of the pairs of keys can post his public key on his website or whatever for anyone to pick, and in fact he has to in order to receive encrypted messages that can only be decrypted with his private key. It's like an address or mailbox. The private key, as the name suggests, must be kept a secret. If the owner of the pairs of keys has his private key compromised, then anyone can know what messages he received. Best thing to do in that case is generate a new pair of keys.

To communicate with assymentric encryption, exchange public keys. Unlike symmetric encryption, you can do this in the open, nobody can read your messages if he only knows your public keys.

  • If you want to send a message, use the public key of the other person to encrypt the message and send it to them, only they will be able to unlock the message with their private key and read it.
  • If you are to receive a message, the other person must have used your public key to encrypt your message, that means only your private key can decrypt the message.

Examples: RSA, DSA.

Of course, most of the time this is done automatically by e-mails or other forms of messaging. You may have communicated with assymentric or symmetric encryption already without manually encrypting and decrypting a message.

Now, in digital signature the opposite is done. You don't encrypt with the other person's public key but with your own private key. Because of this, anyone can use your public key that is out in the open to decrypt that message. How is this a signature? Because only you had access to your private key, which means that if decrypted only you could have sent that message.

This doesn't only create authenticity, but also integrity of the message and non-repudiation. Why as latter 2 as well?

Because what the digital signature actually encrypts with the private key is a hash of the whole message that you are sending.

  • If your message is: "Hello there, General Grievous!" a hash is used for all this text that generates a code, that code is then encrypted with your own private key.
  • The one who receives your message, uses your own public key to decrypt the signature, then he gets a code. He applies the same hash algorithm (for example MD5 pe SHA1) that you used to the whole message, you should mention what hash algorithm you used in the message, and if the hash result he got matches the code/hash result that he got after decrypting your digital signature with your public key, it means not only that the message was sent by you, since you are the one who owns your private key that encrypted the digital signature, but also that the message he received is the original one you meant to send, since its hash matches the hash in the signature. Because of the signature, you cannot deny the authenticity of the message and of yourself.

But how can you make sure that the public key you send in the open cannot be tempered with, or have someone make a public key of their own and claim it's your key? That way they can decrypt the messages that are meant to you, and you can't. That is where digital certificates come in. Digital certificates make sure that the public key posted in your name is indeed your public key.

Digital certificates include information about the public key, information about the identity of its owner called the subject and the digital signature of an entity that has verified the certificate's contents, a 3rd party called the issuer. If the signature is valid, and the software examining the certificate trusts the issuer, then it can use that public key to communicate securely with the digital certificate's subject.

Why can't you just make a simple hash to guarantee the integrity of the message? Because an attacker can take your message, create a new one, and then make a new hash then send them to the receiver. The hashes will match and there's no way the receiver can tell whether he got that message from your or an attacker. Where as in the case of digital signature, the attacker doesn't have your private key to go that extra mile of asymmetric key encryption. He can encrypt it with his own private key, but then the receiver won't be able to decrypt it with your public key and will realise that signature is not from you.

But what if you want to ensure the integrity of the message but not necessary the authorship of the message and you just want the messages to work faster? You're not at work or in a public institution, you talk to a friend and none of you cares about the legal bindings of making sure the message is from each other. That's where HMAC comes in, unlike digital signature, the HMAC encrypts the hash of the message with a symmetric key.

Being encrypted with a symmetric key, the authorship of the message cannot be tracked back to you, because you're not the only one who has access to that symmetric key. The receiver also has the same key and he could have made that message himself. Of course, they are the only 2 people that have access to the symmetric key, so unless one of them compromised the key, the message that you received, if you know that you're not the one who wrote it, you can be sure that it came from the other person who has the symmetric key.

The H in HMAC stands for hash and the MAC stands for message authentication code, meaning a code that guarantees data integrity as well and authenticity, by allowing the viewers who posses the secret key to detect any changes to the message content. A MAC usually has 3 parts: a key generation algorithm, a signing algorithm and a verifying algorithm.

In short:

Digital Signature = Hash of the message is encrypted with the private key of the sender.

HMAC = Hash of the message is encrypted with the symmetric key.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to crypto.SE. This answer has multiple issues. A few: "reverse engineer" is finding specification from example or code, when the standard assumption with hashes is that their construction is public; you want: difficult to "reverse", but that's only one of the desired properties of a hash. "The result of applying hash to a text is a long code" is misleading: output is typically shorter than input; you want "a fixed-size bitstring". "If the 2 hashes match it means the message is the original one" is wrong, the hash can be altered too! $\endgroup$ – fgrieu Jun 29 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.