Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Random string generator

by tachyon (Chancellor)
on Feb 06, 2003 at 02:02 UTC ( [id://233030]=note: print w/replies, xml ) Need Help??


in reply to Random string generator

Something like this produces pseudo-random vaguely memorable char sequences. For default passwords I just tend to pick one that is easy to remember from a dozen options:

#!/usr/bin/perl; srand( time() ^ ($$ + ($$ << 15)) ); my @v = qw ( a e i o u y ); my @c = qw ( b c d f g h j k l m n p q r s t v w x z ); for (1..12) { my ($flip, $str) = (0,''); $str .= ($flip++ % 2) ? $v[rand(6)] : $c[rand(20)] for 1 .. 9; $str =~ s/(....)/$1 . int rand(10)/e; $str = ucfirst $str if rand() > 0.5; print "$str\n"; } __DATA__ Fuco1wipon name5jeweb Vute2tecis Paco8podec wopu3wasig lune2fosuk Same2jamek Qeqy0nebit rizi5muwuj Qone7tatat Daho7cejab fesi2jideq

This algorithm produces 2*20*6*20*6*10*20*6*20*6*20 or around 82 billion permutations so it is quite feasible to brute force it though quite time consuming. 26**8 is around 208 billion so there is similar (order of magnitude) complexity to a random 8 char same case alphabetic string but far more memorability.

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

Replies are listed 'Best First'.
Re: Random string generator
by jonadab (Parson) on Feb 06, 2003 at 04:25 UTC
    This algorithm produces 2*20*6*20*6*10*20*6*20*6*20 or around 82 billion permutations so it is quite feasible to brute force it though quite time consuming.

    If all passwords don't have to be exactly the same length (just within a range), it's possible to modify your algorithm slightly, keeping the same principle, by allowing a vowel to be a dipthong and/or allowing a consonant to be a blend, at random. This will throw off the odd-even pattern, while still leaving something more likely to be pronounceable than an entirely random string.

    srand( time() ^ ($$ + ($$ << 15)) ); my @v = ( 'a', 'e', 'i', 'o', 'u', 'y'); #, 'ai', 'ou', 'oo', 'ee', 'oi'); my @c = ( 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z'); $nc = @c; # Number of consonants excluding blends. # (Some of the blends are not good endings.) @c = (@c, 'bl', 'br', 'tr', 'st', 'dr', 'th', 'ch', 'sh'); my @d = (0..9, '_', '-', '.'); my $length = 10; # This is a minimum. my ($flip, $str) = (0,''); for ( 1 .. ($length - 1) ) { $flip++; if ($flip%2) { if ($flip==$length-1) { $str .= $c[rand($nc)]; } else { $str .= $c[rand(@c)]; } } else { $str .= $v[rand(@v)]; } } my $re; my $digitpos = rand(5)+3; foreach (1..$digitpos) { $re .= "."; } $str =~ s/($re)/$1 . $d[rand(@d)]/e; $str = ucfirst $str; print "$str\n";

    Results...

    • Vedos5titem
    • Rif7yfadrom
    • Cajy1dugec
    • Kunory7trir
    • Zih4ychusyv
    • Meb9rishystil
    • Brucuce4chyv
    • Nob0achuchew
    • Buq6ehiqor
    • Lybru-bexuk

    So the question is, how secure are these passwords with that modification? Well, if the person doing the brute-forcing knows exactly how you generate them, or has seen a good number of them, they're not much better, because there's not enough variation. Adding in a bunch of different blends and dipthongs would probably help a bit. What would help more would be using several different algorithms and alternating between them at random -- so that one time you might get one like the above, and another time you might get "ad-hoc(Variable)17" or "e.g.{Sputnik}82" and yet another time you might get "f0rtu1t10us_gr33nh0us3" or "m4rg1n_bl4sph3my". (Update: those patterns are not as hard to brute-force as the one above, but they were intended only as quick examples.)

    Any one of those patterns could be brute-forced, but trying to code a general case that takes in all of them could be just about as bad as doing each one of them in turn; with a dozen different such patterns, that could get prohibitive. If you want to be sure that they have to do them in turn (rather than coding a general case of some kind), throw in one pattern that generates fairly lengthy stuff like "running-implicit-tomorrow-wet-Howard" and "chortle-wax-Susan-dromedary-green". That makes for a very nice pessimal case when the algorithm trying to break it also has to deal with the possibilities inherent in the other patterns. Oh, and make sure your wordlist is large and undisclosed. (The wordlist can be disclosed if it is seriously large, e.g., if you scan in the OED.)

    Of course, if they can get what they want by compromising only any one password, then you have to make sure each and every one of the patterns has a certain minimum of resistance to brute-forcing. Your exact threshhold will depend on your circumstances.

     --jonadab

      You can do the maths easy enough. Say you have a dictionary of 10**5 words and use dict_word[0..9] as the pattern you get 10**5*10 == 10**6 == not enough permutations that should be memorable. If you use dict_word[0..9]dict_word instead you then get a respectable 10**11 or 100 billion permutations which is the same conmplexity as what was presented. The rationale for \w{4}\d\w{5} was to make two reasonably easy to remember strings separated by an easy to remeber digit. By adding [-_.] to the mix you only up the permutations to 106 billion (81*10**9*13/10) from 81 == small change. If you add the digit in position 5 or 6 randomly you up the permutations from 82 to 164 billion which is still a relatively small change. Using dipthongs instead of single consonants still only adds ((consonants+dipthongs)/consonants))**5 units of complexity.

      Extra length is a good way to increase conplexity as each extra alphanumeric adds roughly one order of magnitude of complexity. Exactly one order of magnitude for digits, a little more for alphabetics where the set > 10.

      By far the best protection from brute forcing is to protect the pwd database with as little as a 1 second retry timout as 82*10**9 seconds is roughly 2100 years so your attacker should be dead long before they crack a pwd.

      Like all security it is simply a matter of how high you want to raise the bar, the idea being for it not to be worth the time expended for the result obtained.

      cheers

      tachyon

      s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

        Extra length is a good way to increase conplexity as each extra alphanumeric adds roughly one order of magnitude of complexity. Exactly one order of magnitude for digits, a little more for alphabetics where the set > 10.

        Interesting. I thought about this a bit and did a little more arithmetic, and I discovered that one of my (slightly improved) randomly-generated syllables is roughly 30*15*53, or about 23 thousand. My words file in /usr/share/dict/words has about 45 thousand (according to wc), so it is less than twice as complex as one of my syllables, even though it could be a good deal longer (brahamaputra came up once; the longest syllable my algorithm can make would be six letters long). However, the word may still be as easy to remember, since it is in fact a real word.

        I know it's considered bad to have a dictword for a password, so obviously one of my syllables is not enough. Two of them strung together, OTOH, with a hyphen in-between for easy legibility, comes to more like 500 million give or take; three of them sends my calculator into scientific notation (e+13). I figured up [A-Za-z0-9]{8}, and that comes to e+14, or slightly more complex. Still, it's close, and it is arguable that Shaf-Golk-Said may be easier to remember than rG8wnPe4, despite being half again as long. So, for posterity, my improved algorithm...

        #!/usr/bin/perl; use strict; use warnings; my $dictionaryfile = '/usr/share/dict/words'; my $number_to_generate=12; my $length = 10; my $showalgorithm=0; # Set true to have the main loop # tell which algorithm it calls for each password. # Note that right now it's always using alg 3; remove # the line $alg=3; to use all three of them. sub rndStr{local $"=''; "@_[map{rand$#_} 1 .. shift]"; } sub algorithm_one { # Pretty much random, but hard to remember. # Security climbs steeply with length. return rndStr $length, 'A'..'Z', 0..9, 'a'..'z', '-', '_', '.'; } my @words; if (open WORD, "<$dictionaryfile") { my $w; while (<WORD>) { chomp; $words[$w++]=lc; } close WORD; } else { @words = (); warn "Unable to open dictionary file $dictionaryfile (error: $!); faking it.\n"; } srand( time() ^ ($$ + ($$ << 15)) ); my @vowels = ('a', 'e', 'i', 'o', 'u'); # 5 my @dipthongs = ('ai', 'ou', 'oo', 'ee', 'oi', 'au', 'ui', 'ea', 'ow', 'aw', ); # 10 my @consonants = ( 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'l', 'm', 'n', 'p', 'r', 's', 't', 'v', 'x', 'z' ); # 17 my @startblends = ('bl', 'br', 'cl', 'ch', 'cr', 'cw', 'dr', 'fl', 'fr', 'gl', 'gr', 'ph', 'qu', 'sc', 'sh', 'sn', 'st', 'sw', 'th', 'tr', 'tw', 'w', 'wh', ); # 23 my @endblends = ('ch', 'ck', 'gh', 'k', 'ld', 'lk', 'lm', 'ln', 'lp', 'lt', 'lv', 'lx', 'mp', 'nd', 'ng', 'nk', 'nt', 'ph', 'rb', 'rd', 'rf', 'rg', 'rk', 'rm', 'rn', 'rp', 'rs', 'rt', 'rv', 'rx', 'sh', 'sk', 'sp', 'st', 'th', 'ts', ); # 36 my @delimiters = (0..9, '_', '-', '.', ',', 'y', '!'); my %delimiter_pairs = ( '<' => '>', '(' => ')', '{' => '}', '[' => ']', '-' => '-', '_' => '_', '.' => '.', # 'y' => 'y', ); sub delimitpairaround { my (@k, $open, $close); @k = keys(%delimiter_pairs); $open = $k[rand(@k)]; $close = $delimiter_pairs{$open}; return $open . "@_" . $close; } sub syllable_start { my @c = (@consonants, @startblends, @consonants); my $s = $c[rand(@c)]; return (rand(973)%7)>4 ? $s : ucfirst $s; } sub syllable_end { my @c = (@consonants, @endblends, @consonants); return $c[rand(@c)]; } sub vowel_or_dipthong { my @v = (@vowels, @dipthongs, @vowels); return $v[rand(@v)]; } sub syllable { return syllable_start() . vowel_or_dipthong() . syllable_end(); } sub realword { my ($w, $r); if (@words) { $w = $words[rand(@words)]; $r = rand(7378)%100; ($r>66) ? ucfirst $w : (($r>12) ? $w : uc $w); } else { return syllable(); } } sub algorithm_two { my ($flip, $str, $l) = (0,'', $length-1); while ($flip < $l) { ++$flip; if (($flip%3)==1) { $str .= syllable_start(); } elsif (($flip%3)==2) { $str .= vowel_or_dipthong(); } else { $str .= syllable_end(); if ((rand(1000)%2) and ($flip<$l)) { $str .= $delimiters[rand(@delimiters)]; $l--; }}} return $str; } sub algorithm_three { my $str = ""; my ($s, $prob); foreach $s (1..(int $length/3)) { $prob=(rand(873)%100); my $piece = ($prob>45) ? syllable() : realword(); if (not $s % 2) { $str .= delimitpairaround($piece); } else { $str .= $piece; } } return $str; } my ($password, $alg); foreach $password (1..$number_to_generate) { $alg=rand(1793)%3+1; $alg=3; # Remove to get a mix of algorithms. if ($showalgorithm) { printf " % 2d> ", $alg; } if ($alg==1) { print algorithm_one() . "\n"; } elsif ($alg==2) { print algorithm_two() . "\n"; } elsif ($alg==3) { print algorithm_three() . "\n"; } else { print STDERR "ERROR: Not sure what algorithm to use for password $password."; } }

         --jonadab

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://233030]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (5)
As of 2024-03-28 16:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found