home.social

#symmetriccryptography — Public Fediverse posts

Live and recent posts from across the Fediverse tagged #symmetriccryptography, aggregated by home.social.

  1. Soatok @[email protected] ·

    Key Transparency and the Right to be Forgotten

    This post is the first in a new series covering some of the reasoning behind decisions made in my project to build end-to-end encryption for direct messages on the Fediverse.

    (Collectively, Fedi-E2EE.)

    Although the reasons for specific design decisions should be immediately obvious from reading the relevant specification (and if not, I consider that a bug in the specification), I believe writing about it less formally will improve the clarity behind the specific design decisions taken.

    In the inaugural post for this series, I’d like to focus on how the Fedi-E2EE Public Key Directory specification aims to provide Key Transparency and an Authority-free PKI for the Fediverse without making GDPR compliance logically impossible.

    CMYKat‘s art, edited by me.

    Background

    Key Transparency

    For a clearer background, I recommend reading my blog post announcing the focused effort on a Public Key Directory, and then my update from August 2024.

    If you’re in a hurry, I’ll be brief:

    The goal of Key Transparency is to ensure everyone in a network sees the same view of who has which public key.

    How it accomplishes this is a little complicated: It involves Merkle trees, digital signatures, and a higher-level protocol of distinct actions that affect the state machine.

    If you’re thinking “blockchain”, you’re in the right ballpark, but we aren’t propping up a cryptocurrency. Instead, we’re using a centralized publisher model (per Public Key Directory instance) with decentralized verification.

    Add a bit of cross-signing and replication, and you can stitch together a robust network of Public Key Directories that can be queried to obtain the currently-trusted list of public keys (or other auxiliary data) for a given Fediverse user. This can then be used to build application-layer protocols (i.e., end-to-end encryption with an identity key more robust than “trust on first use” due to the built-in audit trail to Merkle trees).

    I’m handwaving a lot of details here. The Architecture and Specification documents are both worth a read if you’re curious to learn more.

    Harubaki

    Right To Be Forgotten

    I am not a lawyer, nor do I play one on TV. This is not legal advice. Other standard disclaimers go here.

    Okay, now that we’ve got that out of the way, Article 17 of the GDPR establishes a “Right to erasure” for Personal Data.

    What this actually means in practice has not been consistently decided by the courts yet. However, a publicly readable, immutable ledger that maps public keys (which may be considered Personal Data) with Actor IDs (which includes usernames, which are definitely Personal Data) goes against the grain when it comes to GDPR.

    It remains an open question of there is public interest in this data persisting in a read-only ledger ad infinitum, which could override the right to be forgotten. If there is, that’s for the courts to decide, not furry tech bloggers.

    I know it can be tempting, especially as an American with no presence in the European Union, to shrug and say, “That seems like a them problem.” However, if other folks want to be able to use my designs within the EU, I would be remiss to at least consider this potential pitfall and try to mitigate it in my designs.

    So that’s exactly what I did.

    AJ

    Almost Contradictory

    At first glance, the privacy goals of both Key Transparency and the GDPR’s Right To Erasure are at odds.

    • One creates an immutable, append-only history.
    • The other establishes a right for EU citizens’ history to be selectively censored, which means history has to be mutable.

    However, they’re not totally impossible to reconcile.

    An untested legal theory circulating around large American tech companies is that “crypto shredding” is legally equivalent to erasure.

    Crypto shredding is the act of storing encrypted data, and then when given a legal takedown request from an EU citizen, deleting the key instead of the data.

    AJ

    This works from a purely technical perspective: If the data is encrypted, and you don’t know the key, to you it’s indistinguishable from someone who encrypted the same number of NUL bytes.

    In fact, many security proofs for encryption schemes are satisfied by reaching this conclusion, so this isn’t a crazy notion.

    Is Crypto Shredding Plausible?

    In 2019, the European Parliamentary Research Service published a lengthy report titled Blockchain and the General Data Protection Regulation which states the following:

    Before any examination of whether blockchain technology is capable of complying with Article 17 GDPR; it must be underscored that the precise meaning of the term ‘erasure’ remains unclear.

    Article 17 GDPR does not define erasure, and the Regulation’s recitals are equally mum on how this term should be understood. It might be assumed that a common-sense understanding of this terminology ought to be embraced. According to the Oxford English Dictionary, erasure means ‘the removal or writing, recorded material, or data’ or ‘the removal of all traces of something: obliteration’.494

    From this perspective, erasure could be taken to equal destruction. It has, however, already been stressed that the destruction of data on blockchains, particularly these of a public and permissionless nature, is far from straightforward.

    There are, however, indications that the obligation inherent to Article 17 GDPR does not have to be interpreted as requiring the outright destruction of data. In Google Spain, the delisting of information from research results was considered to amount to erasure. It is important to note, however, that in this case, this is all that was requested of Google by the claimant, who did not have control over the original data source (an online newspaper publication). Had the claimant wished to obtain the outright destruction of the relevant data it would have had to address the newspaper, not Google. This may be taken as an indication that what the GDPR requires is that the obligation resting on data controllers is to do all they can to secure a result as close as possible to the destruction of their data within the limits of [their] own factual possibilities.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 75-76

    From this, we can kind of intuit that the courts aren’t pedantic: The cited Google Spain case was satisfied by merely delisting the content, not the erasure of the newspaper’s archives.

    The report goes on to say:

    As awareness regarding the tricky reconciliation between Article 17 GDPR and distributed ledgers grows, a number of technical alternatives to the outright destruction of data have been considered by various actors. An often-mentioned solution is that of the destruction of the private key, which would have the effect of making data encrypted with a public key inaccessible. This is indeed the solution that has been put forward by the French data protection authority CNIL in its guidance on blockchains and the GDPR. The CNIL has suggested that erasure could be obtained where the keyed hash function’s secret key is deleted together with information from other systems where it was stored for processing.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 76-77

    That said, I cannot locate a specific court decision that affirms that crypto erasure is legally sufficient for complying with data erasure requests (nor any that affirm that it’s necessary).

    I don’t have a crystal ball that can read the future on what government compliance will decide, nor am I an expert in legal matters.

    Given the absence of a clear legal framework, I do think it’s totally reasonable to consider crypto-shredding equivalent to data erasure. Most experts would probably agree with this. But it’s also possible that the courts could rule totally stupidly on this one day.

    Therefore, I must caution anyone that follows a similar path: Do not claim GDPR compliance just because you implement crypto-shredding in a distributed ledger. All you can realistically promise is that you’re not going out of your way to make compliance logically impossible. All we have to go by are untested legal hypotheses, and very little clarity (even if the technologists are near-unanimous on the topic!).

    Towards A Solution

    With all that in mind, let’s start with “crypto shredding” as the answer to the GDPR + transparency log conundrum.

    This is only the start of our complications.

    CMYKat

    Protocol Risks Introduced by Crypto Shredding

    Before the introduction of crypto shredding, the job of the Public Key Directory was simple:

    1. Receive a protocol message.
    2. Validate the protocol message.
    3. Commit the protocol message to a transparency log (in this case, Sigsum).
    4. Retrieve the protocol message whenever someone requests it to independently verify its inclusion.
    5. Miscellaneous other protocol things (cross-directory checkpoint commitment, replication, etc.).

    Point being: there was very little that the directory could do to be dishonest. If they lied about the contents of a record, it would invalidate the inclusion proofs of every successive record in the ledger.

    In order to make a given record crypto-shreddable without breaking the inclusion proofs for every record that follows, we need to commit to the ciphertext, not the plaintext. (And then, when a takedown request comes in, wipe the key.)

    Now, things are quite more interesting.

    Do you…

    • …Distribute the encryption key alongside the ciphertext and let independent third parties decrypt it on demand?

      …OR…

    • Decrypt the ciphertext and serve plaintext through the public API, keeping the encryption key private so that it may be shredded later?

    The first option seems simple, but runs into governance issues: How do you claim the data was crypto-shredded if countless individuals have a copy of the encryption key, and can therefore recover the plaintext from the ciphertext?

    I don’t think that would stand up in court.

    CMYKat

    Clearly, your best option is the second one.

    Okay, so how does an end user know that the ciphertext that was committed to the transparency ledger decrypts to the specific plaintext value served by the Public Key Directory? How do users know it’s not lying?

    Quick aside: This question is also relevant if you went with the first option and used a non-committing AEAD mode for the actual encryption scheme.

    In that scenario, a hostile nation state adversary could pressure a Public Key Directory to selectively give one decryption key to targeted users, and another to the rest of the Internet, in order to perform a targeted attack against citizens they’d rather didn’t have civil rights.

    My entire goal with introducing key transparency to my end-to-end encryption proposal is to prevent these sorts of attacks, not enable them.

    There are a lot of avenues we could explore here, but it’s always worth outlining the specific assumptions and security goals of any design before you start perusing the literature.

    AJ

    Assumptions

    This is just a list of things we assume are true, and do not need to prove for the sake of our discussion here today. The first two are legal assumptions; the remainder are cryptographic.

    Ask your lawyer if you want advice about the first two assumptions. Ask your cryptographer if you suspect any of the remaining assumptions are false.

    1. Crypto-shredding is a legally valid way to provide data erasure (as discussed above).
    2. EU courts will consider public keys to be Personal Data.
    3. The SHA-2 family of hash functions is secure (ignoring length-extension attacks, which won’t matter for how we’re using them).
    4. HMAC is a secure way to build a MAC algorithm out of a secure hash function.
    5. HKDF is a secure KDF if used correctly.
    6. AES is a secure 128-bit block cipher.
    7. Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.
    8. AES-CTR + HMAC-SHA2 can be turned into a secure AEAD mode, if done carefully.
    9. Ed25519 is a digital signature algorithm that provides strong security against existent forgery under a chosen-message attack (SUF-CMA).
    10. Argon2id is a secure, memory-hard password KDF, when used with reasonable parameters. (You’ll see why in a moment.)
    11. Sigsum is a secure mechanism for building a transparency log.

    This list isn’t exhaustive or formal, but should be sufficient for our purposes.

    Security Goals

    1. The protocol messages stored in the Public Key Directory are accompanied by a Merkle tree proof of inclusion. This makes it append-only with an immutable history.
    2. The Public Key Directory cannot behave dishonestly about the decrypted plaintext for a given ciphertext without clients detecting the deception.
    3. Whatever strategy we use to solve this should be resistant to economic precomputation and brute-force attacks.

    Can We Use Zero-Knowledge Proofs?

    At first, this seems like an ideal situation for a succinct, non-interactive zero-knowledge proof.

    After all, you’ve got some secret data that you hold, and you want to prove that a calculation is correct without revealing the data to the end user. This seems like the ideal setup for Schnorr’s identification protocol.

    CMYKat

    Unfortunately, the second assumption (public keys being considered Personal Data by courts, even though they’re derived from random secret keys) makes implementing a Zero-Knowledge Proof here very challenging.

    First, if you look at Ed25519 carefully, you’ll realize that it’s just a digital signature algorithm built atop a Schnorr proof, which requires some sort of public key (even an ephemeral one) to be managed.

    Worse, if you try to derive this value solely from public inputs (rather than creating a key management catch-22), the secret scalar your system derives at will have been calculated from the user’s Personal Data–which only strengthens a court’s argument that the public key is therefore personally identifiable.

    CMKat

    There may be a more exotic zero-knowledge proof scheme that might be appropriate for our needs, but I’m generally wary of fancy new cryptography.

    Here are two rules I live by in this context:

    1. If I can’t get the algorithms out of the crypto module for whatever programming language I find myself working with, it may as well not even exist.
      • Corollary: If libsodium bindings are available, that counts as “the crypto module” too.
    2. If a developer needs to reach for a generic Big Integer library (e.g., GMP) for any reason in the course of implementing a protocol, I do not trust their implementation.

    Unfortunately, a lot of zero-knowledge proof designs fail one or both of these rules in practice.

    (Sorry not sorry, homomorphic encryption enthusiasts! The real world hasn’t caught up to your ideas yet.)

    What About Verifiable Random Functions (VRFs)?

    It may be tempting to use VRFs (i.e., RFC 9381), but this runs into the same problem as zero-knowledge proofs: we’re assuming that an EU court would deem public keys Personal Data.

    But even if that assumption turns out false, the lifecycle of a protocol message looks like this:

    1. User wants to perform an action (e.g., AddKey).
    2. Their client software creates a plaintext protocol message.
    3. Their client software generates a random 256-bit key for each potentially-sensitive attribute, so it can be shredded later.
    4. Their client software encrypts each attribute of the protocol message.
    5. The ciphertext and keys are sent to the Public Key Directory.
    6. For each attribute, the Public Key Directory decrypts the ciphertext with the key, verifies the contents, and then stores both. The ciphertext is used to generate a commitment on Sigsum (signed by the Public Key Directory’s keypair).
    7. The Public Key Directory serves plaintext to requestors, but does not disclose the key.
    8. In the future, the end user can demand a legal takedown, which just wipes the key.

    Let’s assume I wanted to build a VRF out of Ed25519 (similar to what Signal does with VXEdDSA). Now I have a key management problem, which is pretty much what this project was meant to address in the first place.

    VRFs are really cool, and more projects should use them, but I don’t think they will help me.

    CMYKat

    Soatok’s Proposed Solution

    If you want to fully understand the nitty-gritty implementation details, I encourage you to read the current draft specification, plus the section describing the encryption algorithm, and finally the plaintext commitment algorithm.

    Now that we’ve established all that, I can begin to describe my approach to solving this problem.

    First, we will encrypt each attribute of a protocol message, as follows:

    • For subkey derivation, we use HKDF-HMAC-SHA512.
    • For encrypting the actual plaintext, we use AES-256-CTR.
    • For message authentication, we use HMAC-SHA512.
    • Additional associated data (AAD) is accepted and handled securely; i.e., we don’t use YOLO as a hash construction.

    This prevents an Invisible Salamander attack from being possible.

    This encryption is performed client-side, by each user, and the symmetric key for each attribute is shared with the Public Key Directory when publishing protocol messages.

    If they later issue a legal request for erasure, they can be sure that the key used to encrypt the data they previously published isn’t secretly the same key used by every other user’s records.

    They always know this because they selected the key, not the server. Furthermore, everyone can verify that the hash published to the Merkle tree matches a locally generated hash of the ciphertext they just emitted.

    This provides a mechanism to keep everyone honest. If anything goes wrong, it will be detected.

    Next, to prevent the server from being dishonest, we include a plaintext commitment hash, which is included as part of the AAD (alongside the attribute name).

    (Implementing crypto-shredding is straightforward: simply wipe the encryption keys for the attributes of the records in scope for the request.)

    If you’ve read this far, you’re probably wondering, “What exactly do you mean by plaintext commitment?”

    Art by Scruff.

    Plaintext Commitments

    The security of a plaintext commitment is attained by the Argon2id password hashing function.

    By using the Argon2id KDF, you can make an effective trapdoor that is easy to calculate if you know the plaintext, but economically infeasible to brute-force attack if you do not.

    However, you need to do a little more work to make it safe.

    Harubaki

    The details here matter a lot, so this section is unavoidably going to be a little dense.

    Pass the Salt?

    Argon2id expects both a password and a salt.

    If you eschew the salt (i.e., zero it out), you open the door to precomputation attacks (see also: rainbow tables) that would greatly weaken the security of this plaintext commitment scheme.

    You need a salt.

    If you generate the salt randomly, this commitment property isn’t guaranteed by the algorithm. It would be difficult, but probably not impossible, to find two salts (, ) such that .

    Deriving the salt from public inputs eliminates this flexibility.

    By itself, this reintroduces the risk of making salts totally deterministic, which reintroduces the risk of precomputation attacks (which motivated the salt in the first place).

    If you include the plaintext in this calculation, it could also create a crib that gives attackers a shortcut for bypassing the cost of password hashing.

    Furthermore, any two encryptions operations that act over the same plaintext would, without any additional design considerations, produce an identical value for the plaintext commitment.

    CMYKat

    Public Inputs for Salt Derivation

    The initial proposal included the plaintext value for Argon2 salt derivation, and published the salt and Argon2 output next to each other.

    Hacker News comex pointed out a flaw with this technique, so I’ve since revised how salts are selected to make them independent of the plaintext.

    The public inputs for the Argon2 salt are now:

    1. The version identifier prefix for the ciphertext blob.
    2. The 256-bit random value used as a KDF salt (also stored in the ciphertext blob).
    3. A recent Merkle tree root.
    4. The attribute name (prefixed by its length).

    These values are all hashed together with SHA-512, and then truncated to 128 bits (the length required by libsodium for Argon2 salts).

    This salt is not stored, but can deterministically be calculated from public information.

    Crisis Averted?

    This sure sounds like we’ve arrived at a solution, but let’s also consider another situation before we declare our job done.

    High-traffic Public Key Directories may have multiple users push a protocol message with the same recent Merkle root.

    This may happen if two or more users query the directory to obtain the latest Merkle root before either of them publish their updates.

    Later, if both of these users issue a legal takedown, someone might observe that the recent-merkle-root is the same for two messages, but their commitments differ.

    Is this enough leakage to distinguish plaintext records?

    In my earlier design, we needed to truncate the salt and rely on understanding the birthday bound to reason about its security. This is no longer the case, since each salt is randomized by the same random value used in key derivation.

    Choosing Other Parameters

    As mentioned a second ago, we set the output length of the Argon2id KDF to 32 bytes (256 bits). We expect the security of this KDF to exceed , which to most users might as well be infinity.

    With apologies to Filippo.

    The other Argon2id parameters are a bit hand-wavey. Although the general recommendation for Argon2id is to use as much memory as possible, this code will inevitably run in some low-memory environments, so asking for several gigabytes isn’t reasonable.

    For the first draft, I settled on 16 MiB of memory, 3 iterations, and a parallelism degree of 1 (for widespread platform support).

    Plaintext Commitment Algorithm

    With all that figured out, our plaintext commitment algorithm looks something like this:

    1. Calculate the SHA512 hash of:
      • A domain separation constant
      • The header prefix (stored in the ciphertext)
      • The randomness used for key-splitting in encryption (stored in the ciphertext)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
    2. Truncate this hash to the rightmost 16 bytes (128 bits). This is the salt.
    3. Calculate Argon2id over the following inputs concatenated in this order, with an output length of 32 bytes (256 bits), using the salt from step 2:
      • Recent Merle Root Length (64-bit unsigned integer)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
      • Plaintext Length (64-bit unsigned integer)
      • Plaintext

    The output (step 3) is included as the AAD in the attribute encryption step, so the authentication tag is calculated over both the randomness and the commitment.

    To verify a commitment (which is extractable from the ciphertext), simply recalculate the commitment you expect (using the recent Merkle root specified by the record), and compare the two in constant-time.

    If they match, then you know the plaintext you’re seeing is the correct value for the ciphertext value that was committed to the Merkle tree.

    If the encryption key is shredded in the future, an attacker without knowledge of the plaintext will have an enormous uphill battle recovering it from the KDF output (and the salt will prove to be somewhat useless as a crib).

    AJ

    Caveats and Limitations

    Although this design does satisfy the specific criteria we’ve established, an attacker that already knows the correct plaintext can confirm that a specific record matches it via the plaintext commitment.

    This cannot be avoided: If we are to publish a commitment of the plaintext, someone with the plaintext can always confirm the commitment after the fact.

    CMYKat

    Whether this matters at all to the courts is a question for which I cannot offer any insight.

    Remember, we don’t even know if any of this is actually necessary, or if “moderation and platform safety” is a sufficient reason to sidestep the right to erasure.

    If the courts ever clarify this adequately, we can simply publish the mapping of Actor IDs to public keys and auxiliary data without any crypto-shredding at all.

    Trying to attack it from the other direction (download a crypto-shredded record and try to recover the plaintext without knowing it ahead of time) is attack angle we’re interested in.

    Herd Immunity for the Forgotten

    Another interesting implication that might not be obvious: The more Fediverse servers and users publish to a single Public Key Directory, the greater the anonymity pool available to each of them.

    Consider the case where a user has erased their previous Fediverse account and used the GDPR to also crypto-shred the Public Key Directory entries containing their old Actor ID.

    To guess the correct plaintext, you must not only brute-force guessing possible usernames, but also permute your guesses across all of the instances in scope.

    The more instances there are, the higher the cost of the attack.

    CMYKat

    Recap

    I tasked myself with designing a Key Transparency solution that doesn’t make complying with Article 17 of the GDPR nigh-impossible. To that end, crypto-shredding seemed like the only viable way forward.

    A serialized record containing ciphertext for each sensitive attribute would be committed to the Merkle tree. The directory would store the key locally and serve plaintext until a legal takedown was requested by the user who owns the data. Afterwards, the stored ciphertext committed to the Merkle tree is indistinguishable from random for any party that doesn’t already know the plaintext value.

    I didn’t want to allow Public Key Directories to lie about the plaintext for a given ciphertext, given that they know the key and the requestor doesn’t.

    After considering zero-knowledge proofs and finding them to not be a perfect fit, I settled on designing a plaintext commitment scheme based on the Argon2id password KDF. The KDF salts can be calculated from public inputs.

    Altogether, this meets the requirements of enabling crypto-shredding while keeping the Public Key Directory honest. All known attacks for this design are prohibitively expensive for any terrestrial threat actors.

    As an added bonus, I didn’t introduce anything fancy. You can build all of this with the cryptography available to your favorite programming language today.

    CMYKat

    Closing Thoughts

    If you’ve made it this far without being horribly confused, you’ve successfully followed my thought process for developing message attribute shreddability in my Public Key Directory specification.

    This is just one component of the overall design proposal, but one that I thought my readers would enjoy exploring in greater detail than the specification needed to capture.

    Header art: Harubaki, CMYKat.

    (This post was updated on 2024-11-22 to replace the incorrect term “PII” with “personal data”. Apologies for the confusion!)

    #Argon2 #crypto #cryptography #E2EE #encryption #FederatedPKI #fediverse #passwordHashing #symmetricCryptography

    #argon2 #crypto #cryptography #e2ee #encryption #federatedpki
  2. Soatok @[email protected] ·

    Key Transparency and the Right to be Forgotten

    This post is the first in a new series covering some of the reasoning behind decisions made in my project to build end-to-end encryption for direct messages on the Fediverse.

    (Collectively, Fedi-E2EE.)

    Although the reasons for specific design decisions should be immediately obvious from reading the relevant specification (and if not, I consider that a bug in the specification), I believe writing about it less formally will improve the clarity behind the specific design decisions taken.

    In the inaugural post for this series, I’d like to focus on how the Fedi-E2EE Public Key Directory specification aims to provide Key Transparency and an Authority-free PKI for the Fediverse without making GDPR compliance logically impossible.

    CMYKat‘s art, edited by me.

    Background

    Key Transparency

    For a clearer background, I recommend reading my blog post announcing the focused effort on a Public Key Directory, and then my update from August 2024.

    If you’re in a hurry, I’ll be brief:

    The goal of Key Transparency is to ensure everyone in a network sees the same view of who has which public key.

    How it accomplishes this is a little complicated: It involves Merkle trees, digital signatures, and a higher-level protocol of distinct actions that affect the state machine.

    If you’re thinking “blockchain”, you’re in the right ballpark, but we aren’t propping up a cryptocurrency. Instead, we’re using a centralized publisher model (per Public Key Directory instance) with decentralized verification.

    Add a bit of cross-signing and replication, and you can stitch together a robust network of Public Key Directories that can be queried to obtain the currently-trusted list of public keys (or other auxiliary data) for a given Fediverse user. This can then be used to build application-layer protocols (i.e., end-to-end encryption with an identity key more robust than “trust on first use” due to the built-in audit trail to Merkle trees).

    I’m handwaving a lot of details here. The Architecture and Specification documents are both worth a read if you’re curious to learn more.

    Right To Be Forgotten

    I am not a lawyer, nor do I play one on TV. This is not legal advice. Other standard disclaimers go here.

    Okay, now that we’ve got that out of the way, Article 17 of the GDPR establishes a “Right to erasure” for Personally Identifiable Information (PII).

    What this actually means in practice has not been consistently decided by the courts yet. However, a publicly readable, immutable ledger that maps public keys (which may be considered PII) with Actor IDs (which includes usernames, which are definitely PII) goes against the grain when it comes to GDPR.

    It remains an open question of there is public interest in this data persisting in a read-only ledger ad infinitum, which could override the right to be forgotten. If there is, that’s for the courts to decide, not furry tech bloggers.

    I know it can be tempting, especially as an American with no presence in the European Union, to shrug and say, “That seems like a them problem.” However, if other folks want to be able to use my designs within the EU, I would be remiss to at least consider this potential pitfall and try to mitigate it in my designs.

    So that’s is what I did.

    Almost Contradictory

    At first glance, the privacy goals of both Key Transparency and the GDPR’s Right To Erasure are at odds.

    • One creates an immutable, append-only history.
    • The other establishes a right for EU citizens’ history to be selectively censored, which means history has to be mutable.

    However, they’re not totally impossible to reconcile.

    An untested legal theory circulating around large American tech companies is that “crypto shredding” is legally equivalent to erasure.

    Crypto shredding is the act of storing encrypted data, and then when given a legal takedown request from an EU citizen, deleting the key instead of the data.

    This works from a purely technical perspective: If the data is encrypted, and you don’t know the key, to you it’s indistinguishable from someone who encrypted the same number of NUL bytes. In fact, many security proofs for encryption schemes are satisfied by reaching this conclusion, so this isn’t a crazy notion.

    Is Crypto Shredding Plausible?

    In 2019, the European Parliamentary Research Service published a lengthy report titled Blockchain and the General Data Protection Regulation which states the following:

    Before any examination of whether blockchain technology is capable of complying with Article 17 GDPR; it must be underscored that the precise meaning of the term ‘erasure’ remains unclear.

    Article 17 GDPR does not define erasure, and the Regulation’s recitals are equally mum on how this term should be understood. It might be assumed that a common-sense understanding of this terminology ought to be embraced. According to the Oxford English Dictionary, erasure means ‘the removal or writing, recorded material, or data’ or ‘the removal of all traces of something: obliteration’.494

    From this perspective, erasure could be taken to equal destruction. It has, however, already been stressed that the destruction of data on blockchains, particularly these of a public and permissionless nature, is far from straightforward.

    There are, however, indications that the obligation inherent to Article 17 GDPR does not have to be interpreted as requiring the outright destruction of data. In Google Spain, the delisting of information from research results was considered to amount to erasure. It is important to note, however, that in this case, this is all that was requested of Google by the claimant, who did not have control over the original data source (an online newspaper publication). Had the claimant wished to obtain the outright destruction of the relevant data it would have had to address the newspaper, not Google. This may be taken as an indication that what the GDPR requires is that the obligation resting on data controllers is to do all they can to secure a result as close as possible to the destruction of their data within the limits of [their] own factual possibilities.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 75-76

    From this, we can kind of intuit that the courts aren’t pedantic: The cited Google Spain case was satisfied by merely delisting the content, not the erasure of the newspaper’s archives.

    The report goes on to say:

    As awareness regarding the tricky reconciliation between Article 17 GDPR and distributed ledgers grows, a number of technical alternatives to the outright destruction of data have been considered by various actors. An often-mentioned solution is that of the destruction of the private key, which would have the effect of making data encrypted with a public key inaccessible. This is indeed the solution that has been put forward by the French data protection authority CNIL in its guidance on blockchains and the GDPR. The CNIL has suggested that erasure could be obtained where the keyed hash function’s secret key is deleted together with information from other systems where it was stored for processing.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 76-77

    That said, I cannot locate a specific court decision that affirms that crypto erasure is legally sufficient for complying with data erasure requests (nor any that affirm that it’s necessary).

    I don’t have a crystal ball that can read the future on what government compliance will decide, nor am I an expert in legal matters.

    Given the absence of a clear legal framework, I do think it’s totally reasonable to consider crypto-shredding equivalent to data erasure. Most experts would probably agree with this. But it’s also possible that the courts could rule totally stupidly on this one day.

    Therefore, I must caution anyone that follows a similar path: Do not claim GDPR compliance just because you implement crypto-shredding in a distributed ledger. All you can realistically promise is that you’re not going out of your way to make compliance logically impossible. All we have to go by are untested legal hypotheses, and very little clarity (even if the technologists are near-unanimous on the topic!).

    Towards A Solution

    With all that in mind, let’s start with “crypto shredding” as the answer to the GDPR + transparency log conundrum.

    This is only the start of our complications.

    CMYKat

    Protocol Risks Introduced by Crypto Shredding

    Before the introduction of crypto shredding, the job of the Public Key Directory was simple:

    1. Receive a protocol message.
    2. Validate the protocol message.
    3. Commit the protocol message to a transparency log (in this case, Sigsum).
    4. Retrieve the protocol message whenever someone requests it to independently verify its inclusion.
    5. Miscellaneous other protocol things (cross-directory checkpoint commitment, replication, etc.).

    Point being: there was very little that the directory could do to be dishonest. If they lied about the contents of a record, it would invalidate the inclusion proofs of every successive record in the ledger.

    In order to make a given record crypto-shreddable without breaking the inclusion proofs for every record that follows, we need to commit to the ciphertext, not the plaintext. (And then, when a takedown request comes in, wipe the key.)

    Now, things are quite more interesting.

    Do you…

    • …Distribute the encryption key alongside the ciphertext and let independent third parties decrypt it on demand?

      …OR…

    • Decrypt the ciphertext and serve plaintext through the public API, keeping the encryption key private so that it may be shredded later?

    The first option seems simple, but runs into governance issues: How do you claim the data was crypto-shredded if countless individuals have a copy of the encryption key, and can therefore recover the plaintext from the ciphertext?

    Your best option is the second one, clearly.

    Okay, so how does an end user know that the ciphertext that was committed to the transparency ledger decrypts to the specific plaintext value served by the Public Key Directory? How do users know it’s not lying?

    Quick aside: This question is also relevant if you went with the first option and used a non-committing AEAD mode for the actual encryption scheme.

    In that scenario, a hostile nation state adversary could pressure a Public Key Directory to selectively give one decryption key to targeted users, and another to the rest of the Internet, in order to perform a targeted attack against citizens they’d rather didn’t have civil rights.

    My entire goal with introducing key transparency to my end-to-end encryption proposal is to prevent these sorts of attacks, not enable them.

    There are a lot of avenues we could explore here, but it’s always worth outlining the specific assumptions and security goals of any design before you start perusing the literature.

    Assumptions

    This is just a list of things we assume are true, and do not need to prove for the sake of our discussion here today. The first two are legal assumptions; the remainder are cryptographic.

    Ask your lawyer if you want advice about the first two assumptions. Ask your cryptographer if you suspect any of the remaining assumptions are false.

    1. Crypto-shredding is a legally valid way to provide data erasure (as discussed above).
    2. EU courts will consider public keys to be PII.
    3. The SHA-2 family of hash functions is secure (ignoring length-extension attacks, which won’t matter for how we’re using them).
    4. HMAC is a secure way to build a MAC algorithm out of a secure hash function.
    5. HKDF is a secure KDF if used correctly.
    6. AES is a secure 128-bit block cipher.
    7. Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.
    8. AES-CTR + HMAC-SHA2 can be turned into a secure AEAD mode, if done carefully.
    9. Ed25519 is a digital signature algorithm that provides strong security against existent forgery under a chosen-message attack (SUF-CMA).
    10. Argon2id is a secure, memory-hard password KDF, when used with reasonable parameters. (You’ll see why in a moment.)
    11. Sigsum is a secure mechanism for building a transparency log.

    This list isn’t exhaustive or formal, but should be sufficient for our purposes.

    Security Goals

    1. The protocol messages stored in the Public Key Directory are accompanied by a Merkle tree proof of inclusion. This makes it append-only with an immutable history.
    2. The Public Key Directory cannot behave dishonestly about the decrypted plaintext for a given ciphertext without clients detecting the deception.
    3. Whatever strategy we use to solve this should be resistant to economic precomputation and brute-force attacks.

    Can We Use Zero-Knowledge Proofs?

    At first, this seems like an ideal situation for a succinct, non-interactive zero-knowledge proof.

    After all, you’ve got some secret data that you hold, and you want to prove that a calculation is correct without revealing the data to the end user. This seems like the ideal setup for Schnorr’s identification protocol.

    Unfortunately, the second assumption (public keys being considered PII by courts, even though they’re derived from random secret keys) makes implementing a Zero-Knowledge Proof here very challenging.

    First, if you look at Ed25519 carefully, you’ll realize that it’s just a digital signature algorithm built atop a Schnorr proof, which requires some sort of public key (even an ephemeral one) to be managed.

    Worse, if you try to derive this value solely from public inputs (rather than creating a key management catch-22), the secret scalar your system derives at will have been calculated from the user’s PII–which only strengthens a court’s argument that the public key is therefore personally identifiable.

    There may be a more exotic zero-knowledge proof scheme that might be appropriate for our needs, but I’m generally wary of fancy new cryptography.

    Here are two rules I live by in this context:

    1. If I can’t get the algorithms out of the crypto module for whatever programming language I find myself working with, it may as well not even exist.
      • Corollary: If libsodium bindings are available, that counts as “the crypto module” too.
    2. If a developer needs to reach for a generic Big Integer library (e.g., GMP) for any reason in the course of implementing a protocol, I do not trust their implementation.

    Unfortunately, a lot of zero-knowledge proof designs fail one or both of these rules in practice.

    (Sorry not sorry, homomorphic encryption enthusiasts! The real world hasn’t caught up to your ideas yet.)

    Soatok’s Proposed Solution

    If you want to fully understand the nitty-gritty implementation details, I encourage you to read the current draft specification, plus the section describing the encryption algorithm, and finally the plaintext commitment algorithm.

    Now that we’ve established all that, I can begin to describe my approach to solving this problem.

    First, we will encrypt each attribute of a protocol message, as follows:

    • For subkey derivation, we use HKDF-HMAC-SHA512.
    • For encrypting the actual plaintext, we use AES-256-CTR.
    • For message authentication, we use HMAC-SHA512.
    • Additional associated data (AAD) is accepted and handled securely; i.e., we don’t use YOLO as a hash construction.

    This prevents an Invisible Salamander attack from being possible.

    Next, to prevent the server from being dishonest, we include a plaintext commitment hash, which is included as part of the AAD (alongside the attribute name).

    (Implementing crypto-shredding is straightforward: simply wipe the encryption keys for the attributes of the records in scope for the request.)

    If you’ve read this far, you’re probably wondering, “What exactly do you mean by plaintext commitment?”

    Plaintext Commitments

    The security of a plaintext commitment is attained by the Argon2id password hashing function.

    By using the Argon2id KDF, you can make an effective trapdoor that is easy to calculate if you know the plaintext, but economically infeasible to brute-force attack if you do not.

    However, you need to do a little more work to make it safe.

    Pass the Salt?

    Argon2id expects both a password and a salt.

    If you eschew the salt (i.e., zero it out), you open the door to precomputation attacks (see also: rainbow tables) that would greatly weaken the security of this plaintext commitment scheme.

    You need a salt.

    If you generate the salt randomly, this commitment property isn’t guaranteed by the algorithm. It would be difficult, but probably not impossible, to find two salts (, ) such that .

    I’m handwaving the fact that the salts are stored for now.

    Deriving the salt from public inputs eliminates this flexibility.

    By itself, this reintroduces the risk of making salts totally deterministic, which reintroduces the risk of precomputation attacks (which motivated the salt in the first place).

    Furthermore, any two encryptions operations that act over the same plaintext would, without any additional design considerations, produce an identical value for the salt, which would lead to an identical plaintext commitment.

    Getting to the Root of the Problem

    The scheme I’m designing, which encrypts the attributes of protocol messages and includes a commitment of the plaintext, doesn’t exist in a vacuum.

    In my system, there is one additional public input we can use to increase the quality of the salt distribution (to resist precomputation) without introducing variability (to ensure the commitment is robust): A recent Merkle tree root.

    Since every protocol message accepted by a Public Key Directory will have a distinct Merkle root, a high-traffic Public Key Directory will produce a high-entropy root hash every time a user issues a new protocol message. This is especially true if, when issuing multiple successive messages, they use the root of their previous accepted Merkle root as the “recent” root when calculating their next plaintext commitment.

    Given that Sigsum uses SHA256, there are possible Merkle roots to choose from.

    Crisis Averted?

    This sure sounds like a solution, but let’s also consider another situation.

    High-traffic Public Key Directories may have multiple users push a protocol message with the same recent Merkle root.

    Later, if both of these users issue a legal takedown, someone might observe that the recent-merkle-root is the same for two messages, but their salts differ.

    Is this enough leakage to distinguish plaintext records?

    After pondering this for a bit, I decided this was a stupid problem to have, and reached for an oft-ignored tool in a cryptographer’s toolkit (except for modern hash function designers): Truncation.

    If we truncate the salt to a smaller value, we can increase the chance of a birthday collision.

    We do need to be careful: Too small, and we improve the economics of precomputation. Too large, and we risk creating a reliably crib for distinct plaintext values.

    How Much is Too Much?

    Let’s revisit the birthday paradox.

    If you have a probability space of , you expect a 50% chance of a single collision after about samples.

    More interesting, you have a probability of a collision after about samples.

    Given that I’m designing this project for the Fediverse, which has millions of accounts (and of which more than 100,000 can reasonably be considered “active”), I posit that a probability space of is sufficient for the Argon2id salt.

    Because salts are expected to be 128 bits (at least with libsodium), we fix the other bytes to a protocol-specific constant, which contains some version information that can be changed in future iterations. This won’t be on the final exam.

    Why ?

    Simply put: we want salts to collide (albeit somewhat rarely).

    Since the salt derivation algorithm is a faster hash than a KDF, collisions make it less useful for attackers hoping for a reliable plaintext crib.

    With 48 bits left after truncation, a 50% collision probability is reached after samples (a little over 16 million). The optimal birthday bound is reached after samples (65,536).

    How do you arrive at this number?

    Let’s assume, for the moment, that my proposal sees widespread adoption with Fediverse users.

    There are just under 11 million total, and 1 million monthly active, Fediverse users as of this writing. BlueSky just hit 20 million users.

    These numbers are in the to range. (For comparison, Twitter boasted over half a billion users earlier this year, which rounds up to .)

    It is therefore expected that at least one pair of distinct plaintext Actor IDs, using two different recent Merkle roots, would produce the same salt for their plaintext commitment.

    This gives attackers a disadvantage, since collisions make the salt (derived from a fast hash) useless, thereby forcing them to attack the KDF output instead.

    Conversely, breaking the KDF output with precomputation strategies would still involve different salts for each possible plaintext.

    This rounds off to about 9 petabytes of storage just for a 48-bit salt and a 208-bit Argon2id KDF output (for a total of 32 bytes).

    Choosing Other Parameters

    As mentioned a second ago, we set the output length of the Argon2id KDF to 26 bytes (208 bits). We expect the security of this KDF to exceed . This allows us to concatenate the salt and KDF output for a total of 256 bits, which keeps the total commitment size reasonable.

    The other Argon2id parameters are a bit hand-wavey. Although the general recommendation for Argon2id is to use as much memory as possible, this code will inevitably run in some low-memory environments, so asking for several gigabytes isn’t reasonable.

    For the first draft, I settled on 16 MiB of memory, 3 iterations, and a parallelism degree of 1 (for widespread platform support).

    Plaintext Commitment Algorithm

    With all that figured out, our plaintext commitment algorithm looks something like this:

    1. Calculate the HMAC-SHA512 hash (whose key is constant for domain separation) of:
      • Recent Merle Root Lengh (64-bit unsigned integer)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
      • Plaintext Length (64-bit unsigned integer)
      • Plaintext
    2. Truncate this hash to the rightmost 6 bytes (48 bits).
    3. Calculate Argon2id with the salt set to the ASCII string FE2EEPKDv1 followed by the truncated hash (step 2), with an output length of 26 bytes (208 bits).
    4. Concatenate the output steps 2 and 3.

    The output (step 4) is included as the AAD in the attribute encryption step.

    To verify a commitment (which is extractable from the ciphertext), simply recalculate the commitment you expect (using the recent Merkle root specified by the record), and compare the two in constant-time.

    If they match, then you know the plaintext you’re seeing is the correct value for the ciphertext value that was committed to the Merkle tree.

    If the encryption key is shredded in the future, an attacker without knowledge of the plaintext will have an enormous uphill battle recovering it from the KDF output (and the salt will prove to be somewhat useless as a crib).

    AJ

    Recap

    I tasked myself with designing a Key Transparency solution that doesn’t make complying with Article 17 of the GDPR nigh-impossible. To that end, crypto-shredding seemed like the only viable way forward.

    A serialized record containing ciphertext for each sensitive attribute would be committed to the Merkle tree. The directory would store the key locally and serve plaintext until a legal takedown was requested by the user who owns the data. Afterwards, the stored ciphertext committed to the Merkle tree is indistinguishable from random for any party that doesn’t already know the plaintext value.

    I didn’t want to allow Public Key Directories to lie about the plaintext for a given ciphertext, given that they know the key and the requestor doesn’t.

    After considering zero-knowledge proofs and finding them to not be a perfect fit, I settled on designing a plaintext commitment scheme based on the Argon2id password KDF, which uses a recent Merkle root to diversify the KDF salt selection, and truncates the result to make salt collisions likely (so anyone trying to attack the salt to guess plaintexts is at a disadvantage).

    Altogether, this meets the requirements of enabling crypto-shredding while keeping the Public Key Directory honest. All known attacks for this design are prohibitively expensive for any terrestrial threat actors.

    As an added bonus, I didn’t introduce anything fancy. You can build all of this with the cryptography available to your favorite programming language today.

    Closing Thoughts

    If you’ve made it this far without being horribly confused, you’ve successfully followed my thought process for developing message attribute shreddability in my Public Key Directory specification.

    This is just one component of the overall design proposal, but one that I thought my readers would enjoy exploring in greater detail than the specification needed to capture.

    Header art: Harubaki, CMYKat.

    #Argon2 #crypto #cryptography #E2EE #encryption #FederatedPKI #fediverse #passwordHashing #symmetricCryptography

    #argon2 #crypto #cryptography #e2ee #encryption #federatedpki
  3. Soatok @[email protected] ·

    Key Transparency and the Right to be Forgotten

    This post is the first in a new series covering some of the reasoning behind decisions made in my project to build end-to-end encryption for direct messages on the Fediverse.

    (Collectively, Fedi-E2EE.)

    Although the reasons for specific design decisions should be immediately obvious from reading the relevant specification (and if not, I consider that a bug in the specification), I believe writing about it less formally will improve the clarity behind the specific design decisions taken.

    In the inaugural post for this series, I’d like to focus on how the Fedi-E2EE Public Key Directory specification aims to provide Key Transparency and an Authority-free PKI for the Fediverse without making GDPR compliance logically impossible.

    CMYKat‘s art, edited by me.

    Background

    Key Transparency

    For a clearer background, I recommend reading my blog post announcing the focused effort on a Public Key Directory, and then my update from August 2024.

    If you’re in a hurry, I’ll be brief:

    The goal of Key Transparency is to ensure everyone in a network sees the same view of who has which public key.

    How it accomplishes this is a little complicated: It involves Merkle trees, digital signatures, and a higher-level protocol of distinct actions that affect the state machine.

    If you’re thinking “blockchain”, you’re in the right ballpark, but we aren’t propping up a cryptocurrency. Instead, we’re using a centralized publisher model (per Public Key Directory instance) with decentralized verification.

    Add a bit of cross-signing and replication, and you can stitch together a robust network of Public Key Directories that can be queried to obtain the currently-trusted list of public keys (or other auxiliary data) for a given Fediverse user. This can then be used to build application-layer protocols (i.e., end-to-end encryption with an identity key more robust than “trust on first use” due to the built-in audit trail to Merkle trees).

    I’m handwaving a lot of details here. The Architecture and Specification documents are both worth a read if you’re curious to learn more.

    Harubaki

    Right To Be Forgotten

    I am not a lawyer, nor do I play one on TV. This is not legal advice. Other standard disclaimers go here.

    Okay, now that we’ve got that out of the way, Article 17 of the GDPR establishes a “Right to erasure” for Personal Data.

    What this actually means in practice has not been consistently decided by the courts yet. However, a publicly readable, immutable ledger that maps public keys (which may be considered Personal Data) with Actor IDs (which includes usernames, which are definitely Personal Data) goes against the grain when it comes to GDPR.

    It remains an open question of there is public interest in this data persisting in a read-only ledger ad infinitum, which could override the right to be forgotten. If there is, that’s for the courts to decide, not furry tech bloggers.

    I know it can be tempting, especially as an American with no presence in the European Union, to shrug and say, “That seems like a them problem.” However, if other folks want to be able to use my designs within the EU, I would be remiss to at least consider this potential pitfall and try to mitigate it in my designs.

    So that’s exactly what I did.

    AJ

    Almost Contradictory

    At first glance, the privacy goals of both Key Transparency and the GDPR’s Right To Erasure are at odds.

    • One creates an immutable, append-only history.
    • The other establishes a right for EU citizens’ history to be selectively censored, which means history has to be mutable.

    However, they’re not totally impossible to reconcile.

    An untested legal theory circulating around large American tech companies is that “crypto shredding” is legally equivalent to erasure.

    Crypto shredding is the act of storing encrypted data, and then when given a legal takedown request from an EU citizen, deleting the key instead of the data.

    AJ

    This works from a purely technical perspective: If the data is encrypted, and you don’t know the key, to you it’s indistinguishable from someone who encrypted the same number of NUL bytes.

    In fact, many security proofs for encryption schemes are satisfied by reaching this conclusion, so this isn’t a crazy notion.

    Is Crypto Shredding Plausible?

    In 2019, the European Parliamentary Research Service published a lengthy report titled Blockchain and the General Data Protection Regulation which states the following:

    Before any examination of whether blockchain technology is capable of complying with Article 17 GDPR; it must be underscored that the precise meaning of the term ‘erasure’ remains unclear.

    Article 17 GDPR does not define erasure, and the Regulation’s recitals are equally mum on how this term should be understood. It might be assumed that a common-sense understanding of this terminology ought to be embraced. According to the Oxford English Dictionary, erasure means ‘the removal or writing, recorded material, or data’ or ‘the removal of all traces of something: obliteration’.494

    From this perspective, erasure could be taken to equal destruction. It has, however, already been stressed that the destruction of data on blockchains, particularly these of a public and permissionless nature, is far from straightforward.

    There are, however, indications that the obligation inherent to Article 17 GDPR does not have to be interpreted as requiring the outright destruction of data. In Google Spain, the delisting of information from research results was considered to amount to erasure. It is important to note, however, that in this case, this is all that was requested of Google by the claimant, who did not have control over the original data source (an online newspaper publication). Had the claimant wished to obtain the outright destruction of the relevant data it would have had to address the newspaper, not Google. This may be taken as an indication that what the GDPR requires is that the obligation resting on data controllers is to do all they can to secure a result as close as possible to the destruction of their data within the limits of [their] own factual possibilities.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 75-76

    From this, we can kind of intuit that the courts aren’t pedantic: The cited Google Spain case was satisfied by merely delisting the content, not the erasure of the newspaper’s archives.

    The report goes on to say:

    As awareness regarding the tricky reconciliation between Article 17 GDPR and distributed ledgers grows, a number of technical alternatives to the outright destruction of data have been considered by various actors. An often-mentioned solution is that of the destruction of the private key, which would have the effect of making data encrypted with a public key inaccessible. This is indeed the solution that has been put forward by the French data protection authority CNIL in its guidance on blockchains and the GDPR. The CNIL has suggested that erasure could be obtained where the keyed hash function’s secret key is deleted together with information from other systems where it was stored for processing.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 76-77

    That said, I cannot locate a specific court decision that affirms that crypto erasure is legally sufficient for complying with data erasure requests (nor any that affirm that it’s necessary).

    I don’t have a crystal ball that can read the future on what government compliance will decide, nor am I an expert in legal matters.

    Given the absence of a clear legal framework, I do think it’s totally reasonable to consider crypto-shredding equivalent to data erasure. Most experts would probably agree with this. But it’s also possible that the courts could rule totally stupidly on this one day.

    Therefore, I must caution anyone that follows a similar path: Do not claim GDPR compliance just because you implement crypto-shredding in a distributed ledger. All you can realistically promise is that you’re not going out of your way to make compliance logically impossible. All we have to go by are untested legal hypotheses, and very little clarity (even if the technologists are near-unanimous on the topic!).

    Towards A Solution

    With all that in mind, let’s start with “crypto shredding” as the answer to the GDPR + transparency log conundrum.

    This is only the start of our complications.

    CMYKat

    Protocol Risks Introduced by Crypto Shredding

    Before the introduction of crypto shredding, the job of the Public Key Directory was simple:

    1. Receive a protocol message.
    2. Validate the protocol message.
    3. Commit the protocol message to a transparency log (in this case, Sigsum).
    4. Retrieve the protocol message whenever someone requests it to independently verify its inclusion.
    5. Miscellaneous other protocol things (cross-directory checkpoint commitment, replication, etc.).

    Point being: there was very little that the directory could do to be dishonest. If they lied about the contents of a record, it would invalidate the inclusion proofs of every successive record in the ledger.

    In order to make a given record crypto-shreddable without breaking the inclusion proofs for every record that follows, we need to commit to the ciphertext, not the plaintext. (And then, when a takedown request comes in, wipe the key.)

    Now, things are quite more interesting.

    Do you…

    • …Distribute the encryption key alongside the ciphertext and let independent third parties decrypt it on demand?

      …OR…

    • Decrypt the ciphertext and serve plaintext through the public API, keeping the encryption key private so that it may be shredded later?

    The first option seems simple, but runs into governance issues: How do you claim the data was crypto-shredded if countless individuals have a copy of the encryption key, and can therefore recover the plaintext from the ciphertext?

    I don’t think that would stand up in court.

    CMYKat

    Clearly, your best option is the second one.

    Okay, so how does an end user know that the ciphertext that was committed to the transparency ledger decrypts to the specific plaintext value served by the Public Key Directory? How do users know it’s not lying?

    Quick aside: This question is also relevant if you went with the first option and used a non-committing AEAD mode for the actual encryption scheme.

    In that scenario, a hostile nation state adversary could pressure a Public Key Directory to selectively give one decryption key to targeted users, and another to the rest of the Internet, in order to perform a targeted attack against citizens they’d rather didn’t have civil rights.

    My entire goal with introducing key transparency to my end-to-end encryption proposal is to prevent these sorts of attacks, not enable them.

    There are a lot of avenues we could explore here, but it’s always worth outlining the specific assumptions and security goals of any design before you start perusing the literature.

    AJ

    Assumptions

    This is just a list of things we assume are true, and do not need to prove for the sake of our discussion here today. The first two are legal assumptions; the remainder are cryptographic.

    Ask your lawyer if you want advice about the first two assumptions. Ask your cryptographer if you suspect any of the remaining assumptions are false.

    1. Crypto-shredding is a legally valid way to provide data erasure (as discussed above).
    2. EU courts will consider public keys to be Personal Data.
    3. The SHA-2 family of hash functions is secure (ignoring length-extension attacks, which won’t matter for how we’re using them).
    4. HMAC is a secure way to build a MAC algorithm out of a secure hash function.
    5. HKDF is a secure KDF if used correctly.
    6. AES is a secure 128-bit block cipher.
    7. Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.
    8. AES-CTR + HMAC-SHA2 can be turned into a secure AEAD mode, if done carefully.
    9. Ed25519 is a digital signature algorithm that provides strong security against existent forgery under a chosen-message attack (SUF-CMA).
    10. Argon2id is a secure, memory-hard password KDF, when used with reasonable parameters. (You’ll see why in a moment.)
    11. Sigsum is a secure mechanism for building a transparency log.

    This list isn’t exhaustive or formal, but should be sufficient for our purposes.

    Security Goals

    1. The protocol messages stored in the Public Key Directory are accompanied by a Merkle tree proof of inclusion. This makes it append-only with an immutable history.
    2. The Public Key Directory cannot behave dishonestly about the decrypted plaintext for a given ciphertext without clients detecting the deception.
    3. Whatever strategy we use to solve this should be resistant to economic precomputation and brute-force attacks.

    Can We Use Zero-Knowledge Proofs?

    At first, this seems like an ideal situation for a succinct, non-interactive zero-knowledge proof.

    After all, you’ve got some secret data that you hold, and you want to prove that a calculation is correct without revealing the data to the end user. This seems like the ideal setup for Schnorr’s identification protocol.

    CMYKat

    Unfortunately, the second assumption (public keys being considered Personal Data by courts, even though they’re derived from random secret keys) makes implementing a Zero-Knowledge Proof here very challenging.

    First, if you look at Ed25519 carefully, you’ll realize that it’s just a digital signature algorithm built atop a Schnorr proof, which requires some sort of public key (even an ephemeral one) to be managed.

    Worse, if you try to derive this value solely from public inputs (rather than creating a key management catch-22), the secret scalar your system derives at will have been calculated from the user’s Personal Data–which only strengthens a court’s argument that the public key is therefore personally identifiable.

    CMKat

    There may be a more exotic zero-knowledge proof scheme that might be appropriate for our needs, but I’m generally wary of fancy new cryptography.

    Here are two rules I live by in this context:

    1. If I can’t get the algorithms out of the crypto module for whatever programming language I find myself working with, it may as well not even exist.
      • Corollary: If libsodium bindings are available, that counts as “the crypto module” too.
    2. If a developer needs to reach for a generic Big Integer library (e.g., GMP) for any reason in the course of implementing a protocol, I do not trust their implementation.

    Unfortunately, a lot of zero-knowledge proof designs fail one or both of these rules in practice.

    (Sorry not sorry, homomorphic encryption enthusiasts! The real world hasn’t caught up to your ideas yet.)

    What About Verifiable Random Functions (VRFs)?

    It may be tempting to use VRFs (i.e., RFC 9381), but this runs into the same problem as zero-knowledge proofs: we’re assuming that an EU court would deem public keys Personal Data.

    But even if that assumption turns out false, the lifecycle of a protocol message looks like this:

    1. User wants to perform an action (e.g., AddKey).
    2. Their client software creates a plaintext protocol message.
    3. Their client software generates a random 256-bit key for each potentially-sensitive attribute, so it can be shredded later.
    4. Their client software encrypts each attribute of the protocol message.
    5. The ciphertext and keys are sent to the Public Key Directory.
    6. For each attribute, the Public Key Directory decrypts the ciphertext with the key, verifies the contents, and then stores both. The ciphertext is used to generate a commitment on Sigsum (signed by the Public Key Directory’s keypair).
    7. The Public Key Directory serves plaintext to requestors, but does not disclose the key.
    8. In the future, the end user can demand a legal takedown, which just wipes the key.

    Let’s assume I wanted to build a VRF out of Ed25519 (similar to what Signal does with VXEdDSA). Now I have a key management problem, which is pretty much what this project was meant to address in the first place.

    VRFs are really cool, and more projects should use them, but I don’t think they will help me.

    CMYKat

    Soatok’s Proposed Solution

    If you want to fully understand the nitty-gritty implementation details, I encourage you to read the current draft specification, plus the section describing the encryption algorithm, and finally the plaintext commitment algorithm.

    Now that we’ve established all that, I can begin to describe my approach to solving this problem.

    First, we will encrypt each attribute of a protocol message, as follows:

    • For subkey derivation, we use HKDF-HMAC-SHA512.
    • For encrypting the actual plaintext, we use AES-256-CTR.
    • For message authentication, we use HMAC-SHA512.
    • Additional associated data (AAD) is accepted and handled securely; i.e., we don’t use YOLO as a hash construction.

    This prevents an Invisible Salamander attack from being possible.

    This encryption is performed client-side, by each user, and the symmetric key for each attribute is shared with the Public Key Directory when publishing protocol messages.

    If they later issue a legal request for erasure, they can be sure that the key used to encrypt the data they previously published isn’t secretly the same key used by every other user’s records.

    They always know this because they selected the key, not the server. Furthermore, everyone can verify that the hash published to the Merkle tree matches a locally generated hash of the ciphertext they just emitted.

    This provides a mechanism to keep everyone honest. If anything goes wrong, it will be detected.

    Next, to prevent the server from being dishonest, we include a plaintext commitment hash, which is included as part of the AAD (alongside the attribute name).

    (Implementing crypto-shredding is straightforward: simply wipe the encryption keys for the attributes of the records in scope for the request.)

    If you’ve read this far, you’re probably wondering, “What exactly do you mean by plaintext commitment?”

    Art by Scruff.

    Plaintext Commitments

    The security of a plaintext commitment is attained by the Argon2id password hashing function.

    By using the Argon2id KDF, you can make an effective trapdoor that is easy to calculate if you know the plaintext, but economically infeasible to brute-force attack if you do not.

    However, you need to do a little more work to make it safe.

    Harubaki

    The details here matter a lot, so this section is unavoidably going to be a little dense.

    Pass the Salt?

    Argon2id expects both a password and a salt.

    If you eschew the salt (i.e., zero it out), you open the door to precomputation attacks (see also: rainbow tables) that would greatly weaken the security of this plaintext commitment scheme.

    You need a salt.

    If you generate the salt randomly, this commitment property isn’t guaranteed by the algorithm. It would be difficult, but probably not impossible, to find two salts (, ) such that .

    Deriving the salt from public inputs eliminates this flexibility.

    By itself, this reintroduces the risk of making salts totally deterministic, which reintroduces the risk of precomputation attacks (which motivated the salt in the first place).

    If you include the plaintext in this calculation, it could also create a crib that gives attackers a shortcut for bypassing the cost of password hashing.

    Furthermore, any two encryptions operations that act over the same plaintext would, without any additional design considerations, produce an identical value for the plaintext commitment.

    CMYKat

    Public Inputs for Salt Derivation

    The initial proposal included the plaintext value for Argon2 salt derivation, and published the salt and Argon2 output next to each other.

    Hacker News comex pointed out a flaw with this technique, so I’ve since revised how salts are selected to make them independent of the plaintext.

    The public inputs for the Argon2 salt are now:

    1. The version identifier prefix for the ciphertext blob.
    2. The 256-bit random value used as a KDF salt (also stored in the ciphertext blob).
    3. A recent Merkle tree root.
    4. The attribute name (prefixed by its length).

    These values are all hashed together with SHA-512, and then truncated to 128 bits (the length required by libsodium for Argon2 salts).

    This salt is not stored, but can deterministically be calculated from public information.

    Crisis Averted?

    This sure sounds like we’ve arrived at a solution, but let’s also consider another situation before we declare our job done.

    High-traffic Public Key Directories may have multiple users push a protocol message with the same recent Merkle root.

    This may happen if two or more users query the directory to obtain the latest Merkle root before either of them publish their updates.

    Later, if both of these users issue a legal takedown, someone might observe that the recent-merkle-root is the same for two messages, but their commitments differ.

    Is this enough leakage to distinguish plaintext records?

    In my earlier design, we needed to truncate the salt and rely on understanding the birthday bound to reason about its security. This is no longer the case, since each salt is randomized by the same random value used in key derivation.

    Choosing Other Parameters

    As mentioned a second ago, we set the output length of the Argon2id KDF to 32 bytes (256 bits). We expect the security of this KDF to exceed , which to most users might as well be infinity.

    With apologies to Filippo.

    The other Argon2id parameters are a bit hand-wavey. Although the general recommendation for Argon2id is to use as much memory as possible, this code will inevitably run in some low-memory environments, so asking for several gigabytes isn’t reasonable.

    For the first draft, I settled on 16 MiB of memory, 3 iterations, and a parallelism degree of 1 (for widespread platform support).

    Plaintext Commitment Algorithm

    With all that figured out, our plaintext commitment algorithm looks something like this:

    1. Calculate the SHA512 hash of:
      • A domain separation constant
      • The header prefix (stored in the ciphertext)
      • The randomness used for key-splitting in encryption (stored in the ciphertext)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
    2. Truncate this hash to the rightmost 16 bytes (128 bits). This is the salt.
    3. Calculate Argon2id over the following inputs concatenated in this order, with an output length of 32 bytes (256 bits), using the salt from step 2:
      • Recent Merle Root Length (64-bit unsigned integer)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
      • Plaintext Length (64-bit unsigned integer)
      • Plaintext

    The output (step 3) is included as the AAD in the attribute encryption step, so the authentication tag is calculated over both the randomness and the commitment.

    To verify a commitment (which is extractable from the ciphertext), simply recalculate the commitment you expect (using the recent Merkle root specified by the record), and compare the two in constant-time.

    If they match, then you know the plaintext you’re seeing is the correct value for the ciphertext value that was committed to the Merkle tree.

    If the encryption key is shredded in the future, an attacker without knowledge of the plaintext will have an enormous uphill battle recovering it from the KDF output (and the salt will prove to be somewhat useless as a crib).

    AJ

    Caveats and Limitations

    Although this design does satisfy the specific criteria we’ve established, an attacker that already knows the correct plaintext can confirm that a specific record matches it via the plaintext commitment.

    This cannot be avoided: If we are to publish a commitment of the plaintext, someone with the plaintext can always confirm the commitment after the fact.

    CMYKat

    Whether this matters at all to the courts is a question for which I cannot offer any insight.

    Remember, we don’t even know if any of this is actually necessary, or if “moderation and platform safety” is a sufficient reason to sidestep the right to erasure.

    If the courts ever clarify this adequately, we can simply publish the mapping of Actor IDs to public keys and auxiliary data without any crypto-shredding at all.

    Trying to attack it from the other direction (download a crypto-shredded record and try to recover the plaintext without knowing it ahead of time) is attack angle we’re interested in.

    Herd Immunity for the Forgotten

    Another interesting implication that might not be obvious: The more Fediverse servers and users publish to a single Public Key Directory, the greater the anonymity pool available to each of them.

    Consider the case where a user has erased their previous Fediverse account and used the GDPR to also crypto-shred the Public Key Directory entries containing their old Actor ID.

    To guess the correct plaintext, you must not only brute-force guessing possible usernames, but also permute your guesses across all of the instances in scope.

    The more instances there are, the higher the cost of the attack.

    CMYKat

    Recap

    I tasked myself with designing a Key Transparency solution that doesn’t make complying with Article 17 of the GDPR nigh-impossible. To that end, crypto-shredding seemed like the only viable way forward.

    A serialized record containing ciphertext for each sensitive attribute would be committed to the Merkle tree. The directory would store the key locally and serve plaintext until a legal takedown was requested by the user who owns the data. Afterwards, the stored ciphertext committed to the Merkle tree is indistinguishable from random for any party that doesn’t already know the plaintext value.

    I didn’t want to allow Public Key Directories to lie about the plaintext for a given ciphertext, given that they know the key and the requestor doesn’t.

    After considering zero-knowledge proofs and finding them to not be a perfect fit, I settled on designing a plaintext commitment scheme based on the Argon2id password KDF. The KDF salts can be calculated from public inputs.

    Altogether, this meets the requirements of enabling crypto-shredding while keeping the Public Key Directory honest. All known attacks for this design are prohibitively expensive for any terrestrial threat actors.

    As an added bonus, I didn’t introduce anything fancy. You can build all of this with the cryptography available to your favorite programming language today.

    CMYKat

    Closing Thoughts

    If you’ve made it this far without being horribly confused, you’ve successfully followed my thought process for developing message attribute shreddability in my Public Key Directory specification.

    This is just one component of the overall design proposal, but one that I thought my readers would enjoy exploring in greater detail than the specification needed to capture.

    Header art: Harubaki, CMYKat.

    (This post was updated on 2024-11-22 to replace the incorrect term “PII” with “personal data”. Apologies for the confusion!)

    #Argon2 #crypto #cryptography #E2EE #encryption #FederatedPKI #fediverse #passwordHashing #symmetricCryptography

    #argon2 #crypto #cryptography #e2ee #encryption #federatedpki
  4. Soatok @[email protected] ·

    Key Transparency and the Right to be Forgotten

    This post is the first in a new series covering some of the reasoning behind decisions made in my project to build end-to-end encryption for direct messages on the Fediverse.

    (Collectively, Fedi-E2EE.)

    Although the reasons for specific design decisions should be immediately obvious from reading the relevant specification (and if not, I consider that a bug in the specification), I believe writing about it less formally will improve the clarity behind the specific design decisions taken.

    In the inaugural post for this series, I’d like to focus on how the Fedi-E2EE Public Key Directory specification aims to provide Key Transparency and an Authority-free PKI for the Fediverse without making GDPR compliance logically impossible.

    CMYKat‘s art, edited by me.

    Background

    Key Transparency

    For a clearer background, I recommend reading my blog post announcing the focused effort on a Public Key Directory, and then my update from August 2024.

    If you’re in a hurry, I’ll be brief:

    The goal of Key Transparency is to ensure everyone in a network sees the same view of who has which public key.

    How it accomplishes this is a little complicated: It involves Merkle trees, digital signatures, and a higher-level protocol of distinct actions that affect the state machine.

    If you’re thinking “blockchain”, you’re in the right ballpark, but we aren’t propping up a cryptocurrency. Instead, we’re using a centralized publisher model (per Public Key Directory instance) with decentralized verification.

    Add a bit of cross-signing and replication, and you can stitch together a robust network of Public Key Directories that can be queried to obtain the currently-trusted list of public keys (or other auxiliary data) for a given Fediverse user. This can then be used to build application-layer protocols (i.e., end-to-end encryption with an identity key more robust than “trust on first use” due to the built-in audit trail to Merkle trees).

    I’m handwaving a lot of details here. The Architecture and Specification documents are both worth a read if you’re curious to learn more.

    Right To Be Forgotten

    I am not a lawyer, nor do I play one on TV. This is not legal advice. Other standard disclaimers go here.

    Okay, now that we’ve got that out of the way, Article 17 of the GDPR establishes a “Right to erasure” for Personally Identifiable Information (PII).

    What this actually means in practice has not been consistently decided by the courts yet. However, a publicly readable, immutable ledger that maps public keys (which may be considered PII) with Actor IDs (which includes usernames, which are definitely PII) goes against the grain when it comes to GDPR.

    It remains an open question of there is public interest in this data persisting in a read-only ledger ad infinitum, which could override the right to be forgotten. If there is, that’s for the courts to decide, not furry tech bloggers.

    I know it can be tempting, especially as an American with no presence in the European Union, to shrug and say, “That seems like a them problem.” However, if other folks want to be able to use my designs within the EU, I would be remiss to at least consider this potential pitfall and try to mitigate it in my designs.

    So that’s is what I did.

    Almost Contradictory

    At first glance, the privacy goals of both Key Transparency and the GDPR’s Right To Erasure are at odds.

    • One creates an immutable, append-only history.
    • The other establishes a right for EU citizens’ history to be selectively censored, which means history has to be mutable.

    However, they’re not totally impossible to reconcile.

    An untested legal theory circulating around large American tech companies is that “crypto shredding” is legally equivalent to erasure.

    Crypto shredding is the act of storing encrypted data, and then when given a legal takedown request from an EU citizen, deleting the key instead of the data.

    This works from a purely technical perspective: If the data is encrypted, and you don’t know the key, to you it’s indistinguishable from someone who encrypted the same number of NUL bytes. In fact, many security proofs for encryption schemes are satisfied by reaching this conclusion, so this isn’t a crazy notion.

    Is Crypto Shredding Plausible?

    In 2019, the European Parliamentary Research Service published a lengthy report titled Blockchain and the General Data Protection Regulation which states the following:

    Before any examination of whether blockchain technology is capable of complying with Article 17 GDPR; it must be underscored that the precise meaning of the term ‘erasure’ remains unclear.

    Article 17 GDPR does not define erasure, and the Regulation’s recitals are equally mum on how this term should be understood. It might be assumed that a common-sense understanding of this terminology ought to be embraced. According to the Oxford English Dictionary, erasure means ‘the removal or writing, recorded material, or data’ or ‘the removal of all traces of something: obliteration’.494

    From this perspective, erasure could be taken to equal destruction. It has, however, already been stressed that the destruction of data on blockchains, particularly these of a public and permissionless nature, is far from straightforward.

    There are, however, indications that the obligation inherent to Article 17 GDPR does not have to be interpreted as requiring the outright destruction of data. In Google Spain, the delisting of information from research results was considered to amount to erasure. It is important to note, however, that in this case, this is all that was requested of Google by the claimant, who did not have control over the original data source (an online newspaper publication). Had the claimant wished to obtain the outright destruction of the relevant data it would have had to address the newspaper, not Google. This may be taken as an indication that what the GDPR requires is that the obligation resting on data controllers is to do all they can to secure a result as close as possible to the destruction of their data within the limits of [their] own factual possibilities.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 75-76

    From this, we can kind of intuit that the courts aren’t pedantic: The cited Google Spain case was satisfied by merely delisting the content, not the erasure of the newspaper’s archives.

    The report goes on to say:

    As awareness regarding the tricky reconciliation between Article 17 GDPR and distributed ledgers grows, a number of technical alternatives to the outright destruction of data have been considered by various actors. An often-mentioned solution is that of the destruction of the private key, which would have the effect of making data encrypted with a public key inaccessible. This is indeed the solution that has been put forward by the French data protection authority CNIL in its guidance on blockchains and the GDPR. The CNIL has suggested that erasure could be obtained where the keyed hash function’s secret key is deleted together with information from other systems where it was stored for processing.

    Dr Michèle Finck, Blockchain and the General Data Protection Regulation, pp. 76-77

    That said, I cannot locate a specific court decision that affirms that crypto erasure is legally sufficient for complying with data erasure requests (nor any that affirm that it’s necessary).

    I don’t have a crystal ball that can read the future on what government compliance will decide, nor am I an expert in legal matters.

    Given the absence of a clear legal framework, I do think it’s totally reasonable to consider crypto-shredding equivalent to data erasure. Most experts would probably agree with this. But it’s also possible that the courts could rule totally stupidly on this one day.

    Therefore, I must caution anyone that follows a similar path: Do not claim GDPR compliance just because you implement crypto-shredding in a distributed ledger. All you can realistically promise is that you’re not going out of your way to make compliance logically impossible. All we have to go by are untested legal hypotheses, and very little clarity (even if the technologists are near-unanimous on the topic!).

    Towards A Solution

    With all that in mind, let’s start with “crypto shredding” as the answer to the GDPR + transparency log conundrum.

    This is only the start of our complications.

    CMYKat

    Protocol Risks Introduced by Crypto Shredding

    Before the introduction of crypto shredding, the job of the Public Key Directory was simple:

    1. Receive a protocol message.
    2. Validate the protocol message.
    3. Commit the protocol message to a transparency log (in this case, Sigsum).
    4. Retrieve the protocol message whenever someone requests it to independently verify its inclusion.
    5. Miscellaneous other protocol things (cross-directory checkpoint commitment, replication, etc.).

    Point being: there was very little that the directory could do to be dishonest. If they lied about the contents of a record, it would invalidate the inclusion proofs of every successive record in the ledger.

    In order to make a given record crypto-shreddable without breaking the inclusion proofs for every record that follows, we need to commit to the ciphertext, not the plaintext. (And then, when a takedown request comes in, wipe the key.)

    Now, things are quite more interesting.

    Do you…

    • …Distribute the encryption key alongside the ciphertext and let independent third parties decrypt it on demand?

      …OR…

    • Decrypt the ciphertext and serve plaintext through the public API, keeping the encryption key private so that it may be shredded later?

    The first option seems simple, but runs into governance issues: How do you claim the data was crypto-shredded if countless individuals have a copy of the encryption key, and can therefore recover the plaintext from the ciphertext?

    Your best option is the second one, clearly.

    Okay, so how does an end user know that the ciphertext that was committed to the transparency ledger decrypts to the specific plaintext value served by the Public Key Directory? How do users know it’s not lying?

    Quick aside: This question is also relevant if you went with the first option and used a non-committing AEAD mode for the actual encryption scheme.

    In that scenario, a hostile nation state adversary could pressure a Public Key Directory to selectively give one decryption key to targeted users, and another to the rest of the Internet, in order to perform a targeted attack against citizens they’d rather didn’t have civil rights.

    My entire goal with introducing key transparency to my end-to-end encryption proposal is to prevent these sorts of attacks, not enable them.

    There are a lot of avenues we could explore here, but it’s always worth outlining the specific assumptions and security goals of any design before you start perusing the literature.

    Assumptions

    This is just a list of things we assume are true, and do not need to prove for the sake of our discussion here today. The first two are legal assumptions; the remainder are cryptographic.

    Ask your lawyer if you want advice about the first two assumptions. Ask your cryptographer if you suspect any of the remaining assumptions are false.

    1. Crypto-shredding is a legally valid way to provide data erasure (as discussed above).
    2. EU courts will consider public keys to be PII.
    3. The SHA-2 family of hash functions is secure (ignoring length-extension attacks, which won’t matter for how we’re using them).
    4. HMAC is a secure way to build a MAC algorithm out of a secure hash function.
    5. HKDF is a secure KDF if used correctly.
    6. AES is a secure 128-bit block cipher.
    7. Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.
    8. AES-CTR + HMAC-SHA2 can be turned into a secure AEAD mode, if done carefully.
    9. Ed25519 is a digital signature algorithm that provides strong security against existent forgery under a chosen-message attack (SUF-CMA).
    10. Argon2id is a secure, memory-hard password KDF, when used with reasonable parameters. (You’ll see why in a moment.)
    11. Sigsum is a secure mechanism for building a transparency log.

    This list isn’t exhaustive or formal, but should be sufficient for our purposes.

    Security Goals

    1. The protocol messages stored in the Public Key Directory are accompanied by a Merkle tree proof of inclusion. This makes it append-only with an immutable history.
    2. The Public Key Directory cannot behave dishonestly about the decrypted plaintext for a given ciphertext without clients detecting the deception.
    3. Whatever strategy we use to solve this should be resistant to economic precomputation and brute-force attacks.

    Can We Use Zero-Knowledge Proofs?

    At first, this seems like an ideal situation for a succinct, non-interactive zero-knowledge proof.

    After all, you’ve got some secret data that you hold, and you want to prove that a calculation is correct without revealing the data to the end user. This seems like the ideal setup for Schnorr’s identification protocol.

    Unfortunately, the second assumption (public keys being considered PII by courts, even though they’re derived from random secret keys) makes implementing a Zero-Knowledge Proof here very challenging.

    First, if you look at Ed25519 carefully, you’ll realize that it’s just a digital signature algorithm built atop a Schnorr proof, which requires some sort of public key (even an ephemeral one) to be managed.

    Worse, if you try to derive this value solely from public inputs (rather than creating a key management catch-22), the secret scalar your system derives at will have been calculated from the user’s PII–which only strengthens a court’s argument that the public key is therefore personally identifiable.

    There may be a more exotic zero-knowledge proof scheme that might be appropriate for our needs, but I’m generally wary of fancy new cryptography.

    Here are two rules I live by in this context:

    1. If I can’t get the algorithms out of the crypto module for whatever programming language I find myself working with, it may as well not even exist.
      • Corollary: If libsodium bindings are available, that counts as “the crypto module” too.
    2. If a developer needs to reach for a generic Big Integer library (e.g., GMP) for any reason in the course of implementing a protocol, I do not trust their implementation.

    Unfortunately, a lot of zero-knowledge proof designs fail one or both of these rules in practice.

    (Sorry not sorry, homomorphic encryption enthusiasts! The real world hasn’t caught up to your ideas yet.)

    Soatok’s Proposed Solution

    If you want to fully understand the nitty-gritty implementation details, I encourage you to read the current draft specification, plus the section describing the encryption algorithm, and finally the plaintext commitment algorithm.

    Now that we’ve established all that, I can begin to describe my approach to solving this problem.

    First, we will encrypt each attribute of a protocol message, as follows:

    • For subkey derivation, we use HKDF-HMAC-SHA512.
    • For encrypting the actual plaintext, we use AES-256-CTR.
    • For message authentication, we use HMAC-SHA512.
    • Additional associated data (AAD) is accepted and handled securely; i.e., we don’t use YOLO as a hash construction.

    This prevents an Invisible Salamander attack from being possible.

    Next, to prevent the server from being dishonest, we include a plaintext commitment hash, which is included as part of the AAD (alongside the attribute name).

    (Implementing crypto-shredding is straightforward: simply wipe the encryption keys for the attributes of the records in scope for the request.)

    If you’ve read this far, you’re probably wondering, “What exactly do you mean by plaintext commitment?”

    Plaintext Commitments

    The security of a plaintext commitment is attained by the Argon2id password hashing function.

    By using the Argon2id KDF, you can make an effective trapdoor that is easy to calculate if you know the plaintext, but economically infeasible to brute-force attack if you do not.

    However, you need to do a little more work to make it safe.

    Pass the Salt?

    Argon2id expects both a password and a salt.

    If you eschew the salt (i.e., zero it out), you open the door to precomputation attacks (see also: rainbow tables) that would greatly weaken the security of this plaintext commitment scheme.

    You need a salt.

    If you generate the salt randomly, this commitment property isn’t guaranteed by the algorithm. It would be difficult, but probably not impossible, to find two salts (, ) such that .

    I’m handwaving the fact that the salts are stored for now.

    Deriving the salt from public inputs eliminates this flexibility.

    By itself, this reintroduces the risk of making salts totally deterministic, which reintroduces the risk of precomputation attacks (which motivated the salt in the first place).

    Furthermore, any two encryptions operations that act over the same plaintext would, without any additional design considerations, produce an identical value for the salt, which would lead to an identical plaintext commitment.

    Getting to the Root of the Problem

    The scheme I’m designing, which encrypts the attributes of protocol messages and includes a commitment of the plaintext, doesn’t exist in a vacuum.

    In my system, there is one additional public input we can use to increase the quality of the salt distribution (to resist precomputation) without introducing variability (to ensure the commitment is robust): A recent Merkle tree root.

    Since every protocol message accepted by a Public Key Directory will have a distinct Merkle root, a high-traffic Public Key Directory will produce a high-entropy root hash every time a user issues a new protocol message. This is especially true if, when issuing multiple successive messages, they use the root of their previous accepted Merkle root as the “recent” root when calculating their next plaintext commitment.

    Given that Sigsum uses SHA256, there are possible Merkle roots to choose from.

    Crisis Averted?

    This sure sounds like a solution, but let’s also consider another situation.

    High-traffic Public Key Directories may have multiple users push a protocol message with the same recent Merkle root.

    Later, if both of these users issue a legal takedown, someone might observe that the recent-merkle-root is the same for two messages, but their salts differ.

    Is this enough leakage to distinguish plaintext records?

    After pondering this for a bit, I decided this was a stupid problem to have, and reached for an oft-ignored tool in a cryptographer’s toolkit (except for modern hash function designers): Truncation.

    If we truncate the salt to a smaller value, we can increase the chance of a birthday collision.

    We do need to be careful: Too small, and we improve the economics of precomputation. Too large, and we risk creating a reliably crib for distinct plaintext values.

    How Much is Too Much?

    Let’s revisit the birthday paradox.

    If you have a probability space of , you expect a 50% chance of a single collision after about samples.

    More interesting, you have a probability of a collision after about samples.

    Given that I’m designing this project for the Fediverse, which has millions of accounts (and of which more than 100,000 can reasonably be considered “active”), I posit that a probability space of is sufficient for the Argon2id salt.

    Because salts are expected to be 128 bits (at least with libsodium), we fix the other bytes to a protocol-specific constant, which contains some version information that can be changed in future iterations. This won’t be on the final exam.

    Why ?

    Simply put: we want salts to collide (albeit somewhat rarely).

    Since the salt derivation algorithm is a faster hash than a KDF, collisions make it less useful for attackers hoping for a reliable plaintext crib.

    With 48 bits left after truncation, a 50% collision probability is reached after samples (a little over 16 million). The optimal birthday bound is reached after samples (65,536).

    How do you arrive at this number?

    Let’s assume, for the moment, that my proposal sees widespread adoption with Fediverse users.

    There are just under 11 million total, and 1 million monthly active, Fediverse users as of this writing. BlueSky just hit 20 million users.

    These numbers are in the to range. (For comparison, Twitter boasted over half a billion users earlier this year, which rounds up to .)

    It is therefore expected that at least one pair of distinct plaintext Actor IDs, using two different recent Merkle roots, would produce the same salt for their plaintext commitment.

    This gives attackers a disadvantage, since collisions make the salt (derived from a fast hash) useless, thereby forcing them to attack the KDF output instead.

    Conversely, breaking the KDF output with precomputation strategies would still involve different salts for each possible plaintext.

    This rounds off to about 9 petabytes of storage just for a 48-bit salt and a 208-bit Argon2id KDF output (for a total of 32 bytes).

    Choosing Other Parameters

    As mentioned a second ago, we set the output length of the Argon2id KDF to 26 bytes (208 bits). We expect the security of this KDF to exceed . This allows us to concatenate the salt and KDF output for a total of 256 bits, which keeps the total commitment size reasonable.

    The other Argon2id parameters are a bit hand-wavey. Although the general recommendation for Argon2id is to use as much memory as possible, this code will inevitably run in some low-memory environments, so asking for several gigabytes isn’t reasonable.

    For the first draft, I settled on 16 MiB of memory, 3 iterations, and a parallelism degree of 1 (for widespread platform support).

    Plaintext Commitment Algorithm

    With all that figured out, our plaintext commitment algorithm looks something like this:

    1. Calculate the HMAC-SHA512 hash (whose key is constant for domain separation) of:
      • Recent Merle Root Lengh (64-bit unsigned integer)
      • Recent Merkle Root
      • Attribute Name Length (64-bit unsigned integer)
      • Attribute Name
      • Plaintext Length (64-bit unsigned integer)
      • Plaintext
    2. Truncate this hash to the rightmost 6 bytes (48 bits).
    3. Calculate Argon2id with the salt set to the ASCII string FE2EEPKDv1 followed by the truncated hash (step 2), with an output length of 26 bytes (208 bits).
    4. Concatenate the output steps 2 and 3.

    The output (step 4) is included as the AAD in the attribute encryption step.

    To verify a commitment (which is extractable from the ciphertext), simply recalculate the commitment you expect (using the recent Merkle root specified by the record), and compare the two in constant-time.

    If they match, then you know the plaintext you’re seeing is the correct value for the ciphertext value that was committed to the Merkle tree.

    If the encryption key is shredded in the future, an attacker without knowledge of the plaintext will have an enormous uphill battle recovering it from the KDF output (and the salt will prove to be somewhat useless as a crib).

    AJ

    Recap

    I tasked myself with designing a Key Transparency solution that doesn’t make complying with Article 17 of the GDPR nigh-impossible. To that end, crypto-shredding seemed like the only viable way forward.

    A serialized record containing ciphertext for each sensitive attribute would be committed to the Merkle tree. The directory would store the key locally and serve plaintext until a legal takedown was requested by the user who owns the data. Afterwards, the stored ciphertext committed to the Merkle tree is indistinguishable from random for any party that doesn’t already know the plaintext value.

    I didn’t want to allow Public Key Directories to lie about the plaintext for a given ciphertext, given that they know the key and the requestor doesn’t.

    After considering zero-knowledge proofs and finding them to not be a perfect fit, I settled on designing a plaintext commitment scheme based on the Argon2id password KDF, which uses a recent Merkle root to diversify the KDF salt selection, and truncates the result to make salt collisions likely (so anyone trying to attack the salt to guess plaintexts is at a disadvantage).

    Altogether, this meets the requirements of enabling crypto-shredding while keeping the Public Key Directory honest. All known attacks for this design are prohibitively expensive for any terrestrial threat actors.

    As an added bonus, I didn’t introduce anything fancy. You can build all of this with the cryptography available to your favorite programming language today.

    Closing Thoughts

    If you’ve made it this far without being horribly confused, you’ve successfully followed my thought process for developing message attribute shreddability in my Public Key Directory specification.

    This is just one component of the overall design proposal, but one that I thought my readers would enjoy exploring in greater detail than the specification needed to capture.

    Header art: Harubaki, CMYKat.

    #Argon2 #crypto #cryptography #E2EE #encryption #FederatedPKI #fediverse #passwordHashing #symmetricCryptography

    #symmetriccryptography #passwordhashing #fediverse #federatedpki #encryption #e2ee
  5. Soatok @[email protected] ·

    Ever since the Invisible Salamanders paper was published, there has been a quiet renaissance within my friends and colleagues in applied cryptography for studying systems that use Authenticated Encryption with Associated Data (AEAD) constructions, understanding what implicit assumptions these systems make about the guarantees of the AEAD mode they chose to build upon, and the consequences of those assumptions being false.

    I’ve discussed Invisible Salamanders several times throughout this blog, from my criticisms of AES-GCM and XMPP + OMEMO to my vulnerability disclosures in Threema.

    Five years after Invisible Salamanders, it’s become clear to me that many software developers do not fully appreciate the underlying problem discussed in the Invisible Salamanders paper, even when I share trivial proof-of-concept exploits.

    Background

    Fast AEAD constructions based on polynomial MACs, such as AES-GCM and ChaCha20-Poly1305, were designed to provide confidentiality and integrity for the plaintext data, and optionally integrity for some additional associated data, in systems where both parties already negotiated one shared symmetric key.

    The integrity goals of the systems that adopted these AEAD constructions were often accompanied by performance goals–usually to prevent Denial of Service (DoS) attacks in networking protocols. Verification needed to be very fast and consume minimal resources.

    In this sense, AEAD constructions were an incredible success. So successful, in fact, that most cryptographers urge application developers to use one of the fast AEAD modes as the default suggestion without looking deeper at the problem being solved. This is a good thing, because most developers will choose something stupid like ECB mode in the absence of guidance from cryptographers, and AEAD modes are much, much safer than any hand-rolled block cipher modes.

    The problem is, that one tiny little assumption that both parties (sender, recipient) for a communication have agreed on exactly one symmetric key for use in the protocol.

    Fast MACs Are Not Key-Committing

    Cryptographers have concluded that AEAD constructions based on polynomial MACs–while great for performance and rejection of malformed packets without creating DoS risks–tend to make the same assumption. This is even true of misuse-resistant modes like AES-GCM-SIV and extended-nonce constructions like XSalsa20-Poly1305.

    When discussing this implicit assumption of only one valid key in the systems that use these AEAD modes, we say that the modes are not key-committing. This terminology is based on what happens when this assumption is false.

    Consequently, you can take a single, specially crafted ciphertext (with an authentication tag) and decrypt it under multiple different keys. The authentication tags will be valid for all keys, and the plaintext will be different.

    Art: Swizz

    What does this look like in practice?

    Consider my GCM exploit, which was written to generate puzzle ciphertexts for the DEFCON Furs badge challenge a few years ago. How it works is conceptually simple (although the actual mechanics behind step 4 is a bit technical):

    1. Generate two keys.

      There’s nothing special about these keys, or their relationship to each other, and can be totally random. They just can’t be identical or the exploit is kind of pointless.

    2. Encrypt some blocks of plaintext with key1.
    3. Encrypt some more blocks of plaintext with key2.
    4. Calculate a collision block from the ciphertext in the previous two steps–which is just a bit of polynomial arithmetic in GF(2^128)
    5. Return the ciphertext (steps 2, 3, 4) and authentication tag calculated over them (which will collide for both keys).

    A system that decrypts the output of this exploit under key1 will see some plaintext, followed by some garbage, followed by 1 final block of garbage.

    If the same system decrypts under key2, it will see some garbage, followed by some plaintext, followed by 1 final block of garbage.

    For many file formats, this garbage isn’t really a problem. Additionally, a bit more precomputation allows you to choose garbage that will be more advantageous to ensuring both outputs are accepted as “valid” by the target system.

    For example, choosing two keys and a targeted nonce may allow both the valid plaintext and garbage blocks to begin with a PDF file header.

    If you’re familiar with the file polyglot work of Ange Albertini, you can use this to turn the Invisible Salamanders problem into an artform.

    And this is just the simple attack!

    The Invisible Salamanders paper outlined a more advanced variant (with a proof of concept) in Section 3.2, which doesn’t suffer from nearly as much garbage data as the simple attack.

    As Bruce Schneier often says, “Attacks only get better, they never get worse.”

    Why is it called Invisible Salamanders?

    The proof-of-concept used in the paper involved sending one picture (of a salamander) over an end-to-end encrypted messaging app, but when the recipient flagged it as abusive, the moderator saw a different picture.

    https://www.youtube.com/watch?v=3M1jIO-jLHI

    Thus, the salamander was invisible to the moderators of the encrypted messaging app.

    As for the choice of a “salamander”, I’ve been told by friends familiar with the research that was inspired by the original name of the Signal Protocol being “Axolotl”.

    But, like, who cares about these details besides me? It’s a cute and memorable name.

    What are the consequences of violating the “one key” assumption?

    That depends entirely on what your system does!

    In Database Cryptography Fur the Rest of Us, I discussed the use of AEAD modes to prevent confused deputy attacks. This works great, but if you’re building an application that supports multi-tenancy, you suddenly have to care about this issue again.

    An earlier design for OPAQUE, a password authenticated key exchange algorithm, was broken by a partitioning oracle attack due to building atop AEAD modes that are not key-committing. This let an attacker recover passwords from Shadowsocks proxy servers with a complexity similar to a binary search algorithm.

    These are two very different impacts from the same weakness, which I believe is a significant factor for why the Invisible Salamanders issue isn’t more widely understood.

    Sometimes violating the “one key” assumption that went into fast AEAD modes based on Polynomial MACs completely destroys the security of your system.

    Other times, it opens the door for a high-complexity but low-impact behavior that simply violates the principle of least astonishment but doesn’t buy the attacker anything useful.

    They Just Don’t Get It

    The Invisible Salamanders issue is relevant in any system that uses symmetric-key encryption where more than one key can be valid.

    This includes, but is not limited to:

    • Multi-tenant data warehouses
    • Group messaging protocols
      • It’s sometimes tempting to discount group messaging as a relevant consideration if your experience is “emulated groups atop 1-to-1 messaging”, but there are protocols that establish a Group Key (i.e., RFC 9420) and then use that for all group messages.
    • Envelope encryption schemes with multiple wrapping keys
    • Bearer tokens (such as JSON Web Tokens) in systems that utilize Key IDs

    Systems can mitigate this issue by introducing an explicit key commitment scheme (based on a cryptographic hash rather than a polynomial MAC) or by using a committing cipher mode (such as AES + HMAC, if done carefully).

    However, most of the time, this advice falls on deaf ears whenever this concern is brought up by a cryptography engineer who’s more aware of this issue.

    “Abuse reporting? We don’t have no stinking abuse reporting!”

    The most common misunderstanding is, “We don’t have a report abuse feature, so this issue doesn’t affect us.”

    This is because the Invisible Salamanders talk and paper focused on how it could be leveraged to defeat abuse reporting tools and bypass content moderation.

    In my experience, many security teams would read the paper and conclude that it only impacts abuse reporting features and not potentially all systems that allow multiple symmetric keys in a given context.

    Another Exploit Scenario

    Imagine you’re building a Data Loss Prevention product that integrates with corporate file-sharing and collaboration software (e.g. ownCloud) for small and medium businesses.

    One day, someone decides to ship an end-to-end encryption feature to the file-sharing software that uses AES-GCM to encrypt files, and then encrypts the keys to each recipient’s public key. This is basically the envelope encryption use-case above.

    So, you dutifully update your integration to act as another “user”, whose public key must be included in all E2EE transfers, and will block download of ciphertexts it cannot decrypt OR contains sensitive information.

    And this works, until an insider threat clever enough to abuse the Invisible Salamanders issue comes along.

    In order for said insider threat (e.g., a senior business analyst) to leak sensitive data (e.g., anything that would be useful for illegal insider trading) to another person that shouldn’t have access to it (e.g., a store clerk that’s talking to the press), they just have to do this:

    1. Encrypt the data they want to exfiltrate using key1.
    2. Encrypt some innocuous data that won’t trigger your DLP product, using key2.
    3. Ensure that both messages encrypt to the same ciphertext and authentication tag.
    4. Give their recipient key1, give everyone else (including your DLP software) key2.

    Bam! File leaked, and everyone’s none the wiser, until it’s too late. Let’s actually imagine what happens next:

    A random store clerk has leaked sensitive data to the press that only a few analysts had access to.

    The only communication between the analyst and the store clerk is a file that was shared to all employees, using the E2EE protocol. No emails or anything else were identified.

    Your DLP product didn’t identify any other communications between these two, but somehow the store clerk has the data on their desktop.

    A detailed forensics analysis may eventually figure out what happened, but by then, the damage is done and your product’s reputation is irrecoverably damaged.

    All because the hypothetical E2EE protocol didn’t include a key-commitment mechanism, and nobody identified this deficit in their designs.

    This isn’t to endorse DLP solutions at all, but rather, to highlight one of the many ways that the Invisible Salamander issue can be used creatively by clever attackers.

    Art: AJ

    “Couldn’t you do the same with steganography?”

    No, the attack is very different from stego.

    Stego is about hiding a message in plain sight, so that only the person that knows where/how to look can find it.

    The Invisible Salamanders attack lets you send one ciphertext through a network then selectively decrypt it to one of two plaintexts, depending on which key you reveal to each participant.

    In the Invisible Salamanders paper and talk, they used this to send “abusive” messages to a recipient that the moderator would not see. Thus, invisible.

    In one, the message is always emitted to anyone who knows how to find it. In the other, the attacker selects which you see, even if you have mechanisms to ensure you’re seeing the same ciphertext. It’s not a subtle difference.

    Mitigation Techniques

    There are multiple ways to mitigate the risk of Invisible Salamanders in a cryptosystem.

    1. Use HMAC, or (failing that) something built atop cryptographic hash functions, rather than a Polynomial MAC.
    2. Use an AEAD cipher designed with multi-recipient integrity as a security goal.
    3. Compute a non-invertible, one-way commitment of the encryption key.

    A trivial mitigation looks like this:

    class SoatokExampleEncryptor {  const NEW_ENCRYPT_KEY = 'myProtocol$encryptKey';  const NEW_COMMITMENT = 'myProtocol$commitment';  public function __construct(#[SensitiveParameter] private string $key)  {}  /**   * Let's assume we're starting with a simple AES-GCM wrapper   */  public function legacyEncrypt(string $plaintext, string $assocData = ''): string  {    $nonce = random_bytes(12);    $tag = '';    $ciphertext = openssl_encrypt(      $plaintext,      'aes-256-gcm',      $this->key,      OPENSSL_RAW_DATA,      $nonce,      $tag,      $assocData    );    return $nonce . $ciphertext . $tag;  }  /**   * An improved function looks something like this   */  public function newEncrypt(string $plaintext, string $assocData = ''): string  {    // Avoid birthday bound issues with 256-bits of randomness    $longerNonce = random_bytes(32);    // Derive a subkey and synthetic nonce    $tmp = hash_hkdf('sha512', $this->key, 44, self::NEW_ENCRYPT_KEY . $longerNonce);    $encKey = substr($tmp, 0, 32);    $nonce = substr($tmp, 32);    // New: Key commitment    $commitment = hash_hkdf('sha512', $this->key, 32, self::NEW_COMMITMENT . $longerNonce);    // Most of this is unchanged        $tag = '';    $ciphertext = openssl_encrypt(      $plaintext,      'aes-256-gcm',      $encKey,      OPENSSL_RAW_DATA,      $nonce,      $tag,      $assocData    );    return $longerNonce . $commitment . $ciphertext . $tag;  }}

    And then the decryption logic would recalculate the commitment, and compare it with the stored value, in constant-time.

    It’s important that the commitment be stored with the ciphertext, rather than bundling it with the key.

    (It may be worthwhile to also include the commitment in the associated data, to add a mechanism against downgrade attacks.)

    The Lesson to Learn

    If you’re building a network protocol that uses AEAD to encrypt data over an insecure network (e.g., WireGuard), keep up the good work.

    If you’re doing anything more involved than that, at the application layer, pause for a moment and consider whether your system will ever need multiple valid symmetric keys at once.

    And, if the answer is “yes”, then you should always explicitly add a key-commitment mechanism to your system design.

    (Hire a cryptographer if you’re not sure how to proceed.)

    In my opinion, hemming and hawing over whether there’s a significant impact to the Invisible Salamanders issue is a worse use of your time than just solving it directly.

    Eventually, I expect a new generation of AEAD modes will be standardized that explicitly provide key-commitment.

    When these new designs are standardized, widely supported, and sufficiently trusted by experts, feel free to update my advice to “prefer using those modes” instead.

    Header art: Harubaki, CMYKat, and a photo by Brian Gratwicke. Poorly photoshopped by myself.

    https://soatok.blog/2024/09/10/invisible-salamanders-are-not-what-you-think/

    #AEAD #AESGCM #InvisibleSalamanders #randomKeyRobustness #symmetricCryptography

    #aead #aesgcm #invisiblesalamanders #randomkeyrobustness #symmetriccryptography
  6. Soatok @[email protected] ·

    Four years ago, I wrote a (surprisingly popular) blog post about the notion of wear-out for symmetric encryption schemes.

    Two years ago, I wrote a thing about extending the nonce used by AES-GCM without introducing foot-guns. This was very recently referenced in one of Filippo Valsorda’s Cryptography Dispatches, which referenced alternative designs in the same vein.

    As I was reading Filippo’s newsletter, it occurred to me that a dedicated treatment to how cryptographers discuss the Birthday Bound for symmetric encryption would be beneficial.

    Birthday Bound?

    The Birthday Bound is rooted in the so-called Birthday Paradox in probability theory. It goes something like this:

    How many people (chosen from a uniform random distribution) would you need to have in the same room in order for there to be a 50% or greater chance that two of them have the same birthday?

    Even though there are 366 possible calendar days in the year (365 if you ignore leap years), the answer is only 23.

    This observation can tell us something interesting about the collision risk in discrete uniformly random samples.

    For example, the random number (called an IV in this case) used to encrypt a message with AES-CBC, which is a 128-bit random number. This means that there are possible values. We can simply describe this situation for any distribution; in this case, .

    For any random distribution (i.e., random nonces or tweaks for an AEAD scheme) of possible values, you expect to have a 50% chance of collision after about queries. This is a loose, order-of-magnitude estimate.

    From our earlier AES-CBC example, this means blocks of data, we’d expect a 50% chance of the two to collide.

    My symmetric wear-out blog post went in-depth about the particulars for specific designs, if you’d like to know how the numbers play out.

    Is 50/50 Good Enough?

    A security policy that cuts off at a 50% chance of a nonce reuse is not fit for the real world. We would call that a YOLO security policy.

    AES-GCM, which accepts a 96-bit nonce, is considered unsafe to use for more than random nonces. At this point, the probability of a collision for each subsequent message is greater than or equal to .

    Consequently, many people consider the point that the risk exceeds the Birthday Bound for a block cipher mode; after which, a new encryption key must be used.

    I certainly don’t fault any security policy that keeps the risk of a bad outcome below the mark, but I think there’s another way to interpret what NIST did with AES-GCM. Namely, the fact that GCM’s risk of is exceeded after samples (for some fixed value ) offers a nice symmetry to the risk analysis.

    Three Birthday Bounds

    (I was originally trying to find a wordplay that references the children’s story Six-Dinner Sid for this section, but ran out of steam and pressed publish before finding an appropriate parody.)

    Soatok Editorial Note

    This gives rise to three different possible values for a given random distribution that can be considered whenever someone says the phrase “birthday bound”.

    1. 50% collision risk after samples, which I like to think of as the
      Hard Birthday Bound.
    2. collision risk after samples, which I like to call the
      Soft Birthday Bound.
    3. collision risk after samples, which I like to call the
      Optimal Birthday Bound.

    (These labels are not official; a better naming convention may be worth considering, should this framework for discussion prove useful at all.)

    Since we’re still dealing with approximations, a useful technique for calculating is to just take the cube-root of (a.k.a., divide the exponent by 3).

    In the case of AES-GCM, the Soft and Optimal values are equivalent.

    In the case of Filippo’s XAES-256-GCM design? They differ quite a bit.

    • Soft: messages for collision probability.
    • Optimal: messages for collision probability.

    Whereas the Soft and Optimal limits for a 96-bit nonce are the same, with a 192-bit nonce, they differ a lot: Soft is about 65,536 times the size as Optimal.

    Does Any Of This Matter?

    If your accepted risk is hard-coded at , then you don’t need to pass Go or collect $200, because your security policy saves you the headache of having to care about math nerd stuff.

    However, I do think that the Optimal Birthday Bound is more useful for risk analysis for one simple reason: This is the point at which the probability of a collision is inversely proportional to the number of samples.

    Being able to say, “Encrypting messages under the same key incurs a probability of a nonce collision of approximately 1 in ,” is much more deeply satisfying than arbitrarily focusing on as an arbitrary safety limit.

    Of course, to most people, and are both ridiculously small numbers that they “might as well be zero”.

    Whenever designing extended-nonce constructions atop AEAD block cipher modes, it may be worthwhile to discuss both the Soft and Optimal limits for nonce collisions.

    So long as the people designing extended-nonce constructions at least consider doing this, my work here is done.

    CMYKat made this

    Can we get a useful table?

    Of course!

    Generally, you don’t want to consider a probability space smaller than (which is the inflection point where Optimal becomes larger than Soft).

    Probability SpaceHard BoundSoft BoundOptimal BoundThe collision probability for any Optimal Bound is 1 divided by the number of messages.

    To use this table, select a probability space from the left column. Then, on the same row, find the cell corresponding to the type of bound you are interested in.

    https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/

    #birthdayAttack #birthdayBound #blockCipherModes #symmetricCryptography

    #birthdayattack #birthdaybound #blockciphermodes #symmetriccryptography
  7. Soatok @[email protected] ·

    Four years ago, I wrote a (surprisingly popular) blog post about the notion of wear-out for symmetric encryption schemes.

    Two years ago, I wrote a thing about extending the nonce used by AES-GCM without introducing foot-guns. This was very recently referenced in one of Filippo Valsorda’s Cryptography Dispatches, which referenced alternative designs in the same vein.

    As I was reading Filippo’s newsletter, it occurred to me that a dedicated treatment to how cryptographers discuss the Birthday Bound for symmetric encryption would be beneficial.

    Birthday Bound?

    The Birthday Bound is rooted in the so-called Birthday Paradox in probability theory. It goes something like this:

    How many people (chosen from a uniform random distribution) would you need to have in the same room in order for there to be a 50% or greater chance that two of them have the same birthday?

    Even though there are 366 possible calendar days in the year (365 if you ignore leap years), the answer is only 23.

    This observation can tell us something interesting about the collision risk in discrete uniformly random samples.

    For example, the random number (called an IV in this case) used to encrypt a message with AES-CBC, which is a 128-bit random number. This means that there are possible values. We can simply describe this situation for any distribution; in this case, .

    For any random distribution (i.e., random nonces or tweaks for an AEAD scheme) of possible values, you expect to have a 50% chance of collision after about queries. This is a loose, order-of-magnitude estimate.

    From our earlier AES-CBC example, this means blocks of data, we’d expect a 50% chance of the two to collide.

    My symmetric wear-out blog post went in-depth about the particulars for specific designs, if you’d like to know how the numbers play out.

    Is 50/50 Good Enough?

    A security policy that cuts off at a 50% chance of a nonce reuse is not fit for the real world. We would call that a YOLO security policy.

    AES-GCM, which accepts a 96-bit nonce, is considered unsafe to use for more than random nonces. At this point, the probability of a collision for each subsequent message is greater than or equal to .

    Consequently, many people consider the point that the risk exceeds the Birthday Bound for a block cipher mode; after which, a new encryption key must be used.

    I certainly don’t fault any security policy that keeps the risk of a bad outcome below the mark, but I think there’s another way to interpret what NIST did with AES-GCM. Namely, the fact that GCM’s risk of is exceeded after samples (for some fixed value ) offers a nice symmetry to the risk analysis.

    Three Birthday Bounds

    (I was originally trying to find a wordplay that references the children’s story Six-Dinner Sid for this section, but ran out of steam and pressed publish before finding an appropriate parody.)

    Soatok Editorial Note

    This gives rise to three different possible values for a given random distribution that can be considered whenever someone says the phrase “birthday bound”.

    1. 50% collision risk after samples, which I like to think of as the
      Hard Birthday Bound.
    2. collision risk after samples, which I like to call the
      Soft Birthday Bound.
    3. collision risk after samples, which I like to call the
      Optimal Birthday Bound.

    (These labels are not official; a better naming convention may be worth considering, should this framework for discussion prove useful at all.)

    Since we’re still dealing with approximations, a useful technique for calculating is to just take the cube-root of (a.k.a., divide the exponent by 3).

    In the case of AES-GCM, the Soft and Optimal values are equivalent.

    In the case of Filippo’s XAES-256-GCM design? They differ quite a bit.

    • Soft: messages for collision probability.
    • Optimal: messages for collision probability.

    Whereas the Soft and Optimal limits for a 96-bit nonce are the same, with a 192-bit nonce, they differ a lot: Soft is about 65,536 times the size as Optimal.

    Does Any Of This Matter?

    If your accepted risk is hard-coded at , then you don’t need to pass Go or collect $200, because your security policy saves you the headache of having to care about math nerd stuff.

    However, I do think that the Optimal Birthday Bound is more useful for risk analysis for one simple reason: This is the point at which the probability of a collision is inversely proportional to the number of samples.

    Being able to say, “Encrypting messages under the same key incurs a probability of a nonce collision of approximately 1 in ,” is much more deeply satisfying than arbitrarily focusing on as an arbitrary safety limit.

    Of course, to most people, and are both ridiculously small numbers that they “might as well be zero”.

    Whenever designing extended-nonce constructions atop AEAD block cipher modes, it may be worthwhile to discuss both the Soft and Optimal limits for nonce collisions.

    So long as the people designing extended-nonce constructions at least consider doing this, my work here is done.

    CMYKat made this

    Can we get a useful table?

    Of course!

    Generally, you don’t want to consider a probability space smaller than (which is the inflection point where Optimal becomes larger than Soft).

    Probability SpaceHard BoundSoft BoundOptimal BoundThe collision probability for any Optimal Bound is 1 divided by the number of messages.

    To use this table, select a probability space from the left column. Then, on the same row, find the cell corresponding to the type of bound you are interested in.

    https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/

    #birthdayAttack #birthdayBound #blockCipherModes #symmetricCryptography

    #birthdayattack #birthdaybound #blockciphermodes #symmetriccryptography
  8. Soatok @[email protected] ·

    Four years ago, I wrote a (surprisingly popular) blog post about the notion of wear-out for symmetric encryption schemes.

    Two years ago, I wrote a thing about extending the nonce used by AES-GCM without introducing foot-guns. This was very recently referenced in one of Filippo Valsorda’s Cryptography Dispatches, which referenced alternative designs in the same vein.

    As I was reading Filippo’s newsletter, it occurred to me that a dedicated treatment to how cryptographers discuss the Birthday Bound for symmetric encryption would be beneficial.

    Birthday Bound?

    The Birthday Bound is rooted in the so-called Birthday Paradox in probability theory. It goes something like this:

    How many people (chosen from a uniform random distribution) would you need to have in the same room in order for there to be a 50% or greater chance that two of them have the same birthday?

    Even though there are 366 possible calendar days in the year (365 if you ignore leap years), the answer is only 23.

    This observation can tell us something interesting about the collision risk in discrete uniformly random samples.

    For example, the random number (called an IV in this case) used to encrypt a message with AES-CBC, which is a 128-bit random number. This means that there are possible values. We can simply describe this situation for any distribution; in this case, .

    For any random distribution (i.e., random nonces or tweaks for an AEAD scheme) of possible values, you expect to have a 50% chance of collision after about queries. This is a loose, order-of-magnitude estimate.

    From our earlier AES-CBC example, this means blocks of data, we’d expect a 50% chance of the two to collide.

    My symmetric wear-out blog post went in-depth about the particulars for specific designs, if you’d like to know how the numbers play out.

    Is 50/50 Good Enough?

    A security policy that cuts off at a 50% chance of a nonce reuse is not fit for the real world. We would call that a YOLO security policy.

    AES-GCM, which accepts a 96-bit nonce, is considered unsafe to use for more than random nonces. At this point, the probability of a collision for each subsequent message is greater than or equal to .

    Consequently, many people consider the point that the risk exceeds the Birthday Bound for a block cipher mode; after which, a new encryption key must be used.

    I certainly don’t fault any security policy that keeps the risk of a bad outcome below the mark, but I think there’s another way to interpret what NIST did with AES-GCM. Namely, the fact that GCM’s risk of is exceeded after samples (for some fixed value ) offers a nice symmetry to the risk analysis.

    Three Birthday Bounds

    (I was originally trying to find a wordplay that references the children’s story Six-Dinner Sid for this section, but ran out of steam and pressed publish before finding an appropriate parody.)

    Soatok Editorial Note

    This gives rise to three different possible values for a given random distribution that can be considered whenever someone says the phrase “birthday bound”.

    1. 50% collision risk after samples, which I like to think of as the
      Hard Birthday Bound.
    2. collision risk after samples, which I like to call the
      Soft Birthday Bound.
    3. collision risk after samples, which I like to call the
      Optimal Birthday Bound.

    (These labels are not official; a better naming convention may be worth considering, should this framework for discussion prove useful at all.)

    Since we’re still dealing with approximations, a useful technique for calculating is to just take the cube-root of (a.k.a., divide the exponent by 3).

    In the case of AES-GCM, the Soft and Optimal values are equivalent.

    In the case of Filippo’s XAES-256-GCM design? They differ quite a bit.

    • Soft: messages for collision probability.
    • Optimal: messages for collision probability.

    Whereas the Soft and Optimal limits for a 96-bit nonce are the same, with a 192-bit nonce, they differ a lot: Soft is about 65,536 times the size as Optimal.

    Does Any Of This Matter?

    If your accepted risk is hard-coded at , then you don’t need to pass Go or collect $200, because your security policy saves you the headache of having to care about math nerd stuff.

    However, I do think that the Optimal Birthday Bound is more useful for risk analysis for one simple reason: This is the point at which the probability of a collision is inversely proportional to the number of samples.

    Being able to say, “Encrypting messages under the same key incurs a probability of a nonce collision of approximately 1 in ,” is much more deeply satisfying than arbitrarily focusing on as an arbitrary safety limit.

    Of course, to most people, and are both ridiculously small numbers that they “might as well be zero”.

    Whenever designing extended-nonce constructions atop AEAD block cipher modes, it may be worthwhile to discuss both the Soft and Optimal limits for nonce collisions.

    So long as the people designing extended-nonce constructions at least consider doing this, my work here is done.

    CMYKat made this

    Can we get a useful table?

    Of course!

    Generally, you don’t want to consider a probability space smaller than (which is the inflection point where Optimal becomes larger than Soft).

    Probability SpaceHard BoundSoft BoundOptimal BoundThe collision probability for any Optimal Bound is 1 divided by the number of messages.

    To use this table, select a probability space from the left column. Then, on the same row, find the cell corresponding to the type of bound you are interested in.

    https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/

    #birthdayAttack #birthdayBound #blockCipherModes #symmetricCryptography

    #birthdayattack #birthdaybound #blockciphermodes #symmetriccryptography
  9. Soatok @[email protected] ·

    Four years ago, I wrote a (surprisingly popular) blog post about the notion of wear-out for symmetric encryption schemes.

    Two years ago, I wrote a thing about extending the nonce used by AES-GCM without introducing foot-guns. This was very recently referenced in one of Filippo Valsorda’s Cryptography Dispatches, which referenced alternative designs in the same vein.

    As I was reading Filippo’s newsletter, it occurred to me that a dedicated treatment to how cryptographers discuss the Birthday Bound for symmetric encryption would be beneficial.

    Birthday Bound?

    The Birthday Bound is rooted in the so-called Birthday Paradox in probability theory. It goes something like this:

    How many people (chosen from a uniform random distribution) would you need to have in the same room in order for there to be a 50% or greater chance that two of them have the same birthday?

    Even though there are 366 possible calendar days in the year (365 if you ignore leap years), the answer is only 23.

    This observation can tell us something interesting about the collision risk in discrete uniformly random samples.

    For example, the random number (called an IV in this case) used to encrypt a message with AES-CBC, which is a 128-bit random number. This means that there are possible values. We can simply describe this situation for any distribution; in this case, .

    For any random distribution (i.e., random nonces or tweaks for an AEAD scheme) of possible values, you expect to have a 50% chance of collision after about queries. This is a loose, order-of-magnitude estimate.

    From our earlier AES-CBC example, this means blocks of data, we’d expect a 50% chance of the two to collide.

    My symmetric wear-out blog post went in-depth about the particulars for specific designs, if you’d like to know how the numbers play out.

    Is 50/50 Good Enough?

    A security policy that cuts off at a 50% chance of a nonce reuse is not fit for the real world. We would call that a YOLO security policy.

    AES-GCM, which accepts a 96-bit nonce, is considered unsafe to use for more than random nonces. At this point, the probability of a collision for each subsequent message is greater than or equal to .

    Consequently, many people consider the point that the risk exceeds the Birthday Bound for a block cipher mode; after which, a new encryption key must be used.

    I certainly don’t fault any security policy that keeps the risk of a bad outcome below the mark, but I think there’s another way to interpret what NIST did with AES-GCM. Namely, the fact that GCM’s risk of is exceeded after samples (for some fixed value ) offers a nice symmetry to the risk analysis.

    Three Birthday Bounds

    (I was originally trying to find a wordplay that references the children’s story Six-Dinner Sid for this section, but ran out of steam and pressed publish before finding an appropriate parody.)

    Soatok Editorial Note

    This gives rise to three different possible values for a given random distribution that can be considered whenever someone says the phrase “birthday bound”.

    1. 50% collision risk after samples, which I like to think of as the
      Hard Birthday Bound.
    2. collision risk after samples, which I like to call the
      Soft Birthday Bound.
    3. collision risk after samples, which I like to call the
      Optimal Birthday Bound.

    (These labels are not official; a better naming convention may be worth considering, should this framework for discussion prove useful at all.)

    Since we’re still dealing with approximations, a useful technique for calculating is to just take the cube-root of (a.k.a., divide the exponent by 3).

    In the case of AES-GCM, the Soft and Optimal values are equivalent.

    In the case of Filippo’s XAES-256-GCM design? They differ quite a bit.

    • Soft: messages for collision probability.
    • Optimal: messages for collision probability.

    Whereas the Soft and Optimal limits for a 96-bit nonce are the same, with a 192-bit nonce, they differ a lot: Soft is about 65,536 times the size as Optimal.

    Does Any Of This Matter?

    If your accepted risk is hard-coded at , then you don’t need to pass Go or collect $200, because your security policy saves you the headache of having to care about math nerd stuff.

    However, I do think that the Optimal Birthday Bound is more useful for risk analysis for one simple reason: This is the point at which the probability of a collision is inversely proportional to the number of samples.

    Being able to say, “Encrypting messages under the same key incurs a probability of a nonce collision of approximately 1 in ,” is much more deeply satisfying than arbitrarily focusing on as an arbitrary safety limit.

    Of course, to most people, and are both ridiculously small numbers that they “might as well be zero”.

    Whenever designing extended-nonce constructions atop AEAD block cipher modes, it may be worthwhile to discuss both the Soft and Optimal limits for nonce collisions.

    So long as the people designing extended-nonce constructions at least consider doing this, my work here is done.

    CMYKat made this

    Can we get a useful table?

    Of course!

    Generally, you don’t want to consider a probability space smaller than (which is the inflection point where Optimal becomes larger than Soft).

    Probability SpaceHard BoundSoft BoundOptimal BoundThe collision probability for any Optimal Bound is 1 divided by the number of messages.

    To use this table, select a probability space from the left column. Then, on the same row, find the cell corresponding to the type of bound you are interested in.

    https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/

    #birthdayAttack #birthdayBound #blockCipherModes #symmetricCryptography

    #symmetriccryptography #blockciphermodes #birthdaybound #birthdayattack
  10. Semantically Secure @[email protected] ·

    If you’ve never heard of NIST SP 800-108 before, or NIST Special Publications in general, here’s a quick primer:

    Special Publications are a type of publication issued by NIST. Specifically, the SP 800-series reports on the Information Technology Laboratory’s research, guidelines, and outreach efforts in computer security, and its collaborative activities with industry, government, and academic organizations. These documents often support FIPS (Federal Information Protection Standards).

    Via NIST.gov

    One of the NIST 800-series documents concerned with Key Derivation using Pseudorandom Functions is NIST SP 800-108, first published in 2009.

    In October 2021, NIST published a draft update to NIST SP 800-108 and opened a comment period until January 2022. This update mostly included Keccak-based Message Authentication Codes (KMAC) in addition to the incumbent standardized designs (HMAC and CMAC).

    Upon reviewing a proposal for NIST SP 800-108 revision 1 after its comment period opened, Amazon’s cryptographers discovered a novel security issue with the standard.

    I was a co-author of the public comment that disclosed this issue, along with Matthew Campagna, Panos Kampanakis, and Adam Petcher, but take no credit for its discovery.

    Consequently, Section 6.7 was added to the final revision 1 of the standard to address Key Control Security.

    This post examines the attack against the initial SP 800-108 design when AES-CMAC is used as the PRF in KDF Counter mode.

    This meme is the TL;DR of this blog post

    Preliminaries

    (If you’re in a hurry, feel free to skip to the attack.)

    NIST SP 800-108 specifies a “KDF in Counter Mode” that can be used with several PRFs, including AES-CMAC. It’s worth noting that this family of KDFs can be defined to use any arbitrary PRF, but only the PRFs approved by NIST for this use are recommended.

    AES-CMAC is a one-key CBC-MAC construction. Some cryptographers, such as Matt Green, are famously not fond of CBC-MAC.

    KDF Security and PRF Security

    Yes, I will take any excuse to turn cryptography knowledge into wholesome memes.

    KDF stands for “Key Derivation Function”.

    PRF stands for “Pseudo-Random Function”.

    The security notion for KDF Security is stronger than PRF Security.

    PRFs require a uniformly-distributed secret key, while KDFs can tolerate a key that is not uniformly random.

    This matters if you’re, say, trying to derive symmetric encryption keys from a Diffie-Hellman shared secret of some sort, where the output of your DH() function has some algebraic structure.

    Realistically, the difference between the two security notions matters a lot less in scenarios where you’re deriving sub-keys from a primary uniformly random cryptographic secret.

    However, it does make your proofs nicer to achieve KDF security instead of merely PRF security.

    Key Control Security

    Let’s pretend, for simplicity, we have a generic KDF() function that offers KDF Security. We don’t need to know how it works just yet.

    Because KDFs are thought of as PRFs, but stronger, it seems perfectly reasonable that you could use KDF() in a setup where multiple inputs are provided, each from a different party, and the output would always be uniformly random.

    Further, even if all other parties’ inputs are known, it should remain computationally infeasible for one of the parties to influence the output of KDF() to produce a specific value; e.g. a key with all bits zeroed.

    The assumption that this result is computationally infeasible when working with KDF() is referred to as “Key Control Security”.

    Loss of Key Control Security in NIST SP 800-108

    You already know where this is going…

    I’m going to explain the attack by way of example.

    If you want a more formal treatment, I believe Appendix B of NIST SP 800-108 rev 1 has what you’re looking for.

    Imagine that you’re designing an online two-party private messaging app. To ensure forward secrecy, you implement a forward-secure KDF ratchet, loosely inspired by Signal’s design.

    For your KDF, you choose AES-CMAC in Counter Mode, because you’re designing for hardware that has accelerated AES instructions and want to avoid the overhead of hash functions.

    (Aside: I guess this would also imply you’re most likely selecting AES-CCM for your actual message encryption.)

    With each message, the sender commits some random bytes by encrypting them with their message. The recipient, after verifying the authentication tag and decrypting the message, possess knowledge of the same random bytes.

    Both parties then use the random bytes and the current symmetric key to ratchet forward to a new 128-bit symmetric key.

    The million dollar question is: Is this ratcheting protocol secure?

    In the case of KDF in Counter Mode with AES-CMAC, if you have more than 16 bytes of input material, the answer is simply: No.

    How The Attack Works

    A two-block implementation of this KDF is normally computed as follows:

    3. Return

    Don’t get intimidated by the notation. This is just AES encryption and XOR.

    The messages and are defined in the KDF specification. In the scenario we sketched above, we assume the attacker can choose these arbitrarily.

    To coerce a recipient to use an arbitrary 128-bit value (i.e., ) all an attacker needs to do is:

    1. Calculate
    2. Let some value
      • Here, is the target value.
    3. Force

    Notice that is the result of encrypting , and our attacker’s goal in step 3 can be achieved solely by manipulating (which exists independent of )?

    That’s the vulnerability.

    The public comments and Appendix B on the NIST document describe the actual steps of computing to force a chosen , which involve manipulating the structure of to achieve this result.

    Feel free to check out both documents if you’re interested in the finer details.

    What Can An Attacker Actually Do With This?

    If an attacker controls both and …

    Or if an attacker knows some and can control …

    …then they can force the final KDF output to equal whatever 128-bit value they want you to use.

    The most straightforward application of the loss of key control security is to introduce a backdoor into an application.

    If the Underhanded Crypto Contest were still running this year, NIST SP 800-108 using AES-CMAC in Counter Mode would be an excellent basis for a contestant.

    Does Anyone Actually Use NIST SP 800-108 This Way?

    I’m not aware of any specific products or services that use this KDF in this way. I will update this section if someone finds any.

    Is This A Deliberate Backdoor in a NIST Standard?

    No.

    I understand that, in the wake of Dual_EC_DRBG, there is a lot of distrust for NIST’s work on standardized cryptography.

    However, I have no specific knowledge to indicate this was placed deliberately in the standard.

    It is inaccurate to describe the loss of key control security in this context as a backdoor. Instead, it’s an unexpected property of the algorithms that can be used to create a clever backdoor. These are wildly different propositions.

    At least, that was the case until it was disclosed to NIST in January 2022. 🙂

    (I’m including an answer to this question, preemptively, in case someone overreacts when I publish this blog post. I hope it proves unnecessary, but I figured some caution was warranted.)

    Mitigation Options

    If you care about Key Control Security and use NIST SP 800-108, you should use HMAC or KMAC instead of CMAC. Only CMAC is impacted.

    Revision 1 of NIST SP800-108 also outlines another mitigation that involves changing the inputs to include an additional (but reusable) PRF output for every block.

    This tweak does change makes the KDF behave more like our intuition for PRFs, but in my opinion it’s better to avoid using CMAC entirely for KDFs.

    Why Wasn’t This Widely Publicized?

    As interesting and surprising as the loss of Key Control Security in a NIST standard is to cryptography nerds, it’s not exactly like Heartbleed or Log4shell.

    That said, regardless of your personal feelings on NIST, if you’re interesting in not having findings like this slip through the cracks in the future, it’s generally worthwhile to pay attention to what NIST is up to.

    https://scottarc.blog/2024/06/04/attacking-nist-sp-800-108/

    #cybersecurity #framework #KDF #KDFSecurity #KeyDerivationFunctions #NIST #NISTSP800108 #PRFSecurity #security #standards #symmetricCryptography

    #cybersecurity #framework #security #symmetriccryptography #kdf #kdfsecurity
  11. Soatok @[email protected] ·

    Earlier this year, Cendyne wrote a blog post covering the use of HKDF, building partially upon my own blog post about HKDF and the KDF security definition, but moreso inspired by a cryptographic issue they identified in another company’s product (dubbed AnonCo).

    At the bottom they teased:

    Database cryptography is hard. The above sketch is not complete and does not address several threats! This article is quite long, so I will not be sharing the fixes.

    Cendyne

    If you read Cendyne’s post, you may have nodded along with that remark and not appreciate the degree to which our naga friend was putting it mildly. So I thought I’d share some of my knowledge about real-world database cryptography in an accessible and fun format in the hopes that it might serve as an introduction to the specialization.

    Note: I’m also not going to fix Cendyne’s sketch of AnonCo’s software here–partly because I don’t want to get in the habit of assigning homework or required reading, but mostly because it’s kind of obvious once you’ve learned the basics.

    I’m including art of my fursona in this post… as is tradition for furry blogs.

    If you don’t like furries, please feel free to leave this blog and read about this topic elsewhere.

    Thanks to CMYKat for the awesome stickers.

    Contents

    • Database Cryptography?
    • Cryptography for Relational Databases
      • The Perils of Built-in Encryption Functions
      • Application-Layer Relational Database Cryptography
        • Confused Deputies
        • Canonicalization Attacks
        • Multi-Tenancy
    • Cryptography for NoSQL Databases
      • NoSQL is Built Different
      • Record Authentication
        • Bonus: A Maximally Schema-Free, Upgradeable Authentication Design
    • Searchable Encryption
      • Order-{Preserving, Revealing} Encryption
      • Deterministic Encryption
      • Homomorphic Encryption
      • Searchable Symmetric Encryption (SSE)
      • You Can Have Little a HMAC, As a Treat
    • Intermission
    • Case Study: MongoDB Client-Side Encryption
      • MongoCrypt: The Good
        • How is Queryable Encryption Implemented?
      • MongoCrypt: The Bad
      • MongoCrypt: The Ugly
    • Wrapping Up

    Database Cryptography?

    The premise of database cryptography is deceptively simple: You have a database, of some sort, and you want to store sensitive data in said database.

    The consequences of this simple premise are anything but simple. Let me explain.

    Art: ScruffKerfluff

    The sensitive data you want to store may need to remain confidential, or you may need to provide some sort of integrity guarantees throughout your entire system, or sometimes both. Sometimes all of your data is sensitive, sometimes only some of it is. Sometimes the confidentiality requirements of your data extends to where within a dataset the record you want actually lives. Sometimes that’s true of some data, but not others, so your cryptography has to be flexible to support multiple types of workloads.

    Other times, you just want your disks encrypted at rest so if they grow legs and walk out of the data center, the data cannot be comprehended by an attacker. And you can’t be bothered to work on this problem any deeper. This is usually what compliance requirements cover. Boxes get checked, executives feel safer about their operation, and the whole time nobody has really analyzed the risks they’re facing.

    But we’re not settling for mere compliance on this blog. Furries have standards, after all.

    So the first thing you need to do before diving into database cryptography is threat modelling. The first step in any good threat model is taking inventory; especially of assumptions, requirements, and desired outcomes. A few good starter questions:

    1. What database software is being used? Is it up to date?
    2. What data is being stored in which database software?
    3. How are databases oriented in the network of the overall system?
      • Is your database properly firewalled from the public Internet?
    4. How does data flow throughout the network, and when do these data flows intersect with the database?
      • Which applications talk to the database? What languages are they written in? Which APIs do they use?
    5. How will cryptography secrets be managed?
      • Is there one key for everyone, one key per tenant, etc.?
      • How are keys rotated?
      • Do you use envelope encryption with an HSM, or vend the raw materials to your end devices?

    The first two questions are paramount for deciding how to write software for database cryptography, before you even get to thinking about the cryptography itself.

    (This is not a comprehensive set of questions to ask, either. A formal threat model is much deeper in the weeds.)

    The kind of cryptography protocol you need for, say, storing encrypted CSV files an S3 bucket is vastly different from relational (SQL) databases, which in turn will be significantly different from schema-free (NoSQL) databases.

    Furthermore, when you get to the point that you can start to think about the cryptography, you’ll often need to tackle confidentiality and integrity separately.

    If that’s unclear, think of a scenario like, “I need to encrypt PII, but I also need to digitally sign the lab results so I know it wasn’t tampered with at rest.”

    My point is, right off the bat, we’ve got a three-dimensional matrix of complexity to contend with:

    1. On one axis, we have the type of database.
      • Flat-file
      • Relational
      • Schema-free
    2. On another, we have the basic confidentiality requirements of the data.
      • Field encryption
      • Row encryption
      • Column encryption
      • Unstructured record encryption
      • Encrypting entire collections of records
    3. Finally, we have the integrity requirements of the data.
      • Field authentication
      • Row/column authentication
      • Unstructured record authentication
      • Collection authentication (based on e.g. Sparse Merkle Trees)

    And then you have a fourth dimension that often falls out of operational requirements for databases: Searchability.

    Why store data in a database if you have no way to index or search the data for fast retrieval?

    Credit: Harubaki

    If you’re starting to feel overwhelmed, you’re not alone. A lot of developers drastically underestimate the difficulty of the undertaking, until they run head-first into the complexity.

    Some just phone it in with AES_Encrypt() calls in their MySQL queries. (Too bad ECB mode doesn’t provide semantic security!)

    Which brings us to the meat of this blog post: The actual cryptography part.

    Cryptography is the art of transforming information security problems into key management problems.

    Former coworker

    Note: In the interest of time, I’m skipping over flat files and focusing instead on actual database technologies.

    Cryptography for Relational Databases

    Encrypting data in an SQL database seems simple enough, even if you’ve managed to shake off the complexity I teased from the introduction.

    You’ve got data, you’ve got a column on a table. Just encrypt the data and shove it in a cell on that column and call it a day, right?

    But, alas, this is a trap. There are so many gotchas that I can’t weave a coherent, easy-to-follow narrative between them all.

    So let’s start with a simple question: where and how are you performing your encryption?

    The Perils of Built-in Encryption Functions

    MySQL provides functions called AES_Encrypt and AES_Decrypt, which many developers have unfortunately decided to rely on in the past.

    It’s unfortunate because these functions implement ECB mode. To illustrate why ECB mode is bad, I encrypted one of my art commissions with AES in ECB mode:

    Art by Riley, encrypted with AES-ECB

    The problems with ECB mode aren’t exactly “you can see the image through it,” because ECB-encrypting a compressed image won’t have redundancy (and thus can make you feel safer than you are).

    ECB art is a good visual for the actual issue you should care about, however: A lack of semantic security.

    A cryptosystem is considered semantically secure if observing the ciphertext doesn’t reveal information about the plaintext (except, perhaps, the length; which all cryptosystems leak to some extent). More information here.

    ECB art isn’t to be confused with ECB poetry, which looks like this:

    Oh little one, you’re growing up
    You’ll soon be writing C
    You’ll treat your ints as pointers
    You’ll nest the ternary
    You’ll cut and paste from github
    And try cryptography
    But even in your darkest hour
    Do not use ECB

    CBC’s BEASTly when padding’s abused
    And CTR’s fine til a nonce is reused
    Some say it’s a CRIME to compress then encrypt
    Or store keys in the browser (or use javascript)
    Diffie Hellman will collapse if hackers choose your g
    And RSA is full of traps when e is set to 3
    Whiten! Blind! In constant time! Don’t write an RNG!
    But failing all, and listen well: Do not use ECB

    They’ll say “It’s like a one-time-pad!
    The data’s short, it’s not so bad
    the keys are long–they’re iron clad
    I have a PhD!”
    And then you’re front page Hacker News
    Your passwords cracked–Adobe Blues.
    Don’t leave your penguins showing through,
    Do not use ECB

    — Ben Nagy, PoC||GTFO 0x04:13

    Most people reading this probably know better than to use ECB mode already, and don’t need any of these reminders, but there is still a lot of code that inadvertently uses ECB mode to encrypt data in the database.

    Also, SHOW processlist; leaks your encryption keys. Oops.

    Credit: CMYKatt

    Application-layer Relational Database Cryptography

    Whether burned by ECB or just cautious about not giving your secrets to the system that stores all the ciphertext protected by said secret, a common next step for developers is to simply encrypt in their server-side application code.

    And, yes, that’s part of the answer. But how you encrypt is important.

    Credit: Harubaki

    “I’ll encrypt with CBC mode.”
    If you don’t authenticate your ciphertext, you’ll be sorry. Maybe try again?

    “Okay, fine, I’ll use an authenticated mode like GCM.”
    Did you remember to make the table and column name part of your AAD? What about the primary key of the record?

    “What on Earth are you talking about, Soatok?”
    Welcome to the first footgun of database cryptography!

    Confused Deputies

    Encrypting your sensitive data is necessary, but not sufficient. You need to also bind your ciphertexts to the specific context in which they are stored.

    To understand why, let’s take a step back: What specific threat does encrypting your database records protect against?

    We’ve already established that “your disks walk out of the datacenter” is a “full disk encryption” problem, so if you’re using application-layer cryptography to encrypt data in a relational database, your threat model probably involves unauthorized access to the database server.

    What, then, stops an attacker from copying ciphertexts around?

    Credit: CMYKatt

    Let’s say I have a legitimate user account with an ID 12345, and I want to read your street address, but it’s encrypted in the database. But because I’m a clever hacker, I have unfettered access to your relational database server.

    All I would need to do is simply…

    UPDATE table SET addr_encrypted = 'your-ciphertext' WHERE id = 12345

    …and then access the application through my legitimate access. Bam, data leaked. As an attacker, I can probably even copy fields from other columns and it will just decrypt. Even if you’re using an authenticated mode.

    We call this a confused deputy attack, because the deputy (the component of the system that has been delegated some authority or privilege) has become confused by the attacker, and thus undermined an intended security goal.

    The fix is to use the AAD parameter from the authenticated mode to bind the data to a given context. (AAD = Additional Authenticated Data.)

    - $addr = aes_gcm_encrypt($addr, $key);+ $addr = aes_gcm_encrypt($addr, $key, canonicalize([+     $tableName,+     $columnName,+     $primaryKey+ ]);

    Now if I start cutting and pasting ciphertexts around, I get a decryption failure instead of silently decrypting plaintext.

    This may sound like a specific vulnerability, but it’s more of a failure to understand an important general lesson with database cryptography:

    Where your data lives is part of its identity, and MUST be authenticated.

    Soatok’s Rule of Database Cryptography

    Canonicalization Attacks

    In the previous section, I introduced a pseudocode called canonicalize(). This isn’t a pasto from some reference code; it’s an important design detail that I will elaborate on now.

    First, consider you didn’t do anything to canonicalize your data, and you just joined strings together and called it a day…

    function dumbCanonicalize(    string $tableName,    string $columnName,    string|int $primaryKey): string {    return $tableName . '_' . $columnName . '#' . $primaryKey;}

    Consider these two inputs to this function:

    1. dumbCanonicalize('customers', 'last_order_uuid', 123);
    2. dumbCanonicalize('customers_last_order', 'uuid', 123);

    In this case, your AAD would be the same, and therefore, your deputy can still be confused (albeit in a narrower use case).

    In Cendyne’s article, AnonCo did something more subtle: The canonicalization bug created a collision on the inputs to HKDF, which resulted in an unintentional key reuse.

    Up until this point, their mistake isn’t relevant to us, because we haven’t even explored key management at all. But the same design flaw can re-emerge in multiple locations, with drastically different consequence.

    Multi-Tenancy

    Once you’ve implemented a mitigation against Confused Deputies, you may think your job is done. And it very well could be.

    Often times, however, software developers are tasked with building support for Bring Your Own Key (BYOK).

    This is often spawned from a specific compliance requirement (such as cryptographic shredding; i.e. if you erase the key, you can no longer recover the plaintext, so it may as well be deleted).

    Other times, this is driven by a need to cut costs: Storing different users’ data in the same database server, but encrypting it such that they can only encrypt their own records.

    Two things can happen when you introduce multi-tenancy into your database cryptography designs:

    1. Invisible Salamanders becomes a risk, due to multiple keys being possible for any given encrypted record.
    2. Failure to address the risk of Invisible Salamanders can undermine your protection against Confused Deputies, thereby returning you to a state before you properly used the AAD.

    So now you have to revisit your designs and ensure you’re using a key-committing authenticated mode, rather than just a regular authenticated mode.

    Isn’t cryptography fun?

    “What Are Invisible Salamanders?”

    This refers to a fun property of AEAD modes based on Polynomical MACs. Basically, if you:

    1. Encrypt one message under a specific key and nonce.
    2. Encrypt another message under a separate key and nonce.

    …Then you can get the same exact ciphertext and authentication tag. Performing this attack requires you to control the keys for both encryption operations.

    This was first demonstrated in an attack against encrypted messaging applications, where a picture of a salamander was hidden from the abuse reporting feature because another attached file had the same authentication tag and ciphertext, and you could trick the system if you disclosed the second key instead of the first. Thus, the salamander is invisible to attackers.

    Art: CMYKat

    We’re not quite done with relational databases yet, but we should talk about NoSQL databases for a bit. The final topic in scope applies equally to both, after all.

    Cryptography for NoSQL Databases

    Most of the topics from relational databases also apply to NoSQL databases, so I shall refrain from duplicating them here. This article is already sufficiently long to read, after all, and I dislike redundancy.

    NoSQL is Built Different

    The main thing that NoSQL databases offer in the service of making cryptographers lose sleep at night is the schema-free nature of NoSQL designs.

    What this means is that, if you’re using a client-side encryption library for a NoSQL database, the previous concerns about confused deputy attacks are amplified by the malleability of the document structure.

    Additionally, the previously discussed cryptographic attacks against the encryption mode may be less expensive for an attacker to pull off.

    Consider the following record structure, which stores a bunch of data stored with AES in CBC mode:

    {  "encrypted-data-key": "<blob>",  "name": "<ciphertext>",  "address": [    "<ciphertext>",    "<ciphertext>"  ],  "social-security": "<ciphertext>",  "zip-code": "<ciphertext>"}

    If this record is decrypted with code that looks something like this:

    $decrypted = [];// ... snip ...foreach ($record['address'] as $i => $addrLine) {    try {        $decrypted['address'][$i] = $this->decrypt($addrLine);    } catch (Throwable $ex) {        // You'd never deliberately do this, but it's for illustration        $this->doSomethingAnOracleCanObserve($i);                // This is more believable, of course:        $this->logDecryptionError($ex, $addrLine);        $decrypted['address'][$i] = '';    }}

    Then you can keep appending rows to the "address" field to reduce the number of writes needed to exploit a padding oracle attack against any of the <ciphertext> fields.

    Art: Harubaki

    This isn’t to say that NoSQL is less secure than SQL, from the context of client-side encryption. However, the powerful feature sets that NoSQL users are accustomed to may also give attackers a more versatile toolkit to work with.

    Record Authentication

    A pedant may point out that record authentication applies to both SQL and NoSQL. However, I mostly only observe this feature in NoSQL databases and document storage systems in the wild, so I’m shoving it in here.

    Encrypting fields is nice and all, but sometimes what you want to know is that your unencrypted data hasn’t been tampered with as it flows through your system.

    The trivial way this is done is by using a digital signature algorithm over the whole record, and then appending the signature to the end. When you go to verify the record, all of the information you need is right there.

    This works well enough for most use cases, and everyone can pack up and go home. Nothing more to see here.

    Except…

    When you’re working with NoSQL databases, you often want systems to be able to write to additional fields, and since you’re working with schema-free blobs of data rather than a normalized set of relatable tables, the most sensible thing to do is to is to append this data to the same record.

    Except, oops! You can’t do that if you’re shoving a digital signature over the record. So now you need to specify which fields are to be included in the signature.

    And you need to think about how to model that in a way that doesn’t prohibit schema upgrades nor allow attackers to perform downgrade attacks. (See below.)

    I don’t have any specific real-world examples here that I can point to of this problem being solved well.

    Art: CMYKat

    Furthermore, as with preventing confused deputy and/or canonicalization attacks above, you must also include the fully qualified path of each field in the data that gets signed.

    As I said with encryption before, but also true here:

    Where your data lives is part of its identity, and MUST be authenticated.

    Soatok’s Rule of Database Cryptography

    This requirement holds true whether you’re using symmetric-key authentication (i.e. HMAC) or asymmetric-key digital signatures (e.g. EdDSA).

    Bonus: A Maximally Schema-Free, Upgradeable Authentication Design

    Art: Harubaki

    Okay, how do you solve this problem so that you can perform updates and upgrades to your schema but without enabling attackers to downgrade the security? Here’s one possible design.

    Let’s say you have two metadata fields on each record:

    1. A compressed binary string representing which fields should be authenticated. This field is, itself, not authenticated. Let’s call this meta-auth.
    2. A compressed binary string representing which of the authenticated fields should also be encrypted. This field is also authenticated. This is at most the same length as the first metadata field. Let’s call this meta-enc.

    Furthermore, you will specify a canonical field ordering for both how data is fed into the signature algorithm as well as the field mappings in meta-auth and meta-enc.

    {  "example": {    "credit-card": {      "number": /* encrypted */,      "expiration": /* encrypted */,      "ccv": /* encrypted */    },    "superfluous": {      "rewards-member": null    }  },  "meta-auth": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true   /* meta-enc */  ]),  "meta-enc": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false  /* example.superfluous.rewards-member */  ]),  "signature": /* -- snip -- */}

    When you go to append data to an existing record, you’ll need to update meta-auth to include the mapping of fields based on this canonical ordering to ensure only the intended fields get validated.

    When you update your code to add an additional field that is intended to be signed, you can roll that out for new records and the record will continue to be self-describing:

    • New records will have the additional field flagged as authenticated in meta-auth (and meta-enc will grow)
    • Old records will not, but your code will still sign them successfully
    • To prevent downgrade attacks, simply include a schema version ID as an additional plaintext field that gets authenticated. An attacker who tries to downgrade will need to be able to produce a valid signature too.

    You might think meta-auth gives an attacker some advantage, but this only includes which fields are included in the security boundary of the signature or MAC, which allows unauthenticated data to be appended for whatever operational purpose without having to update signatures or expose signing keys to a wider part of the network.

    {  "example": {    "credit-card": {      "number": /* encrypted */,      "expiration": /* encrypted */,      "ccv": /* encrypted */    },    "superfluous": {      "rewards-member": null    }  },  "meta-auth": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true,  /* meta-enc */    true   /* meta-version */  ]),  "meta-enc": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true   /* meta-version */  ]),  "meta-version": 0x01000000,  "signature": /* -- snip -- */}

    If an attacker tries to use the meta-auth field to mess with a record, the best they can hope for is an Invalid Signature exception (assuming the signature algorithm is secure to begin with).

    Even if they keep all of the fields the same, but play around with the structure of the record (e.g. changing the XPath or equivalent), so long as the path is authenticated with each field, breaking this is computationally infeasible.

    Searchable Encryption

    If you’ve managed to make it through the previous sections, congratulations, you now know enough to build a secure but completely useless database.

    Art: CMYKat

    Okay, put away the pitchforks; I will explain.

    Part of the reason why we store data in a database, rather than a flat file, is because we want to do more than just read and write. Sometimes computer scientists want to compute. Almost always, you want to be able to query your database for a subset of records based on your specific business logic needs.

    And so, a database which doesn’t do anything more than store ciphertext and maybe signatures is pretty useless to most people. You’d have better luck selling Monkey JPEGs to furries than convincing most businesses to part with their precious database-driven report generators.

    Art: Sophie

    So whenever one of your users wants to actually use their data, rather than just store it, they’re forced to decide between two mutually exclusive options:

    1. Encrypting the data, to protect it from unauthorized disclosure, but render it useless
    2. Doing anything useful with the data, but leaving it unencrypted in the database

    This is especially annoying for business types that are all in on the Zero Trust buzzword.

    Fortunately, the cryptographers are at it again, and boy howdy do they have a lot of solutions for this problem.

    Order-{Preserving, Revealing} Encryption

    On the fun side of things, you have things like Order-Preserving and Order-Revealing Encryption, which Matthew Green wrote about at length.

    [D]atabase encryption has been a controversial subject in our field. I wish I could say that there’s been an actual debate, but it’s more that different researchers have fallen into different camps, and nobody has really had the data to make their position in a compelling way. There have actually been some very personal arguments made about it.

    Attack of the week: searchable encryption and the ever-expanding leakage function

    The problem with these designs is that they have a significant enough leakage that it no longer provides semantic security.

    From Grubbs, et al. (GLMP, 2019.)
    Colors inverted to fit my blog’s theme better.

    To put it in other words: These designs are only marginally better than ECB mode, and probably deserve their own poems too.

    Order revealing
    Reveals much more than order
    Softcore ECB

    Order preserving
    Semantic security?
    Only in your dreams

    Haiku for your consideration

    Deterministic Encryption

    Here’s a simpler, but also terrible, idea for searchable encryption: Simply give up on semantic security entirely.

    If you recall the AES_{De,En}crypt() functions built into MySQL I mentioned at the start of this article, those are the most common form of deterministic encryption I’ve seen in use.

     SELECT * FROM foo WHERE bar = AES_Encrypt('query', 'key');

    However, there are slightly less bad variants. If you use AES-GCM-SIV with a static nonce, your ciphertexts are fully deterministic, and you can encrypt a small number of distinct records safely before you’re no longer secure.

    From Page 14 of the linked paper. Full view.

    That’s certainly better than nothing, but you also can’t mitigate confused deputy attacks. But we can do better than this.

    Homomorphic Encryption

    In a safer plane of academia, you’ll find homomorphic encryption, which researchers recently demonstrated with serving Wikipedia pages in a reasonable amount of time.

    Homomorphic encryption allows computations over the ciphertext, which will be reflected in the plaintext, without ever revealing the key to the entity performing the computation.

    If this sounds vaguely similar to the conditions that enable chosen-ciphertext attacks, you probably have a good intuition for how it works: RSA is homomorphic to multiplication, AES-CTR is homomorphic to XOR. Fully homomorphic encryption uses lattices, which enables multiple operations but carries a relatively enormous performance cost.

    Art: Harubaki

    Homomorphic encryption sometimes intersects with machine learning, because the notion of training an encrypted model by feeding it encrypted data, then decrypting it after-the-fact is desirable for certain business verticals. Your data scientists never see your data, and you have some plausible deniability about the final ML model this work produces. This is like a Siren song for Venture Capitalist-backed medical technology companies. Tech journalists love writing about it.

    However, a less-explored use case is the ability to encrypt your programs but still get the correct behavior and outputs. Although this sounds like a DRM technology, it’s actually something that individuals could one day use to prevent their ISPs or cloud providers from knowing what software is being executed on the customer’s leased hardware. The potential for a privacy win here is certainly worth pondering, even if you’re a tried and true Pirate Party member.

    Just say “NO” to the copyright cartels.

    Art: CMYKat

    Searchable Symmetric Encryption (SSE)

    Forget about working at the level of fields and rows or individual records. What if we, instead, worked over collections of documents, where each document is viewed as a set of keywords from a keyword space?

    Art: CMYKat

    That’s the basic premise of SSE: Encrypting collections of documents rather than individual records.

    The actual implementation details differ greatly between designs. They also differ greatly in their leakage profiles and susceptibility to side-channel attacks.

    Some schemes use a so-called trapdoor permutation, such as RSA, as one of their building blocks.

    Some schemes only allow for searching a static set of records, while others can accommodate new data over time (with the trade-off between more leakage or worse performance).

    If you’re curious, you can learn more about SSE here, and see some open source SEE implementations online here.

    You’re probably wondering, “If SSE is this well-studied and there are open source implementations available, why isn’t it more widely used?”

    Your guess is as good as mine, but I can think of a few reasons:

    1. The protocols can be a little complicated to implement, and aren’t shipped by default in cryptography libraries (i.e. OpenSSL’s libcrypto or libsodium).
    2. Every known security risk in SSE is the product of a trade-offs, rather than there being a single winner for all use cases that developers can feel comfortable picking.
    3. Insufficient marketing and developer advocacy.
      SSE schemes are mostly of interest to academics, although Seny Kamara (Brown Univeristy professior and one of the luminaries of searchable encryption) did try to develop an app called Pixek which used SSE to encrypt photos.

    Maybe there’s room for a cryptography competition on searchable encryption schemes in the future.

    You Can Have Little a HMAC, As a Treat

    Finally, I can’t talk about searchable encryption without discussing a technique that’s older than dirt by Internet standards, that has been independently reinvented by countless software developers tasked with encrypting database records.

    The oldest version I’ve been able to track down dates to 2006 by Raul Garcia at Microsoft, but I’m not confident that it didn’t exist before.

    The idea I’m alluding to goes like this:

    1. Encrypt your data, securely, using symmetric cryptography.
      (Hopefully your encryption addresses the considerations outlined in the relevant sections above.)
    2. Separately, calculate an HMAC over the unencrypted data with a separate key used exclusively for indexing.

    When you need to query your data, you can just recalculate the HMAC of your challenge and fetch the records that match it. Easy, right?

    Even if you rotate your keys for encryption, you keep your indexing keys static across your entire data set. This lets you have durable indexes for encrypted data, which gives you the ability to do literal lookups for the performance hit of a hash function.

    Additionally, everyone has HMAC in their toolkit, so you don’t have to move around implementations of complex cryptographic building blocks. You can live off the land. What’s not to love?

    Hooray!

    However, if you stopped here, we regret to inform you that your data is no longer indistinguishable from random, which probably undermines the security proof for your encryption scheme.

    How annoying!

    Of course, you don’t have to stop with the addition of plain HMAC to your database encryption software.

    Take a page from Troy Hunt: Truncate the output to provide k-anonymity rather than a direct literal look-up.

    “K-What Now?”

    Imagine you have a full HMAC-SHA256 of the plaintext next to every ciphertext record with a static key, for searchability.

    Each HMAC output corresponds 1:1 with a unique plaintext.

    Because you’re using HMAC with a secret key, an attacker can’t just build a rainbow table like they would when attempting password cracking, but it still leaks duplicate plaintexts.

    For example, an HMAC-SHA256 output might look like this: 04a74e4c0158e34a566785d1a5e1167c4e3455c42aea173104e48ca810a8b1ae

    Art: CMYKat\

    If you were to slice off most of those bytes (e.g. leaving only the last 3, which in the previous example yields a8b1ae), then with sufficient records, multiple plaintexts will now map to the same truncated HMAC tag.

    Which means if you’re only revealing a truncated HMAC tag to the database server (both when storing records or retrieving them), you can now expect false positives due to collisions in your truncated HMAC tag.

    These false positives give your data a discrete set of anonymity (called k-anonymity), which means an attacker with access to your database cannot:

    1. Distinguish between two encrypted records with the same short HMAC tag.
    2. Reverse engineer the short HMAC tag into a single possible plaintext value, even if they can supply candidate queries and study the tags sent to the database.
    Art: CMYKat\

    As with SSE above, this short HMAC technique exposes a trade-off to users.

    • Too much k-anonymity (i.e. too many false positives), and you will have to decrypt-then-discard multiple mismatching records. This can make queries slow.
    • Not enough k-anonymity (i.e. insufficient false positives), and you’re no better off than a full HMAC.

    Even more troublesome, the right amount to truncate is expressed in bits (not bytes), and calculating this value depends on the number of unique plaintext values you anticipate in your dataset. (Fortunately, it grows logarithmically, so you’ll rarely if ever have to tune this.)

    If you’d like to play with this idea, here’s a quick and dirty demo script.

    Intermission

    If you started reading this post with any doubts about Cendyne’s statement that “Database cryptography is hard”, by making it to this point, they’ve probably been long since put to rest.

    Art: Harubaki

    Conversely, anyone that specializes in this topic is probably waiting for me to say anything novel or interesting; their patience wearing thin as I continue to rehash a surface-level introduction of their field without really diving deep into anything.

    Thus, if you’ve read this far, I’d like to demonstrate the application of what I’ve covered thus far into a real-world case study into an database cryptography product.

    Case Study: MongoDB Client-Side Encryption

    MongoDB is an open source schema-free NoSQL database. Last year, MongoDB made waves when they announced Queryable Encryption in their upcoming client-side encryption release.

    Taken from the press release, but adapted for dark themes.

    A statement at the bottom of their press release indicates that this isn’t clown-shoes:

    Queryable Encryption was designed by MongoDB’s Advanced Cryptography Research Group, headed by Seny Kamara and Tarik Moataz, who are pioneers in the field of encrypted search. The Group conducts cutting-edge peer-reviewed research in cryptography and works with MongoDB engineering teams to transfer and deploy the latest innovations in cryptography and privacy to the MongoDB data platform.

    If you recall, I mentioned Seny Kamara in the SSE section of this post. They certainly aren’t wrong about Kamara and Moataz being pioneers in this field.

    So with that in mind, let’s explore the implementation in libmongocrypt and see how it stands up to scrutiny.

    MongoCrypt: The Good

    MongoDB’s encryption library takes key management seriously: They provide a KMS integration for cloud users by default (supporting both AWS and Azure).

    MongoDB uses Encrypt-then-MAC with AES-CBC and HMAC-SHA256, which is congruent to what Signal does for message encryption.

    How Is Queryable Encryption Implemented?

    From the current source code, we can see that MongoCrypt generates several different types of tokens, using HMAC (calculation defined here).

    According to their press release:

    The feature supports equality searches, with additional query types such as range, prefix, suffix, and substring planned for future releases.

    MongoDB Queryable Encryption Announcement

    Which means that most of the juicy details probably aren’t public yet.

    These HMAC-derived tokens are stored wholesale in the data structure, but most are encrypted before storage using AES-CTR.

    There are more layers of encryption (using AEAD), server-side token processing, and more AES-CTR-encrypted edge tokens. All of this is finally serialized (implementation) as one blob for storage.

    Since only the equality operation is currently supported (which is the same feature you’d get from HMAC), it’s difficult to speculate what the full feature set looks like.

    However, since Kamara and Moataz are leading its development, it’s likely that this feature set will be excellent.

    MongoCrypt: The Bad

    Every call to do_encrypt() includes at most the Key ID (but typically NULL) as the AAD. This means that the concerns over Confused Deputies (and NoSQL specifically) are relevant to MongoDB.

    However, even if they did support authenticating the fully qualified path to a field in the AAD for their encryption, their AEAD construction is vulnerable to the kind of canonicalization attack I wrote about previously.

    First, observe this code which assembles the multi-part inputs into HMAC.

    /* Construct the input to the HMAC */uint32_t num_intermediates = 0;_mongocrypt_buffer_t intermediates[3];// -- snip --if (!_mongocrypt_buffer_concat (  &to_hmac, intermediates, num_intermediates)) {   CLIENT_ERR ("failed to allocate buffer");   goto done;}if (hmac == HMAC_SHA_512_256) {   uint8_t storage[64];   _mongocrypt_buffer_t tag = {.data = storage, .len = sizeof (storage)};   if (!_crypto_hmac_sha_512 (crypto, Km, &to_hmac, &tag, status)) {      goto done;   }   // Truncate sha512 to first 256 bits.   memcpy (out->data, tag.data, MONGOCRYPT_HMAC_LEN);} else {   BSON_ASSERT (hmac == HMAC_SHA_256);   if (!_mongocrypt_hmac_sha_256 (crypto, Km, &to_hmac, out, status)) {      goto done;   }}

    The implementation of _mongocrypt_buffer_concat() can be found here.

    If either the implementation of that function, or the code I snipped from my excerpt, had contained code that prefixed every segment of the AAD with the length of the segment (represented as a uint64_t to make overflow infeasible), then their AEAD mode would not be vulnerable to canonicalization issues.

    Using TupleHash would also have prevented this issue.

    Silver lining for MongoDB developers: Because the AAD is either a key ID or NULL, this isn’t exploitable in practice.

    The first cryptographic flaw sort of cancels the second out.

    If the libmongocrypt developers ever want to mitigate Confused Deputy attacks, they’ll need to address this canonicalization issue too.

    MongoCrypt: The Ugly

    MongoCrypt supports deterministic encryption.

    If you specify deterministic encryption for a field, your application passes a deterministic initialization vector to AEAD.

    MongoDB documentation

    We already discussed why this is bad above.

    Wrapping Up

    This was not a comprehensive treatment of the field of database cryptography. There are many areas of this field that I did not cover, nor do I feel qualified to discuss.

    However, I hope anyone who takes the time to read this finds themselves more familiar with the subject.

    Additionally, I hope any developers who think “encrypting data in a database is [easy, trivial] (select appropriate)” will find this broad introduction a humbling experience.

    Art: CMYKat

    https://soatok.blog/2023/03/01/database-cryptography-fur-the-rest-of-us/

    #appliedCryptography #blockCipherModes #cryptography #databaseCryptography #databases #encryptedSearch #HMAC #MongoCrypt #MongoDB #QueryableEncryption #realWorldCryptography #security #SecurityGuidance #SQL #SSE #symmetricCryptography #symmetricSearchableEncryption

    #appliedcryptography #blockciphermodes #cryptography #databasecryptography #databases #encryptedsearch
  12. Soatok @[email protected] ·

    Earlier this year, Cendyne wrote a blog post covering the use of HKDF, building partially upon my own blog post about HKDF and the KDF security definition, but moreso inspired by a cryptographic issue they identified in another company’s product (dubbed AnonCo).

    At the bottom they teased:

    Database cryptography is hard. The above sketch is not complete and does not address several threats! This article is quite long, so I will not be sharing the fixes.

    Cendyne

    If you read Cendyne’s post, you may have nodded along with that remark and not appreciate the degree to which our naga friend was putting it mildly. So I thought I’d share some of my knowledge about real-world database cryptography in an accessible and fun format in the hopes that it might serve as an introduction to the specialization.

    Note: I’m also not going to fix Cendyne’s sketch of AnonCo’s software here–partly because I don’t want to get in the habit of assigning homework or required reading, but mostly because it’s kind of obvious once you’ve learned the basics.

    I’m including art of my fursona in this post… as is tradition for furry blogs.

    If you don’t like furries, please feel free to leave this blog and read about this topic elsewhere.

    Thanks to CMYKat for the awesome stickers.

    Contents

    • Database Cryptography?
    • Cryptography for Relational Databases
      • The Perils of Built-in Encryption Functions
      • Application-Layer Relational Database Cryptography
        • Confused Deputies
        • Canonicalization Attacks
        • Multi-Tenancy
    • Cryptography for NoSQL Databases
      • NoSQL is Built Different
      • Record Authentication
        • Bonus: A Maximally Schema-Free, Upgradeable Authentication Design
    • Searchable Encryption
      • Order-{Preserving, Revealing} Encryption
      • Deterministic Encryption
      • Homomorphic Encryption
      • Searchable Symmetric Encryption (SSE)
      • You Can Have Little a HMAC, As a Treat
    • Intermission
    • Case Study: MongoDB Client-Side Encryption
      • MongoCrypt: The Good
        • How is Queryable Encryption Implemented?
      • MongoCrypt: The Bad
      • MongoCrypt: The Ugly
    • Wrapping Up

    Database Cryptography?

    The premise of database cryptography is deceptively simple: You have a database, of some sort, and you want to store sensitive data in said database.

    The consequences of this simple premise are anything but simple. Let me explain.

    Art: ScruffKerfluff

    The sensitive data you want to store may need to remain confidential, or you may need to provide some sort of integrity guarantees throughout your entire system, or sometimes both. Sometimes all of your data is sensitive, sometimes only some of it is. Sometimes the confidentiality requirements of your data extends to where within a dataset the record you want actually lives. Sometimes that’s true of some data, but not others, so your cryptography has to be flexible to support multiple types of workloads.

    Other times, you just want your disks encrypted at rest so if they grow legs and walk out of the data center, the data cannot be comprehended by an attacker. And you can’t be bothered to work on this problem any deeper. This is usually what compliance requirements cover. Boxes get checked, executives feel safer about their operation, and the whole time nobody has really analyzed the risks they’re facing.

    But we’re not settling for mere compliance on this blog. Furries have standards, after all.

    So the first thing you need to do before diving into database cryptography is threat modelling. The first step in any good threat model is taking inventory; especially of assumptions, requirements, and desired outcomes. A few good starter questions:

    1. What database software is being used? Is it up to date?
    2. What data is being stored in which database software?
    3. How are databases oriented in the network of the overall system?
      • Is your database properly firewalled from the public Internet?
    4. How does data flow throughout the network, and when do these data flows intersect with the database?
      • Which applications talk to the database? What languages are they written in? Which APIs do they use?
    5. How will cryptography secrets be managed?
      • Is there one key for everyone, one key per tenant, etc.?
      • How are keys rotated?
      • Do you use envelope encryption with an HSM, or vend the raw materials to your end devices?

    The first two questions are paramount for deciding how to write software for database cryptography, before you even get to thinking about the cryptography itself.

    (This is not a comprehensive set of questions to ask, either. A formal threat model is much deeper in the weeds.)

    The kind of cryptography protocol you need for, say, storing encrypted CSV files an S3 bucket is vastly different from relational (SQL) databases, which in turn will be significantly different from schema-free (NoSQL) databases.

    Furthermore, when you get to the point that you can start to think about the cryptography, you’ll often need to tackle confidentiality and integrity separately.

    If that’s unclear, think of a scenario like, “I need to encrypt PII, but I also need to digitally sign the lab results so I know it wasn’t tampered with at rest.”

    My point is, right off the bat, we’ve got a three-dimensional matrix of complexity to contend with:

    1. On one axis, we have the type of database.
      • Flat-file
      • Relational
      • Schema-free
    2. On another, we have the basic confidentiality requirements of the data.
      • Field encryption
      • Row encryption
      • Column encryption
      • Unstructured record encryption
      • Encrypting entire collections of records
    3. Finally, we have the integrity requirements of the data.
      • Field authentication
      • Row/column authentication
      • Unstructured record authentication
      • Collection authentication (based on e.g. Sparse Merkle Trees)

    And then you have a fourth dimension that often falls out of operational requirements for databases: Searchability.

    Why store data in a database if you have no way to index or search the data for fast retrieval?

    Credit: Harubaki

    If you’re starting to feel overwhelmed, you’re not alone. A lot of developers drastically underestimate the difficulty of the undertaking, until they run head-first into the complexity.

    Some just phone it in with AES_Encrypt() calls in their MySQL queries. (Too bad ECB mode doesn’t provide semantic security!)

    Which brings us to the meat of this blog post: The actual cryptography part.

    Cryptography is the art of transforming information security problems into key management problems.

    Former coworker

    Note: In the interest of time, I’m skipping over flat files and focusing instead on actual database technologies.

    Cryptography for Relational Databases

    Encrypting data in an SQL database seems simple enough, even if you’ve managed to shake off the complexity I teased from the introduction.

    You’ve got data, you’ve got a column on a table. Just encrypt the data and shove it in a cell on that column and call it a day, right?

    But, alas, this is a trap. There are so many gotchas that I can’t weave a coherent, easy-to-follow narrative between them all.

    So let’s start with a simple question: where and how are you performing your encryption?

    The Perils of Built-in Encryption Functions

    MySQL provides functions called AES_Encrypt and AES_Decrypt, which many developers have unfortunately decided to rely on in the past.

    It’s unfortunate because these functions implement ECB mode. To illustrate why ECB mode is bad, I encrypted one of my art commissions with AES in ECB mode:

    Art by Riley, encrypted with AES-ECB

    The problems with ECB mode aren’t exactly “you can see the image through it,” because ECB-encrypting a compressed image won’t have redundancy (and thus can make you feel safer than you are).

    ECB art is a good visual for the actual issue you should care about, however: A lack of semantic security.

    A cryptosystem is considered semantically secure if observing the ciphertext doesn’t reveal information about the plaintext (except, perhaps, the length; which all cryptosystems leak to some extent). More information here.

    ECB art isn’t to be confused with ECB poetry, which looks like this:

    Oh little one, you’re growing up
    You’ll soon be writing C
    You’ll treat your ints as pointers
    You’ll nest the ternary
    You’ll cut and paste from github
    And try cryptography
    But even in your darkest hour
    Do not use ECB

    CBC’s BEASTly when padding’s abused
    And CTR’s fine til a nonce is reused
    Some say it’s a CRIME to compress then encrypt
    Or store keys in the browser (or use javascript)
    Diffie Hellman will collapse if hackers choose your g
    And RSA is full of traps when e is set to 3
    Whiten! Blind! In constant time! Don’t write an RNG!
    But failing all, and listen well: Do not use ECB

    They’ll say “It’s like a one-time-pad!
    The data’s short, it’s not so bad
    the keys are long–they’re iron clad
    I have a PhD!”
    And then you’re front page Hacker News
    Your passwords cracked–Adobe Blues.
    Don’t leave your penguins showing through,
    Do not use ECB

    — Ben Nagy, PoC||GTFO 0x04:13

    Most people reading this probably know better than to use ECB mode already, and don’t need any of these reminders, but there is still a lot of code that inadvertently uses ECB mode to encrypt data in the database.

    Also, SHOW processlist; leaks your encryption keys. Oops.

    Credit: CMYKatt

    Application-layer Relational Database Cryptography

    Whether burned by ECB or just cautious about not giving your secrets to the system that stores all the ciphertext protected by said secret, a common next step for developers is to simply encrypt in their server-side application code.

    And, yes, that’s part of the answer. But how you encrypt is important.

    Credit: Harubaki

    “I’ll encrypt with CBC mode.”
    If you don’t authenticate your ciphertext, you’ll be sorry. Maybe try again?

    “Okay, fine, I’ll use an authenticated mode like GCM.”
    Did you remember to make the table and column name part of your AAD? What about the primary key of the record?

    “What on Earth are you talking about, Soatok?”
    Welcome to the first footgun of database cryptography!

    Confused Deputies

    Encrypting your sensitive data is necessary, but not sufficient. You need to also bind your ciphertexts to the specific context in which they are stored.

    To understand why, let’s take a step back: What specific threat does encrypting your database records protect against?

    We’ve already established that “your disks walk out of the datacenter” is a “full disk encryption” problem, so if you’re using application-layer cryptography to encrypt data in a relational database, your threat model probably involves unauthorized access to the database server.

    What, then, stops an attacker from copying ciphertexts around?

    Credit: CMYKatt

    Let’s say I have a legitimate user account with an ID 12345, and I want to read your street address, but it’s encrypted in the database. But because I’m a clever hacker, I have unfettered access to your relational database server.

    All I would need to do is simply…

    UPDATE table SET addr_encrypted = 'your-ciphertext' WHERE id = 12345

    …and then access the application through my legitimate access. Bam, data leaked. As an attacker, I can probably even copy fields from other columns and it will just decrypt. Even if you’re using an authenticated mode.

    We call this a confused deputy attack, because the deputy (the component of the system that has been delegated some authority or privilege) has become confused by the attacker, and thus undermined an intended security goal.

    The fix is to use the AAD parameter from the authenticated mode to bind the data to a given context. (AAD = Additional Authenticated Data.)

    - $addr = aes_gcm_encrypt($addr, $key);+ $addr = aes_gcm_encrypt($addr, $key, canonicalize([+     $tableName,+     $columnName,+     $primaryKey+ ]);

    Now if I start cutting and pasting ciphertexts around, I get a decryption failure instead of silently decrypting plaintext.

    This may sound like a specific vulnerability, but it’s more of a failure to understand an important general lesson with database cryptography:

    Where your data lives is part of its identity, and MUST be authenticated.

    Soatok’s Rule of Database Cryptography

    Canonicalization Attacks

    In the previous section, I introduced a pseudocode called canonicalize(). This isn’t a pasto from some reference code; it’s an important design detail that I will elaborate on now.

    First, consider you didn’t do anything to canonicalize your data, and you just joined strings together and called it a day…

    function dumbCanonicalize(    string $tableName,    string $columnName,    string|int $primaryKey): string {    return $tableName . '_' . $columnName . '#' . $primaryKey;}

    Consider these two inputs to this function:

    1. dumbCanonicalize('customers', 'last_order_uuid', 123);
    2. dumbCanonicalize('customers_last_order', 'uuid', 123);

    In this case, your AAD would be the same, and therefore, your deputy can still be confused (albeit in a narrower use case).

    In Cendyne’s article, AnonCo did something more subtle: The canonicalization bug created a collision on the inputs to HKDF, which resulted in an unintentional key reuse.

    Up until this point, their mistake isn’t relevant to us, because we haven’t even explored key management at all. But the same design flaw can re-emerge in multiple locations, with drastically different consequence.

    Multi-Tenancy

    Once you’ve implemented a mitigation against Confused Deputies, you may think your job is done. And it very well could be.

    Often times, however, software developers are tasked with building support for Bring Your Own Key (BYOK).

    This is often spawned from a specific compliance requirement (such as cryptographic shredding; i.e. if you erase the key, you can no longer recover the plaintext, so it may as well be deleted).

    Other times, this is driven by a need to cut costs: Storing different users’ data in the same database server, but encrypting it such that they can only encrypt their own records.

    Two things can happen when you introduce multi-tenancy into your database cryptography designs:

    1. Invisible Salamanders becomes a risk, due to multiple keys being possible for any given encrypted record.
    2. Failure to address the risk of Invisible Salamanders can undermine your protection against Confused Deputies, thereby returning you to a state before you properly used the AAD.

    So now you have to revisit your designs and ensure you’re using a key-committing authenticated mode, rather than just a regular authenticated mode.

    Isn’t cryptography fun?

    “What Are Invisible Salamanders?”

    This refers to a fun property of AEAD modes based on Polynomical MACs. Basically, if you:

    1. Encrypt one message under a specific key and nonce.
    2. Encrypt another message under a separate key and nonce.

    …Then you can get the same exact ciphertext and authentication tag. Performing this attack requires you to control the keys for both encryption operations.

    This was first demonstrated in an attack against encrypted messaging applications, where a picture of a salamander was hidden from the abuse reporting feature because another attached file had the same authentication tag and ciphertext, and you could trick the system if you disclosed the second key instead of the first. Thus, the salamander is invisible to attackers.

    Art: CMYKat

    We’re not quite done with relational databases yet, but we should talk about NoSQL databases for a bit. The final topic in scope applies equally to both, after all.

    Cryptography for NoSQL Databases

    Most of the topics from relational databases also apply to NoSQL databases, so I shall refrain from duplicating them here. This article is already sufficiently long to read, after all, and I dislike redundancy.

    NoSQL is Built Different

    The main thing that NoSQL databases offer in the service of making cryptographers lose sleep at night is the schema-free nature of NoSQL designs.

    What this means is that, if you’re using a client-side encryption library for a NoSQL database, the previous concerns about confused deputy attacks are amplified by the malleability of the document structure.

    Additionally, the previously discussed cryptographic attacks against the encryption mode may be less expensive for an attacker to pull off.

    Consider the following record structure, which stores a bunch of data stored with AES in CBC mode:

    {  "encrypted-data-key": "<blob>",  "name": "<ciphertext>",  "address": [    "<ciphertext>",    "<ciphertext>"  ],  "social-security": "<ciphertext>",  "zip-code": "<ciphertext>"}

    If this record is decrypted with code that looks something like this:

    $decrypted = [];// ... snip ...foreach ($record['address'] as $i => $addrLine) {    try {        $decrypted['address'][$i] = $this->decrypt($addrLine);    } catch (Throwable $ex) {        // You'd never deliberately do this, but it's for illustration        $this->doSomethingAnOracleCanObserve($i);                // This is more believable, of course:        $this->logDecryptionError($ex, $addrLine);        $decrypted['address'][$i] = '';    }}

    Then you can keep appending rows to the "address" field to reduce the number of writes needed to exploit a padding oracle attack against any of the <ciphertext> fields.

    Art: Harubaki

    This isn’t to say that NoSQL is less secure than SQL, from the context of client-side encryption. However, the powerful feature sets that NoSQL users are accustomed to may also give attackers a more versatile toolkit to work with.

    Record Authentication

    A pedant may point out that record authentication applies to both SQL and NoSQL. However, I mostly only observe this feature in NoSQL databases and document storage systems in the wild, so I’m shoving it in here.

    Encrypting fields is nice and all, but sometimes what you want to know is that your unencrypted data hasn’t been tampered with as it flows through your system.

    The trivial way this is done is by using a digital signature algorithm over the whole record, and then appending the signature to the end. When you go to verify the record, all of the information you need is right there.

    This works well enough for most use cases, and everyone can pack up and go home. Nothing more to see here.

    Except…

    When you’re working with NoSQL databases, you often want systems to be able to write to additional fields, and since you’re working with schema-free blobs of data rather than a normalized set of relatable tables, the most sensible thing to do is to is to append this data to the same record.

    Except, oops! You can’t do that if you’re shoving a digital signature over the record. So now you need to specify which fields are to be included in the signature.

    And you need to think about how to model that in a way that doesn’t prohibit schema upgrades nor allow attackers to perform downgrade attacks. (See below.)

    I don’t have any specific real-world examples here that I can point to of this problem being solved well.

    Art: CMYKat

    Furthermore, as with preventing confused deputy and/or canonicalization attacks above, you must also include the fully qualified path of each field in the data that gets signed.

    As I said with encryption before, but also true here:

    Where your data lives is part of its identity, and MUST be authenticated.

    Soatok’s Rule of Database Cryptography

    This requirement holds true whether you’re using symmetric-key authentication (i.e. HMAC) or asymmetric-key digital signatures (e.g. EdDSA).

    Bonus: A Maximally Schema-Free, Upgradeable Authentication Design

    Art: Harubaki

    Okay, how do you solve this problem so that you can perform updates and upgrades to your schema but without enabling attackers to downgrade the security? Here’s one possible design.

    Let’s say you have two metadata fields on each record:

    1. A compressed binary string representing which fields should be authenticated. This field is, itself, not authenticated. Let’s call this meta-auth.
    2. A compressed binary string representing which of the authenticated fields should also be encrypted. This field is also authenticated. This is at most the same length as the first metadata field. Let’s call this meta-enc.

    Furthermore, you will specify a canonical field ordering for both how data is fed into the signature algorithm as well as the field mappings in meta-auth and meta-enc.

    {  "example": {    "credit-card": {      "number": /* encrypted */,      "expiration": /* encrypted */,      "ccv": /* encrypted */    },    "superfluous": {      "rewards-member": null    }  },  "meta-auth": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true   /* meta-enc */  ]),  "meta-enc": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false  /* example.superfluous.rewards-member */  ]),  "signature": /* -- snip -- */}

    When you go to append data to an existing record, you’ll need to update meta-auth to include the mapping of fields based on this canonical ordering to ensure only the intended fields get validated.

    When you update your code to add an additional field that is intended to be signed, you can roll that out for new records and the record will continue to be self-describing:

    • New records will have the additional field flagged as authenticated in meta-auth (and meta-enc will grow)
    • Old records will not, but your code will still sign them successfully
    • To prevent downgrade attacks, simply include a schema version ID as an additional plaintext field that gets authenticated. An attacker who tries to downgrade will need to be able to produce a valid signature too.

    You might think meta-auth gives an attacker some advantage, but this only includes which fields are included in the security boundary of the signature or MAC, which allows unauthenticated data to be appended for whatever operational purpose without having to update signatures or expose signing keys to a wider part of the network.

    {  "example": {    "credit-card": {      "number": /* encrypted */,      "expiration": /* encrypted */,      "ccv": /* encrypted */    },    "superfluous": {      "rewards-member": null    }  },  "meta-auth": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true,  /* meta-enc */    true   /* meta-version */  ]),  "meta-enc": compress_bools([    true,  /* example.credit-card.number */    true,  /* example.credit-card.expiration */    true,  /* example.credit-card.ccv */    false, /* example.superfluous.rewards-member */    true   /* meta-version */  ]),  "meta-version": 0x01000000,  "signature": /* -- snip -- */}

    If an attacker tries to use the meta-auth field to mess with a record, the best they can hope for is an Invalid Signature exception (assuming the signature algorithm is secure to begin with).

    Even if they keep all of the fields the same, but play around with the structure of the record (e.g. changing the XPath or equivalent), so long as the path is authenticated with each field, breaking this is computationally infeasible.

    Searchable Encryption

    If you’ve managed to make it through the previous sections, congratulations, you now know enough to build a secure but completely useless database.

    Art: CMYKat

    Okay, put away the pitchforks; I will explain.

    Part of the reason why we store data in a database, rather than a flat file, is because we want to do more than just read and write. Sometimes computer scientists want to compute. Almost always, you want to be able to query your database for a subset of records based on your specific business logic needs.

    And so, a database which doesn’t do anything more than store ciphertext and maybe signatures is pretty useless to most people. You’d have better luck selling Monkey JPEGs to furries than convincing most businesses to part with their precious database-driven report generators.

    Art: Sophie

    So whenever one of your users wants to actually use their data, rather than just store it, they’re forced to decide between two mutually exclusive options:

    1. Encrypting the data, to protect it from unauthorized disclosure, but render it useless
    2. Doing anything useful with the data, but leaving it unencrypted in the database

    This is especially annoying for business types that are all in on the Zero Trust buzzword.

    Fortunately, the cryptographers are at it again, and boy howdy do they have a lot of solutions for this problem.

    Order-{Preserving, Revealing} Encryption

    On the fun side of things, you have things like Order-Preserving and Order-Revealing Encryption, which Matthew Green wrote about at length.

    [D]atabase encryption has been a controversial subject in our field. I wish I could say that there’s been an actual debate, but it’s more that different researchers have fallen into different camps, and nobody has really had the data to make their position in a compelling way. There have actually been some very personal arguments made about it.

    Attack of the week: searchable encryption and the ever-expanding leakage function

    The problem with these designs is that they have a significant enough leakage that it no longer provides semantic security.

    From Grubbs, et al. (GLMP, 2019.)
    Colors inverted to fit my blog’s theme better.

    To put it in other words: These designs are only marginally better than ECB mode, and probably deserve their own poems too.

    Order revealing
    Reveals much more than order
    Softcore ECB

    Order preserving
    Semantic security?
    Only in your dreams

    Haiku for your consideration

    Deterministic Encryption

    Here’s a simpler, but also terrible, idea for searchable encryption: Simply give up on semantic security entirely.

    If you recall the AES_{De,En}crypt() functions built into MySQL I mentioned at the start of this article, those are the most common form of deterministic encryption I’ve seen in use.

     SELECT * FROM foo WHERE bar = AES_Encrypt('query', 'key');

    However, there are slightly less bad variants. If you use AES-GCM-SIV with a static nonce, your ciphertexts are fully deterministic, and you can encrypt a small number of distinct records safely before you’re no longer secure.

    From Page 14 of the linked paper. Full view.

    That’s certainly better than nothing, but you also can’t mitigate confused deputy attacks. But we can do better than this.

    Homomorphic Encryption

    In a safer plane of academia, you’ll find homomorphic encryption, which researchers recently demonstrated with serving Wikipedia pages in a reasonable amount of time.

    Homomorphic encryption allows computations over the ciphertext, which will be reflected in the plaintext, without ever revealing the key to the entity performing the computation.

    If this sounds vaguely similar to the conditions that enable chosen-ciphertext attacks, you probably have a good intuition for how it works: RSA is homomorphic to multiplication, AES-CTR is homomorphic to XOR. Fully homomorphic encryption uses lattices, which enables multiple operations but carries a relatively enormous performance cost.

    Art: Harubaki

    Homomorphic encryption sometimes intersects with machine learning, because the notion of training an encrypted model by feeding it encrypted data, then decrypting it after-the-fact is desirable for certain business verticals. Your data scientists never see your data, and you have some plausible deniability about the final ML model this work produces. This is like a Siren song for Venture Capitalist-backed medical technology companies. Tech journalists love writing about it.

    However, a less-explored use case is the ability to encrypt your programs but still get the correct behavior and outputs. Although this sounds like a DRM technology, it’s actually something that individuals could one day use to prevent their ISPs or cloud providers from knowing what software is being executed on the customer’s leased hardware. The potential for a privacy win here is certainly worth pondering, even if you’re a tried and true Pirate Party member.

    Just say “NO” to the copyright cartels.

    Art: CMYKat

    Searchable Symmetric Encryption (SSE)

    Forget about working at the level of fields and rows or individual records. What if we, instead, worked over collections of documents, where each document is viewed as a set of keywords from a keyword space?

    Art: CMYKat

    That’s the basic premise of SSE: Encrypting collections of documents rather than individual records.

    The actual implementation details differ greatly between designs. They also differ greatly in their leakage profiles and susceptibility to side-channel attacks.

    Some schemes use a so-called trapdoor permutation, such as RSA, as one of their building blocks.

    Some schemes only allow for searching a static set of records, while others can accommodate new data over time (with the trade-off between more leakage or worse performance).

    If you’re curious, you can learn more about SSE here, and see some open source SEE implementations online here.

    You’re probably wondering, “If SSE is this well-studied and there are open source implementations available, why isn’t it more widely used?”

    Your guess is as good as mine, but I can think of a few reasons:

    1. The protocols can be a little complicated to implement, and aren’t shipped by default in cryptography libraries (i.e. OpenSSL’s libcrypto or libsodium).
    2. Every known security risk in SSE is the product of a trade-offs, rather than there being a single winner for all use cases that developers can feel comfortable picking.
    3. Insufficient marketing and developer advocacy.
      SSE schemes are mostly of interest to academics, although Seny Kamara (Brown Univeristy professior and one of the luminaries of searchable encryption) did try to develop an app called Pixek which used SSE to encrypt photos.

    Maybe there’s room for a cryptography competition on searchable encryption schemes in the future.

    You Can Have Little a HMAC, As a Treat

    Finally, I can’t talk about searchable encryption without discussing a technique that’s older than dirt by Internet standards, that has been independently reinvented by countless software developers tasked with encrypting database records.

    The oldest version I’ve been able to track down dates to 2006 by Raul Garcia at Microsoft, but I’m not confident that it didn’t exist before.

    The idea I’m alluding to goes like this:

    1. Encrypt your data, securely, using symmetric cryptography.
      (Hopefully your encryption addresses the considerations outlined in the relevant sections above.)
    2. Separately, calculate an HMAC over the unencrypted data with a separate key used exclusively for indexing.

    When you need to query your data, you can just recalculate the HMAC of your challenge and fetch the records that match it. Easy, right?

    Even if you rotate your keys for encryption, you keep your indexing keys static across your entire data set. This lets you have durable indexes for encrypted data, which gives you the ability to do literal lookups for the performance hit of a hash function.

    Additionally, everyone has HMAC in their toolkit, so you don’t have to move around implementations of complex cryptographic building blocks. You can live off the land. What’s not to love?

    Hooray!

    However, if you stopped here, we regret to inform you that your data is no longer indistinguishable from random, which probably undermines the security proof for your encryption scheme.

    How annoying!

    Of course, you don’t have to stop with the addition of plain HMAC to your database encryption software.

    Take a page from Troy Hunt: Truncate the output to provide k-anonymity rather than a direct literal look-up.

    “K-What Now?”

    Imagine you have a full HMAC-SHA256 of the plaintext next to every ciphertext record with a static key, for searchability.

    Each HMAC output corresponds 1:1 with a unique plaintext.

    Because you’re using HMAC with a secret key, an attacker can’t just build a rainbow table like they would when attempting password cracking, but it still leaks duplicate plaintexts.

    For example, an HMAC-SHA256 output might look like this: 04a74e4c0158e34a566785d1a5e1167c4e3455c42aea173104e48ca810a8b1ae

    Art: CMYKat\

    If you were to slice off most of those bytes (e.g. leaving only the last 3, which in the previous example yields a8b1ae), then with sufficient records, multiple plaintexts will now map to the same truncated HMAC tag.

    Which means if you’re only revealing a truncated HMAC tag to the database server (both when storing records or retrieving them), you can now expect false positives due to collisions in your truncated HMAC tag.

    These false positives give your data a discrete set of anonymity (called k-anonymity), which means an attacker with access to your database cannot:

    1. Distinguish between two encrypted records with the same short HMAC tag.
    2. Reverse engineer the short HMAC tag into a single possible plaintext value, even if they can supply candidate queries and study the tags sent to the database.
    Art: CMYKat\

    As with SSE above, this short HMAC technique exposes a trade-off to users.

    • Too much k-anonymity (i.e. too many false positives), and you will have to decrypt-then-discard multiple mismatching records. This can make queries slow.
    • Not enough k-anonymity (i.e. insufficient false positives), and you’re no better off than a full HMAC.

    Even more troublesome, the right amount to truncate is expressed in bits (not bytes), and calculating this value depends on the number of unique plaintext values you anticipate in your dataset. (Fortunately, it grows logarithmically, so you’ll rarely if ever have to tune this.)

    If you’d like to play with this idea, here’s a quick and dirty demo script.

    Intermission

    If you started reading this post with any doubts about Cendyne’s statement that “Database cryptography is hard”, by making it to this point, they’ve probably been long since put to rest.

    Art: Harubaki

    Conversely, anyone that specializes in this topic is probably waiting for me to say anything novel or interesting; their patience wearing thin as I continue to rehash a surface-level introduction of their field without really diving deep into anything.

    Thus, if you’ve read this far, I’d like to demonstrate the application of what I’ve covered thus far into a real-world case study into an database cryptography product.

    Case Study: MongoDB Client-Side Encryption

    MongoDB is an open source schema-free NoSQL database. Last year, MongoDB made waves when they announced Queryable Encryption in their upcoming client-side encryption release.

    Taken from the press release, but adapted for dark themes.

    A statement at the bottom of their press release indicates that this isn’t clown-shoes:

    Queryable Encryption was designed by MongoDB’s Advanced Cryptography Research Group, headed by Seny Kamara and Tarik Moataz, who are pioneers in the field of encrypted search. The Group conducts cutting-edge peer-reviewed research in cryptography and works with MongoDB engineering teams to transfer and deploy the latest innovations in cryptography and privacy to the MongoDB data platform.

    If you recall, I mentioned Seny Kamara in the SSE section of this post. They certainly aren’t wrong about Kamara and Moataz being pioneers in this field.

    So with that in mind, let’s explore the implementation in libmongocrypt and see how it stands up to scrutiny.

    MongoCrypt: The Good

    MongoDB’s encryption library takes key management seriously: They provide a KMS integration for cloud users by default (supporting both AWS and Azure).

    MongoDB uses Encrypt-then-MAC with AES-CBC and HMAC-SHA256, which is congruent to what Signal does for message encryption.

    How Is Queryable Encryption Implemented?

    From the current source code, we can see that MongoCrypt generates several different types of tokens, using HMAC (calculation defined here).

    According to their press release:

    The feature supports equality searches, with additional query types such as range, prefix, suffix, and substring planned for future releases.

    MongoDB Queryable Encryption Announcement

    Which means that most of the juicy details probably aren’t public yet.

    These HMAC-derived tokens are stored wholesale in the data structure, but most are encrypted before storage using AES-CTR.

    There are more layers of encryption (using AEAD), server-side token processing, and more AES-CTR-encrypted edge tokens. All of this is finally serialized (implementation) as one blob for storage.

    Since only the equality operation is currently supported (which is the same feature you’d get from HMAC), it’s difficult to speculate what the full feature set looks like.

    However, since Kamara and Moataz are leading its development, it’s likely that this feature set will be excellent.

    MongoCrypt: The Bad

    Every call to do_encrypt() includes at most the Key ID (but typically NULL) as the AAD. This means that the concerns over Confused Deputies (and NoSQL specifically) are relevant to MongoDB.

    However, even if they did support authenticating the fully qualified path to a field in the AAD for their encryption, their AEAD construction is vulnerable to the kind of canonicalization attack I wrote about previously.

    First, observe this code which assembles the multi-part inputs into HMAC.

    /* Construct the input to the HMAC */uint32_t num_intermediates = 0;_mongocrypt_buffer_t intermediates[3];// -- snip --if (!_mongocrypt_buffer_concat (  &to_hmac, intermediates, num_intermediates)) {   CLIENT_ERR ("failed to allocate buffer");   goto done;}if (hmac == HMAC_SHA_512_256) {   uint8_t storage[64];   _mongocrypt_buffer_t tag = {.data = storage, .len = sizeof (storage)};   if (!_crypto_hmac_sha_512 (crypto, Km, &to_hmac, &tag, status)) {      goto done;   }   // Truncate sha512 to first 256 bits.   memcpy (out->data, tag.data, MONGOCRYPT_HMAC_LEN);} else {   BSON_ASSERT (hmac == HMAC_SHA_256);   if (!_mongocrypt_hmac_sha_256 (crypto, Km, &to_hmac, out, status)) {      goto done;   }}

    The implementation of _mongocrypt_buffer_concat() can be found here.

    If either the implementation of that function, or the code I snipped from my excerpt, had contained code that prefixed every segment of the AAD with the length of the segment (represented as a uint64_t to make overflow infeasible), then their AEAD mode would not be vulnerable to canonicalization issues.

    Using TupleHash would also have prevented this issue.

    Silver lining for MongoDB developers: Because the AAD is either a key ID or NULL, this isn’t exploitable in practice.

    The first cryptographic flaw sort of cancels the second out.

    If the libmongocrypt developers ever want to mitigate Confused Deputy attacks, they’ll need to address this canonicalization issue too.

    MongoCrypt: The Ugly

    MongoCrypt supports deterministic encryption.

    If you specify deterministic encryption for a field, your application passes a deterministic initialization vector to AEAD.

    MongoDB documentation

    We already discussed why this is bad above.

    Wrapping Up

    This was not a comprehensive treatment of the field of database cryptography. There are many areas of this field that I did not cover, nor do I feel qualified to discuss.

    However, I hope anyone who takes the time to read this finds themselves more familiar with the subject.

    Additionally, I hope any developers who think “encrypting data in a database is [easy, trivial] (select appropriate)” will find this broad introduction a humbling experience.

    Art: CMYKat

    https://soatok.blog/2023/03/01/database-cryptography-fur-the-rest-of-us/

    #appliedCryptography #blockCipherModes #cryptography #databaseCryptography #databases #encryptedSearch #HMAC #MongoCrypt #MongoDB #QueryableEncryption #realWorldCryptography #security #SecurityGuidance #SQL #SSE #symmetricCryptography #symmetricSearchableEncryption

    #appliedcryptography #blockciphermodes #cryptography #databasecryptography #databases #encryptedsearch