Uneven password distribution

[CrachedAgain]

When using LAPS I noticed that the passwords had too many numbers. I checked the frequency of characters for ~800 computers, which confirmed that this was the case.

Using equal possibilities for each dict gives letters 1/4*1/26 chance, special characters 1/4*1/20 chance while numbers have 1/4*1/10 chance. In addition the plus sign is repeated in the special dictionary.

All of these problems are in PasswordGenerator.h in the Generate function.

[jformacek]

Hello,
Thanks for reporting.
Can you share your results of char category distribution? Will look at it.

Thank you,
Jiri

[CrachedAgain]

Upper and lower case characters had from 81 to 123 occurences.
Special chars except plus had from 123 to 166 occurences.
Numbers and plus had from 240 to 291 occurences.

[jformacek]

Hello,
I tested myself - created code below that includes passwordGenerator.h as it is in the project, and checked char distribution on 2000 paswords generated (complexity=4, length=16)
Results:
Small: 7858
Large: 8227
Nums: 8034
Spec: 7881
So distribution quite OK; on higher number of passowords even more close to complete random.
Results for 200K passwords:
Small: 799531
Large: 799926
Nums: 799517
Spec: 801026
So Ibased on this, I would say password gen algo works as expected.

Can you test on your end as well? Like running the C++ code below on machine in your environment to see results? Or, export your passwords to file such as D:\testpwd.txt and count char distribution using powershell below, like this and share results?

Thanks,
Jiri

$r=@();"[A-Z] Large","[a-z] Small","\d Num","[\,\.\-\+\;\!\#\&\@\{\}\[\]\$\/\(\)\%\|] Spec" | 
    %{$s=$_.Split(' '); $r+=new-object PSObject -property @{"Regex"="^$($s[0])`$";"Cat"=$s[1];"Count"=0}}
Get-Content D:\testpwd.txt | 
    %{$_.GetEnumerator() | 
    %{ $c=$_; $r | 
    %{if($c -cmatch $_.Regex) {
    $_.Count++}}}};$r | Select Cat,Count

#include "stdafx.h"
#include "PasswordGenerator.h"

int main()
{
	int pwdLen = 16;
	int numOfPwd = 200000;

	PasswordGenerator gen(4, pwdLen);
	int smalls = 0;
	int large = 0;
	int nums = 0;
	int spec = 0;

	for (int i = 0; i < numOfPwd; i++)
	{
		auto pwd = gen.Generate();
		//_putts(pwd);
		for (int j = 0; j < pwdLen; j++)
		{
			auto c = (int)pwd[j];
			if (c >= (int)'a' && c <= (int)'z')
				smalls++;
			else if
				(c >= (int)'A' && c <= (int)'Z')
				large++;
			else if
				(c >= (int)'0' && c <= (int)'9')
				nums++;
			else
				spec++;
		}
	}
	_tprintf(L"Results:\n"
		"  Small: %u\n"
		"  Large: %u\n"
		"  Nums:  %u\n"
		"  Spec:  %u\n",
		smalls, large, nums, spec
	);
	_gettch();
}

[CrachedAgain]

Results for 200K passwords:
Small: 799531
Large: 799926
Nums: 799517
Spec: 801026
So Ibased on this, I would say password gen algo works as expected.

You misunderstood. I didn't say that the characterclasses were not evenly distributed, I said that they should not be. From the list above you'll have ca.

• 799531/26 = 30751 letter "m"
• 799926/26 = 30766 letter "K"
• 799517/10 = 79951 digit "8"
• 801026/19 = 42159 character ";"

Since the dictionaries are not the same length, they should not have the same weight.
Pseudocode for a better distribution:

N = length of all used dictionaries
Dicts[] list of dictionaries
Used[] list of used dictionaries
Random(N) gives cryptographic random integer in range 0 to N-1

If not near end of password or the dictionary is already used:
   r=Random(N)
   dic=0
   while 1:
       if  r < len( Dicts[dic] ):
           ch = r
           Used[dic] = true
           break
       else:
           r = r - len( Dicts[dic] )
           dic = dic + 1
else: // must use a given dictionary
    dic = whichever dictionary is not used
    ch = Random( len( Dicts[dic] ) )
    Used[dic] = true
At the end dic gives the dictionary and ch gives the index in the dictionary.

[jformacek]

Well, actually it was never a design goal to ensure wighted distribution of chars from different dictionaries - main design goal was to ensure proper randomness of generated password.
Algo provided with solution gives equal distiobution of dictionaries used.

Currently I'm thinking on extension model so as you could develop own PasswordGenerator.dll that would be loaded when there's need for getting a password (basically a DLL that exports an entry point something like TCHAR* Generate(int Complexity, int Length), and updated password generator according to your proposal could be one of those implementations. The other could be password gen that returns password created of predefined words (dice-words generator) that was proposed by other guy I'm talking with about passwords.

Makes sense?

Jiri