Talk:Disk encryption theory

From Wikipedia, the free encyclopedia

Contents

[edit] External links

Does the link to ipcores belong on this page or Disk encryption hardware? Kasperd 19:22, 3 September 2006 (UTC)

Cores are closer to crypto algorithms than to actual boxes, so I think the link has more affinity here. The Disk encryption hardware article does not currently mention LRW. Dimawik 03:58, 4 September 2006 (UTC)
I was under the impression that these are blueprints detailed enough that they could directly be turned into a piece of hardware. If I'm correct about this, I'd say they are closer to a piece of hardware than an algorithm. But still I agree they are not actual hardware. Kasperd 13:08, 5 September 2006 (UTC)

[edit] EME/CMC patents

Can somebody provide a link to the patent (I cannot find it on patft.uspto.gov) or at least where SISWG discusses it (their mail archive is public). GBL 12:13, 18 January 2006 (UTC)

Added.
Maxt 12:21, 19 January 2006 (UTC)Maxt

Regarding the request for the EME flaw: The reference for the EME mode flaw is in the process of being obtained. 11:57 11 September 2006

I removed the reference to the EME flaw until a proper sitation could be found chongo 13:05 11 September 2006

[edit] Integrity

The integrity paragraph in the problem definition section describes a sector per sector integrity. But this protection is of limited value as an adversary could combine data and metadata from different points in time and thereby trick the decryption module to decrypt the wrong data. This is a serious attack in scenarios where the adversary may have legitimate access to some of the encrypted data, but not all of them. Kasperd 10:16, 28 December 2005 (UTC)

To some extent it may even be possible to protect against rollbacks. This article by Kristian Gjøsteen has some discussion about it http://eprint.iacr.org/2005/083. Kasperd 10:29, 28 December 2005 (UTC)

Maybe this section should be moved to Talk:Disk_encryption. Kasperd 10:29, 28 December 2005 (UTC)

done GBL 11:31, 18 January 2006 (UTC)

[edit] LRW

I don't think that the following sentence is true: The LRW mode of operations was introduced by Liskov, Rivest, and Wagner. If it is true, then a reference should be added. Maxt 13:57, 6 January 2006 (UTC)Maxt

I also doubt that. They did introduce tweakable block ciphers in this article http://theory.lcs.mit.edu/~rivest/LiskovRivestWagner-TweakableBlockCiphers.pdf. LRW is based on this article, but it is not introduced in the article. So I also think a reference is missing to document who introduced LRW mode. Kasperd 12:09, 8 January 2006 (UTC)
LRW mode is what described in Theorem 2 of the ref combined with some particular 2-xor-universal (AXU_2) function. GBL 12:13, 18 January 2006 (UTC)
You are right. The LRW mode in fact was introduced by Liskov, Rivest and Wagner. They specify the mode generally. With other modes (like CBC or CTR) there are no prescribed ciphers. In case of LRW there are also no prescribed encryption or hash algorithms. Only the mode is defined. The choice of these algorithms has nothing to do with the mode as long as the algorithms fall into the right categories (i.e. a cipher, a hash function with certain desired properties). However, what's still unknown is who came up with the name LRW. Maxt 12:04, 19 January 2006 (UTC)Maxt

LRW issue: P1619 right now (Aug 30th 2006) appear to be unhappy with the LRW. Major changes are being proposed, see for example [1]. It seems like the activity is spurred by a comment made by Niels Ferguson in the Crypto conference. Essentially, if the K2 is accidentally (due to poor design of the overall system) is encrypted on the media, it is leaked. Dimawik 02:01, 31 August 2006 (UTC)

This issue has been known for years (and the IEEE drafts have mentioned it for years too). There's no news.
I agree with the first statement. But 30 messages on email reflector over a span of the day is news to me. Dimawik 07:54, 3 September 2006 (UTC)
The text of the article now says that the P1619 decided to replace the LRW. Minutes of the meeting contain no such thing. Any comments by people who know? Dimawik 00:45, 11 September 2006 (UTC)
The text of the article now says "SISWG is looking into possible alternatives including a replacement tweak function and a completely new mode". See below for more details. chongo 11:48 11 September 2006 (UTC).

Some members of P1619.0 informally discussed issues related to LRW. Following that discusssion a formal meeting of P1619.0 was held. The Aug 30, 2006 meeting minutes show:

There are implementations that cannot guarantee where and how K2 is stored and that is not followed by 0. This is clearly an issue with current proposal.
XCB could be used to realize a narrow block mode, or LRW could be fixed to address this issue (even if there are many applications). One possible solution would be to forbid SW implementation of LRW, and specify that is only for HW ones that do not store K2 on the data path.
A raw poll showed that almost no one would approve 1619 as is. We need to have a meeting soon where there are a few proposals to fix the tweak and decide upon that.
AI All: come back with a proposed tweak change for LRW and a better understanding of the collision problem.
Next meeting will be the start of 1619.0 and first item on the agenda will be to solve the tweak issue.

As of September 2006, the P1619.0 group is discussing variants on the LRW treak as well the replacement of LRW with XCB which can be seen in the P1619 Email archive. chongo 11:31, 11 September 2006 (UTC)

The article now states that:

"other types of encryption software (including on-the-fly volume encryption software, such as TrueCrypt) the probability that the tweak key will be encrypted with itself is negligible".

I'm curious how does TrueCrypt manages to prevent the LRW tweak key from being self encrypted? Do they use Encryption-Scheme Security in the Presence of Key-Dependent Messages or do they take other steps to keep the tweak key out of the plaintext stream? chongo 12:03, 11 September 2006 (UTC)

There are only a few ways to encrypt the tweak key currently in RAM with itself. One is bad design/implementation, the other is the tweak key being stored in swap/hibernation file. Now, two things: 1) TrueCrypt can't encrypt the operating system (so the swap/hibernation file senario does not apply to TrueCrypt). 2) TrueCrypt uses only random keys (rejects non-random-looking or low-hamming-weight keys) so the chance that the a plaintext block will contain the tweak key is 2**-128 for 128-bit ciphers and 2**-64 for 64-bit ciphers (ie. in both cases the probability is negligible).
There are other ways that an attacker can attempt inject a tweak key into the plaintext space. The RAM path you outline is just one of several possible vectors, BTW. And some of those vectors are not impacted by generating random or pseudo-random keys. In fact, some methods can make use of the fact that keys are being generated as part of their attack. I assume you have looked into such other attack vectors?
What other attack vectors are there? If an adversary was allowed to make you save your key material anywhere, no mode of operation can help you. You lose all security.
That might be true. However if you require the key material to only be stored on the encrypted device and give the encryption algorithm access to real randomness, there may be ways to achieve security. My point here is, that if key material is encrypted in some random way, which the adversary cannot predict, then I don't see an obvious way to force the key to be leaked except by using sector numbers as a covert channel since most storage encryption schemes do not hide access patterns.
Probably this approach does not lead to any efficient solution for the problem. Rather than assuming an arbitrary adversary to choose key dependent messages, we probably should consider some more restricted key dependent messages.
I can come up with one realistic attack vector. Assume the user decides to do a dump of system memory with the purpose of later performing some debuging analysis of the dump. Now performing such a dump to an unencrypted storage is always going to be a problem, and there is nothing to do about that. The user should know this and perform the dump to an encrypted storage, and obviously the key for this storage must currently be in memory, and thus written as part of the dump to the storage. Kasperd 14:49, 13 September 2006 (UTC)
If you use TrueCrypt as you are told to, you prevent this attack. The TrueCrypt documentation says: "we strongly recommend that you disable memory dump file generation on your computer at least for each session during which your work with any sensitive data and during which you mount a TrueCrypt volume". http://www.truecrypt.org/docs/?s=memory-dump-files . They also urge users to disable swap file, and hibernation file in the same situation.
It seems the reason they give such advice is because the file could potentially written to an unencrypted file system. If you configured the system to do such dumps to an encrypted storage, you would not expect the key to leak. However the way TrueCrypt works, it could leak. This is the reason LRW was rejected by SISWG P1619. It is a weakness in LRW, not specific to TrueCrypt. Kasperd 04:53, 17 October 2006 (UTC)
I agree. Well, it seems to me that they covered that issue specifically in another section of the "Security Precautions".Maxt 19:22, 17 October 2006 (UTC)
You are right, they actually do cover lots of security problems in that section. Notice the introduction Please note that it is impossible to inform about all security risks here. There are, unfortunately, too many of them and it would require thousands of pages to describe them. And indeed there are problems which are not mentioned. Kasperd 04:10, 20 October 2006 (UTC)
Yes, and what's your point again? Maxt 13:36, 20 October 2006 (UTC)
I was commenting on the discussion regarding one of the flaws in LRW. My point is, that there are real weaknesses in LRW. Things that could be safe with a better mode are not safe with LRW. Another point, which may not be that relevant to this particular discussion is the fact that TrueCrypt seems to assume the user knows about every possible weakness and avoids triggering them. Some users may have an intuition about what is safe and what is not safe (such as not storing an unencrypted version of the key or password), but I think very few users have an intuition about which things are unsafe to do because of obscure weaknesses (such as storing an encrypted version of a memory dump containing the key). It seems users are supposed to carefully read the entire documentation and remember all the weaknesses. And avoiding all of them may not be that practical. The LRW weakness may be mitigated by using different secondary keys before and after applying the block cipher. TrueCrypt does not have the tight memory requirements like some hardware implementations where every byte counts. Kasperd 19:22, 21 October 2006 (UTC)
> It seems users are supposed to carefully read the entire documentation and remember all the weaknesses.
Well if not the entire documentation, they should at least read the "Security Precautions" chapter. It's like driving your car above the maximum allowed speed of the tyres. You are supposed to read the maximum allowed speed of the tyres, remember it, and not exceed it. If you do exceed it, you may die. If one is from the lazy crowd, he will face the consequences. It's a serious security product and as such it requires a serious and responsible approach from the user, it's not a toy for the careless.
>The LRW weakness may be mitigated by using different secondary keys before and after applying the block cipher.
Based on my benchmarks, LRW mode is already 20% slower than ECB. Using two tweak keys would not only not be LRW mode anymore, it would also be 40% slower than ECB, which would be major slowdown (remember why they chose Rijndael as AES, instead of the slow Serpent?) And what would be the benefit? For the purposes of TrueCrypt the weakness is insignificant (it's a problem for full disk encryption software where the chance that the key will encrypt itself is not negligible, due to the swap file). For TrueCrypt, the LRW issues are practically non-issues (see above), and if they should become real issues, they are already mentioned in the manual. Maxt 11:36, 22 October 2006 (UTC)
I think you exaggerate the cost of using two different keys for tweaking. And I don't know what to make of your numbers without knowing what key size you used to perform those benchmarks. There is a difference in the performance when using 128 bit keys and 256 bit keys, but the absolute additional cost of doing LRW is the same in both cases. I didn't even know that TrueCrypt supported ECB mode, why include a mode known to be that weak? And are you sure the TrueCrypt implementation is optimal with respect to performance? There is a lot of potential for speedup of LRW by precomputing parts of the patterns needed for XOR. As for not being LRW I disagree, it still is LRW just with an additional whitening layer. You can do the full LRW and after that XOR with a pattern computed in the same way, but with a different key. But it is equivalent to just xoring the two keys before computing the pattern. Claiming that TrueCrypt is more secure than a full disk encryption doesn't make sense to me. It will always be less secure to store the key completely unencrypted rather than storing it on the media it is used to encrypt. Besides, encrypting a complete disk using TrueCrypt is just a matter of configuration. Kasperd 04:04, 23 October 2006 (UTC)
> I didn't even know that TrueCrypt supported ECB mode
I didn't say that TrueCrypt supports ECB mode, and it of course does not. My benchmark was basically based on comparing the speed of encryption of TrueCrypt 4.0 (CBC mode) and TrueCrypt 4.1 (LRW mode). There was a 15-20% slow down, obviously due to the addition of the LRW hash. I referred to it as ECB mode because it is the fastest mode (so it is ideal for performance comparisons) and CBC (TC 4.0) is just as fast as ECB.
> There is a lot of potential for speedup of LRW by precomputing parts of the patterns needed for XOR.
I believe TrueCrypt does that already. But you know more about the inner workings of TrueCrypt than I do probably.
> Claiming that TrueCrypt is more secure than a full disk encryption doesn't make sense to me.
I didn't claim that. If you read what I wrote again, you will see that what I wrote basically was: True full disk encryption software should not use LRW mode, because it has a non-negligible chance that the tweak key will encrypt itself. In contrast, in all configurations under which you can use TrueCrypt, the chance that the LRW tweak key will encrypt itself is practically negligible (and the obscure scenario where it could happen is documented in the TC manual).
> Besides, encrypting a complete disk using TrueCrypt is just a matter of configuration.
Yes, it is possible to do that by encrypting an image of a VMWare disk etc. But even in such configuration the tweak key would not encrypt itself even if it ended up in a swap file (the tweak key could end up in the swap file of the host operating system, under which VMWare would be running, but TrueCrypt cannot encrypt this "uppermost" swap file, so we're back to square one :-) And as the TrueCrypt manual recommends, this uppermost swap file should be disabled when you mount a TrueCrypt volume.Maxt 18:23, 25 October 2006 (UTC)
You should also be aware that encrypting a value that is a low hamming distance from a tweak key (no matter how the tweak key was generated) can leak key material. It is not sufficient to guard against encrypting the exact value of the tweak key.
You probably confuse this with the situation where the tweak key is low-entropy. Then if the plaintext is low-entropy too, collisions are more likely. If the tweak key is high-entropy and random-looking, the Liskov-Rivest-Wagner proof holds.

I removed all of that text about IEEE SISWG and TrueCrypt. The article on Disk encryption / LRW is not the place to debate a standard. Just stick to the LRW description. If you want to talk about the standard, then take that up in a standards body or start a Wikipedia page about SISWG. If you want to remark about the TrueCrypt implementation, then take those topics on the TrueCrypt. 15:25 13 September 2006

Since I think that the LRW text deleted by 67.188.223.123 has some value, I have moved it to the P1619 article, where the discussion about the current LRW tribulations seems to be a better fit. In the process, I have removed more controversial aspects of it (the ones that required citations :-) Dimawik 05:23, 14 September 2006 (UTC)
I have added a simple link to SISWG article to the LRW section. CMC/EME section does have a similar link. Dimawik 05:33, 14 September 2006 (UTC)

[edit] What is "F"?

The math in the treatment of LRW uses the symbol F which is not introduced in the paragraph. However, 'A' is used, so perhaps the math doesn't match the prose? I don't understand it so I can't fix it.

Also, the aside about precomputing uses a '+' symbol; I think a circled plus (XOR) is needed?

—Długosz

It looks like A and F both are names for the additional key. Pehaps we should take a look on the article introducing tweakable block ciphers to see what notation is used there. The + symbol of which you talk is addition in the finite field, and as such I don't think the using + can be considered incorrect. However since in in the standard representation addition in the field is the same as XOR, using the circled plus would be equally correct and possibly easier to understand. How about the XOR operation already used in the definition? Does the proof use properties of XOR or the finite field to show security? Kasperd 11:01, 6 February 2006 (UTC)
Fixed. GBL 13:21, 8 February 2006 (UTC)

[edit] Simple approaches

"On the other extreme it maybe be enough to adversary, who lured the user to store some file, to know that the file is actually stored (e.g., to convince the curt"

Can anybody figure out what that sentence was trying to say? I was about to fix the "maybe be" and then realized I really had no idea what was going on here...

It is a bit confusing. It doesn't quite fit with the rest of the text, even after being cleaned up. I believe what he is trying to say is something like this:
"Another difficulty with establishing a threat model is assessing the goal of the adversary. While most attackers are after the data on the hard drive, some attackers have different goals. One attacker may require a large portion of your data in order to act, while at the other extreme, it may be enough for the adversary to know only that a particular file was on the machine.
For example, some encryption methods encrypt the individual files, but not the filing system. This prevents the attacker from reading the file itself, but allows him to find the names of the files that are encrypted. If the attacker's goal was not accessing the data, but placing incriminating data on to the drive, he could then send the target a file containing incriminating information, with the intent that the target save the information to his drive. The attacker would then check to ensure that a file with that name had been saved to the drive, and contact the authorities to turn the person in.
If done properly, this could even work on an entirely innocent target. For instance, the attacker could send the target an encrypted file containing child pornography, then alert the authorities, supplying said authorities with the key to the file in question. The target, not possessing the key, would be completely unaware of the contents."
Filksinger 17:02, 16 October 2006 (UTC)

[edit] Clean-up

I made some clean-up and I hope to continue it soon (at least to describe how to encrypt 520-byte blocks). The following is a list of changes I made

  • Examples of what is “threat model” and how hard to get it right should be in threat model. I moved the text to talk:threat model.
  • “change the MBR to make the disk unbootable” does not hide information because you will end-up with non-bootable computer :-)
  • 520-byte sectors of AS/400 are mentioned in P1619/D9
  • Apparently, some believe that in E_K(P \oplus T) \oplus T (LRW) T is the tweak. It is not true, the tweak is the input to the cipher — I renamed T to X to avoid confusion.
  • Refs to hardware moved to disk encryption hardware.

Btw, I guess we should seriously clean-up this talk page as well GBL 16:58, 26 November 2006 (UTC)

Thanks for taking up the dirty work. :)
There's more to do than you can probably imagine at this point, please see Wikipedia talk:WikiProject Cryptography#Disk encryption reorganization. As for cleaning up talk pages: one does not clean them. If at all, they are archived, but the current talk page is not long enough to warrant that. Also, note that new comments should be added to the bottom, not at the top. -- intgr 17:11, 26 November 2006 (UTC)
I agree this talk page may be needing a cleanup. Maybe parts of it should be archived (though I don't know in details how archiving of talk pages work). But have all the things discussed on this page been fixed yet? Kasperd 06:28, 30 November 2006 (UTC)
See WP:ARCHIVE for details about archiving talk pages. -- intgr 07:47, 30 November 2006 (UTC)

[edit] typo in XEX?

"...and α is the primitive element of GF(2128) defined by polynomial x (0x2 in hexadecimal)."

0x2 in hexadecimal??? Doesn't make much sense to me. Does this mean 0*(x^2), which is 0? Or 0*x*2, which is 0 again? Or is "0x" the prefix for hexadecimal and it is the constant "2"? Maybe it's a typo for "K2 in hexadecimal" (the second key part)? 141.76.46.116 08:47, 30 August 2007 (UTC)

"x" is represented by an integer with the second least significant bit set: 10 in binary. "0x" is traditional notation for hexadecimal numbers. GBL 13:44, 1 October 2007 (UTC)