File exist

[Michael Wojcik]

My opinion is that your inability to see something does not change its
existence.

Fine, but there's quite a gulf between "your inability to see
something" and "it's impossible to prove the existence or
nonexistence".

So I would say that running under such a system just makes it
impossible to use non-standard means to determine if a file exists,

It's impossible to determine whether a file exists (in principle;
in practice, there are a finite, albeit very large, number of
possible keys, so you can brute-force it), full stop.

that
does not translate in to the file not existing if you can't open it (or
tell it exists) because you don't have the key.

If there's no decision procedure that can distinguish between two
conditions, on what basis do you decide those conditions are
distinct?

With a steganographic deniable filesystem, it's always possible
that a "file" you do succeed in opening is actually just a random
artifact of a combination of the filesystem data and key; it may
not have been created "on purpose" at all. The probability of
such an accidental file diminishes as the file's entropy
increases, of course, but in theory you could find any finite
file in a sufficiently large SD filesystem just by choosing the
appropriate key. (Obviously the key length has to grow in order
to select the necessary "file", by the pigeonhole principle.)

The whole point of an SD filesystem is to erase the distinction
between "does not exist" and "cannot be found (opened, etc)". Any
meaningful message is just some transformation of noise - SD
filesystems keep the noise and make you remember (in a compressed
form, in practice) the transformation.

--
Michael Wojcik (e-mail address removed)

Memory, I realize, can be an unreliable thing; often it is heavily coloured
by the circumstances in which one remembers, and no doubt this applies to
certain of the recollections I have gathered here. -- Kazuo Ishiguro

 

[Keith Thompson]

Keith Thompson wrote: [...]
Hence the "errno=0" prior to fopen(), and the check for "errno != 0"
prior to calling perror().

No, it's still not 100% portable (i.e., it's not guaranteed by the
standard). A failing fopen() could legally set errno to a non-zero
value that has nothing to do with the reason the fopen() call failed.
I presented a (rather implausible) example elsewhere in this thread.

I know that the standard doesn't guarantee that fopen() will set errno
on failure. But does it really allow it to change errno to a non-zero
value that's not the actual error? Is this a "legal" implementation
within fopen()?

...
if ( it_failed )
{
errno = rand();
return(NULL);
}
...

Okay, so someone will probably point out that it's not allowed to call
rand() for some reason.
Right.

So how about:

if ( it_failed )
{
errno = (int)time(NULL);
return(NULL);
}

Yes, and something like it is even plausible.

Suppose the implementer decided not to have fopen() set errno to a
meaningful value on an error, because the standard doesn't require it.
But fopen() is implemented on top of lower-level routines, some of
which do set errno. One of those routines might fail for reasons
having nothing to do with the failure of fopen().

For example, suppose fopen("foo.txt", "w") calls a routine (similar to
the Unix stat() function) that gets information about an existing
file; if the file doesn't exist, it fails and sets errno to EEXIST
("No such file or directory"). (EEXIST isn't defined by the C
standard, but we'll assume it's defined by the implementation).
fopen() now knows that the file doesn't exist, so it attempts to
create it. The attempt fails because, say, the user doesn't have
write permission on the current directory -- but the routine that
attempts to create the file doesn't set errno. Perhaps it just
returns a null pointer, or uses some other mechanism to report errors.

The net result is that fopen("foo.txt", "w") fails with errno set to
EEXIST, implying that the attempt to create the file failed because
the file doesn't exist (!).

This scenario is unlikely to happen in real life; if the stat()-like
function sets errno properly, chances are the file creation function
does so as well. But it's allowed by the standard.

As I mentioned elsethread, this kind of problem could have been
avoided by requiring all functions defined in the standard library, on
failure, *either* to set errno to some meaningful value, *or* to reset
it to its previous value. Or by requiring all standard library
functions to set errno to some meaningful value, and defining EERROR
as a generic unknown error indication.

Well, does "99.99% portable" qualify?

Serious answer: Does it qualify as what? Does it qualify as 100%
portable? No. Does it qualify as good enough for your purposes?
That's entirely up to you.

I wonder if someone wants to implement a C environment where it does
all of the "legal, but probably not taken into account" behaviors?
Things like setting errno to something other than the "real" value,
or randomly zeroing memory on "a = i++".

No, this is not me volunteering to do so.

Like a real-life DS9K? That would be a handy thing to have.

 

[Flash Gordon]

Fine, but there's quite a gulf between "your inability to see
something" and "it's impossible to prove the existence or
nonexistence".

Whether or not you can prove its existence still doesn't affect whether
it exists or not. I run a number of Linux boxes, and even if I gave you
a user account on one of them you still could not tell whether the file
/root/t.txt exists. This does not affect its existence.

It's impossible to determine whether a file exists (in principle;
in practice, there are a finite, albeit very large, number of
possible keys, so you can brute-force it), full stop.

So? I have already stated that there may not be a way to prove whether
or not a file exists. It still either exists or does not exist. Unless
you are using quantum storage in which case, like Schrodinger's cat, it
might both exist and not exist at the same time.

If there's no decision procedure that can distinguish between two
conditions, on what basis do you decide those conditions are
distinct?

So? There is no way for you to determine whether my brother's wife's
uncles house has a second story. Does that affect whether or not it exists?

With a steganographic deniable filesystem, it's always possible
that a "file" you do succeed in opening is actually just a random
artifact of a combination of the filesystem data and key; it may
not have been created "on purpose" at all. The probability of
such an accidental file diminishes as the file's entropy
increases, of course, but in theory you could find any finite
file in a sufficiently large SD filesystem just by choosing the
appropriate key. (Obviously the key length has to grow in order
to select the necessary "file", by the pigeonhole principle.)

The whole point of an SD filesystem is to erase the distinction
between "does not exist" and "cannot be found (opened, etc)". Any
meaningful message is just some transformation of noise - SD
filesystems keep the noise and make you remember (in a compressed
form, in practice) the transformation.

So? The information still either exists or does not exist. Just because
you or I can't prove whether or not it exists doesn't change that. Even
if the key is lost forever the information is still encoded there until
it is overwritten.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php

 

[Kenneth Brody]

Michael Wojcik wrote:
[... "failed to open" vs. "file doesn't exist" ...]

With a steganographic deniable filesystem, it's always possible
that a "file" you do succeed in opening is actually just a random
artifact of a combination of the filesystem data and key; it may
not have been created "on purpose" at all. The probability of
such an accidental file diminishes as the file's entropy
increases, of course, but in theory you could find any finite
file in a sufficiently large SD filesystem just by choosing the
appropriate key. (Obviously the key length has to grow in order
to select the necessary "file", by the pigeonhole principle.)

The whole point of an SD filesystem is to erase the distinction
between "does not exist" and "cannot be found (opened, etc)". Any
meaningful message is just some transformation of noise - SD
filesystems keep the noise and make you remember (in a compressed
form, in practice) the transformation.

Does this mean that, if you have the "right" filename, you can open it
in any mode whatsoever? There's no such thing as a read-only file?

(And, in any case, this is just a "special case" situation, which has
been designed to purposfully hide such distinctions.)

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Kenneth Brody]

Yes, and something like it is even plausible.

Suppose the implementer decided not to have fopen() set errno to a
meaningful value on an error, because the standard doesn't require it.
But fopen() is implemented on top of lower-level routines, some of
which do set errno. One of those routines might fail for reasons
having nothing to do with the failure of fopen().

[... fopen() using stat() to test existence ...]

The net result is that fopen("foo.txt", "w") fails with errno set to
EEXIST, implying that the attempt to create the file failed because
the file doesn't exist (!).

This scenario is unlikely to happen in real life; if the stat()-like
function sets errno properly, chances are the file creation function
does so as well. But it's allowed by the standard.

True, since the Standard doesn't specify how fopen() actually opens
the file, though it's probably via the "non-Standard" open() call.

Thanks for a plausible, yet still unlikely, scenario.

I have run into cases where fopen() would fail, even though the
low-level open() call succeeded. Sometimes, malloc'ing the buffer
would fail, so even though the file was "open", it would return NULL,
and errno would be "out of memory". Other times, the runtime library
was limited to X open FILEs, while the O/S was set to allow Y (where
Y>X) open files. So, the open() call would succeed, and then the
runtime library would fail because there was no FILE to stick it in.
(In this case, I think errno was left unchanged.)

As I mentioned elsethread, this kind of problem could have been
avoided by requiring all functions defined in the standard library, on
failure, *either* to set errno to some meaningful value, *or* to reset
it to its previous value. Or by requiring all standard library
functions to set errno to some meaningful value, and defining EERROR
as a generic unknown error indication.

I think "resetting it to its previous value" would add too much
overhead to the library, as it would require _every_ failable function
to save/restore it. However, requiring that it set errno on failure,
even to some generic "EERROR" if needed, would be useful.

Well, does "99.99% portable" qualify?

Serious answer: Does it qualify as what? Does it qualify as 100%
portable? No. Does it qualify as good enough for your purposes?
That's entirely up to you.

I wonder if someone wants to implement a C environment where it does
all of the "legal, but probably not taken into account" behaviors?
Things like setting errno to something other than the "real" value,
or randomly zeroing memory on "a = i++".

No, this is not me volunteering to do so.

Like a real-life DS9K? That would be a handy thing to have.

I think the C compiler would be easier to build in real-life, however.

They have test suites to verify a compiler's adherence to the Standard,
so why not a compiler that stress-tests C source?

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Mark McIntyre]

Whether or not you can prove its existence still doesn't affect whether
it exists or not.

Not to get metaphysical, but in point of fact its central.

I run a number of Linux boxes, and even if I gave you
a user account on one of them you still could not tell whether the file
/root/t.txt exists. This does not affect its existence.

In a very real sense, it /defines/ its state of existence. In this
case, indeterminate.

I'm guessing you're not a physicist, and don't have a cat. Or any
boxes.

Mark McIntyre

 

[Flash Gordon]

Not to get metaphysical, but in point of fact its central.


In a very real sense, it /defines/ its state of existence. In this
case, indeterminate.

I'm guessing you're not a physicist, and don't have a cat. Or any
boxes.

Well, unless you can prove that no one else is looking at the file that
might or might not exist, then the state of it's existence is still not
completely dependant on whether you can see it or not.

I do know a bit about cats, boxes and physics and the relationship
between them. Perhaps we should repeat the experiment with a file
containing a picture of a cat and a computer set up to delete the file
if the particle decays?
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php

 

[Michael Wojcik]

Whether or not you can prove its existence still doesn't affect whether
it exists or not.

Sigh. Whether or not *I* can prove the existence of something is
very different from whether or not it's possible *in general* to
prove the existence of something.

The existence of an entity whose existence cannot be demonstrated is
a question for metaphysics. It's not at all certain that existence
is independent from proof (or demonstration).

So? I have already stated that there may not be a way to prove whether
or not a file exists. It still either exists or does not exist.

Simply claiming that does not constitute an argument.

So? There is no way for you to determine whether my brother's wife's
uncles house has a second story. Does that affect whether or not it exists?

Entirely irrelevant, as I noted above.

So? The information still either exists or does not exist.

That's a tenuous position that's widely disputed. Do you have an
actual argument to make in favor of it, or is this just a blind
belief?

Just because
you or I can't prove whether or not it exists doesn't change that.

Let me try again: it is *impossible* for *anyone* to prove whether an
SD filesystem contains a given piece of information. Or considered
another way, an SD filesystem contains *all* messages of less than a
certain maximum entropy (where the amount of entropy is a function of
the size of the filesystem).

Even
if the key is lost forever the information is still encoded there until
it is overwritten.

That's a question of metaphysics, or of belief; it can't be positively
demonstrated.

--
Michael Wojcik (e-mail address removed)

An intense imaginative activity accompanied by a psychological and moral
passivity is bound eventually to result in a curbing of the growth to
maturity and in consequent artistic repetitiveness and stultification.
-- D. S. Savage

 

[Michael Wojcik]

Michael Wojcik wrote:
[... "failed to open" vs. "file doesn't exist" ...]

With a steganographic deniable filesystem, it's always possible
that a "file" you do succeed in opening is actually just a random
artifact of a combination of the filesystem data and key; it may
not have been created "on purpose" at all. The probability of
such an accidental file diminishes as the file's entropy
increases, of course, but in theory you could find any finite
file in a sufficiently large SD filesystem just by choosing the
appropriate key. (Obviously the key length has to grow in order
to select the necessary "file", by the pigeonhole principle.)

The whole point of an SD filesystem is to erase the distinction
between "does not exist" and "cannot be found (opened, etc)". Any
meaningful message is just some transformation of noise - SD
filesystems keep the noise and make you remember (in a compressed
form, in practice) the transformation.

Does this mean that, if you have the "right" filename, you can open it
in any mode whatsoever? There's no such thing as a read-only file?

That's an implementation detail. An SD filesystem could include
filesystem metadata in such a way that for a given message, there
might exist a key which produced that message plus metadata that
meant "read only" to the filesystem, but no key shorter than the
message itself which produced the message plus "read/write" metadata,
so in effect the file could only be opened read-only. Or it might be
implemented on read-only media, for that matter.

(And, in any case, this is just a "special case" situation, which has
been designed to purposfully hide such distinctions.)

Right, but my original point - that the distinction between "does not
exist" and "cannot be opened" doesn't always hold - only requires a
counterexample to that distinction.

There are other, less esoteric examples where a filesystem might not
be able to meaningfully distinguish those conditions. Secure file
access in general often obscures the distinction at the media-access
level, so the API couldn't return an error indicator that
distinguished them. A network filesystem often wouldn't be able to
tell whether a remote resource was unavailable or simply didn't
exist. And so on.

More generally, a "does not exist" indication cannot be completely
reliable, because that would require proving a negative. It can be
made arbitrarily reliable under specific constraints, but no
algorithm can ensure that a given message exists nowhere (except for
the special case of messages that provably cannot exist, like
compressed forms of Chaitin's omega, and it's dubious that those can
be said to constitute "messages" per se anyway). SD filesystems are
just a way of leveraging that doubt in practice.

 

[Walter Roberson]

An SD filesystem could include
filesystem metadata in such a way that for a given message, there
might exist a key which produced that message plus metadata that
meant "read only" to the filesystem, but no key shorter than the
message itself which produced the message plus "read/write" metadata,
so in effect the file could only be opened read-only.

I don't see where the restriction to "no key shorter" would come in,
nor the relevance of that length to "in effect" make the file read-only?
If you had said "no key that did not include the message itself"
perhaps, but even then it doesn't sound right.

If I have a file on a SD filesystem that currently decodes to
1 byte, and I have a read-write key to it, then the extra 1 byte
you would impose is not a meaningful expansion of key space
sufficient to "in effect" make the file read-only. But once I
have a read-write key to the file and I write (say) 1 megabyte
there, the read-write keysize is not suddenly going to bloom
to more than a megabyte: the read-write key would stay the same.

It seems to me that any restriction that forced keys to be
larger than the files would impede the deniability. Isn't it the
case that for SD, -every- key should get -something-? If so,
then every read-write key would, in your "no shorter" proposal,
map through SD to a shorter value -- but that would, in effect,
be a compression function, and by the pigeon-hole principle
you can't have a compression function which uniquely maps every input
to a shorter output. Therefore if you have read-write keys, some of
them must be shorter than the file they allow to be written.

[This argument does not hold if some keys are "invalid". For example,
there is the trivial mapping that the read-write key is a byte of 0
followed by content, and that the value so accessed is the content
with the 0 stripped off; this does uniquely map each valid input,
but the cost of it is that keys that started with 1 to 255 in the
first byte could never be read-write keys.]

 

[Andrew Poelstra]

I don't see where the restriction to "no key shorter" would come in,
nor the relevance of that length to "in effect" make the file read-only?
If you had said "no key that did not include the message itself"
perhaps, but even then it doesn't sound right.

If I have a file on a SD filesystem that currently decodes to
1 byte, and I have a read-write key to it, then the extra 1 byte
you would impose is not a meaningful expansion of key space
sufficient to "in effect" make the file read-only. But once I
have a read-write key to the file and I write (say) 1 megabyte
there, the read-write keysize is not suddenly going to bloom
to more than a megabyte: the read-write key would stay the same.

It's possible that the key will grow, similar to an autokey cipher,
although more secure.

It seems to me that any restriction that forced keys to be
larger than the files would impede the deniability. Isn't it the
case that for SD, -every- key should get -something-? If so,
then every read-write key would, in your "no shorter" proposal,
map through SD to a shorter value -- but that would, in effect,
be a compression function, and by the pigeon-hole principle
you can't have a compression function which uniquely maps every input
to a shorter output.

Most compression algorithms eliminate redundancy in texts; by replacing
the repeated work "and" or repeated byte sequence "te se" with a single
byte, all information is retained and therefore the compression does
retain all information.

As I'm typing this, I realize that my method of compression is not an
"algorithm" in the mathematical sense, because it can't be expressed as
a series of formulas (or can it?). So, you're point still stands.

 

[Walter Roberson]

[OT]
It seems to me that any restriction that forced keys to be
larger than the files would impede the deniability. Isn't it the
case that for SD, -every- key should get -something-? If so,
then every read-write key would, in your "no shorter" proposal,
map through SD to a shorter value -- but that would, in effect,
be a compression function, and by the pigeon-hole principle
you can't have a compression function which uniquely maps every input
to a shorter output.

Most compression algorithms eliminate redundancy in texts; by replacing
the repeated work "and" or repeated byte sequence "te se" with a single
byte, all information is retained and therefore the compression does
retain all information.

[Going further OT]

I am not a compression expert, but I have studied the subject and
hung around in comp.compression for a few years.

The heart of compression turns out not to be the elimination of
redundancy: that's an optimization.

A function is a compression function if and only if for at least one of
its inputs, the output is "shorter" than the input. The compression
function is "lossless" if the function is one-to-one, and "lossy" if
the function is not one-to-one.

There does not need to be a "formula" or "algorithm" for the
compression function: it can be a pure function in the mathematical
sense where a function is a set of tuples mapping a Domain to a Range
and that the tuples can be arbitrary.

It may sound pretty useless to have a compression function that only
compresses one input, but imagine that the corpus to be compressed
consists of data that is ten million times more likely to be that
particular input: you can see that that seemingly useless compression
function might be just the thing *for that particular input data*.

It is not possible to construct a compression program that compresses
*every* arbitrary input: by the pigeon-hole principle, if one is
operating over an unrestricted input domain, then if some input is
compressed then at least one output must be an expansion.

The goal of people who write generalized compression programs is have
the program compress inputs that likely to be "interesting" to humans,
and to postpone the expansion to inputs that are unlikely to be of
interest. It so happens that humans tend to be "interested" in inputs
that contain a fair bit of redundancy and so redundancy-elimination
algorithms tend to be fairly prominent, but such algorithms, though
very important, are not actually the foundation of compression theory.

 

[Michael Wojcik]

I don't see where the restriction to "no key shorter" would come in,
nor the relevance of that length to "in effect" make the file read-only?

I just wanted to specify a stronger condition. Filesystems are a
compression mechanism: they let you substitute a shorter message
(the location of the file) for a longer one (the file itself). In
specific instances, the file may be shorter than the message that
specifies its location, but in general this holds for a majority
of cases. Consequently, I was indicating that it didn't matter if
there was a key longer than the message that didn't satisfy the
condition for read-only access.

Put another way, if the necessary key is larger than the file, you
might as well just carry around the file, and forget about the
filesystem entirely, so that case isn't interesting. And since
typical SD designs let you create any message no longer than the size
of the filesystem, by finding a suitable key, it's possible that the
implementation would reject any key over a certain size, on the
grounds that "real" keys used in practice would be kept to a
managable length. (The deniability aspect can be maintained to a
sufficient level to meet a given threat model even in this case by
setting the maximum key length high enough, provided the threat model
doesn't require absolute deniability.)

On reflection, though, this may not be an interesting distinction.
For one thing, the compression function of a filesystem is really the
mapping between the location of the file and the pair consisting of
the set of all possible valid messages contained in that file and
the index of the current message.

It's since occurred to me that a more relevant issue is what the
distinction between "read-only" and "writable" means in this context.
For example, does writable imply readable? If not, how is write-
only access implemented? (This is a different question from a
possible implementation of stdio, since the latter could simply
ignore readability when opening write-only.)

In practice, a more suitable way of imposing write protection for an
SD filesystem would probably be to keep file verifiers separately, so
they can't be captured as part of the filesystem and used to defeat
deniability.

Oh well. This is really a sci.crypt topic, and to be honest just
something I keep an idle eye on, so I might be talking complete
rubbish about the possibility of imposing access restrictions in a
case like this.