[Cryptography] Really good ideas, harsh reality, tailored covertraffic

Peter Fairbrother peter at tsto.co.uk
Sun Aug 30 00:03:08 EDT 2020

I don't know whether you have been following the terakey thread, but 
afaict it is something which at first sight looks like a great idea, but 
turns out not to work as advertised.

I had a similar - looks great but doesn't work - idea a decade or more 
years ago, in the context of steganographic file systems "in the cloud"; 
or more generally steganographic file systems where every read and write 
is visible to an attacker.

[a steganographic file system is a file system where unless you know the 
relevant keys you can't tell whether something in it is a real file or 
not, nevermind read the contents]

[this is not a cautionary tale, but it did hurt at the time]

The cloud filing system would have a bunch of files, all the same size, 
all filled with random-looking data, stored in the cloud. Some of these 
would contain encrypted real user files, some would just be actual 
random data.

A subset of these files would also be copied/stored in the user's 
computer. They would act as a pool.

Using universal re-encryption these pool entries would be re-encrypted 
and returned to storage in a randomly-chosen fashion, replacing their 
cloud counterparts, at regular intervals - the mechanism to do this 
would not need to know whether the file was a real file or not [1].

Another file, chosen either at random or in accordance with user read 
need, would then be transferred into the pool replacing the written-out 
file in the pool.

This store-fetch cycle would repeat at regular intervals.

When a real user file was created or deleted it would initially go into 
the local pool; in the creation case replacing a randomly-selected pool 
entry, in the deletion case by deleting the user key.

As the cycle mechanism would not know whether the local pool file was a 
real file or not (if it did know it could be called to account), real 
files were duplicated and spread over the cloud to minimise deletion. 
Bit complicated, but that part also worked.

Great idea. The paper was accepted for one of the PET conferences. Many 
people congratulated me.

Except - it doesn't work in real-world numbers. There are patterns to 
real user file accesses, and these patterns are detectable.

If an attacker can see all present and past reads/writes to the cloud 
store, using that randomly-chosen replacement pool system you can only 
say a vanishing proportion of the real files are secure in existence.

Practically it might be useful, but only against your little sister. 
Well maybe a bit, or quite a bit, more than that; but not securely, 
against a major adversary.

So I went away and gnawed my liver.

Damn. Great-seeming idea, but it didn't work. BTW, after a while fresh 
human liver makes you feel sick and have the dire-rear.

But ..

Out of this chaos I invented tailored covertraffic.

Tailored covertraffic is covertraffic where an observer can't say with 
any certainty, based on all past observations and all other link-based 
evidence available to him, that any piece of traffic is real traffic  - 
as it could also have been plausibly generated by the tailored 
covertraffic generating mechanism.

Tailored covertraffic covers real traffic better than random 
covertraffic because it can cover a specific piece of real traffic more 
efficiently than random covertraffic can by hiding it in a 
smaller-but-more-likely set of possible traffics.

I have often meant to write a paper about tailored covertraffic, 
someday: but it is not complicated, just complex, the name and 
description should be enough to give the idea.

There is still one more problem (at least) - given a cloud storage set 
and a set of revealed files, can an attacker say with confidence that 
there are more real files still to be revealed (without identifying 
which files) in the storage set?

And all this with a complete historical access/change history?

Afaict neither is an insoluble problem, but they do have to be considered.

And I also invented - but that's another story, I'm working on that. :)

Peter Fairbrother

[1] I also invented a suitable universal re-encryption mechanism for this.

and this has now a become an almost drunken rambling, so don't take it 
too otherwise. But it may still be a bit wise, I hope, else I wouldn't 
have posted it.

More information about the cryptography mailing list