Improve qvm-backup key derivation/management #971
Comments
marmarek
added
T: enhancement
marmarek
added
the
help wanted
|
We need someone who know cryptography to check discussed key derivation scheme. Especially answer for questions in this message: https://groups.google.com/d/msg/qubes-devel/CZ7WRwLXcnk/1N0sYf6lVvUJ |
|
We may never get the assistance of a cryptographer on this. For now, we should at least pass the This would be better than nothing. Currently, |
|
On Thu, Oct 22, 2015 at 02:54:10AM -0700, Axon wrote:
As the user can (theoretically) freely choose encryption algorithm, just Best Regards, |
Two ideas:
I'm not aware of any. That would be my guess too... |
|
Based on this and after further research, I think it would be best to go with GPG for encryption (but not for integrity-verification). Ideally, we would read from the user-defined preferences in Recommended defaults: |
|
This seems to be the best option.
|
|
As for most secure gpg settings, check this out. Quote https://github.com/Whonix/anon-gpg-tweaks "Security and privacy enhancements for gnupg's config file for user
Not a bad thought. In past there were "known plaintext attacks", where Normally it should not. If it did, it would be a critical cipher weakness. I am just worried of the extra complexity of double encryption wrt to
Yes, programs should not rely on user settings in gpg supports --no-options (skip By the way, in Qubes Q3 (and earlier) you cannot continue to backup if |
Not encryption, just integrity protection - (.hmac files).
Can you create separate ticket for it? I was not aware of this Best Regards, |
Oops. Right.
Sounds good to me. :)
I suggested 65011712 as the default because it's the maximum. I think we should assume Qubes users want the "most secure" options by default. If they value backward compatibility more, they can override the defaults. (The security gain of the "most secure defaults" strategy is in some cases debatable, but the choice of defaults acts as an important reputational signal for a security-oriented OS.)
Yes, this is the other part of the problem.
True...
IANAC either. I take it integrity-protection from gpg can't be turned off?
The only reason I suggested parsing
Sorry, I don't understand. Can you rephrase?
Which file?
Would it be something like this? |
I'm glad you and @marmarek pointed this out to me. As mentioned in my previous message, my suggestion about reading from However, now I'm curious: Why is it such a bad idea for programs to read from/rely on
What does this mean? |
|
On Fri, Oct 23, 2015 at 07:16:42PM -0700, Axon wrote:
Yes, I think it can't be disabled.
qvm-backup (one program) should not read So for each option we should either set it explicitly on command line
Yes. Best Regards, |
|
Axon:
It's not super bad, not a huge issue, just bad practice. Because that
An optional, non-essential, nice to have, thing if someone contributes it. |
|
Axon:
I don't know if it should be turned off (why?) but it can be configured: --force-mdc / --disable-mdc |
Ok, that makes sense. Thank you for explaining it to me. :) |
Right, makes sense.
Oh, I see. Thanks. :)
Oh, ok. I guess the only reason to turn it off would be if we're worried about double integrity-protection causing problems, but it sounds like that's not really a concern. |
|
FWIW, I wonder whether the minimum effort variation would be to apply the key stretching just once, to encrypt a random master key. e.g.:
Using a unique key for each file's MAC resolves a possible issue where an attacker could swap files around in the archive, potentially migrating an infection from a lower-security VM to a higher-security VM. This also avoids having an attacker brute-force the user's passphrase against one/any of the HMACs. A NIST-specified KDF could be used on the Master Key to derive the other keys instead, but none lend themselves to being specified in an Alas, this proposal requires more operations before verifying the I've not looked at the code yet, but if GnuPG does not do /too much/ parsing, maybe it's still okay to use it for key stretching? There was actually a competition held recently to pick a good key stretching ("password hashing") algorithm. The winner was an entrant called Of course, the problem with exotic key stretching algos is that it's hard to use them without making manual backup recovery dependent on non-ubiquitous software. And a million iterations of SHA512 is much better than no stretching at all. I'll look into this a bit more later, and report back with any developments :) |
|
On Sun, Oct 25, 2015 at 10:13:47AM -0700, pqg wrote:
Generally we want to avoid doing to much low-level crypto handling,
This isn't a problem, because paths are stored inside of archive(s). Outer layer is only for convenience (streaming the backup while creating it, partial restore). Take a look at point 7 here:
Yes, IMO this is currently the main concern. When we get to the
I think we previously concluded, that we don't want to expose gpg to any unverified input.
And also using exotic algorithms isn't a good idea, because those didn't received that much review/analysis/tests. But generally IMHO Best Regards, |
Exactly. I'm skeptical that the practical security benefits of using a newer KDF will outweigh the benefits of being able to do manual backup recovery in a variety of disaster scenarios. Security-concious users (which almost by definition includes all Qubes users) ought to be using reasonably long, high-entropy passphrases (I'll refer to these as "good" passphrases for the sake of brevity). The current system (in which openssl applies a single round of md5) punishes users who pick good passphrases by capping maximum entropy at a measly 128 bits. We should fix that. However, my understanding (correct me if I'm wrong) is that S2K or PBKDF2, applied to good passphrases, will be uncrackable for the foreseeable long-term future (i.e., even if we assume many quadrillions of guesses per second, it would still take at least millions of years). If that's correct, then it seems to me that we should instead select the most trusted, tested, ubiquitous tools available. My backup is no good to me if I can't recover the data because the only software available to me is whatever's on an old Ubuntu disc, for example. (We can't predict in advance what kinds of emergency scenarios Qubes users might find themselves in, and under what conditions they might need manual access to their data.) |
|
Having said all that, if |
|
we should add a crypto tag to this (and any other similar issues) and I will create a thread with Cure53 (or NCC / iSec Partners) about this. They can provide free crypto advice to OTF-funded projects. |
|
Great idea! |
|
@axon-qubes I concur with your position that, if at all possible, the data should be recoverable with an "old Ubuntu disc". The scrypt binary and python-scrypt module don't seem to be currently packaged with Fedora anyway (they are available on Debian Jessie; I've not checked elsewhere). And keeping scrypt alongside the backup would be problematic if we need to invoke scrypt /before/ we can verify the integrity of anything. As an aside, I think we should distinguish between 2 uses of "KDF":
For instance, scrypt could provide function 2, but not function 1. Function 1 is served by things like NIST 800-108, which in the special case of all subkeys being of equal or shorter length than the underlying hash function, reduces to
...should work almost anywhere, yield the desired different keys for different purposes, and be just as secure as long as SHA-256 is a strong hash function. (The fancier derivation methods are just meant to give some additional protection if it should turn out that the underlying hash function is weaker than expected.) Though note that the Master Key (randomly generated or the result of scrypt or some other key stretching) will be a binary blob, which will be tough to pass via
So that the output is actually
With no key stretching, e.g. just take the SHA-256 of the passphrase, an attacker capable of 10 quadrillion tries a second for 10 million years would exhaust an ~101-bit keyspace. This represents approximately an 8-word diceware passphrase (~103 bits). With ~1million rounds of key stretching, as in S2K Mode 3 at max settings, ~81 bits of input keyspace could be searched, which requires a diceware passphrase of 7 words (~90 bits) though you would get pretty close with 6 words (~78 bits). A GPU running hashcat can currently trial on the order of 2 billion SHA-256 sums per second (2*10^9/sec) so 10^16/sec represents a powerful adversary indeed. 10 million years is of course just providing a robust margin of error, since in 30 years the crypto will be completely obsolete, and in 100 years we'll all be dead. So 128 bits is still enough for anyone. Unless your threat model includes the arrival of quantum computers in the very near term, in which case you should double all your symmetric crypto key length requirements. That said, as you originally advanced, even if nothing else changes from this discussion, None of this, of course, helps with the MACs, where we really want to salt and stretch the user's passphrase before doing anything, even if the same resulting key is used for both verification and encryption. Adding a salt not only avoids precomputaion attacks, but binds the files to the particular backup. While the renaming attack I previously feared is indeed impossible, I don't /think/ that there's currently any protection against shuffling in an identically-named VM from a different backup, as long as both backups were made with the same passphrase. However, there then needs to be some way to store the salt and, if variable, any key stretching parameters, and load them before verification. Would it be an acceptable risk to parse just the key=values out of the This certainly presents less attack surface than any way I can think of using GPG to do pre-verification stretching. Though, I'm aware I haven't actually proposed another way to perform key stretching yet. Python has baked-in The bcrypt functionality in On the other hand, the scrypt binary is pretty easy to build if you've got gcc and autotools. As mentioned, it's only good for encrypting/decrypting files, not plain key stretching, so we'd be back to the |
Yes, such attack probably is possible.
This might be some option if nothing better comes to us. Those
And according to previous comments,
I think we can simply have hex-encoded, encrypted master key included in And as the backup format is going to be more and more complex, maybe [1] Best Regards, |
|
Heads up that I added a feature to crack Qubes v3.1 (and think, but have not verified v3.2) backup encryption (default settings) to CrackStation: https://bqp.io/qubes-backup-encryption-added-to-crackstation.html I hope by doing this I'll attract some more cryptographers in here making sure the next version is rock solid. In case anyone wants a short-term workaround, what I've done personally is to encrypt my backup disk with LUKS, and then store my Qubes-encrypted backups on there. |
Yes, this applies to 3.2 also.
Thanks, @defuse. Related question: Theoretically, what's the fastest way to brute force a Qubes backup under the current scheme? There are at least two ways to go, right?
Is 1 theoretically faster because it entails a smaller keyspace? Or is there another, faster way? The reason I ask is because this would seem to affect estimates of how strong/weak the current system is (i.e., how long it would take to brute force given different values of passphrase entropy). |
No, 128 bits is an unthinkably large state space to try to brute-force. The set of md5(likely_passphrases) is sparse within that space, so you would definitely want to start with likely passphrase candidates and pass those through md5 to generate candidate aes keys, not try to randomly guess a correct 128-bit value (assumed to be so incredibly unlikely that it is why many standards target the 128-bit effective security level). The larger problem with this approach though is checking whether or not a resulting passphrase is correct. You then need to use the resulting key to try to decrypt the filesystem, and check if the plaintext looks like a filesystem. The HMAC-cracking approach has the benefit that it is immediately obvious whether or not the result is correct.
Yes. This.
No. The question is not about 128-bits vs 256-bits (both are assumed to be sufficient in crypto literature). The design flaw here is that is the HMAC and encryption key are derived from exactly the same input, and an HMAC construction allows fast (cheap to attack) checking of whether or not a key is correct (because it is designed for cheap message authentication using shared secrets), whereas a strong KDF is designed to be expensive-to-compute (and that expense does not need to be paid by an attacker who can bypass it by computing the HMAC for each candidate passphrase instead). Disclaimer: I am not a cryptographer, I just like reading and thinking about applied crypto, and occasionally have to crack passwords |
In its current (3.2) state, we essentially have the cheapest KDF possible, so I think the only safe way to use it is to have a passphrase that is already sufficiently high entropy for use directly as a key. When I used qvm-backup (to transfer VMs from old laptop to new laptop), I used a key from dd if=/dev/random, encrypted the result asymmetrically to a key generated on the destination machine, signed that with a key generated on the origin machine, performed the backup & transfer, then decrypted the used symmetric key on the destination machine. I think such an asymmetric scheme is really the way to go for various reasons, but I've yet to put my arguments together and formally make a case for it. tl;dr - allows to do away with passphrases and have a safely-stored offline backup-recovery key (which is not needed at backup-creation time), and a backup-origin signing key. This would enable the creation of encrypted and authenticated backups in a hostile environment where entering a backup passphrase would be problematic. |
That recovery key could (should) of course be protected with a passphrase itself, but it need not be used (or even known) at backup-creation time. |
Of course. I didn't say anything about randomly guessing 128-bit values. It goes without saying that you would prioritize the possible outputs of likely passphrases before unlikely ones. (This is, of course, an oversimplification of what sophisticated password crackers actually do.)
That's one thing I was wondering about. I suppose it depends on how much additional time it takes to attempt to decrypt the file with each key.
You're missing the point. The question is which one is theoretically faster. The question is not whether both would take a sufficiently long time.
I know. You just repeated the issue that I originally reported. |
Err, oops. Indeed. This thread has been so long I'd forgotten you were the OP. :) My apologies if you feel I've insulted your intelligence by my explanation. |
These are about equivalent, if you ignore the difference in time it takes to compute MD5 then AES vs. HMAC-SHA512.
The worst problem with the current system is that the password isn't salted. Without a salt, the attacker can perform their brute-force attack once, saving all the (HMAC, password) pairs they compute into a lookup table, then quickly crack any HMAC in that list with a fast (<1 second) lookup. That's a lot cheaper than having to re-run the brute-force attack for each hash (which using salt ensures). Fixing this changes the asymptotics of the best attack -- O(N) precomputation then O(1) for each hash to crack into no precomputation and O(N) for each hash to crack. The second problem is that we want to use some sort of slow key derivation function on the password, like Argon2, scrypt, bcrypt, etc, to increase the cost of attacks further. |
|
See #971 (comment) I think it all have been covered already (mostly by using |
|
One issue with new backup format is that each chunk (currently 100M) has key derived separately - and it takes time (by design). I think the easiest think to do is to increase chunk size to for example 1GB, to minimize the impact.
|
Is this "just" a performance issue, or is it also a security issue? How much of a performance impact are we talking about? Why is the current chunk size 100M in the first place?
Both of those options sound undesirable. Are there any downsides to just using a 1GB chunk size?
Not sure what you mean here. Why would we have to go through it all again? |
|
On Fri, Jan 13, 2017 at 01:44:14AM -0800, Andrew David Wong wrote:
> One issue with new backup format is that each chunk (currently 100M) has key derived separately - and it takes time (by design). I think the easiest think to do is to increase chunk size to for example 1GB, to minimize the impact.
Is this "just" a performance issue, or is it also a security issue? How much of a performance impact are we talking about? Why is the current chunk size 100M in the first place?
Yes, I think it is "just" performance issue. 100MB was arbitrary chosen as a
trade-off between space needed in dom0 temporary directory and
performance. There is also a second arbitrary number here: how many
chunks can be queued in dom0 - currently it is 10. Each chunk needs to
be first created in dom0 and only when the whole chunk is ready it can
be sent to VM/final storage. Having at most 10*100MB chunks means it
require at most 1GB, which is feasible to keep even in tmpfs (RAM), for
performance. Something like 10*1GB, or even 5*1GB probably will be too
much, so disk will need to be used (lowering performance).
> Looking at this long discussion, I don't want to go through it all along again...
Not sure what you mean here. Why would we have to go through it all again?
There are many tools, and assessing which is the best is tricky,
especially when none of us is a cryptographer...
…--
Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
|
|
In that case, I agree with you. Better to keep it simple and just increase the chunk size to 1GB (or some similarly suitable size). |
|
Keep in mind that some people want to backup things because their disk is almost full. That was the reason of using chunks in the first place. I feel that 1GB chucks are dangerous in such cases. For instance, if I have 5GB free, the backup should not queue more than 4 chunks of 1GB. With lvm thin provisioning, I usually ends up with a read-only device with IO errors because of a full disk, with no opportunity to clear some free space without running a live cd. |
|
Just to add to the discussion. I worked on an alternative version that still uses openssl enc and dgst while using python hashlib key derivation function:
Problems are:
|
Then tmpfs could be used (so RAM + swap). When using 1GB chunks, maximum number of them should be probably decreased to 5 or so (currently it's 10). The number of chunks in the queue is not really important as long as it isn't 1 - it should be only large enough to allow parallel uploading one chunk while preparing the next one. Maybe a good compromise would be 4x500MB? |
|
Yes, most Qubes users probably use at least 8GB of RAM, and most VMs currently needs to be stopped to perform backups. So we can hope that there is 4GB of free space in dom0, or maybe we can request that before performing a backup, and warn the user about bad performance if this assertion failed ? |
|
If the performance impact is significant (e.g., at least several minutes faster per |
|
It's about 1s for the sole KDF. Lets do some math: assume 100GB backup, with VM sizes being multiply of 1GB. This gives:
Is ~3.5m bad? |
|
Suppose a single user makes weekly backups for a year: Suppose a little under 10% of the estimated Qubes userbase does this: So, even with conservative assumptions, we'd be saving users thousands of hours per year, collectively. And the only cost is that users with only 4GB of RAM may have to shut down their VMs before they run |
|
I don't see why to look at collective time of Qubes userbase. It isn't really observable value for anyone. But it does make sense to look at time spent/saved per year. |
|
On Feb 16, 2017 14:47, "Andrew David Wong" <[email protected]> wrote:
If the performance impact is significant (e.g., at least several minutes
faster per qvm-backup) on systems with sufficient RAM, then I recommend
keeping the larger 1GB chunk size. As @ptitdoc <https://github.com/ptitdoc>
pointed out, most Qubes systems will have at least 8GB. The ones that have
less will never be running many VMs anyway, so it won't be hard to shut
them down for qvm-backup. Meanwhile, the vast majority of users will
benefit from performance gains on a task they do (or should be doing)
frequently. Across all Qubes users, this seems like it could easily add up
to thousands of hours saved over the lifetime
Users should know explicitly the requirements for backup before them start
it. No matter of the chunk size you agree on the requirement to have X
gigabytes on disk or free ram should appear before process is allowed to
start. BTW: if you want that size on disk - why not to reserve it by
creating loop-mounted image of that size for backup operations, then use
and finally delete it? If the memory minimum could be located that way -
why not to do this on backup start?
|
|
I don't see a fundamental reason why the KDF needs to be recomputed for each chunk... the output of the KDF should be safely cacheable, just as we must cache the plaintext passphrase between chunks today. Do I understand correctly that the current KDF-recomputation-on-each-chunk is just an artifact of wanting to build the backup system out of guaranteed-to-be-easily-obtainable-in-the-future programs and treat each such program as a black box, and the single scrypt binary being responsible for both computing the KDF and doing the bulk encryption, thus having no clean way to cache the KDF output? Or is there some other reason? |
|
Yes, exactly this one alone. |
marmarek
added
the
release notes
See:
https://groups.google.com/d/msg/qubes-devel/CZ7WRwLXcnk/u_rZPoVxL5IJ
The text was updated successfully, but these errors were encountered: