When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)? Quoting the article Gone in 60 Months or Less:


  The National Institute of Standards and Technology (NIST) has disallowed the use of 1024-bit keys after 31 December 2013 because they are insecure. Rapid advances in computational power and cloud computing make it easy for cybercriminals to break 1024-bit keys. When a researcher from Ecole Polytechnique Fédérale de Lausanne (EPFL) in Switzerland cracked a 700-bit RSA key in 2007, he estimated that 1024-bit key lengths would be exploitable 5 to 10 years from then. Not even three years later, in 2010, researchers cracked a 1024-bit RSA key.


So, we're talking about a 512-bit "cryptographically secure" hash meeting cipher implementations where 1024-bit keys are not disallowed anymore by the end of the year 2013.

What does that mean for SHA-3, as the NIST submission sets the rate $r$ as 1152, 1088, 832, or 576 (144, 136, 104 and 72 bytes) for 224, 256, 384 and 512-bit hash sizes, respectively? Can we still think about using SHA-3 to hash passwords to the desired bit-length and comply to NIST rules on the long run, or do we need to expect NIST gradually starting to enforce that 1024-bit key rule across all protocols?
That's not the same kind of key.
Symmetric keys are a bunch of bits, such that any sequence of bits of the right size is a possible key. Such keys are subject to brute force attacks, with a cost of $2^n$ for an $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is &quot;perfect,&quot; then enumerating all possible keys is the most efficient attack (i.e., &quot;no shortcut&quot;).
RSA keys are mathematical objects with a lot of internal structure. In a 1024-bit RSA key, there is a 1024-bit integer value, called the modulus: this is a big integer whose value lies between $2^{1023}$ and $2^{1024}$. To break an RSA key, you &quot;just&quot; have to factor this modulus into its prime factors. There are relatively efficient algorithms for that, to the extent that factoring a 1024-bit RSA modulus is on the verge of the feasible. It has been estimated that the &quot;cost&quot; of factoring a 1024-bit RSA modulus is similar to the &quot;cost&quot; of brute-forcing a 77-bit symmetric key. Note that this is not the same kind of cost (you need a lot of fast RAM for factoring big integers, whereas enumerating many AES keys requires no RAM at all).
DSA and Diffie-Hellman keys are also mathematical objects, with again a lot of internal structure. There is also a modulus, but a prime one, so it is not about factorization, but something else, called discrete logarithm. It so happens that breaking discrete logarithm modulo an $n$-bit prime has a cost that is roughly similar to the cost of factoring an $n$-bit RSA modulus (the DL cost is, in fact, a bit higher). So a 1024-bit DSA or DH key is also similar in strength to a 77-bit symmetric key (or maybe an 80-bit symmetric key).
Elliptic curve cryptography yet again uses mathematical objects as keys, but with another structure that fits in fewer bits for a given security level. Basically, you get &quot;$n$-bit security&quot; (resistance similar to that of an $n$-bit symmetric key) with a $2n$-bit curve.
Hash functions have no keys. Yet there is a concept of resistance to various attacks (collisions, preimages, second preimages...) with costs that can be estimated depending on the function output size (assuming that the function is &quot;perfect&quot;). For a hash function with an $n$-bit output size, resistance to collisions is in $2^{n/2}$, resistance to preimages (and second preimages) is in $2^n$. (There are ongoing discussions about making SHA-3 faster by relaxing this latter value, i.e., having &quot;only&quot; 128-bit security against preimages with a 256-bit output length.)

See this site for lots of data on comparative strength estimates. In particular, these NIST recommendations illustrate their point of view:

1024-bit RSA/DSA/DH and 160-bit ECC are &quot;as good&quot; as an 80-bit symmetric key.
2048-bit RSA/DSA/DH and 224-bit ECC are &quot;as good&quot; as a 112-bit symmetric key.
3072-bit RSA/DSA/DH and 256-bit ECC are &quot;as good&quot; as a 128-bit symmetric key.
7680-bit RSA/DSA/DH and 384-bit ECC are &quot;as good&quot; as a 192-bit symmetric key.
15360-bit RSA/DSA/DH and 512-bit ECC are &quot;as good&quot; as a 256-bit symmetric key.

NIST also says that the &quot;80-bit&quot; security level should be shunned except when mandated for interoperability with legacy systems.
These five formal &quot;security levels&quot; are the reason why AES was defined with three key sizes (128, 192 and 256 bits -- the two lower levels mapping to 2DES and 3DES), and SHA-2 with four output sizes (SHA-224, SHA-256, SHA-384 and SHA-512, the &quot;80-bit&quot; level being used for SHA-1); and, similarly, SHA-3 is (was) meant to offer the four output sizes 224, 256, 384 and 512 bits.