PasswordMaker Forums
Firefox/SeaMonkey/Mozilla/Netscape/Flock Browser Extension => Bugs => Topic started by: David on October 11, 2005, 03:53:31 AM
-
Steps to reproduce (with my setup at least):
1) Enter a large password length-say 40.
2) Enter a large number of characters-say 200.
3) Use PM to populate password field.
Actual results:
The password generated by PM is shorter than requested. The exact length depends on other factors.
Desired results:
The password length matches the requested length.
This is not a case of a password being cut off by maxlength.
Incidentally, the random character feature is off by one character in length: ask for 3 random characters, and it gives you 4.
-
Eric, I nailed this down to at least give you a starting point of where to look:
Password Length set to 35
No leet
HMAC-SHA-256
URL Contains: .google.com/
Use URL: google.com
I simply copied the default character set and pasted it at the end of itself to produce an incorrect password length. I then used the half-split method, until I hit upon the magic number of 180 characters that produce a good result - anything more produces a password that is one character short:
Character set length = 180
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789`~!@#$%^&*()_-+={}|[]\:";'<>?,./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789`~!@#$%^&*()_-+={}|[]\:"
PW: OK
CYY_FFQT,&?C9QSU-`v{o}v%ehl{J#{&u:& = 35
Character set length = 181
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789`~!@#$%^&*()_-+={}|[]\:";'<>?,./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789`~!@#$%^&*()_-+={}|[]\:";
PW: WRONG
;!Ut$(MkhV*^Ya_xbE@CW4Pm6%Dv2*<#SL = 34 - off by one
Next, I tried just alphanumeric characters, to see if maybe it had anything to do with the non-alpha-numerics, but this produced the same results (180 character max).
I did play with even larger character sets, and the resulting password length gets even shorter, so the bug seems to be compounding.
I hope this helps...
-
Incidentally, the random character feature is off by one character in length: ask for 3 random characters, and it gives you 4.
This one is confirmed, but not every time...
The first few times I tried it, it worked fine - then it started doing as you described.
I tried closing the Browser, and reopening it, and again - it would work once, twice, sometimes three times, but then it would start giving one extra character.
-
The password generated by PM is shorter than requested. The exact length depends on other factors.
I'm aware of this. It's due to the nature of hash functions: they each produce a fixed length byte array. SHA-1 always produces 160 bytes; SHA-256 always produces 256 bytes. The bytes are encoded into printable characters using the character set you define, but that character set is a radix. The more characters in the set, the more bytes can be encoded by a single character.
The only way around this is to repeat the password to meet the requested password length.
Is this an acceptable fix?
-
Ok... well, as long as the problem is known and reproducable - and not likely to change? - then I'm ok with simply dcumenting it myself (when, why and how it happens). Even better would be a pop-up warning whenever someone sets their Settings in such a way that this 'issue (I guess bug isn't the correct term) kicks in?
I don't use character sets that big or passwords that long, so this doesn't affect me anyway. Now that you mention it, I do recall something about his, but I guess since it didn't affect me I simply forgot about it.
-
I will add a popup warning about it; good idea, and also have the password repeat until it meets the desired length.
David, I'll fix the Random character length problem--thanks for reporting it.
-Eric
-
I think for the repeat thing, have the repeat occur before the rstr2any function, so that if the character set is more than the hex string "0123456789abcdef" you can't see where it repeats. Maybe repeat the hash some 30 times?
BTW, you sure about SHA1 returning 160 bytes? I thought it was 20. Maybe you're thinking bits? (160/8=20)
-
I will add a popup warning about it; good idea, and also have the password repeat until it meets the desired length.
Perfect...
Out of curiousity...
It's due to the nature of hash functions: they each produce a fixed length byte array. SHA-1 always produces 160 bytes; SHA-256 always produces 256 bytes.
This may be a dumb question (obvious to anyone who understands 'the nature of hash functions'), but - is this something that is likely to ever change? If not, then your solution of repeating the password until the number of characters is reached si definitely the best solution.
-
I'm aware of this. It's due to the nature of hash functions: they each produce a fixed length byte array. SHA-1 always produces 160 bytes; SHA-256 always produces 256 bytes. The bytes are encoded into printable characters using the character set you define, but that character set is a radix. The more characters in the set, the more bytes can be encoded by a single character.
The only way around this is to repeat the password to meet the requested password length.
Is this an acceptable fix?
Thanks for the replies!
Three things:
(1) I don't understand what increasing the number of characters inputted has to do with the outputted password length. With 100 characters, the outputted password matches the requested password in length. With 200+ characters, the outputted password is shorter. With 10,000 characters, it's quite a bit shorter.
In my confused mind, if the # of characters inputted really has to affect the outputted password length, wouldn't it be more secure (than repeating the password) to pick a random set of x (max number of characters) characters from the inputted set?
(2) Repeating the password or whatever solution is done runs the chance of altering existing passwords, so like other fixes, it probably should only be done with new passwords.
(3) I would suggest that if there's a warning, it should give the max input characters and max password length so people aren't having to play around to find those values...
Anyway, sorry for the confusion. I regularly use very long passwords; I think it was the addition of the random feature that brought this issue to the fore, as it's now simple to have input character sets of whatever length you wish.
Edit: I guess it can't be random, silly me. :)
-
I think for the repeat thing, have the repeat occur before the rstr2any function, so that if the character set is more than the hex string "0123456789abcdef" you can't see where it repeats.
I don't understand how this would hide the repeat. Inputting the byte array duplicated 30 times to rstr2any() should produce repeated output, no? BTW, maybe you could tell me how you setup Venkman to step through this code. It would be very helpful to me.
BTW, you sure about SHA1 returning 160 bytes? I thought it was 20. Maybe you're thinking bits? (160/8=20)
Sorry, I meant bits.
is this something that is likely to ever change?
Nope. Never.
I don't understand what increasing the number of characters inputted has to do with the outputted password length
I'll demonstrate by analogy, and assume you know what hexadecimal (http://en.wikipedia.org/wiki/Hexadecimal). Suppose you want to represent the number fifteen in decimal notation (base 10). It requires two characters to do so; a one and a five: 15. Now suppose you want to represent that same number in hexadecimal notation (base 16). It requires only one character to do so: F. But in base 2 (binary), you'd require four characters: 1111. As you can see, the higher the base, the less characters needed to represent ("encode") the same information.
The character set for base 10 is generally 0123456789. The character set for base 16 is generally 0123456789abcdef. When you specify a character set comprised of 200 characters, you are using base 200 notation to encode a mere 8 bytes of data for MD4/MD5, 20 bytes for SHA1 and RIPEMD-160, and 32 bytes for SHA-256. I hope this explains things.
Reading your last response, David, has given me another idea. I think PasswordMaker should limit password length as a function of the length of the character set rather than repeating the password.
-
Ok, I'd have to look at the code. Perhaps it has something to do with hashing, but from an outsider's perspective, the character set should not be doing double duty as (1) characters to choose from to make the password and (2) radix.
I don't think you should limit password length. If the radix (character set) is too large, I would suggest, as before, selecting characters from the inputted character set to actually use.
Example: User enters 10000 characters ($input). To get the desired password length, the character set needs to be 100 (say) ($maxinput). $input/$maxinput = $characterskipvalue (in this case, 100). PM will then use every $characterskipvalue'th character in the inputted set, setting the radix based on this limited set and using the characters in this limited set.
Again, though, it's not clear to me why the character set is doing double-duty. Don't feel like you have/ought to explain it though--I'll take your word. :)
-
it's not clear to me why the character set is doing double-duty
Hm, can you explain why you think the character set is being used for two things? What's the second purpose? You might help me to think of other ways of solving this/doing this by talking it through with me.
-
The bytes are encoded into printable characters using [1] the character set you define, but that [2] character set is a radix.
the character set should not be doing double duty as (1) characters to choose from to make the password and (2) radix.
Is that clearer? I told you I was confused :-(
-
Unless you're using a base that is a power of 2 (Most likely being 16 (hex character set)) the hash returns one big ass number, and rstr2any is basically converting raw bytes into another base.
Look at this: http://www.miquelfire.com/stuff/rstr2any.htm (http://www.miquelfire.com/stuff/rstr2any.htm) ;)
-
Unless you're using a base that is a power of 2
What does it return if it is a power of 2? this code was written by Paul Johnston, and I haven't stepped through it with Venkman...yet.
the character set should not be doing double duty as (1) characters to choose from to make the password and (2) radix.
Well, that's not really double-duty. Those are one and the same. Think about hex, for instance. Hex's character set is 0123456789abcdef and its radix is 16. The character set is merely defining an encoding (or code page) with which to map bytes to characters... just like ASCII, UTF-8, UTF-16, IS0-8859-1, or any other code page... (http://en.wikipedia.org/wiki/Code_page)
-
On that sample page I posted, look at the hex line and study the output, note how the repeat shows up in the output?
-
I don't understand, but it's okay :-)
My basic point is that giving PM 10,000 unique characters to choose from in composing the password should not make the outputted password less secure than if I gave it 100 unique characters to choose from. On the contrary, the opposite should be true.
However, it seems that's the way it works (10000 characters -> ~6? character password; 100 characters -> 40 character password), and, moreover, has to work. Rather unfortunate.
-
I think the key piece of information you're not understanding is that hash functions -- the underlying core of password generation -- output a fixed length regardless of input size.
If the radix (character set) is too large, I would suggest, as before, selecting characters from the inputted character set to actually use.
Then not all of the characters have the potential to be in the generated password.
Example: User enters 10000 characters ($input). To get the desired password length, the character set needs to be 100 (say) ($maxinput). $input/$maxinput = $characterskipvalue (in this case, 100). PM will then use every $characterskipvalue'th character in the inputted set, setting the radix based on this limited set and using the characters in this limited set.
Again, this has the drawback that not all of the 10,000 characters have the potential to be in the generated password. I'd rather inform the user that the character set is too large than fool him into thinking all the specified characters can be used in the generated password.
-
Alright, here's another solution: multiple hashes.
"Because of the nature of hash functions, your requested hash+character set precludes a password of the desired length. The maximum password length possible with your chosen settings is ___. Please choose an additional hash or make a change in your existing hash/character set settings.
For additional information, please see the <link>Help Section</link> on this topic."
Example: User chooses SHA-1 and SHA-256, in that order. The generated password is a concatenation of the hashes->SHA-1.SHA-256.
I'm not sure how you would go about implementing this solution--it is likely that at some point someone would want three hashes, or four, or whatever.
It seems to me that one ought to be able to enter the Unicode character set and generate a password of at least 127 characters (your current windows max, likely to change). Am I crazy?
One problem with this solution is insecurity--I don't know enough to know if this is insecure. But I'm sure the answer to that is clear to people familiar with hashes.
-
Or, why not, another:
"If the hash size is less than the key size, multiple instances of
the hash context are created -- enough to produce the required key
data. These instances are preloaded with 0, 1, 2, ... octets of
zeros (that is to say, the first instance has no preloading, the
second gets preloaded with 1 octet of zero, the third is preloaded
with two octets of zeros, and so forth).
As the data is hashed, it is given independently to each hash
context. Since the contexts have been initialized differently, they
will each produce different hash output. Once the passphrase is
hashed, the output data from the multiple hashes is concatenated,
first hash leftmost, to produce the key data, with any excess octets
on the right discarded."
(http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-14.txt)
Here's a discussion on the insecurity of multiple hash concatenation: http://man.phpschool.com/manual/kr/function.md5.php (http://man.phpschool.com/manual/kr/function.md5.php). You can look at the regular php manual, but at least one of the responses has been deleted there.
-
Or maybe PM should simply institute a sane limitation on the length of passwords?
Personally, I do not see the value in a 128 character password... I mean, its not like you're protecting the CIA NOC list, or the launch codes to the nations ballistic missile system or anything.
I see no reason to complicate the process. My suggestion is to simply limit the length of the passwords according to the inherent limitations of the hashes themselves.
-
Since we're on the topic, what about collisions?
Given a fixed character set output, the chance of collisions using a good hash is next to nothing.
Password generation using a variable character set, however, looks offhand to raise the probability of collisions significantly though.
(1) Obtain a 6 character output from a requested 20-character password with 400- character input.
(2) Obtain the same 6 character output from a requested 6-character password with 50-character input
etc.
I apologize if this is another dumb question.
Thanks everyone for helping me understand what's going on with the original issue here.
I think it's much clearer now. :)
-
Hi David,
I'm not sure how you would go about implementing this solution--it is likely that at some point someone would want three hashes, or four, or whatever.
Right. Inherent problem with that solution.
Regarding your quote from the OpenPGP RFC (http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-14.txt), PasswordMaker only uses one-way, non-symmetric hashing for generated passwords... therefore, no keys, keyrings, or keystores are involved. Thanks for the link, but it's not really applicable.
Hi tanstaafl,
Or maybe PM should simply institute a sane limitation on the length of passwords?
I'd rather not when there is a decent solution. I've thought of one, I think: the hash value itself should be the input to iterative calls of the hash function. In pseudo-code:
output = ""; // the generated password
input = master_password + url + modifier + the_other_stuff;
while (length_of_output < desired_pw_length) {
temp = hash(input);
output = output + temp;
input = temp;
}
-
Regarding your quote from the OpenPGP RFC (http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-14.txt), PasswordMaker only uses one-way, non-symmetric hashing for generated passwords... therefore, no keys, keyrings, or keystores are involved. Thanks for the link, but it's not really applicable.
Hmm. I didn't mean for the link to be taken literally--just that their solution to their own problem might shed light on a way to solve PM's.
-
I see. Well, what do you think of the solution I just proposed?
-
Perhaps it's because of my lack of understanding, but wouldn't it be rather repetitive-and if repetitive, while perhaps it wouldn't matter, fairly easy to establish the original hash given the entire password?
What I mean is that, if I understand it correctly-and there's a good chance I don't-the first x characters (the first hash) would be a selection of the original 10,000 characters, say, while the following characters would be a selection of the characters in the first hash.
First x characters: selected from 10,000.
Following characters: selected from x.
The OpenPGP initialization variation avoids this by concatenating multiple, different hashes of the original.
-
wouldn't it be rather repetitive
Definitely not. I can give you some examples if you'd like.
would be a selection of the original 10,000 characters, say, while the following characters would be a selection of the characters in the first hash.
No. The encoding remains the same for all iterations.
-
Ok, sounds good then--not surprising I misunderstood. :) Thanks for pursuing this Eric!
-
Thanks for pursuing this Eric!
My pleasure. Feel free to ask away :)
-
Or maybe PM should simply institute a sane limitation on the length of passwords?
I'd rather not when there is a decent solution. I've thought of one, I think: the hash value itself should be the input to iterative calls of the hash function. In pseudo-code:
Really, I was only kidding. I don't like limitations, but was just making a point... are there really people in here who are using 128 character passwords and/or 200+ character sets? If so... WHY?
Or maybe a better question to ask... just *how* much more secure is it? I think using a 12 character passwords based on HMAC-SHA-256 and the Default Character Set (modified by me in my own special way, of course) is more than sufficient, even for highly critical and/or sensitive top-secret government purposes.
That said, your proposed solution sounds best - as usual...
-
BTW, for warning of power of two, here's some code in which you can check to see if a number is a power of 2 (it's false if it is a power of 2)
((number - 1) & number)number being the length of the encode string, your proposed solution may not suffer from that too much...
-
It's still not clear to me why character sets which aren't a power of 2 cause the repetition?
-
Character set are a power of 2 cause the repetition, those that aren't won't cause it. Look at the test page I posted, it has a repeating string as input for rstr2any and shows some random encodings to be used. Though if your solutions ends up runing the code through rstr2any, and append stuff to it's output, it may not be an issue.
-
NOW i get it. I didn't notice the input was also a repeated string. Thanks.
-
Hello,
My suggestion for extending the password length is to use an additional counter which is hashed together with the data, instead of hashing the hash which might introduce unknown problems. Something like this:
For the first iteration, just 'data' is hashed, as before (this helps keeping backward compatibility).
For the second iteration, 'data' + '2' is hashed.
For the third iteraton, 'data' + '3' is hashed.
And so on. One caveat: in order to simplify the explanation I haven't introduced a separator between the data and the counter, but it's advisable to do so. '\n' or '\0' would be good separators. This is how it would look like for the second and following iterations when adding '\n' as separator:
Second iteration: 'data' + '\n' + '2' is hashed.
Third iteration: 'data' + '\n' + '3' is hashed.
...
The addition of the separator prevents that e.g. if 'data' ends in '2' the hash is the same as with 'data' with the '2' removed, in the second iteration. Example: say data = 'abc2'; without separator, the substring resulting from it would be the same as with data = 'abc' in the second iteration. With separator, the hash from 'abc\n2' is different from the one from 'abc2' and the problem disappears.
Thoughts?
-- Pedro Gimeno
-
Hi Pedro,
I like this idea. One question: is a separator necessary for each iteration, or just the first? If so, why?
-
Eric,
Just the second and following need a separator. The first one may stay as it is now.
The separator is needed to identify 'abc2' without any extra data and 'abc' + '2' (the '2' appended because it is the second iteration) as different strings.
I'll try a better explanation. Consider the following scenario:
You have two users, 'user' and 'user2', for connecting to domain.com. Your master password is 'PW'. You want to generate a long key which needs 2 hashes. If you don't use a separator, in the case of the first user the hashes would apply to these strings:
'PWdomain.comuser' (for the first iteration)
'PWdomain.comuser2' (for the second iteration)
On the other hand, in the case of the second user the following strings will be hashed:
'PWdomain.comuser2'
'PWdomain.comuser22'
The first string in this case is the same as the second string used before, thus the password characters generated will be equal. However, using separators the strings hashed would be, for the first user:
'PWdomain.comuser'
'PWdomain.comuser\n2'
and for the second user:
'PWdomain.comuser2'
'PWdomain.comuser2\n2'
All strings are now different, which is safer. Actually, I would like to see separators between all the input fields in the password generation algorithm for similar reasons (simple concatenation doesn't distinguish where each field terminates and the next starts), but that would break compatibility.
Note that everywhere I write \n I mean ASCII character LF, code 10. In any case the idea is to choose a separator that can't be entered by the user.
-- Pedro Gimeno
-
Sounds like a good idea. Thanks for the clarification. I'll use your suggestion instead of mine for the implementation.
-
My suggestion for extending the password length is to use an additional counter which is hashed together with the data, instead of hashing the hash which might introduce unknown problems.
This is implemented in 1.3.3. Additionally, one of the original bugs mentioned in this thread by David is also fixed:
Incidentally, the random character feature is off by one character in length: ask for 3 random characters, and it gives you 4.
-Eric
-
Tell me please you only implemented this fix for *new* passwords...
-
Yikes, unfortunately not. I didn't think anyone was experiencing the password limit length except when doing testing. I didn't realize you actually experienced this problem with real accounts.
You should be able to get around the problem by reducing the password length to the length of the password generated by 1.3.2. If you don't remember the password lengths you had in 1.3.2, uninstall 1.3.3, reinstall 1.3.2 and write them down.
1.3.3 *is* backwards compatible with 1.3.2 in that generated passwords are the same up to the max password lengths of 1.3.2. Where 1.3.2 would have stopped generating characters even though you requested a longer password, 1.3.3 steps up and actually provides you with all the needed characters.
Does that help?
-
Thanks Eric! I appreciate all your work--especially when you fix bugs that are bugging me ;).
So there'll just be a little bump here.
I figured I would have to do something like this, but I wanted to make sure that PM update was the problem and not something else (like I can't type today, etc.).