On Tue, May 27, 2014 at 9:50 PM, Joseph Bonneau <[email protected]> wrote: >> >> Delivery attempts contain (msg, y, HMAC(k,y), sig(msg, x)). The server can >> check the HMAC because it holds the HMAC key. The recipient can find who >> sent a message because they know who a given public key was given to. A >> sender's pool of pairs is refreshed in the normal exchange of messages. >> >> Once accepted, a server records HMAC(k, y) and rejects it in the future. [...] > > There's a space optimization for the server I proposed here: > https://moderncrypto.org/mail-archive/messaging/2014/000292.html > > The user distributes pairs (x, HMAC_k(i || y)) for serial numbers i in > [1,N]. Now the server can just "cross off" the serial number i instead of > HMAC(k, y). This can be implemented as a bitmap with 1 bit of storage for > each outstanding value. This is probably a factor 100 space savings.
You'd want to hand out serial #s randomly, so the server's bitmask would need to be sized to MAX number of messages that a user can receive. Not sure if that's a win spacewise vs storing 100 or 64 bits for each actual message. Another way to reduce server state would be to change the HMAC key occasionally, so the server could delete old state (whether bitmask or list). I can see a couple challenges there, but I think they're solvable: * Before you change your HMAC receiving key, you'd need to send a "key-change" message with new pairs to all your correspondents, and a time when they should discard old pairs and start using new pairs (and your correspondents need to be time-sync'd and switch at the same time, otherwise the server will be able to distinguish messages from new-key vs old-key correspondents). * Before you send a message, you need to ensure that you've retrieved any relevant "key-change" messages from your mailbox, otherwise you might be unaware that a key-change had been scheduled, and use an old-key pair. Assuming key changes are scheduled at least a week or month in advance, your client would prohibit you from sending a new message until you had downloaded messages at least up to the last week or month. Trevor _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
