a dictionary + rules + time. yes (i assume - i have no inside knowledge).
[...] passwords which were randomly generated are, and are likely to remain, safe?
it depends on the length and range of characters. random passwords are still vulnerable if they are short and/or use a restricted range of characters. they can be found "by accident" when using rules and dictionaries. they can also be found by simply trying all combinations ("a", "b", ..., "aa", ..., "ab"...). length and character range protects against both of these.
it's likely that attackers will use all available approaches, including simple brute force. i focused on dictionaries + rules above because (1) that's generally more efficient and (2) some people don't seem to realize how powerful it is.
Also, if there is no restricted range of characters, and a solid, random password is used, how can the attacker know when they have broken it, short of trying them all against the actual server?
Edit: Forget that last bit. I'm confusing myself.
You just keep going in bruteforce and build bigger rainbow tables / variant dictionary attacks. Given a large number of GPU's you will get all passwords.. time though could be a number of years to thousands of years.
I guess if this ever actually became a relevant concern, you'd simply keep adding a few extra chars to the hashing algorithm output to keep it beyond the range of reasonable.
9 = 58.5-bits
10 = 65.0-bits
11 = 71.5-bits
Edit: Spelling & Grammar
My question: is there an intrinsic weakness in storing these passwords at a central location? E.g. would it be feasible that LastPass gets targeted by a complicated blackhat attack, and then instead of losing just one of my passwords I lost them all? Or is the manner in which they are encrypted and transmitted secure enough to prevent this?
Thanks.
That's the weakness of services that are supposedly "Host-proof". If the host is sending you the webapp/javascript/webpage in which your data is decrypted, each and every time you visit their website, you have to trust that they wont (or someone else wont) modify it in a malicious way in order to gain access to your data.
The only way to be safe from this kind of attack is to use the same trusted copy of the code, and not use any new versions until you trust that it is also safe, or to somehow verify that the webpage sent to your browser is exactly what you expect it to be.
Cortesi has a very good write up on this issue: http://corte.si/posts/security/hostproof.html
An alternate option to reduce some of this: http://www.rakkhis.com/2011/06/i-was-hacked-mtgox-bitcoin-3-...
It's only technically "buying some time." In reality it's keeping it completely secure.
And what use would a hacker have attacking a whole database full of them? It would take too long to do it, even with less secure passwords. It takes your fruit out of the "low hanging" category, which is a bit of security in itself.
so what's D? i imagine most people would use common words, so let's take the most popular 1 percent of "dict/words" on my computer. that's 4,000 words. log2(D^N) = N * log2(D) = N * 12 (since log2(1000)~10).
now in another thread here there's an article saying that 9 characters drawn from an alphabet of 100 (lower+upper+symbols) is around the current limit. the equivalent number of bits there is log2(100^9) = 60. so you'd need about 5 words (5*12=60) for the same level of security.
tl;dr: you need more than 5 words (very) roughly. i am not 100% sure i have the maths right, either :o)
in more practical terms, i don't know of a program that actually does this. the programs i know about typically only combine a few words. but i am no great expert, and it would be fairly easy to write such a program.
[edit: actually, you are less safe than i estimate above if the attacker is smart, because the words probably aren't independent (most people will use meaningful sentences). so you can use markov chains to hugely reduce the search space (in more general terms: "the" will be followed by a noun phrase, etc). so you need significantly more than 5 words. heh. if someone wants to pay me to write such a program, please get in touch... ;o]
WTF. some fuckwit downvoted this? i wrote the text i am correcting. screw you. why do i bother to write useful comments? this place gets worse.
Also, some downvotes are cast in error. This is very easy on touch-screens, and occasionally a problem elsewhere. Since totals are no longer displayed, a person may not even realize their intended upvote registered as a downvote.
So assume it was a mistake. Or a hopelessly grumpy person whose bad attitude is best ignored, rather than amplified with curses and complaints. Brush off the first downvote or two, and well-considered upvotes follow soon enough.
you start with a dictionary. a good dictionary combines multiple passwords, slang, common patterns of keys on the keyboard, and old, known, passwords (so all the entries here will be added, for example).
but that's just the start. the cracking programs also have rules. in simple terms these can be "shift to upper case" or "combine two words from dictionary" or "reverse word" or "replace "e" with "3". and there are common sets of rules that people develop (and test) that do standard transformations like automatically making passwords "leet", or extending with common sequences (123), etc.
and you can automate this. so something like hashcat will generate random rules and apply them to the dictionary. because the rules are written so that they can be composed this is surprisingly powerful and probably explains some of the "harder" cracks on this list.
the only way to beat this, then, is to use random passwords (for example, as generated by keepass) and to make them large enough that just running through every combination doesn't work.
on size: what is important is the number of available combinations. systematic cracking - trying every possible combination - still uses common characters first so "size" is a combination of character variety and number of characters. again, something like keepass makes this easy.
finally, note that on some old or poorly maintained systems, you may be restricted (perhaps without knowing) to 8 characters. then using a wide range of characters is critical.
i know this is obvious to many, but some of the comments about "hard" passwords made me think it might be useful...