File exist

[Mark McIntyre]

Re: File exist

On Thu, 20 Apr 2006 21:29:43 +0100, in comp.lang.c , Flash Gordon
<spam@flash-gordon.me.uk> wrote:
[color=blue]
>Michael Wojcik wrote:[color=green]
>> Fine, but there's quite a gulf between "your inability to see
>> something" and "it's impossible to prove the existence or
>> nonexistence".[/color]
>
>Whether or not you can prove its existence still doesn't affect whether
>it exists or not.[/color]

Not to get metaphysical, but in point of fact its central.
[color=blue]
>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.[/color]

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
--
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

[Flash Gordon]

Re: File exist

Mark McIntyre wrote:[color=blue]
> On Thu, 20 Apr 2006 21:29:43 +0100, in comp.lang.c , Flash Gordon
> <spam@flash-gordon.me.uk> wrote:
>[color=green]
>> Michael Wojcik wrote:[color=darkred]
>>> Fine, but there's quite a gulf between "your inability to see
>>> something" and "it's impossible to prove the existence or
>>> nonexistence".[/color]
>> Whether or not you can prove its existence still doesn't affect whether
>> it exists or not.[/color]
>
> Not to get metaphysical, but in point of fact its central.
>[color=green]
>> 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.[/color]
>
> 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.[/color]

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]

Re: File exist


In article <mi7lh3xt0g.ln2 @news.flash-gordon.me.uk>, Flash Gordon <spam@flash-gordon.me.uk> writes:[color=blue]
> Michael Wojcik wrote:[color=green]
> > In article <fiaih3xr2b.ln2 @news.flash-gordon.me.uk>, Flash Gordon <spam@flash-gordon.me.uk> writes:[color=darkred]
> >> Michael Wojcik wrote:
> >>> In article <kuphh3x77a.ln2 @news.flash-gordon.me.uk>, Flash Gordon <spam@flash-gordon.me.uk> writes:
> >>>> I disagree, does not exist and cannot be opened are very different concepts.
> >>> Always? I've seen filesystems where they're indistinguishab le, such
> >>> as steganographic "deniable" filesystems where the proper key is
> >>> required to determine both the existence and contents of a particular
> >>> "file". Without that key, it's impossible to prove the existence or
> >>> nonexistence of the file.
> >> My opinion is that your inability to see something does not change its
> >> existence.[/color]
> >
> > Fine, but there's quite a gulf between "your inability to see
> > something" and "it's impossible to prove the existence or
> > nonexistence".[/color]
>
> Whether or not you can prove its existence still doesn't affect whether
> it exists or not.[/color]

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).
[color=blue][color=green][color=darkred]
> >> 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,[/color]
> >
> > 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.[/color]
>
> 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.[/color]

Simply claiming that does not constitute an argument.
[color=blue][color=green][color=darkred]
> >> 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.[/color]
> >
> > If there's no decision procedure that can distinguish between two
> > conditions, on what basis do you decide those conditions are
> > distinct?[/color]
>
> 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?[/color]

Entirely irrelevant, as I noted above.
[color=blue][color=green]
> > 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.[/color]
>
> So? The information still either exists or does not exist.[/color]

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?
[color=blue]
> Just because
> you or I can't prove whether or not it exists doesn't change that.[/color]

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).
[color=blue]
> Even
> if the key is lost forever the information is still encoded there until
> it is overwritten.[/color]

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

--
Michael Wojcik michael.wojcik@ microfocus.com

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]

Re: File exist


In article <4448DC99.D0B40 02B@spamcop.net >, Kenneth Brody <kenbrody@spamc op.net> writes:[color=blue]
> Michael Wojcik wrote:
> [... "failed to open" vs. "file doesn't exist" ...][color=green]
> > 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.[/color]
>
> 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?[/color]

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.
[color=blue]
> (And, in any case, this is just a "special case" situation, which has
> been designed to purposfully hide such distinctions.)[/color]

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.

--
Michael Wojcik michael.wojcik@ microfocus.com

If Mokona means for us to eat this, I, a gentle person, will become
angry! -- Umi (CLAMP & unknown translator), _Magic Knight Rayearth_

[Walter Roberson]

Re: File exist

In article <e2gklc01qui@ne ws2.newsguy.com >,
Michael Wojcik <mwojcik@newsgu y.com> wrote:
[OT]
[color=blue]
>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.[/color]

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.]
--
"It is important to remember that when it comes to law, computers
never make copies, only human beings make copies. Computers are given
commands, not permission. Only people can be given permission."
-- Brad Templeton

[Andrew Poelstra]

Re: File exist

Walter Roberson wrote:[color=blue]
> In article <e2gklc01qui@ne ws2.newsguy.com >,
> Michael Wojcik <mwojcik@newsgu y.com> wrote:
> [OT]
>[color=green]
>> 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.[/color]
>
> 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.[/color]

It's possible that the key will grow, similar to an autokey cipher,
although more secure.
[color=blue]
> 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.[/color]

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]

Re: File exist

In article <yT43g.66152$7a .42118@pd7tw1no >,
Andrew Poelstra <apoelstra@shaw .ca> wrote:
[color=blue]
>Walter Roberson wrote:[color=green]
>> [OT][/color][/color]
[color=blue][color=green]
>> 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.[/color][/color]
[color=blue]
>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.[/color]

[Going further OT]

I am not a compression expert, but I have studied the subject and
hung around in comp.compressio n 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 "interestin g" 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.
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell

[Michael Wojcik]

Re: File exist


In article <e2gttq$3i8$1@c anopus.cc.umani toba.ca>, roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) writes:[color=blue]
> In article <e2gklc01qui@ne ws2.newsguy.com >,
> Michael Wojcik <mwojcik@newsgu y.com> wrote:
> [OT]
>[color=green]
> >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.[/color]
>
> 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?[/color]

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.

--
Michael Wojcik michael.wojcik@ microfocus.com

I do not care to listen; obloquy injures my self-esteem and I am
skeptical of praise. -- Jack Vance