Conversation

Notices

1. Embed this notice
   feld (feld@bikeshed.party)'s status on Wednesday, 05-Jul-2023 12:40:43 JST feld

   in reply to

   • Jeff Martin
   • varx/tech
   > Ugh. Privacy is hard. I'm not sure contact graph anonymity is worth it anymore.
   
   Wouldn't it be simpler to just borrow whatever crypto implementation and ring signatures that Monero has? I bet that would work great. Just a weird thought I had browsing this thread ...
   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:44 JST Jeff Martin

     in reply to

     • varx/tech

     @varx oh for sure, those are definitely risks. No way to really know though. I'll just design it the best way I can think of and hope for the best. I'm betting that sticking to really basic applications like authenticated encryption and signing will get me pretty far. I was doing pretty great until I tried to do anonymous multi-recipient encryption. Think I've about got it though.

   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:44 JST Jeff Martin

     in reply to

     • varx/tech

     @varx Oh snap. I think I poked a huge hole in my contact graph anonymity scheme. :blobcatverysad:

     The senders can't be anonymous for ... reasons. But the hope was at least the recipients can be anonymous and that would be enough to prevent eavesdroppers from harvesting contact graphs.

     Turns out I can anonymize message recipient lists all I want, but as soon as a recipient ever responds, their signature is on the response. A simple signature verification operation using a list of all known identities could very quickly reveal the responder's (and therefore the recipient's) identity.

     I mean sure, I could setup shared secrets for every pair of identities to hide identity info from eavesdroppers, but managing that many secrets would be a huge pain in the ass. Do not want!

     Ugh. Privacy is hard. I'm not sure contact graph anonymity is worth it anymore.

   • Embed this notice
     varx/tech (varx@infosec.exchange)'s status on Wednesday, 05-Jul-2023 12:40:46 JST varx/tech

     in reply to

     • Jeff Martin

     @cuchaz There's some truth to that. For instance, the top post-quantum schemes seem to have pretty large keys, which might violate some protocol assumptions.

     But they also might just work really differently in ways that don't match either RSA *or* ECC. Think of how ECC relies on key exchange rather than RSA's traditional asymmetric encryption, and doesn't have a notion of unifying encryption and signing. It seems to me there's a not-inconsiderable chance of further fundamental changes in the available primitives. Without being a serious cryptographer (let alone one who is up-to-date and has an eye for trends) it's impossible for me to make that kind of prognostication, though! I think keeping an eye on later versions of the protocol being able to swap out cryptosystems at a lower level makes sense, but I feel like it would be easy to unduly constrain the overall protocol.

     (That said, all of the round-4 NIST PQ submissions appear to describe KEMs, making them more similar in shape to public-key ECC than to RSA, if I'm not totally misunderstanding things.)

   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:48 JST Jeff Martin

     in reply to

     • varx/tech

     @varx ECC has a few quality-of-life improvements over RSA for sure. But if I tailor my schemes too closely to how ECC works, then my high-level stuff is less likely be compatible with the new post-quantum thing, or whatever the future best primitives end up being. The hope was that by supporting RSA and ECC at first, the high-level stuff would be more likely to survive future developments without breaking backwards compatibility. Ie, people with different key types should still be able to talk to each other. It's easy to forget to make that happen when there's only one key type.

   • Embed this notice
     varx/tech (varx@infosec.exchange)'s status on Wednesday, 05-Jul-2023 12:40:49 JST varx/tech

     in reply to

     • Jeff Martin

     @cuchaz Another benefit is that keys are small and unstructured. Any 32 byte string can be converted to a key via some bit-masking—you create them from random data (or a hash output). So the keys are fast and simple to generate, they're small, and they can be readily derived deterministically from a passphrase if you're into that sort of thing. (And if you have both X25519 and Ed25519 keys, they can both come from the same shared seed, with a bit of context separation for safety.)

   • Embed this notice
     varx/tech (varx@infosec.exchange)'s status on Wednesday, 05-Jul-2023 12:40:51 JST varx/tech

     in reply to

     • Jeff Martin

     @cuchaz It's also pretty fast. The marginal cost on my 10+ year old laptop of performing an encryption or decryption is less than 80 µs. "Brute forcing" a list of 1000 small items until I find the one that's for me would take under 100 ms, which seems fine.

     40k items would take about 3 seconds to process. At that scale I'd want to start using k-anonymity for sure; including just an 8-bit public key prefix would bring that down to 12 ms.

   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:53 JST Jeff Martin

     in reply to

     • varx/tech

     @varx Btw, another option is dropping support for RSA entirely which would give me access to ECDH. Getting a shared secret from two keypairs for free feels like a superpower and I don't know how to do that with RSA. It might be the most compelling reason I've seen yet for why ECC is better than RSA.

   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:54 JST Jeff Martin

     in reply to

     • varx/tech

     @varx yeah, it's a tricky problem. I'm currently looking into using k-anonymity to probabilistically anonymize the list. Ie, each recipient will have to do O(log(n)) checks to confirm their number, but an attacker will never be able to get an exact match.

     Or set up some kind of shared secret or other anonymized id to use instead of the real id. This is actually a much simpler approach, but due do where the API layers land wrt ecapsulation, it's harder to design the software so each API layer makes sense.

     Ugh, why is everything so difficult? :blobcat_thisisfine:

   • Embed this notice
     varx/tech (varx@infosec.exchange)'s status on Wednesday, 05-Jul-2023 12:40:55 JST varx/tech

     in reply to

     • Jeff Martin

     @cuchaz Cavern has a problem that's very similar; my solution is for the friends to have to brute-force the list until they find something they can decrypt, but not have to do this *often*.

     Not sure if this is appropriate in your use-case, but consider whether there's a way to "stabilize" the numbers you're sending your friends; if they can act optimistically on the presumption of the number not having changed since last time (if that's even a meaningful concept) then they get to skip the expensive step whenever they're right.

     Barring that, it feels like this might require some fancy math involving combining multiple people's public keys. :-/

   • Embed this notice
     Jeff Martin (cuchaz@gladtech.social)'s status on Wednesday, 05-Jul-2023 12:40:56 JST Jeff Martin

     Howdy #cryptography friends,

     Let's say I have 1000 friends (haha, I know, right?) and I want to send each of them a number. If I put all the numbers into a list and send the list to all my friends, that sort of works, but each friend won't know which number is theirs.

     So I'd like some way to tag each number in the list so each friend can quickly tell which number is theirs, but no one else can. ie, something faster than linear time search through the list would be ideal, but I'd settle for something linear if the constants are small. Maybe something like string equality as the match operation, but not a decryption.

     And if someone who isn't my friend sees the list with all the tagged numbers, they shouldn't be able to tell who any of my friends are by using the tags somehow.

     Me and all my 1000 friends (lol, it's still funny) all have asymmetric keypairs, so we can use those.

     Is this a well-studied problem that has a name I don't know about yet? Maybe there are special-purpose tools that are a good fit for this?

     Or maybe there's some clever scheme using encryption that solves this? I feel like a deterministic encryption of some well-known message for each friend gets pretty close. Then add a list-level nonce to make it randomized for each list, but not each friend. Then a friend can do the deterministic encryption using the nonce and scan through the list pretty quickly to find their number. But my asymmetric encryption primitive is randomized, so I can't quite make it work that way unless I use a different primitive.

     Although, if the message to be encrypted deterministically is well-known, and the goal is not actually to protect the message, that kind of suggests encryption is the wrong tool here. I'm looking for some kind of tag that is only recognizable by the holder of the private key.

     Thoughts?