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

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

From	markspace <-@.>
Newsgroups	comp.lang.java.programmer
Subject	Re: Password quality (Was: Patricia trie vs binary search.)
Date	2012-05-25 12:17 -0700
Organization	A noiseless patient Spider
Message-ID	<jpolrn$ale$1@dont-email.me> (permalink)
References	<jpmev4$63l$1@dont-email.me> <jpmgrb$o5a$1@speranza.aioe.org> <jpmlbf$a3o$1@dont-email.me> <a076f3cb-d062-41e1-9a9a-43de60de82fb@googlegroups.com>

Show all headers | View raw

On 5/25/2012 9:41 AM, Lew wrote:
>
> I wonder about eliminating two-letter combinations. How much entropy
> does that add (or subtract) from passwords?

I was thinking the same thing.  Also searching for the longest possible 
word, and not bactracking, might be sufficient.  Once you find "word", 
why go back and scan for two or three letter combinations?

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

The idea was that if you increase the required length of a passphrase, 
users may defeat your requirement by just repeating a shorter bad 
password. "birdbirdbirdbird" is a pretty guessable 16 letter password, 
and "bird" appears in the bad password list.  However, 
"birdaliceferretsalut" is a pretty decent password, even though each of 
its four component words appears in the bad password list.  So if you 
can spot the individual component words and make sure they don't repeat, 
you've improved entropy a bit.

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

Yes, there should be other checks.  Overall length, and let's say at 
least 5 to 7 different characters.  So even though "UB40UB40UB40UB40" is 
16 characters and no sub-words appear on the bad password list, it only 
uses 4 different characters, which we might not want to allow.

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

Right, although comparing algorithms can be hard too.  I would have to 
implement each algorithm such that it was optimal, and I don't always 
have the skill or time to do that.  "Many eyes" on a problem is often 
the more efficient solution.  (This is also know as "research" and "not 
re-inventing the wheel".)  Though certainly it wouldn't hurt to make the 
attempt.

Glen's answer above was very helpful.  Wikipedia has cross-referenced 
their string-matching algorithms so that finding one leads to all the 
others.

<http://en.wikipedia.org/wiki/Category:String_matching_algorithms>

This gives me something to chew on, at least.

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