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.

Vitiligo

What language are you trying to do this in? – Benevolence

@citizen-conn I'm language agnostic at this point. I'm willing to work with whichever provides the best way to do it. – Vitiligo

Note that the easiest way of enforcing strong password is to generate them randomly and not giving the user any option to change it themselves. If you restrict the space by rules, you're making passwords weaker, actually. – Tricotine

What keyboard are you trying to do this with? (Different human languages have different layouts. Really.) – Putrescible

@Donal For now we'll stick with the standard QWERTY keyboard. Point taken though. – Vitiligo

@Tricotine My initial thought was for analysis of password dumps, but I see your point about restricting the space. – Vitiligo

Answer 1

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?

Scarletscarlett

Thanks, I think this puts me on the right track. I'm not sure what I was thinking with regex, I've changed the tags to reflect that. – Vitiligo

Answer 2

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...

Netti

There's a lot fewer n-path nodes in the keyboard graph than there are n-combinations of nodes, though. – Royden

Thanks for the response. I'm going to go with this. Looks like Python-Graphs has above and beyond the functionality I need to quickly accomplish this. I gave e.dan the checkmark since he clocked in just ahead of you. – Vitiligo

Keep in mind, you have to do this for every possible keyboard layout. And they are patterns such as "QPWOEIRUTZ" that you don't detect this way. – Donny

Answer 3

This actually probably wouldn't be that hard. Store a collection of objects that represent characters, with properties on them like TL, BR, T, BL (Top Left, Bottom Right, Top, Bottom Left) so for example:

a = RunKey.get("A");



public class RunKey{

    public static Key get(Character char){
        switch(char){
            case A,a: return new A();
            break;
            // one for every letter
        }
     }
 }

 private class A extends RunKey implements IRunKey{

     public IRunKey BR(){
         return new Z();
     }

     public IRunKey TR(){
         return new W();
     }

     public IRunKey T(){
         return new Q();
     }

     public Direction getDirection(Character char){
         tempRunKey = Runkey.get(char);
         if (tempRunKey.T.toString == "char"){
             return T;
         }
     }
 }

I started getting crazy creating a "Direction" interface so its a little more complicated than at first but you only have so many complications and relatively simple objects, so if you kept it light then it would probably remain pretty fast.

I feel like a dynamic language might be the best for something like this...

And yes, as other answers note, regex would not work.

Benevolence