Matt Mahoney wrote:
> John McCarten wrote:
> > maud wrote:
> > > Matt Mahoney wrote in part:
> > >
> > > > Here is an easier problem. I generate one 8 MB file and post it. You
> > > > compress it and post an archive containing the compressed file and a
> > > > decompression program, such that the archive is at least one byte
> > > > smaller than the file I post. Follow the rules of
> > > > http://mailcom.com/challenge/ for creating the archive and decompressor
> > > > (substituting the test file for the Calgary corpus).
> > > > ...
> > > > To make it easier still, I will tell you how I will create the test
> > > > file. I will use the program sharnd.exe to create it.
> > > > ...
> > If you look at the rules for the challenge you will see an important
> > element missing for challenges such as the one proposed. There is no
> > time limit.
> I am patient.
Yes. Me too. One often has to wait patiently for a bite. I only got one
bite, from BR, but that's the way it sometimes goes when fishing
> > The second thing is that the challenge file is to be created by sharnd.
> > The source code of which has been made available.
> So the problem ought to be easy.
True. Lucky for me the source was available. I would have been in
serious trouble otherwise.
> After einstein gives up
You may be in for a long wait, but as you've said
> I'll post a
> decompressor under 30 KB just to prove it can be done.
This will be definitely be worth seeing. I won't be calling tho'. I
will be safely out of harm's way, sitting on the rail, when you play
> > Now some readers will already have clicked where this is going, but I
> > will continue.
> > loop through all possible values of secret key
> > compare the sharnd output to the challenge file
> > stop when match found else continue
> > The decompressor is a modified version of sharnd itself with the
> > matching key and the 8MB length value embedded.
> > The length that meets the challenge is length(modifiedsharnd).
> > Now, it might take a while to find the key but hey! thats combinatorics
> > for you.
> > john.
> That's the obvious solution.
> Also, there are known weaknesses in SHA-1
> (2^69 resistance to collisions), but I'm not too concerned.
My only concern is that I probably wouldn't be around when the key was
> -- Matt Mahoney