-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256
Robert J. Hansen wrote:
> Alphax wrote:
>
>>attributes, should it not be possible to re-generate
a file (even if it
>>were brute-forced) if you had enough of these pieces
of information?
>
>
> The answer can be found in Claude Shannon somewhere.
The formal proof
> is worth skipping; let's just talk about compression
instead.
>
> Take a 128-bit hash. By definition, it can't have
more than 128 bits of
> entropy. If the file is larger than this--let's say
it's a book, which
> in ASCII can easily fit in 50k of compressed file--then
you're going to,
> by Dirichlet's Box Principle [1], have multiple
different files which
> will redact down to the same hash value. What you're
asking is, if we
> know certain bits of information in addition to this
hash value, can we
> isolate down precisely what the original file was?
>
> If we want to recreate those 400,000 bits of data, then
we're going to
> need another 399,878 bits of information. If we know
that all our files
> are less than 2**32 bytes in size, then by knowing the
size of our file
> we've got 32 bits of additional information--only
399,846 bits to go!
>
> So the short version: no. The long version: only if
you're _really_
> bored and have _lots_ of additional information.
>
> Now, whether you could come up with a set of _likely_
messages... that's
> a different question, and possibly a much more
interesting one. Haven't
> thought much about it.
>
There are two things which I'm thinking /might/ be helpful:
- - Some hash algorithms are "broken"; it is
possible to generate the
inputs for a given input (of a given size), reducing the
number of
"possible" inputs by some amount - I'm guessing
by the size of the hash.
So even though there are still however many milllion
possible files with
that filesize, how many /also/ have that particular hash
value for that
particular algorithm?
- - What if we have two hash values from different
algorithms? Three?
Four? N? Does this make it any easier?
- --
Alphax | /"\
Encrypted Email Preferred | \ / ASCII Ribbon
Campaign
OpenPGP key ID: 0xF874C613 | X Against HTML email
& vCards
http://tinyurl.com/cc9up
| / \
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3rc1: (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iQEVAwUBQ/sFpbMAAH8MeUlWAQgnEwf+KzRRIB74lEJPXr3Hgy05CYQkLktV
0oRo
mS1T7gnYiJ2BgnvsBBzj+nWcmPnIh7f5m8MZ5Sj26aA0FnORyXCsYo+i9hlI
6Ahd
kMDDQvA/GnuoqzRf4SzX8mKeNbqSvEkjV/Zin/kS92XuWLQrIOB/5jQbN/+j
RWum
KAEPJ2OMH8rWUQyeVFxv3Sku6gZoPlecUYGmmoSonwDLYdbVtp9oEnwS8lNI
vGi2
QHohQnwAkkBC4/PMdwZLAtpTJaUQRJDPUotcOOlLMAdwxOlragFBdyHVSRi7
fUvp
NZms6N4z/gXjHn2XX/Dcr6SEz6g9vwXOaxYZkRHbTddertlzjtHCNQ==
=isLS
-----END PGP SIGNATURE-----
____________________________________________________________
__
Archives: htt
p://groups.yahoo.com/group/PGP-Basics/messages
OT List: http://gr
oups.yahoo.com/group/PGP-Basics-OT
OT Subscribe:
mailto:PGP-Basics-OT-subscribe@yahoogroups.com
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://grou
ps.yahoo.com/group/PGP-Basics/
<*> To unsubscribe from this group, send an email to:
PGP-Basics-unsubscribe@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.c
om/info/terms/
|
Suppose I want to move a file somewhere, but it's either
too big or
there are other "limiting factors" (you can use
your imagination here).
Since I have a copy of the file, I can find out (and tell
anyone who
enquires):
- - The exact size of the file, in bytes
- - The hash value of the file, using any hash algorithm for
which there
is software available for me to use
- - The value of a byte in the file at any offset
Given that there exist several "broken" hash
algorithms (and possibly
even despite this fact), and the fact that there are a
finite number of
possible files which would have the same given values for
all of these
attributes, should it not be possible to re-generate a file
(even if it
were brute-forced) if you had enough of these pieces of
information?
More importantly, should it be possible to do so and require
*substantially* less information in terms of bytes required
for the
message vs. the size of the file?
- --
Alphax | /"\
Encrypted Email Preferred | \ / ASCII Ribbon
Campaign
OpenPGP key ID: 0xF874C613 | X Against HTML email
& vCards