6 ms·
Generate memorable passwords using Markov Chains, Huffman trees, and Dickens
- jbclements 12y agoSeriously. Has someone already done this? Next gen peer review, anyone?
- espadrine 12y agoIt's weird, but I actually had a very similar idea a few years back! I struggled implementing it and left it half done. I was trying to work directly with the letter frequencies; using a Huffman tree is much nicer. Instead, I tweaked it to generate random Sherlock Holmes paragraphs. It gave the best results with Markov state strings of size equal to the average word size. It's great to see that it gives a really nice output. Also, your paper is a breeze to read. I ended up making this[0], which is a Diceware-like with more words, and I just added substitutions to see what it would look like. At entropy 75, here are five from Molis Hai: look had can's asing his, nativa "Hemmer,'" Charactiour roopiaties more folks and conful never succepth myriage; by! Let taughter, any mind shu goost out uponsibing of?" "Your," rem And five passphrases with 3 substitutions: ov&rload grXas<proof investing Men,ts peartrees Yamages automata adVredGstudy/ng chloroformed exh>linYFassessable gGla rumbOs draughtBmanship It is hard to determine which is easiest to remember, however. We should perform tests; maybe ask a large number of users to remember one passphrase, and send them a mail three days later asking them to input it. If that sounds like fun to you, I can help. [0]: https://github.com/espadrine/passphrase https://github.com/espadrine/passphrase
- bumbledraven 12y agoThe http://www.diceware.com http://www.diceware.com passphrase-generation algorithm is more straightforward to implement and analyze. It uses only whole words, so the result is easier to memorize.
- coyotebush 12y agoDiceware is great, though the paper fairly points out that algorithms like that and https://xkcd.com/936/ https://xkcd.com/936/ necessarily often choose very uncommon words. I suppose the Markov model could just as well use whole words (as done in all sorts of other scenarios), at the expense of substantially longer passwords.
- jbclements 12y agoI took a look at whole words. Things got a lot longer. Like, twice as long. Here, let me generate some. These are 56-bits each: '(#" that looked up to Darnay: you not?\" \"Very willingly,\" pointing" #" that it was confirmed. \"He may not--thou wouldst rescue this is touched the child" #" that direction through his, and said Stryver, \"that, there! I" #" that criminal in Lombard-street, out at neighbouring streets that she" #" that he,\" said Darnay. Released yesterday. I.\" It was set, and--in a highly" #" that although Sydney Carton.\" This must have to finish that way" #" that Madame Defarge's wine-rotted fragments of his. \"Carton, idlest and its accessories" #" that every rapid movement, and, as the executioner showed a high grass and") Really, I would not not like to type in "that every movement, and, as the executioner showed a high grass and" every time I opened my laptop.
- deleted 12y ago[deleted]
- nullc 12y agoYou can use a 10-bit "common english" wordlist that has no exceptionally rare words and code your 56 bit values with just 6 words. It's not clear that the markov property helps memorability much when you're still left with lots of structurally incorrect punctuation.
- jbclements 12y agotry it out! I found this style of password (horse-battery-staple) to be much longer and less memorable. The proof, of course, is in the pudding. The next step (for me) is to conduct a reasonable experiment to discover whether or not these passwords are memorable.
- exratione 12y agoHere is one of my attempts at a memorable passphrase generator, using Moby Dick as source material. It is interesting to see just how distinctive some works and authors are when you are doing this sort of thing: https://github.com/exratione/four-word-phrase https://github.com/exratione/four-word-phrase clenched bakers detestable evincing keenly eastern expertness presto topsails existence self-created fittings delusion brushed lockers discipline seaman vintages cross-bones uncouth furnished vanity copied invited sea-captains cross-running engendered disastrous freshet willingly lead-lined asserted remarking repentance insert compendious vice-bench equally imminent quadrupeds
- eridius 12y agoVery cute. But all of the presented passwords I got had lots of punctuation strewn about them (most commonly the " character), and the "words" were extreme nonsense. For example, I just generated a new set and I'm getting passphrases like firs." Neven," drifty-T and is!" Mr. Look fore," oble) Perhaps the best password to date is still complete gobbledygook: lon tunittory lippile This has the benefit of at least being pronounceable, but it bears no resemblance to actual words. All that said, I wonder how it would do with different source material, or source material with all punctuation deleted.
- jbclements 12y agoThings will definitely get a bit longer if you make the source more uniform. I sympathize with you on the quotation marks, though; I think it might be nice to toss just those. Lemme try that.
- jbclements 12y agoI tried it, and ... eliminating the double-quotes looks like a win. Average password lengths in the order-2 model don't increase measurably; it rounds to 20.0 chars for both models. I've now deployed this. Um ... I mean... what quotations? I don't see any quotation marks! (Many thanks.)
- eridius 12y agoIt definitely looks better. I'm curious what the results would be if you eliminated all punctuation, but removing the quotes alone is a marked improvement.
- nullc 12y agoThe "secure unless" list needs to include: * Author of page is malicious. * Operator of server is malicious. * Anyone with access to the network between you and the server is malicious. (no HTTPS) * Google or anyone who has compromised their infrastructure is malicious (has embedded google js on the page). * Likewise for 'bootstrapcdn', 'jquery.com', or cloudflare. OTOH, it uses window.crypto and doesn't silently fall back to insecure randomness like 95% of JS crypto that I've looked at... :)
- jbclements 12y agoUm... certificate pinning? Fortunately, my last caveat covers a bunch of these. Also, I think you(I) forgot: * You are in fact hallucinating at this very moment.
- nullc 12y ago:) Cert pinning does nothing when the page is plain http as it is here. (and HTTPS's helpfulness is limited without HSTS; were it HTTPS I'd have a couple of other assumptions like none of the hundreds of CAs are malicious, and "no attacker is able to MITM between the site and any CA that does domain-validation.) I didn't run off that list to criticize the site. The last bullet is indeed good. :)
- ryan-c 12y agoIs it possible to get the source bits back from the password?
- jbclements 12y agoYes, absolutely. 100% invertible.
- deleted 12y ago[deleted]
- dminor 12y agoI did something similar using Markov chains and a dictionary - you can see it at http://password.supply http://password.supply
- jbclements 12y agocool... can you guarantee that every password is generated with equal probability?
- dminor 12y agoI guarantee nothing, other than they look somewhat like English words :)
- 616c 12y agoThis is very cool. And now even more Racket on HN's front page. I will look at the code later. For those interested, variable-order Markov chaining is different form traditional Markov models. I studied the latter in computational linguistics courses; they are a right of passage in stastical models for CL/NLP work. I was wondering how it was a good idea to model passwords, even pseudorandomly with Markov chains, but VO Markov chains are somewhat different. For the uninitiated, like myself. https://en.wikipedia.org/wiki/Variable-order_Markov_model https://en.wikipedia.org/wiki/Variable-order_Markov_model
- jbclements 12y agoVariable-order markov models do sound interesting; this tool isn't using them, though....
- 616c 12y agoIs that not what order-3 Markov model means? I mean, I will not lie. I skimmed the article and searched DDG/Wikipedia for "order 3 markov" and that article is what I got. Granted, my statistical comp ling course was ages ago. Perhaps it is time to crack open that book, but neither the article or Wikipedia article cleared up for me if order 3 or variable order are different or what is implemented.
- chm 12y agoI think it should read "row" not "column":)
- VanillaCafe 12y agoOkay, but for 56-bits, you can also just have 3 quadruples of a-z, such as "envh zmds vrdq" (dropping the spaces for the actual password). I'm not sure random, punctuated text is so much easier to commit to memory.
- tempestn 12y agoThis looks like a fun project, although whenever something like this comes up I have to wonder if providing ways to make passwords more memorable is in fact a beneficial activity, since ideally people won't be remembering more than one password anyway (the master password of their manager). Of course there are exceptions, like login/unlock codes for PC and phone, but often in those exception cases a long string of characters isn't practical anyway. The cases where it is would normally be very few. That said, I don't think I really believe my own argument. Anything that gets people thinking about better ways to handle their passwords is probably a good thing. Once the ball is rolling, they might even land on a password manager. Perhaps even through this comment!
- ketralnis 12y agoI use a password manager, but I still use xkcd936 password for things that I have to type in often. Like the password to unlock my phone or computer, or passwords to mobile banking apps that I check often. Copy-pasting out of the password manager on a phone is a multi-step process, most of which is all of iOS's new animation delays. There's a world for both of these things, and xkcd936 passwords are very easy to generate: $ cat $(which xkcd936) #!/bin/sh cat /usr/share/dict/words | unsort | head -n 40 | xargs -n4 echo
- tempestn 12y agoMm, ya, those make sense. On Android, Lastpass is getting better at autofilling into native apps, but it's still not foolproof. Getting better though!
- avinashv 12y agoI killed those animations in settings the day I installed iOS 7. You should too!
- ketralnis 12y agoHow? I've only found the option to reduce motion sickness which changes the zooms and slides to fadeouts that take the same point of time
- SixSigma 12y agoI would still rather gamble with using : It was the best of times. Or Please sir can I have some more?
- ternaryoperator 12y agoCould someone explain how these passwords are secure? Given that some phrases are all lower-case letters with a single punctuation character, aren't they vulnerable to brute-force attacks? My understanding has been that stronger passwords use a wide range of character options: lower-case, upper-case, punctuation, special chars. So, #RedBum72! would be more secure than abigredbum despite each having 11 chars. Is it simply the length of these passwords that makes them secure?
- aaronsnoswell 12y agoYes - the length of a password is approximately proportional to the time taken to perform a naive brute force attack against it. Mixing different characters into passwords is a technique to limit the effectiveness of dictionary attacks against that password. Both techniques should ideally be combined for really strong passwords, but length alone is a good place to start.
- dietrichepp 12y ago> the length of a password is approximately proportional to the time taken to perform a naive brute force attack against it This is incorrect. The time (or resources, in general) required to perform a brute force attack grows exponentially as the length of a password increases. For example, let's say you use lower-case letters only, but choose them uniformly at random. If it takes an attacker one day to crack your password now, then adding a single letter means that it takes the same attacker 26 days, and adding 4 letters makes it so the same attack would take over 1,000 years.
- dietrichepp 12y agoI think you have a misunderstanding of the mathematics behind password security. If I choose lower-case letters only, then the password can have about 4.7 bits of entropy per letter, so a 16-character password would have about 75 bits, maximum. If I choose from the entire set of non-control ASCII characters, I get about 6.6 bits of entropy per letter, which means that I can get 78 bits of entropy with only 12 characters. The difficulty of a brute force attack is proportional to the number of possible passwords. So, you can make brute force attacks harder by using longer passwords, or you can use a wider range of characters. Strictly speaking, there is no need to do both, since either option gives you the exact same benefit. The technique demonstrated in the article is significantly more complex, because the letters in the passwords are not chosen uniformly, but they are chosen to form words that fit the surrounding context according to a certain kind of statistical model (a Markov chain). This makes it harder to calculate how many bits of entropy is in the password, but the bijection shown in the article makes it much easier—when you have a bijection, you are neither creating nor destroying entropy, so we know that passwords selected uniformly from the right column (such as "buill to Sound thand exp") have the exact same entropy as passwords selected uniformly from the left column (such as "0fe5c363d354d7").
- EGreg 12y agoThe default "choose a password" interface on our platform asks the user to set up a Pass Phrase (see http://blog.codinghorror.com/passwords-vs-pass-phrases/ http://blog.codinghorror.com/passwords-vs-pass-phrases/ ) and also scrapes Yahoo News for three consecutive words once in a while, to provide suggests to inspire people. For example "and the horse" or "the car was" are suggestions. Do you see any obvious flaws in that? After the fact it's hard to scrape ALL of Yahoo news.
- garrettr_ 12y agoBasing passphrases off of a (since you've just mentioned it on Hacker News) well-known public source is usually a bad idea. Why not just pick random words (using a CSPRNG like /dev/urandom) from a dictionary? This is the "Diceware" approach, which is recommended because it is simple to implement and has straightforward provable security guarantees.
- EGreg 12y agoWe do have a mode where the software generates random phrases like "the [noun] [verb] the [noun]" generating about a million possible combinations (100 x 100 x 100) But the space of three consecutive words in Yahoo News is even larger, and frankly, most passwords are chosen from a small space anyway. And finally, the examples are just meant to inspire, so people don't select "password" as their password.
- Vektorweg 12y agoHer watches, why him, fog A nice description why crypto.