[dm-crypt] simple ideas addressing ssd TRIM security concern

[dm-crypt] simple ideas addressing ssd TRIM security concern

[alban bernard]

Hi,

I carefully read that page http://asalor.blogspot.fr/2011/08/trim-dm-crypt-problems.html to understand the basics behind the main security problem involved by trim commands. Simple ideas came to my mind, but I need to submit them to know how they fail (or by any chance how they may succeed).

From what I understand, TRIM commands are used to say to the SSD controller: "these sectors are discarded, so you can erase them at any time chosen by you rather than waiting an explicit rewrite from me". So, from a crytographic point of view, using TRIM commands is like replacing deleted files by "zero" files in a totally uncontrolled manner. This breaks the main purpose of cryptography: hiding as much things as possible.

After TRIM commands, the SSD controller erases blocks whenever he wants after receiving the command. Thus, it seems to not inform us back where those blocks are remapped in its LBA translation table (not sure about that).

So, what about running TRIM commands only in certain cases: on-demand / by sectors / ... ? The overall purpose being:
- to limit the TRIMed space on device
- to control the TRIMed pattern (spread it randomly as much as possible)

Here the naive things:
- send on-demand TRIM commands based on device write access rate and remaining free space
- keep a table of TRIMed blocks or just their total size (send TRIM commands only below a certain size limit threshold)
- send TRIM commands on randomly chosen deleted blocks only (not all deleted blocks)
- write garbage to fill some TRIMed "blanks" (less than a threshold critical to ssd performance)
- randomize device usage pattern when choosing blocks to TRIM (hide filesystem)

Let me know if it could lead to real life solution. Any criticism appreciated.

~Alban.

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[Arno Wagner]

Hi Alban,

On Sat, Apr 14, 2012 at 02:23:23AM +0100, alban bernard wrote:
> Hi,
> 
> I carefully read that page
> http://asalor.blogspot.fr/2011/08/trim-dm-crypt-problems.html to
> understand the basics behind the main security problem involved by trim
> commands.  Simple ideas came to my mind, but I need to submit them to know
> how they fail (or by any chance how they may succeed).
> 
> From what I understand, TRIM commands are used to say to the SSD
> controller: "these sectors are discarded, so you can erase them at any
> time chosen by you rather than waiting an explicit rewrite from me".  So,
> from a crytographic point of view, using TRIM commands is like replacing
> deleted files by "zero" files in a totally uncontrolled manner.  This
> breaks the main purpose of cryptography: hiding as much things as
> possible.

Well, it does not quite "break" it. The correct terminology is that
you have an information leak where filesystem-discarded blocks
(by TRIM) can be identified by an attacker with low effort
Well, low "cryptoanalytic effort", actually. 

For a "break", you would actually have to have real information
end up on the raw block device, but in most situations, the
information content of the TRIM information will be small.

There are scenarios though: Assume you have never TRIMed
and a large file gets deleted. Then an attacker can determine
the size of that file, but rounded up to the block size.
For a file in the 1GB range that would man (asuming 512B 
sectors, even though filesystem block are typically larger),
that the total file sizte is 30 bit, of which the first
21 are leaking. While that is information, it is pretty fuzzy 
and requires pretty special conditions to be visible in the
first place.

A second scenario would arise if some malicious software that
can write only the encrypted device wishes to signal to the
outside. Then a "0" could be a low number of TRIMed blocks
and a "1" copuld be a high number. Both can be achieved by
wrinting alot of data or deleting a lot of data. Repeated
action and observer access to only the encrypted data to
transfer more bits. While this may be a concern, it is a 
pretty bizzare scenario. And the same can be achieved by 
changing sector contents, as the observer-part of the attacker
_can_ detect changes in the on-disk data. 

The Design "error" is of course that the raw device is told about
some things that should only be visible after decryption.

> After TRIM commands, the SSD controller erases blocks whenever he wants
> after receiving the command.  Thus, it seems to not inform us back where
> those blocks are remapped in its LBA translation table (not sure about
> that).

It does not, but forensic analysis may be able to extract some sort
of log or trace from the device.

> 
> So, what about running TRIM commands only in certain cases: on-demand / by
> sectors / ...  ?  The overall purpose being:
> - to limit the TRIMed space on device
> - to control the TRIMed pattern (spread it randomly as much as possible)

The information leakage is very small. If it is a concern,
then TRIM must never be used. If not, TRIM can be used in unlimited
fashion. It is a standard security trade-off. Your options can
in some circumstances decrease the information lekage, but they
will not so so reliably (comments below), and hence do not reduce
the worst-case. But the risk-analysis that form the basis of the 
decision to allow TRIM or not has to use the worst-case as there
is no basis for forming an average-case and an attacker may be able
to provoke the worst-case scenario.

> Here the naive things:
> - send on-demand TRIM commands based on device write access rate and
>   remaining free space 

Can leak information just as well, will be fuzzier in only some cases.

> - keep a table of TRIMed blocks or just their total size (send TRIM
>   commands only below a certain size limit threshold)

See above.

> - send TRIM commands on randomly chosen deleted blocks only (not all
>   deleted blocks)

Selecting them randomly would here mean "selecting them in a
cryptographically secure random way". This violates KISS as it
would be pretty complex and suddently you have information to
protect by hard crypto in the filesystem layer that is not
designed for this. If the goal of an attacker is to recognize 
some specific action the attacker designed before (e.g. malware
accessing the device in a pattern), this may still be visible.

> - write garbage to fill some TRIMed "blanks" (less than a threshold
>   critical to ssd performance)

"garbage" would again need to be "cryptographic garbage". I am not even
sure this is possible. And you still can deduce that blocks are 
actually deleted, as they show up as deleted in the SSD's internal
tables, so the effect is only higher attacker effort, but the
leackage stays exactly the same.

> - randomize device usage pattern when choosing blocks to TRIM (hide
>   filesystem) 

I don't quite understand how that could work, do you mean to have
a random mapping between encrypted and hysical secors? That would
kill performance a lot worse than not using TRIM in the first place.

> Let me know if it could lead to real life solution. Any criticism
> appreciated.

Well, I think you do understand the problem, but not quite its
implications. It really is a case of "secure, fast, cheap,
pick any two". If security is your primary concern, then do
not use TRIM. The SSD can still to garbage collection (well, 
garbage compaction really) but only with the spare capacity it
reserves for that. Leads to a bit of performance decrease, 
depending on the SSD. 

My advice would be to decide how important the postential data
leakage is (depending on the application) and then do with or 
without TRIM entirely. The default should be no TRIM though
as it is really a decision by the user to make the system less
secure for a performance gain.
 
Arno
-- 
Arno Wagner, Dr. sc. techn., Dipl. Inform., CISSP -- Email: arno@wagner.name 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
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] simple ideas addressing ssd TRIM security concern

[alban bernard]

--- On Sat, 4/14/12, Arno Wagner <arno@wagner.name> wrote:
> The Design "error" is of course that the raw device is told
> about
> some things that should only be visible after decryption.
>

In a way, TRIMing leads to the same situation as not writing garbage before device encryption.

> The information leakage is very small. If it is a concern,
> then TRIM must never be used. If not, TRIM can be used in
> unlimited
> fashion. It is a standard security trade-off. Your options
> can
> in some circumstances decrease the information lekage, but
> they
> will not so so reliably (comments below), and hence do not
> reduce
> the worst-case. But the risk-analysis that form the basis of
> the
> decision to allow TRIM or not has to use the worst-case as
> there
> is no basis for forming an average-case and an attacker may
> be able
> to provoke the worst-case scenario.

In case the user chooses the performance trade-off, an option to maximize security is still interesting to him. I agree with you, a layer that cryptographically randomize TRIMed blocks while limiting information leakage is not a key point to decide to allow TRIM or not (the worst case is still possible), but it is still important to have the option from the user perspective.

> > - randomize device usage pattern when choosing blocks
> to TRIM (hide
> >   filesystem)
>
> I don't quite understand how that could work, do you mean to
> have
> a random mapping between encrypted and hysical secors? That
> would
> kill performance a lot worse than not using TRIM in the
> first place.
>

I meant to randomly distribute TRIMed blocks across the device by choosing to not TRIM contiguous blocks of some files. E.g. when a big file is deleted, allow TRIM only on a randomly chosen set of its blocks limited to about 1 percent of its size. The 99 percent of it would stay unTRIMed on the device.

So, these ideas could only limit the information leakage that could be used by an attacker. To complete my understanding, if the device is completely used (no more free space), an attacker could not benefit of any leakage from TRIMed space. So, there is a relation between information leakage rate and amount of TRIMed space. A question rises to me: does an amount of TRIMed space exist to keep performance and still harden crypto-analysis in a controllable manner?

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[Arno Wagner]

On Sat, Apr 14, 2012 at 11:22:15PM +0100, alban bernard wrote:
> --- On Sat, 4/14/12, Arno Wagner <arno@wagner.name> wrote:
> > The Design "error" is of course that the raw device is told
> > about
> > some things that should only be visible after decryption.
> >
> 
> In a way, TRIMing leads to the same situation as not writing garbage
> before device encryption.
> 
> > The information leakage is very small. If it is a concern,
> > then TRIM must never be used. If not, TRIM can be used in
> > unlimited
> > fashion. It is a standard security trade-off. Your options
> > can
> > in some circumstances decrease the information lekage, but
> > they
> > will not so so reliably (comments below), and hence do not
> > reduce
> > the worst-case. But the risk-analysis that form the basis of
> > the
> > decision to allow TRIM or not has to use the worst-case as
> > there
> > is no basis for forming an average-case and an attacker may
> > be able
> > to provoke the worst-case scenario.
> 
> In case the user chooses the performance trade-off, an option to maximize
> security is still interesting to him.  I agree with you, a layer that
> cryptographically randomize TRIMed blocks while limiting information
> leakage is not a key point to decide to allow TRIM or not (the worst case
> is still possible), but it is still important to have the option from the
> user perspective.

I do not agree. Most users will not understand what they are doing
and an option that increses performance while seemingly still having
high-security (as there is this "additional measure") will just 
mislead them. And there is no way to "maximize security" when TRIM
is active. The way to maximize security is to not use TRIM.
 
> > > - randomize device usage pattern when choosing blocks
> > to TRIM (hide
> > >   filesystem)
> >
> > I don't quite understand how that could work, do you mean to
> > have
> > a random mapping between encrypted and hysical secors? That
> > would
> > kill performance a lot worse than not using TRIM in the
> > first place.
> >

> I meant to randomly distribute TRIMed blocks across the device by choosing
> to not TRIM contiguous blocks of some files.  E.g.  when a big file is
> deleted, allow TRIM only on a randomly chosen set of its blocks limited to
> about 1 percent of its size.  The 99 percent of it would stay unTRIMed on
> the device.

That would have very little benefit, while still having the same
worst-case information leakage. 

>
> So, these ideas could only limit the information leakage that could be
> used by an attacker.  

No. They would not limit anything. They would decrease the probability of
accidental leaks of a higher amount of data, but the worst-case stays
the same.

> To complete my understanding, if the device is
> completely used (no more free space), an attacker could not benefit of any
> leakage from TRIMed space.  So, there is a relation between information
> leakage rate and amount of TRIMed space.  A question rises to me: does an
> amount of TRIMed space exist to keep performance and still harden
> crypto-analysis in a controllable manner?

No. You can only decrease probabilities, but not amount leaked in the
worst case. Crypto is very hard. Using worst-case scenarios is 
necessary to be sure of an analysis.

To put it in another way, if performance is important enough to 
you to compromise security, then there is a high probability that
you will break security. It happens all the time by developers that
do not know what they are doing.

Arno
-- 
Arno Wagner, Dr. sc. techn., Dipl. Inform., CISSP -- Email: arno@wagner.name 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
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] simple ideas addressing ssd TRIM security concern

[Sven Eschenberg]

That would render TRIMing completely useless anyway and you could as well
turn it off.

On Sun, April 15, 2012 00:22, alban bernard wrote:
>
> I meant to randomly distribute TRIMed blocks across the device by choosing
> to not TRIM contiguous blocks of some files. E.g. when a big file is
> deleted, allow TRIM only on a randomly chosen set of its blocks limited to
> about 1 percent of its size. The 99 percent of it would stay unTRIMed on
> the device.
>

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[alban bernard]

--- On Sun, 4/15/12, Sven Eschenberg <sven@whgl.uni-frankfurt.de> wrote:
> That would render TRIMing completely
> useless anyway and you could as well
> turn it off.

Not really if there are enough TRIMed blocks before block writes occur. There lies the purpose of a "smart" layer that will be responsible of TRIMing blocks in a certain amount of the total space: a kind of TRIMed block buffer that smooths writing zeroes and spreads them among the device the "crypto" way.

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[Sven Eschenberg]

The purpose of TRIMing is to get erase pages as soon as possible back into
the allocation pool. These pages can then be erased (as needed) to
increase  'write' performance and have enough allocateable free pages for
upcoming writes (which are actually read, modify, erase, write, ops, while
TRIMing helps in prefetching the very expensive erase op).

An erase block is a continuous block of sectors. As long as not all FS
blocks covering this erase block were trimmed, the advantage of trimming
is anihilated (for obvious reasons). As an example, assume a 64k erase
page size and 4k FS-blocks. Now erase a big file (i.e. 1GB), while only
trimming 1% of the covered space randomly. The probability that you'd TRIM
multiple sets of 16 continuous FS blocks (if we assume proper alignment)
when only trimming 1% of the 1GB file is next to zero. If the FS blocksize
is smaller and the erase page size bigger, it's even worse.

Sidenote: An erase page size of 512KB is not really uncommon for MLC NAND.

As Arno already said, all you can do is weigh out leakage versus performance.


On Sun, April 15, 2012 18:55, alban bernard wrote:
> --- On Sun, 4/15/12, Sven Eschenberg <sven@whgl.uni-frankfurt.de> wrote:
>> That would render TRIMing completely
>> useless anyway and you could as well
>> turn it off.
>
> Not really if there are enough TRIMed blocks before block writes occur.
> There lies the purpose of a "smart" layer that will be responsible of
> TRIMing blocks in a certain amount of the total space: a kind of TRIMed
> block buffer that smooths writing zeroes and spreads them among the device
> the "crypto" way.
>
> _______________________________________________
> dm-crypt mailing list
> dm-crypt@saout.de
> http://www.saout.de/mailman/listinfo/dm-crypt
>

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[alban bernard]

--- On Mon, 4/16/12, Sven Eschenberg <sven@whgl.uni-frankfurt.de> wrote:
> An erase block is a continuous block of sectors. As long as
> not all FS
> blocks covering this erase block were trimmed, the advantage
> of trimming
> is anihilated (for obvious reasons). As an example, assume a
> 64k erase
> page size and 4k FS-blocks. Now erase a big file (i.e. 1GB),
> while only
> trimming 1% of the covered space randomly. The probability
> that you'd TRIM
> multiple sets of 16 continuous FS blocks (if we assume
> proper alignment)
> when only trimming 1% of the 1GB file is next to zero. If
> the FS blocksize
> is smaller and the erase page size bigger, it's even worse.

To me, due to the "virtual" LBA table allocation handled internally by the ssd controller and in the case TRIM is allowed and fully used accross the entire device, the big file of 1GB is already erase-block fragmented. That is the purpose of the garbage collector: aggregating valid pages to isolate discarded pages inside future "erasable" blocks.

In my case, the probability is maybe next to zero (not sure about that), right after sending the TRIM commands on the 1% percent of the big file. But after a certain amount of time, the garbage collector will un-puzzle all the mess and help the controller to erase trimmed blocks (those 1% aggregated with another erasable pages).

> As Arno already said, all you can do is weigh out leakage
> versus performance.

Weighing out really is the most difficult part when you have no tangible data: how much is it difficult to break a TRIMed and crypted device?

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[Arno Wagner]

On Mon, Apr 16, 2012 at 01:28:25AM +0100, alban bernard wrote:
> --- On Mon, 4/16/12, Sven Eschenberg <sven@whgl.uni-frankfurt.de> wrote:
> > An erase block is a continuous block of sectors. As long as
> > not all FS
> > blocks covering this erase block were trimmed, the advantage
> > of trimming
> > is anihilated (for obvious reasons). As an example, assume a
> > 64k erase
> > page size and 4k FS-blocks. Now erase a big file (i.e. 1GB),
> > while only
> > trimming 1% of the covered space randomly. The probability
> > that you'd TRIM
> > multiple sets of 16 continuous FS blocks (if we assume
> > proper alignment)
> > when only trimming 1% of the 1GB file is next to zero. If
> > the FS blocksize
> > is smaller and the erase page size bigger, it's even worse.
> 
> To me, due to the "virtual" LBA table allocation handled internally by the
> ssd controller and in the case TRIM is allowed and fully used accross the
> entire device, the big file of 1GB is already erase-block fragmented. 
> That is the purpose of the garbage collector: aggregating valid pages to
> isolate discarded pages inside future "erasable" blocks.
> 
> In my case, the probability is maybe next to zero (not sure about that),
> right after sending the TRIM commands on the 1% percent of the big file. 

You fogte that any malicious use of that feature could be aware
of the details and compensate. Then the probability becomes 100%.

> But after a certain amount of time, the garbage collector will un-puzzle
> all the mess and help the controller to erase trimmed blocks (those 1%
> aggregated with another erasable pages).
> 
> > As Arno already said, all you can do is weigh out leakage
> > versus performance.
> 
> Weighing out really is the most difficult part when you have no tangible
> data: how much is it difficult to break a TRIMed and crypted device?

It is not difficult. It is impossible. Therefore a sane secure
design tries not to do it but forbids TRIM in the first place.

If security requirements are lower, the design can allow the user
to enable it, but even having the possibility in there is a risk.

You are of course free to compromise the security of your own system
as far as you like. But default mechanisms must be held to a higher
standard. 

Arno
-- 
Arno Wagner, Dr. sc. techn., Dipl. Inform., CISSP -- Email: arno@wagner.name 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
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] simple ideas addressing ssd TRIM security concern

[Heinz Diehl]

On 16.04.2012, Arno Wagner wrote: 

> > Weighing out really is the most difficult part when you have no tangible
> > data: how much is it difficult to break a TRIMed and crypted device?
 
> It is not difficult. It is impossible.

If this is true, then why not use it and end of story?

Re: [dm-crypt] simple ideas addressing ssd TRIM security concern

[Arno Wagner]

On Mon, Apr 16, 2012 at 09:53:32PM +0200, Heinz Diehl wrote:
> On 16.04.2012, Arno Wagner wrote: 
> 
> > > Weighing out really is the most difficult part when you have no tangible
> > > data: how much is it difficult to break a TRIMed and crypted device?
>  
> > It is not difficult. It is impossible.
> 
> If this is true, then why not use it and end of story?

The assessment of the difficulty is impossible....

Arno
-- 
Arno Wagner, Dr. sc. techn., Dipl. Inform., CISSP -- Email: arno@wagner.name 
GnuPG:  ID: 1E25338F  FP: 0C30 5782 9D93 F785 E79C  0296 797F 6B50 1E25 338F
----
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