You've configured bcrypt with a work factor of 12, migrated away from MD5, and enforced Multi-Factor Authentication (MFA). You assume your password hashing strategy is solid.
But when threat actors rent GPU farms or deploy custom ASICs, the assumptions behind traditional password-hardening functions start to crack. The myths below persist because they're rooted in older threat models, single-threaded attackers with limited resources. Today, parallel processing at scale is the reality, and the cryptographic methods protecting your customers' credentials need to match that reality.
Myth 1: "Memory-hard functions are all equally resistant to parallel attacks"
Reality: The model you evaluate against determines what you're actually protecting.
Dynamic pebbling models, used to analyze many memory-hard functions, assume attackers must process nodes in a specific graph sequentially. They're useful for proving lower bounds on computational cost but don't account for attackers who can parallelize oracle queries or exploit implementation-level optimizations.
The Parallel Random Oracle Model (PROM) represents a stronger adversary: one who can issue multiple hash queries simultaneously and potentially find shortcuts that pure graph analysis misses. A function proven secure in dynamic pebbling might still be vulnerable to PROM-based attacks. DEGSample, a data-dependent MHF, achieves sustained space complexity of Ω(N) for Ω(N) steps in the PROM, meaning an attacker with parallel processing capability still can't compress the memory footprint without incurring steep penalties.
When selecting a password hashing function for a payments platform or cardholder authentication system, ask which attack model the security proof assumes. If the proof relies solely on pebbling abstractions, you're not accounting for real-world parallel adversaries.
Myth 2: "Cumulative memory complexity is the only metric that matters"
Reality: Sustained space complexity tells you how long an attacker's memory stays above a threshold, and that duration matters as much as total memory consumption.
Cumulative memory complexity (CMC) measures total memory usage over time. It's a strong metric, but it doesn't distinguish between an attacker who uses 10 GB for one second versus one who sustains 1 GB for ten seconds.
Sustained space complexity (SSC) captures that duration. If your function forces an attacker to sustain Ω(N) memory for Ω(N) steps, you're extending the time window in which they're resource-constrained, even if they have access to parallel hardware. In the PROM, any attacker who doesn't sustain the required memory against DEGSample incurs a CMC penalty of at least Ω(N^2.5-ε). This creates a structural barrier that makes parallelization less effective.
For payment security engineers protecting high-value credentials, SSC ensures that even well-resourced attackers face time-based constraints, not just cost-based ones.
Myth 3: "Data-independent functions are always safer than data-dependent ones"
Reality: Data-dependent MHFs can offer stronger memory-hardness guarantees when you need resistance against parallel attacks.
Data-independent functions (like Argon2i) compute the same sequence of operations regardless of input, making them resistant to side-channel attacks via cache timing. That's critical in shared hosting environments or scenarios where an attacker can observe memory access patterns.
But data-dependent functions (like Argon2d or DEGSample) tie the computation graph to the input itself. An attacker can't precompute a generic strategy; they must process each password candidate individually. This property makes parallelization harder. The tradeoff: you're accepting some side-channel risk in exchange for stronger guarantees against brute-force attacks with parallel resources.
In high-risk environments, data-dependent MHFs can provide a stronger defense. You're not choosing "safer" in absolute terms; you're choosing the threat model you're optimizing against.
Myth 4: "If my function is sequential-time optimal, I'm protected"
Reality: Sequential efficiency doesn't constrain parallel attackers.
A function that computes in Θ(N) sequential time is efficient for legitimate users, but that doesn't mean an attacker with 1,000 cores faces Θ(N) time. If the function lacks strong SSC/CMC tradeoffs, a parallel adversary can distribute the workload and compress the effective time.
The goal isn't just sequential optimality. It's ensuring that any strategy to reduce sustained memory incurs a steep penalty in cumulative complexity. DEGSample's Ω(N^2.5-ε) CMC penalty in the PROM means that even if an attacker tries to parallelize aggressively, they pay a superlinear cost. That's the tradeoff you're enforcing: either sustain the memory or accept a multiplicative explosion in total work.
When evaluating password hashing for systems subject to PCI DSS Requirement 8.3.2, don't just verify that the algorithm is approved. Verify that the security proof accounts for parallel adversaries.
Myth 5: "Theoretical cryptographic improvements don't affect production systems"
Reality: The gap between theory and practice is narrowing faster than your threat model updates.
Five years ago, renting GPU clusters for password cracking was expensive and niche. Today, attackers lease compute capacity by the hour, deploy custom FPGAs, and share optimized cracking tools in underground forums. The adversary you're modeling isn't a hobbyist with a single workstation; it's an organized group with access to parallel processing infrastructure.
Functions like DEGSample introduce properties (ancestral robustness, fractional depth-robustness) that directly translate to resistance against these real-world attacks. Ancestral robustness ensures that even if an attacker tries to skip intermediate steps, the dependency structure forces them back into memory-intensive computation. Fractional depth-robustness guarantees that no shortcut through the computation graph reduces the sustained memory requirement without triggering the CMC penalty.
These aren't abstract properties. They're defenses against the attack techniques your adversaries are already using.
What to do instead
Start by auditing your current password hashing configuration. If you're using bcrypt or PBKDF2, you're relying on iteration count as your primary defense, and iteration count doesn't scale well against parallel attacks. Argon2 is a significant improvement, but verify which variant you're using (Argon2i, Argon2d, or Argon2id) and whether the memory parameter is set appropriately for your threat model.
For high-risk environments, evaluate whether data-dependent MHFs with proven PROM security offer a better tradeoff. You'll need to assess side-channel risk (can an attacker observe memory access patterns?) versus brute-force risk (can they parallelize across many cores?). In HSM-backed systems or air-gapped key derivation, the PROM guarantees matter more than cache-timing resistance.
Document the threat model you're defending against. If your risk assessment assumes attackers have access to parallel processing (and it should), your cryptographic choices need to reflect that. SSC/CMC tradeoffs aren't just theoretical curiosities; they're the mechanism that forces attackers to choose between memory exhaustion and computational explosion.
And when you're reviewing vendor claims about "military-grade encryption" or "unbreakable password security," ask which attack model their security proof assumes. If they can't answer, you're not buying security, you're buying marketing.
