Weekly Edition
Return to the Security page
| |||||||||||||
A weak cryptoloop implementation in Linux?
The "cryptoloop" code in the Linux kernel allows "loopback" mounts of
filesystems. Essentially, cryptoloop looks like a block driver which
encrypts data on its way through. It can thus be used to add encryption to
any of the standard Linux filesystems without changing the filesystem code
itself.
Recently, in response to a bug report with the 2.6.1-mm3 cryptoloop implementation, Jari Ruusu made a disturbing claim:
If you want your data secure, you need to re-encrypt your data
anyway. Mainline loop crypto implementation has exploitable
vulnerability that is equivalent to back door. Kerneli.org folks
have always shipped back-doored loop crypto, and now mainline folks
are shipping back-doored loop crypto. Kerneli.org derivatives such
as Debian, SuSE, and others are also back-doored.
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
A weak cryptoloop implementation in Linux? Posted Jan 22, 2004 11:00 UTC (Thu) by ekj (guest, #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 (guest, #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 (guest, #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 (guest, #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 20 ascii characters is a 130 bit key. - this is a worst case, but long enough to be secure IMO. My question is: was the loopback device ever MEANT to Further the other vulnerabilities should the loopback device is possibly the best way of securing -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
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: 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.
/amen :-)
|
|||||||||||||