When your team selects a cryptographic primitive to protect cardholder data, you're choosing from a family of related constructions that share fundamental security properties. Understanding these relationships helps make defensible choices during QSA assessments and avoid redundant validation work.
This checklist guides you through evaluating cryptographic primitives for PCI DSS Requirement 3 (Protect Stored Cardholder Data) and Requirement 4 (Protect Cardholder Data with Strong Cryptography During Transmission Over Open, Public Networks), focusing on how circular-security properties affect your compliance posture.
Prerequisites
Before using this checklist, confirm:
- You've documented which systems store, process, or transmit Primary Account Numbers (PANs).
- Your cryptographic architecture diagram identifies where Data Encryption Keys (DEKs) and Key Encryption Keys (KEKs) are used.
- You know which NIST approved algorithms your current implementation uses (per PCI DSS Requirement 3.6.1).
- Your QSA has provided guidance on acceptable encryption methods for your environment.
Cryptographic Primitive Evaluation Checklist
1. Identify Your Security Model Requirements
Done when: You've documented whether your implementation requires resistance to key-dependent attacks.
If your system encrypts data that includes or derives from key material, you need primitives with circular-security properties. Standard encryption schemes don't guarantee security when the plaintext depends on the encryption key.
What good looks like: A one-page security model document that states: "Our tokenization vault encrypts tokens using keys derived from the PAN itself" or "Our P2PE implementation uses independent keys with no circular dependencies."
2. Map Your Primitives to Established Security Definitions
Done when: Each cryptographic component in your architecture maps to a specific security definition (IND-CPA, KDM-security, authenticated encryption).
PCI DSS requires "strong cryptography" but doesn't specify security models. Your QSA will ask how you know your implementation is secure. If you're using secret-key encryption where plaintext depends on keys, verify that your primitive satisfies key-dependent-message (KDM) security or an equivalent property.
What good looks like: Your System Security Plan includes a table: "AES-256-GCM (DEK encryption) → IND-CPA + authenticated encryption; HKDF key derivation → PRF security per NIST SP 800-108."
3. Verify Equivalence for Redundant Validations
Done when: You've eliminated duplicate cryptographic validations by recognizing equivalent primitives.
Research shows that KDM-secure secret-key encryption, certain pseudorandom generator constructions, and specific weak pseudorandom function variants provide equivalent security guarantees. If your QSA requires validation of multiple components, check whether they're existentially equivalent. You may consolidate testing.
What good looks like: During your assessment, you demonstrate that validating your KDM-secure encryption scheme covers the security properties your QSA was separately questioning about your key-derivation function, reducing your validation scope.
4. Assess Public-Key Encryption for Key Exchange
Done when: Your key exchange mechanisms have documented security properties beyond standard semantic security.
If your implementation uses public-key encryption for establishing session keys, verify whether the ciphertext or key-generation process depends on random values that later appear in plaintext. Standard PKE doesn't guarantee randomness-dependent-message (RDM) security. Newer constructions built on key-dependent-shift secure primitives do.
What good looks like: Your P2PE documentation states: "Data Encryption Key (DEK) establishment uses ECIES with independent randomness; no RDM concerns" or "We use [specific construction] which provides RDM security per [citation]."
5. Document Cryptographic Assumptions for Assessors
Done when: Your compliance documentation explicitly states which hardness assumptions your security relies on.
Your QSA doesn't need to understand the mathematics, but they need to verify you've made informed choices. If your implementation relies on circular-security properties, document the underlying assumption (for example, "Security reduces to the decisional Diffie-Hellman assumption under key-dependent messages").
What good looks like: A "Cryptographic Basis" section in your documentation that states: "Our vault encryption security relies on AES-256 satisfying KDM security, which is a standard assumption for AES when used with independent keys per NIST guidelines."
6. Validate FIPS 140-3 Module Compatibility
Done when: Your selected primitives are implementable within your FIPS 140-3 validated modules.
PCI DSS Requirement 3.6.1 requires FIPS 140-2 or higher for key management. Verify that primitives with circular-security properties can be constructed using approved algorithms within your Hardware Security Module (HSM) or software cryptographic module.
What good looks like: Confirmation from your HSM vendor: "KDM-secure encryption using AES-256-GCM with HKDF key derivation is supported within our FIPS 140-3 Level 3 validated boundary."
7. Review Key Hierarchy for Circular Dependencies
Done when: You've traced every key derivation path and confirmed no key encrypts data that was used to derive that key.
Draw your key hierarchy from KEKs down to DEKs. Mark any path where plaintext data influences key generation. These paths require primitives with circular-security properties.
What good looks like: A key hierarchy diagram with annotations: "DEK-1 encrypts PAN; DEK-1 derived from KEK-A using PAN as input → requires KDM-secure encryption" or "All keys derived from HSM root using independent entropy → no circular dependencies."
8. Test Segmentation Between Cryptographic Domains
Done when: You've verified that a compromise in one cryptographic domain doesn't cascade to others.
Even with circular-secure primitives, your architecture should limit blast radius. Confirm that your segmentation testing (PCI DSS Requirement 11.4.6) includes cryptographic isolation. A compromise of encryption keys in your tokenization vault shouldn't compromise your P2PE session keys.
What good looks like: Segmentation test results showing: "Simulated DEK compromise in CDE Zone A did not expose key material in CDE Zone B; cryptographic domains are properly isolated."
Common Mistakes
Assuming all NIST-approved algorithms provide equivalent security properties. AES-256 is approved for encryption, but that doesn't mean every use of AES-256 satisfies KDM security. The security property depends on how you use the primitive, not just which algorithm you chose.
Failing to document why you selected a specific construction. "We use AES because it's required" won't satisfy your QSA when they ask about circular-security scenarios. Document the specific security property you need and why your chosen primitive provides it.
Over-engineering for theoretical attacks that don't apply to your architecture. If your keys are truly independent and plaintext never depends on key material, you don't need KDM-secure encryption. Don't add complexity you don't need.
Treating cryptographic validation as a one-time exercise. When you update your encryption implementation, re-evaluate this checklist. A change to your key derivation function might introduce circular dependencies that weren't present before.
Next Steps
- Schedule a technical review with your QSA to walk through items 1-4 before your next assessment.
- If you identified circular dependencies in item 7, consult with your cryptographic module vendor about KDM-secure implementations.
- Update your System Security Plan to include the security model documentation from items 2 and 5.
- Add cryptographic domain isolation to your annual segmentation testing scope (item 8).
Your encryption choices cascade through your entire compliance program. Understanding the security properties of your primitives, not just their algorithm names, gives you confidence during assessments and reduces the risk of implementing cryptography that doesn't actually protect cardholder data under your specific usage patterns.
