Improve backup encryption efficiency

[keepiru]

The problem you're addressing (if any)

scrypt was designed as a secure key derivation function. It intentionally uses large amounts of memory and CPU to make brute force key recovery more difficult.

Passing the entire backup stream through scrypt greatly increases the time to create and restore backups. Doing so does not strengthen the encryption compared to using scrypt only as a KDF.

Indeed, it may weaken the encryption - scrypt has not been subject to the extensive cryptanalysis that AES or other mainstream encryption algorithms have been. It is possible that it has vulnerabilities which do not affect its usual use as a KDF, but which can be exploited with long data streams.

Describe the solution you'd like

Change the backup pipeline so scrypt is only used to derive the encryption key. Perform the bulk encryption with AES.

Where is the value to a user, and who might that user be?

This will improve performance for anyone using qvm-backup. On my system, scrypt bottlenecks the process at around 20MiB/s. This makes the process of backing up my system take about 5 hours, compared to perhaps 1 hour if I could run by backup drive at full speed.

This will also reduce wasted CPU, freeing most of a core for application use.

This may also avert a security failure in event of a future cryptanalysis of scrypt.

Describe alternatives you've considered

Continue suffering in silence.

[marmarek]

No, the backup archive is not passed through scrypt KDF. It is passed through scrypt encryption utility, which uses scrypt KDF algorithm to derive an encryption key and then encrypts the actual data with AES and also protects its integrity with HMAC-SHA256. What it does however, is to encrypt each (100MB) chunk of the data separately - this allows to require much less temporary space during both creating the backup archive and restoring it (it needs to verify data integrity before processing it - having not-so-big chunks allows doing it in parts, not the whole thing at once). But does mean KDF function is called several times... One simple improvement is to increase chunk size (at the cost of requiring more space to process the data) - I think value like 500MB is totally reasonable.

[keepiru]

Thank you for the clarification.

I still advocate using scrypt only as a KDF, and letting openssl (or similar) handle the bulk encryption. Increasing the chunk size would create an incremental improvement at the expense of temp space. Using a standard encryption+HMAC would be even faster, with no speed tradeoff, admittedly at the expense of a much larger change.

[donob4n]

Pretty off-topic but any thoughts about borgbackup encryption? I would like to work on a borg setup for Qubes where a 'backup-vm' mounts last 'private.img' for each VM and runs borg at a filesystem level. Main problem is that 'backup-vm' must be trusted but it could be "easily" improved using different backup-vm's for different group of qubes but this also forces (or encourages) to use different borg repositories.

[DemiMarie]

Borg has some cryptographic vulnerabilities.

[donob4n]

Hehe thanks for your fast response @DemiMarie but could you specify? I know there is one "vulnerability" that only applies if you push the same repository from different sources: https://borgbackup.readthedocs.io/en/stable/faq.html#can-i-backup-from-multiple-servers-into-a-single-repository https://borgbackup.readthedocs.io/en/stable/faq.html#borg-security-critique

[DemiMarie]

@donob4n last I checked, that vulnerability also applies in the case of a rollback attack.

[andrewdavidwong]

Updated title for accuracy.

@donob4n, please do not use qubes-issues for off-topic discussion. Please use the forum or mailing lists instead.

[DemiMarie]

libsodium has stream encryption code that could be used.

[jakoblell]

I've taken a look into this and investigated the options, it may be possible to reach some quite significant improvements either by increasing the cunk size or by tweaking the scrypt parameters without switching to a totally new backup library. Combined with the hopefully soon to be implemented zstd support (see https://github.com/QubesOS/qubes-issues/issues/8211) this could lead to a massive improvement in backup speed with relatively little implementation effort.

With the default settings we get the following performance (measured for 100/1000/10000MB, all benchmarks done on an Ryzen 7 Pro 6850U):

[user@dom0 ~]$ dd if=/dev/zero bs=1M count=100|time scrypt enc --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 4.14148 s, 25.3 MB/s
3.95user 0.15system 0:04.14elapsed 99%CPU (0avgtext+0avgdata 264704maxresident)k
0inputs+0outputs (0major+65713minor)pagefaults 0swaps
[user@dom0 ~]$ dd if=/dev/zero bs=1M count=1000|time scrypt enc --passphrase file:/dev/null - > /dev/null
1000+0 records in
1000+0 records out
1048576000 bytes (1.0 GB, 1000 MiB) copied, 6.93758 s, 151 MB/s
6.65user 0.25system 0:06.93elapsed 99%CPU (0avgtext+0avgdata 264868maxresident)k
0inputs+0outputs (0major+65719minor)pagefaults 0swaps
[user@dom0 ~]$ dd if=/dev/zero bs=1M count=10000|time scrypt enc --passphrase file:/dev/null - > /dev/null
10000+0 records in
10000+0 records out
10485760000 bytes (10 GB, 9.8 GiB) copied, 33.2267 s, 316 MB/s
31.71user 1.43system 0:33.22elapsed 99%CPU (0avgtext+0avgdata 264808maxresident)k
0inputs+0outputs (0major+65718minor)pagefaults 0swaps

This demonstrates that increasing the cunk size could bring more than a factor 10 increment in encryption speed. However, since the backup tool is maintaining a queue of up to ten files of chunk_size (plus maybe one more file currently being processed on either side of the queue), the room for improvement is limited, at some time the default 20 Gb disk size available to Dom0 will be exhausted.

Instead of increasing the chunk size it may also be possible to just tweak scrypt security parameters. By default the following settings are used:

[user@dom0 ~]$ scrypt enc --passphrase file:/dev/null -v - < /dev/null
Parameters used: N = 262144; r = 8; p = 10;

The parameter N = 262144 corresponds to --logN 18, log2(262144) = 16.

The following benchmarks show the encryption speed with different values for the --logN setting:

[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 18 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 4.35839 s, 24.1 MB/s
4.17user 0.15system 0:04.35elapsed 99%CPU (0avgtext+0avgdata 264784maxresident)k
0inputs+0outputs (0major+65718minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 17 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 2.27929 s, 46.0 MB/s
2.19user 0.07system 0:02.28elapsed 99%CPU (0avgtext+0avgdata 133808maxresident)k
0inputs+0outputs (0major+32950minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 16 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 1.27861 s, 82.0 MB/s
1.22user 0.04system 0:01.27elapsed 99%CPU (0avgtext+0avgdata 68340maxresident)k
0inputs+0outputs (0major+16565minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 15 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.775573 s, 135 MB/s
0.74user 0.02system 0:00.77elapsed 99%CPU (0avgtext+0avgdata 35360maxresident)k
0inputs+0outputs (0major+8372minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 14 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.523323 s, 200 MB/s
0.50user 0.01system 0:00.52elapsed 99%CPU (0avgtext+0avgdata 18972maxresident)k
0inputs+0outputs (0major+4277minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 13 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.399728 s, 262 MB/s
0.38user 0.01system 0:00.40elapsed 99%CPU (0avgtext+0avgdata 10812maxresident)k
0inputs+0outputs (0major+2231minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 12 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.343308 s, 305 MB/s
0.32user 0.02system 0:00.34elapsed 99%CPU (0avgtext+0avgdata 6808maxresident)k
0inputs+0outputs (0major+1206minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 11 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.315774 s, 332 MB/s
0.29user 0.01system 0:00.31elapsed 99%CPU (0avgtext+0avgdata 4672maxresident)k
0inputs+0outputs (0major+692minor)pagefaults 0swaps
[user@dom0 qubes]# dd if=/dev/zero bs=1M count=100|time scrypt enc --logN 10 -r 8 -p 10 --passphrase file:/dev/null - > /dev/null
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.297602 s, 352 MB/s
0.27user 0.01system 0:00.29elapsed 99%CPU (0avgtext+0avgdata 3628maxresident)k
0inputs+0outputs (0major+437minor)pagefaults 0swaps

This clearly shows that the encryption speed can drastically be improved by changing the scrypt security level. This will obviously come at the expense of making the backup more susceptible to brute force attacks. However a responsible user can compensate this by chosing a more secure password. So in order to improve backup performance without a breaking change of the backup fromat it may be a good idea to make the scrypt security level configurable, something like --logN 13 will bring about a 10-fold increment in encryption speed and may be a good compromise.

In the long run it may still be a good idea to make a breaking change to the backup format and use the expensive scrypt operation only one single time at the beginning of the whole backup and only do a simple authenticated encryption (without the scrypt algorithm) for the individual chunks of the backup.

[DemiMarie]

Current thoughts:

• It is possible to use the expensive scrypt operation only once by caching the result of the scrypt call.
• scrypt is not the current state-of-the-art password hashing algorithm; Argon2id is. This justifies a new major version in any case. The implementation of Argon2id in libsodium is very heavily optimized.
• libsodium provides the crypto_secretstream_* functions that could be used.

[jakoblell]

One more related note on backup efficiency: Storing all data in temporary files on disk as part of the encryption operation is not really optimal, it will add quite some load on the SSD. Depending on the hardware this may become the limiting factor, especially if we get something like a 10x boost in backup speed with zstd and fast encryption (and it will also wear out the SSD over time). Would be a lot more efficient to implement the whole pipeline (including compression, encryption and sending it to the destination qube) in memory, maybe that can be implemented as part of the migration from scrypt to libsodium.

[andrewdavidwong]

@DemiMarie:

scrypt is not the current state-of-the-art password hashing algorithm; Argon2id is. This justifies a new major version in any case.

If you think it warranted, I would recommend opening a separate issue for this, since it's a claim about backup security, not just efficiency. (This issue concerns only the latter.)

(Although we have https://github.com/QubesOS/qubes-issues/issues/971, I would not recommend reopening that issue for this, since that was about an older backup format version, and any future KDF change would result in a new backup format version.)