So working in IT, we have a requirement to generate secure passwords pretty much all the time, well certain organizations add more stringent requirements beyond the number of required character classes and length requirements. One such organization I work for also limits the number of characters of a single character class (lowercase, uppercase, special characters, numbers) that can appear consecutively. I have built a function that does facilitate this, however, it essentially just brute forces the password, which is pretty terrible. How would you approach this particular problem from a computer science perspective knowing speed is critical while maintaining randomness.
I feel like there should be some sort of shuffle technique I can implement, but every solution I come up with is either too slow or reduces the randomness of the string.
Function New-Password {
PARAM(
[Int]$PasswordLength = 64,
[Int]$MinUpperCase = 5,
[Int]$MinLowerCase = 5,
[Int]$MinSpecialCharacters = 5,
[Int]$MinNumbers = 5,
[Int]$ConsecutiveCharClass = 0,
[Int]$ConsecutiveCharCheckCount = 1000,
[String]$LowerCase = 'abcdefghiklmnoprstuvwxyz',
[String]$UpperCase = 'ABCDEFGHKLMNOPRSTUVWXYZ',
[String]$Numbers = '1234567890',
[String]$SpecialCharacters = '!"$%&/()=?}][{@#* ',
[String]$PasswordProfile = '',
#Advanced Options
[Bool]$EnhancedEntrophy = $True
)
If ([String]::IsNullOrEmpty($PasswordProfile) -eq $False) {
#You can define custom password profiles here for easy reference later on.
New-Variable -Force -Name:'PasswordProfiles' -Value:@{
'iDrac' = [PSCustomObject]@{PasswordLength=20;SpecialCharacters=" &?>-}|.!(',_[`"@#)*;$]/§%=<:{@";}
}
If ($PasswordProfile -in $PasswordProfiles.Keys) {
$PasswordProfiles[$PasswordProfile] |Get-Member -MemberType NoteProperty |ForEach-Object {
Set-Variable -Name $_.name -Value $PasswordProfiles[$PasswordProfile].($_.name)
}
}
}
New-Variable -Force -Name:'PassBldr' -Value @{}
New-Variable -Force -Name:'CharacterClass' -Value:([String]::Empty)
ForEach ($CharacterClass in @("UpperCase","LowerCase","SpecialCharacters","Numbers")) {
$Characters = (Get-Variable -Name:$CharacterClass -ValueOnly)
If ($Characters.Length -gt 0) {
$PassBldr[$CharacterClass] = [PSCustomObject]@{
Min = (Get-Variable -Name:"min$CharacterClass" -ValueOnly);
Characters = $Characters
Length = $Characters.length
}
}
}
#Sanity Check(s)
$MinimumChars = $MinUpperCase $MinLowerCase $MinSpecialCharacters $MinNumbers
If ($MinimumChars -gt $PasswordLength) {
Write-Error -Message:"Specified number of minimum characters ($MinimumChars) is greater than password length ($PasswordLength)."
Return
}
#New-Variable -Force -Name:'Random' -Value:(New-Object -TypeName:'System.Random')
New-Variable -Force -Name:'Randomizer' -Value:$Null
New-Variable -Force -Name:'Random' -Value:([ScriptBlock]::Create({
Param([Int]$Max=[Int32]::MaxValue,[Int32]$Min=1)
if ($Min -gt $Max) {
Write-Warning "[$($myinvocation.ScriptLineNumber)] Min ($Min) must be less than Max ($Max)."
return -1
}
if ($EnhancedEntrophy) {
if ($Randomizer -eq $Null) {
Set-Variable -Name:'Randomizer' -Value:(New-Object -TypeName:'System.Security.Cryptography.RNGCryptoServiceProvider') -Scope:1
}
#initialize everything
$Difference=$Max-$Min
[Byte[]] $bytes = 1..4 #4 byte array for int32/uint32
#generate the number
$Randomizer.getbytes($bytes)
$Number = [System.BitConverter]::ToUInt32(($bytes),0)
return ([Int32]($Number % $Difference $Min))
} Else {
if ($Randomizer -eq $Null) {
Set-Variable -Name:'Randomizer' -Value:(New-Object -TypeName:'System.Random') -Scope:1
}
return ([Int]$Randomizer.Next($Min,$Max))
}
}))
$GetString = [ScriptBlock]::Create({
Param([Int]$Length,[String]$Characters)
Return ([String]$Characters[(1..$Length |ForEach-Object {& $Random $Characters.length})] -replace " ","")
})
$CreatePassword = [scriptblock]::Create({
New-Variable -Name Password -Value ([System.Text.StringBuilder]::new()) -Force
#Meet the minimum requirements for each character class
ForEach ($CharacterClass in $PassBldr.Values) {
If ($CharacterClass.Min -gt 0) {
$Null = $Password.Append([string](Invoke-Command $GetString -ArgumentList $CharacterClass.Min,$CharacterClass.Characters))
}
}
#Now meet the minimum length requirements.
If ([Int]($PasswordLength-$Password.length) -gt 0) {
$Null = $Password.Append((Invoke-Command $GetString -ArgumentList ($PasswordLength-$Password.length),($PassBldr.Values.Characters -join "")))
}
return (([Char[]]$Password.ToString() | Get-Random -Count $Password.Length) -join "")
})
Switch ([Int]$ConsecutiveCharClass) {
'0' { New-Variable -Name NewPassword -Value (& $CreatePassword) -Force }
{$_ -gt 0} {
New-Variable -Name CheckPass -Value $False -Force
New-Variable -Name CheckCount -Value ([Int]0) -Force
For ($I=0; $I -le $ConsecutiveCharCheckCount -and $CheckPass -eq $False; $I ) {
New-Variable -Name NewPassword -Value (& $CreatePassword) -Force
$TestPassed = 0
ForEach ($CharClass in $PassBldr.Values) {
IF ([Regex]::IsMatch([Regex]::Escape($NewPassword),"[$([Regex]::Escape($CharClass.Characters))]{$ConsecutiveCharClass}") -eq $False) {
$TestPassed
}
}
if ($TestPassed -eq $CheckClasses.Count) {
$CheckPass = $True
}
}
}
Default {Write-Warning -Message "This shouldn't be possible, how did you get here?!"}
}
Return $NewPassword
}
CodePudding user response：
How would you approach this particular problem from a computer science perspective knowing speed is critical while maintaining randomness.
Before moving any further, I should note that these properties (compliance with the described policy vs maintaining randomness/entropy) are mutually exclusive - you can't "maintain randomness" by carefully "correcting" the distribution of output from a PRNG.
I would split the problem into two separate functions:
Test-PasswordCharSequence- to quickly validate whether a given password string complies with the policyShuffle-PasswordCharSequence- to randomly shuffle the characters in any given password once
Atomizing these core operations should make it easier to tune/refactor.
For the validation function, it might be tempting to use regular expression - but I would suggest simply iterating over the string and keep track of consecutive characters of the same class.
function Test-PasswordCharSequence {
param(
[string]
$String,
[System.Collections.IDictionary]
$CharacterMap,
[int]$Limit = 5
)
# Keep tracking the last seen character class and length of consecutive sequence
$currentClass = ""
$counter = 0
foreach($char in $String.ToCharArray())
{
if($CharacterMap.ContainsKey($char) -and $CharacterMap[$char] -eq $currentClass)
{
$counter
}
else
{
$counter = 1
$currentClass = $CharacterMap[$char]
}
# if we've seen the same class for too many consecutive characters, fail
if($counter -gt $Limit){
return $false
}
}
# No sequence over limit observed
return $true
}
Then we need a function to shuffle the password. The most efficient truly random (again, depending on the RNG used) shuffling algorithm that I know of is the in-place Fisher-Yates shuffle algorithm, which can be implemented as follows:
function Shuffle-PasswordCharSequence
{
param(
[Parameter(Mandatory)]
[string]$String
)
$chars = $String.ToCharArray()
$max = $chars.Length
#Fisher-Yates Left to Right
for($i = 0; $i -lt $max - 1; $i )
{
$j = Get-Random -Minimum 0 -Maximum ($max - $i)
$chars[$j],$chars[$i $j] = $chars[$i $j],$chars[$j]
}
return [string]::new($chars)
}
To use these in conjunction with your existing New-Password function:
# define character classes to use
$CharacterClasses = @{
LowerCase = 'abcdefghiklmnoprstuvwxyz'
UpperCase = 'ABCDEFGHKLMNOPRSTUVWXYZ'
Numbers = '1234567890'
SpecialCharacters = '!"$%&/()=?}][{@#* '
}
# generate inverse character map for the validation function
# we use [Dictionary[char,string]] rather than [hashtable] to ensure case-sensitive handling of keys ('b' vs 'B')
$classMap = [System.Collections.Generic.Dictionary[char,string]]::new()
foreach($entry in $CharacterClasses.GetEnumerator())
{
foreach($char in $entry.Value.ToCharArray())
{
$classMap[$char] = $entry.Name
}
}
# generate initial password
$passwordCandidate = New-Password -PasswordLength 127 @CharacterClasses
# validate generated password, shuffle until successful
$shuffleCount = 0
while(!(Test-PasswordCharSequence $passwordCandidate -CharacterMap $classMap)){
$passwordCandidate = Shuffle-PasswordCharSequence $passwordCandidate
$shuffleCount
}
Write-Host "Generated valid password after ${shuffleCount} shuffles"
CodePudding user response：
I think that what @vonPryz mentioned in his comment "Why not build the password character by character?" is actually possible and probably the fastest way to do this.
The point is that you have to create the password in 2 stages, first build a complexity list with the charactersets (rather then the final characters) and than in the next stage select the concerned character for the character set on that position. If the $MaxConsecutiveChar is reached, choose a new character from the character set at that position:
Function New-Password {
Param(
[Int]$PasswordLength = 64,
[Int]$MinUpperCase = 5,
[Int]$MinLowerCase = 5,
[Int]$MinSpecialCharacters = 5,
[Int]$MinNumbers = 5,
[Int]$MaxConsecutiveChar = 3,
[String]$LowerCase = 'abcdefghiklmnoprstuvwxyz',
[String]$UpperCase = 'ABCDEFGHKLMNOPRSTUVWXYZ',
[String]$Numbers = '1234567890',
[String]$SpecialCharacters = '!"$%&/()=?}][{@#* '
)
enum CharSet {
LowerCase
UpperCase
SpecialCharacters
Numbers
}
$CharSets = [system.collections.generic.dictionary[CharSet, Char[]]]::new()
$MinSetChars = [system.collections.generic.dictionary[CharSet, Int]]::new()
$MinimumChars = 0
[CharSet].GetEnumNames().ForEach{
$CharSets[$_] = (Get-Variable -ValueOnly -Name $_).ToCharArray()
$MinChar = [Int](Get-Variable -ValueOnly -Name "Min$_")
$MinSetChars[$_] = $MinChar
$MinimumChars = $MinChar
}
If ($MinimumChars -gt $PasswordLength) {
Throw "Specified number of minimum characters ($MinimumChars) is greater than password length ($PasswordLength)."
}
# Build a list of characters sets
$SetList = for ($i = 0; $i -lt $PasswordLength; $i ) { $CharSets.Keys |Get-Random }
# Insert the Min* required characters for the specific sets
# Making sure that the position is not already taken by another Min* characterset
$Used = [System.Collections.Generic.HashSet[int]]::New()
$CharSets.Keys.ForEach{
for ($i = 0; $i -lt $MinSetChars[$_]) {
$At = Get-Random $PasswordLength
if (!$Used.Contains[$At]) {
$SetList[$At] = $_
$Null = $Used.Add($At)
$i
}
}
}
# Elect a character for each set
$LastChar = $Null
$ConsecutiveChars = 1
-Join $SetList.ForEach{
$Char = $CharSets[$_] |Get-Random
# Check the consecutive characters (choose another when required)
While ($ConsecutiveChars -ge $MaxConsecutiveChar -and $Char -eq $LastChar) { $Char = $CharSets[$_] |Get-Random }
$ConsecutiveChars = if ($Char -eq $LastChar) { $ConsecutiveChars 1 } else { 1 }
$LastChar = $Char
$Char
}
}
New-Password
X23@[X0C5%FL3Demyf5?5})f]5Kt#usC#m1 3?T(NOb4DmYsX8FA3pF46OUZeW3V
To prove that the -MaxConsecutiveChar works and is quiet fast:
$Params = @{
MaxConsecutiveChar = 1
LowerCase = 'ab'
UpperCase = 'ab'
Numbers = 'ab'
SpecialCharacters = 'ab'
}
New-Password @Params
babababababababababababababababababababababababababababababababa