2

Recently I've been having a look at some interesting stenographic filesystems such as RubberhoseFS and StegFS. As far as I can see (at least in the case of StegFS) infeasibility of determining how many keys are used and how much content is encrypted with different keys is achieved to the extent that it is as strong as the cryptographic primitives involved - it really is infeasible to determine the number of different files encrypted with different keys and how many keys even exist in the system. In other words one can plausibly deny that any other keys save the ones he/she provided were used*. However, there is one disadvantage - these systems (at least StegFS) tend to achieve this by become lossy filesystems. So the main question is - is it possible to implement a system with plausible denyability that is at least as strong as accepted cryptographic primitives (AES-CBC, SHA1-HMAC, e.t.c.) yet is not a lossy filesystem?

*) I'm not saying exist here, because technically they do exist. One can just 'decrypt' any file name (existent or non-existent) with any random key and you will end up with something.

Tom K.
  • 7,913
  • 3
  • 30
  • 53
Samuel Allan
  • 132
  • 8
  • First, it's steganographic, not stenographic (the latter refers to shorthand writing), and second... I'm confused. "Lossy" usually refers to a system in which you cannot recover the exact original data, e.g. lossy compression of images. Do you mean a filesystem with plausible deniability where the secret container does not take up any reserved space, yet you can still somehow fill both the visible and hidden containers? If such a thing were possible then you could double the size of your disk for free. – Polynomial Feb 08 '18 at 22:42
  • @Polynomial, StegFS is an example of a lossy steganographic filesystem - and yes it means there is a chance one file will be written over by another file (beacuse file storage location is determined based on password and filename). And no I don't want to magically increase disc space, I have thought about this and this is the obvious conclusion, however, what if a filesystem had 100 volumes of fixed size to begin with (loaded with random data) and it was the user's choice to use some of them to store encrypted files, would this not be deniably steganographic? – Samuel Allan Feb 08 '18 at 23:23
  • @Polynomial, what if some kind of homomorphic encryption could be used too? Where you could use some homomorphically encrypted metadata portion to determine where you can put a new file, yet you would not be able to learn where existing files had already been placed – Samuel Allan Feb 08 '18 at 23:24
  • 1
    Homomorphic encryption wouldn't offer anything here, and there aren't feasible implementations of full homomorphism yet anyway. Your system in your first comment would prove that you were using a steganographic system in the first place, which rather proves that you are hiding files, which in any practical scenario is likely to get you in more trouble rather than less. The point of steganography is for the attacker to not even know you were using that kind of system at all. – Polynomial Feb 09 '18 at 10:30
  • @Polynomial, I see no problem with letting your attacker know you are having a steganographic file system. I see the main point of steganographic filesystems as a way to avoid legal responsibility to reveal all keys - because there is no proof more keys than provided even exist. Also homomorphism was mentioned in my comment as a potential idea and not a solid concept, the answer I am looking for is one that takes a stance (such as YES it is possible, or NO it is not possible, provides a system & an approximate proof of the statement) – Samuel Allan Feb 09 '18 at 23:08
  • 1
    @Polynomial, the idea behind a steganographic filesystem is that you can hand over the keys to your financial records immediately, then hand over the keys to your collection of goat porn when pressed, and they can't prove you've also got a set of keys that would reveal the stolen Death Star plans. – Mark Feb 14 '18 at 04:52
  • 1
    @Mark Yes, I'm well aware of that - it's a feature in many FDE solutions - but in practice you're also required to hide the fact that you're using such a system in the first place, because almost any legal jurisdiction will consider the suspicion actionable, and if a court has any reason to believe that you have hidden evidence then they can hold you in contempt *even if the data does not exist*. They don't need to prove that the data exists, they just need reasonable suspicion that you are hiding something. This leaves you utterly screwed. – Polynomial Feb 14 '18 at 12:02
  • @Polynomial, it needs to be *reasonable* suspicion. In an ideal steganographic filesystem, once they've got the keys for your finances and your goat porn, every byte in the filesystem has been accounted for. Yes, you *could* be storing the Death Star plans, but you could also be storing the location of the Holy Grail, or a roster of KGB spies, or nothing at all, and no analysis can tell which is the case. This makes the filesystem useless for the prosecution, since "innocent until proven guilty" means they can't just make accusations and require you to disprove them. – Mark Feb 14 '18 at 22:21
  • @Mark No, that's not how it works at all, but feel free to try that in court. I suggest clearing your calendar for the next few years if you do. – Polynomial Feb 15 '18 at 10:50
  • @Polynomial: "...they can hold you in contempt even if the data does not exist": I've been looking for actual cases for a while. Can you refer us to one? – Out of Band Feb 15 '18 at 14:12
  • @Pascal As far as I can tell the law has not been tested against "hidden volumes", so to speak, but [RIPA 2000](https://www.legislation.gov.uk/ukpga/2000/23/contents) in the UK allows for a 2 year prison sentence (or 5 in the case of child abuse charges) should a suspect refuse to provide passwords for encrypted materials if there is "reasonable suspicion" that encrypted materials exist. The courts here have jailed a few people for not handing over passwords, although the specifics are not public because the cases are still considered open. – Polynomial Feb 15 '18 at 14:28
  • Ultimately it falls down to the fact that if you use a product with a plausible deniability option (e.g. TrueCrypt's hidden volumes) you're going to have to be *extremely* convincing to get a court to believe that you only used the regular encryption feature and not the hidden volume feature. If you're up to anything considered criminal in your jurisdiction, and your defence is based upon the "hidden data" feature, you are literally betting your livelihood on the correctness of the software's hidden volume implementation and your ability to bluff that you didn't use that feature at all. – Polynomial Feb 15 '18 at 14:32
  • @Polynomial - I completely agree (see my answer). But I do wonder why the law handles such cases in the "proof your innocence" instead of the "innocent until proven guilty" mode. It also makes me wonder whether all my old encrypted hard drives and zip disks (they reach back more than 20 years) would pose a threat to me if I was ever accused of anything - I've long since forgotten the passphrases to some of those, so I couldn't actually prove there was nothing illegal rotting away on them... – Out of Band Feb 15 '18 at 16:51
  • @Pascal In this specific case it's because it's not about proving guilt, it's about responding to discovery, and that's a hugely different aspect of the legal process. Usually you are free to omit information or not incriminate yourself (no comment) but when it comes to discovery you *have* to provide all pertinent information, and being suspected of hiding evidence puts you in a very perilous situation. – Polynomial Feb 15 '18 at 17:58
  • @Pascal If you use a TrueCrypt-like solution, all they need to do is ask for your volume password (which you are legally required to provide) and decide that the contents of the non-hidden volume are not convincing (e.g. you made a 100GB volume and all you put in it were some credit card details and a small set of compromising pictures of you and your spouse) and then you're utterly screwed unless you can convince them otherwise, which may be a damn hard job depending on what you're accused of, how expensive your lawyer is, and how grumpy the judge is feeling on that particular day. – Polynomial Feb 15 '18 at 18:06

1 Answers1

0

is it possible to implement a system with plausible denyability that is at least as strong as accepted cryptographic primitives (AES-CBC, SHA1-HMAC, e.t.c.) yet is not a lossy filesystem?

Yes, in a way. TrueCrypt and it's successor VeraCrypt support hidden volumes. They work by embedding a hidden encrypted container inside an encrypted container. You can protect the "inner" or "hidden" volume from being partly overwritten if you have access to it. But see Mark's comment for a gotcha. There are more; the TrueCrypt manual explains some of them.

This goes for StegFS, too. StegFS is only lossy if you don't provide it with the passwords to all the security levels you're using.

So you can easily construct a steganographic filesystem which doesn't lose your files - but in order for the filesystem to not overwrite them, it needs to know where they are, and this can only be achieved if you tell it the necessary passwords/passphrases before starting to work on the file system.

Have your cake and eat it, too

This is from your question in the comments:

Basically my biggest question was whether you can derive the place to store the file given the password, and somehow there would be a function that would allow you to find a free spot, yet would not reveal used spots

Again, if you provide the system with all the relevant passwords, this is easy. A very simple way to come up with stable disk storage locations based on passwords is by using hash functions - hash a password, or any other combination of identifiers, and get a stable number, which you can use as a pointer to a disk storage block.

If you DON'T want to provide all the relevant passwords, then it becomes much, much harder, and file system efficiency will suffer greatly.

First, you'll have to agree on an important point: The file system storage space is limited. If you have, say, 1 TB of space, and you have 1 GB of hidden files stored in it, then no matter how good the system is, if you write 1 TB of files to the disk, your hidden files will get overwritten. This is impossible to avoid.

But there may be methods to make sure that the files only start to get overwritten after you copied the first 999 GB to the disk.

Consider the following block allocation scheme:Whenever your file system requests a free storage block, a counter gets incremented and the counter determines which block to allocate. This means that you won't ever allocate a block that's already used as long as there still are free blocks on the disk. So you don't need to worry about overwriting hidden files as long as there is still free space on the disk.

The idea comes with a number of problems. For example, in the presented form, this doesn't work so good because you can immediately see how many blocks were allocated. Then you could count the number of blocks currently assigned to visible files and if that differed greatly from what you came up with, you could infer that there are lots of blocks assigned to hidden files. The other explanation would be that these were blocks of files you had deleted, but that's another problem with this system: There's no easy way to claim blocks of deleted files - if you want to reclaim the space of deleted files, you'd have to run special defragmenter software that reorganized all the data on disk.

There's another idea that might work a little bit better: You can have the block allocator for visible files allocate free blocks by allocating blocks 1, 3, 5, 7, 9, ..., and eventually coming back in reverse to claim the even blocks ..., 10, 8, 6, 4, 2.

Then you could have the allocator of the first hidden level allocate blocks starting at 2, 6, 10, 14, ...

Then you could have the allocator for the second hidden level allocate blocks starting at 4, 12, 20, ...

and so on. Each level L would provide 1/2^L of the total available space before starting to mess with data stored in other levels. Depending on how much data you stored on the various levels, level 1 could get away with storing more than 50% of data before starting to overwrite data in all the other levels.

(BTW: This would have a side effect: In this system, if you wanted or needed to, you could prove that there were no more hidden levels beyond the last one by storing twice the number of blocks that were actually assigned to it in it. This would overwrite the data of all the lower hidden levels. E.g. If you wanted to prove that there were no more hidden levels beyond the first hidden level on a 1 TB disk, you'd just have to store 500 GB of data in it, and if you used the file system without any hidden levels, you could store the full 1 TB)

But does plausible deniability work in real life?

I'm very sceptical about whether plausible deniability works in real life (generally, not just with TrueCrypt/VeraCrypt/StegFS).

I imagine two cases in which you might be forced to give up your encryption keys / passphrases:

  • You're legally obligated to give them up because law enforcement in your country has the right to request them, and a judge can hold you in contempt if you don't give them up

  • You're facing some criminal who is willing to torture the keys out of you.

In both cases, I fail to see how saying "there really aren't any hidden files on my computer besides the ones I showed you" makes a practical difference from "I don't remember the password for the encrypted file you see right here, but I remember it is last year's tax return statement."

Both law enforcement and the criminal probably won't believe you either way (there is a reason why they're talking to you! they expect you to have some specific documents they haven't found yet, after all), and they'll use whatever methods they have at their disposal to make you give up the key/passphrase. You're better off with law enforcement, of course, because the methods they can use are much more limited in civilized states.

Just think about what it tells an attacker about you if you use StegFS: It means you're trying to hide files. So how many files do you have to reveal before you can plausibly explain there is nothing more to reveal? This might actually work against you: You can't plausibly show that you've revealed all your hidden files, so a court in a country where the law allows for it might hold you in contempt indefinitely because you can't prove your innocence...

If you do live in a country where a court has to prove your guilt instead, then what would most likely happen is that the police confiscated all your drives and sent them to be analysed by a forensic unit to see if they could find a way around your denials. They probably wouldn't be discussing your steganographic file system with you in order to find out how plausible it was that you kept hidden data on it. So in that case, again, it wouldn't matter whether you used a steganographic file system or simply encrypted your data.

Plausible deniability through steganography is a nice idea, but I seriously doubt it works in practice. https://xkcd.com/538/ is somewhat related to this - the real world doesn't always conform to what we're imagining it to work like.

Out of Band
  • 9,150
  • 1
  • 21
  • 30
  • Plausible deniability works very well with encryption of external drives. I have several dozen storage devices in my home, and they are all either encrypted with VeraCrypt, or securely wiped. There's no way to tell which is which and honestly, even I have trouble remembering. Plausible deniability is much less effective for containers (how do you explain a large, opaque file on your computer?) and system encryption (the bootloader itself must remain in plaintext), but for external device encryption, it's wonderful. – forest Feb 14 '18 at 04:05
  • TrueCrypt/VeraCrypt can be steganographic, or it can be non-lossy, but it can't be both at the same time. If you set up a hidden volume, then either you use the outer volume without providing the password to the hidden volume and risk having the hidden volume corrupted, or you *do* provide the password to the hidden volume when using the outer volume and leave a suspicious-looking hole in the outer volume's disk usage patterns. – Mark Feb 14 '18 at 04:56
  • @Mark: Well, yes. This is why the manual tells you to set up the outer volume as a decoy and basically not use it, except to copy some decoy files to it when you set it up. What matters is that you CAN hide files with VeraCrypt without running the risk of losing them, which is what the OP asked. – Out of Band Feb 14 '18 at 08:37
  • @forest: You actually can install TrueCrypt (VeraCrypt?) with a hidden encrypted system in a manner that might offer you plausible deniability, but the explanation you're supposed to give according to the manual as for why you have all these partitions set up the way they are is a good illustration of the problems I have with plausible deniability: Sure, they offer ONE explanation as to why things are the way they are, but the other one, that you're running a hidden system in one of these partitions, is much more plausible to someone who wants to find secret information on your computer. – Out of Band Feb 14 '18 at 08:40
  • @Pascal, yes, if you follow the manual's directions, you won't damage the contents of the hidden volume. But you won't hide them, either: an attacker examining the outer volume will see a huge unused region. – Mark Feb 14 '18 at 09:25
  • @Mark: This doesn't differ from what you'd expect to see on a plain file system that's not yet filled up 100% with files. If you have a 1 TB disk and your hidden volume is 50 GB, a block of 5% of seemingly free space at the end of the disk isn't anything special. – Out of Band Feb 14 '18 at 09:30
  • @Pascal, in order to reduce fragmentation when a file grows, most filesystems scatter files around the available space rather than packing them front-to-back. You can't do this with a VeraCrypt hidden volume. – Mark Feb 14 '18 at 09:34
  • Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/73115/discussion-between-pascal-and-mark). – Out of Band Feb 14 '18 at 09:36
  • Thank you for a detailed answer! Still waiting for other potential answers, but thanks! Basically my biggest question was whether you can derive the place to store the file given the password, and somehow there would be a function that would allow you to find a free spot, yet would not reveal used spots (I realize this sounds a bit weird - but if for instance, by far not all free spots would be given off, and the free spot selection depended on existing data on disk, a construction could be built where iterating through all free spots would not reveal where the used space is). – Samuel Allan Feb 15 '18 at 23:20
  • @Samuel Allan: I expanded my answer to take this into account. – Out of Band Feb 16 '18 at 15:40