Re: Don Knuth - Uncompressable sequences

tan_steve@xxxxxxxxx wrote:
Algorithmically, is it not possible that there exists an oracle, that
given a sha or other hash of the input sequence, can predict or
reconstruct the original sequence regardless of the length of the
original sequence?

No. There only exists 2^160 sha1 hashes. Under the assumption that it produces as few collisions as possible, you would only be able to identify the 2^160 unique 20 byte files. Even if you specified the length (and assuming that the sha1 hash was uniformly distributed), you would have 256 possible matches for a 21 byte file with a particular sha1 hash, 65536 for a 22 byte file, etc.

Despite what the internet says, Bruce Schneier does not see sha1 as an invertible compression algorithm. :)

- Josiah
.

Relevant Pages

  • Re: Don Knuth - Uncompressable sequences
    ... reconstruct the original sequence regardless of the length of the ... length (and assuming that the sha1 hash was uniformly distributed), ... sha1 hash, 65536 for a 22 byte file, etc. ... compression algorithm the universe is using that is causing that small ...
    (comp.compression)
  • Re: File Hashing
    ... Are you a programmer at all? ... definitely off-topic in the VB.NET newsgroup, ... Two different files will NEVER have the same hash value? ... SHA1 hash value? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: API to access loaded assembly hash
    ... > same way as the strong name public key used in evidence. ... here is how to get the sha1 hash. ... >>> Dominick Baier - DevelopMentor ...
    (microsoft.public.dotnet.security)
  • SHA1 Hash question with large Files
    ... I guess I don't fully understand how a SHA1 hash value is calculated ... the large file, passing it to a byte array, and passing the byte array ... Does this load the entire file into main memory ...
    (microsoft.public.dotnet.languages.csharp)