Bug#781568: libfuzzy2: incorrect comparison when comparing digests from relatively simple files

[Tsukasa #01 (OI)]

Package: libfuzzy2
Version: 2.12-1
Severity: important
Source: ssdeep
Tags: patch jessie

Dear Maintainer,

While I'm reviewing ssdeep source code as a new ssdeep developer,
I found several bugs including this. Because of this bug's severity and
Debian's freeze policy on Jessie, I want this bug to be reviewed and if
it's considered as RC, I'd like to contribute targeted patch to fix this
particular bug.

[TECH BACKGROUND]

A ssdeep digest consists of three parts:

* Block size
* First substring
* Second substring

For instance, "3:ubvcl+nz:uTcknzbn" can be splitted like this:

* Block size (3)
* First substring ("ubvcl+nz")
* Second substring ("uTcknzbn")

[BUG]

The bug is in fuzzy_compare function which will be used to compare
digests. This function is supposed to return 100 if given digests are
identical. However, this function actually returns 100 if the block size
and the first digest substring are identical. This means, even if second
digest substring is not identical, fuzzy_compare considers it is.

[REPRODUCTION]

I attached two files to reproduce this issue easily
(file1.gz and file2.gz).

| $ ssdeep -V
| 2.12
| $ /path/to/ssdeep-2.13-rc/ssdeep -V
| 2.13
| $
| $ gzip -d file1.gz
| $ gzip -d file2.gz
| $
| $ ssdeep -l file1 file2 | tee files.ssdeep
| ssdeep,1.1--blocksize:hash:hash,filename
| 3:urNZHi:0/C,"file1"
| 3:urNZHi:uJp,"file2"
| $
| $ ssdeep -a -k files.ssdeep -x files.ssdeep
| files.ssdeep:file1 matches files.ssdeep:file2 (100)
| files.ssdeep:file1 matches files.ssdeep:file2 (100)
|
| files.ssdeep:file2 matches files.ssdeep:file1 (100)
| files.ssdeep:file2 matches files.ssdeep:file1 (100)
|
| files.ssdeep:file1 matches files.ssdeep:file2 (100)
| files.ssdeep:file1 matches files.ssdeep:file2 (100)
|
| files.ssdeep:file2 matches files.ssdeep:file1 (100)
| files.ssdeep:file2 matches files.ssdeep:file1 (100)
|
| $ /path/to/ssdeep-2.13-rc/ssdeep -a -k files.ssdeep -x files.ssdeep
| files.ssdeep:file1 matches files.ssdeep:file2 (0)
| files.ssdeep:file1 matches files.ssdeep:file2 (0)
|
| files.ssdeep:file2 matches files.ssdeep:file1 (0)
| files.ssdeep:file2 matches files.ssdeep:file1 (0)
|
| files.ssdeep:file1 matches files.ssdeep:file2 (0)
| files.ssdeep:file1 matches files.ssdeep:file2 (0)
|
| files.ssdeep:file2 matches files.ssdeep:file1 (0)
| files.ssdeep:file2 matches files.ssdeep:file1 (0)
|
| $

As you can see, "file1" and "file2" digests are different
("3:urNZHi:0/C" and "3:urNZHi:uJp") but the block size and the first
substring are identical. Because ssdeep don't compare short substrings
(to prevent exaggrations), comparison should result in mismatch (0).
However, ssdeep 2.12 considers these digests are identical because of
the bug and results in complete match (100).

[SEVERITY]

Since it affects reliability of digest match and clustering features (I
mean most of ssdeep features) and this software is used for security
purposes, it may be release critical on Jessie.

[UPSTREAM]

Please note that this bug is fixed in version 2.13 RC and the new
release, version 2.13 will be released in a few weeks.



-- System Information:
Debian Release: 8.0
  APT prefers testing-updates
  APT policy: (500, 'testing-updates'), (500, 'testing')
Architecture: amd64 (x86_64)

Kernel: Linux 3.16.0-4-amd64 (SMP w/8 CPU cores)
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash
Init: systemd (via /run/systemd/system)

Versions of packages libfuzzy2 depends on:
ii  libc6              2.19-15
ii  multiarch-support  2.19-15

libfuzzy2 recommends no packages.

libfuzzy2 suggests no packages.

-- no debconf information

-------------- next part --------------
A non-text attachment was scrubbed...
Name: fix-simple-digest-comparison.patch
Type: text/x-diff
Size: 1355 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/forensics-devel/attachments/20150331/a4ff56e8/attachment-0001.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: file1.gz
Type: application/octet-stream
Size: 92 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/forensics-devel/attachments/20150331/a4ff56e8/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: file2.gz
Type: application/octet-stream
Size: 91 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/forensics-devel/attachments/20150331/a4ff56e8/attachment-0003.obj>