Which is obviously not constant time, and will leak information through cache/timing sidechannels.
AES lends itself to a table based implementation which is simple, fairly fast, and-- unfortunately-- not secure if sidechannels matter. Fortunately, AES-NI eliminated most of the motivation for using such implementations on a vast collection of popular desktop hardware which has had AES-NI for quite a few years now.
For the sake of also being constructive, here is a constant time implementation in naive C for both AES encryption and decryption (the latter being somewhat hard to find, because stream modes only use the former):
(sadly, being single-block-at-a-time and constant time without hardware acceleration has a significant performance cost! ... better could be done for XTS mode, as the above algorithm could run SIMD using SSE2-- it isn't implemented in that implementation because the intended use was CBC mode which can't be parallelized like that)
Can't the kernel aes-ni just be setup to save the fpu registers itself on the stack, if necessary?
Curious why CF needs to worry about side-channel attacks when all software run on those machines belong to / written by them. They do have a “workers” product with 3rd party code but they can easily keep storage servers out of that pool. Typically storage encryption is all about what happens when a machine is physically stolen, hard disk discarded on failure or other such actions beyond network security. Please correct me if I am wrong.
> Which is obviously not constant time, and will leak information through cache/timing sidechannels.
This confuses me. Why is it in the kernel if it's not constant time? Isn't that a security risk? (Is there any context where it would be safe to invoke this?)
I wish the world could move on from AES. We have ciphers that are nearly as fast without requiring specialized hardware, just generic SIMD. Imagine how fast a ChaCha ASIC could run!
There are other options for non-AES FDE too: most infamously Speck (suspected to be compromised by the NSA), but also Adiantum, which is now in Linux 5.0.
>Which is obviously not constant time, and will leak information through cache/timing sidechannels.
What's the threat model here? I can't think of a plausible scenario where side channel attacks can be used to gain unauthorized access to FDE contents.
Did this commercially for 15 years. Always the same problems.
We ended up with several solutions- but all of them generally work the same conceptually.
First off, separation of I/O layers. System calls into the FS stack should be reading and writing only to memory cache.
Middle layer to schedule, synchronize and prioritize process IO. This layer fills the file system caché with cleartext and schedules writes back to disk using queues or journals.
You also need a way to convert data without downtime. A simple block or file kernel thread to lock, encrypt, mark and writeback works well.
Another beneficial technique is to increase blocksizes on disk. User Processes usually work in 4K blocks, but writing back blocks at small sizes is expensive. Better to schedule those writebacks later at 64k blocks so that hopefully the application is done with that particular stretch of data.
The blog post reads like this all happened recently, but their linked post to the dm-crypt mailing list is from September 2017[1]. I'm curious if they've interacted with the dm-crypt people more recently.
Yeah, the time frame is somewhat unclear. The patch they link to in their tree is dated December 2019 however [1], so I assume this blog post is about stuff they've completed recently.
Did they reach out to the Linux kernel mailing list? Or just the dm-crypt team, I found the answer they received rather arrogant and useless to be honest.
Ages ago I benchmarked truecrypt overhead on my machine at the time (2006, I think?) and it was about 3%; I assumed that's a reasonable and still applicable number, also do dm-crypt and modern VeraCrypt. Guess I was get gradually more wrong through those years, according to the git archeology....
Wow those speed improvements are very neat. And an awesome blog post accompanying them. Prior to reading this, I've considered Linux disk encryption adding negligible latency because no HDDs/SSD can be fast enough for a CPU equipped with AES-NI, but that view has changed. Two questions: 1. are there any efforts to upstream them? 2. Invoking non-hw-accelerated AES decryption routines sounds quite expensive. Has it been tried out to save the FPU registers only if there is the need for decryption?
The existing Linux system is useful for hardware that does less than 200MB/s, so you should be fine with HDDs.
Cloudflare is optimising for SSDs.
They don't talk about latency: all their crypto benchmarks measure throughput. Near the end they hint at response time for their overall cache system but there's no detailed discussion of latency issues.
The takeaway for me is that I'm OK with what's currently in Linux for the HDDs I use for my backups but I'd probably lose out if I encrypted my main SSD with LUKS.
At the end of the article they say that they're not going to upstream the patches as they are because they've only tested them with this one workload.
I'd also be interested to see a benchmark comparing SW AES with FPU-saving + HW AES. Unfortunately their post does not include stats for how often their proxy falls into the HW or SW implementations. Whatever those numbers are, I'd expect FPU-saving + HW AES to be somewhere in the middle.
> Many companies, however, don't encrypt their disks, because they fear the potential performance penalty caused by encryption overhead.
There is also the overhead of automatically unblocking a remote server during an unattended reboot. Reading the encryption password on a USB stick or fetching it through internet is a no from me. I think there are solutions about storing the password in RAM or in an unencrypted partition, but that's the overhead I'm talking about. I wonder how companies deal with that.
> The Network-Bound Disk Encryption (NBDE) allows the user to encrypt root volumes of hard drives on physical and virtual machines without requiring to manually enter a password when systems are restarted. [0]
i use kexec for reboots and store the keys for disks inside an initramfs which itself is stored on an encrypted boot partition. When i do a cold boot these systems boot into a recovery like OS so i can fix stuff when needed but mainly to do a kexec there (its not perfect but what is). If its possible to avoid this (i.e. i have physical access) i can decrypt the initramfs directly from grub using a passphrase entered locally.
A warm reboot using kexec does not need any intervention from my side and directly boots into the already decrypted initramfs with the key already present and thus able to mount the encrypted volumes including the root volume.
Debian offers a dropbear shell in initramfs which you can use to SSH in and provide keys. I only have a handful of servers so currently I do this manually on a reboot but it would not be difficult to automate using for example SSH keys unlocking key material. The downside of this is your initramfs and kernel are on an unencrypted disk so a physical attacker could feasibly backdoor them. I'm sure there's some secure boot UEFI / TPM solution here.
Interesting. One other thing they don't mention that I found interesting when doing my own digging on dmcrypt speeds a while back is that the 'cryptosetup benchmark' command is only showing the single core performance of each of those encryption algorithms. You can verify this by watching the processor load as it performs the benchmark. That lead me to find that if you have a Linux software RAID you can get much better performance by having 1 dmcrpyt volume per disk and then software RAID the dm devices instead of putting a single dmcrypt on top of the software RAID. Curious if that would stack performance wise with what they found here or if that just happened to help with the queuing issue they identified.
i remember somewhat recently efforts to parallelize the work of dm-crypt where applicable had been merged. However, i guess having multiple separate encryption parameters and states (read: disks) leaves more opportunity for parallelization of the work especially if disk access patterns are not spread wide enough.
>Being desperate we decided to seek support from the Internet and posted our findings to the dm-crypt mailing list
When I see a company such as CloudFlare being so transparent about their difficulties, and trying to find an answer using their community members, it makes me love them even more.
You won't know about their ego or professionalism until you work with them. Posting on a mailing list and making a blog post about it is not proof of either of these, it's brand marketing. They're trumpeting their engineering talent to build good will/nerd rep so people will love their company, spend money there, and apply for jobs. (But what it does show is that they're good at marketing, because it's working)
> Unlike file system level encryption it encrypts all data on the disk including file metadata and even free space.
Anyone have a source on how full disk aka block-level encryption encrypts free space? The only way I can imagine this could happen is by overwriting the entire disk initially with random data, so that you can't distinguish between encrypted and true "free space", i.e. on a brand new clean disk. Then, when a file (which, when written, would have been encrypted) is deleted (which by any conventional meaning of the word 'deleted' means the encrypted data is still present, but unallocated, thus indistinguishable from the random data in step 1), then gets overwritten again with random data?
I would argue that overwriting an encrypted file with random data isn't really encrypting free space, but rather just overwriting the data, which already appeared random/encrypted. It is hardly any different to having a cleartext disk and overwriting deleted files with zeros, making them indistinguishable from actual free space.
Debian does the first thing you discussed if you create an encrypted partition in the installer - it writes 0s through the crypto layer to fill the entire disk with encrypted data.
> Data encryption at rest is a must-have for any modern Internet company
What is it protecting against — data recovery from discarded old disks? Very stupid criminals breaking into the datacenter, powering servers off and stealing disks?
A breach in some web app would give the attacker access to a live system that has the encrypted disks already mounted…
As we push further and further to the edge — closer and closer to every Internet user — the risk of a machine just walking away becomes higher and higher. As a result, we aim to build our servers with a similar mindset to how Apple builds iPhones — how can we ensure that secrets remain safe even if someone has physical access to the machines themselves. Ignat's work here is critical to us continuing to build our network to the furthest corners of the Internet. Stay tuned for more posts on how we use Trusted and Secure Boot, TPMs, signed packages, and much more to give us confidence to continue to expand Cloudflare's network.
> criminals breaking into the datacenter, powering servers off and stealing disks?
Yes, exactly. A company I worked for had a hard drive pulled from a running server in a (third party) data center that contained their game server binaries. Shortly afterwards as pirate company setup a business running “gray shards”, with - no surprise - lower prices.
> one can only encrypt the whole disk with a single key
You can still use partitions.
> not all cryptographic algorithms can be used as the block layer doesn't have a high-level overview of the data anymore
I do not really understand this. Which cryptographic algorithms can't be used?
> Most common algorithms require some sort of block chaining to be secure
Nowadays I would say that from these only CTR is common, which does not require chaining.
> Application and file system level encryption are usually the preferred choice for client systems because of the flexibility
One big issue with "Application and file system level encryption" is that you often end up leaking metadata (such as the date edited, file name, file size, etc).
Regardless I think that this is a really nice article. I can't wait to try their patches on my laptop.
You can't use any algorithm that requires O(n) IVs (e.g. a separate IV per disk sector), because there's nowhere to store the IVs. (Another consequence of this is that you can't store checksums anywhere, so you can't provide integrity checks.)
You can't use CTR mode either, because you'll end up reusing counter values. What do you do when you need to overwrite a block with new data?
XTS mode solves this, at least partially. It's like CTR mode, but with an extra "tweak" that essentially hashes the block's content into the encryption key. So if you overwrite a block with new data, you get a new encryption key.
This isn't perfect, though, because it's still deterministic. If an attacker can see multiple states of the disk, they can tell when you revert a block to a previous state. But it's much better than other modes, especially since the main threat you want to protect against is your laptop getting stolen (in which case the attacker only sees a single state).
> One big issue with "Application and file system level encryption" is that you often end up leaking metadata (such as the date edited, file name, file size, etc).
Neat. Poorly optimized queues can have a significant impact on performance, doubling throughput for disk encryption with some queue tweaks is pretty significant.
> We are going to submit this work for inclusion in the main kernel source tree, but most likely not in its current form. Although the results look encouraging we have to remember that Linux is a highly portable operating system: it runs on powerful servers as well as small resource constrained IoT devices and on many other CPU architectures as well. The current version of the patches just optimises disk encryption for a particular workload on a particular architecture, but Linux needs a solution which runs smoothly everywhere.
That is, they think their current patch is too specialized for their own use-case to warrant inclusion in the mainline kernel without significant adaptation.
>but there doesn't appear to have been any serious effort to coordinate with other Linux contributors to figure out a solution to the problem.
Well when they reached out to the community they were told they're idiots and should f* off in only somewhat nicer language. Then they were simply ignored.
When your community is toxic don't complain that people don't want to be part of it.
They are submitting their work, after they put in even more work to make it more universally applicable to all Linux users. They also did try to engage with the community who basically told them that they didn't know how fast crypto should be.
[+] [-] nullc|6 years ago|reply
This seems like at least something of a bad idea, because that implementation (if my search-fu is correct) is:
https://github.com/torvalds/linux/blob/master/crypto/aes_gen...
Which is obviously not constant time, and will leak information through cache/timing sidechannels.
AES lends itself to a table based implementation which is simple, fairly fast, and-- unfortunately-- not secure if sidechannels matter. Fortunately, AES-NI eliminated most of the motivation for using such implementations on a vast collection of popular desktop hardware which has had AES-NI for quite a few years now.
For the sake of also being constructive, here is a constant time implementation in naive C for both AES encryption and decryption (the latter being somewhat hard to find, because stream modes only use the former):
https://github.com/bitcoin-core/ctaes
(sadly, being single-block-at-a-time and constant time without hardware acceleration has a significant performance cost! ... better could be done for XTS mode, as the above algorithm could run SIMD using SSE2-- it isn't implemented in that implementation because the intended use was CBC mode which can't be parallelized like that)
Can't the kernel aes-ni just be setup to save the fpu registers itself on the stack, if necessary?
[+] [-] harikb|6 years ago|reply
[+] [-] nshepperd|6 years ago|reply
This confuses me. Why is it in the kernel if it's not constant time? Isn't that a security risk? (Is there any context where it would be safe to invoke this?)
[+] [-] nemo1618|6 years ago|reply
There are other options for non-AES FDE too: most infamously Speck (suspected to be compromised by the NSA), but also Adiantum, which is now in Linux 5.0.
[+] [-] gruez|6 years ago|reply
What's the threat model here? I can't think of a plausible scenario where side channel attacks can be used to gain unauthorized access to FDE contents.
[+] [-] convivialdingo|6 years ago|reply
We ended up with several solutions- but all of them generally work the same conceptually.
First off, separation of I/O layers. System calls into the FS stack should be reading and writing only to memory cache.
Middle layer to schedule, synchronize and prioritize process IO. This layer fills the file system caché with cleartext and schedules writes back to disk using queues or journals.
You also need a way to convert data without downtime. A simple block or file kernel thread to lock, encrypt, mark and writeback works well.
Another beneficial technique is to increase blocksizes on disk. User Processes usually work in 4K blocks, but writing back blocks at small sizes is expensive. Better to schedule those writebacks later at 64k blocks so that hopefully the application is done with that particular stretch of data.
Anyway, my 2 pennies.
[+] [-] tyingq|6 years ago|reply
[1]https://www.spinics.net/lists/dm-crypt/msg07516.html
[+] [-] mattst88|6 years ago|reply
[1] https://github.com/cloudflare/linux/blob/master/patches/0023...
[+] [-] unixhero|6 years ago|reply
[+] [-] jlgaddis|6 years ago|reply
[+] [-] beagle3|6 years ago|reply
[+] [-] est31|6 years ago|reply
[+] [-] andyjpb|6 years ago|reply
Cloudflare is optimising for SSDs.
They don't talk about latency: all their crypto benchmarks measure throughput. Near the end they hint at response time for their overall cache system but there's no detailed discussion of latency issues.
The takeaway for me is that I'm OK with what's currently in Linux for the HDDs I use for my backups but I'd probably lose out if I encrypted my main SSD with LUKS.
At the end of the article they say that they're not going to upstream the patches as they are because they've only tested them with this one workload.
I'd also be interested to see a benchmark comparing SW AES with FPU-saving + HW AES. Unfortunately their post does not include stats for how often their proxy falls into the HW or SW implementations. Whatever those numbers are, I'd expect FPU-saving + HW AES to be somewhere in the middle.
[+] [-] knorker|6 years ago|reply
[+] [-] ggregoire|6 years ago|reply
There is also the overhead of automatically unblocking a remote server during an unattended reboot. Reading the encryption password on a USB stick or fetching it through internet is a no from me. I think there are solutions about storing the password in RAM or in an unencrypted partition, but that's the overhead I'm talking about. I wonder how companies deal with that.
[+] [-] jlgaddis|6 years ago|reply
> The Network-Bound Disk Encryption (NBDE) allows the user to encrypt root volumes of hard drives on physical and virtual machines without requiring to manually enter a password when systems are restarted. [0]
[0]: https://access.redhat.com/documentation/en-US/Red_Hat_Enterp...
[+] [-] gruez|6 years ago|reply
[+] [-] mercora|6 years ago|reply
A warm reboot using kexec does not need any intervention from my side and directly boots into the already decrypted initramfs with the key already present and thus able to mount the encrypted volumes including the root volume.
[+] [-] r1ch|6 years ago|reply
[+] [-] vletal|6 years ago|reply
[+] [-] pmorici|6 years ago|reply
[+] [-] mercora|6 years ago|reply
[+] [-] thereyougo|6 years ago|reply
When I see a company such as CloudFlare being so transparent about their difficulties, and trying to find an answer using their community members, it makes me love them even more.
No ego, pure Professionalism
[+] [-] sneak|6 years ago|reply
[+] [-] peterwwillis|6 years ago|reply
[+] [-] herpderperator|6 years ago|reply
Anyone have a source on how full disk aka block-level encryption encrypts free space? The only way I can imagine this could happen is by overwriting the entire disk initially with random data, so that you can't distinguish between encrypted and true "free space", i.e. on a brand new clean disk. Then, when a file (which, when written, would have been encrypted) is deleted (which by any conventional meaning of the word 'deleted' means the encrypted data is still present, but unallocated, thus indistinguishable from the random data in step 1), then gets overwritten again with random data?
I would argue that overwriting an encrypted file with random data isn't really encrypting free space, but rather just overwriting the data, which already appeared random/encrypted. It is hardly any different to having a cleartext disk and overwriting deleted files with zeros, making them indistinguishable from actual free space.
[+] [-] koala_man|6 years ago|reply
This way, an attacker can't focus cracking on the fullest disk, match stolen backup disks to hosts based on non-sensitive health metrics, etc.
>The only way I can imagine this could happen is by overwriting the entire disk initially with random data
Traditionally, for speed, you'd write all zeroes to the encrypted volume (causing the physical volume to appear random), but yes
>Then, when a file (which, when written, would have been encrypted) is deleted
You'd just leave it. Crucially, you don't TRIM it.
>I would argue that overwriting an encrypted file with random data isn't really encrypting free space
Yup, that's why it's not done
[+] [-] dlgeek|6 years ago|reply
[+] [-] floatboth|6 years ago|reply
What is it protecting against — data recovery from discarded old disks? Very stupid criminals breaking into the datacenter, powering servers off and stealing disks?
A breach in some web app would give the attacker access to a live system that has the encrypted disks already mounted…
[+] [-] eastdakota|6 years ago|reply
[+] [-] netcoyote|6 years ago|reply
Yes, exactly. A company I worked for had a hard drive pulled from a running server in a (third party) data center that contained their game server binaries. Shortly afterwards as pirate company setup a business running “gray shards”, with - no surprise - lower prices.
[+] [-] dependenttypes|6 years ago|reply
You can still use partitions.
> not all cryptographic algorithms can be used as the block layer doesn't have a high-level overview of the data anymore
I do not really understand this. Which cryptographic algorithms can't be used?
> Most common algorithms require some sort of block chaining to be secure
Nowadays I would say that from these only CTR is common, which does not require chaining.
> Application and file system level encryption are usually the preferred choice for client systems because of the flexibility
One big issue with "Application and file system level encryption" is that you often end up leaking metadata (such as the date edited, file name, file size, etc).
Regardless I think that this is a really nice article. I can't wait to try their patches on my laptop.
[+] [-] nemo1618|6 years ago|reply
You can't use any algorithm that requires O(n) IVs (e.g. a separate IV per disk sector), because there's nowhere to store the IVs. (Another consequence of this is that you can't store checksums anywhere, so you can't provide integrity checks.)
You can't use CTR mode either, because you'll end up reusing counter values. What do you do when you need to overwrite a block with new data?
XTS mode solves this, at least partially. It's like CTR mode, but with an extra "tweak" that essentially hashes the block's content into the encryption key. So if you overwrite a block with new data, you get a new encryption key.
This isn't perfect, though, because it's still deterministic. If an attacker can see multiple states of the disk, they can tell when you revert a block to a previous state. But it's much better than other modes, especially since the main threat you want to protect against is your laptop getting stolen (in which case the attacker only sees a single state).
[+] [-] richardwhiuk|6 years ago|reply
CBC - which is one the most common stream cipher algorithm.
It's not clear me whether GCM would work or not.
[+] [-] steerablesafe|6 years ago|reply
I wonder how cryfs stacks up in this regard.
https://www.cryfs.org
[+] [-] yrro|6 years ago|reply
[+] [-] gok|6 years ago|reply
[+] [-] vbezhenar|6 years ago|reply
[+] [-] zackbloom|6 years ago|reply
[+] [-] tyingq|6 years ago|reply
grep -A 11 'xts(aes)' /proc/crypto
Is that what you mean?
[+] [-] gautamcgoel|6 years ago|reply
[+] [-] LinuxBender|6 years ago|reply
[+] [-] tbrock|6 years ago|reply
[+] [-] justlexi93|6 years ago|reply
[+] [-] lidHanteyk|6 years ago|reply
[deleted]
[+] [-] Majromax|6 years ago|reply
> We are going to submit this work for inclusion in the main kernel source tree, but most likely not in its current form. Although the results look encouraging we have to remember that Linux is a highly portable operating system: it runs on powerful servers as well as small resource constrained IoT devices and on many other CPU architectures as well. The current version of the patches just optimises disk encryption for a particular workload on a particular architecture, but Linux needs a solution which runs smoothly everywhere.
That is, they think their current patch is too specialized for their own use-case to warrant inclusion in the mainline kernel without significant adaptation.
[+] [-] marcinzm|6 years ago|reply
Well when they reached out to the community they were told they're idiots and should f* off in only somewhat nicer language. Then they were simply ignored.
When your community is toxic don't complain that people don't want to be part of it.
[+] [-] manigandham|6 years ago|reply
[+] [-] unknown|6 years ago|reply
[deleted]
[+] [-] unknown|6 years ago|reply
[deleted]