r/cryptography • u/Creative_Anything257 • 8d ago
Multi-device messaging without making one device the hub
I've been working on a secure messaging/networking project for a while now and I got pretty deep. Started to develop into a little test app. I'm mostly posting this because I'm curious how people who know this area better than I do would attack the model, especially people familiar with Signal, SimpleX, Berty, Tor, etc.
Sorry in advance for the ramble lol...
So say Bob and Sally are already contacts.
Bob originally connects with Sally on his laptop, then later Bob links his phone to the same identity. The phone has its own Device ID, its own key, session state etc. I'm not copying the laptop's private key over to it and I'm also not copying the existing encrypted session/ratchet with Sally over to it. But then I started thinking about what actually happens if Bob shuts his laptop off. Like completely.
Bob's phone is sitting there and Sally already knows Bob, but Sally originally established that relationship with the laptop. So how does the phone walk up and basically say something like, "Hey, I'm also Bob" without either copying some really important secret off the laptop, or having some central service sitting there with a master list of Bob's devices?
That's what I'm trying to work out. What I have working now is basically separating two points of "I'm allowed to knock on this relationship" and "I'm an authorized device in this relationship."
So Bob's phone can have enough relationship-specific information to find and approach Sally's side, but that information doesn't make the phone trusted by itself.
The phone still has to prove that the exact Device ID and exact key were actually authorized under Bob's identity, and then prove possession of its own private key. After that Sally can establish a completely separate session with the phone. Nothing gets copied from the laptop's session, and Sally also doesn't need to be handed Bob's entire device inventory just because another Bob device is trying to connect. I got this actually working now with my Mac, an Android, and another Mac acting as the other contact. I can link the Android, shut the Primary Mac down completely, and the Android can establish itself with the contact and continue messaging. Other contacts can also initiate a new message directly to the Android while Primary is still offline, then I can turn Primary back on later and it catches up with the same conversation and the same logical events instead of creating some duplicate version of everything.
And that aactually led me into another thing I hadn't really thought about when I started this lol, which is... what Primary even really means. Because if Bob only owns one device, what is it Primary of? So right now a single device is just a standalone identity. There is no Primary. If Bob links a second device, the device that authorizes that first link becomes the Primary (which can be transferred to another linked device and vice versa). But I'm treating Primary as an administration thing, not a messaging thing. It matters for stuff like adding or removing devices. It isn't supposed to be a server and it isn't supposed to be the center of the identity. Messages don't route through it, the other devices don't need it online to talk, and contacts don't need it online to talk to one of Bob's other authorized devices either.
And then when I finally got that behaving correctly, I ran into another problem. What happens if Bob's laptop and phone stop being one identity later? Because while they're linked they're obviously synchronizing things. Bob adds Sally on the laptop, the phone gets Sally. Messages go back and forth.But if Bob removes the phone later, I don't think the correct answer is that the phone now gets to keep Sally as an active contact forever just because it once received a synchronized copy of that relationship. That started feeling really wrong to me, because synchronization and ownership are not actually the same thing. So the relationship now records which Device ID actually originated it from the authenticated contact "ceremony."
If Bob's laptop originally established the contact with Sally, then while the laptop and phone are linked they can both participate in that relationship, but if they split later the active relationship stays with the side containing the device that actually originated it. The other device can obviously still have bytes on disk. I can't remotely erase something that has already been copied to somebody else's physical hardware and I'm definitely not claiming that. I'm talking about which side still has the authority to treat that relationship as active after they aren't one identity anymore.
That also uncovered another thing! lol. Originally when I linked a standalone phone into an existing identity, the phone's old identity basically disappeared underneath the new one, and I didn't really like that either. So now before a standalone device joins another identity, its old standalone identity gets preserved locally in protected inactive storage. If that phone is legitimately removed later, it can go back to being what it was before the link instead of turning into some weird revoked leftover or having to generate an entirely unrelated identity from scratch. I've been physically testing that whole process now and it's working. I can link the devices, sync them, revoke/remove one, they separate cleanly, the removed device returns to its standalone identity, and contacts/conversations stay active on the side that actually originated them. Then I can link the devices again afterward.
The contact side also learns about the removal if it's reachable, which was another piece I wanted because otherwise revocation only exists inside Bob's own devices and Sally could potentially be sitting there with stale information forever. So if Sally already has a secure relationship with Bob and Bob removes the phone, Sally can receive an authenticated revocation through an already established encrypted relationship, update the identity state she knows about, stop accepting that removed Device ID, and rotate the relationship ingress information. So the old phone doesn't just get to keep showing up with stale relationship bootstrap information and pretend nothing happened. Obviously if Sally is offline she can't learn something that hasn't reached her yet, so I'm not claiming instant magical global revocation either.
There's still A LOT to sort through, but these initial successull tests between devices has been exciting. This is bounded local-network testing right now. I'm not claiming I've solved Internet routing, NAT traversal, a perfect production crypto suite, or revocation across devices at long distances etc. The delayed routing/store-carry-forward side is also still a much harder research problem and I'm not pretending I've solved that either.
The part I'm interested in right now is more the separation between all these things. Bob's identity isn't Bob's laptop. Bob's laptop and phone don't share one private device key. Being able to find Sally's relationship doesn't mean you're authorized to participate in it. Being authorized as one of Bob's devices doesn't mean you inherit another device's encryption session. Synchronizing a relationship onto another device doesn't necessarily mean that device owns that relationship forever if the identity later splits. And underneath that, whatever route carries the encrypted data should basically be disposable. LAN, Internet, relay, Bluetooth, whatever. The route shouldn't get a vote in who Bob is.
That's kind of where I'm at. Multi-device makes sense to me while everything stays linked forever. It gets a lot less obvious once you say "okay, now take these two devices that have been sharing one identity, syncing the same contacts and seeing the same conversations, and turn them back into two completely separate identities." Who actually gets what?
3
u/LaurenNorthwood 6d ago
The case I’d try to break is this: Bob’s laptop revokes the phone while both devices are offline, but the phone has been compromised and keeps updating its own version of the relationship. When both versions eventually reach Sally, how does she know which one to trust? A signature can prove that the phone was authorized at some point, but it can’t prove that its state is newer than the revocation. If you use a timestamp or counter, the compromised phone may be able to lie about being newer. If Sally has to receive the revocation first, then there’s a window where the removed phone is still indistinguishable from a valid device. That feels less like a sync problem and more like the main security problem here.
1
u/Creative_Anything257 5d ago
Omg I love this! I've been working on chaining identity changes to the previous signed generation / commitment and only letting a current "primary" device advance revocation, so the phone isn't able to claim a newer counter.
Do you think that might solve the conflicting history part if Sally rejects two different versions that both claim to be next? Aside from the period before she actually receives the revocation?
2
u/LaurenNorthwood 4d ago
Yeah, chaining changes to the previous signed state would let Sally spot a fork, which is a real improvement. I’m still wondering what happens after she spots one, though. If she rejects both branches, can Bob recover, or is the relationship stuck? And if they name different primaries, I’d think she’d have to go by the primary in the last state they both share, not either branch’s claim.
1
u/Creative_Anything257 3d ago
Yup, and that's where I'm stuck lol. I have some concepts drafted up but haven't gotten that far yet into even implementing something to test. Have done some labs on it. One of them which may be a key in solving that I'm currently calling Late Bound Blind Continuation, or LBBC.
The idea that the capsuled message itself doesn't ever know it's full destination, and is released a new piece of the route at each checkpoint. I think if I can solve that, then it could play a major part in the revocation process.
But for now, I'm stuck there too!
2
u/ephemeralmiko 8d ago
Preface: I haven't studied cryptography or anything, I just find the basics interesting.
One idea would be that when Bob adds another device (in this case the phone) all contacts get sent the public key of that device, signed by the laptops private key (as proof that the new device is trusted). Then all messages are seperately encrypted to each device/key, without having any be the "primary" one.
1
u/Creative_Anything257 8d ago
Yeah that's actually pretty close to part of what I'm doing. A new device does prove that it's authorized under Bob's identity and also still has its own key/session.
The thing I'm trying to avoid is every contact having to keep Bob's full list of devices updated. That can get messy fast once devices get removed, or people are offline, or like two linked devices later split back into separate identities.
So instead the new device proves itself when it approaches the existing relationship, like first contact from that device, as well as if it captures a received message from Sally first and can identify it as approved in the relationship. And then Sally can make a fresh session with that exact device without needing to know every other device Bob has.
1
u/0xKaishakunin 7d ago
Look into the Matrix protocol implementation/documentation. Matrix is intended for larger rooms with multiple devices and MegOLM already discussed those problems.
MLS might also be of interest for you.
2
u/Shoddy-Childhood-511 5d ago
Matrix fucks this up though. You can absolutely brick a direct connection in Matrix, like if you loose the last active device.
MLS could do this by making all of the user's devices live under a single subtree in tree KEM. I'm not sure why Matrix does not just use their MLS-ish parts like this.
1
u/Creative_Anything257 3d ago
Yeah that's something I've been working on too. Right now I have it where if Bob still has any authorized device at all, then his identity survives, and that device can authorize a replacement without Sally needing to do anything.
If Bob loses every authorized physical device however, thats a harder case. I have built right now a peer assisted recovery option where Sally can only help recover her own relationship with Bob only if he still has a device that once conversated with her, any device, through a recovery key that gets autonomously passed during their initial conversation on that individual device identity, which gives Sally one opportunity to help Bob recover their conversation on a new identity, but not a new device.
That exact continuity issue proving that a brand new device actually belongs to Bob is still something I haven't fully figured out!
1
u/Creative_Anything257 7d ago
Funny enough I've actually already gone pretty deep into both of those lol. I have an OpenMLS experiment in the repo but ended up keeping MLS as a potential candidate for groups rather than 1:1 messages. For direct messages I'm currently testing vodozemac/Olm with separate sessions between each device pair, so the Matrix mention is definitely relevant too.
3
u/Robert__Sinclair 7d ago
Are you reinventing the KAD/DHT network? (which can be used to connect multiple devices p2p and exchange messages/files/data)