Targeted Password Guessing Using k-Nearest Neighbors

Targeted Password Guessing Using k-Nearest Neighbors

Speakers: Zhen Li

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=Cg247bKZU1o

Overview

This research introduces KPG (k-Nearest Neighbor Password Guessing), a novel non-parametric approach to targeted password guessing that addresses a previously overlooked password reuse behavior: semantically similar password creation (Type 3). While prior work focused on structural modifications (Type 1: "shark0301" to "shark03") and popular password selection (Type 2: "shark0301" to "loveyouforever"), KPG captures cases where users create passwords based on partial semantic patterns (Type 3: "shark0301" to "bear1" -- where "bear" derives semantically from "shark").

The system combines a TransGuess transformer-based sequence-to-sequence model with a k-nearest neighbor data store to interpolate three distributions during password generation. Evaluated across 4.8 billion passwords from 12 datasets spanning 30 attack scenarios, KPG achieves 8.52% to 27.66% higher success rates within 100 guesses compared to prior targeted password guessing models, with the strongest improvements in capturing Type 3 semantic reuse patterns.

Background

▶ Watch: Three types of password reuse behavior defined (0:00)

Text passwords remain the most prevalent authentication method due to their simplicity, ease of change, and low deployment cost. However, research consistently shows that 21-33% of users slightly modify existing passwords when creating new ones, and 20-59% of users directly reuse passwords across services. This password reuse behavior creates a significant threat: once attackers obtain credentials leaked from one service, they can exploit reuse patterns to compromise other accounts through credential stuffing attacks.

Recent large-scale data breaches have provided attackers with ample material for credential stuffing. The attacker's core objective is to simulate user password reuse behavior -- given a known leaked password (the "source password"), predict the user's passwords on other services (the "target passwords").

Prior work classified password reuse into two types: Type 1 (structural modifications where the new password is visibly similar to the source) and Type 2 (switching to a popular password). This research identifies Type 3 -- semantic similarity where passwords appear dissimilar at the character level but share underlying semantic patterns -- and develops methods to exploit it.

Key Findings

▶ Watch: TransGuess transformer model and improved popular password mixing (4:00)

Type 3 password reuse is a real and exploitable behavior. Users create passwords based on partial semantic patterns of their existing passwords, producing credentials that appear dissimilar at the character level but are intrinsically related. Example: "shark0301" to "bear1" (both animals, related semantic field).

KPG achieves 8.52-27.66% higher success rates within 100 guesses. Across 30 attack scenarios on 12 datasets (4.8 billion passwords), KPG consistently outperforms prior targeted password guessing models.

New popular password mixing method improves Type 2 capture by 9.21%. Rather than assuming equal probability of choosing any popular password regardless of source, KPG calculates the distance between source and popular passwords in high-dimensional space, weighting popular password probability by similarity to the source.

KPG captures the most Type 3 reuse pairs. Comparison of the proportion and number of password pairs correctly guessed shows KPG achieves the highest coverage of Type 3 semantically-related pairs, validating the k-nearest neighbor approach for capturing semantic reuse.

KPG also improves Type 1 and Type 2 capture. Despite being designed primarily for Type 3, the interpolation approach also produces higher numbers of correctly guessed Type 1 and Type 2 passwords compared to other models.

Technical Deep Dive

▶ Watch: KPG: k-nearest neighbor data store for semantic reuse capture (6:00)

KPG's architecture combines three components through distribution interpolation:

TransGuess (Base Model): A transformer-based sequence-to-sequence model that takes a source password as input and generates target password variations character by character. Training data is filtered using cosine similarity > 0.3 to focus on Type 1 structural modifications. This produces the basic code distribution for each decoding step.

k-Nearest Neighbor Data Store: A data store mapping context vectors (source password + target prefix representations) to the next correct character. At each decoding step, the model:

1. Computes a high-dimensional representation of the current state
2. Retrieves the k nearest neighbors from the data store
3. Applies three operations to produce the KNN distribution

The key insight: when two password pairs follow similar transformation patterns, their vector representations in latent space will be close -- even if the passwords appear dissimilar at the character level. This is how Type 3 semantic similarity is captured without explicit semantic analysis.

Local Distribution: The last segment of generated tokens serves as mask tokens, input to a secondary retrieval to obtain a local distribution that captures fine-grained structural patterns.

Interpolation: The final character prediction at each decoding step is an interpolation of three distributions:

• Basic code distribution (captures Type 1 structural reuse)
• KNN distribution (captures Type 3 semantic reuse)
• Local distribution (captures fine-grained Type 1 patterns)

Three parameters (lambda_basic, lambda_k, lambda_local, summing to 1) control the proportions.

Popular Password Mixing: Instead of uniform mixing, the probability of generating a popular password is weighted by its distance from the source password in high-dimensional space. Closer popular passwords have higher generation probability, better simulating how users choose popular passwords influenced by their existing password patterns.

Demo / Proof of Concept

▶ Watch: Results: 8.52-27.66% improvement across 30 attack scenarios (10:00)

The evaluation used 12 datasets from high-profile websites:

• 5 Chinese datasets
• 5 English datasets
• 2 mixed-language datasets
• Total: 4.8 billion passwords with leak dates ranging from 2012 to 2021

30 attack scenarios were evaluated, with specific filtering methods applied based on each website's characteristics. Within 100 guesses per target, KPG achieved success rates 8.52-27.66% higher than competing models. The Type 3 capture results showed the highest correct prediction of semantically-related password pairs compared to all baselines.

Defensive Implications

▶ Watch: Q&A: passkeys recommendation and Type 1 performance discussion (12:00)

This research demonstrates that password reuse attacks are becoming increasingly sophisticated, exploiting not just obvious structural similarities but subtle semantic relationships between passwords. The defensive implications include:

Password similarity checking should include semantic analysis. Current password strength meters and reuse detection focus on character-level similarity. The Type 3 reuse pattern shows that semantically related passwords (same category, related concepts) should also be flagged.

Credential stuffing defenses need updating. Rate limiting and CAPTCHA-based defenses assume attackers try many variations of known passwords. KPG's efficiency (higher success within 100 guesses) means attackers need fewer attempts to succeed, potentially staying under rate-limiting thresholds.

Passkey adoption reduces the entire attack surface. As noted in the Q&A, password-based authentication is fundamentally vulnerable to this class of attack. Passkeys and biometric authentication eliminate the password reuse problem entirely.

User education should address semantic reuse. Security awareness training typically warns against obvious password reuse and simple modifications. Users should also be warned that choosing related concepts (both animals, both sports, both foods) creates exploitable patterns.

Key Takeaways

• A third type of password reuse behavior identified: semantic similarity where passwords appear different but share underlying patterns (e.g., "shark0301" to "bear1")
• KPG uses k-nearest neighbor retrieval in latent space to capture semantic reuse patterns without explicit semantic analysis
• 8.52-27.66% higher success rates within 100 guesses compared to prior targeted password guessing models
• New popular password mixing method improves Type 2 capture by 9.21% by weighting probability based on source-password similarity
• Evaluated across 4.8 billion passwords from 12 datasets spanning 30 attack scenarios
• The interpolation of three distributions (basic, KNN, local) captures all three types of password reuse behavior simultaneously

About the Speaker(s)

Zhen Li (presented as "Journeyi") is a master's student at Nankai University. The research was independently conducted at Nankai University, focusing on password security, credential stuffing attacks, and machine learning-based password guessing models.