Weekly Edition
Return to the Security page| Weekly edition | Kernel | Security | Distributions | Search |
| Archives | Calendar | Subscribe | Write for LWN | LWN.net FAQ |
A weak cryptoloop implementation in Linux?
Recently, in response to a bug report with the 2.6.1-mm3 cryptoloop implementation, Jari Ruusu made a disturbing claim:
It will come as no surprise that this message was followed by requests for more details on the "back-doored" cryptoloop. Jari obliged with a clear, technical explanation of what is going on. If you are using (or considering) cryptoloop. it is worth a look, even if there may be no need for immediate panic.
The problem, it seems, is that cryptoloop is susceptible to a certain kind of known plaintext attack. For any given filesystem type, the contents of certain sectors will be easy to predict. Given some time and an idle processor, an attacker can generate an exhaustive dictionary of likely passwords and the resulting ciphertext that will appear on disk. With access to the actual, encrypted disk, a quick lookup in the dictionary will yield the password and enable decryption of the entire filesystem. This attack is not practical for casual snoopers, but it would not be entirely surprising if government agencies and other, relatively organized groups had this sort of dictionary handy.
There are two ways of getting around this sort of problem. One is to choose a lengthy, non-obvious password. The other is to use salted passwords, where the password is modified by a randomly-chosen value before the data is encrypted. The salt value has to be retrievable, but it has the effect of requiring an attacker to create a separate dictionary for every possible number. If the range of salt values is large enough, salting the password will render the dictionary attack impractical.
The end result is that most cryptoloop users need not go into an immediate panic, but this weakness is worth being aware of. It would also be a good idea to get a stronger mechanism into the mainline kernel. There is little to be gained and much to be lost by shipping crypto code with known weaknesses.
(Log in to post comments)
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 8:32 UTC (Thu) by error27 (subscriber, #8346) [Link]
> Kerneli.org loop crypto implementation (and derived versions such as> Debian, SuSE and others) are vulnerable to optimized dictionary attacks
> because they use unseeded (unsalted) and uniterated key setup.
This is a flaw, but it's not a back-door. "Back-door" implies malice and deliberate deceit. It's a bad word to use unless you want to offend someone.
The article explains salting, but the other part of the solution is in the "uniterated". Basically, you take the password and the salt and you hash them. Take that hash and hash it. Repeat the process as many times as you can in .2 seconds. Save the salt and the number of times you hashed the password and salt so you can check the password later.
If you use a 128 bit salt the attacker can't use a dictionary attack directly, but he can still test thousands of possible passwords in a second. With the extra hash iterations the attacker can only test 5 possible passwords in a second.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 16:23 UTC (Thu) by freethinker (guest, #4397) [Link]
Well, multiplied by the number of processors and cycles the attacker has, with their large budget, compared to the number you have, with your single machine. But it's still a good idea, as long as the hash algorithm doesn't tend to converge or something.In any case, while salt is good and should be used in any implementation, real security comes from a good passphrase.
A weak cryptoloop implementation in Linux?
Posted Feb 24, 2004 21:38 UTC (Tue) by quantus (guest, #19763) [Link]
Wouldn't aplying an offset to losetup significanly increase the dificulty of finding the location ofthe encrypted "plain" text of which to launch the dictionary attack?
>On popular file systems
>such as ext2, ext3, reiserfs and not so popular minix, first 16 bytes of
>fourth 512 byte sector is such good known plaintext. Byte offset 0x600 to
>0x60F of plaintext contain all zero bits. File system itself does not use
>that data at all, but mkfs for file system in question puts that known
>plaintext there.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 11:00 UTC (Thu) by ekj (subscriber, #1524) [Link]
This is a quite strange claim. First, as is pointed out here, at worst it's a bug, not a back-door. A back-door is something deliberate.<p>Secondly, this does nothing at all for the attacker who wants to crack a single encrypted filesystem. It <b>is</b> true that because of the lack of salt, an attacker who wants to crack a large number of encrypted filesystems has an advantage as he can calculate the encrypted version of the "likely" passwords only once instead of once for each filesystem as would be required with a salt.<p>
However, this ain't *that* horrible a vulnerability. First, it only helps by a factor of how many encrypted filesystems (of the same type) you want to crack. Secondly, it only helps for those passwords that are simple enough that they'll appear in a list of "likely" passwords. With current storage it's not reasonable to create dictionaries much larger than a terabyte. So, loosely, if your password is not among the most common billion passwords, you're in the clear. Choosing a good password is required for security anyways.<p>
All this means is, if you need real security, choose a password with more than 40 bits of real entropy in it, or a dictionary like this could be constructed and help crack it. Dictionaries with much more than 2^40 entries are unlikely to be practical at the moment. <p>
Offcourse 2^40 possible keys kan reasonably be brute-forced even without a dictionary as a one-off crack. So to guard against this you'd want a better password than this anyway.<p>
It's true that the set of passwords that can a) Be reasonably memorized and b) cannot reasonably be brute-forced is rapidly approaching zero. But that's a fundamental problem and has nothing in particular to do with the crypto-loop implementation.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 13:29 UTC (Thu) by ballombe (subscriber, #9523) [Link]
[ I agree it is not a backdoor since it requires a dictionnary attack. ]> Secondly, this does nothing at all for the attacker who wants to crack a
> single encrypted filesystem.
That's not true. This weakness allows to precompute the table without
more knowledge of the targeted system. At this point, the part of
the exploit that require access to the crypto-loop device can be carried
out very quickly.
The second problem: if someone is able to have a quick access to the
device, he just need to read a known plain-text sector. With that
knowledge he can try a dictionnary attack to recover the password without
more access.
Suppose you keep password-less SSH keys on a crypto-loop on a USB stick:
with the attack above, the crypto-loop will be broken in before you notice
the USB stick was stolen so you may not have time to disabled them before
they get used.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 13:26 UTC (Thu) by macc (subscriber, #510) [Link]
What about replacing the knownplaintext strings with (random)
text?
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 13:45 UTC (Thu) by gyles (subscriber, #1600) [Link]
I imagine the known plaintext refers to known features of the file system - partition tables, inode/FAT tables, root directory structures etc.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 15:28 UTC (Thu) by IkeTo (subscriber, #2122) [Link]
But the alternative to just XOR every disk block with a 4096-byte random string (and store that string somewhere, in plaintext) before passing it to the loopback device will work to stop the attack described here.
A weak cryptoloop implementation in Linux?
Posted Jan 23, 2004 20:50 UTC (Fri) by Ross (subscriber, #4065) [Link]
Better would be to generate that random string through a pseudorandomnumber generator given a seed like the position of that block. I thought
this was already done? I mean this is basically the initialization
vector and without it identical blocks on disk would be identical after
they were encypted... leaking all kinds of information. If this is not
done it is a very serious bug. If it is done, why is this other attack
a problem? Is the seeds for the generator the same for every filesystem?
If so, a simple fix would be to store a single value to XOR with the
offset before calculating the IV.
A weak cryptoloop implementation in Linux?
Posted Jan 23, 2004 13:47 UTC (Fri) by bockman (subscriber, #3650) [Link]
I wonder if it is would be possible to store such 'known plaintext' as real plaintext, thus making it useless for an attacker. But maybe this would make the cryptoloop not transparent to the above file system code.The conclusion seems to be that it is more secure to encrypt each single file that the whole filesystem.
A weak cryptoloop implementation in Linux?
Posted Jan 22, 2004 20:32 UTC (Thu) by oak (subscriber, #2786) [Link]
Why not just calculate a number based on the password in range of:0 - [number of sectors in the loopfile]
And then offset the sectors on the loopfile by that number (and doing modulo when the sector index goes over number of sectors) when accessing the files?
That should be pretty easy to implement...
What about 20 characters?
Posted Jan 23, 2004 11:27 UTC (Fri) by paulsheer (guest, #3925) [Link]
When you run losetup, it does not let you proceed unless
the password is more than 20 characters:
/sbin/losetup -e AES128 /dev/loop0 FILE
Password: xxxx
Error: Password string must be at least 20 characters.
20 ascii characters is a 130 bit key.
if they are lower case only, and composed of whole
words (and, say, there are 10000 words to choose from)
then we have (10000^5) ~= 66 bits.
- this is a worst case, but long enough to be secure IMO.
My question is: was the loopback device ever MEANT to
be secure against a chosen plaintext attack? Surely not.
I believe it should be dead obvious to users
that a long key is essential because there is
no protocol protection.
Further the other vulnerabilities should
also be obvious: key snooping + memory snooping
during setup, etc. these are all *obvious* attacks that
the user ought to be aware of. Also you can't really be
protected against such attacks within the scope of what
such software is trying to provide.
the loopback device is possibly the best way of securing
your data because its simple and clean and basically as
as secure the block cipher you are using.
-paul
What about 20 characters?
Posted Jan 24, 2004 6:23 UTC (Sat) by obobo (guest, #684) [Link]
Typical entropy for text is about one bit per character, IIRC. That is taking into account correlations between adjacent words, etc. Granted that it is probably somewhat higher for short text fragments, but still... a dictionary of 2^40 passphrases would be rather potent for cracking 20 character text-fragment based passwords.
What about 20 characters?
Posted Feb 2, 2004 15:47 UTC (Mon) by lars_stefan_axelsson (guest, #10660) [Link]
Typical entropy for text is about one bit per character, IIRC. That is taking into account correlations between adjacent words, etc. Granted that it is probably somewhat higher for short text fragments, but still... a dictionary of 2^40 passphrases would be rather potent for cracking 20 character text-fragment based passwords.
Well, the estimates of the entropy of 'typical' English texts range from anywhere between 1.0 and 2.63 (One of Shannon's estimates), and 2.0 would give you 40 bits. However, and that's a big 'however' IMHO, we're not talking typical English text, but a passphrase. Password entropy can easily be 4 bits per character without having to remember a 'random' password, and there's no reason not to choose a passphrase consisting of several 'password like' words strung together.
That ought to give you a decent passphrase with sufficient entropy in 20 characters.
I'm ignoring the general hopelessness of the entire subject of passwords, of course. But if you're savy enough to be able to use loopback encryption, and sufficiently bothered by secrecy issues to bother, you ought to be able to come up with a decent passphrase and commit it to memory.
A weak cryptoloop implementation in Linux?
Posted Jan 23, 2004 16:21 UTC (Fri) by spudbeach (guest, #5837) [Link]
One other way around the problem is Cipher Block Chaining (CBC), where the output of each block is dependent on all prior blocks, as well as a randomly chosen initial vector (IV). That basically makes known plaintext / dictionary attacks such as this one useless, unless they are on the first block encrypted. All at very little cost to decrypt, too.Oh, and should anybody not trust Juri, note that he has been the big guy in the loop-AES project for a couple of years, doing loop mounted crypto outside of the kernel. Yes, he does know what he's doing. And yes, I'm sticking with loop-AES, for at least a couple of years. [And BTW: loop-AES is by design free from this attack: rather than using a passphrase directly, a true random key is used, which is then encrypted with a passphrase -- hence, one more step between the passphrase and known plaintext.]
Steve Beach
GPG key ID 7675D05E
A weak cryptoloop implementation in Linux?
Posted Jan 23, 2004 20:52 UTC (Fri) by Ross (subscriber, #4065) [Link]
Wouldn't that cause severe problem for a random-access read/write blockdevice? A change to a block would require reading, decrypting,
reencrypting, and finally re-writing every block that came after it!
A weak cryptoloop implementation in Linux?
Posted Oct 5, 2005 18:05 UTC (Wed) by kokopelli (guest, #11341) [Link]
You always have to read and write a complete disk page. Each page should be handled independently for various reasons. The only information that should "leak" into the encryption process is the absolute or relative block offset - as others mentioned it's used to set up a different 'initialization vector' for each page. (Global or per-page salt would also end up in the IV.)
Block ciphers will typically encrypt 8 to 32 bytes as a unit. If they're run independently you get a 'codebook' cipher - vulnerable to known-text attack anywhere within the disk page. If they're chained you're only vulnerable for the first cipher block of each page. There's no real cost to chaining as long as it doesn't extend beyond the disk page.
A weak cryptoloop implementation in Linux?
Posted Jan 30, 2004 20:57 UTC (Fri) by jmason (guest, #13586) [Link]
Surely lack of salting is a really basic issue? I'm surprised it took so long for someone to notice this, to be honest.A good implementation, actually, would be to reserve a few bytes at the start of every block for a per-block salt value; along with a per-volume salt, that should cause quite a bit of difficulty for prospective attackers. ;)
But I definitely would agree with other posters, and not call this issue a "back door".
A weak cryptoloop implementation in Linux?
Posted Feb 19, 2004 14:56 UTC (Thu) by raegis (guest, #19594) [Link]
I think people have been ignoring the problem for a long time.
A weak cryptoloop implementation in Linux?
Posted Mar 23, 2004 2:53 UTC (Tue) by sproket (guest, #20386) [Link]
This is just silly. Cryptoloop is not broken if you use it right, and there's no good reason to change the way it works. Especially now that the hashing has rightfully been pulled out of the kernel layer. All you have to do is copy a few bytes of random data into a file as a salt. Save it in clear form to your disk. Then when you want to setup encrypted swap, hash your salt file with your password and pipe that to losetup as your key. Voila!It would be terribly stupid to try and store the salt on the block device you were encrypting, it would either force you to overwrite block data, or shift it.
A Solution to the Known Plain Text Problem
Posted Jun 20, 2004 19:23 UTC (Sun) by nj (guest, #22465) [Link]
Here is a proposed solution to known plain text vulnerability. I am optimistic but not confident of it's cryptographic worth and would like feedback.The procedure:
Create and store a segment of random data equal in size to the data being encrypted.
XOR the user data with stored random data.
Encrypt both the random segment and the user data with conventional block cipher methods.
Since the user data was XORed with randomness, reminiscent of OTP, this would prevent usage of a precomputed dictionary against known plain text.
A weak cryptoloop implementation in Linux?
Posted Sep 13, 2004 13:38 UTC (Mon) by schander (guest, #24686) [Link]
The known-plaintext attack that is described is not specific to cryptoloop, but to just about any encrypted filesystem that does not pre-whiten the plaintext before encryption. Under no circumstance can this be called a backdoor in cryptoloop.
In any event, there are very simple existing userland fixes that make cryptoloop invulnerable to this kind of dictionary attack:
1) The simplest method involves the use of true cryptographically-random strings (from /dev/random, for example) as the first-level passphrase; encrypt them with a hashed, second-level salted passphrase as the key, and store the encrypted first-level passphrase with the salt. To setup the cryptoloop, just decrypt the encrypted first-level passphrase and use it.
(This is the approach that is taken by both pam_mount, as well as pam_losetup from my project, qryptix. In both cases, the main goal is to use the standard Linux login password (even with insufficient entropy) as the second-level passphrase. But the lack of entropy in the second-level passphrase is compensated for by salting and hashing it, and using it to encrypt a truly-random first-level passphrase. Any dictionary attacks on the second-level passphrase cannot be precomputed, because of the salt. Computing it on the fly will require calculating the hash, which is designed to be very slow.)
It also helped that util-linux-2.11 had another layer of ripemd160 hashing on the passphrase supplied to it, allowing for further whitening (just in case the entropy in /dev/random was inadequate).
2) Cryptoloop is also modular - this also us to iterate it two or more times with independent first-level keys, effectively multiplying the length of the key by the number of iterations. This is also easily supported in userland; qryptix, for instance, supports the use of multiple-iterated cryptoloops fairly trivially (e.g. /dev/hda9<->/dev/loop0<->/dev/loop1...).
With either of these two existing precautions, dictionary-based known-plaintext attacks on the filesystem, of the kind that Jari Ruusu describes, are a complete non-starter.
I fervently hope that Andrew Morton doesn't drop cryptoloop support in 2.6 because of this FUD. Cryptoloop just works, simply and reliably. I haven't ever lost a single bit of data using HVR's 2.4 kerneli patches.
A weak cryptoloop implementation in Linux?
Posted Dec 12, 2004 22:56 UTC (Sun) by markus76 (guest, #26625) [Link]
first of all, really "true cryptographically-random strings" would be directly derived from radioactive decay (which is purely random by nature), not from something inside a computer which is pseudo-random at best.
setting up several layers of encrypted block-devices is not the idea of cryptoloop both from a plain user's point of view and the ppl who introduced it into mainline kernels. it may work, but it is clumsy and unefficient.
nobody said one could lose data when using mainline cryptoloop, it's just a Bad Idea to do so. at least for data you want to be secure, anyway, and what is the point of using cryptoloop if your data is not secure? btw, when jari speaks of _equivalent_ to back door he means _equivalent_ to back door and not back door itself. should be obvious, but i got the impression that ppl increasingly start reacting to some kind of pavlov's bell instead of using their brain in the first place (no offense intended, just venting needed).
mainline cryptoloop is just not to be recommended if you want your data secure. a certain researcher in cryptography (whom i won't mention here, since he's got too much public attention already about just the same "trivial" topic we speak about) also points out these disadvantages of cryptoloop when it comes to security, he's given talks about it on security conferences, wrote articles, .... - what more info do you need?
if you want your data secure and want to stick with cryptoloop for the fun of it, that's fine with me. but don't try to evangelise mere users to believe cryptoloop is subject to some kind of bashing contest! it is not! let ppl make up their own minds, their data is their stuff, and turf.
cryptoloop is not a bad idea basically speaking, but it really needs to be fixed if it is to be used for the stuff is was made for: securing your data and not giving crypto(loop) a bad name.
/amen :-)