Re: DSS/DSA

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 03/17/04 

Date: Wed, 17 Mar 2004 14:21:07 -0500

They came up with a new standard for hashing:
http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf
with larger outputs.
I'm expecting they will come up with a new DSS standard that uses a larger
prime
modulus and one of these new hash algorithms.

For hash functions, you sometimes need to consider the birthday paradox.
For a
given x, I can find x' different from x, such that H(x) = H(x') in
2^hash_length
work factor, where hash_length is the length in bits of the ouput of the
hash function
(160 for SHA1). But I can find two arbitrary inputs, x and x', such that
H(x) = H(x'),
in 2^(hash_length / 2) work factor, with good probability. That would be
2^80 for SHA1.

So it depends how you are using your hash function.

In the analyses of DSA, you need to consider discrete log on the subgroup of
size
2^160, which can be done in 2^80 work factor.

--Anton

Relevant Pages

  • Re: hash/SHA-1 questions
    ... If we take SHA1, by internal contruction for small number of bits, ... Without more precision than "H is a hash function with N-bit output" ... This pathological hash function enjoys excellent second premimage ... indistinguishibility from random, and preimage resistance), ...
    (sci.crypt)
  • Re: hash/SHA-1 questions
    ... > If we take SHA1, by internal contruction for small number of bits, ... For example, consider the following hash function, ... > defined on same input and output domain as SHA1 ... > indistinguishibility from random, and preimage resistance), ...
    (sci.crypt)
  • Re: NSA "telephone monitoring" program
    ... since MD5 is actually supposed ... to be a cryptographic hash function, ... consider that it's dead and gone. ... Flaws found in SHA1 ...
    (alt.computer.security)
  • Re: a program to delete duplicate files
    ... > should be extremely small, or else, your hash function is not a good one. ... We're talking about md5, sha1 or similar. ... > comparing files. ... > than the probability of my computer returning the wrong answer, ...
    (comp.lang.python)
  • Re: SHA1 and entropy
    ... we don't need to get into all that random oracle ... then let's just talk about SHA1. ... As for design principles for building the inner core of a hash function, ...
    (sci.crypt)
Quantcast