Thanks for the feedback! I'm glad someone validated this idea.
Please do not use a #@$@ number without an assignment. Just call it BIP-oleganza-backup for the moment, until the text is ready. Otherwise we get a mess of number collisions and people calling things by colliding numbers they picked and not wanting to change them.
(this isn't nitpicking, it's happened multiple times)
Ok, noted.
Otherwise— this sounds useful! Should it perhaps specify more of the storage service? e.g. how much data can you expect to store, how would such a service be compensated? how would you know which service(s) you're using?
The last in particular seems to be a tough question... but in general we should probably try to specify a "minimum interoperable unit", and I'm not sure if the message alone is terribly interesting.
That would be nice, but can be added as an additional server-side BIP after a couple of actual implementation (and if people really want to produce generalized API).
WRT the spec. The IV really should be non-determinstic, it's already stored in the encrypted message. With a constant IV an observer can tell with AES block precision where the first modification to an updated copy was (and perhaps some more elaborate attacks, e.g. it would be trivially insecure if the cipher mode selected was CTR—). There is no need for the IV to be deterministic that I'm aware of... If you're worried about embedded device RNG quality, you could recommend that the IV be constructed as H(time||other-random||pubkey).
IV is deterministic, but not static. I've made it more clear in BIP. For each backup wallet is supposed to pick next index and derive another unpredictable IV. This is not mandatory (IV is published anyway and can be random), but allows us to have a good default that does not depend on RNGs and can be verified with test vectors.
You appear to have no length encoded for the plaintext. AES-CBC is only capable of encoding an integral number of blocks, so something must encode the plaintext length. I might suggest it use self-descriptive padding, e.g. there is always at least 1 byte of padding, and last byte says how many bytes of padding there are (up to 16, though perhaps some applications might want more padding to close a size sidechannel?). Another style of self-descriptive padding I've seen used is to pad with a 0 bit and then all ones until the end, and the receiver drops all trailing 1s and the last 0 (has the advantage of fewer decodings being invalid).
Thanks for noting this. I myself used PKCS7 padding which I think is exactly what you suggested. Now it's mentioned explicitly in the BIP.
The signature encoding can be made constant length, and probably should be, doing so will save at least one byte (and probably several, depending on how you were planning on having a variable length signature encoding).
Is there a reason to keep the AuthFingerprint? It can be derived from the message itself and the signature (e.g. how bitcoin's signed message works), omitting it would save ~19 bytes.
Good point. I've replaced the auth fingerprint, signature and its length prefix with a single 65-byte long compact signature.
Is there a particular motivation for using a digital signature instead of using a MAC? One reason I could see is that you might want to have multiple servers synchronizing their data without individually talking to the user, like the PGP SKS keyserver— but for that case you'd want to add a sequence number (so you know if an update you're getting is a newer message or not).
Should these encrypted data chunks have a good-until date coded in them? I'd say it could be provided out of band, but not if we wanted it to be authenticated by the signatures (for the imagined synchronization network).
Initially I had an idea about adding a timestamp and making the whole thing verifiable without access to the private keys. But it was not well-thought. Now I've clarified this:
auth key is non-hardened auth pubkey can be kept in memory/stored on disk unencrypted so the wallet can verify various backup payloads without asking user for his password. When the fresh valid backup is found (or the user selected one of the available backups), wallet asks for a password or TouchID verification to unlock private master key and derive decryption keys.
[Hm. Wow, a synchronizing server would be super cool for this, if we had a good way of avoiding abuse.]
Maybe some proof of work would do? However, I'd prefer some payment scheme built-in. So we could pay a little bit upfront for X uploads and therefore has some incentive for the server to stick around when we need to retrieve the data. Maybe the payment is better be done afterwards. Or with some sort of 2-of-2 bilateral deposit.
