possible DoS attack against PAR2 clients

[BlackIkeEagle]

This is a forwarded issue from multipar

check if the problem exists in par2cmdline and fix if needed

--- refer start ---

This is an important update to fix a rare (but fatal if happen)
problem.
When data of source file is almost same or sparce,
finding slices happened to be very slow ...
almost impossible for large data size.
This is categolized as hash collision problem.

PAR2 uses two hash algorithms (CRC-32 and MD5) to detect slices.
CRC-32 is used to locate a slice, because MD5 is slow.
When there are some slices of same contents (both CRC-32 and MD5 are
same),
detection by CRC-32 happens many times for same data.
It requires MD5 calculation for the slice everytime,
and verification becomes very slow.
For example, if all file data bytes are 0,
hash from all offset matches hash of a slice.
To avoid this "too many detection problem",
par2cmdline and QuickPar skip a range of a found slice.
Because MultiPar tries to find more complete slices than QuickPar,
MultiPar was freezed in this case.

When there are some slices of same CRC-32 (but different MD5),
miss-detection by CRC-32 happens many times for same data.
From the restriction of 32-bit checksum, miss-detection can happen,
but the frequency is low.
When number of blocks is 32768, miss-detection may happen only 1 time
per 128KB.
Because the chance of CRC-32 collision is very low normally,
most PAR2 clients don't avoid it.
As nobody reported this kind problem after PAR2 was public,
users don't need to care the risk in general usage.
Anyway I implemented a feature to count the frequency of miss-
detection,
and par2j.exe will avoid freeze in most case.

I made a sample data set to test behavior in this collision problem.
There are only 4 blocks in a 2MB file.
Because I changed first 2 bytes as a damage,
a PAR2 client should detect 3 complete blocks from the damaged file.

2mb_0s.bin : This is a sample of sparce data. Bytes are almost 0.
par2cmdline and QuickPar find only 2 blocks.
Old MultiPar was freezed, but will find 3 blocks after many minutes.
New MultiPar finds 3 blocks.

2mb_col.bin : This is a sample of checksum collision of every byte.
par2cmdline and QuickPar are freezed, but find only 1 block after
several minutes.
Old MultiPar was freezed, but will find 3 blocks after many minutes.
New MultiPar finds 3 blocks.

pattern16.bin : This is a sample of checksum collision per 16-bytes.
par2cmdline and QuickPar are freezed, but find only 2 blocks after a
few minutes.
Old MultiPar was freezed, but find 3 blocks after several minutes.
New MultiPar finds 3 blocks.

If you want to check your using PAR2 client, set of "pattern16.bin"
is faster to finish.
If your PC is slow, the freeze period may become longer.
I'm not sure this problem can be used for DoS attack against
automated PAR2 usage.
If someone has a skill to forge CRC-32,
it is possible to make a set of source file and PAR2 file,
which freeze a PAR2 client for several hours.
But, the malicious file data has continual short pattern,
and human being can recognize the oddness with ease.
Also, developer can solve the problem, like I did.

--- refer end ---

[eMPee584]

[side note.. ⛵
ah co0l.. so Mr Sawada set up a proper website and respects the GPL: http://multipar.eu/source
good you are watching that one. Is there any notable functionality in his so-called PAR3-implementation lacking in current par2cmdline?]

[BlackIkeEagle]

par3 is similar to par2, but has some advantages

it has smaller headers and uses another technique to create recovery files
this results in smaller recovery files for the same % of recoverable data

[BlackIkeEagle]

the sollution offered is not perfect but it will avoid a massive slowdown

it could in some cases give false positives of missing blocks

[Yutaka-Sawada]

I found that this issue was not solved in recent version. But, the problem had been solved at year 2014. So, something change might happen to remove the solution.

I put the sample set of PAR2 files and source files (testCollision_2014-05-06.zip) in "Tool" folder on OneDrive. They are same as old data set, which were refered in the first post. par2cmdline v0.8.1 fails (freeze) at verifying these three cases.