Many enterprise professionals use passwords that are weak and easily compromised. Equipped with this knowledge, as well as the exposure of more and more password leaks, dictionary attacks focused on compromised or popular passwords have become increasingly effective. As such, the National Institute of Standards and Technology recommends password blacklisting as a highly-effective means of preventing such attacks. Unfortunately, use of password blacklisting countermeasures has remained a relatively new innovation that has not yet achieved widespread corporate adoption.

At Yelp, however, we strive to add the latest and greatest defense mechanisms to our arsenal, which is why we adopted such password blacklisting countermeasures very quickly. Since Yelp uses Active Directory (AD) for all employee authentication and management, implementing our own customized Password Filter dynamic-link library (DLL) was the clear solution.

In this blog post we will outline how we built a password blacklisting service out of an existing open source DLL that met our policy and security needs.

Why didn’t we use a commercial option

Given the plethora of commercial options available, we debated whether to use a pay-for-pricing solution or an existing open-source option. Many of the 3rd party providers in the space offered software solutions that were easy to set up and proven to be effective. However, they often lack transparency in password filtering. We also worried that any fault on the third-party side could cause the Local Authority Subsystem Service to crash, resulting in a Blue Screen of Death and a reboot of all affected Domain Controllers (DCs). The outcome of such an event would greatly impact employees using the system. Lastly, reliance on third-party providers for such sensitive issues would increase Yelp’s attack surface area so we opted for an open-source solution that would give us fine-grained control.

Choosing the solution

After much research and testing, we found that OpenPasswordFilter (OPF) suited our needs best. We chose a forked version of the original implementation that added the ability to connect with a SQL database rather than comparing hashes in plaintext. One of the biggest concerns with utilizing a customized Password Filter DLL was the risk that any error run by the Local Security Authority (LSA) could potentially crash the running DC server. Another major concern was ensuring that new passwords could be appended quickly and effectively without affecting user experience. The chosen solution solved both these problems by incorporating a service-oriented architecture that decoupled essential LSA thread code from filtering functionality while also integrating an SQL-based DB that could be directly queried by the service. Furthermore, the design was fail-safe. Any triggered exceptions or errors during filtering would cause the system to fail open, mitigating any worrisome DC shutdown possibilities. Given the vulnerability of the LSA to DLL errors, this was a necessary tradeoff, especially knowing that errors would be logged if compromised password resets were made.

System Architecture

The Password Filtering service is comprised of three places:

  • OPF Service: The module for password verification (talks with the DLL over loopback).
  • OPF DLL: The raw Password Filter DLL which interfaces with the LSA for credential approval.
  • OPF DB: The database holding SHA-1 hashes of all easily-compromised passwords.

Whenever a client requests a password change, the request routes through their assigned domain controller that contacts the LSA. If the default password policy is not met (a combination of minimum password length and certain character criteria), the Password Filter DLL is not called and the password is automatically rejected. If, however, the default policy requirements are met, the DLL will be called with the password. The diagram below illustrates the process:

Figure 1: AD Password Filter Authentication Flow

Figure 1: AD Password Filter Authentication Flow

  1. Client initiates password request change through DC to LSA. The contact from DC to LSA is done by configuring the LSA notification package. If default password policy is met, registered DLLs are called, otherwise the password is denied.
  2. The PasswordFilter function, one of the three core methods of Microsoft’s PasswordFilter DLL interface, is called. This function returns a boolean response based on whether or not a reset should be made. The OPF version attempts connection to a specific port on the loopback interface to call the registered service. If this fails, the function returns true due to its fail-safe nature.
  3. If a connection can be established, the DLL attempts to send credentials to the OPF Service. A predetermined preamble is sent first, after which credentials are propagated.
  4. The hashed credential (SHA-1) is then checked for existence in the DB of easily-compromised passwords. An index on password hashes makes this significantly faster.
  5. Depending on whether the hash was found, a message indicating success or failure is returned to the OPFService, which makes its way to the initial DLL as a boolean, ending back in the hands of the LSA.
  6. The above process is repeated for all registered DLLs. Assuming all are successful, the password is officially committed to the Security Account Manager (SAM).
  7. The PasswordChangeNotify function is then called for each registered DLL for synchronization purposes.

Testing

Thoroughly testing this process was particularly important, since any errors would have serious impact, such as crashing the Domain Controller. Additionally, we wanted to make sure the system didn’t impose a significant performance overhead. Therefore, before touching our production environment, we tested the service on a standalone domain controller, and then again in a lab environment. The methodology was as follows:

  1. Setup a DC in its own standalone domain or in a lab domain.
  2. Configure the default domain password policy settings in accordance to Yelp’s password policy.
  3. Download a large dump of the top most commonly used/breached passwords. We chose to sample from this popular security password list.
  4. Randomly divide the password dump into four subsets (we used 4 of size 5000 each):

    1. Those conforming to default policy but belonging in the blacklist (A)
    2. Those conforming to default policy and not belonging in the blacklist (B)
    3. Those not conforming to the default policy and belonging in the blacklist (C)
    4. Those not conforming to the default policy and not belonging in the blacklist (D)

    For the above four sets, we would thus expect only B to result in reset successes.

  5. Generate SHA-1 hashes for B and C
  6. Create enabled LDAP users in the amount of total passwords to be tested
  7. Create a CSV file with each row containing a user, password, and category (A, B, C, D) pertaining to the password categorization.
  8. Run our custom-made powershell script (next page) for checking verified behavior.

Powershell script details:

  1. Each enabled user attempts to have their respective password reset
  2. The total time required is recorded using a stopwatch
  3. Expected reset success is validated based off exit code
  4. An AD bind is then performed to verify successful login
  5. Expected AD bind behavior is also validated based off exit code
  6. Results are aggregated and output by password category (specifically, average time per password reset and number of errors found)

The below script does the testing described above.

param([string]$file, [string]$dc, [string]$admin_usr, [string]$admin_pwd)

# Default error usage message
    Set-Variable errUsg -option Constant -Value "$($MyInvocation.MyCommand.Name) [CSV_FILE] [DC] [ADMIN_USR] [ADMIN_PWD]"

# Ensure proper parameters are given
    $CommandName = $MyInvocation.InvocationName
    $ParameterList = (Get-Command -Name $CommandName).Parameters
    foreach ( $key in $ParameterList.Keys  ) {
        $value = (Get-Variable $key -ErrorAction SilentlyContinue).Value
            if ([string]::IsNullOrEmpty($value)) {
                Write-Host "Required parameter not found."
                Write-Host "$errUsg"
                exit 1
            }
    }

# Check existence of csv file
if (!(test-path $file)) {
    Write-Host "File $file not found."
    exit 1
}

# Set password types and associated expectations (0 = failure, 1 = success)
$csv = Import-CSV -Path $file
$pwdTypes = @("NO_POLICY_NO_DUMP", "NO_POLICY_YES_DUMP", "YES_POLICY_NO_DUMP", "YES_POLICY_YES_DUMP")
$expected = @(0, 0, 1, 0)
$times = @(0) * 4
$errors = @(0) * 4
$counts = @(0) * 4

# Check provided DC is valid and that admin login credentials valid
dsquery user -u $admin_usr -p $admin_pwd -s $dc -q > $null 2>&1
if ($LastExitCode -ne 0) {
    Write-Host "Invalid remote credentials or DC server specified."
    exit 1
}

# Start logging
start-transcript -path C:\nail\syslog\DLL_LOG_$(get-date -format 'MM-dd-yyyy-HH-mm-ss').log
Foreach ($el in $csv) {

    # Extracted relevant fields
    $ex = $expected[$el.Id]
    $type = $pwdTypes[$el.Id]
    $usr = dsquery user -samid $el.User -s $dc -u $admin_usr -p $admin_pwd
    $pwd = $el.Password

    # Record time in milleseconds for password reset
    $sw = [system.diagnostics.stopwatch]::startNew()
    dsmod user $usr -pwd "$pwd" -mustchpwd no -d $dc -u $admin_usr -p "$admin_pwd" > $null 2>&1
    $sw.Stop()

    # Check exit code with expectations to validate reset success
    $r_s = If ($lastexitcode -ne 0) {0} Else {1}
    $t = $sw.get_ElapsedMilliseconds()
    $times[$el.Id] += $t
    if ($r_s -ne $ex) {
        $errors[$el.Id]++
    }

    # Perform AD bind and check with expectations to verify successful login
    (new-object directoryservices.directoryentry "", $usr, $pwd).psbase.name -ne $null > $null 2>&1
    $b_s = If ($lastexitcode -ne 0) {0} Else {1}
    if ($b_s -ne $ex) {
        $errors[$el.Id]++
    }

    # Log appropriately in the format of (EXPECTED, ACTUAL) for both the reset and bind
    $logline = "($usr) : [ $type  ] : RESET ($ex,$r_s) : BIND ($ex,$b_s) : TIME ($t)"
    if (($b_s -ne $ex) -or ($r_s -ne $ex)) {
        $logline = "[ERROR] [PASSWORD = $pwd] $logline"
    }
    $counts[$el.Id]++
    Write-Output $logline
}

# Aggregate final results
Write-Output ("*" * 22)
Write-Output "RESULTS:"
for ($i=0; $i -lt $pwdTypes.Length; $i++) {
    $type = $pwdTypes[$i]
    if ($counts[$i] -ne 0) {
        $t = $times[$i] / $counts[$i]
    } else {
        $t = 0
    }
    $es = $errors[$i]
    Write-Output "($type) ERRORS: $es AVG TIME: $t"
}  
stop-transcript

Results

Testing not only allowed us to verify correctness of our password filtering service, but also visualize data like reset time intervals:

Figure 2: AD Password Reset Time Intervals (with DLL)

Figure 2: AD Password Reset Time Intervals (with DLL)

More importantly, the DLL imposed marginal overhead:

Figure 3: AD Password Reset Time Intervals (with DLL)

Figure 3: AD Password Reset Time Intervals (with DLL)

Figure 4: AD Password Reset Time Intervals (with DLL)

Figure 4: AD Password Reset Time Intervals (with DLL)

Indeed, on average, with approximately 1 million passwords in our dump, we found the following:

Average Rest Time - Standalone Domain

Category Time
Not in dump 115.7656 ms
Yes in dump 83.2938 ms

Average Rest Time - Lab Domain

Category Time
Not in dump 415.8513 ms
Yes in dump 377.3411 ms

Conclusions

All in all, this project allowed us to better understand the underpinnings behind AD authentication and gave Yelp a much stronger layer of security for preventing threats against easily-compromised password dictionary attacks.

We strongly recommend employing similar blacklisting measures in your corporate environment. At the very least, ensure strong minimum password policy requirements. But understand that blacklisting offers a more effective means of mitigating against dictionary attacks while not imposing the counterproductive restrictiveness high-complexity password requirements offer.

For further readings, please refer to the original author’s open-source fork which inspired our implementation.

Back to blog