Password Generation Algorithms Using a Phonetically Memorable Password

Question

Background

While in the gym, I worked with my combination lock and realized what would be useful to me as a programmer. To do this, my combination consists of three separate sets of numbers that either sound the same or have some other relationship that makes them easier to remember. For example, 5-15-25, 7-17-2, 6-24-5. These examples are easy to remember.

Question

How do I implement something similar for passwords? Yes, they should be hard to crack, but they should also be easy for the end user to remember. Combination locks do this with a combination of numbers that have similar sounds, and with numbers that have similar properties (7-17-23: All Prime, 17 rolls immediately after language 7, and 23 are another simple one and (outside of this set) , "hard" to remember).

Criteria

• Password should be easy to remember. Dog!Wolf easy to remember, but as soon as an attacker knows that your site produces this combination, it makes it infinitely easier to check.
• Words or letters should basically follow the same sounds (for the most part).
• At least 8 letters
• Do not use !@#$%^&*();'{}_+<>?,./ These punctuation marks, while suitable for "hard" passwords, do not have a "catchy" sound.

Resources

This question is an agnostic of the language, but if there is a specific implementation for C #, I would be happy to hear about it.

Update

Several users said that "this is bad password protection." Do not assume this is for a website. It may just be for me to make an application for myself that generates passwords in accordance with these rules. Here is an example.

The letters A - C - C - L - I - M - O - P "flow" and they turn out to be two regular words collected ( Acclimatize and Mop ). Further, when the user speaks these letters, or speaks them as a word, this word is for them. Easy to remember, but hard to crack (dictionary attack, obviously).

This question has two goals:

• Build passwords from letters similar to sound (using alliteration) or
• To build passwords that combine common words is similar to creating a third set of letters that is not in the dictionary.

Answer 1

You can watch:

• The password generation algorithm used by apg is explained in FIPS-181
• Koremutake

Answer 2

First of all, make sure the password is long. Consider using a "pass-phrase" instead of a single "pass-word". Violating phrases such as "Dogs and wolves hate each other." very difficult, but easy to remember.

Some sites may also give you advice that may be useful, such as Strong passwords: how to create and use them (associated with Password checker , which is a useful tool in itself).

In addition, instead of trying to create an easy-to-remember password, in some cases a much better alternative is to avoid remembering the password at all, using (and educating your users) a good password management utility (see What is your favorite password storage tool? ) - in this case, the only part is to create a hard password for hacking, which is easy (any sufficiently long random sentence will do).

Answer 3

You can use Markov chains to generate words that sound like English (or any other language you want), but they are not actual words.

The easy-to-remember question is really subjective, so I don’t think you can write an algorithm that is good for everyone.

And why use short passwords on websites / computer applications instead of passwords? They are easy to remember, but hard to crack.

Answer 4

I am surprised that no one has mentioned the Multics algorithm described in http://www.multicians.org/thvv/gpw.html , which is similar to the FIPS algorithm, but based on trigraphs and not digraphs. It produces output such as

 ahmouryleg thasylecta tronicatic terstabble 

I ported the code to python: http://pastebin.com/f6a10de7b

Answer 5

Many years later, I decided to use the first letter of the words in the keyword phrase. It’s impossible to hack, universal for length and limitations such as “you must have a number”, and it’s hard to make mistakes.

This works by creating a phrase. Useful crazy fun theme ! "Stack overflows by aliens landed without using rockets or wheels." Take the first letter, your password is "soalwurow"

You can type quickly and accurately , since you don’t remember the letter, you just say the sentence in your head.

I also like when words are alternated on the left and right side of the keyboard, this gives you a lower typing speed and a more pleasant rhythm. Note that in my example, your hands alternate left-right-left-left-right.

Answer 6

I used the following algorithm several times:

• Put all lowercase vowels (from az) in an array. Vowels
• Put all lower consonants (from az) into another consonant array
• Create a third array of Pairs of two letters so that you create all possible pairs of letters between vowels and consonants ("ab", "ba", "ac", etc.).
• Randomly select 3-5 items from pairs and connect them together as a Password string
• Randomly select true or false
  • If true , remove the last letter from the password
  • If false , do nothing
• Replace 2-4 randomly selected characters in Password with its uppercase equivalent
• Replace 2-4 randomly selected characters in Password with a randomly selected integer 0-9

Voilá - now you should have a password from 5 to 10 characters long, with alphanumeric upper and lower case characters. The presence of vowels and consonants in turn often makes them semisolvable and therefore easier to remember.

Answer 7

FWIW I really like the gossip of syllable words for a simple but essentially random password. Take Bongo, for example, as a random word. Change the syllables you get "Gobong". Change o for zeros at the top (or some other general replacement), and you have essentially a random sequence of characters with some track to help you remember it.

Now, how you programmatically select syllables - this is another question!

Answer 8

When you create a password for a user and send it by e-mail, the first thing you need to do when they first log in if they force them to change their password. Passwords created by the system do not have to be remembered, because they need to be needed only once.

It’s easy to remember, it’s difficult to guess passwords - this is a useful concept for your users, but not one that the system should apply in some way. Suppose you sent a password to your gmail user account and the user did not change the password after logging in. If the password for the gmail account is cracked, the password for your system is compromised.

Thus, creating easy-to-remember passwords for your users does not help if they must immediately change the password. And if they do not change it immediately, you have other problems.

Answer 9

I prefer to give users a “hard” password, requiring them to change it on first use and give them instructions on how to create a nice long phrase. I would also associate this with reasonable requirements for password complexity (8+ characters, a combination of upper and lower case, punctuation or numbers). My rationale for this is that people are more likely to remember what they choose, and less likely to write it somewhere if they can remember it.

Answer 10

The spin on the idea of ​​a "phrase phrase" is to take the phrase and write the first letters of each word in the phrase. For example.

 "A specter is haunting Europe - the specter of communism." 

becomes

 asihe-tsoc 

If the phrase has an exact point, such as!,? etc., can also put her there. The same goes for numbers or simply replaces letters or appends corresponding numbers to the end. For example. Karl Marx (who said this quote) died in 1883, so why not "asihe-tsoc83"?

I am sure that a brute force attack can use the statistical properties of such a password, but it is still an order of magnitude more secure than a dictionary attack.

---

Another great approach is to just make funny words, for example. 'Barangamop. After using it several times, you will pass it into memory, but it is difficult for brute force. Add some numbers or punctuation for added security, for example. '386Barangamop!

Answer 11

Here, part 2 of your idea is prototyped into a shell script. It will take 4, 5 and 6 letter words (approximately 50,000) from the Unix dictionary file on your computer and combine these words with the first character.

 #! /bin/bash RANDOM=$$ WORDSFILE=./simple-words DICTFILE=/usr/share/dict/words grep -ve '[^az]' ${DICTFILE} | grep -Ee '^.{4,6}$' > ${WORDSFILE} N_WORDS=$(wc -l < ${WORDSFILE}) for i in $(seq 1 20); do password="" while [ ! "${#password}" -ge 8 ] || grep -qe"^${password}$" ${DICTFILE}; do while [ -z "${password}" ]; do password="$(sed -ne "$(( (150 * $RANDOM) % $N_WORDS + 1))p" ${WORDSFILE})" builtfrom="${password}" done word="$(sort -R ${WORDSFILE} | grep -m 1 -e "^..*${password:0:1}")" builtfrom="${word} ${builtfrom}" password="${word%${password:0:1}*}${password}" done echo "${password} (${builtfrom})" done 

Like most password generators, I cheat by exposing them in twenties sets. This is often protected from the point of view of "security" (someone looks over his shoulder), but in fact it is easy to crack, so that the user just picks up the friendliest password.

I found 4-word words in the dictionary, still containing obscure words.

The best source of words would be a written document. I copied all the words on this page and pasted them into a text document, and then executed the following set of commands to get the actual English words.

 perl -pe 's/[^az]+/\n/gi' ./624425.txt | tr AZ az | sort -u > ./words ispell -l ./words | grep -Fvf - ./words > ./simple-words 

Then I used these 500 or so very simple words from this page to generate the following passwords with a shell script - the script in brackets shows the words that make up the password.

 backgroundied (background died) soundecrazy (sounding decided crazy) aboupper (about upper) commusers (community users) reprogrammer (replacing programmer) alliterafter (alliteration after) actualetter (actual letter) statisticrhythm (statistical crazy rhythm) othereplacing (other replacing) enjumbling (enjoying jumbling) feedbacombination (feedback combination) rinstead (right instead) unbelievabut (unbelievably but) createdogso (created dogs so) apphours (applications phrase hours) chainsoftwas (chains software was) compupper (computer upper) withomepage (without homepage) welcomputer (welcome computer) choosome (choose some) 

Some of the results there are winners.

The prototype shows that this is probably possible, but the intelligence you need for information about alliteration or a syllable requires a better data source than just words. You need pronunciation information. In addition, I showed that you probably want the database of simple simple words to choose, not all words, to better meet your password requirements.

Creating a single password for the first time and every time - something you need for the Internet - will lead to a better data source and more sophistication. Using a better programming language than Bash with text files, and using a database can make it work instantly. Using the database system, you can use the SOUNDEX algorithm or some of them.

A sophisticated idea. Good luck.

Answer 12

I am completely with rjh. The advantage of using the initial letters of a passphrase is that it looks random, which makes you wonder if you don’t know the phrase behind it, in case Eve looks over her shoulder when entering her password.
OTOH, if she sees that you are typing about 8 characters, including “twice”, and then “o” and “r”, she may guess for the first time.
Forcing the use of at least one digit does not really help; you just know that it will be "pa55word" or "passw0rd".

Lyrics are an inexhaustible source of passwords.

 "But I should have known this right from the start" 

becomes "bishktrfts". 10 letters, even only lowercase letters give you 10 ^ 15 combinations, which is a lot, especially since there is no shortcut for breaking it. (At 1 million combinations per second, it takes 30 years to test all combinations 10 ^ 15.)
As an extra (in case Eva knows that you are a fan of the police), you can change, for example. 2nd and 3rd letters, or take the second letter of the third word. Endless possibilities.

Answer 13

Take a look at the gpw tool . The package is also available in the Debian / Ubuntu repositories.

Answer 14

System-generated passwords are a bad idea for anything other than internal service accounts or temporary resets (etc.).

You should always use your "passphrases" that are easy for you to remember, but it's almost impossible to guess or brute force. For example, the password for my old university account was.

Here to study again!

These are 20 characters using upper and lower case with punctuation. This is an incredibly strong password, and there is no software that could create a more secure one that is easier to remember for me.

Answer 15

One way to generate passwords that “sound like” is to use a chain of stamps. The n-degree mark chain is basically a large set of n-tuples that appear in your input enclosure, as well as their frequency. For example, an “aardwark” with a chain of marks of the 2nd degree will generate tuples (a, a, 1), (a, r, 2), (r, d, 1), (d, v, 1), (v, a, 1), (r, k, 1). If you wish, you can also include "virtual" tokens of the start word and end word.

To create a useful chain of stamps for your purposes, you will feed a lot of data in English - there are many available, including, for example, Project Gutenburg - to create a set of records, as described above. For the generation of words or sentences of a natural language, which, at least, mainly follow the rules of grammar or composition, a chain of marks of the third degree is usually sufficient.

Then, to generate a password, you select a random "source" tuple from the set, weighted by its frequency, and output the first letter. Then repeatedly select at random (again weighted by frequency) the "next" tuple, that is, one that starts with the same letters as your current one and has only one letter. Using the above example, suppose I start with (a, a, 1) and print 'a'. My only next choice is (a, r, 2), so I output another "a". Now I can choose either (r, d, 1) or (r, k, 1), so I choose one randomly depending on their frequency of occurrence. Suppose I select (r, k, 1) - I output 'r'. This process continues until you reach the end-of-word marker or decide to stop independently (since most chain strings form a cyclic graph, you cannot stop generating unless you apply a constraint on the artificial length).

At the level of words (for example, each element of a tuple is a word), this method is used by some “conversation bots” to create reasonably seemingly meaningless sentences. It is also used by spammers to try to evade spam filters. At the letter level, as described above, it can be used to generate meaningless words, in this case for passwords.

One drawback: if your input enclosure contains nothing but letters, and your output phrases, so they won’t convey most of the “secure” password requirements. You might want to apply some post-processing to substitute some characters for numbers or characters.

Answer 16

edit: After the answer, I realized that this is in no way phonetically memorable. In any case, leaving the answer, I find it interesting. / Edit

Old thread, I know ... but it's worth it.

1) I would probably create the largest dictionary that you can use. Place them in buckets for part of speech.

2) Then create a grammar that can create several types of sentences. The "type" of a sentence is determined by permutations of the parts of speech.

3) Randomly (or as close as possible to random) select the type of offer. A placeholder pattern is returned for parts of speech (nvn will be a noun-noun-noun)

3) Choose the words randomly in each part of the speech bucket in order to replace the placeholders. Fill them out. (The example above may become something like a car bike.)

4) randomly scan each character, deciding whether you want to replace it with either a similar sounding character (or a set of characters) or similar to it. This is the most difficult step in this problem.

5) the resulting password will be similar to kaR @tebyCICle

6) laugh at humorous results like the ones above that look like a karate bike

Answer 17

I really love to see someone implement passwords with control characters such as " <Ctrl>+N " or even combined characters such as " A+C " at the same time. Converting this to some binary equivalent, IMHO, makes password requirements much easier to remember, faster to type, and harder to crack (MANY other combinations to check).