LM hash format: Add test vectors with 8-bit chars

[solardiz]

Our current test vectors in LM_fmt.c don't test FINALIZE_NEXT_KEY_BIT_7 (except that it advances the key bit pointer), so any bugs/miscompile in there may go unnoticed. We should add test vectors to ensure proper code coverage by tests.

[exaghost]

Hi!
Try this from an old Windows XP system. C6A3396B0AEF1EF9AAD3B435B51404EE
cp852 or ?b?b?b?b.

[magnumripper]

Thank you @exaghost, I'll submit a PR with that one.

[solardiz]

Thank you @exaghost and @magnumripper!

Unfortunately, there are two issues:

1. This broke --test-full=0:

Testing: LM [DES 512/512 AVX512F]... FAILED (LM doesn't set FMT_CASE but at least one test-vector is case-sensitive)

2. It appears that we need many more test vectors for LM hashes to reach full "finalize key" code coverage. With this added test vector, the below hack of FINALIZE_NEXT_KEY_BIT_7 is now detected (self-test fails):

+++ b/src/DES_bs_b.c
@@ -549,7 +549,7 @@ typedef unsigned ARCH_WORD kvtype;
        kvtype m = mask80, va, vb, tmp; \
        kvand_shr(va, v0, m, 7); \
        kvand_shr(vb, v1, m, 6); \
-       kvand_shr_or(va, v2, m, 5); \
+       kvand_shr_or(va, vzero, m, 5); \
        kvand_shr_or(vb, v3, m, 4); \
        kvand_shr_or(va, v4, m, 3); \
        kvand_shr_or(vb, v5, m, 2); \

However, similar hacks of FINALIZE_NEXT_KEY_BIT_7 for any other v (0, 1, or 3 to 7) go undetected (self-test passes). I now suspect we might not have 100% coverage for 7-bit chars, either.

[solardiz]

1. This broke --test-full=0:

Oops, I'm wrong about this one. This is actually a result of my hack to FINALIZE_NEXT_KEY_BIT_7, for v0 in this case, which went undetected by --test, but was detected by --test-full=0 in this weird way.

[solardiz]

In my testing, --test-full=1 (or =0) detects force-zero hacks of v0 and v7 (only), whereas --test detects hacks of v2 only. Weird stuff.

I only tested hacks of FINALIZE_NEXT_KEY_BIT_7 so far, and only with vzero (not vones). I suspect we may also be lacking proper test coverage for other key bits and for zero-to-one changes.

[solardiz]

Simply repeating the existing test vectors tens of times in the tests array makes the tests detect far more errors.

I think we have a bug here in formats.c:

        for (i = match - 1; i >= 0; i--) {
                if (format->methods.cmp_one(binary, i))
                        break;
        }

We're satisfied with finding a match for any index, not for the index where we actually expect it. This doesn't explain everything for me (if there's a match for some other index, this suggests key setup for the same key did work correctly at some previous point in the same run), but it may be part of the solution to this puzzle.

[solardiz]

We're satisfied with finding a match for any index, not for the index where we actually expect it.

This logic was first introduced in 89ab0ca by Sayantan, I guess in relation to his work on OpenCL formats with on-device mask and hash comparison. But I don't get exactly why. The code I had in core was meant to also support such cases.

[solardiz]

with on-device mask and hash comparison. But I don't get exactly why.

Oh, I do now. With on-device comparison, the output indices may be in a narrower range, covering only the subset of hashes that matched. So what we may want to do is insist on correct index when match == count or something like that.

[solardiz]

The below still passes all tests on CPU, but unfortunately doesn't make detection of my hacks to FINALIZE_NEXT_KEY_BIT_7 more robust:

+++ b/src/formats.c
@@ -608,9 +608,15 @@ static char* is_key_right(struct fmt_main *format, int index,
                return err_buf;
        }
 
-       for (i = match - 1; i >= 0; i--) {
-               if (format->methods.cmp_one(binary, i))
-                       break;
+       if (match == count) {
+               i = -1;
+               if (format->methods.cmp_one(binary, index))
+                       i = index;
+       } else {
+               for (i = match - 1; i >= 0; i--) {
+                       if (format->methods.cmp_one(binary, i))
+                               break;
+               }
        }
 
        if (i == -1) {

[solardiz]

For now, I am able to achieve robust tests by padding the tests array to 64 entries. But longer-term, we should adjust the way we run tests, so that large test vector arrays would not be necessary for coverage. We probably also have this problem for other formats that use bitslice DES, but at least now we'll catch errors in the common FINALIZE_NEXT_KEY_BIT_* macros when LM tests are run.