Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Keys beside keys on keyboards

by Smaug (Pilgrim)
on Nov 06, 2006 at 06:11 UTC ( [id://582382] : perlquestion . print w/replies, xml ) Need Help??

Smaug has asked for the wisdom of the Perl Monks concerning the following question:

Hello all

In a resent conversation about passwords and their strength a friend of mine told me how their passwords can not contain three sequential characters on a keyboard. At first I thought this was just another case of security gone mad. (The more you restrict users the easier attacks become - in this case you can immediately eliminate surrounding keys if you know one - but that's another debate)
However, I've become increasingly intrigued as to how this is done. I've tried searching for modules or keyboard maps, but still can't work out how it's done.
To make things worse, the app in question is web based and could be accessed from anywhere in the world and I'm fairly sure we aren't all using QWERTY US keyboards....
In short, please help me with this conceptually; How do I tell if three key pressed in sequence are next to each other on different keyboards?

Thanks a million,
Smaug.

Update:
Hi all,
Thanks for the insight. To be honest I have no idea if their method is 100% accurate, I just assumed it would be, and as for using cell phones, well I don't think they have ever thought about it!!
As for diagonal sequences, I would assume they check those too, but that makes it far more complex.
Thanks all for you explanations on this question. It seems that however this is done it requires you to know the keyboard layout as the starting point.
Is there any way to detect a users input locale using a CGI script? Perhaps that is where they start.
Thanks again!!

Replies are listed 'Best First'.
Re: Keys beside keys on keyboards
by TedPride (Priest) on Nov 06, 2006 at 06:41 UTC
    An interesting problem, even just for English keyboards. The good news is that there's somewhat less than 35,000 possible 3-letter sequences, so the easiest method might just be to generate a hash of those sequences and test every 3-letter sequence in the input string, preferably with a routine that stays up permanently so you don't have to regenerate the hash every time someone enters a new password.

    Of course, the interesting part is writing a routine to generate the sequences for you. The following perhaps isn't the cleanest piece of code in the world, but it works as proof of concept:

    use strict; use warnings; print find('mskrtgdiwpa'), "\n"; print find('mwslkdftghm'), "\n"; sub find { my $s = $_[0]; my $key = init(); for (0..(length($s)-2)) { return substr($s, $_, 3) if exists $key->{substr($s, $_, 3)}; } } BEGIN { my (@keys, $rows, $cols, %seq, $run); @keys = ('1 2 3 4 5 6 7 8 9 0', 'q w e r t y u i o p', 'a s d f g h j k l ;', 'z x c v b n m , . /'); $_ = [split / /, $_] for @keys; $rows = $#keys; $cols = $#{$keys[0]}; sub init { if (!$run) { my ($x, $y); for $y (0..$rows) { for $x (0..$cols) { spider($x, $y, 3, ''); } } $run = 1; } return \%seq; } sub spider { my ($x, $y, $depth, $s) = @_; $s .= $keys[$y][$x]; if (!--$depth) { $seq{$s} = (); return; } spider($x, $y-1, $depth, $s) if $y > 0; spider($x+1, $y-1, $depth, $s) if $y > 0 && $x < $cols; spider($x-1, $y, $depth, $s) if $x > 0; spider($x, $y, $depth, $s); spider($x+1, $y, $depth, $s) if $x < $cols; spider($x-1, $y+1, $depth, $s) if $y < $rows && $x > 0; spider($x, $y+1, $depth, $s) if $y < $rows; } }
    As it turns out, I miscalculated. There are probably less than 1500 sequences.
Re: Keys beside keys on keyboards
by shmem (Chancellor) on Nov 06, 2006 at 10:01 UTC
    They might deduce the keyboard from Client IP / Accept-Language-Header and such and correlate that with the default keyboard layout of the respective country the request comes from. Of course with that approach there might be false positives, e.g. somebody in a qwertz country using a querty keyboard. Is their method 100% accurate?

    Here's how I'd do it:

    # keyboard sequence (qwertz), for request from germany my $k = <<EOH; 1234567890ß' !"§$%&/()=?` qwertzuiopü+ asdfghjklöä# <yxcvbnm,.- >YXCVBNM;:_ EOH my @k = split/\n/,$k; # update: strings for diagonal mapping, e.g 1qa 2ws 3ed # the other diagonal is left as an exercise to the reader push @k, map { my $i=$_ ;join('',map{substr($k[$_],$_>3? $i+1:$i,1)} 0 +,2..4) } 0..11; push @k, map { my $i=$_ ;join('',map{substr($k[$_],$_>3? $i+1:$i,1)} 1 +..3,5) } 0..11; my @matches; chop (my $seq = <STDIN>); for my $i(0..length($seq) - 3) { my $t = substr($seq,$i,3); push @matches, /$t/ig for @k; } print "matches: @matches\n"; __END__ djuriops>yxcvatgb5 matches: iop >YX yxc YXC xcv XCV tgb tgB

    --shmem

    update: added diagonal match

    _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                  /\_¯/(q    /
    ----------------------------  \__(m.====·.(_("always off the crowd"))."·
    ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}
Re: Keys beside keys on keyboards
by Anonymous Monk on Nov 06, 2006 at 10:45 UTC
    If you have a keyboard where "asd" is next to each other, would you consider "aSd" to be next to each other? Or "aS^D"?

    And what about "edc" on a standard US keyboard? IMO, it doesn't make sense to disallow three keys in a horizontal row, but allow them vertically.

    But then, what are you going to do on a keyboard that only has a few keys...? (An example of a keyboard that has only a few keys is a cell phone).

Re: Keys beside keys on keyboards
by wjw (Priest) on Nov 06, 2006 at 14:15 UTC
    Ok, going on 1 hour sleep in the last 36, so maybe I am to lagged to think, but my foggy mind wonders if one could write a java script(or similar) that captures the actual hex input from the keyboard port before it gets through the keyboard map. I would guess that if one could do that, then the the problem would be reduced to one 101 key grid in the program. Just a thought... Yes, those diagonal keys... and then the old sun/sparc keyboards.. Well anyway, for the diagonal keys maybe one could make an array for each row of keys. the diagonal keys would always be one row up/down and one index +/-. Your right, this is one of those little ideas that just kind of grabs you! I better get back to work... :-)

    ...the majority is always wrong, and always the last to know about it...

      Hi wjw,

      I had thought of that, and also wondered if perhaps the hex was sequential in which case it would be as easy as adding 1 or subtracting 1 to get the keys on either side. Granted the diagonal keys are still a problem.....

      Update:
      I went on to check my xmodmap file and found the following:

      keycode 54 = c C 0xbd 0xbc keycode 55 = v V 0xc9 0xc8 keycode 56 = b B 0xf9 0xf8 keycode 57 = n N 0xcb 0xca keycode 58 = m M 0xdf 0xde keycode 59 = comma less 0xab 0xa7 keycode 60 = period greater 0xa9 0xa6 keycode 61 = slash question 0xb1 0xa1
      The "keycode" is in the exact order of the keys on my keyboard and but the only other ordering I can see is the upper and lower cases being offset by 1.
        On my keyboard, the backquote/tilde key is next to the one/exclaimation mark key. The former has keycode 49, the latter keycode 10. On the other hand, keycode 51 is the backslash/pipe key, the key on the right end of the second row. Keycode 52 is the z key, which is the second key from the left on the fourth row.
Re: Keys beside keys on keyboards
by thezip (Vicar) on Nov 07, 2006 at 01:38 UTC
    You could create a static table of "neighbors" for each allowable password character. (I interpreted "sequential character" to mean any character that touches the current char in any direction):
    $neighbors = { a => { q => 1, w => 1, s => 1, z => 1, }, s => { a => 1, w => 1, e => 1, d => 1, x => 1, z => 1, }, etc. }

    This hash would be specific to the type of keyboard being used.

    You could then traverse, character-by-character, through the password to see if three successive finds occur in the neighbors hash for each letter traversed.

    #!/usr/bin/perl use strict; use warnings; my $neighbors = { a => { q => 1, w => 1, s => 1, z => 1, }, s => { a => 1, w => 1, e => 1, d => 1, x => 1, z => 1, }, }; my $password = "asasas"; my $counter = 1; my $lastchar = ""; for my $char (split(//, $password)) { print $char, "\n"; $counter++ if $neighbors->{$lastchar}->{$char}; $lastchar = $char; last if $counter == 3; } if ($counter == 3) { print "Invalid password"; # make them enter a new password... }
    Where do you want *them* to go today?

      Update

      I realized on my drive home tonight that I neglected to reset the counter to 1 if it didn't find a match.

      Where do you want *them* to go today?
Re: Keys beside keys on keyboards
by Anonymous Monk on Nov 07, 2006 at 09:26 UTC
    Here's a nice paradox to think about. Disallowing certain patterns in passwords make the set of possible passwords to choose from smaller. And the smaller the pool of passwords, the easier it is for an attacker.
Re: Keys beside keys on keyboards
by spatterson (Pilgrim) on Nov 07, 2006 at 16:04 UTC
    Your CGI script probably has access to $ENV{HTTP_ACCEPT_CHARSET} && $ENV{HTTP_ACCEPT_LANGUAGE}

    Checking for adjacent characters seems like a relatively trivial use for a hash of arrays or an array of arrays, once you know which keyboard map is being used & how that map is laid out.


    just another cpan module author