HN Reader

That is well-written and a potentially good application for crypto-shredding, which has a lot of drawbacks in other contexts.

The issue with crypto-shredding in many applications is that it aggressively pessimizes the software architectures possible in support of the data model. For things like databases and analytics, that feature increases the required hardware footprint -- compute and storage -- by orders of magnitude. The loss of efficiency has little to do with the crypto per se, since hardware support makes that cheap, but with how the change in representation interacts with idiomatic data structures and algorithms for high-efficiency data systems.

Many system internals are essentially a bag of tricks for constructing the maximally compressive representation of the important relationships in a data model while preserving practical tractability of operations over the data model. Crypto-shredding architectures have the effect of "encrypting" before "compressing", rendering the latter moot.

Very good, but needs more furry art.

Note that “PII” is American terminology, and it has a much more restricted meaning than the European term “personal data”. https://en.wikipedia.org/wiki/Personal_data

For all that the author doesn’t like exotic crypto, this seems like the sort of problem that the sort of fancy cryptography that the Ethereum folks love would actually be appropriate for. The goals are, approximately:

1. There exists a log, and the log follows certain rules, and everyone agrees on a summary of the log from which log entries can be validated and from which the fact that the log follows the rules can be validated.

2. One can validate a record without retrieving the whole log.

3. Appends can be done, and new summaries generated, without access to some of the entries.

Cryptocurrency, as far as I know, does not care about #3, whereas this project does. But maybe similar sorts of exotic crypto could generate a stronger form of shredding: a scheme where deleted PII only persists in the form of a constant or logarithmic size ever changing summary. It’s a bit hard to argue that, say, 10kb of data contains PII from a million users.

Not sure I'm a big fan of focusing on concrete cryptographic primitives; I suspect all you need is a commitment scheme and change the leaves to be commitments to the data (instead of the data itself), but I found it quite difficult to ascertain whether this would meet the requirements

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 :)

I’m confused about the purpose of truncating the salt.

How does the attacker learn anything about the salt without breaking Argon2id first? It’s not like the salt is included in the Sigsum ledger.

If the attacker did somehow learn the salt (truncated HMAC), it seems like that would immediately break security, regardless of truncation. Suppose the attacker starts with a dictionary of all possible Actor IDs, which seems reasonable, and that they calculate the truncated HMAC for every possibility until it matches. Due to the truncation, the attacker may get one or more false username matches in addition to the true username match. But if the attacker has narrowed down the username to two or three possibilities, they’ve already basically won. And they could just check the possibilities against Argon2id to learn which one it is.

On the other hand, if the attacker doesn’t know anything about the salt, then why would it matter if the salt did uniquely identify a user? How would they “observe that the recent-merkle-root is the same for two messages, but their salts differ”?

It’s quite possible that I’m misunderstanding something. I am not a cryptography expert.

But more broadly, it just seems wrong to use a salted password hash but have the salt be based on the same password that’s being hashed. I don’t think it’s _insecure_, because the salt also includes a high-entropy part (the recent-merkle-root). But I don’t see how it increases security at all. The security should be the same as if the salt only included the high-entropy part.

In other words, the entire “HMAC -> truncate -> Argon2id” process can be seen as a password hash in its own right, where the input consists of the secret username, plus various bits of public information such as the recent-merkle-root. But that’s essentially a form of rolling your own crypto, and it’s unnecessary. Argon2id is already a secure password hash by itself, so you can just feed that data directly to it.

HN must also respect the principles of the right to be forgotten.

There is no easy way to delete your comments or profile.

It is a interesting idea.

Somehow, when I accessed it first I got a HTML file, but then I tried again and got JSON instead. Why is that?

> Counter Mode (CTR) is a secure way to turn a block cipher into a stream cipher.

Note that block ciphers can be reversible. CTR mode does not require that the block cipher is reversible. However, it can be made non-reversible, which is how ChaCha20 works; it is a block cipher in CTR mode, but with an extra step to make it difficult to reverse.

Honestly, I don't get it. Maybe I don't know enough about the fediverse?

Doesn't the fediverse already have a mechanism where each user can set a profile, which everyone else has a common view of and other people can't change? Couldn't a parallel mechanism distribute public keys in a similar way?

What's the issue here - that the server where you have your account can replace your keys?

I know SSL's "certificate transparency" tries to detect replaced and mis-issued certificates after the fact, by putting them all into an immutable log that can be searched by domain name. It doesn't stop the attack, but it at least makes it detectable after the fact. Yet if the entries in the log can be deleted, so there's no longer a log that would prove an attack had happened, wouldn't that prevent the log fulfilling its sole purpose?