librelist archives

« back to archive

Nonce replay attack

Nonce replay attack

From:
Jeremy Maitin-Shepard
Date:
2014-05-13 @ 18:03
I believe there is an issue with how the nonce/counter is used with an
untrusted repository:

Each client initializes its nonce/counter to the value that just follows
the last counter used for the most recent manifest it finds in the
repository.

However, if there is filesystem data loss/roll back or an adversary
controls the repository, the client may be using the same manifest that was
previously used to initialize the counter (and based on which, encrypted
data was already written to the repository).

A single client could keep track of the last nonce it used, and ensure that
the new nonce is at least as high as that value, but there could be
multiple clients accessing the adversary-controlled repository
simultaneously.

The safe solution is for the client to randomly generate a new nonce for
each session.  That probably means that more than 8-bytes of it have to be
stored in each repository entry, though.

As a related issue, if random padding of encrypted payloads is used to hide
the chunk size, the amount of padding should be a deterministic function of
the content, e.g. based on HMAC(content-id).  That avoids the possibility
that due to repository tampering the same chunk would be written with a
different amount of padding, which would reveal some information aobut the
amount of padding.

Re: [attic] Nonce replay attack

From:
Jonas Borgström
Date:
2014-05-13 @ 20:25
On 2014-05-13 20:03, Jeremy Maitin-Shepard wrote:
> I believe there is an issue with how the nonce/counter is used with an
> untrusted repository:
> 
> Each client initializes its nonce/counter to the value that just follows
> the last counter used for the most recent manifest it finds in the
> repository.

That is not true.

> However, if there is filesystem data loss/roll back or an adversary
> controls the repository, the client may be using the same manifest that
> was previously used to initialize the counter (and based on which,
> encrypted data was already written to the repository).

The client will refuse to access a repository if the manifest timestamp
is older than the timestamp recorded in the clint's cache directory. But
of course this protection only works as long as the cache directory is
available.

This could be improved further by always increment the counter with a
large enough amount whenever the stored timestamp is not available
(unknown repository) or older (repository modified by other client).

> A single client could keep track of the last nonce it used, and ensure
> that the new nonce is at least as high as that value, but there could be
> multiple clients accessing the adversary-controlled repository
> simultaneously.

A multiple clients per repository setup is rarely used since a costly
full cache rebuild is required whenever the cache directory is detected.
But that might change if we figure out a way to do the rebuild more
efficiently in the future.

> The safe solution is for the client to randomly generate a new nonce for
> each session.  That probably means that more than 8-bytes of it have to
> be stored in each repository entry, though.

Even though I still think the current method is secure, using a random
IV has other benefits as well. It would for example be easier use more
than one core for compression and encryption. But as you said, that
would require changing the encryption envelope format...

> As a related issue, if random padding of encrypted payloads is used to
> hide the chunk size, the amount of padding should be a deterministic
> function of the content, e.g. based on HMAC(content-id).  That avoids
> the possibility that due to repository tampering the same chunk would be
> written with a different amount of padding, which would reveal some
> information aobut the amount of padding.

Speaking about format change :)

That's a good point. Do you have any idea on how to do this efficiently
and securely?

/ Jonas




Re: [attic] Nonce replay attack

From:
Jeremy Maitin-Shepard
Date:
2014-05-13 @ 21:33
By the way, although I've mentioned a number of issues I've spotted in
Attic, the reason I'm on this list is that Attic seems to be the
best-designed and most elegant free-software backup program available.  I
really appreciate all the work you've put into it.

On Tue, May 13, 2014 at 1:25 PM, Jonas Borgström <jonas@borgstrom.se> wrote:

> On 2014-05-13 20:03, Jeremy Maitin-Shepard wrote:
> > I believe there is an issue with how the nonce/counter is used with an
> > untrusted repository:
> >
> > Each client initializes its nonce/counter to the value that just follows
> > the last counter used for the most recent manifest it finds in the
> > repository.
>
> That is not true.
>

That is what I gathered from looking at PassphraseKey.detect
KeyfileKey.detect.  How am I incorrect (other than the timestamp check)?



>
> > However, if there is filesystem data loss/roll back or an adversary
> > controls the repository, the client may be using the same manifest that
> > was previously used to initialize the counter (and based on which,
> > encrypted data was already written to the repository).
>
> The client will refuse to access a repository if the manifest timestamp
> is older than the timestamp recorded in the clint's cache directory. But
> of course this protection only works as long as the cache directory is
> available.
>

Even if the cache directory is available and a single client is used, what
if the backup is interrupted before committing a transaction (e.g. network
failure)?

Won't that result in the same nonce being used the next time?


> This could be improved further by always increment the counter with a
> large enough amount whenever the stored timestamp is not available
> (unknown repository) or older (repository modified by other client).
>

> > A single client could keep track of the last nonce it used, and ensure
> > that the new nonce is at least as high as that value, but there could be
> > multiple clients accessing the adversary-controlled repository
> > simultaneously.
>
> A multiple clients per repository setup is rarely used since a costly
> full cache rebuild is required whenever the cache directory is detected.
> But that might change if we figure out a way to do the rebuild more
> efficiently in the future.
>

It seems to me the way to efficiently support multiple clients is along the
lines of what you already suggested: mark archives as deleted, but don't
actually delete them, until all clients have a chance to update their
caches.  This means the manifest also needs to store the list of clients
and the last transaction id each client has seen.


> > The safe solution is for the client to randomly generate a new nonce for
> > each session.  That probably means that more than 8-bytes of it have to
> > be stored in each repository entry, though.
>
> Even though I still think the current method is secure, using a random
> IV has other benefits as well. It would for example be easier use more
> than one core for compression and encryption. But as you said, that
> would require changing the encryption envelope format...
>

Perhaps such a change could be done at the same time as some of the other
changes we've been discussing that might also result in repository format
changes.


>
> > As a related issue, if random padding of encrypted payloads is used to
> > hide the chunk size, the amount of padding should be a deterministic
> > function of the content, e.g. based on HMAC(content-id).  That avoids
> > the possibility that due to repository tampering the same chunk would be
> > written with a different amount of padding, which would reveal some
> > information aobut the amount of padding.
>
> Speaking about format change :)
>
> That's a good point. Do you have any idea on how to do this efficiently
> and securely?
>
> I don't know what distribution of random padding would be required to
ensure privacy.  I am also not completely convinced that padding the
encryption envelope is the best way to hide information about chunk/file
sizes.  However, assuming the distribution is known, you could do the
following:

Chunks are already stored in the repository based on their id_hash, which
requires performing a sha256 pass over the chunk data.  (Additionally the
encryption envelope contains an HMAC of the nonce and data, which requires
another sha256 pass over the chunk data.  To avoid having to perform a
third sha256 pass over the chunk data, we could just compute an HMAC (using
a different key) of the id_hash (perhaps actually just the repository key,
which would be equal to the id_hash except for the manifest).  The 32-byte
HMAC would serve as a source of random bits for sampling from the desired
padding distribution.  Conveniently this also means there is no need to
store the amount of padding, since it can be recomputed when loading the
block.

Re: [attic] Nonce replay attack

From:
Jonas Borgström
Date:
2014-05-13 @ 22:03
On 2014-05-13 23:33, Jeremy Maitin-Shepard wrote:
> By the way, although I've mentioned a number of issues I've spotted in
> Attic, the reason I'm on this list is that Attic seems to be the
> best-designed and most elegant free-software backup program available.  I
> really appreciate all the work you've put into it.
> 
> On Tue, May 13, 2014 at 1:25 PM, Jonas Borgström <jonas@borgstrom.se> wrote:
> 
>> On 2014-05-13 20:03, Jeremy Maitin-Shepard wrote:
>>> I believe there is an issue with how the nonce/counter is used with an
>>> untrusted repository:
>>>
>>> Each client initializes its nonce/counter to the value that just follows
>>> the last counter used for the most recent manifest it finds in the
>>> repository.
>>
>> That is not true.
>>
> 
> That is what I gathered from looking at PassphraseKey.detect
> KeyfileKey.detect.  How am I incorrect (other than the timestamp check)?

It was the timestamp check I was referring to

>>> However, if there is filesystem data loss/roll back or an adversary
>>> controls the repository, the client may be using the same manifest that
>>> was previously used to initialize the counter (and based on which,
>>> encrypted data was already written to the repository).
>>
>> The client will refuse to access a repository if the manifest timestamp
>> is older than the timestamp recorded in the clint's cache directory. But
>> of course this protection only works as long as the cache directory is
>> available.
>>
> 
> Even if the cache directory is available and a single client is used, what
> if the backup is interrupted before committing a transaction (e.g. network
> failure)?
> 
> Won't that result in the same nonce being used the next time?

Yes, in that case it's true. Since we know transactions never live
longer than 5 minutes (due to archive checkpointing) we would simply add
a rather small constant to the nonce when extracting it from the
manifest to avoid this.

>> This could be improved further by always increment the counter with a
>> large enough amount whenever the stored timestamp is not available
>> (unknown repository) or older (repository modified by other client).
>>
> 
>>> A single client could keep track of the last nonce it used, and ensure
>>> that the new nonce is at least as high as that value, but there could be
>>> multiple clients accessing the adversary-controlled repository
>>> simultaneously.
>>
>> A multiple clients per repository setup is rarely used since a costly
>> full cache rebuild is required whenever the cache directory is detected.
>> But that might change if we figure out a way to do the rebuild more
>> efficiently in the future.
>>
> 
> It seems to me the way to efficiently support multiple clients is along the
> lines of what you already suggested: mark archives as deleted, but don't
> actually delete them, until all clients have a chance to update their
> caches.  This means the manifest also needs to store the list of clients
> and the last transaction id each client has seen.

Unfortunately the devil's in the details. The main problem is that the
information we want to delete is the same information the other clients
need to update their cache. And requiring client to know about other
client is probably something we should try to avoid if possible...

>>> The safe solution is for the client to randomly generate a new nonce for
>>> each session.  That probably means that more than 8-bytes of it have to
>>> be stored in each repository entry, though.
>>
>> Even though I still think the current method is secure, using a random
>> IV has other benefits as well. It would for example be easier use more
>> than one core for compression and encryption. But as you said, that
>> would require changing the encryption envelope format...
>>
> 
> Perhaps such a change could be done at the same time as some of the other
> changes we've been discussing that might also result in repository format
> changes.

That was what I was hinting at :)

>>> As a related issue, if random padding of encrypted payloads is used to
>>> hide the chunk size, the amount of padding should be a deterministic
>>> function of the content, e.g. based on HMAC(content-id).  That avoids
>>> the possibility that due to repository tampering the same chunk would be
>>> written with a different amount of padding, which would reveal some
>>> information aobut the amount of padding.
>>
>> Speaking about format change :)
>>
>> That's a good point. Do you have any idea on how to do this efficiently
>> and securely?
>>
>> I don't know what distribution of random padding would be required to
> ensure privacy.  I am also not completely convinced that padding the
> encryption envelope is the best way to hide information about chunk/file
> sizes.  However, assuming the distribution is known, you could do the
> following:
> 
> Chunks are already stored in the repository based on their id_hash, which
> requires performing a sha256 pass over the chunk data.  (Additionally the
> encryption envelope contains an HMAC of the nonce and data, which requires
> another sha256 pass over the chunk data.  To avoid having to perform a
> third sha256 pass over the chunk data, we could just compute an HMAC (using
> a different key) of the id_hash (perhaps actually just the repository key,
> which would be equal to the id_hash except for the manifest).  The 32-byte
> HMAC would serve as a source of random bits for sampling from the desired
> padding distribution.  Conveniently this also means there is no need to
> store the amount of padding, since it can be recomputed when loading the
> block.
> 

Re: [attic] Nonce replay attack

From:
Jeremy Maitin-Shepard
Date:
2014-05-13 @ 23:29
On Tue, May 13, 2014 at 3:03 PM, Jonas Borgström <jonas@borgstrom.se> wrote:

Unfortunately the devil's in the details. The main problem is that the
> information we want to delete is the same information the other clients
> need to update their cache. And requiring client to know about other
> client is probably something we should try to avoid if possible...


Well, yes, the simplest approach does require the clients know about each
other.

One way to avoid the clients needing to know about each other is to use a
time delay:

1. When the user requests to delete an archive, a deletion record is
written to the manifest with a timestamp, and the data chunks are
dereferenced (and possibly deleted from the repository) immediately.  The
metadata remains in the repository.  The client also needs to store locally
the list of metadata chunks for that archive (but not the content of those
metadata chunks), which should only be a small amount of data even for a
large archive.

2. Any other client that sees a previously unseen deletion record needs to
fetch the metadata (specifically the list of data chunks) so that it can
dereference all of the data chunks in its cache (but it does not actually
have to delete any chunks that end up with a reference count of 0, since
the deletions already happened in step 1).  Additionally, the client needs
to store locally the list of metedata chunks for the archive.

3. If a client sees a deletion record and determines that sufficient time
has passed since the deletion time (some time period the user specifies),
it both dereferences (and actually removes from the repository if the
reference count reaches 0) all of the metadata chunks for the deleted
archive, and removes the deletion record from the manifest.  It also
deletes its stored copy of the list of metedata chunks for that archive.

4. If a client sees that a deletion record it previously saw has been
removed from the manifest by a different client, it uses its stored list of
metadata chunks for that record to dereference the metadata chunks locally
(but does not delete anything from the repository if the count reaches 0,
since those deletions already happened in step 3).  It then deletes its
stored copy of the list of metedata chunks for the archive.

A client only has to rebuild its cache if it detects that an archive for
which it hasn't seen a deletion record has been removed from the manifest,
which would happen if the client does not access the repository for a
period longer than the deletion waiting period.

(The same basic approach could also be used if the clients *do* know about
each other.)

Re: [attic] Nonce replay attack

From:
Jonas Borgström
Date:
2014-05-14 @ 11:29
On 14/05/14 01:29, Jeremy Maitin-Shepard wrote:
> On Tue, May 13, 2014 at 3:03 PM, Jonas Borgström <jonas@borgstrom.se
> <mailto:jonas@borgstrom.se>> wrote:
> 
>     Unfortunately the devil's in the details. The main problem is that the
>     information we want to delete is the same information the other clients
>     need to update their cache. And requiring client to know about other
>     client is probably something we should try to avoid if possible...
> 
>  
> Well, yes, the simplest approach does require the clients know about
> each other.
> 
> One way to avoid the clients needing to know about each other is to use
> a time delay:
> 
> 1. When the user requests to delete an archive, a deletion record is
> written to the manifest with a timestamp, and the data chunks are
> dereferenced (and possibly deleted from the repository) immediately. 
> The metadata remains in the repository.  The client also needs to store
> locally the list of metadata chunks for that archive (but not the
> content of those metadata chunks), which should only be a small amount
> of data even for a large archive.
> 
> 2. Any other client that sees a previously unseen deletion record needs
> to fetch the metadata (specifically the list of data chunks) so that it
> can dereference all of the data chunks in its cache (but it does not
> actually have to delete any chunks that end up with a reference count of
> 0, since the deletions already happened in step 1).  Additionally, the
> client needs to store locally the list of metedata chunks for the archive.
> 
> 3. If a client sees a deletion record and determines that sufficient
> time has passed since the deletion time (some time period the user
> specifies), it both dereferences (and actually removes from the
> repository if the reference count reaches 0) all of the metadata chunks
> for the deleted archive, and removes the deletion record from the
> manifest.  It also deletes its stored copy of the list of metedata
> chunks for that archive.
> 
> 4. If a client sees that a deletion record it previously saw has been
> removed from the manifest by a different client, it uses its stored list
> of metadata chunks for that record to dereference the metadata chunks
> locally (but does not delete anything from the repository if the count
> reaches 0, since those deletions already happened in step 3).  It then
> deletes its stored copy of the list of metedata chunks for the archive.
> 
> A client only has to rebuild its cache if it detects that an archive for
> which it hasn't seen a deletion record has been removed from the
> manifest, which would happen if the client does not access the
> repository for a period longer than the deletion waiting period.

That should probably work. I've been testing a bunch different ways to
do this without needing to store any extra state in the client cache,
without finding any good enough solution.
But since the metadata required by this approach is so small the size
should not be an issue.

This feature is fairly high on my todo list but I still would like to
reduce the file cache memory usage and chunker/nonce handling before
tackling this.

/ Jonas