PassGAN: A Deep Learning Approach for Password Guessing

Pagan is the name for a password generator.

I'm assuming by iterate you mean "generate outputs of a GAN which preserve some order that you can iterate through."

The answer is yes, but not in the way that one might think. Despite the fact that we seed the GAN with input noise, there is no guarantee that the GAN makes use of this at all. This is a theme with GANs: we often want to imbue them with prior knowledge that we think is important, but is easily ignored by the GAN. In this case, we want to generate samples from p(x|z), where x is in the space of our data (often images, in this case passwords), but provided it gets good results according the the loss function, your GAN may learn p(x|z)=p(x). This is fine if you don't care about enforcing some relationship between input and generated samples, but here we do.

One solution is to use InfoGAN (https://arxiv.org/abs/1606.03657), which adds a term to the loss function that the mutual information between a latent code and the generator output must be high. Your latent code might be drawn from a uniform distribution on [-1,1], and the generator output will be conditioned on this code. This being continuous, it's questionable what "iterate" might mean. On a computer, maybe you iterate through every possible float (as someone mentioned), but if you want to generate N different samples, you could also discretize this distribution to N values on the given interval, each with probability 1/N and sample from this PMF.

The generator is passed random noise from a distribution, so iterating through all the samples is the same as just sampling from that distribution a ton.

If your noise is uniform on [0, 1], then, sure, you could just iterate through every possible float, I guess. Though in practice you're talking an astronomical number of possible combinations.

Another option is to take two samples from the distribution and interpolate in-between them, which might give you an idea of the distribution of samples. Maybe, it depends on the GAN and data.

A GAN effectively takes a seed to generate output, normally people provide random inputs, but you could iterate on the seed. Not sure how good your output would be though.

I've used email addresses as source dictionaries. Turns out people see both choosing an email address and choosing a password as a kind of personality test, meaning there's a lot of overlap.

Chargrams from the email address would be an excellent feature.

I don't think you can do better than brute force search for cryptographic randomness, but it would be interesting to see if this does well on personal heuristics people use. Eg the XKCD approach.

Target someone. Wget their LinkedIn and their friend's LinkedIns. Wget the wikipedia pages for their hobbies and skills on said linkedIn pages.

Remove duplicate words and code.

Repeat with other sources of information (FB profiles, etc, etc).

Remove duplicate words.

Add it to your dictionary and then use that to see the generated dictionary.

Password cracking is always a compromise between speed and thoroughness.

Better moral is that humans are bad at generating randomness, use CSPRNG.

> correct horse battery staple

Assuming a vocabulary of 16K words, it's 15 bits per word for a total of 60 bits for the four word password. Letters plus punctuation will give you about 60 symbols or 6 bits per position. At 60 bits, the four word password is as good as the 10 characters you generated by smashing your elbows on the keyboard and, hopefully, easier to remember.

> Also reduces the time it takes to crack because the algorithm can simply dump a huge amount of possible answers?

Yes. Knowing the password rules limits the space that'd need to be bruteforced.

Limiting character is wrong because the space is totally limited. Plenty of "important" websites do that and I go sigh. I use different password for different types of services for that reason.

If we don't limit number of characters (but seriously I'd say on average password lengh would be 8-10; I go a lot beyond that). In practice forcing to have combinations of various character sets increase search space, but in practice I bet most users are likely to use @ for a, l for 1, or captialize either first initial, or first initial of every word.

Or worse, just append, preappend, or modify one or two characters because some other websites decided to have a more unique password policy, and users hate to reinvent a whole new password. Then imagine one website got hacked, the next is easy..

So essentially if we can gather sufficent data about a target, then the brute force search space is now hammered and reduced.

In any case, I am a big believer of no restriction, because of what I said above. The behavior of choosing password is not too random so we can predict and infer from whatever we know. Password and passphrase are the same shit because "ILoveTacoAndBurgersWhatever1984" is a legitmate password. Good luck guessing that because I am not a huge fan of Taco, and I bet you no machine brute force this in any reasonable time.

The whole password vs passphrase is a campaign to get rid of the sophicated password policy, so people came up with a new name.

In the end, I believe having a 2-auth and allowing users to freely choose whatever passwors they want is better than forcing them to choose whatever we think is best. Education is the key, both on social engineering and on choosing passwords. We as software technologists have the responsibility to make dangerous / "i am not sure if that's a good thing to do" warning more obvious.

Of course I am aware there are other alternative proposals to replace pwd but for now password is not going anywhere soon.

I'm not an expert in this area but my general perception is that all those restrictions make system overall much less secure. This is simply because average users can't remember lengthy passwords and so they tend to use same password on many website or write it down somewhere insecurely. A much better approach may be just to have user use two or three words as password.

First question: If the size of the (known) dictionary is n words and the number of words in your passphrase is k, and if the choice of each word is made by a random number generator, then the entropy of the passphrase is k x log2(n). So for example a passphrase with 8 words from a dictionary containing 200,000 words has entropy 8 x log2(200000)=140.9 bits, which is very secure.

If you don't choose the words randomly, the security may decrease drastically, but I doubt it will be less for a passphrase of 8 words than a non-randomly chosen short 'password'. Generally, XKCD's advice is sound, as long as people are aware that dedicated attackers can and probably will guess common phrases and book codes (passages from a book).

Second question: Yes, any restrictions on password length or allowed characters drastically reduces password security. For example, 8 characters of random Latin1 is too short, it only has an entropy of 56.87 bit. Things get way worse once passords are not randomly generated. A user-chosen password limited to 8 characters of Latin1 is ridiculous and anyone can crack it.

Generally speaking, humanly generated passphrases are no longer secure.

The xkcd comic doesn't claim that "correct horse battery staple" is a completely secure password, it just shows that it's so much better than weird passwords that people tend to generate by themselves, like "k@tApU1t2143", and also how much easier it is to remember. So the suggestion is, if you're gonna use a password that you're going to remember, it's better to use a long one than a "complex" one. But yes, if the attacker knows that you're using English words for your passwords, the English language has about 170.000 words according to Oxford English Dict, and if you consider 1/10 of them to be known enough to be used in a password by you, if you use 4 words you have about 80.000.000.000.000.000 combinations, or about a day of brute-forcing with JTR. (Someone correct me if I'm wrong).

Five words makes it a lot more secure, or using more obscure words. Coming up with a "random" method of choosing some 5-6 words out of a dictionary, using dice or coin flips, can go a long way to make your "phrase" password more secure against these kinds of attacks.

Of course, the best approach is to use such a password, and use a password manager.

As for your second question, I believe it doesn't reduce the time it takes to guess some user's password. The restriction to include capital letters or special characters forces users to introduce more entropy in their password, and thus prevents a lot of common password usage. An attacker knowing that the site's password must be at least 8 characters long is not that helpful. Checking all the 1-7 character long passwords is trivial compared to checking all the 8-10 character long passwords. So it is helpful, since it prevents a lot of users from using simple, guessable passwords. In short, the restrictions introduce more complexity than they subtract for most users.

Edit: Having read the other replies, yes, it does technically reduce the search space, and it might be a bad thing (due to users adding simple common symbols, which are again easily guessed). So it probably isn't good practice.

Its bit annoying how much misinformation there is on the web about diceware-style passwords (that correct horse batter staple is an example of). There are so many people (luckily not in this thread!) saying that because it is using dictionary words it is vulnerable to dictionary attacks. That is utterly false. The numbers simply do not lie:

    Set             Number of symbols    Bits per symbol    80 bit string length
    20k word dict               20000              14.29                       6
    Printable ASCII                95               6.57                      13
    [A-Za-z0-9]                    62               5.95                      14
    [a-zA-Z]                       52               5.70                      15
    [a-z0-9]                       36               5.17                      16
    [a-z]                          26               4.70                      18
    [0-9]                          10               3.32                      25
    ????                            n            log2(n)        ceil(80/log2(n))

Bigger question is what is reasonable security level for common use. 80 bit security (like in that table) is probably good enough for most people, 40ish bits like in the XKCD is on the low side. Of course those bits should be always be generated in a secure manner, e.g. CSPRNG, no matter how they are then transformed into a password/phrse/whatever.

edit: did some further quick math: From random internet source I got that single Nvidia 1080 GPU can do about 25 GH/s for MD5 (and much less for something sane). With that 80 bit password takes about 60000 GPU years to crack, 64 bits 1 GPU year, 40 bits less than a single GPU minute.

There are 6 mentions of the word Markov in the paper, not counting citations.

Has anyone proven that the recent spate of "apply neural networks to a text corpus" projects produce output any "better" than a markov chain with the same inputs would?

You could say that about practically anything.

what's the difference between "There is a similar technique using markov chain. The author don't seem to be aware." AND "There is a similar technique using markov chain! :) "

Could you link that?

I don't think so: as they're generated randomly, there's no structure you can "deep learn". (You might recover password rules that are imposed by the password manager, such as at least one number, one capital letter, etc. But that doesn't give you that much).

The point is that humans are quite bad at generating "random" strings, and you can extract regularities there.