Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 16 May 2012 01:53:55 +0200
From: magnum <john.magnum@...hmail.com>
To: john-dev@...ts.openwall.com
Subject: Re: RAR early reject

On 05/15/2012 09:05 AM, Milen Rangelov wrote:
> I believe some more clever LZ test should be performed, but I am too
> lazy to dig into the algorithm.

Here is an early description from JimF of what he does in pkzip. I
believe it's not the exact same LZ type but it's very curious reading
anyway:

> Step 3. decrypt 1 more byte.Check bits 1 and 2 (byte & 6). - If the
> check is a 6, then we are done, that is an invalid inflate code type.
> This is a 100% valid check.  NOTHING that has this code can be
> valid. - If the check is a 0, then if the first byte is not 0 or 1,
> then we are done (I am not 100% sure about THIS check, I will have to
> do more research).  If the byte is a 0/1, then read the 2 next 16 bit
> words. If the first is != the second^0xFFFF, then we are done. This
> check catches almost 100%.  Also, this is usually only seen 'for
> real', on files which zip would have stored.  The file 'is' stored,
> but it is done using inflate store blocks (using a zip type 8 blob,
> inflate, and not type 0 store blob).  This was to try to hide
> signatures, but it DOES NOT.  However the check will only let about 1
> out of 65000 through (or actually 1 out of 65000*(2^5), since the top
> 5 bits of the first character have to also be 0. - If the check is a
> 2 (inflate code == 1), then decrypt a block of data using FIXED
> huffman tree, the built in tree data within inflate. I think I use 64
> bytes, but I might shorten this a lot.  Then send this block to my
> own custom code that does deflation 'checking'.  It is looking for
> invalid codes, or reverse lookup that is past the start of the
> buffer.  The code was taken from inf_fast.c and inflate.c in zlib,
> and is significantly cut down. This is the most likely to allow bad
> passwords to 'pass'.  About 1 in 60 slip through. - If the check is a
> 4 (inflate code ==3), then we have a variable huffman tree block.
> Most 'real' zips start with this, (but not all). Also, almost all of
> them that do start with a fixed huff tree, are tiny files (base_64.h
> does, if you compress it).  To decode this, I decrypt 12 bytes
> (that's all that is needed). I then load the sums of the counts of
> huffman codes, and run a 'counting' algorithm' on this.  This is VERY
> quick.  It is also pretty damn good.  Only about 1 out of 330 or so
> pass this simple check. It is fast and good.
> 
> All in all, only about 1 our of 215 candidates which PASS the
> checksum, also pass the 2nd layer testing.  Thus for a zip file with
> 1 file in it that is 1 byte checksum, about 1/(256*215) candidates
> pass these 2 layers of checking 15.7 bits.  For a single file, 2 byte
> checksum, we are about 23.7 bits of validation, or only about 1 out
> of 14 million.

Pretty damn cool. When I read it, I get both encouraged and discouraged,
lol. It can be done, it's just a hell of a task.

magnum

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.