Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Removing similar characters

by rspishock (Monk)
on Sep 01, 2011 at 16:54 UTC ( #923666=perlquestion: print w/ replies, xml ) Need Help??
rspishock has asked for the wisdom of the Perl Monks concerning the following question:

Greetings Monks

I am currently working on yet another revision of a script I wrote which generates random passwords based off of user specified criteria.

While I haven't come across this yet, I am currently stuck while trying to add the ability to eliminate three or more duplicate characters from the generated password. By duplicate characters, I don't just mean duplicate letters  aaa, BBB, 111, or ### but I also mean similar types of characters. For example  CYQ, bte, 735, and ^@( would all be in violation of the password policy.

I'm assuming that I would want to use some form of a regex to perform this kind of check, but I'm not too familiar with them so I could be wrong. Can anyone offer some advice as to where I should be looking to add this function?

Thanks for the repeated help.

Comment on Removing similar characters
Select or Download Code
Re: Removing similar characters
by SuicideJunkie (Priest) on Sep 01, 2011 at 17:19 UTC

    To look for three of a set of things in a row, first specify the set: /[a-z]/ then specify that you want three of them: /[a-z]{3}/

      Is it possible to list multiple sets? For example:

      if ($level == 5) { /[a-z], [A-Z], [0-9](3)/ #generat new password }

Re: Removing similar characters
by Kc12349 (Monk) on Sep 01, 2011 at 17:24 UTC

    Regex will surely be your friend here. Do you want to remove from the string, replace them with new random chars, or throw out the password entirely and regenerate a new random string?

    I would use character classes for each set of things you want to be track duplicates for, with something like the below.

    my $password = 'a8f3%djk$'; # some random string if ($password =~ m/[[:alpha:]]{3,}|\d{3,}|[\^@\(]{3,}/) { # regenerate password }

    You could use a character class like [A-Za-z] instead of [[:alpha:]] if you know you will only see ascii character. You will likely have to add to the [\^@\(] character class any other symbols you want. The other option is to exclude anything you don't want to match in that class. Maybe [^0-9A-Za-z] is enough there.

      Thanks for the tip. I was guessing that using a regex was probably going to be one of the best ways to achieve this. Since I'm not too familiar with using regex, my question is can I direct the regex to the array which contains the characters? For example, since I want to be able to check 88 individual characters for duplicates.

      Below is a small portion of the script that I'm working on.

      my @chars6 = ('0'..'9', 'a'..'z', 'A'..'Z', '!','@', '#', '$', '%', '^', '&', '*', '(', ')', '<', '>', '?', '`', '+', '/', '[', '{', ']', '}', '|', '=', '_','~', ',', '.'); if ($level == 5) { m/@chars6/ #generate new password }

      Looks like I'm off to Amazon to get a book to start learning regex.

        A better bet is to generate a string from that array and insert it into the regex pattern. I did this below with the string $chars6_class. Note that I escaped many of the symbols which have special meaning in regex and perl, though I didn't really double check I got all the right ones.

        Then I use the back reference, \1, to look for two more occurrences of what I just found.

        my @chars6 = ('0'..'9', 'a'..'z', 'A'..'Z', '!','\@', '#', '\$', '\%','^', '&', '\*', '\(', '\)', '<', '>', '\?', '`', '\+', '\/', '\[', '\{', '\]','\}', '\|', '=','_', '~', ',', '\.'); my $chars6_class = '[' . join( '', @chars6) . ']'; if ($password=~ m/($chars6_class)\1{2}/) { # regenerate password }

        Further, I would take a look at the posix character classes to see if there is already a set of what you are looking for. My guess would be that you could just use the below regex instead of dealing with an array of characters.

        m/([[:alnum:]]|[[:punct:]])\1{2}/
Re: Removing similar characters
by Kc12349 (Monk) on Sep 01, 2011 at 18:18 UTC

    Below is some sample code using String::Random to generate random strings of a certain length. It then removes invalid duplicates and appends new random strings until the password passes without duplicates. This assumes you are only working with ascii.

    use String::Random; my $length = 15; my $Random = new String::Random; my $password = ''; while (length($password) < $length) { my $missing_length = $length - length($password); my $added_string = $Random->randpattern('.' x $missing_length); $password .= $added_string; $password =~ s/[A-Za-z]{3,}|\d{3,}|[^A-Za-z\d]{3,}//; }
Re: Removing similar characters
by ikegami (Pope) on Sep 01, 2011 at 18:34 UTC
    I wish password strength enforcers would reduce the number of crazy rules as the length of the password increases. http://xkcd.com/936/
Re: Removing similar characters
by CountZero (Bishop) on Sep 01, 2011 at 18:56 UTC
    All such rules make it easier to guess the passwords. One of our less enlightened IT security PHBs has actually made it into a rule that the passwords must be exactly 8 characters long, start with a [A-Z] and contain one \d. It is not entirely clear from his specs if we are allowed to have more than one \d. Oh yes, and no punctuation and such because that messes up with an application that remembers your passwords for you and enters them automatically.

    I tried to explain that such moronic rules have reduced the searchspace for possible keys to about one tenth of what it would be without his clever rules and moreover still makes the passwords vulnerable to simple dictionary attacks since 99% of the users now have an easy to remember 7 character word + digit as their password.

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

Re: Removing similar characters
by onelesd (Pilgrim) on Sep 01, 2011 at 18:57 UTC
    use String::Random ; my $generator = new String::Random ; my $invalid_pass_re = qr/(\d{3}|\w{3}|[[:punct:]]{3})/ ; my $pass ; do { $pass = $generator->randregex('.{15}') ; } while ($pass =~ $invalid_pass_re) ; print "$pass\n" ;

      This is a slightly simpler solution than my similar code sample above. It's a good solution for shorter password lengths, but will become significantly slower as password length increases because you throw out the entire string each time it is invalid.

        You are right, but at 15 characters it takes .02s on my hardware. I did notice that randomregex() will emit consecutive duplicates rather frequently - I didn't check to see if a new instance of String::Random in each iteration would reduce that at all (or enough to make a difference in execution time).

Re: Removing similar characters
by Anonymous Monk on Sep 01, 2011 at 19:27 UTC
    Perhaps you could define some string-sequence patterns that are known to conform to the password policy. Select a pattern at random and then generate a string based on it. For example, a pattern "cdvaaa" might mean: consonant, digit, vowel, alpha, alpha, alpha."

      That's a good idea. Here is a stab at it using String::Random. The sub generates a string of given length of 0,1,2 and then converts this to character codes that String::Random understands. The sub ensures that no three values in a row are the same.

      use String::Random; my $length = 10; my $Random = new String::Random; # add new pattern char for upper and lower case $Random->{'A'} = [ 'A'..'Z', 'a'..'z' ]; my $pattern = generate_pattern($length); my $password = $Random->randpattern($pattern);; say $password; sub generate_pattern { my $length = shift; # populate first two values my @chars = ( int(rand(3)), int(rand(3)) ); for my $i (2..$length-1) { # check if previous two values match if ($chars[$i - 1] == $chars[$i - 2]) { my @other_values = grep( !($_ == $chars[$i - 1]), (0..2)); # get random other value. ie if last two values were 1, pick +0 or 2 $chars[$i] = $other_values[ int(rand(2)) ]; } else { $chars[$i] = int(rand(3)); } } my $pattern = join '', @chars; # convert random string of 0,1,2 to A,n,! $pattern =~ tr/012/An!/; return $pattern; }

      Edit: It's a little ugly, but this is quite a bit faster than the route I took in my other code sample above.

Re: Removing similar characters
by Kc12349 (Monk) on Sep 02, 2011 at 12:55 UTC

    Out of curiousity, what are you relying on for randomness?

      See below for the code. I have 6 arrays set up to handle the various types of passwords that the user could request. Once the user inputs the type of password and the password length, I'm using the rand function to generate the password and then either output it to the user directly, or output it to a file. The script also checks the length of the password and warns them if it is below 14 characters, suggesting that longer passwords are more secure. </P.

      use diagnostics; use strict; use warnings; #sets password ranges my @password; my $password; my $password_length = 0; my $user_length = 0; #seperate arrays for each password type my @chars1 = ('0'..'9'); my @chars2 = ('A'..'Z'); my @chars3 = ('a'..'z'); my @chars4 = ('A'..'Z', 'a'..'z'); my @chars5 = ('A'..'Z', 'a'..'z', '0'..'9'); my @chars6 = ('0'..'9', 'a'..'z', 'A'..'Z', '!','@', '#', '$', '%', '^', '&', '*', '(', ')', '<', '>', '?', '`', '+', '/', '[', '{', ']', '}', '|', '=', '_','~', ',', '.'); #user inputs required length of password print "Enter the required password length. "; chomp($user_length = <STDIN>); print "\n"; #user selects level of complexity12 print "Select a level of complexity for your password: \n"; print "1. Numeric passcode\t\t\t\t(low level of security) \n"; print "2. Single case alphabetic\t\t\t(low level of security) \n"; print "3. Multi-case alphabetic\t\t\t(low level of security) \n"; print "4. Alphanumeric\t\t\t\t\t(medium level of security) \n"; print "5. Alphanumeric with special characters\t\t(high level of secur +ity) \n"; print "Complexity level: "; chomp(my $level = <STDIN>); print "\n"; if ($level > 1) { while ($user_length < 14) { print "*********************************\n"; print "*\t\tError!\t\t*\n"; print "*********************************\n"; print "\n"; print "Strong password guidelines require a minimum password l +ength of 14 characters."; print "\n"; print "\n"; print "Do you want to generate a password which conforms to st +rong password guidelines? \n"; chomp (my $guidelines = <STDIN>); if ($guidelines =~ m/^y/i) { print "Enter a new password length: "; chomp ($user_length = <STDIN>); } elsif ($guidelines =~ m/^n/i) { goto PW; } } } PW: if ($level == 1) { #mixed case password print "Generating a numeric passcode."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars1[int rand @chars1]; push @password, $password; ++$password_length; } } elsif ( $level == 2) { #single case password print "Select case: \n"; print "1. Upper \n"; print "2. Lower \n"; print "Case: "; chomp(my $case = <STDIN>); if ($case == 1) { #uppercase password print "Generating an uppercase password."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars2[int rand @chars2]; push @password, $password; ++$password_length; } } else { #lower case password print "Generating a lower case password."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars3[int rand @chars3]; push @password, $password; ++$password_length; } } } elsif ($level == 3) { #mixed case password print "Generating a mixed case password."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars4[int rand @chars4]; push @password, $password; ++$password_length; } } elsif ($level == 4) { #alphanumeric password print "Generating an alphanumeric password."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars5[int rand @chars5]; push @password, $password; ++$password_length; } } else { #alphanumeric password with special characters print "Generating an alphanumeric password with special characters +."; #increments until $user_length is met while ($password_length <= ($user_length-1)) { $password = $chars6[int rand @chars6]; push @password, $password; ++$password_length; } } #start export function print "Do you want to export your password to a text file? (y/n) "; chomp(my $export = <STDIN>); print "\n"; if ($export =~ m/^y/i) { open (FH, '>>password.txt') or die $!; print FH "Your password is: ", @password, "\n"; close FH; } elsif ($export =~ m/^n/i) { print "Your password is: ", @password ,"\n"; } else { print "Enter either y or n to continue. \n" ; #needs to return to top of $export function } print "\n"; print "\n"; print "Your password has been generated. \n";
Re: Removing similar characters
by Not_a_Number (Parson) on Sep 02, 2011 at 13:09 UTC

    A bit late, perhaps, but:

    1) I agree that overgenerating and then filtering out unwanted strings is a Bad Idea (too redolent of a bogosort for my liking :).

    2) The code below uses the four character classes implicit in the OP.

    use strict; use warnings; my $password_length = 8 + rand 3; # Or whatever (here 8-10 chars) my @classes = ( qw/ upper lower digit punct / ); my @pattern; for ( 1 .. $password_length ) { my @tmp = grep { $_ ne last2( \@pattern ) } @classes; push @pattern, $tmp[ rand @tmp ]; } my %chars; for my $class ( @classes ) { @{ $chars{$class} } = map { chr =~ /[[:$class:]]/g } 0 .. 127; } my $password = join '', map ${ $chars{$_} }[ rand @{ $chars{$_} } ], @ +pattern; print $password; sub last2 { my $to_check = shift; return 'ok' if @{ $to_check } < 2; return $to_check->[ -1 ] if $to_check->[ -1 ] eq $to_check->[ -2 ]; return 'ok'; }

    That said, if I were to be issued a password like |V$w`'N#^8, I wouldn't hesitate to write it on a post-it and stick it on my monitor!

Re: Removing similar characters
by Marshall (Prior) on Sep 03, 2011 at 01:43 UTC
    I am not sure that your algorithm will generate more secure passwords. I think it is likely that the passwords will be less secure because you are ruling out large segments of the "password name space".

    If passwords can have a max of:
    - 2 upper case letters (AB) in a row...
    - 2 lower case letters (xy) in a row...
    - 2 non [A-Za-z0-9] letters in a row...
    Geez...

    This will be an intrinsically insecure system because the requirements are so extreme that the users will write the passwords down on paper (they are too weird to remember). Or they will come up with simple algorithms 1QaZ2WsX or whatever that easy for a program to guess.

    I would talk with your security folks. I think your proposed scheme has some serious flaws in practice.

    A password like: my2ndDogCamero is a pretty hard thing to guess, but might be pretty easy for me to remember - so easy that I don't have to write it down on a "sticky" in an office drawer. Maybe Camero is really my first car instead of my second dog...whatever..

Reaped: Re: Removing similar characters
by NodeReaper (Curate) on Sep 04, 2011 at 13:47 UTC
Reaped: Re: Removing similar characters
by NodeReaper (Curate) on Sep 05, 2011 at 13:47 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://923666]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (13)
As of 2014-11-24 20:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (147 votes), past polls