Deniable data storage

[Peter Fairbrother]

Tarapia Tapioco wrote:

> James A. Donald (jamesd at echeque.com) wrote on 2003-11-06:
>> I want fully deniable information storage -- information
>> theoretic deniable, not merely steganographic deniable, for
>> stenography can never be wholly secure.

Information-theoretic deniability is impossible (or impractical). You can
have computationally-bounded secure deniability though.

> 
> So, StegFS is not "deniable enough"? I'm not much of a theory buff,
> but it sure sounds nice from the paper...
> 

StegFS (if that's the one Markus Kuhn wrote, there is another program with a
similar name which isn't as secure), and the other construction in Ross
Anderson, Roger Needham and Adi Shamir's paper [1] are pretty good, at least
as good as your outline construction.

All hide ciphertext in random data, rather than in eg images, where there is
no underlying pattern to the covertext which an adversary can use a better
understanding of than the filing system has to extract and identify
ciphertext.

The moral? - hide ciphertext in random data, not "partly-random" data such
as images.

You might also want to look at Mnemosyne [2], but I haven't analysed it and
have no idea whether it's any good.


It also depends on whether your adversary is going to torture you, or take
you to Court. There's not a great deal of difference in effect, but a
torturer can harm you on suspicion only, whereby a Court can't jail you on
suspicion alone but needs, at least in theory, proof beyond reasonable
doubt.




Getting a bit theoretical now, but still important:

Two problems with all these systems are observability and secure deletion.
If the database can be continuously observed (eg a NFS-based FS) then an
adversary can ask why the SFS was modified. This can be overcome - I'm
writing a paper on how to do that right now, but it's not finished yet.

Secure deletion is harder - if someone can prove that some data is in the
SFS (or, combining this with observability, that some data was at some time
in the SFS) then they can demand a key - are you going to remember a zillion
different keys/passwords, and what they refer to? If you store them
somewhere then they can demand the key to the keys, so to speak.
Problematic.

I think secure deletion in observable SFS's is impossible, it seems obvious
on information grounds - but there also seems to be just a teeny hint of a
crack in that proof. I'm working on it.



James, you might want to move this to eg the cryptography list if you want
more technical answers. Or subject yourself to sci.crypt's abuse, which will
at least stop some elementary mistakes.

[1] http://www.cl.cam.ac.uk/ftp/users/rja14/sfs3.pdf

[2] www.cs.rice.edu/Conferences/IPTPS02/107.pdf

-- 
Peter Fairbrother