2
$\begingroup$

I'm preparing for an examination of an Information Security course at university, but I'm not sure about an explanation I created for a specific exercise. The question is:

There are now DSA versions using a 2048 bit prime number. Which hash function would you choose?

My answer:

The goal of the hash function is to provide enough security, while not being overkill for it's application. DSA works by choosing a prime number p (of length 2048 bits in this case), and a prime number q (160 bits for the 1024 bits case of p, so more than 160 bits for the 2048 bit case). Then the value s is generated by calculating s = [k^-1 * (H(M) + x * r)] mod q (with x being the private key and r being a value that was generated earlier in the process). Now because the generated value is calculated mod q, the result is no longer than q itself.

It is thus pointless (or overkill) to use a hash function that produces values with more than |q| bits. We know that |q| > 160 bits (and it will presumably be no longer than 256 bits). This allows us to choose for SHA-256 as an appropriate hash function, as it is not yet known to be broken, and produces the smallest hash values not known to lower the degree of security of our DSA algorithm.

Is this a correct explanation for this problem? I can't seem to find the rational behind some hash function choices for DSA elsewhere.

$\endgroup$
  • $\begingroup$ The standard for DSA, FIPS186 (-3 and -4), specifies subgroup size 224 or 256 for group 2048, and 256 for 3072. It (indirectly) recommends the hashsize equal the subgroup size and (unlike earlier versions which directly specified SHA-1, for 160 in 512-to-1024) references FIPS180 for the hash(es), which in addition to SHA-1 for 160 has two sets the correct size: SHA-224 SHA-256 and SHA-512/224 SHA-512/256. It presumably will be updated to add SHA-3, but hasn't been yet AFAICS. $\endgroup$ – dave_thompson_085 May 21 '18 at 22:55
4
$\begingroup$

This is reasonable and gets at most of it.

One critical limit of DSA with a 160-bit prime group is that you can't get better than 80-bit collision resistance by the birthday bound. You really want a uniform random function from whatever is your finite message space to $\mathbb Z/q\mathbb Z$, but that's a pain to achieve, so you might choose a $\lceil\lg q\rceil$-bit hash function like SHA-1—but SHA-1 is known not to be collision-resistant at the maximum possible 80-bit security level in the circumstances.

You might be concerned about the small modulo bias of reducing a uniform random integer in $\mathbb Z/\lceil\lg q\rceil\mathbb Z$ modulo $q$. You might be concerned about security against multi-target attacks. If you are concerned about that, then you might choose a double- or 1.6-size hash like SHA-256 or BLAKE2s, and attain collision resistance up to the maximum possible 80-bit security level.

For a loose comparison, a double-size hash, SHA-512, was chosen for Ed25519's ~256-bit group, for several conservative reasons. Now, the comparison is not precise, because Ed25519 is a qualitatively different signature scheme—and superior in pretty much every respect, except compliance with US government standards, to DSA: it uses the hash in a different way so it doesn't even rely on collision resistance, it doesn't break catastrophically and barf out your private key if you use it on a machine with a broken RNG, it's faster and smaller, etc.

$\endgroup$

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.