DOS ain't dead - CRITICAL OFF-by-32-KiB-BUG

DOS386

27.03.2013, 09:10

CRITICAL OFF-by-32-KiB-BUG (Users)

There is an "interesting" random BUG occurring rarely (maybe cca 1% per 100 MiB processed) when decompressing encrypted 7-ZIP archives. In the output file, a 4 MiB block is off by 32 KiB like this:

POSITION GOOD BAD -------- ---- --- x - 12 MiB meh999(32 KiB) meh999(32 KiB) (OK, but see below) x - 32 KiB meh888(32 KiB) meh888(32 KiB) (OK) x (16 MiB aligned) meh0(32 KiB) meh1(32 KiB) (lost 32 KiB block !!!) x + 32 KiB meh1(32 KiB) meh2(32 KiB) (off by 32 KiB) x + 64 KiB meh2(32 KiB) meh3(32 KiB) (off by 32 KiB) ... ... ... ... x + 4 MiB - 64 KiB meh126(32 KiB) meh127(32 KiB) (off by 32 KiB) x + 4 MiB - 32 KiB meh127(32 KiB) meh999(32 KiB) (repeating old stuff !!!) x + 4 MiB meh777(32 KiB) meh777(32 KiB) (OK)

Actually it's the same BUG I had already reported some 1'000'000's years ago and suspected it to be a FreeDOS BUG. Recently I could reproduce it 2 more times with EDR-DOS and 7-ZIP 9.20, so

- The good news is that it is NOT a FreeDOS BUG :-)

- The malicious news is that there is a critical BUG in 7-ZIP or HX :-(

Maybe it's related to the other random 7-ZIP rarely occurring (with same probability?) BUG during creation of encrypted 7-ZIP archives raising a Page Fault in Ring0.

7-ZIP brews a broken output file and boasts "Everything os OK". So either the CRC32 check is broken ("condition is always true", of course the bad file has a bad CRC32 too) or the BUG occurs "between" the CRC32 check and writing the data into the filesystem (note: cluster size was 4 KiB, not 32 KiB). But extracting again the very same way gives a good file.

It's unknown whether the BUG also occurs:

- If the archive isn't encrypted
- In Windaube
- With all those DGJPP ports of 7-ZIP (or at least those that do run at all)

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***

RayeR

CZ,
28.03.2013, 02:16

@ DOS386

CRITICAL OFF-by-32-KiB-BUG

Post reply

Can you make a simple test package with archive so someone lece could try to reproduce it at same input but different OS/system?

---
DOS gives me freedom to unlimited HW access.

DOS386

29.03.2013, 09:26

@ RayeR

CRITICAL OFF-by-32-KiB-BUG

Post reply

TYPO: "Everything os OK" -> "Everything is OK"
NOTE: Used 4.65 to create the archives, and 4.42, 4.65 and 9.20 to extract.

> Can you make a simple test package with archive

Thanks for caring ... but:

1. The affected archives are cca 100 MiB to 1 GiB and full of sensitive and unredistributable stuff ... bad idea to send them around :-(

2. The problem most likely is NOT related to the archive content ... fortunately ( :-\ ) ... but random

... so encrypt 7-ZIP anything (one single TAR or similar file) bloated (Firefox source, CD or DVD images, Windows (XP or older, newer would be > 2 GiB) backups, ...) and try to extract, and check CRC32 or MD5 of result. Unfortunately, 2 or 3 attempts are a bit insufficient, rather at least 100 attempts would be needed to get a "good chance" to reproduce this (and then you have to compare by content the 2 several 100 MiB files to see the OFF-by-32-KiB-BUG).

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***

RayeR

CZ,
29.03.2013, 11:02

@ DOS386

CRITICAL OFF-by-32-KiB-BUG

Post reply

OK, so to sumarize test conditions:
* problem is in decompression routine
* file must be password protected
* file must be quite large
* decompression must be done many times until error occur
* bug is not dependent on file content or password (length)?
To test do some repeated decompression, md5sum, comparison...
Did you tried under different OSes?

---
DOS gives me freedom to unlimited HW access.

DOS386

29.03.2013, 11:19

@ RayeR

CRITICAL OFF-by-32-KiB-BUG

Post reply

> OK, so to sumarize test conditions:
> * problem is in decompression routine

Right ... there is another problem (also rare and random) with compression too (Page Fault in Ring0) 2011-07-03

> * file must be password protected

Possibly (not yet observed without)

> * file must be quite large

Right

> * decompression must be done many times until error occur

Right :-(

> * bug is not dependent on file content or password (length)?

Most likely. AFAIK 7-ZIP does 2^19 of SHA256 hashes anyway, so any (length) PWD ends up in a 256-bit key :-)

> To test do some repeated decompression, md5sum, comparison...

Right ... like repeatedly throw 4 dices and wait for (6,6,6,6).

> Did you tried under different OSes?

FreeDOS and EDR-DOS.

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***

DOS386

31.03.2013, 17:42

@ DOS386

CRITICAL OFF-by-32-KiB-BUG (threads)

Post reply

As Igor revealed, the LZMA algo needs 2 threads compression but only 1 for decompression ... but if the archive is encrypted, there will be an additional thread in both cases ... so I suspect a HX threading vulnerabibility to be the source of the problem, and it would NOT affect archives that are not encrypted then.

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***

RayeR

CZ,
03.04.2013, 12:35
(edited by RayeR, 03.04.2013, 13:16)

@ DOS386

CRITICAL OFF-by-32-KiB-BUG (threads)

Post reply

I made a test of 7za DOS version that I use:7-Zip (A) 9.20 Copyright (c) 1999-2010 Igor Pavlov 2010-11-18 p7zip Version 9.20 (locale=C,Utf16=off,HugeFiles=off,1 CPU)under Windows XP.
I compressed 2,5GB ISO image with 11-chars password and then decompressed it 80-times using this password (-p) to different files. Then I ran MD5sum over all files, cat to one file and see there is no difference. So with this version/conditions I cannot reproduce the bug.

---
DOS gives me freedom to unlimited HW access.

Zyzzle 04.04.2013, 04:17 @ RayeR	CRITICAL OFF-by-32-KiB-BUG (threads) Post reply
	How did you get past the 2GB limit of DJGPP? I guess a Win32 environment allows for 4GB - 1 file length? Your test - which must have taken a LONG time - shows your dedication to the task! Thanks for doing it.

RayeR

CZ,
04.04.2013, 13:51

@ Zyzzle

CRITICAL OFF-by-32-KiB-BUG (threads)

Post reply

> How did you get past the 2GB limit of DJGPP? I guess a Win32 environment
> allows for 4GB - 1 file length?

It's probably supported since djgpp 2.04 (I use updated version of libc by author of DOS Hexen), I saw there are some 64bit file pointers. When it run under DOS it's limited but under XP it can reach >2GB and maybe >4GB (on NTFS).

> Your test - which must have taken a LONG time - shows your dedication to
> the task! Thanks for doing it.

Yes, but I have a quadcore machine at work that is boring for most of the time so I could run this heavy task without discomfort. It took about a half of a day... :)

I don't remember where I exactly got this 7zip version but it was probably announced in this forum. I prefer to run DOS native programs under DOS instead of using HX when I can choose both versions :)

---
DOS gives me freedom to unlimited HW access.

DOS386

04.04.2013, 04:37

@ RayeR

CRITICAL OFF-by-32-KiB-BUG (threads)

Post reply

> I made a test of 7za DOS version that I use:> 7-Zip (A) 9.20 Copyright (c) 1999-2010 Igor Pavlov 2010-11-18 > p7zip Version 9.20 (locale=C,Utf16=off,HugeFiles=off,1 CPU) >under Windows XP.
> I compressed 2,5GB ISO image with 11-chars password and then decompressed
> it 80-times

I suspect the BUG to be related to the HX threading ... (you tested the DGJPP threading ... well seems to work ... in XP :-| ) ... maybe I'll start using this (where did you get it? http://www.freedos.org/software/?prog=7-zip NOT up to date) DGJPP version too to see if I get the BUG one day or not ...

> How did you get past the 2GB limit of DJGPP?
> I guess a Win32 environment allows for 4GB - 1 file length?

AFAIK FreeDOS has a 2 GiB limit but DGJPP doesn't ... IIRC I successfully downloaded a 21 GiB file using DGJPP WGET some years ago :-)

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***

Rugxulo

Usono,
05.04.2013, 19:15

@ DOS386

CRITICAL OFF-by-32-KiB-BUG

Post reply

(quoting Eric Auer):

> I just had an idea ... what if a pointer or counter is updated in a
> non- atomic way where some block count or the upper N bits could get
> updated concurrently while multi-threading, somehow skipping 32 k of data?

I don't know all the details. LZMA2 is supposed to be better for multithreaded compression. Not sure about decompression, IIRC it sounded like it only normally used like maybe two threads, one for I/O and one for disk writes.

EDIT:
LZMA2 ... Better multithreading support. If you compress big file, LZMA2 can split that file to chunks and compress these chunks in multiple threads. LZMA2 uses: 1 thread for each chunk in x1 and x3 modes; and 2 threads for each chunk in x5, x7 and x9 modes. If LZMA2 is set to use only such number of threads required for one chunk, it doesn't split stream to chunks. So you can get different compression ratio for different number of threads. You can get the best compression ratio, when you use 1 or 2 threads.

(LZMA2 is default in latest alphas, but I think all our older versions default to original LZMA only.)

Maybe "-mtt" can configure how many threads, dunno, lemme check docs ...

(from p7zip_9.20.1/DOCS/MANUAL/switches/method.htm): mt=[off | on | {N}] Sets multithread mode. If you have a multiprocessor or multicore system, you can get a speed increase with this switch. This option affects only compression (with any method) and decompression of BZip2 streams. Each thread in the multithread mode uses 32 MB of RAM for buffering. If you specify {N}, 7-Zip tries to use N threads.

EDIT: Apparently this actually means "-mmt=whatever". Try "7za b -mmt=2" on a four-core machine, etc. etc.

Dunno if the docs are truly consistent with latest code. But, if any of you can reliably reproduce the failure (and please mention which OS build and version and which HX version and which OS tested and similar stats), please try again with "-mmt=off" or similar. (And of course report bugs to Igor Pavlov or p7zip dude "myspace" on SourceForge.)

DOS386

10.04.2013, 12:00

@ Rugxulo

CRITICAL OFF-by-32-KiB-BUG | Eric | LZMA2

Post reply

(quoting Eric Auer):

> I just had an idea ... what if a pointer or counter is updated in a
> non- atomic way where some block count or the upper N bits could get
> updated concurrently while multi-threading, somehow skipping 32 k of data?

yeah ... I still suspect HX threading ... one is already confirmed: BUG

> I don't know all the details. LZMA2 is supposed to be better for
> multithreaded compression. Not sure about decompression

My archives causing the BUG were all created with 4.65 and LZMA1.

LZMA2 AFAIK should prevent excessive expansion on poorly compressible or incompressible data, apart from quad-core support not available in DOS anyway.

> When it run under DOS it's limited but under XP it can reach >2GB and maybe
> 4GB (on NTFS)

I got 21 GiB under EDR-DOS on FAT :-) Anyway, I suspect that under XP the thread/interrupt hazard might NOT be able to occur the same way as it does in DOS.

---
This is a LOGITECH mouse driver, but some software expect here
the following string:*** This is Copyright 1983 Microsoft ***