3
$\begingroup$

I'm studying Hash functions and Digital Signatures in sequence, and came up with some doubts about their usage.

First of all:

  • What is the difference between hashing a document and signing it?
  • And why aren't Standard Hash Functions considered fit for message authentication?

More specifically, considering Keyed Hash functions (MACs):

  • Are keyed hash functions (MACs) the mechanism on which Digital Signatures are based, or are they a way to implement a particular scheme of Digital Signature (e.g HMAC provided along with the message)?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Digital Signatures, hashes and MACs can do similar jobs. They allow someone sending a message to a check value along with the message. They allow someone receiving the message to verify that the message corresponds to the check value. However, a hash is an unkeyed operation; anyone can compute the hash of the message. So, while they provide protection against accidental message modification, they cannot provide any protection from an active attacker.

Digital signatures and MACs both ensure that someone in the middle (without the key) cannot modify a message without being detected (by the check value not validating).

However, even here still a difference; with a MAC, the sender and the receiver have the same key. So, someone in the middle (without the key) cannot forge a message; however, the receiver can himself generate a message that validates.

With a digital signature, this is not the case. The sender has a 'signing' key, and the receiver has a 'verification' key; the verification key allows the receiver to validate messages; however, he himself cannot forge any messages.

So, if the question is "should I use a HASH, a MAC (such as HMAC), or a digital signature", well, that depends on how much you trust anyone who does the validation. If you just want to protect accidental changes to the message, well, a hash is fine (and doesn't force you to do the bother of key management). If what you need is to protect messages from Alice to Bob (and so Bob is the only person who will ever validate a message with that key), then a MAC is appropriate (and a lot cheaper). On the other hand, if you are posting messages to your blog, and you want everyone to be able to verify that you are the one posting, well, everyone will need the verification key, and so in that case, a digital signature is required.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I understand, but I know of existing digital signature schemes based on symmetric key crypto algorithms...what case is that? $\endgroup$
    – Matteo
    Jun 18, 2012 at 13:46
  • $\begingroup$ @Matteo: the only digital signature scheme I know of which is based on symmetric crypto is the Merkle and Lamport one time signature schemes; anything else would be a MAC (Message Authentication Code), as the sender and verifier would share keys. $\endgroup$
    – poncho
    Jun 18, 2012 at 13:51
  • $\begingroup$ It was exactly the scheme I was thinking about. So, if I got it right, Lamport is very similar to MAC (conceptually)? Just a thing I do not understand: you say that with a MAC...the receiver can himself generate a message that validates in which way will this cause problems to the authentication of a message (or of its source)? $\endgroup$
    – Matteo
    Jun 18, 2012 at 13:58
  • 1
    $\begingroup$ @Matteo: no, Lamport is a digital signature algorithm, not a MAC, as the verifier cannot generate his own signatures. As for what problems a receiver generating a message, that depends on how the scheme is used (and who do we trust to do what). If we're using the same key to communicate to a lot of people (and so everyone has the verification key), it's generally the case that we don't want one verifier to forge a message that would fool another (that is, we don't trust them not to do so); in this case, we need a Digital Signature rather than a MAC $\endgroup$
    – poncho
    Jun 18, 2012 at 14:03
  • $\begingroup$ thks for explanation! ;D $\endgroup$
    – Matteo
    Jun 18, 2012 at 14:10
2
$\begingroup$

A hash function is a publicly computable function $H: \{0,1\}^* \rightarrow \{0,1\}^n$ for some fixed output length $n$. For a secure cryptographic hash function it should be infeasible to find two inputs $m_0$, $m_1$ such that $H(m_0)=H(m_1)$. This is called collision resistance.

A signature scheme is a triple of Algorithms $(\mathsf{KGen}, \mathsf{Sign},\mathsf{Verify})$. You use $\mathsf{KGen}$ to generate a random key pair $sk,pk$, $sk$ is secret and $pk$ is published publicly. $\mathsf{Sign}(sk,m)$ is used to compute a signature $\sigma$ under public key $pk$ on message $m$. $\mathsf{Verif}(pk,m,\sigma)$ can be used by anyone to verify the validity of $\sigma$. For a secure signature scheme, it should be infeasible for anyone to compute a valid signature on a message without knowing the secret key $sk$.

As you can see, a hash value can be computed by anyone, whereas a signature can only be computed by someone knowing $sk$, so their purpose is very different. A hash can be used to verify, that the document has not been altered only if the hash value comes from, a trusted source. Sending the hash value along with the document does not give you any guarantee. A signature on the other hand proves, that the document has not been altered after somebody knowing that particular secret key has signed it. That is, a signature can be used to achieve integrity and authenticity.

HMAC is neither a hash function nor a digital signature scheme. It is a MAC scheme. (Kind of a symmetric version of digital signatures.)

Signatures and hash functions are related in the way, that many signature schemes us a hash function as a building block. (For example in the hash-the-sign approach.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ there is a typing error at the end of the second paragraph about pk and sk i guess...beside this, can you please explain me better the following: 1. hash value can be computed by anyone, whereas a signature can only be computed by someone knowing sk this is not the case of keyed hash (typically used for MAC) 2. Sending the hash value along with the document does not give you any guarantee. why not?I thought exactly the opposite...Am I wrong? $\endgroup$
    – Matteo
    Jun 18, 2012 at 13:50
  • $\begingroup$ A MAC is not a hash function. A hash function is supposed to be computable by anyone. There are constructions of MACs from hash function (under very strong assumptions.) but those are not hash functions. A hash function itself does not take a key as input. As poncho said, the only thing a hash can do is catch accidental changes (such as random bitflips). If I maliciously changed the document I could simply compute the new hash, and you had no way of noticing. $\endgroup$
    – Maeher
    Jun 18, 2012 at 14:03
  • $\begingroup$ Regarding the fact that you could alter the digest along with the message I agree. But MACs are Hash functions... Handbook of applied cryptography chapter 9 page 324 figure 9.1! $\endgroup$
    – Matteo
    Jun 18, 2012 at 14:07
  • $\begingroup$ Hm, ok I have never seen that definition. Usually when we talk about hash functions in cryptography, we mean collision resistant hash functions. (on the lower right in that figure) If you are asking about the difference between MACs and Signatures, maybe you should reword your question (and I should rewrite my answer to fit the question ;) ). $\endgroup$
    – Maeher
    Jun 18, 2012 at 14:15
  • $\begingroup$ Yeah maybe I didn't state it clearly!sorry for that, but anyway your answer was useful for understanding why an hash function isn't fit. I'll change question so you can update answer if you wish and have time! $\endgroup$
    – Matteo
    Jun 18, 2012 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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