Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

This is really interesting! The webpage

http://standards.ieee.org/about/sasb/patcom/pat1390.html

links to a non-awareness statement of UC Davis concerning IEEE Standard No. 1619.2 (that standardizes EME2). By the way there is also a mail discussion of the corresponding IEEE working group:  http://grouper.ieee.org/groups/1619/email-2/msg00005.html, that also links to this „Letter of Asssurance“.

This document states the submitter's (UC Davis) position as:

„After a Reasonable and Good Faith Inquiry, the Submitter is not aware of any Patent Claims that the Submitter may own, control, or have the ability to license that might be or become Essential Patent Claims.“

As far as I understand, this „only“ certifies that UC Davis is not aware of any patent claims or pending patent applications after asking people/employees involved in this matter. This does not sound as a patent disclosure to me, which might rather be checking boxes 1. and c. in section D. of that Letter of Assurance. But on the other hand D.1.c. would be a really hard statement.

I do not know the real-life meaning of this non-awareness statement. But my first feeling is that (IEEE-1619.2 standardized) EME2 is good to go from an intellectual property point of view. That's just my feeling though.

Stavros

> >> BTW anyone know what had happened with EME2 wide mode?
> >> [snip long link]
> >
> > As far as I know there are intellectual-property issues:
> >
> > P. Rogaway, Block cipher mode of operation for constructing a
> > wide-blocksize block cipher from a conventional block cipher, US Patent
> > Application 20040131182 A1 _______________________________________________
>
> Hey, this caught my attention so I contacted Dr. Rogaway. Included below is
> the email conversation (my apologies for the format, he replied at the top
> so I followed suit):
>
> =======
>
> > Cool, thank you. It seems there was some misinformation in that thread
> then,
> > so would you mind if I quoted your response?
>
> Go right ahead.
>
> Best wishes,
> Phil Rogaway
>
> > On Friday, February 08, 2013 09:34:14 AM you wrote:
> >> Hi Alex,
> >>
> >> There is no Rogaway or UC patent related to EME2.
> >> The University of California did do a patent application,
> >> but abandoned it (that is, decided not to pursue a utility patent).
> >> I had to look up some old correspondence to remind myself of this,
> >> but it seems that we informed Matt Ball and Jim Hughes back in Nov 2007
> >> that there'd be no patent, filling out some IEEE patent-disclosure
> >> form saying this, too.
> >>
> >> Best wishes,
> >> phil rogaway
> >>
> >> On Fri, 8 Feb 2013, Alex Elsayed wrote:
> >>> Hi, I was wondering if you had any plans to (explicitly) offer similar
> >>> terms regarding open-source software for EME2 as you recently have for
> >>> OCB. There was a recent discussion on the dm-crypt mailing list with the
> >>> title "Cryptographic issues with SSD-technology and wide-block
> encryption
> >>> modes." In the course of the discussion Milan Broz, the maintainer of
> >>> dm-crypt, stated the following:
> >>>
> >>> "[It] would be nice to have some not patent encumbered wide mode (no
> code
> >>> changes needed, just someone have to invent it and add to crypto API)"
> >>>
> >>> I'm just someone who reads the list, but I thought I'd write to point
> out
> >>> that there's interest.
> >>>
> >>> (Frankly, I'm also very interested in OCB, but the other AE patents have
> >>> an
> >>> exceedingly unfortunate chilling effect independent of your license.)

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Arno Wagner]

Hmm. Was the original publication on EME2 by them?
There is also a possible problem if the EME patent holder 
thinks it covers EME2.

Arno

On Tue, Feb 12, 2013 at 09:47:01AM +0100, Stavros Kousidis wrote:
> This is really interesting! The webpage
> 
> http://standards.ieee.org/about/sasb/patcom/pat1390.html
> 
> links to a non-awareness statement of UC Davis concerning IEEE Standard No. 1619.2 (that standardizes EME2). By the way there is also a mail discussion of the corresponding IEEE working group:  http://grouper.ieee.org/groups/1619/email-2/msg00005.html, that also links to this „Letter of Asssurance“.
> 
> This document states the submitter's (UC Davis) position as:
> 
> „After a Reasonable and Good Faith Inquiry, the Submitter is not aware of any Patent Claims that the Submitter may own, control, or have the ability to license that might be or become Essential Patent Claims.“
> 
> As far as I understand, this „only“ certifies that UC Davis is not aware of any patent claims or pending patent applications after asking people/employees involved in this matter. This does not sound as a patent disclosure to me, which might rather be checking boxes 1. and c. in section D. of that Letter of Assurance. But on the other hand D.1.c. would be a really hard statement.
> 
> I do not know the real-life meaning of this non-awareness statement. But my first feeling is that (IEEE-1619.2 standardized) EME2 is good to go from an intellectual property point of view. That's just my feeling though.
> 
> Stavros
> 
> > >> BTW anyone know what had happened with EME2 wide mode?
> > >> [snip long link]
> > >
> > > As far as I know there are intellectual-property issues:
> > >
> > > P. Rogaway, Block cipher mode of operation for constructing a
> > > wide-blocksize block cipher from a conventional block cipher, US Patent
> > > Application 20040131182 A1 _______________________________________________
> >
> > Hey, this caught my attention so I contacted Dr. Rogaway. Included below is
> > the email conversation (my apologies for the format, he replied at the top
> > so I followed suit):
> >
> > =======
> >
> > > Cool, thank you. It seems there was some misinformation in that thread
> > then,
> > > so would you mind if I quoted your response?
> >
> > Go right ahead.
> >
> > Best wishes,
> > Phil Rogaway
> >
> > > On Friday, February 08, 2013 09:34:14 AM you wrote:
> > >> Hi Alex,
> > >>
> > >> There is no Rogaway or UC patent related to EME2.
> > >> The University of California did do a patent application,
> > >> but abandoned it (that is, decided not to pursue a utility patent).
> > >> I had to look up some old correspondence to remind myself of this,
> > >> but it seems that we informed Matt Ball and Jim Hughes back in Nov 2007
> > >> that there'd be no patent, filling out some IEEE patent-disclosure
> > >> form saying this, too.
> > >>
> > >> Best wishes,
> > >> phil rogaway
> > >>
> > >> On Fri, 8 Feb 2013, Alex Elsayed wrote:
> > >>> Hi, I was wondering if you had any plans to (explicitly) offer similar
> > >>> terms regarding open-source software for EME2 as you recently have for
> > >>> OCB. There was a recent discussion on the dm-crypt mailing list with the
> > >>> title "Cryptographic issues with SSD-technology and wide-block
> > encryption
> > >>> modes." In the course of the discussion Milan Broz, the maintainer of
> > >>> dm-crypt, stated the following:
> > >>>
> > >>> "[It] would be nice to have some not patent encumbered wide mode (no
> > code
> > >>> changes needed, just someone have to invent it and add to crypto API)"
> > >>>
> > >>> I'm just someone who reads the list, but I thought I'd write to point
> > out
> > >>> that there's interest.
> > >>>
> > >>> (Frankly, I'm also very interested in OCB, but the other AE patents have
> > >>> an
> > >>> exceedingly unfortunate chilling effect independent of your license.)
> _______________________________________________
> dm-crypt mailing list
> dm-crypt@saout.de
> http://www.saout.de/mailman/listinfo/dm-crypt

-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Alex Elsayed]

Stavros Kousidis wrote:

>> BTW anyone know what had happened with EME2 wide mode?
>> [snip long link]
> 
> As far as I know there are intellectual-property issues:
> 
> P. Rogaway, Block cipher mode of operation for constructing a
> wide-blocksize block cipher from a conventional block cipher, US Patent
> Application 20040131182 A1 _______________________________________________
> dm-crypt mailing list dm-crypt@saout.de
> http://www.saout.de/mailman/listinfo/dm-crypt

Hey, this caught my attention so I contacted Dr. Rogaway. Included below is 
the email conversation (my apologies for the format, he replied at the top 
so I followed suit):

=======

> Cool, thank you. It seems there was some misinformation in that thread 
then,
> so would you mind if I quoted your response?

Go right ahead.

Best wishes,
Phil Rogaway

> On Friday, February 08, 2013 09:34:14 AM you wrote:
>> Hi Alex,
>>
>>   There is no Rogaway or UC patent related to EME2.
>>   The University of California did do a patent application,
>>   but abandoned it (that is, decided not to pursue a utility patent).
>>   I had to look up some old correspondence to remind myself of this,
>>   but it seems that we informed Matt Ball and Jim Hughes back in Nov 2007
>>   that there'd be no patent, filling out some IEEE patent-disclosure
>>   form saying this, too.
>>
>> Best wishes,
>> phil rogaway
>>
>> On Fri, 8 Feb 2013, Alex Elsayed wrote:
>>> Hi, I was wondering if you had any plans to (explicitly) offer similar
>>> terms regarding open-source software for EME2 as you recently have for
>>> OCB. There was a recent discussion on the dm-crypt mailing list with the
>>> title "Cryptographic issues with SSD-technology and wide-block 
encryption
>>> modes." In the course of the discussion Milan Broz, the maintainer of
>>> dm-crypt, stated the following:
>>>
>>> "[It] would be nice to have some not patent encumbered wide mode (no 
code
>>> changes needed, just someone have to invent it and add to crypto API)"
>>>
>>> I'm just someone who reads the list, but I thought I'd write to point 
out
>>> that there's interest.
>>>
>>> (Frankly, I'm also very interested in OCB, but the other AE patents have
>>> an
>>> exceedingly unfortunate chilling effect independent of your license.)
>

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Milan Broz]

On 02/06/2013 02:34 PM, Stavros Kousidis wrote:
>> But that said, yes I'm very well aware of this problem and I would
>> like to have at least some analysis what's really going on in todays
>> flash storage devices and how it is related to disk encryption security.
>> So let's try to gather some data first.
> 
> That clarifies some things to me, and yes, I would also like to know what's happening inside those things. Especially since I have seen:
> http://static.usenix.org/events/fast11/tech/full_papers/Wei.pdf

yes, this is nice paper!

Please if anyone here have more such pointers, please post it here!

I am quite interested in research here and there are several interesting
interactions which surely need more coverage.

>> But do not forget one thing - while cryptsetup is always open to support
>> wide range of algorithms, a huge user base is bound by standards which do not
>> allow them to use anything else. That's why XTS is so widely used.
> 
> Ok that sounds reasonable (doable???). What exactly do you mean by a huge user base being bound by standards and to XTS?

I mean users which are required to comply (at least to some extent) to FIPS standards for example.
(Usually government & public sector etc.)
Here, AFAIK, you can use AES and CBC or XTS modes only.
And I am trying to keep default cryptsetup/LUKS modes compatible with these,
but really, that was just note that many people will (or will have to) prefer standard modes
(which get more analysis as well).

Milan

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

> BTW anyone know what had happened with EME2 wide mode?
> http://siswg.net/index.php?option=com_content&task=view&id=36&Itemid=1[http://siswg.net/index.php?option=com_content&task=view&id=36&Itemid=1]

As far as I know there are intellectual-property issues:

P. Rogaway, Block cipher mode of operation for constructing a wide-blocksize block cipher from a conventional block cipher, US Patent Application 20040131182 A1

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

> The main problem (I see) with these analysis is that it usually
> take just part of the system (either SSD architecture or block encryption).
> 
> But it is more complex system with several layer interfering, this
> interference can make the problem with ciphertext block copies worse
> but also decrease impact.
> 
> An example (illustrative but I hope not completely wrong:)
> 
> Imagine you have write pattern changing several consecutive 512 bytes
> sectors with some delay between writes.
> 
> In theory, that's exactly case you are describing,
> you will get several copies inside SSD (on flash chips)
> because of wear leveling and similar techniques (do not forget
> internal garbage collection as well).
> 
> In reality, it depends
> 
> - Filesystem above uses large blocks as well (most common is page size 4k I think).
> The filesystem (and page cache) will send IO request only of this block (page)
> size, not 512 bytes sector. Depending on timing, you will see either
> several IOs or only just one (write-cache effect).
> 
> - The transparent dmcrypt is using 512 bytes for encryption but it always
> encrypts the whole submitted IO before resending. (Let's ignore
> corner case with IO split because of lack or memory or storage restriction for now.)
> (Note dmcrypt has no own IO scheduler but it has internal queues for
> requests - so there is some delay in processing.)
> 
> - The encrypted IO request is submitted to underlying device, where
> IO scheduler is responsible for real submission to device.
> And here it can be (and will be with exception of noop scheduler)
> merged into one big IO.
> 
> - internal SSD architecture, and storage in general, have write-cache
> internally and will optimize writes as well.
> 
> - storage (specifically SSD) uses hints for IO size, and every user
> in kernel should (or must) produce IOs restricted by these hints
> 
> So, in this example you changed e.g. whole 4k page in several writes,
> but you cold see just one final IO! All it depends how the stack is
> configured and how filesystem is using Flush/FUA requests to sync
> IO in-flight.
> 
> There is always some corner cases but I am trying to say that I am not
> sure if this problem is really so important in usual use cases.
> 
> (As someone already mentioned, there are other attack vectors where the risk
> is probably higher.)
> 
> But that said, yes I'm very well aware of this problem and I would
> like to have at least some analysis what's really going on in todays
> flash storage devices and how it is related to disk encryption security.
> So let's try to gather some data first.

That clarifies some things to me, and yes, I would also like to know what's happening inside those things. Especially since I have seen:
http://static.usenix.org/events/fast11/tech/full_papers/Wei.pdf


> > A countermeasure to those history-building SSD-mechanisms is to blur
> > what is written to the flash device by forcing a multi-sector-wide
> > change when a bit changes (preferrably: multi-sector = size of file
> > system blocks). There are two concrete realizations of that strategy
> > that I know of:
> >
> > 1) Use random IVs. Leaves you with data expansion, since you have to
> > store the IVs, and a pain in the *** effort to implement this
> > reliably.
> 
> Anything what need more space is problem (that includes data integrity,
> auth tags, whatever). And IMHO (pseudo-)random IV will cause more
> problems than it solves.

That's true. I just included it to mention a no-go.

> > 2) Add a (claimed patent free) wide-block mode like TET or HEHfp (see
> > articles below) from the Hash-Encrypt-Hash family to the Crypto-API
> > and change the dmcrypt crypto engine to handle variable block sizes
> > instead of always operating on 512 Bytes of data (compare the
> > discussion:
> > http://www.saout.de/pipermail/dm-crypt/2011-April/001667.html)
> 
> Yes, the work on deploying new cipher or encryption mode (either narrow or wide)
> for Linux block encryption starts in Linux kernel API.
> 
> Send a patch to crypto kernel API list, get it in official kernel
> and dmcrypt/cryptsetup can start to use it.
> (But if there is any patent problem, no chance...)
> 
> But do not forget one thing - while cryptsetup is always open to support
> wide range of algorithms, a huge user base is bound by standards which do not
> allow them to use anything else. That's why XTS is so widely used.

Ok that sounds reasonable (doable???). What exactly do you mean by a huge user base being bound by standards and to XTS?

Stavros

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

Wow, there has been a lot of response. Thanks!
This is what I wrote so far.
Let me post it and I try to reply to the other messages.
=====================================================================================

> I am aware of that issue. However, XTS mode should lead to a full sector
> (512 Bytes) chage even if only one bit is changed. That is the whole
> point of modes like XTS, EME, etc.

XTS-AES-128 (key size is 256 bit then) is by design a narrow-block en-/decryption mode, i.e. a (thank god) *parallelizable* en-/decryption of consecutive 128 bit = 16 bytes sized blocks of data inside the 512 bytes sector. This makes 32 parallel en-/decryptions and flipping the 2345th bit in that sector will change the 19th block out of those 32 and nothing more (remember that the IV is constant for that sector; a fresh random IV instead would trigger a sector-wide change but leads to data expansion). This is simply ECB mode without mixing (as e.g. in EME - standardized but patented) or universal hashing (as e.g. in TET, HEHfp). Nevertheless, XTS is a damn fine mode of operation :-)


> I think you just have to live with it at this time. It is not a severe
> vulnerability in most situations. And it will not build up to badly, at
> some time the blocks get re-used. The amounth of spares/write pool
> in SSDs seems to be shrinking as well.

That is true, I agree to such a pragmatic approach. But again: in XTS operation mode a single bit changes only 16 bytes of data and not the whole sector. It is definitely *not* a pseudo-random permutation on the sector as e.g. EME, XCB, TET or HEHfp. Anyway, I do think that there are other attack vector


> > 1) Use random IVs. Leaves you with data expansion, since you have to store
> > the IVs, and a pain in the *** effort to implement this reliably.
>
> It is. It also breaks the dm-model as additional accesses
> are required. Not an option, I think.

Absolutely.


> > 2) Add a (claimed patent free) wide-block mode like TET or HEHfp (see
> > articles below) from the Hash-Encrypt-Hash family to the Crypto-API and
> > change the dmcrypt crypto engine to handle variable block sizes instead of
> > always operating on 512 Bytes of data (compare the discussion:
> > http://www.saout.de/pipermail/dm-crypt/2011-April/001667.html)
>
> I will have a look at the articles, but I think this is not
> really an option either, agen because of mismatch with the
> dm-layer.

I would really like to understand this mismatch better. Is there any documentation that I could read except the source code itself? I am not a kernel space developer and would like to understand why (and what kind of) incompatibility issues arise when you think about a variable size of data processing via the dm-crypt crypto engine. I thought the file system block size is the smallest entity that is written and read in the system anyway. Why split this into 512 Byte chunks of data and not process the data that is carried through the crypto engine as a whole?


> > Another (great) advantage of those wide-block modes is their inherent
> > 1/2*MAC functionality due to the intended collision avoidance in the
> > encryption layer that is built in by the universal hash pre- and
> > post-processing („1/2“ for: not a MAC but more than no MAC at all).

Here is a very important point concerning the TET or HEHfp mode of operation that I would like to emphasize again. Those operation modes offer the best security performance that one can get out of a length-preserving block device encryption mode. More precise: They each have three layers, a bijection, a parallelizable ECB encryption mode, and another bijection. The bijections have good cryptographic properties and depend on the secret key. They prevent collisions in the middle ECB layer. That is, controlled changes to the cipher text produce a possibly freaky plain text and hence are detectable. This is what I called „1/2*MAC“. If you want to have more security you would have to use a MAC on your plain/cipher text to make sure that you read what you have written before.


> > Since you maintain the code I would like to know your opinion on this and
> > if there is a chance to pursue such a project.
>
> That would be Milan. I am just the volunteer that does the documentation.
> Milan actually gets paid for real work on cryotsetup.

Thanks for clarifying those things to me.

What about the following approach?

Leave the dm-crypt crypto engine as it is – processing 512 bytes – and add e.g. TET or HEHfp to the Crypto-API and (as an option) to dm-crypt. This would add a pseudo-random operation on 512 Bytes of data to the system that is not present at the moment.

Stavros

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

> I would call this is a typical case for the: "Law Of Diminishing
> Returns"
> There is a gain, but the amount of work is disproportional.

You are probably right.

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Arno Wagner]

On Wed, Feb 06, 2013 at 01:52:40PM +0100, Milan Broz wrote:
> On 02/06/2013 11:32 AM, Arno Wagner wrote:
> 
> > On Wed, Feb 06, 2013 at 11:06:11AM +0100, Stavros Kousidis wrote:
> >> One essential issue that concerns full disk encryption on SSDs, that I
> >> have not seen in a mail discussion here so far (might be there and I
> >> simply missed it), is the distribution of an uncontrollable amount of
> >> copies of SSD-page contents (~4096 Bytes) where only a limited number of
> >> blocks (~16 Bytes) have changed.  This is initiated by local changes in
> >> userspace data and technically due to the complex nature of the flash
> >> translation layer (mainly wear leveling techniques), the narrow-block
> >> encryption modes (here: XTS) and sector-wise constant IVs.  In
> >> Cipher-block chaining mode the position where a bit-flip happened is
> >> visible in principle.
> > 
> > I am aware of that issue. However, XTS mode should lead to a full sector
> > (512 Bytes) chage even if only one bit is changed. That is the whole
> > point of modes like XTS, EME, etc.
> 
> I am afraid this is not true for XTS. blocks inside XTS can be processed
> in parallel (so they cannot depend on each other) so the effect can be

Hmm. You are right, my mistake. I sort-of assumed XTS was not
weaker than CBC for this particular attack without really
checking. One look at the definition makes it very obvious 
though.

> exactly opposite - first bit change in (the same) sector using e.g. CBC
> will change the whole ciphertext sector, while with XTS only first
> encryption block (16 bytes) is changed.
> I tried to show it here http://mbroz.fedorapeople.org/talks/DevConf2012/img6.jpg
> 
> But despite that, XTS is usually better. 

I agree. And attacks were attackers have repeated access to the
ciphertext, but not the plaintext are quite rare anyways. And
even then, usually nothing aignificant is gained. 

> But it would be nice to have
> some not patent encumbered wide mode (no code changes needed, just someone
> have to invent it and add to crypto API :-)

Indeed. 

Arno
-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Milan Broz]

On 02/06/2013 11:32 AM, Arno Wagner wrote:

> On Wed, Feb 06, 2013 at 11:06:11AM +0100, Stavros Kousidis wrote:
>> One essential issue that concerns full disk encryption on SSDs, that I
>> have not seen in a mail discussion here so far (might be there and I
>> simply missed it), is the distribution of an uncontrollable amount of
>> copies of SSD-page contents (~4096 Bytes) where only a limited number of
>> blocks (~16 Bytes) have changed.  This is initiated by local changes in
>> userspace data and technically due to the complex nature of the flash
>> translation layer (mainly wear leveling techniques), the narrow-block
>> encryption modes (here: XTS) and sector-wise constant IVs.  In
>> Cipher-block chaining mode the position where a bit-flip happened is
>> visible in principle.
> 
> I am aware of that issue. However, XTS mode should lead to a full sector
> (512 Bytes) chage even if only one bit is changed. That is the whole
> point of modes like XTS, EME, etc.

I am afraid this is not true for XTS. blocks inside XTS can be processed
in parallel (so they cannot depend on each other) so the effect can be
exactly opposite - first bit change in (the same) sector using e.g. CBC
will change the whole ciphertext sector, while with XTS only first
encryption block (16 bytes) is changed.
I tried to show it here http://mbroz.fedorapeople.org/talks/DevConf2012/img6.jpg

But despite that, XTS is usually better. But it would be nice to have
some not patent encumbered wide mode (no code changes needed, just someone
have to invent it and add to crypto API :-)

Milan

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Arno Wagner]

On Wed, Feb 06, 2013 at 12:07:13PM +0100, Matthias Schniedermeyer wrote:
> On 06.02.2013 11:06, Stavros Kousidis wrote:
> > 
> > One essential issue that concerns full disk encryption on SSDs, that I 
> > have not seen in a mail discussion here so far (might be there and I 
> > simply missed it), is the distribution of an uncontrollable amount of 
> > copies of SSD-page contents (~4096 Bytes) where only a limited number 
> > of blocks (~16 Bytes) have changed. This is initiated by local changes 
> > in userspace data and technically due to the complex nature of the 
> > flash translation layer (mainly wear leveling techniques), the 
> > narrow-block encryption modes (here: XTS) and sector-wise constant 
> > IVs. In Cipher-block chaining mode the position where a bit-flip 
> > happened is visible in principle.
> 
> Let me paraphrase, you are worried about someone physically ripping the 
> SSD out of your computer, desoldering the chips and reverse engeneering 
> the wear-leveling. In the off-change that there actually are several 
> generations of a somehow vulnerable block (or several) and the changes 
> would tell the attacker "something".
> 
> With the slight variatians:
> a) Somone with root-priviles making full-copies of the device at 
> different points in time
> b) Somone with root-priviledes and the SSD containing some vendor 
> specific commands to read the RAW contents of the flash and/or 
> possibility to get older versions of blocks (at different points in 
> time)
> c) Taking the SSD out and making full copies at different points in 
> time.
> d) c in variant b
> e) Things that don't come to my mind

Nice list! ;-)

Here is one more: 
f) Chain-reallocation of a sector in a HDD because of some externel 
   issue like vibration. With the difference that the old copies 
   live forever.
 
> In short:
> I would worry about these things, before i worry about POTENTIAL 
> information leakage of several generations of a specific block.
> In all cases you already need a vulnerability to even get to the 
> information.
> 
> I don't say the theoretical vulnerability doesn't exist, but there are 
> things much more serious before worrying about such theoretical things.

Actually, I think it is a bit different: These vulnerabilities
are practical, but do not apply in almost all situations. That
means the right way to deal with them is to document them but
tell the very few people that would have a problem to just 
not use this system. It certainly does not justify massive
changes to a system that works well.

> Among the first i would worry about: The so called "cold-boot attack".
> At least for cases were you worry about someone with physical access.
> 
> I would call this is a typical case for the: "Law Of Diminishing 
> Returns"
>
> There is a gain, but the amount of work is disproportional.

Indeed. 

Arno
-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Milan Broz]

Hi,

On 02/06/2013 11:06 AM, Stavros Kousidis wrote:
> One essential issue that concerns full disk encryption on SSDs, that
> I have not seen in a mail discussion here so far (might be there and
> I simply missed it), is the distribution of an uncontrollable amount
> of copies of SSD-page contents (~4096 Bytes) where only a limited
> number of blocks (~16 Bytes) have changed. This is initiated by local
> changes in userspace data and technically due to the complex nature
> of the flash translation layer (mainly wear leveling techniques), the
> narrow-block encryption modes (here: XTS) and sector-wise constant
> IVs. In Cipher-block chaining mode the position where a bit-flip
> happened is visible in principle.

The main problem (I see) with these analysis is that it usually
take just part of the system (either SSD architecture or block encryption).

But it is more complex system with several layer interfering, this
interference can make the problem with ciphertext block copies worse
but also decrease impact.

An example (illustrative but I hope not completely wrong:)

Imagine you have write pattern changing several consecutive 512 bytes
sectors with some delay between writes.

In theory, that's exactly case you are describing,
you will get several copies inside SSD (on flash chips)
because of wear leveling and similar techniques (do not forget
internal garbage collection as well).

In reality, it depends

- Filesystem above uses large blocks as well (most common is page size 4k I think).
  The filesystem (and page cache) will send IO request only of this block (page)
  size, not 512 bytes sector. Depending on timing, you will see either
  several IOs or only just one (write-cache effect).

- The transparent dmcrypt is using 512 bytes for encryption but it always
  encrypts the whole submitted IO before resending. (Let's ignore
  corner case with IO split because of lack or memory or storage restriction for now.)
  (Note dmcrypt has no own IO scheduler but it has internal queues for
   requests - so there is some delay in processing.)

- The encrypted IO request is submitted to underlying device, where
  IO scheduler is responsible for real submission to device.
  And here it can be (and will be with exception of noop scheduler)
  merged into one big IO.

- internal SSD architecture, and storage in general, have write-cache
  internally and will optimize writes as well.

- storage (specifically SSD) uses hints for IO size, and every user
  in kernel should (or must) produce IOs restricted by these hints

So, in this example you changed e.g. whole 4k page in several writes,
but you cold see just one final IO! All it depends how the stack is
configured and how filesystem is using Flush/FUA requests to sync
IO in-flight.

There is always some corner cases but I am trying to say that I am not
sure if this problem is really so important in usual use cases.

(As someone already mentioned, there are other attack vectors where the risk
is probably higher.)

But that said, yes I'm very well aware of this problem and I would
like to have at least some analysis what's really going on in todays
flash storage devices and how it is related to disk encryption security.
So let's try to gather some data first.

> A countermeasure to those history-building SSD-mechanisms is to blur
> what is written to the flash device by forcing a multi-sector-wide
> change when a bit changes (preferrably: multi-sector = size of file
> system blocks). There are two concrete realizations of that strategy
> that I know of:
> 
> 1) Use random IVs. Leaves you with data expansion, since you have to
> store the IVs, and a pain in the *** effort to implement this
> reliably.

Anything what need more space is problem (that includes data integrity,
auth tags, whatever). And IMHO (pseudo-)random IV will cause more
problems than it solves.

> 2) Add a (claimed patent free) wide-block mode like TET or HEHfp (see
> articles below) from the Hash-Encrypt-Hash family to the Crypto-API
> and change the dmcrypt crypto engine to handle variable block sizes
> instead of always operating on 512 Bytes of data (compare the
> discussion:
> http://www.saout.de/pipermail/dm-crypt/2011-April/001667.html)

Yes, the work on deploying new cipher or encryption mode (either narrow or wide)
for Linux block encryption starts in Linux kernel API.

Send a patch to crypto kernel API list, get it in official kernel
and dmcrypt/cryptsetup can start to use it.
(But if there is any patent problem, no chance...)

But do not forget one thing - while cryptsetup is always open to support
wide range of algorithms, a huge user base is bound by standards which do not
allow them to use anything else. That's why XTS is so widely used.

BTW anyone know what had happened with EME2 wide mode?
http://siswg.net/index.php?option=com_content&task=view&id=36&Itemid=1
 
Milan

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Matthias Schniedermeyer]

On 06.02.2013 11:06, Stavros Kousidis wrote:
> 
> One essential issue that concerns full disk encryption on SSDs, that I 
> have not seen in a mail discussion here so far (might be there and I 
> simply missed it), is the distribution of an uncontrollable amount of 
> copies of SSD-page contents (~4096 Bytes) where only a limited number 
> of blocks (~16 Bytes) have changed. This is initiated by local changes 
> in userspace data and technically due to the complex nature of the 
> flash translation layer (mainly wear leveling techniques), the 
> narrow-block encryption modes (here: XTS) and sector-wise constant 
> IVs. In Cipher-block chaining mode the position where a bit-flip 
> happened is visible in principle.

Let me paraphrase, you are worried about someone physically ripping the 
SSD out of your computer, desoldering the chips and reverse engeneering 
the wear-leveling. In the off-change that there actually are several 
generations of a somehow vulnerable block (or several) and the changes 
would tell the attacker "something".

With the slight variatians:
a) Somone with root-priviles making full-copies of the device at 
different points in time
b) Somone with root-priviledes and the SSD containing some vendor 
specific commands to read the RAW contents of the flash and/or 
possibility to get older versions of blocks (at different points in 
time)
c) Taking the SSD out and making full copies at different points in 
time.
d) c in variant b
e) Things that don't come to my mind



In short:
I would worry about these things, before i worry about POTENTIAL 
information leakage of several generations of a specific block.
In all cases you already need a vulnerability to even get to the 
information.

I don't say the theoretical vulnerability doesn't exist, but there are 
things much more serious before worrying about such theoretical things.
Among the first i would worry about: The so called "cold-boot attack".
At least for cases were you worry about someone with physical access.

I would call this is a typical case for the: "Law Of Diminishing 
Returns"
There is a gain, but the amount of work is disproportional.



-- 

Matthias

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Arno Wagner]

On Wed, Feb 06, 2013 at 11:06:11AM +0100, Stavros Kousidis wrote:
> > An HTML attachment was scrubbed...
> > URL: <http://www.saout.de/pipermail/dm-crypt/attachments/20130206/89e2ec35/attachment.html
> > [http://www.saout.de/pipermail/dm-crypt/attachments/20130206/89e2ec35/attachment.html]>
> 
> Oops, forgot about the HTML web interface. Here's the plain text:
> -------------------------------------------------------------------------------

Ah, thanks. I was just about to complain. 
 
> Dear Arno, dear Milan,
> 
> I have seen that you are well aware of the SSD-technology drawbacks from a cryptographic viewpoint, e.g.
> 
> http://www.saout.de/pipermail/dm-crypt/2012-August/002665.html
> http://asalor.blogspot.de/2011/08/trim-dm-crypt-problems.html
> 
> One essential issue that concerns full disk encryption on SSDs, that I
> have not seen in a mail discussion here so far (might be there and I
> simply missed it), is the distribution of an uncontrollable amount of
> copies of SSD-page contents (~4096 Bytes) where only a limited number of
> blocks (~16 Bytes) have changed.  This is initiated by local changes in
> userspace data and technically due to the complex nature of the flash
> translation layer (mainly wear leveling techniques), the narrow-block
> encryption modes (here: XTS) and sector-wise constant IVs.  In
> Cipher-block chaining mode the position where a bit-flip happened is
> visible in principle.

I am aware of that issue. However, XTS mode should lead to a full sector
(512 Bytes) chage even if only one bit is changed. That is the whole
point of modes like XTS, EME, etc.

> A countermeasure to those history-building SSD-mechanisms is to blur what
> is written to the flash device by forcing a multi-sector-wide change when
> a bit changes (preferrably: multi-sector = size of file system blocks). 
> There are two concrete realizations of that strategy that I know of:

I think you just have to live with it at this time. It is not a severe
vulnerability in most situations. And it will not build up to badly, at
some time the blocks get re-used. The amounth of spares/write pool
in SSDs seems to be shrinking as well.

> 1) Use random IVs. Leaves you with data expansion, since you have to store
> the IVs, and a pain in the *** effort to implement this reliably.

It is. It also breaks the dm-model as additional accesses
are required. Not an option, I think.

> 2) Add a (claimed patent free) wide-block mode like TET or HEHfp (see
> articles below) from the Hash-Encrypt-Hash family to the Crypto-API and
> change the dmcrypt crypto engine to handle variable block sizes instead of
> always operating on 512 Bytes of data (compare the discussion:
> http://www.saout.de/pipermail/dm-crypt/2011-April/001667.html)

I will have a look at the articles, but I think this is not
really an option either, agen because of mismatch with the
dm-layer. 
 
> Another (great) advantage of those wide-block modes is their inherent
> 1/2*MAC functionality due to the intended collision avoidance in the
> encryption layer that is built in by the universal hash pre- and
> post-processing („1/2“ for: not a MAC but more than no MAC at all).

> Since you maintain the code I would like to know your opinion on this and
> if there is a chance to pursue such a project.

That would be Milan. I am just the volunteer that does the documentation.
Milan actually gets paid for real work on cryotsetup.

Arno

> 
> Best
> Stavros
> 
> P.S.: You can search the web for the above mentioned articles:
> 
> TET: Shai Halevi, „Invertible universal hashing and the TET encryption mode“
> HEHfp: Palash Sarkar, „Improving upon the TET mode of operation“
> 
> Those are instances of the hash-encrypt-hash family introduced by Naor and Reingold in „A pseudo-random encryption mode“. Halevi discusses the intellectual-property issues et the end of his article.
> _______________________________________________
> dm-crypt mailing list
> dm-crypt@saout.de
> http://www.saout.de/mailman/listinfo/dm-crypt

-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Re: [dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

> An HTML attachment was scrubbed...
> URL: <http://www.saout.de/pipermail/dm-crypt/attachments/20130206/89e2ec35/attachment.html
> [http://www.saout.de/pipermail/dm-crypt/attachments/20130206/89e2ec35/attachment.html]>

Oops, forgot about the HTML web interface. Here's the plain text:
-------------------------------------------------------------------------------

Dear Arno, dear Milan,

I have seen that you are well aware of the SSD-technology drawbacks from a cryptographic viewpoint, e.g.

http://www.saout.de/pipermail/dm-crypt/2012-August/002665.html
http://asalor.blogspot.de/2011/08/trim-dm-crypt-problems.html

One essential issue that concerns full disk encryption on SSDs, that I have not seen in a mail discussion here so far (might be there and I simply missed it), is the distribution of an uncontrollable amount of copies of SSD-page contents (~4096 Bytes) where only a limited number of blocks (~16 Bytes) have changed. This is initiated by local changes in userspace data and technically due to the complex nature of the flash translation layer (mainly wear leveling techniques), the narrow-block encryption modes (here: XTS) and sector-wise constant IVs. In Cipher-block chaining mode the position where a bit-flip happened is visible in principle.

A countermeasure to those history-building SSD-mechanisms is to blur what is written to the flash device by forcing a multi-sector-wide change when a bit changes (preferrably: multi-sector = size of file system blocks). There are two concrete realizations of that strategy that I know of:

1) Use random IVs. Leaves you with data expansion, since you have to store the IVs, and a pain in the *** effort to implement this reliably.

2) Add a (claimed patent free) wide-block mode like TET or HEHfp (see articles below) from the Hash-Encrypt-Hash family to the Crypto-API and change the dmcrypt crypto engine to handle variable block sizes instead of always operating on 512 Bytes of data (compare the discussion: http://www.saout.de/pipermail/dm-crypt/2011-April/001667.html)

Another (great) advantage of those wide-block modes is their inherent 1/2*MAC functionality due to the intended collision avoidance in the encryption layer that is built in by the universal hash pre- and post-processing („1/2“ for: not a MAC but more than no MAC at all).

Since you maintain the code I would like to know your opinion on this and if there is a chance to pursue such a project.

Best
Stavros

P.S.: You can search the web for the above mentioned articles:

TET: Shai Halevi, „Invertible universal hashing and the TET encryption mode“
HEHfp: Palash Sarkar, „Improving upon the TET mode of operation“

Those are instances of the hash-encrypt-hash family introduced by Naor and Reingold in „A pseudo-random encryption mode“. Halevi discusses the intellectual-property issues et the end of his article.

[dm-crypt] Cryptographic issues with SSD-technology and wide-block encryption modes

[Stavros Kousidis]

[-- Attachment #1: Type: text/html, Size: 3068 bytes --]