4 ms·

Let's think about the problem qualitatively, without worrying about specific protocol details, KDF's, AES modes, or bit lengths. Let us say each DB record is a

by csense 2y ago

Let's think about the problem qualitatively, without worrying about specific protocol details, KDF's, AES modes, or bit lengths. Let us say each DB record is a JSON string containing a name and a base58-encoded public key, for example record[57] = '{"name" : "bob", "pubkey" : "1A1zP1e"}'. If you have some hash function H = sha256 let us say, you could calculate h = H('{"name" : "bob", "pubkey" : "1A1zP1e"}')[:N] and then set record[57] = h (I'll use a 24-bit h = 71b686 for my examples, OP suggests a 48-bit). Then when Bob asks for his data to be redacted (say, via GDPR-nuke), you can forget 71b686=H('{"name" : "bob", "pubkey" : "1A1zP1e"}'), leaving the DB with just record[57] = 71b686 but this number is meaningless. (You can be extra sure it's meaningless by encouraging / requiring clients to put a high-entropy throwaway "salt" field inside the JSON.) Note, you can't just del record[57] because that breaks the data store's append-only property. You want to stream updates to your DB to (untrusted, decentralized) clients to host their own replicas (so they can independently verify you're answering your queries honestly). Those client replicas need to handle queries of the form SELECT i WHERE record[i]["name"] == "bob", or at least verify that a purported response to SELECT i WHERE record[i]["name"] == "bob" is correct. This seems...tricky, if you can't give the clients the "name" field because when you can't trust the client replicas to "forget" it when they're "supposed" to. Unfortunately, OP is clouded with low-level details to the point that I'm honestly not sure if OP has genuinely discovered a clever way to solve the tricky part, or if OP's claimed solution doesn't actually work. For that matter, I'm not even convinced the problem OP's trying to solve is possible. How can the replicas verify a query result without having access to the redactable data? I don't understand it at all. OP if you're reading, clarification would be most welcome :)

some_furry 2y ago
> If you have some hash function H = sha256 let us say, you could calculate h = H('{"name" : "bob", "pubkey" : "1A1zP1e"}')[:N] and then set record[57] = h (I'll use a 24-bit h = 71b686 for my examples, OP suggests a 48-bit). You're responding to an earlier revision of the blog post, and the design has been updated to not truncate salts this way (nor store them at all), based on feedback on the design. > This seems...tricky, if you can't give the clients the "name" field because when you can't trust the client replicas to "forget" it when they're "supposed" to. The ciphertext is the aspect that's committed to the Merkle tree. The plaintext and the key are not committed to the Merkle tree, and can be freely deleted. That's the important bit. As for your other concern, the replication aspect is specified clearly. https://github.com/fedi-e2ee/public-key-directory-specification/blob/main/Specification.md#gossip-protocol https://github.com/fedi-e2ee/public-key-directory-specificat... If a non-conformant replica persists copies of the plaintext indefinitely, then you can now use the same legal process to request erasure from the replica. If they do not comply, then you have the same amount of legal recourse you had to begin with. This becomes a lawyer problem, not a technology problem. > How can the replicas verify a query result without having access to the redactable data? The thing you can continue to verify, after a record has been forgotten, is all of the other records in the ledger. Before erasure, that includes the record in question. After erasure, you shouldn't have anything to verify, except that history hasn't been altered beyond the decryption key being zeroed out. If you assert your right to be forgotten, the system should forget. You can no longer be verified, because as far as the system is concerned, the record in scope does not exist. But either way, history remains intact. You don't break the Merkle proofs. You can erase records by zeroing out the key, but you cannot alter them in any other way. The plaintext commitment prevents a server that's committed to a ciphertext, Enc(k1, Alice), from responding with a plaintext for Bob. The commitment is a slow hash that's included in the calculation of the authentication tag over the ciphertext (which is what's committed to the Merkle tree). The tree survives. If this still doesn't make sense, check the docs on GitHub. > OP if you're reading, clarification would be most welcome :) Here's a short and oversimplified workflow to help illustrate it: Alice -> Directory: [Encrypted Data], [Keys] Directory -> SigSum: [Encrypted Data] Bob -> Directory: [Alice]? Directory -> Bob: [Encrypted Data], [Plaintext], [Merkle Proofs over Encrypted Data] Is that easier to follow? If Alice later requests her keys deleted, then you end up with: Bob -> Directory: [Alice]? Directory -> Bob: [Encrypted Data], nil, [Merkle Proofs over Encrypted Data]

by csense 2y ago

some_furry 2y ago

> If you have some hash function H = sha256 let us say, you could calculate h = H('{"name" : "bob", "pubkey" : "1A1zP1e"}')[:N] and then set record[57] = h (I'll use a 24-bit h = 71b686 for my examples, OP suggests a 48-bit). You're responding to an earlier revision of the blog post, and the design has been updated to not truncate salts this way (nor store them at all), based on feedback on the design. > This seems...tricky, if you can't give the clients the "name" field because when you can't trust the client replicas to "forget" it when they're "supposed" to. The ciphertext is the aspect that's committed to the Merkle tree. The plaintext and the key are not committed to the Merkle tree, and can be freely deleted. That's the important bit. As for your other concern, the replication aspect is specified clearly. https://github.com/fedi-e2ee/public-key-directory-specification/blob/main/Specification.md#gossip-protocol https://github.com/fedi-e2ee/public-key-directory-specificat... If a non-conformant replica persists copies of the plaintext indefinitely, then you can now use the same legal process to request erasure from the replica. If they do not comply, then you have the same amount of legal recourse you had to begin with. This becomes a lawyer problem, not a technology problem. > How can the replicas verify a query result without having access to the redactable data? The thing you can continue to verify, after a record has been forgotten, is all of the other records in the ledger. Before erasure, that includes the record in question. After erasure, you shouldn't have anything to verify, except that history hasn't been altered beyond the decryption key being zeroed out. If you assert your right to be forgotten, the system should forget. You can no longer be verified, because as far as the system is concerned, the record in scope does not exist. But either way, history remains intact. You don't break the Merkle proofs. You can erase records by zeroing out the key, but you cannot alter them in any other way. The plaintext commitment prevents a server that's committed to a ciphertext, Enc(k1, Alice), from responding with a plaintext for Bob. The commitment is a slow hash that's included in the calculation of the authentication tag over the ciphertext (which is what's committed to the Merkle tree). The tree survives. If this still doesn't make sense, check the docs on GitHub. > OP if you're reading, clarification would be most welcome :) Here's a short and oversimplified workflow to help illustrate it: Alice -> Directory: [Encrypted Data], [Keys] Directory -> SigSum: [Encrypted Data] Bob -> Directory: [Alice]? Directory -> Bob: [Encrypted Data], [Plaintext], [Merkle Proofs over Encrypted Data] Is that easier to follow? If Alice later requests her keys deleted, then you end up with: Bob -> Directory: [Alice]? Directory -> Bob: [Encrypted Data], nil, [Merkle Proofs over Encrypted Data]