Not-different-enough IVs?
Message # 1
Date: Mon, 12 Dec 2005
To: practicalsecurity at hbarel.com
From: Hagai Bar-El
Subject: [PracticalSecurity] Not-different-enough IVs?
Hello,
When designing methods for disk encryption (sector-by-sector encryption), and when using CBC, it is customary to use the sector address, possibly along with other data, as the IV that is used for encrypting the sector data.
One such mechanism is part of CGD, which is documented in "The CryptoGraphic Disk Driver" by Roland C. Dowdeswell and John Ioannidis.
However, in their design they encrypt the sector address and use the ciphertext as an IV for the data encryption, rather than simply use the address as an IV, possibly along with some other data. The reasoning for this move is not straightforward to me. I see it as one extra encryption operation that comes for no visible need. The authors claim that (without encryption) adjacent sectors will have IVs that are just a few bits apart from each other. However, does this matter? Does anyone see the motivation for "hashing" addressed before using them as IVs?
Regards,
Hagai.
Message # 2
Date: Mon, 12 Dec 2005
From: Alexander Klimov
To: Hagai Bar-El
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
On Sun, 11 Dec 2005, Hagai Bar-El wrote:
The authors claim that (without encryption) adjacent sectors willFirst of all CBC with a non-random IV gives away information about plain text: if, say, one (even) sector starts with 'x...x0' and the next one (odd) starts with 'x...x1' (IV is the sector number), then the first block of both sectors will be the same.
have IVs that are just a few bits apart from each other. However,
does this matter? Does anyone see the motivation for "hashing"
addressed before using them as IVs?
Using this an adversary can sent to user a file with the above structure repeated several times and when convince the curt that a random garbage on the user's disk is not just garbage but an encrypted disk which stores the file sent by adversary.
--
Regards,
ASK
Message # 3
Date: Tue, 13 Dec 2005
To: Alexander Klimov
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
Cc: practicalsecurity at hbarel.com
Hi Alex,
At 12/12/05 12:42, Alexander Klimov wrote:
On Sun, 11 Dec 2005, Hagai Bar-El wrote:I agree. This seems as a most awkward attack in reality terms, but nonetheless a valid one that should, even for paperwork sake, be mitigated.
The authors claim that (without encryption) adjacent sectors willFirst of all CBC with a non-random IV gives away information about
have IVs that are just a few bits apart from each other. However,
does this matter? Does anyone see the motivation for "hashing"
addressed before using them as IVs?
plain text: if, say, one (even) sector starts with 'x...x0' and the
next one (odd) starts with 'x...x1' (IV is the sector number), then
the first block of both sectors will be the same.
Using this an adversary can sent to user a file with the above
structure repeated several times and when convince the curt that a
random garbage on the user's disk is not just garbage but an encrypted
disk which stores the file sent by adversary.
In practice, The attacker needs to make the victim store arbitrary data on his encrypted volume, this data should be long enough to cover enough sectors to form a proof, but yet not too long so not to be fragmented by the file-system into non-adjacent sectors... Okay, not a real problem for most users, but still something that it worth being mitigated.
Honestly, I wonder about the validity of the entire concept of concealing encrypted information. Most governments that look for people encrypting stuff, to the level of seizing their PCs, do not need formal proofs, they just need to suspect, and then they look for a proof somewhere else, if at all. A blob of several giga-bytes of DIEHARD-passing, seemingly random information, causes more suspicion than anything else, unless you can prove that designing PRNGs is your way to make a living. In other words, if you are found to be holding something that looks like encrypted data and does not seem like it can be anything else, you are in deep mud regardless of what can be "formally" proven by a bunch of similar sectors. :)
Also, what people tend to ignore is that, at least on Win32 machines, hiding the traces of the encryption application is orders of magnitude harder than hiding the ciphertext.
Again, this is not to deny the validity of the CBC attack, just to lessen its perceived implications.
Hagai.
Message # 4
Date: Wed, 14 Dec 2005
From: Stephan Neuhaus
To: Hagai Bar-El
Cc: practicalsecurity at hbarel.com
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
I agree. This seems as a most awkward attack in reality terms, butI don't agree. You yourself say that concealing encrypted information is not practical, so mitigating the threat of revealing that the data is encrypted has little practical value. Also, mitigating this threat will make the software more complex, more difficult to test or validate, and hence more prone to errors.
nonetheless a valid one that should, even for paperwork sake, be mitigated.
Fun,
Stephan
Message # 5
Date: Wed, 14 Dec 2005
To: Stephan Neuhaus
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
Cc: practicalsecurity at hbarel.com
Hi,
At 14/12/05 09:30, Stephan Neuhaus wrote:
It's not black and white. It's difficult to hide the existence of SEEMINGLY-encrypted data (unless when using steganography, but this has it's own issues), but whether or not this implies that we should not bother to prevent this data from being IDENTIFIED as a result of encryption depends on the opponent and on what you are trying to achieve. If being suspected is as bad as being convicted (or if being suspected equals being convicted) then there is no reason to bother making the identification of the encrypted data as such unprovable.I agree. This seems as a most awkward attack in reality terms, butI don't agree. You yourself say that concealing encrypted
nonetheless a valid one that should, even for paperwork sake, be mitigated.
information is not practical, so mitigating the threat of revealing
that the data is encrypted has little practical value. Also,
mitigating this threat will make the software more complex, more
difficult to test or validate, and hence more prone to errors.
Fun,
Stephan
In other cases it may. For example, if you face a legal system that requires the prosecutor to prove that the random data is indeed ciphertext and if an awkward method of inserting known blocks and showing the resulting ciphertext is a valid proof, then you will want to go the extra mile to make sure this is impossible.
BTW, I don't think it complicates the application by much. I think it can be enough to choose a mode such as LRW rather than CBC or to use encrypted addresses as IVs. I don't think it takes more than that.
Best regards,
Hagai.
Message # 6
Date: Wed, 14 Dec 2005
From: lists
To: Stephan Neuhaus
Cc: practicalsecurity at hbarel.com, Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
On 14 Dec 2005 13:22:59 -0500, Stephan Neuhaus wrote:
There is a difference between letting someone know you are using encryption, and breaking the privacy of that encryption through improper usage or poor choice in modes, the latter of which is what the attack pointed out does to some degree. Even ignoring the notions of indistinguishablity/semantic security that have commonly been used for describing the security of encryption schemes, when you think about why someone might use disk encryption, the ability to identify that certain data was encrypted and stored on the drive could be a significantly bad form of information leakage for them.I agree. This seems as a most awkward attack in reality terms, butI don't agree. You yourself say that concealing encrypted information
nonetheless a valid one that should, even for paperwork sake, be
mitigated.
is not practical, so mitigating the threat of revealing that the data is
encrypted has little practical value. Also, mitigating this threat will
make the software more complex, more difficult to test or validate, and
hence more prone to errors.
My previous post in response to this thread was bounced, but I included it below next as it has some links that might be of interest.
---
Message # 7
Date: Tue, 13 Dec 2005
On 12 Dec 2005 12:42:48 +0200, Alexander Klimov wrote:
On Sun, 11 Dec 2005, Hagai Bar-El wrote:This made me remember an implementation issue in loop AES (and others), and a quick Google (loop aes watermark) popped up a post [1] and a paper [2].
The authors claim that (without encryption) adjacent sectors willFirst of all CBC with a non-random IV gives away information about
have IVs that are just a few bits apart from each other. However,
does this matter? Does anyone see the motivation for "hashing"
addressed before using them as IVs?
plain text: if, say, one (even) sector starts with 'x...x0' and the
next one (odd) starts with 'x...x1' (IV is the sector number), then
the first block of both sectors will be the same.
[1] http://www.uwsg.iu.edu/hypermail/linux/kernel/0402.2/1137.html [2] http://mareichelt.de/pub/notmine/wisa2004.pdf
-Andrew
---
-Andrew
Message # 8
Date: Thu, 15 Dec 2005
From: Stephan Neuhaus
To: lists
Cc: practicalsecurity at hbarel.com, Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
lists wrote:
On 14 Dec 2005 13:22:59 -0500, Stephan Neuhaus wrote:I agree with the first part of your statement, but if I remember correctly, the attack used chosen plaintext to make two encrypted blocks equal and from this to infer that they must have been encrypted using CBC with the sector number as the IV[*]. This was merely to prove that encryption was used, not to get the plaintexts or to break the keys. In this case, there is no privacy that is broken because the plaintext is known.
There is a difference between letting someone know you are usingI agree. This seems as a most awkward attack in reality terms, butI don't agree. [...]
nonetheless a valid one that should, even for paperwork sake, be
mitigated.
encryption, and breaking the privacy of that encryption through
improper usage or poor choice in modes, the latter of which is what the
attack pointed out does to some degree.
My point was that attacks should not be mitigated "for paperwork sake", but only if the threat model says that they need to be mitigated.
Fun,
Stephan
[*] The logic behind this is a bit shaky, too. It is true that if "XOR of plaintext and IV is equal and encryptopn method is CBC" ==> "ciphertext blocks are equal", but it does not follow that "two blocks of seemingly random data are equal" ==> "blocks were encrypted using CBC with equal XOR of plaintext and IV".
Message # 9
Date: Thu, 15 Dec 2005
To: Stephan Neuhaus
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
Cc: practicalsecurity at hbarel.com
Hi Stephan,
At 15/12/05 09:45, Stephan Neuhaus wrote:
lists wrote:I think that what Andrew means is that the mere knowing that a piece of seemingly-random data is a result of encryption is enough of a violation of privacy for itself to be protected against, even if the plaintext cannot be determined.
There is a difference between letting someone know you are usingI agree with the first part of your statement, but if I remember
encryption, and breaking the privacy of that encryption through
improper usage or poor choice in modes, the latter of which is what
the attack pointed out does to some degree.
correctly, the attack used chosen plaintext to make two encrypted
blocks equal and from this to infer that they must have been
encrypted using CBC with the sector number as the IV[*]. This was
merely to prove that encryption was used, not to get the plaintexts
or to break the keys. In this case, there is no privacy that is
broken because the plaintext is known.
My point was that attacks should not be mitigated "for paperwork
(snip)
With regards to the "shakiness" of the proof, I agree that it is a complicated case, but please keep in mind that the proof method suggested by Alex used more than two sectors. Two similar sectors may say nothing, but 10 similar sectors, for example, are not likely to be caused by coincidence.
I cannot agree more with what you said about the no need to protect for sakes of "paperwork" alone. As I expressed in a previous post, in some (rare?) cases this needs to be part of the threat model. In other (most?) cases - mitigating this attack is a waste of time. I wouldn't worry about it on my own encrypted drives (I did not even rename them from the file extension that associates them with the encryption application :) ), but some people may have threat models that require such mitigation.
Hagai.
Message # 10
Date: Thu, 15 Dec 2005
To: lists
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
Cc: practicalsecurity at hbarel.com
Hello,
At 14/12/05 21:32, lists wrote:
This made me remember an implementation issue in loop AES (andI think this one presents a threat of encrypted volumes that is worth mitigating is a much bigger percentage of the cases than most others.
others), (snip...)
[2] http://mareichelt.de/pub/notmine/wisa2004.pdf
Of course, using CBC makes copy paste attacks leave only small tracks, and malicious alterations do not cause enough plaintext mess to always be noticed. These are, however, generic CBC problems that everybody using CBC is already aware of. This is also regardless of whether you encrypt the IVs or not.
The coolest attack was the detection of a watermarked file. The ability to detect a watermarked file "through" the encrypted volume, without knowing the key, is alarming and is something most designers should worry about.
The watermarked file is not a special file that the user needs to be convinced into storing and which "only" allows the attacker to know that a blob is an encrypted drive. The watermarked file is a "normal" file, having its own meaning and purpose, with additions. Most importantly, its detection does not indicate the mere use of encryption but rather the existence of that particular file within the encrypted drive. This has many threat scenarios, such as detection of illegal software, sensitive documents, political stuff, etc.
Hagai.
Message # 11
Date: Thu, 15 Dec 2005
From: lists
To: Hagai Bar-El
Cc: practicalsecurity at hbarel.com, Stephan Neuhaus
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
On 15 Dec 2005 11:36:16 +0200, Hagai Bar-El wrote:
At 15/12/05 09:45, Stephan Neuhaus wrote:Alexander gave a simple example of an attack based on a disk encryption scheme using CBC with a particular method for generating IVs. What I am trying to say is that this sort of thing compromises the privacy of the encryption scheme as used for disk encryption because it can be extended to attempt to identify that particular data was encrypted and stored on the disk, which is why I included a previous, bounced message that had links to such an occurrence, and not because it can identify that disk encryption was used. This sort of thing has been used in real-world attacks on actual disk encryption mechanisms, and those attacks did reveal that a particular file was very likely encrypted and stored on the disk (watermarking). This, for me, is a big problem, but, I agree with
lists wrote:I think that what Andrew means is that the mere knowing that a piece of
There is a difference between letting someone know you are usingI agree with the first part of your statement, but if I remember
encryption, and breaking the privacy of that encryption through
improper usage or poor choice in modes, the latter of which is what
the attack pointed out does to some degree.
correctly, the attack used chosen plaintext to make two encrypted
blocks equal and from this to infer that they must have been encrypted
using CBC with the sector number as the IV[*]. This was merely to
prove that encryption was used, not to get the plaintexts or to break
the keys. In this case, there is no privacy that is broken because the
plaintext is known.
My point was that attacks should not be mitigated "for paperwork
sake", but only if the threat model says that they need to be mitigated.
[*] The logic behind this is a bit shaky, too. It is true that if
"XOR of plaintext and IV is equal and encryptopn method is CBC" ==>
"ciphertext blocks are equal", but it does not follow that "two blocks
of seemingly random data are equal" ==> "blocks were encrypted using
CBC with equal XOR of plaintext and IV".
seemingly-random data is a result of encryption is enough of a violation
of privacy for itself to be protected against, even if the plaintext
cannot be determined.
With regards to the "shakiness" of the proof, I agree that it is a
complicated case, but please keep in mind that the proof method
suggested by Alex used more than two sectors. Two similar sectors may
say nothing, but 10 similar sectors, for example, are not likely to be
(snip)
agai and Stephan that we never defined a threat model, and I just assumed that this was a problem by default (because that is just my nature and what I think of as necessary security notions for a disk encryption scheme). But, to just disregard this attack outright as theoretical and paperwork, is, well, not my approach. My default setting is fix it if you know about it, and there have to be solid reasons to override this configuration of mine. (I guess that is why I like OpenBSD. ;) ) "Attacks only get better..." Going from Alexander's example to actual attacks on a prior version of loop A
S demonstrates that.
I only had a minute, so have fun with this big blob of text.
-Andrew
Message # 12
Date: Fri, 16 Dec 2005
From: Stephan Neuhaus
To: lists
Cc: practicalsecurity at hbarel.com, Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
lists wrote:
the disk, which is why I included a previous, bounced message that hadSorry, I didn't scan through the attached links. Indeed, if your threat model includes identifying known plaintext on an encrypted disk, this is a problem and needs to be fixed.
links to such an occurrence, and not because it can identify that disk
encryption was used.
encryption scheme). But, to just disregard this attack outright asIt's not mine either. I just balked at the notion of fixing a perceived threat "for paperwork's sake" (Hagai's words).
theoretical and paperwork, is, well, not my approach.
My default settingAnd my default setting is "fix it if you know about it and if you think it's a threat". Otherwise, we won't be getting anywhere. It regularly turns out that stuff that you think is easy to fix is in fact difficult to do right (for example, making sure that sensitive in-memory data is being zeroed after use[*]). You might therefore end up with a simpler and hence potentially more secure implementation if you don't fix something that's not actually a threat[**], especially if you do it wrong and believe yourself immune to an attack when you in fact aren't.
is fix it if you know about it, and there have to be solid reasons to
override this configuration of mine.
There are occasions where you don't have a choice but to fix things.
These occur when you must assume the strictest possible threat model by default. For example, if you're writing a crypto library, then you don't know whether it will be used to encrypt Grandma's Secret Apple Pie Recipe or data for nuclear missile control. You also can't trust users of the library to provide you with correct hints as to the threat model, so you don't have a choice other than to treat the recipe like the launch codes. An encrypted file system should probably fall into this category.
Fun,
Stephan
[*] ...which should be designed into the system from the beginning, but often enough isn't
[**] ...even though I have seen software that was advertised as "simple, hence secure" that wasn't.
Message # 13
Date: Sat, 17 Dec 2005
To: Stephan Neuhaus
From: Hagai Bar-El
Subject: Re: [PracticalSecurity] Not-different-enough IVs?
Cc: practicalsecurity at hbarel.com
Hi,
At 16/12/05 10:12, Stephan Neuhaus wrote:
lists wrote:I never stated that this attack should be disregarded altogether. I just implied that mitigation should be done to the light of the perceived threat, the ease of mitigation, as well as other parameters, and not for the sake of "paperwork" - hence, for the sake of assuring there is absolutely no issue that was not addressed.
encryption scheme). But, to just disregard this attack outright asIt's not mine either. I just balked at the notion of fixing a
theoretical and paperwork, is, well, not my approach.
perceived threat "for paperwork's sake" (Hagai's words).
On this particular attack that Alex presented, I actually wrote: "Okay, not a real problem for most users, but still something that it worth being mitigated." I think it should be mitigated not because it's a major threat, but because mitigation is easy, and it's all about balance.
In the case of this attack, the cons for mitigating are strong:
1. Most users don't care if the data is identifiable as cipher-text or not. (It's usually outside the threat model).
2. For the one ones who care, in many cases being suspected is as bad as being convicted.
3. Even if they solve the identifiability problem of the ciphertext, they are not likely to be able to hide the application anyway, so believing that they cannot be accused of encrypting information is a false sense of security for them.
Yet, I think that even to light of all these arguments, the attack should be mitigated, for one reason: it is very straightforward, and "risk-free" to solve it. Since it's just another AES operation per block, why not make the application suitable for those people who: have identifiability in their threat model && their opponent has to come up with a proof && a bunch of sectors is enough for a proof && they found a way to hide the application (will be glad to know how).
The attack presented by Alex (as opposed to the watermarking attack), to my opinion is actually worth mitigating primarily because it's a no-brainer to solve. If, for example, solving this problem would require using an unknown mode of operation (security risk), or double the code size (performance penalty + security risk), I would certainly see its mitigation as a "paperwork" issue, that is: mitigation for the purpose of a check-mark that is not worth it otherwise. In that case, the attack should have been disclaimed, but not mitigated.
The watermarking attack that Andrew pointed us to is worth mitigating even at very high cost, because it forms a more "visible" and widely-acceptable threat.
There are occasions where you don't have a choice but to fix things.Hey, my grandma would kill for a good apple pie recipe! :) I generally agree, but the fact that an application is flexible in its uses just pushes the bar higher, not to an unlimited extent. Some more attacks, especially of the marginal ones, would have to be solved. Yet, those that have too high cost in complexity may have to be left out for "specialized" versions of the code and omitted from the code being used by people who do not see these attacks as part of their threat model.
These occur when you must assume the strictest possible threat model
by default. For example, if you're writing a crypto library, then
you don't know whether it will be used to encrypt Grandma's Secret
Apple Pie Recipe or data for nuclear missile control. You also
can't trust users of the library to provide you with correct hints
as to the threat model, so you don't have a choice other than to
(snip)
Hagai.