⭐ Merited by ETFbitcoin (9)
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)
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.
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).
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).
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.
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).
[Hm. Wow, a synchronizing server would be super cool for this, if we had a good way of avoiding abuse.]
(this isn't nitpicking, it's happened multiple times)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.
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).
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).
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.
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).
[Hm. Wow, a synchronizing server would be super cool for this, if we had a good way of avoiding abuse.]