Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

As a programmer and language enthusiast I've been very interested in Markov chains for some time. Considering the influence of natural language on password and passphrase selection (by humans of course) I would like to know the state of the art in applying Markov Chains and Hidden Markov Models to the task of guessing passwords.

Are there some good papers or articles on this topic I should read?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

Here is a good academic paper on the subject:

Advances in password cracking by Simon Marechal: http://www.springerlink.com/content/y24724w25118n884/

I don't have the full article here atm, but if I recall correctly, the experimental results are based on leaked real-use passwords.

You will of course not be able to find passwords that does not contain a sequence previously trained into the markov chain.

When you use a markov chain to perform bruteforce attacks, you are effectively dynamically reducing the charset used.

share|improve this answer

Papers. In addition to @Dogeatcat world's excellent answer, here are some more papers:

Matt Weir, Sudhir Aggarwal, Breno de Medeiros, Bill Glodek, Password Cracking Using Probabilistic Context-Free Grammars, IEEE Security & Privacy 2009.

Arvind Narayanan, Vitaly Shmatikov, Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff, CCS 2005.

Matteo Dell’Amico, Pietro Michiardi, Yves Roudier, Password Strength: An Empirical Analysis, Infocom 2010. (Thanks to @Martin Carpenter for this one.)

Manjesh Kumar Hanawal and Rajesh Sundaresan, Randomised attacks on passwords, Technical report TR-PME-2010-11, DRDO-IISc, 2010.

C. Davies and R. Ganesan, Bapasswd: A new proactive password checker, NCSC 1993.

I'd start with the paper @Dogeatcatworld mentions, but then read the ones I cited above.

Tools. I believe John the Ripper implements a Markov-model based mode. See also MiddleChild.

Tips. Here are some tips to help you find research papers, in the future. I'd start by going to Google Scholar, Microsoft Academic Search, and Citeseer. Enter in some search terms and see if you can find any papers that look relevant (when you see some candidates, reading the abstract can often tell you if it will be useful to you). When you find some papers that are on-topic or at least nearby, read the related work section of those papers to find older papers that might also be relevant. Also, when you find papers that are relevant, use these web services to list other papers that cite them; sometimes that can help you find newer papers that might be relevant. Hopefully this will help you do a literature search in the future!

share|improve this answer
3  
+1 for classic "Fast dictionary attacks...". Also good "Password strength: an empirical analysis" (Dell'Amico et al), results for k>2 interesting eurecom.fr/~michiard/downloads/infocom10.pdf. If you came here via recent xkcd strip then check out "Human selection of mnemonic phrase-based passwords" (Kuo et al) cups.cs.cmu.edu/soups/2006/proceedings/p67_kuo.pdf –  Martin Carpenter Aug 15 '11 at 21:03
    
Ahh, yes, that's a good one, too. Thanks, @Martin. I added it to the list. –  D.W. Aug 16 '11 at 2:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.