OmniFocus Sync Encryption: Gory Technical Details!

OmniFocus
#1

Hello, everyone! A while ago, Ken mentioned that we are in the process of adding client-side encryption support to our products. There are several places we think encryption is worthwhile, and they each require their own approach. Right now, I want to talk about what we’re working on for OmniFocus Sync encryption.

We’ve always encrypted the communications between OmniFocus and the server, of course. But we’d like to do better. The only things which should ever have access to your OmniFocus tasks are the devices you own and control: your phone, your Mac, your tablet.

What does this mean for you? There are positive and negative aspects. The positive aspect is that you can be more sure of the privacy of your OmniFocus tasks, whether they’re stored on our server or a third-party server. You should be able to put sensitive data in OmniFocus without worrying about auditing our datacenter. The other side of the coin, though, is that we won’t be able to look at your data even if you ask us to- unless you also give us the passphrase. If you lose your passphrase and all of your devices, there will be nothing we can do; we can’t recover or reset a passphrase. We think that, for most people, this is a good tradeoff.

What follows is very technical. I’m going to describe in more detail what we’re trying to achieve and what cryptographic techniques we’re using. We’d love to hear feedback on this: if you have a need that this doesn’t quite cover, or if you think we’ve missed a risk or an opportunity, please let us know. We are also having this reviewed by experts. But the more eyes, the better!

It’s likely that there will be changes to this before it becomes final. But we will document the final version. Our goal is not to hold your data hostage.

Goals and Threat Model

“Before I built a wall I’d ask to know / What I was walling in or walling out” - Robert Frost

Our main goal is to secure your data against a passive attacker: someone who can read the files on the server, intercept them on the network, look at old backup tapes, etc., but who cannot modify your files on the server. This describes a lot of real-world compromises. The passive attacker should be able to learn very little about your use of OmniFocus. They will, by definition, be able to tell when you’re making changes and syncing them, and they can tell if you’ve added an especially large attachment, for example, because of the increase in traffic. But they should not be able to read the contents of any of your tasks.

We can’t provide complete protection against an active attacker, who can modify files on the server. But we will limit their options as much as we can.

An attacker might learn an old passphrase of yours, or might learn a current passphrase but only have access to an old copy of your database. In these cases, we want to ensure they still can’t read your information. Additionally, if someone has access (to both your database and passphrase), and you change the passphrase, they should not be able to read tasks you add after changing your password.

There are a lot of scenarios we’re not trying to deal with, at least not with this feature. For example, if someone compromises your phone or your Mac, there’s very little we can do. However, Apple provides many protections in the form of Data Protection, FileVault, Gatekeeper, and so on. OmniFocus Sync encryption is meant to fit into the larger system of security technologies, not to re-invent wheels you already have.

We have some other goals, as well. We’re intentionally preferring “boring” algorithms, which are widely used, and which are available in Apple’s system frameworks (the less low-level crypto we have to ship, the better for everyone).

Overall Design

It’s simple: You enter a passphrase, we encrypt your data with that passphrase.

Okay, it’s not that simple. An OmniFocus sync database is a directory full of files which are read and written asynchronously by multiple clients that don’t have other ways to communicate.

An encrypted database has one extra file, the “encryption metadata” or key management file. Your passphrase decrypts this file, which contains one or more file-encryption subkeys, each with an identifying key index.

Individual files start with the key index of one of the keys in the key management/metadata file, and then are encrypted using that key.

When the user changes their passphrase, therefore, we don’t need to re-encrypt every file immediately. We can simply re-encrypt the metadata blob with the new passphrase. At the same time, we add a new key to it, and mark the new key as “active”, and the old key as “retired”. Any new files uploaded by OmniFocus clients after this point use the new subkey, and old data is eventually re-encrypted or deleted, at which time the “retired” subkey is deleted.

Concrete details

TL;DR: PBKDF2-SHA256, AESWRAP, AES128-CTR, HMAC-SHA256.

The metadata / key management file is a plist containing PBKDF2 parameters, and an encrypted blob. Your passphrase is fed to PBKDF2, and the result is used as an AES-256 key to unwrap (decrypt) the encrypted blob using AESWRAP. The blob contains a collection of file subkeys, each identified by a key index (a small integer). Most of the time, there will be only one key in the blob.

Individual files contain (after a magic number) the index of the key with which they are encrypted. Using this key index, OmniFocus retrieves an AES key and a HMAC key from the key management blob, and encrypts the file using AES in CTR mode and HMAC-SHA256 as an integrity check.

Most files are quite short (maybe 1kB), but some are large (gigabytes). CTR mode is used for its random-read-access capability: sometimes, we may want to be able to read a sub-range of the file without decrypting the whole thing. For this reason, the encrypted data is broken into segments of (up to) 65536 bytes. Each segment has its own CTR IV and HMAC. The file as a whole has an HMAC which is simply the HMAC of every segment’s HMAC- like a 1-level Merkle tree.

A file consists of:

  • Fixed-length header containing magic number and key index
    • File magic (a fixed string to identify encrypted files)
    • Key information length (2 bytes, size of next section not including padding)
  • File key information
    • Key index (2 bytes). Selects a document key for unwrapping the file key.
    • Any encrypted information needed by the key. Currently, this is empty.
  • Padding to a 16-byte boundary. Must be zero; must be checked by reader.
  • Variable-length array of encrypted segments
    • Segment IV (12 bytes = block size minus the 32-bit AES-CTR counter)
    • Segment MAC (20 bytes): the truncated HMAC-SHA256 of ( IV || segment number || encrypted data ) where the segment number is a 32-bit number.
    • Segment data (SEGMENTED_PAGE_SIZE = 64k bytes, except possibly for the last segment): encrypted with initial IV of ( IV || zeroes ) as is normal for CTR mode.
  • Trailer
    • File HMAC: (SEGMENTED_FILE_MAC_LEN = 32 bytes) computed over a version identifier (currently, the single byte 0x01) and the segment MACs concatenated in order.

Why not… ?

Why not GCM? GCM or GHASH isn’t available from the system libraries, and although HMAC-SHA256 is slower, it’s still fast enough. GHASH is easy for us to implement in our code, but probably hard for us to implement securely.

Why not ChaCha+Poly1305, or something like that? Technically, we could certainly use a different AEAD algorithm. We’re trying to stick to boring, tried-and-true algorithms wherever possible, and unless we have a good reason we’re also trying to stick to algorithms which are available in CommonCrypto. Right now, that means AES and SHA.

Weaknesses

Our forward and reverse secrecy is not perfect: key rollover is not instant, since it involves re-encrypting and re-uploading everything. We wait until the next time we have to rewrite the server database (a “compaction”) to eliminate the use of the old subkeys.

An active attacker (or server administrator) can roll back the database to a previous state or delete files. However, OmniFocus’s sync algorithm will typically silently repair this kind of damage.

Because OmniFocus compresses its files, we’re vulnerable to information leakage similar to the CRIME attack: someone with the ability to add tasks to your database and to observe your sync traffic can, potentially, probe for the existence of particular text in your database. It would be hard to do this without the user noticing, though.

An active attacker can rename files without detection. We’ll probably add protection against this before finalizing the format.

Possibilities for Future Development

There are several features that are desirable but which we aren’t working on for this release. We’re trying to leave ourselves the flexibility to add them later:

Password-less encryption

Passwords are what people are used to, but they have a lot of problems, and can be inconvenient to use securely. Perhaps in the future we can eliminate them in favor of some other form of key agreement or secret-sharing among your devices.

Key Escrow

Right now, if you lose your encryption passphrase and all of your devices, there’s no way to recover your data. From a security perspective, that’s great. But it’s often nice to be able to leave a “spare key” somewhere: perhaps with us, perhaps with your company’s IT people, perhaps with your spouse.

Write-only Encryption

Tools like Quick Entry and Mail Drop would ideally be able to write a file that OmniFocus can read, but no one else (including Mail Drop) can. The encryption metadata file could contain an asymmetric keypair for this purpose.

9 Likes
New encryption feature and third-party services
How does the OmniSync server handle sending passwords?
API into web database?
#2

Public feedback on these plans are welcome here, of course! If you’d prefer to send your feedback directly to us through email, please email our support humans at omnifocus@omnigroup.com and cc me at kc@omnigroup.com.

Thanks!

#3

Not sure it is a good point to ask to accommodate for two-factor (TOTP seems good enough) sync server auth (and/or passphrase?), but leaving it here just in case it is…

#4

All of this sync encryption is designed to work with any back end WebDAV server you choose to store your data on, not just with our Omni Sync Server. Your encryption keys and your server authentication credentials are separate (and you can use different passphrases for each). I can imagine two-factor authentication being used to authenticate with a server when setting up a new device, but in general OmniFocus is expected to invisibly sync in the background (with no additional authentication) once a device is set up (much like Messages or Mail).

On an unrelated note:

We’re planning to post a small, readable Python implementation of this encryption design: we think that will be a good way of communicating exactly how this design is expected to work. (And customers will be able to use this reference implementation to decode data they’ve downloaded directly from our server using WebDAV.)

Also, the native code which implements this in our apps will be published as part of our open source frameworks.

#5

Giving it a second thought, looks like encryption keys are a much better place for 2FA than server sync. Because there are many ways to intercept database / sync traffic, but they are useless without encryption keys. At the same time, the encryption credentials are much more difficult to steal (and, more importantly, reuse) if they are not only a long-living static password, but also a time-dependent OTP which is valid for only about a minute.

Of course, an OTP should be provided only once for a device, at a DB setup phase.

#6

Good stuff. I’ve skimmed through the design as written and am going to politely sweep any feature requests that came into mind directly to the back of my mind and focus on potential exploits and weaknesses.

Most of them are covered in the weakness section, however there’s one weakness that I think may not be obvious, hasn’t been specifically called out, or hasn’t been specifically addressed: CTR mode and, specifically, re-use of IVs.

If an attacker has access to two ciphertexts which use the same IV in CTR mode, then the xor of the those ciphertexts is also the xor of the plaintexts. And if one of the plaintexts is a common phrase or expected byte sequence because the attacker has reverse engineered with their own copy of OmniFocus, then it becomes easy for them to determine the other plaintext.

Since it isn’t explicitly called out in the design, I assume you’re using random IVs because that is what everyone does by default. (Apologies if you’re not.)

With random IVs, this means that you’re rolling the dice every time you encrypt one of those 64k segments. Probably going to be an unused IV, but you won’t know for sure unless you look at all the IVs previously used.

Instead, consider using a 128 bit global counter in the document key metadata. When a new IV is needed, lock the counter, read its value and assign that as the IV, increment it by one, write that back into the counter value, and then unlock it. That should keep an OmniFocus instance able to encrypt without every duplicating an IV until it stores…uh…2^144 bytes of data.

Or consider each file having its first IV be 128 0-bits, the next IV be 127 0-bits and 1-bit, etc. etc. Essentially, a counter for the file itself, which will remove the potential for global lock contention.

Alright, enough typing from me. Hope this was useful!

6 Likes
#7

Thanks for pointing that out! Our current implementation does, in fact, use random IVs. We’ll look into adding safeguards to prevent the (unlikely-but-very-dangerous) possibility of IV duplication. (Thanks for suggesting those two solutions!)

#8

Hi, @bfd, thank you for your comment! Yes, the fragility of CTR mode if IVs are reused is definitely something I’ve thought about.

We actually use a hybrid approach for the CTR IVs. As you know, the IV is 12 bytes (with the remaining 4 bytes incremented per block as is common for CTR mode— again we’re restricted here by what CommonCrypto supplies). Of those, 8 are from a CSPRNG, and four are from a counter. That means it’ll take 2^32 encryptions for the counter to roll over, and roughly 2^32 encryptions until there’s a significant chance of a collision in the random part. So if one of the two mechanisms fails completely, you’re still okay for around 256GiB of bulk upload, or more realistically, 2^32 database changes (most of which require far less than one 64kB segment to record). If both mechanisms are working as they should, their collisions are independent, and you have 2^64 segments before you have to worry; though actually it’s not that good because different clients can’t communicate their counter values. Between clients, we rely on the random portion for collision resistance. Within one client, the counter should guarantee uniqueness for large files.

Right, I probably should have included it. (It’s not a fixed part of the design— as far as compatibility goes, it doesn’t matter what mechanism each client uses to generate unique IVs— but it is, as you point out, a pretty important detail.)

FWIW, although I haven’t looked into it further, another approach is to put a long counter through a per-client secure pseudorandom permutation (see e.g. Phillip Rogaway’s summary of FPE modes). I haven’t done the math on how that would affect the collision probabilities, though. (It would have the additional benefit of not leaking the order in which segments were encrypted. Right now the attacker can easily deduce that order from the timestamps on the files, but conceivably it could be relevant in a future context.)

1 Like
#9

The chances of a collision of IVs is in non-negligible if you are encrypting lots (billions) of things under the same key. That is, the issue is when you reuse the same IV with the same key. But because each file has its own key, the chance of a key/IV pair being reused in negligible. So I don’t see the current design as a bug.

However, @bfd’s point still holds because the security properties that make random IVs safe depend on other parts of the system that might change someday. So a good defensive strategy would be to do something like what @bfd is suggesting.

#10

I really like the fact that you are building in at this point a mechanism for keeping previous keys and distinguishing the current key. That is laying the groundwork for allowing a password change to have the effects that users expect it to have.

1 Like
#11

Thank you very much for the heads-up, Ken. I am happy to read about your plans to fully document the format and even release a python implementation.

There is just one question remaining: You’re declaring “Write-only Encryption” as future development. Since I want to use my own WebDAV storage and create tasks there: May I assume that unencrypted files in the current format are still working to add tasks on the server side?

Patrick

#12

You’ll still be able to write unencrypted files in the same format to add tasks to an encrypted database, but there will be a change: you’ll need to give them a filename of the form <guid>-transaction.inbox. When an OmniFocus client syncs, it will download and process those unencrypted .inbox files and rewrite them as encrypted transaction files.

Eventually, this approach of handing off that transaction integration to the client (rather than having the server try to do that work itself) will let us extend Mail Drop to support features like adding a task directly to a project or context by simply communicating that intent to the client (rather than having to try to decode the database—which the server won’t have access to do anyway).

2 Likes
#13

I’m in love with what you’re doing here—thank you!

Asking a bigger-picture question… right now each app ends up having to write it’s own encryption code. It feels like there’s a missed opportunity to contribute to an existing open source system that solves the problem in a more general way. For example, what if OmniFocus used a Cryptomator Vault for storing it’s data? It’s open source, secure, works with WebDAV and other Cloud storage, and it’s already developed for Mac and iOS. Or if not Cryptomator, some other open source encrypted Cloud filesystem. Is that a question you’ve considered?

#14

CBC mode gets you random read access too, on 16 byte boundaries. Just use the previous 16 bytes as the IV. (It does not get you random write access, however.) I’m using this technique in an app to implement a CGDataProvider on top of an encrypted file.

#15

For those that would like to provide feedback on the implementation, its current state is now available at https://github.com/omnigroup/OmniGroup. In particular, see Frameworks/OmniFileStore with DecryptionExample.py and OFSEncryptingFileManager.m being good starting points.

I’m not the author of any the encryption bits, so I’m not sure if @wiml would prefer source-level comments go here or to github issues.

2 Likes
#16

Well, one answer is that I didn’t know about Cryptomator when designing this— I don’t think it was nearly as complete when we started. (We did investigate similar general purpose schemes, like EncFS and eCryptFS.) But the longer answer is we’ve found that each of our encryption use cases wants different things from the encryption layer, mostly in the ways that they manage session- and long-term keys. I’ve come to the conclusion that there are some places where good general-purpose solutions already exist (like transport encryption (TLS), and block-device encryption (FileVault, dmcrypt)) and some places where there isn’t a one-size-fits-all solution (yet?). We’re open to the idea, though!

This is true! Another one of our motivations was the possibility of parallelizing the encryption. (Although we haven’t taken advantage of that, we may in the future, since multi-core machines are the norm nowadays.) We could certainly have used CBC mode giving up only a few things.

#17

Nice to see the chief defender against the dark arts over here :-)

#18

Hi Ken, First, thanks for doing this. I keep my data on a local WebDAVNav server, but it’d be nice to have other options. I presume that it’ll continue to work with the local solution?

I’m OK at crypto, but there’s others in the thread much better, so I’ll let them comment.

Regarding key escrow, the new 1Password for Teams/Families would be a great option (For the record, I don’t work for them, just love their products). Related request, please make sure that both OSX and IOS support password pasting so we can leverage a password manager.

If the local DB is still unencrypted, the need for a formal key escrow (corporate use) would be minimized, as eDiscovery could take place against the regular disk image. Implementing some formal process is a massive design effort, and probably not cost justified. For those who want to have extra local encryption, moving the database to an encrypted DMG and setting hard links in the original location works just fine. Net is that I’d suggest making local encryption an option - it avoids a lot of issues.

For the password itself, that’s always the weak spot in any system like this. Are you thinking of any sort of kevlar footwear around password entry? Strength meters are misleading at best, but do provide some defense against really dumb passwords (like Omni).

What happens if the Plist file becomes corrupted? Is there a duplicate/backup on the sync server?

And last, I wholeheartedly approve of your decision to leverage common algorithms. For this use case, they’re both the best vetted and we know what to expect. Boutique ones are a can of worms. Likewise on the implementation, there’s no sense reinventing the wheel, and if Apple’s compromised, we have a whole lot more things to worry about.

#21

This is great news! My tasks include a lot of confidential information about clients and what I am doing on a daily basis. Sync Encryption means I can now rest assured that it will be difficult for an attacker to access this data.

I’m not a technical expert, but it sounds like you (the OmniFocus people) have taken this very seriously and done a thorough job. I appreciated how nicely you informed me of the details of your latest upgrade, and managed the upgrade process for which I give you top marks for ease of use / usability ;)

#22

Fantastic news on supporting End to End Encryption. As a security professional, this has been a major concern of mine for awhile.

The Leviathon Design Review recommends performing a review of the implementation once it’s substantially complete. I know from experience that it can often be tricky to manage keyphrases properly. Has this implementation review taken place or is it currently planned?

Thanks!

HIPAA compliant use