Hacker News Reader

Comment by lyle_nel | Hacker News Reader

Yes the training set should be representative of the candidates you want to crack, also the larger the training set is, the better it seems to perform. It is also important to note that, as passwords are being cracked they become part of the training set. So the program can start of completely blind then it will figure out common structures as the simulation progresses.

I have not put them head to head, but the program seems to find passwords that are far outside the tractable search-space for a bruteforce attack. Passwords like the following are found withing a few hours:

34 a111111111111111111111111111111111

20 12345678900987654321

19 9876543211234567089

19 password12345678910

18 sexytinkerbell2013

18 prettyprincess4812

18 mickeymouseforever

18 littlepinkprincess

18 iloveyoumomforever

View on HN

So XKCD style correcthorsebatterystaple-esque passwords would fall in no time?

No, the point of that style of password is that you choose the words randomly. Random words are just easier to remember than random characters.

Almost yea. In a few hours it manages to find these horse related passwords.

15 strawberryhorse

15 ilovehorses1995

15 ilovehorses1994

15 ilovehorses1234

15 horselover4ever

Cool system. For clarity though, those aren't xkcd style passwords. They're words that form a normal pattern. Xkcd requires that the words are randomly generated.

Sorry for going slightly OT but I think more people should know this:

xkcd style passwords are actually called diceware passwords [1], the wikipedia article [2] links to arstechnica that reported in 2014 [3] that the original author upped his recommended diceware password length to at least 6 (random) words.

You can obviously always use a bigger dictionary too (as long as you choose truly random).

[1] http://world.std.com/~reinhold/diceware.html funny enough, chromium doesn't like the ssl versions the site uses "ERR_SSL_FALLBACK_BEYOND_MINIMUM_VERSION"

[2] https://en.wikipedia.org/wiki/Diceware

[3] http://arstechnica.com/information-technology/2014/03/dicewa...

this is easier to understand with a bit of math..

let's say you have a pad lock with a 4 number combination, each of those numbers being a ring of 6 numbers themselves(o)

we have four 'slots' with six possible numbers for each slot

that means there are a total of 1296 combinations, (possible values)^(slots), 6^4=1296

a contemporary computer can do 1300 calculations perceptually instantaneously

now we look at randall and diceware's suggestion of using a series of words to bulk out your password, since a word in english is built of a possible combination of 26 character alphabet the possible values becomes 26

for a four letter word, all possible combinations of those 26 characters becomes 26^4=456,976 possible combinations, again, all values can be computed in nanoseconds

what i think randall and diceware is hoping to achieve is a higher permutation value with little tax on the user's memory

conceptually [c,o,r,r,e,c,t,h,o,r,s,e,b,a,t,t,e,r,y,s,t,a,p,l,e] is 25 characters long with each 'slot' having 26 possible combinations.. 26^25~23x10^34, that is a huge number of possible permutations which makes brute forcing finally impractical

but here is where the whole thing starts to break down a bit..

because the suggestion is to use real words to aide in remembering which negates character length in lieu of number of words

that also means that figure above is significantly less because the first in that list of 456,976 permutations is ['a','a','a','a'] which would be invalid in regard to existing words, so in reality that 450,000 figure is significantly less

'correcthorsebatterystaple' can be broken into 25 characters 'slots' or 4 word 'slots': [correct,horse,battery,staple]

what was 26^25, is now (possible words)^4

we can keep going, look at randall's most recent book(i), using the 1000 most used words

possible words becomes 1000 and 4 slots we are looking at 1000^4=1,000,000,000,000 possible permutations

which will take a contemporary laptop a few hours, respectively, to churn out

all this broken into a chart:

     81 = 3**4 : [(3),(3),(3),(3)]
     253 = 3**5 : [(3),(3),(3),(3),(3)] 
     256 = 4**4 : [(4),(4),(4),(4)] 
     456976 = 26**4 : [(26),(26),(26),(26)]
     1000000000000 = 1000**4 [(1000),(1000),(1000),(1000)]
    ~230000000000000000000000000000000000+ = 26**25 : [(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26)]
    ~640000000000000000000000000000000000000000000+ = (26*2+10)**25 : [(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62)]

what this is showing you, is that anything that makes things easier for you also will make things easier for a cracker

for best security increase the number of characters when possible avoiding words.. using a combination of lowercase(26 characters) and upper case(26 characters) and numbers(0-9, 10) for 26+26+10=62 possible values.. and put those characters in as many slots as you can muster

(o) http://www.padlocks4less.com/media/catalog/product/cache/1/i...

(i) https://xkcd.com/thing-explainer/

diceware is a list of 7776 words. You pick 6 words. (That's 7776^6). If the attacker knows you're using Diceware, knows what word list you're using, and knows how many words you're using (ie worst case) you get 12.9 bits of entropy per word. If the attacker doesn't know how many words you're using, or they don't don't what wordlist you're using you get more than 12.9 bits of entropy per word.

You've made a mistake here:

> 'correcthorsebatterystaple' can be broken into 25 characters 'slots' or 4 word 'slots': [correct,horse,battery,staple]

> what was 26^25, is now (possible words)^4

1) No-one suggests using 4 words. Randall uses 4 words because it fit in the cartoon. Diceware suggests using 6 words for minimum.

2) No-one at all suggests using just the 1,000 "most common words". Diceware is a list of 7776 words. Except there's more than one diceware list.

i should think you could grok from my comment that i'm on board for your two points

why explain away the comic as just being an example but then confront the comment as being unaware?

why did i use 4 word 'slots' instead of diceware's suggested 6 minimum? because the comic did and that was referenced in the gp

why did i use 1000 words instead of diceware's 7776? because the number of words is arbitrary for an explanation, and, as i stated, i was playfully referencing, and intentionally promoting, more of randall's work

your comment fails to negate anything in my explanation, which was meant as a means of explaining how to think about these things

what the effectiveness of the ga cracking repo shows is that people are using even less possible words than dice's 7776 or randall's 1000

and the concluding statements that more variety with less patterns equates to better security stands

> The complete list contains 7776 short words, abbreviations and easy-to-remember character strings. The average length of each word is about 4.2 characters(o)

i'll be kind and round that 4.2 up to 5

> Diceware suggests using 6 words for minimum

so we are looking at 6 words of 5 characters.. 30 total characters

let's compare diceware to individual characters:

    ~220000000000000000000000+ = 7776**6 : diceware with 6 word minimum
    ~800000000000000000000000000000000000000000+ = 7776**10 : diceware with 10 words
    ~2800000000000000000000000000000000000000000000+ = 26**30 : english alphabet, 30 characters

>what this is showing you, is that anything that makes things easier for you also will make things easier for a cracker

(o) http://world.std.com/~reinhold/diceware.html

Why are you comparing a 30 character word with a 6 word passphrase?

You need to look at bits of entropy.

A 6 word passphrase is about the same as a 12 character password if you use any printable ASCII character.

because entropy is directly related to the number of possible values and number of values in the password, which is what i am comparing

i then went on to establish those values as being only those in the english alphabet, 26 characters, stead your referenced ascii set or even the diceware character set which allows some special characters

then i took the minimum suggested diceware length of 6 words, rounded the average word length of 4.2 up to 5, which gives us 6*5=30 characters

so one diceware password example:

    affixafireafootagainagateagave
    
    can be seen as diceware would have it, 6 words of length 5:
      [affix, afire, afoot, again, agate, agave]
    or 30 individual characters:
      [a,f,f,i,x,a,f,i,r,e,a,f,o,o,t,a,g,a,i,n,a,g,a,t,e,a,g,a,v,e]

so utilising any underlying pattern, here only using the diceware wordset, weakens a passphrase of equal length

or if you want to abstract away from the actual values that you use to determine a passphrase's strength you could say: diceware lowers the entropy of an individually random value passphrase of equal length

but that phrase unecesarily contains verbage that can confuse whereas my previous comment showed all of the number possible permutations in such a way as to easily see that one is greater than the other making the guess space larger

Just to add to that. The program as it currently is rarely finds passwords that consist of more than 3 long words, which can still amount to decently long passwords. I have not tried to give it an english dictionary as a seed population. Maybe it would perform better if I do that.

I'd be interested to see how it copes with Diceware. Maybe generate a list of 1000 Diceware passphrases (or several lists of 4, 5, and 6 word phrases) and use the diceware wordlist as a seed population.

Sure I'll run some tests for you.

I ran 2 experiments each lasting 120 seconds.

For the diceware list as a seed population it finds 4570 passwords. The 6 longest ones are:

11 michelle420

11 karen123456

11 iloveyouu16

11 iloveyou789

11 iloveyou234

11 iloveyou191

For the top 2000 ngrams from the rock_you list(which is the current list used) it finds 5317 passwords. The top 6 longest passwords are:

14 fuckyouhackers

13 fuckyouhahaha

11 sexylove889

11 scooter1234

11 princess123

11 iloveyouu16

Reply on news.ycombinator.com