How can I programmatically create/detect keyboard runs in passwords?

Question

I'm looking for a method to create a list of or detect keyboard runs in a password.

I can bound my problem with password criteria such as length and number of special characters required.

An example simple key run could be "6yhn^YHN" or "zse4ZSE$".

More complicated key runs could be in different shapes, like a 'V' or 'X' (e.g. "mko0mju7MKO)MJU&")

The initial idea for this was for doing statistical analysis on large password dumps and seeing the prevalence of key run only passwords, but I think it could have positive applications in password strength enforcement tools.

Answer 1

You're not going to do this with regex.

You're going to need to create a graph data structure modeling the keyboard, with each key being a node and the edges being assigned a direction (so node G would have an edge with direction Right and destination H). You could also have an edge going from a key to it's shifted version (or from shifted to unshifted). You can then test for a run in a password by checking that it follows the graph in a consistent direction for N characters.

There's a very large number of possible runs on a keyboard, so I'm not sure that a password that is composed of runs is less secure than other possible passwords...

Answer 2

I don't see how this is related to regex - do you think you can do this with regular expressions? I can't see how.

I think it's a graphing problem, no? Build a graph with all the edges between keys and their neighbors, and then traverse the input and see if it represents a valid traversal of the graph. Your "more complicated runs" are essentially just backtracking - if the next key in the input is not an edge in your graph, go back to the beginning (or maybe backtrack one by one, if you want to cover "T" or other variations?) and see if you can keep traversing...

It's a pretty vague answer for a pretty vague question, wouldn't you say?