Q: password generation
Ralph
by using the following procedure:
- Open an English dictionary to a random page. If the left hand page
"tens" digit in the page number is even, use the pattern digit-word-
digit-word, else use the pattern word-digit-word-digit
- Open the dictionary to another random page and select the first
word (that I recognize :-)) on the left page
- Open the dictionary to another random page and select the first
word on the right page
- Open the dictionary to another random page and select the "tens"
digit on the left page
- Open the dictionary to another random page and select the "tens"
digit on the left page
- Using the pattern selected earlier, form the new password
Recently, I have modified my technique to include "special" characters
by using the digits generated to select the character above the
appropriate number key on the keyboard (1 = '!', 2 = '@', etc.),
choosing whether to use a special character or a number based again on
the tens digit of a random page selection.
Is this method "secure"? Are the password reasonable?
I thought of using a similar method to write a generator using a
secure random number generator (java.security.SecureRandom or
something similar in Python) and a LONG list of English words that I
found on the 'net.
Any thoughts?
Are my accounts going to be attacked now that people know how I
generated my passwords :-)?
Carsten Krueger
> Is this method "secure"?
No more, now I know your scheme and reduce the searching range extremly.
greetings
Carsten
--
ID = 0x2BFBF5D8 FP = 53CA 1609 B00A D2DB A066 314C 6493 69AB 2BFB F5D8
http://www.realname-diskussion.info - Realnames sind keine Pflicht
http://www.spamgourmet.com/ + http://www.temporaryinbox.com/ - Antispam
cakruege (at) gmail (dot) com | http://www.geocities.com/mungfaq/
Kristian Gj�steen
>For about 25 years, I have been generating new passwords for my logins
>by using the following procedure:
Start counting:
> - Open an English dictionary to a random page. If the left hand page
>"tens" digit in the page number is even, use the pattern digit-word-
>digit-word, else use the pattern word-digit-word-digit
How many choices?
> - Open the dictionary to another random page and select the first
>word (that I recognize :-)) on the left page
The number of choices is equal to half the number of pages in your
dictionary. Count them.
> - Open the dictionary to another random page and select the first
>word on the right page
The number of choices is equal to half the number of pages in your
dictionary. Count them.
Does it matter much if you use the left or right page?
> - Open the dictionary to another random page and select the "tens"
>digit on the left page
How many choices?
> - Open the dictionary to another random page and select the "tens"
>digit on the left page
How many choices?
> - Using the pattern selected earlier, form the new password
How do we count the total number of combinations?
>Recently, I have modified my technique to include "special" characters
>by using the digits generated to select the character above the
>appropriate number key on the keyboard (1 = '!', 2 = '@', etc.),
>choosing whether to use a special character or a number based again on
>the tens digit of a random page selection.
What does this add?
>Is this method "secure"? Are the password reasonable?
No.
>I thought of using a similar method to write a generator using a
>secure random number generator (java.security.SecureRandom or
>something similar in Python) and a LONG list of English words that I
>found on the 'net.
>
>Any thoughts?
Diceware is a word that keeps appearing in these discussions. I've never
looked closely at it myself.
>Are my accounts going to be attacked now that people know how I
>generated my passwords :-)?
I would not be terribly surprised if that happened.
--
Kristian Gj�steen
Maaartin
> secure random number generator (java.security.SecureRandom or
> something similar in Python) and a LONG list of English words that I
> found on the 'net.
As you was already told, your method is not secure as it allows too
few choices.
IMHO, it was much stronger before you published the algorithm.
Before writing the generator, have a look at diceware, KeePass,
PasswordSafe, etc., first.
rossum
<kristi...@math.ntnu.no> wrote:
>>Is this method "secure"? Are the password reasonable?
>
>No.
<mode=grammar_nazi>No to the first question, no to the second question
or no to both questions?</mode>
Feel free to answer "yes". :)
>
>>I thought of using a similar method to write a generator using a
>>secure random number generator (java.security.SecureRandom or
>>something similar in Python) and a LONG list of English words that I
>>found on the 'net.
>>
>>Any thoughts?
>
>Diceware is a word that keeps appearing in these discussions. I've never
>looked closely at it myself.
Diceware has actually done the calculations, so you can select the
level of security you require.
See: http://world.std.com/~reinhold/diceware.html
rossum
Kristian Gj�steen
>On Wed, 24 Jun 2009 12:58:23 +0000 (UTC), Kristian Gjøsteen
><kristi...@math.ntnu.no> wrote:
>
>>>Is this method "secure"? Are the password reasonable?
>>
>>No.
><mode=grammar_nazi>No to the first question, no to the second question
>or no to both questions?</mode>
>Feel free to answer "yes". :)
:-) Yes, that should have been a no no.
--
Kristian Gj�steen
Ertugrul Söylemez
> For about 25 years, I have been generating new passwords for my logins
> by using the following procedure:
> [...]
>
> Any thoughts?
The following method is much stronger and yields much easier to remember
passwords: Select five random words from your dictionary and
concatenate them.
If we use the same dictionary with 20000 words on 500 pages, my password
will be 256000 billion times stronger than yours. See Kristian's post
for how to verify that.
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Paul Rubin
> - Open an English dictionary to a random page. If the left hand page
Other people have discussed issues with your approach. You might take
a look at www.diceware.com which gives something a bit more sound,
while still being easy to do without a computer.
Ilmari Karonen
>
> The following method is much stronger and yields much easier to remember
> passwords: Select five random words from your dictionary and
> concatenate them.
That is indeed a very good method. Personally, I prefer to limit
myself to four-letter words only (of which my dictionary has about
3300), and use six of them. That gives about the same total strength,
and seems to make the passwords easier to type and remember.
There are also standardized lists of a few thousand short and easily
remembered words compiled specifically for this use, but I haven't
really found them to produce any better passwords in practice than my
method. YMMV.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
glenbadd
>
> > The following method is much stronger and yields much easier to remember
> > passwords: Select five random words from your dictionary and
> > concatenate them.
>
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.
Mateusz Stankiewicz
> That is indeed a very good method. Personally, I prefer to limit
> myself to four-letter words only (of which my dictionary has about
> 3300), and use six of them. That gives about the same total strength,
> and seems to make the passwords easier to type and remember.
I am not arguing that this method is wrong or whatsoever (it's many
times better than let's say first name as a pass) but for curiosity sake
I wonder how much entropy is in such password. How easy is it to break?
David Eather
if he is choosing 6 words from 3300 candidate words then 3300**6 equals
70-bits of entropy. For systems that implement passwords to key
conversion properly (key stretching and so forth) that length would be
secure against all but the biggest TLA's. If the passwords to key
conversion is done poorly then it would be within the abilities of large
companies such as IBM etc.
rossum
wrote:
Yeah, but an XTLA (such as GCHQ) has 33% more resources to throw at
the problem. :)
rossum
Ilmari Karonen
*chuckles* :)
Anyway, even without key strengthening, 70 bits should be enough to
ensure that the password is probably not the weakest link. If a big
government agency or someone else with comparable resources *really*
wants my password, they can just sneak a (software or hardware)
keylogger onto my computer, compromise whatever software or service
I'm using the password for, or even just kidnap me and apply a rubber
hose until I cough up the password. Depending on the mix of resources
available to the would-be attacker, at least one of these options is
likely to be significantly quicker and easier than brute forcing 2**70
iterations of any reasonable key derivation function.
Indeed, for most purposes, six random 4-letter words are probably
overkill. Even four words (~ 46 bits) ought to be enough to deter
most casual attackers, or at least make them seek alternative
approaches such as the ones outlined above (or easier targets).
Ertugrul Söylemez
> > > The following method is much stronger and yields much easier to
> > > remember passwords: Select five random words from your dictionary
> > > and concatenate them.
>
> 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.
Maaartin
> > 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.
Andrew Swallow
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
Ertugrul Söylemez
The point is: random capitalization of the first character merely
doubles the number of words available, which adds exactly one bit per
word. You would need to use a 12 words password to compensate for the
11.69 bits of entropy added by a single additional word in the original
3300 words dictionary.
I'm assuming that the attacker knows everything except the words chosen
from the dictionary. In particular he knows the dictionary and the
exact generation method used.
Greets,
Ertugrul.
Maaartin
> larger dictionary, permitting use of passphrases containing say
> 10 word sentences.
>
> My paper dictionary contains "Over 60,000 definitions".
Ok, but using twice as much words gives you only 1 bit per word. And
using longer words means more typing.
> I'm assuming that the attacker knows everything except the words chosen
> from the dictionary. In particular he knows the dictionary and the
> exact generation method used.
Under your assumption you're surely right.
> The point is: random capitalization of the first character merely
> doubles the number of words available, which adds exactly one bit per
> word. You would need to use a 12 words password to compensate for the
> 11.69 bits of entropy added by a single additional word in the original
> 3300 words dictionary.
That's right. That's why I'd never use it this way.
Random capitalization of any character would give me 20 bits (on the 5
4-character word passphrase),
but it'd way harder to type (at least for me) than your additional
word.
That's why I'd use some strange substitutions giving me much more for
less effort.
Ilmari Karonen
>
> Random capitalization of any character would give me 20 bits (on the
> 5 4-character word passphrase), but it'd way harder to type (at
> least for me) than your additional word.
More importantly, it would be much harder to *remember* which letters
you need to capitalize than to remember one or two additional words.
Or which of these passphrases (generated using a slightly smaller
dictionary of only 2354 words) would _you_ find easier to memorize:
a) "ramp true boat deem land card buoy" (7*11.2 = 78.4 bits), or
b) "iaMb Laid ZETA DiCK hOBO" (5*11.2 + 20 = 76 bits)?
Try it -- type both a few times, for practice, then go away for five
minutes and see if you can retype them exactly without looking.
rossum
wrote:
>On 2009-07-03, Maaartin <graj...@seznam.cz> wrote:
>>
>> Random capitalization of any character would give me 20 bits (on the
>> 5 4-character word passphrase), but it'd way harder to type (at
>> least for me) than your additional word.
>
>More importantly, it would be much harder to *remember* which letters
>you need to capitalize than to remember one or two additional words.
>
>Or which of these passphrases (generated using a slightly smaller
>dictionary of only 2354 words) would _you_ find easier to memorize:
>
> a) "ramp true boat deem land card buoy" (7*11.2 = 78.4 bits), or
> b) "iaMb Laid ZETA DiCK hOBO" (5*11.2 + 20 = 76 bits)?
>
>Try it -- type both a few times, for practice, then go away for five
>minutes and see if you can retype them exactly without looking.
I sometimes use a system of regular capitalisation across the phrase,
for example:
tramP kilLs stOat aFter Seven
xxxxX xxxXx xxXxx xXxxx Xxxxx
That makes it easier to remember where the capital letters go, though
it does reduce the entropy somewhat compared to random capitalisation.
rossum
Ertugrul Söylemez
> I sometimes use a system of regular capitalisation across the phrase,
> for example:
>
> tramP kilLs stOat aFter Seven
>
> xxxxX xxxXx xxXxx xXxxx Xxxxx
>
> That makes it easier to remember where the capital letters go, though
> it does reduce the entropy somewhat compared to random capitalisation.
After having told us that, the entropy added is zero. ;)
Seriously: Your method adds very little, because there aren't many such
regular patterns.
Ertugrul Söylemez
> > 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".
>
> Ok, but using twice as much words gives you only 1 bit per word. And
> using longer words means more typing.
You should quote properly mentioning the original poster. Many
newsreaders have a threaded view, where you could be mistaken to quote
me instead of Andrew. In such cases it's best to just write two
separate messages starting two subthreads.
> > The point is: random capitalization of the first character merely
> > doubles the number of words available, which adds exactly one bit
> > per word. You would need to use a 12 words password to compensate
> > for the 11.69 bits of entropy added by a single additional word in
> > the original 3300 words dictionary.
>
> That's right. That's why I'd never use it this way.
> Random capitalization of any character would give me 20 bits (on the 5
> 4-character word passphrase), but it'd way harder to type (at least
> for me) than your additional word.
> That's why I'd use some strange substitutions giving me much more for
> less effort.
The point of using a dictionary is passwords, which are both easy to
remember and easy to type. One more word is probably much better as
Ilmari pointed out. Adding two words (from a 3300 words dictionary)
gives you more than 20 bits. If you insist on not increasing the number
of words, you can use a larger dictionary.
rossum
wrote:
>rossum <ross...@coldmail.com> wrote:
>
>> I sometimes use a system of regular capitalisation across the phrase,
>> for example:
>>
>> tramP kilLs stOat aFter Seven
>>
>> xxxxX xxxXx xxXxx xXxxx Xxxxx
>>
>> That makes it easier to remember where the capital letters go, though
>> it does reduce the entropy somewhat compared to random capitalisation.
>
>After having told us that, the entropy added is zero. ;)
And you believed me? :)
>
>Seriously: Your method adds very little, because there aren't many such
>regular patterns.
Agreed. I have sixteen patterns, eight patterns and the equivalent
eight antipatterns, so they add just four bits.
rossum
>
>
>Greets,
>Ertugrul.
Ertugrul Söylemez
> >> I sometimes use a system of regular capitalisation across the
> >> phrase, for example:
> >>
> >> tramP kilLs stOat aFter Seven
> >>
> >> xxxxX xxxXx xxXxx xXxxx Xxxxx
> >>
> >> That makes it easier to remember where the capital letters go,
> >> though it does reduce the entropy somewhat compared to random
> >> capitalisation.
> >
> > After having told us that, the entropy added is zero. ;)
>
> And you believed me? :)
At least I'll consider it when breaking your passwords. =)
> > Seriously: Your method adds very little, because there aren't many
> > such regular patterns.
>
> Agreed. I have sixteen patterns, eight patterns and the equivalent
> eight antipatterns, so they add just four bits.
And they are inconvenient to type anyway.
Maaartin
> You should quote properly mentioning the original poster. Many
> newsreaders have a threaded view, where you could be mistaken to quote
> me instead of Andrew. In such cases it's best to just write two
> separate messages starting two subthreads.
Ok, but I'm reading it online and see it very differently.
I'm used to repeat only the necessary part of the previous message
'cause I hate to be forced to read all the stuff I already have read.
I also prefer to reply to all at once, since otherwise I'd make four
times as much postings.
But next time I'll do it your way (at least I'll try).
> The point of using a dictionary is passwords, which are both easy to
> remember and easy to type. One more word is probably much better as
> Ilmari pointed out. Adding two words (from a 3300 words dictionary)
> gives you more than 20 bits. If you insist on not increasing the number
> of words, you can use a larger dictionary.
I do not insist, I just think that escaping somehow from any pattern
makes it stronger.
Using a larger dictionary hardly helps as YOU demostrated. According
to
http://en.wikipedia.org/wiki/English_language#Number_of_words_in_English
there are 475,000 words in the probably largest dictionary, which
gives me only 3.8 bit more per word
and weights 6 kg and $47.50.
***TO Ilmari Karonen:
> More importantly, it would be much harder to *remember* which letters
> you need to capitalize than to remember one or two additional words.
>
> Or which of these passphrases (generated using a slightly smaller
> dictionary of only 2354 words) would _you_ find easier to memorize:
>
> a) "ramp true boat deem land card buoy" (7*11.2 = 78.4 bits), or
> b) "iaMb Laid ZETA DiCK hOBO" (5*11.2 + 20 = 76 bits)?
>
> Try it -- type both a few times, for practice, then go away for five
> minutes and see if you can retype them exactly without looking.
You're right... that's why I need a simple rule used for ALL my
passwords.
My password looks like none of the above, let's say I start with
ramptrueboatdeemland
having (according to you) 5*11.2 bits = 56 bits, apply my rule 1
1. Capitalize the letters at positions 2, 3, 5, and 7.
and get (using position numbering starting at 0)
raMPtRuEboatdeemland
apply the rule
2. Increment (Caesar-like) each letter following the first and second
vowel.
and get (the wovels are "a" and "u")
raNPtRuFboatdeemland
apply the rule
3. Capitalize all letters between the last two characters belonging to
the set {"z", "x", "c", ..., "m"}
and get again (the two characters are the "e" and the immediatelly
preceding "e", so this is a no-op)
raNPtRuFboatdeemland
apply the rule
4. Replace "q"->"1", "w"->"2", ..., "o"->"9", "p"->"0", but only
twice, starting from position 10.
and get
raNPtRuFboa5d3emland
I see it's a bit complicated, but I claim:
1. The rules are easy to remember and not hard to use (once you've got
used to them).
2. There's no way to find out the rules given only few passwords.
3. Even if you know some rules, applying them makes you risk to miss
the password.
***TO rossum:
> I sometimes use a system of regular capitalisation across the phrase,
> for example:
>
> tramP kilLs stOat aFter Seven
>
> xxxxX xxxXx xxXxx xXxxx Xxxxx
>
> That makes it easier to remember where the capital letters go, though
> it does reduce the entropy somewhat compared to random capitalisation.
***TO Ertugrul Söylemez:
For somebody knowing your rule, the entropy is zero.
For somebody not knowing it, the entropy is 1 bit per letter.
The rule is simple, but easy to find out given a single other
password.
> After having told us that, the entropy added is zero. ;)
Right. I understand the added entropy here as the amount of missing
information,
so if I tell you my favorite password
p^&iyg/*-Y))~hJ87UVjhvjh,m:\}{uit/|
than it's entropy is zero for you.
> Seriously: Your method adds very little, because there aren't many such
> regular patterns.
It depends what regular means. For somebody the following may be
regular:
xxxXX xxXxX xxXXx xXxxX xxXXx
In fact, there's simple rule for it, do you see it?
Even here, there's a similar simple rule:
xxxXX xXxxX XXxXX XxxxX XxxXX
***TO rossum:
> >> I sometimes use a system of regular capitalisation across the phrase,
> >Seriously: Your method adds very little, because there aren't many such
> >regular patterns.
> Agreed. I have sixteen patterns, eight patterns and the equivalent
> eight antipatterns, so they add just four bits.
They do now. After you have told us.
> And you believed me? :)
At least I'll consider it when breaking your passwords. =)
***TO Ertugrul Söylemez:
> > And you believed me? :)
> At least I'll consider it when breaking your passwords. =)
That's why I gave you so many fake ideas. :D:D
Ertugrul Söylemez
>> The point of using a dictionary is passwords, which are both easy to
>> remember and easy to type. One more word is probably much better as
>> Ilmari pointed out. Adding two words (from a 3300 words dictionary)
>> gives you more than 20 bits. If you insist on not increasing the number
>> of words, you can use a larger dictionary.
>
> I do not insist, I just think that escaping somehow from any pattern
> makes it stronger.
But this is not how security works. Your system should assume that the
attacker knows your method completely including all possible patterns.
They just need to find out, which of the patterns and words you used at
which positions.
Here is the reason: Firstly and most importantly this makes the math
much simpler (x^y), hence it makes reasoning about your security easier
by the same factor. Particularly it eliminates assumptions and special
cases.
Of course your extensions contribute some security, but the expense is
higher complexity and less convenience. This is likely not what you
wanted when deciding to use dictionary-based passwords in the first place.
> Using a larger dictionary hardly helps as YOU demostrated. According
> to
> http://en.wikipedia.org/wiki/English_language#Number_of_words_in_English
> there are 475,000 words in the probably largest dictionary, which
> gives me only 3.8 bit more per word
> and weights 6 kg and $47.50.
A 3300 words dictionary is quite small. Modern dictionaries contain far
more words. For example the German Duden contains more than 150000
definitions. You can also find large word lists online.
Moving from a 3300 words dictionary to a 6600 words dictionary certainly
doesn't add much, but you would be moving to 475000 words, which would
add 7.17 bits (not 3.8 bits) per word, without making the passwords any
harder to remember. However, it bears the risk of getting longer words,
so adding a few more short words from the 3300-dictionary would probably
be better, and this is still what I'm recommending. Also beware that
real dictionaries are redundant to some extent, so the actual number of
terms may be less than the number of definitions.
If you want high entropy with short easy-to-type passwords, don't use a
dictionary-based approach, but rather a pronounceable password
generator. Those passwords are not as easy to remember, although the
pronounceability helps a lot.
>> Seriously: Your method adds very little, because there aren't many such
>> regular patterns.
>
> It depends what regular means. For somebody the following may be
> regular:
> xxxXX xxXxX xxXXx xXxxX xxXXx
> In fact, there's simple rule for it, do you see it?
> Even here, there's a similar simple rule:
> xxxXX xXxxX XXxXX XxxxX XxxXX
You could add up to 5 bits per word using such capitalization rules,
assuming that the attacker doesn't know what "regular" means for you,
i.e. the attacker needs to assume random patterns. This is for
five-letter passwords. Using a 3300 * 2^5 = 105600 words dictionary has
the same effect without that assumption.
However, using the original 3300 words dictionary and seven random
words, do you really need such strengthening methods?
Greets,
Ertugrul.