Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #14795

Password quality (Was: Patricia trie vs binary search.)

Show all headers | View raw

markspace wrote:
> Thanks for those pointers (pun not intended).  The "sub-string search" 
> was referring to was picking words out of a longer, undelimited string.
> 
> The example I posted looked for bad passwords within a larger password.
> 
> "passxword" contains at least two bad passwords, pass and word, 
> according to the dictionary file I download from here (that's the 
> bpw.txt file in the sample code):
> 
> <http://www.godlikeproductions.com/badpasswords.php>
> 
> The code I posted find pass, ass, word, and or in the string 
> "passxword", which are all bad passwords according to that link above. 
> (I deliberately avoid reporting single letters as bad).

I wonder about eliminating two-letter combinations. How much entropy does that add (or subtract) from passwords?

It's practicable and arguably more reliable to use passphrases comprising 
all natural words whose entropy exceeds that of a fairly long Mxyzptlk® 
key. (Note: "Mxyzptlk" may well pass all your password checks, yet is highly 
guessable. Equally flawed are other stringlets that pass naive checks, 
like "XB-17", "UB40" and others.) See 
http://world.std.com/~reinhold/diceware.html 
for how to create high-entropy, highly memorable passphrases.

> Practically speaking, hashing appears to be just as fast for a lookup, 
> but hashing doesn't tell you when to stop, so it's always N^2 for this 
> sort of problem.  My algorithm should average less, hopefully much less 
> if you have very long input strings.
> 
> I really don't know what set me off looking at this; it's just a little 
> random experiment I suppose.

Your main question of space- and time-efficient substring matching is 
a fairly well-studied problem. I don't off the top of my head have better 
answers, but your approach to experiment is viable.

You could instrument (profile) your code over different algorithms and 
input dataset profiles (that is, relative proportion of long, medium-length 
and short strings, relative proportion of "bad" substrings in the mix, and 
other factors that affect the "shape" of the data your algorithms process).
Algorithm analysis should give you the big O, but not the constant factors 
or where they break for lower /n/.

A lot of algorithm analysis critically depends on what constitutes "average" 
datasets.

-- 
Lew

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Patricia trie vs binary search. markspace <-@.> - 2012-05-24 16:07 -0700
  Re: Patricia trie vs binary search. glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-05-24 23:39 +0000
    Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-24 17:56 -0700
      Password quality (Was: Patricia trie vs binary search.) Lew <lewbloch@gmail.com> - 2012-05-25 09:41 -0700
        Re: Password quality (Was: Patricia trie vs binary search.) markspace <-@.> - 2012-05-25 12:17 -0700
  Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-26 17:30 -0700
    Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-26 18:17 -0700
    Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-27 18:44 -0700
      Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-27 22:00 -0700
        Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-28 08:20 -0700
          Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-28 14:38 -0700
        Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-28 09:20 -0700
          Re: Patricia trie vs binary search. Lew <noone@lewscanon.com> - 2012-05-28 21:54 -0700
            Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 09:14 -0700
              Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 09:55 -0700
                Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 11:17 -0700
                Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 11:22 -0700
                Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 14:44 -0700
                Re: Patricia trie vs binary search. Lew <lewbloch@gmail.com> - 2012-05-29 14:03 -0700
                Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 14:49 -0700
                Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 15:23 -0700
                Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 15:39 -0700
                Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 16:08 -0700
                Re: Patricia trie vs binary search. Lew <lewbloch@gmail.com> - 2012-05-29 18:25 -0700
            Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 09:16 -0700
              Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 13:37 -0400
                Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 10:49 -0700
                Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 13:58 -0400
                Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 14:20 -0400
                Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 11:21 -0700
                Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 14:29 -0400
                Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 15:00 -0400
  Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 09:24 -0400

csiph-web