Do you know any good approach for de-hashing/actually bruteforcing hashed passwords in the shadow file?
On various operating systems, any good solutions/methods/programs.
Or is it better to upload a hash to somewhere? A paying-or free site?
If you like speed, you can employ commercial tools supporting large-scale clustering, like: http://www.elcomsoft.com/edpr.html (starts at $599)
Here is a short blog entry from Nov. 2010 discussing the use of Amazon’s EC2 Cluster GPU instances to accelerate password cracking.
I think the best password dictionary site at this time is from SkullSecurity: http://www.skullsecurity.org/wiki/index.php/Passwords
Another good set of password dictionaries: http://www.insidepro.com/eng/download.shtml
Read this PDF titled “Cracking Passwords Version 1.1” This document is for people who want to learn to the how and why of password cracking. http://tools.question-defense.com/Cracking_Passwords_Guide.pdf
John the Ripper (JtR) with some few well picked dictionaries and rulesets can be amazingly fast and efficient. Depending on the type and amount of hashes you got, you want to adjust how much you throw at it. Anything salted is going to be difficult, same goes for multiple rounds (FreeBSD-MD5), or just computationally expensive hashes (SHA-512).
My heuristic for order is to go for the cheap and easy stuff first: LM/NTLM. Then look at what you found, if you can observe any patterns (lots of passwords with alpha-nums only), then that's the rules you want to use. Also, once you find passwords for one type of hash, use it as a dictionary for other types of hashes.
I've tried using rainbow tables, because I thought they would give me a much greater coverage for the cheap stuff. Turns out there's like 6 different formats for the tables, and each software uses slightly different one, so I ended up spending two weeks just to get all the different utilities, downloading enough rainbow tables, and then doing internal format conversions. In the end, the rainbow tables turned out to be not that effective either. So I'd use rainbow tables only if you're dealing mostly with windows passwords, and you're gonna be doing it multiple times, because the prep time & effort for it is significant.
In the same two weeks time, and old quad core with 4 instances of JtR with 4 combinations of wordlists/rulesets cracked like 65% of passwords I needed to crack. That took me like 30 minutes to script. So be aware that the amount of time you want to invest in this stuff can vary greatly.
Before using brute-force approaches (as covered well by others here), check whether there are direct preimage cryptanalysis attacks on the password hash algorithm used for the hashes you have - whether it has been "broken" for password hashing purposes. If it has been broken, that may be a much faster way to recover good passwords, though brute-force may still be faster for weaker passwords.
For example, the original 16-hex-byte MySQL hashes are based on a terrible custom hash function which has been broken twice, such that 8-character printable ASCII passwords can be broken on a laptop in a few minutes, as documented at MySQL OLD_PASSWORD cryptanalysis? (note updated speed - not as fast/comprehensive as I thought before)
Worse than that is the "Collisions-R-Us" VxWorks vxencrypt password hash algorithm tracked as VU#840249 and publicized last year. It has so few actual possible hash outputs that it can typically be brute-forced in 30 minutes over the network.... And once again it seems that bad advice was given, this time in the CERT response, to just use SHA-512 one time. No mention of either salts or iterations....
Another example is LM hash. Although the underlying hash primitive they used was DES (which doesn't have any practical breaks), the way they used it destroyed the overall strength of the hash.
Note that MD5 has been broken for collision attacks, but not for preimage attacks. So for now we know of no direct attack on MD5-based password hashes and must do brute-force or rainbow. Nevertheless people are now very suspicious of MD5 and it should not be used for password hashing.
As always, it depends what your aim is.
My usual go-to tool just for pure speed is John the Ripper - which will brute force, dictionary attack, and blends. This is also ideal for password strength audits, as you can report on how many passwords lasted 1 hour, 2 hours etc.
Rainbow tables are an excellent tool where the password length is within the rainbow table spec., where the result will come back incredibly quickly (seconds) if the hash is in the table. Not so useful for an audit, but useful for a targeted test on a particular account.
Uploading hashes can work - however you then have provided the owner of that site with a password on your system.