Re: Q: password generation

Maaartin wrote:
Little tricks like adding numbers between the words, capitalising some
letters and mutating some letters (e->3, o->0, i->1) also multiplies
the possibilities and is still easy to remember.
Adding one more word will likely be much better than introducing noise,
because the larger the alphabet gets, the less is the effect of adding
more characters (in this case words/numbers) to it. Reason (where b =
bits of entropy, c = alphabet size, n = number of random characters):

2^b = c^n
=> b = n * log c / log 2

As you see, only the logarithm of 'c' contributes to the entropy. It
grows very slowly:

db/dc = n / (c * log 2)

Increasing 'n' will be much more effective.

Your computation is correct, nonetheless I think you're wrong.
Using 5 words from the 3300 word dictionary you get
log2(pow(3300, 5)) = log2(4e17) = 58.4 bits
A single additional word gives you 11.7 bits more, an additional word
would give you about nothing.
That's exactly as you wrote (assuming c=3300, i.e., taking the
dictionary as the alphabet).

Let me assume, the dictionary is public and all the words consist of
four lowercase letters each.
This allows the attacker to limit the search to the above 4e17
possibilities.
If the dictionary contained 3300 secretly kept random words, he'd have
to try all 5*4 lowercase letter strings giving
log2(pow(26, 20)) = log2(2e28) = 94.0 bits
just like in case of 20 random letters, right?

Surely, such a secretly kept dictionary is totally impractical.
But some random-looking capitalizing and random substitutions applied
to publicly known dictionary are nearly as good.
Imagine the following simple rules:
1. Capitalize the letters at positions 2, 3, 5, and 7.
2. Increment (Caesar-like) each letter following the first and second
vowel.
3. Capitalize all letters between the last two characters belonging to
the set {"z", "x", "c", ..., "m"}
4. Replace "q"->"1", "w"->"2", ..., "o"->"9", "p"->"0", but only
twice, starting from position 10.
My description may be confusing, but the details don't matter and I'm
sure, you've got the idea.
These rules are easy to follow and easy to remember, so I'd use them
for all my passwords.

Given some hundreds of passwords made according to them, you can
probably crack them.
But you'll never get hundreds of passwords of mine since I'm not going
to use so many passwords.

Given only a couple of them, you could probably make some assumptions
about my rules, but I'm not sure if it helped you.
And you could be never sure, you got all of them.

Given no password of mine and having no idea about my rules,
you'd have to try all 20 character long strings consisting of (let's
say) lowercase and uppercase letters and digits, leading to
log2(pow(26+26+10, 20)) = log2(7e35) = 119.0 bits

What I wanted to say:
1. Starting with dictionary words, there're two views of the
passphrase: 5 words or 20 characters
2. Using some simple tricks might make bruteforcing using the words
IMHO impossible.
3. Using these tricks doesn't increase the alphabet size by one, but
more then doubles it instead.
In reality, I'd use simpler rules, but I'd use special characters as
well.

The spelling checker in most word processors contains a much
larger dictionary, permitting use of passphrases containing say
10 word sentences.

My paper dictionary contains "Over 60,000 definitions".

Andrew Swallow
.

Relevant Pages

  • Re: Q: password generation
    ... because the larger the alphabet gets, the less is the effect of adding ... more characters to it. ... four lowercase letters each. ... Given some hundreds of passwords made according to them, ...
    (sci.crypt)
  • Re: Q: password generation
    ... because the larger the alphabet gets, the less is the effect of adding ... four lowercase letters each. ... Capitalize all letters between the last two characters belonging to ... Given some hundreds of passwords made according to them, ...
    (sci.crypt)
  • Re: Security level of SET PASS /GENERATE ?
    ... passwords use an "alphabet" of syllables, each about 3 characters long. ... I have no idea how many "letters" are in this alphabet, ... Hitchhiker's guide to the galaxy. ...
    (comp.os.vms)
  • Re: Security level of SET PASS /GENERATE ?
    ... passwords use an "alphabet" of syllables, each about 3 characters long. ... I have no idea how many "letters" are in this alphabet, ...
    (comp.os.vms)
  • Re: Etymology of the name KRAVITZ
    ... it could neve have evolved but for the fact that the sounds "B" and "V" are rendered by the same alphabet character in Cyrillic. ... The two characters look similar enough to anyone who does not know the alphabet or the language, ... The analogy Stan makes with the similarity between various Hebrew letters is a good one. ... My point was that the same thing can happen with the Cyrillic "B" characters, among people who were literate in Yiddish, but had some visual familiarity with Cyrillic alphabet letters. ...
    (soc.genealogy.jewish)
Quantcast