http://blog.webernetz.net/wp-content/uploads/2013/07/Password-Entropy.jpgWe traditionally think of password strength needing to be strong enough to prevent a brute force attack on a single password, but the password-only protection (ie, brain wallet) of NXTcoin presents a different challenge. With typical accounts (e.g. bitcoin qt) an attacker would first have to gain access to your wallet file and THEN start a brute force attack on encryption or other passwords. But we now have to prevent a random brute force attack, that is, a situation where the attacker does not need to pick the single correct target password for a stolen wallet file, but rather he need only guess anyone's password correctly to gain access to their account without any access to a wallet file. There are numerous postings here of people complaining that they lost their NXTcoins from their wallet, likely because they picked a fairly simple password and an attacker guessed it correctly. An attacker with even a modest setup can easily guess over a billion passwords a day so many possible passwords are vulnerable.
If people keep losing their coins to these simple attacks then faith may be lost in the NXTcoin protocol which would be a shame since it is such an interesting innovation in many many ways. One innovation of NXT is that it is purely a brain wallet, something many of us aren't used to (unless we use Electrum clients) so we need to adjust our understanding of the importance of password strength while also making a real brain wallet based on words possible. Of course we could all make passwords of random characters that consume all 256 bits of entropy available, but I'm taking the approach of trying to come up with reasonable recommendations for those who want to try and rely on a reasonable number of random words as their password.
So how good do our passwords really have to be to insure that it is extremely unlike that anyone would lose their wallet due to a random brute force attack?
Jean-Luc (NXTcoin developer) gives a starting point as to how many passwords a processor might be able to guess in a second:
... On my laptop, with the Vanity.java code I posted on bitcointalk, I can go through 8000 passwords per seconds.
Simple attack:Assuming the attacker starts with the lowest entropy passwords and moves up from there we can calculate how many bits are needed to prevent such an attacker from guessing your password in the course of a year:
Attacker entropy covered = logbase2(1 processor * 8000 pws/sec * 31536000 sec/year) = 37.9 bits of entropy
According to this excellent post on entropy and passwords (
http://blog.webernetz.net/2013/07/30/password-strengthentropy-characters-vs-words/ , see jpg above) 38 bits of entropy is what you get in a password consisting of 12 random numbers, 6 random characters (drawn from 83 possible), or 3 words (drawn from 10,000). So that gives you an idea of what type of passwords will
definitely be hacked, if your password is as simple as "Igetbread", you'll lose your coins soon.
Note that 38 bits is not a suggested level, it is the MINIMUM entropy needed to have any chance of surviving such an attack.
(In all calculations I assume the attacker chooses a password type and sticks with it (e.g., number string, character string, or passphrase), though there are methods of more efficient attacks on non-random passwords)
Expected attack:But an attacker who is serious (either about stealing coins to get rich or destroying NXT by destroying people's trust in it) and has access to resources will have many more processors and a probably a more efficient guessing algorithm. I don't know what's realistic for either of those (suggestions welcome!) so I'll say 1,000,000 processors and an algorithm that guesses ten times faster, 80,000 pws/sec. In this situation the attacker will be able to guess up through an entropy of 61 bits in a year. I judge that such a level of attack is likely (definitely if NXT continues on it's current growth trajectory) and passwords that would be compromised by this attack are: 18 numbers, 10 characters, or 4 words. This is still a pretty low bar for passwords, but the thought that ALL NXTcoin wallet passwords that do not exceed these lengths are likely to be successfully attacked is still unsettling. After all, many websites consider 8-10 random characters a very good password.
High-end attack:What if the attacker has an incredible algorithm (1,000,000 pw/sec) and even more processors (10,000,000)? Then the threshold
becomes 68 bits of entropy, which would be a password with 6 words (drawn from 10,000). If the attacker carries this out for 10 years then the minimum entropy needed to avoid the attack would be 71.5 bits. (Again, I welcome input on how realistic these # of processors and guessing algorithms are for a resource rich attacker)
However, these previous calculations all assume that the attacker will start at the lowest entropy passwords and move up as he goes.
If instead an attacker sets the max bits of entropy he will attempt to compromise higher, then his reach can increase significantly. With the 'simple attack' an attacker who used a max limit of 40 would guess one out of every 4.3 passwords with 40 bits of entropy or less (in a year) and if he choose a max of 50 he would guess one out of every 4460 passwords with 50 bits or less.
In the case of the 'Expected attack', this would lead to chances of one in every 468 passwords compromised that have 70 or less bits of entropy or one in every 480,000 with less than 80 bits. If this attack were carried out for 10 years, those would change to one in every 47 and one in every 48,000.
On the extreme side, if the 'High-end attack' were carried out for 10 years then passwords with 80 bits of entropy have a one in 380 chance of compromise while those with 90 bits have a one in 390,000 chance. A password with 100 bits would have a chance of one in 400,000,000 to be compromised.
Conclusion:Now, one in 400,000,000 or even one in 390,000 sound pretty unlikely (though they are not far from the chances of winning lottery tickets that people buy everyday) but they are probably worth avoiding if is as simple as adding an extra word or two to a passphrase. Furthermore, I may underestimate the capability of current or future technology in carrying out a brute force attack. For these reasons
I think that NXT users should make wallets with 140+ bits of entropy, the absolute minimum should be 120 bits.
Passwords with 140 bits of entropy are composed of:
43 random numbers
22 random characters (of 83 possible)
11 random words (from a pool of 10,000 possible)
9 random words (from a pool of 90,000 possible)(Note this recommendation is well above the 80 bits of entropy frequently suggested for internet passwords)
If you want a brain wallet made of random words then make sure you know how big the pool of words is that you draw from.
Generating a list of random words is probably safest to do with a physical dictionary (ie, completely offline and non-electronically) but here are some links I found with a quick search for word generators - I can't vouch for these products in any way and I'm sure there are many other good ones out there:
90k words online:
http://www.wordgenerator.net/random-word-generator.php28k words online:
http://coyotecult.com/tools/randomwordgenerator.php300k words program:
http://www.gammadyne.com/rndword.htmUsing an online generator is risky because the website could be recording words or could use an poorly/predictably randomized algorithm. If you do use word generators online, then maybe use multiple ones to come up with the password so if any of the websites are logging entries or compromised they won't be able to record your password. That said, many people would never use an online generator due to the risks.
An ideal solution might be like that of Electrum: the NXT software could give a user a new password of 11+ random words when the user wants to create a new account. This could be modified by the user but would at least make the point to them that the password should be very long. At the least, a better warning when putting in a short password would be great - maybe the warning could suggest the above
password sizes or something like that. If people want to be stupid they will still be stupid and make a short password, but at least such an improved warning would give them a chance to make an informed decision.
I know this may all be pretty basic info for the many experienced folks out there but I wanted to post this as guidance for those who aren't this knowledgeable or thinking this carefully.
And please don't hesitate to check/ask questions about my math. I'm pretty such these calculations are correct but of course I may have made mistakes.
Cheers!
paultramarine
NXT: 7633621308036609036
BTC: 1AedbB3jAv1AaTQZ1KMiaVoqu1VFouHGCj
*Some might take issue with my point that NXT is susceptible to this attack because it's the users who pick their passwords - but NXT could have a minimum length password or some other way of making these attacks much less likely. Ultimately, yes, people do foolish things like make short passwords and that is up to them.
