search

openwall / john

John the Ripper jumbo - advanced offline password cracker, which supports hundreds of hash and cipher types, and runs on many operating systems, CPUs, GPUs, and even some FPGAs
https://www.openwall.com/john/
9.63k stars 2.04k forks source link

hmac-MD5 fails on some builds for long salt. #2059

Closed magnumripper closed 8 years ago

magnumripper commented 8 years ago

After e7fb92eeb

../run/john -test-full=0
Testing: HMAC-MD5 [password is key, MD5 128/128 SSE2 4x3]... 
/base/JohnTheRipper/src/CircleCI-MinGW.sh: line 126: 15717 Segmentation fault      (core dumped)

I can't reproduce. I've tested with and without SIMD, OpenMP and --test-full in all combinations.

frank-dittrich commented 8 years ago

Could we try to temporarily build a legacy debug build, and run it with

echo -e -n "run --test=0\nbt\nquit\ny\n" | gdn ./john

Then we would be able to see a back trace of the crash. May be there's a clue.

frank-dittrich commented 8 years ago

On my Linux system, I get

(bleeding-jumbo)run $ ./john --test=0 --format=cpu-dynamic|LC_ALL=C grep -v -C1 PASS
Testing: HAVAL-256-3 [32/64]... PASS
Testing: HMAC-MD5 [password is key, MD5 128/128 SSE2 4x3]... FAILED (cmp_all(1) 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789#050a9de
(bleeding-jumbo)run $ ./john --list=build-info 
Version: 1.8.0.6-jumbo-1-2036-ge7fb92e
Build: linux-x86-64
SIMD: SSE2, interleaving: MD4:3 MD5:3 SHA1:1 SHA256:1 SHA512:1
$JOHN is ./
Format interface version: 13
Max. number of reported tunable costs: 3
Rec file version: REC4
Charset file version: CHR3
CHARSET_MIN: 1 (0x01)
CHARSET_MAX: 255 (0xff)
CHARSET_LENGTH: 24
SALT_HASH_SIZE: 1048576
Max. Markov mode level: 400
Max. Markov mode password length: 30
gcc version: 5.3.1
GNU libc version: 2.21 (loaded: 2.21)
Crypto library: OpenSSL
OpenSSL library version: 0100010bf
OpenSSL 1.0.1k-fips 8 Jan 2015
GMP library version: 6.0.0
Regex library version: 1.3  (loaded: 1.3.1)
File locking: fcntl()
fseek(): fseek
ftell(): ftell
fopen(): fopen
memmem(): JtR internal
frank-dittrich commented 8 years ago

A legacy linux-x86-64-avx build fails in the same way.

frank-dittrich commented 8 years ago

Could we try to temporarily build a legacy debug build, and run it with

echo -e -n "run --test=0\nbt\nquit\ny\n" | gdb ./john

Then we would be able to see a back trace of the crash. May be there's a clue.

jfoug commented 8 years ago

The core is on this test in the mingw script:

now testing a 32 bit SSE2 build

So looking in the circleci-mingw.sh build script, I find this line:

JOHN_CFLAGS=-m32 JOHN_ASFLAGS=-m32 JOHN_LDFLAGS=-m32 make -f Makefile.legacy -sj4 linux-x86-sse2

So this is the build that is getting the core dump. Let me check this out on my fedora-32bit VM and see if it crashes there.

jfoug commented 8 years ago

When built/run under 32 bit Fedora, I get a FAILED (cmp_all(1)). With -verb=4 it is the new hash that failed.

Now starting a test under 64 bit fedora. (had to edit makefile.legacy to comment out the GMP which I only have 64 bit installed)

Now on 64 bit (building with -m32), I get the core dump.

jfoug commented 8 years ago

It is crashing on line 225 in simd-intrinsics.c

The call stack is:

simd-intrinsics.c:225 hmacMD5_fmt_plug.c:425 bench.c:525

So the call from 

             SIMDmd5body(cur_salt->salt[i],
                    (unsigned int*)&crypt_key[index * PAD_SIZE],
                    i ? (unsigned int*)&crypt_key[index * PAD_SIZE] :
                    (unsigned int*)&prep_ipad[index * BINARY_SIZE],
                    SSEi_MIXED_IN|SSEi_RELOAD|SSEi_OUTPUT_AS_INP_FMT);

just after the salt for loop is the one causing the crash. Looks like buffers are probably pointing past ed of allocation or something. I am not good with linux debugging, so I can't give much more insight than this.

But has been shown, it IS giving cmp(1) failures on other builds, so something is wrong with the code.

jfoug commented 8 years ago

Ok, on the one that crashes, this pointer: cur_salt->salt[i] is not SIMD aligned (I can test with VC 32bit, it crashes there also). Now just have to figure out WHY it is not properly aligning on 32 bit builds.

jfoug commented 8 years ago

This is a BUG in core code!!! a8a23fc I am not sure the hmacMD5_fmt_plug.c change was actually 'needed', but it does not hurt. The bug was in bench.c !!! Not sure how this has never bitten us before!!!

jfoug commented 8 years ago

Well, that did not work. Reverting to mem_alloc_tiny and removing the MEM_FREE. That works fine. cd98df1

NOTE, there may still be problems with the format (we were seeing some cmp(1) failures). This fixx was in benchmark code, NOT in ST code. This fix solves 32-bit the CRASH problem, but I am not sure about the ST.

Nope, the cmp(1) failure is still there for hmacMD5 format. But the crash is now gone.

frank-dittrich commented 8 years ago

I guess changing hmacMD5_fmt_plug.c was needed, because on my Raspberry Pi 2 (linux-gnueabihf 32-bit NEON-ac OMP build) I got a warning about salt() returning a misaligned pointer, followed by a failed cmp_all(43) for HMAC-MD5. For HMAC-SHA256, I got the same warning, but the self test passed. I'll repeat the test with the latest commit.

jfoug commented 8 years ago

I am still getting failures on hmac-md5. BUT it is no longer crashing on 32 bit SIMD builds, like it was. I am not sure HOW that bug in bench lived for as long as it did. Bad bug.

The align warning should be corrected with the JTR_ALIGN statement. We may need the same thing on other hmac hash formats for SIMD builds.

frank-dittrich commented 8 years ago

Yes, warning for HMAC-MD5 now gone, but format still fails on ARM NEON. Warning for HMAC-SHA256 still exists (as expected).

frank-dittrich commented 8 years ago

Argh. HMAC-SHA1: no warning. The warnings were for HMAC-SHA256.

jfoug commented 8 years ago

Circle-CI seems happy now, BUT I am getting a FAILED (cmp_all(1)) on a real linux-32 bit SIMD build, so there still is something not right about the hash. It may be where SIMD_PARA > 1 I am pretty sure circle-ci's biuld gets para 1 and my VC build is para1 and it passes ST just fine.

magnumripper commented 8 years ago

Hmm we should have the very same problem in HMAC-SHA256 which got this feature a while ago.

jfoug commented 8 years ago

Found a bug (pair of them) in both formats. But this still does not fix the problem.

https://github.com/magnumripper/JohnTheRipper/commit/13f8193f2eb2a6a22a2a4abe4f7049878da7a993 https://github.com/magnumripper/JohnTheRipper/commit/3c2d7b4c8cfa590de4b79d90b8c2684440b117f8

This bug would only impact salts which were salt_len%64==55 But if the salt was max length, then it was a core, since we were processing 1 buffer past where we have allocated.

But this does not fix the underlying hmacMD5 failures on certain builds.

jfoug commented 8 years ago

I am pretty sure there is a problem here:

        SIMDmd5body(cur_salt->salt[i],
                    (unsigned int*)&crypt_key[index * PAD_SIZE],
                    i ? (unsigned int*)&crypt_key[index * PAD_SIZE] :
                    (unsigned int*)&prep_ipad[index * BINARY_SIZE],
                    SSEi_MIXED_IN|SSEi_RELOAD|SSEi_OUTPUT_AS_INP_FMT);

I have been working with it, trying to find the right bits to use.

        if (i)
        SIMDmd5body(cur_salt->salt[i],
                    (unsigned int*)&crypt_key[index * PAD_SIZE],
                    (unsigned int*)&crypt_key[index * PAD_SIZE],
                    SSEi_MIXED_IN|SSEi_RELOAD_INP_FMT|SSEi_OUTPUT_AS_INP_FMT);
        else
        SIMDmd5body(cur_salt->salt[i],
                    (unsigned int*)&crypt_key[index * PAD_SIZE],
                    (unsigned int*)&prep_ipad[index * BINARY_SIZE],
                    SSEi_MIXED_IN|SSEi_RELOAD|SSEi_OUTPUT_AS_INP_FMT);

Made no progress yet, but I am pretty sure this needs adjustment of some kind.

The size of crypt_key and prep_ipad are different. There is no way we can use them interchangeably and get away with it.

jfoug commented 8 years ago

Ok, I hope this fixes it: 2084425

jfoug commented 8 years ago

I am going to do some rand salt length input files for jtrts.pl for hmac-md5 and hmac-sha256 to make sure things are 'fixed' properly. But I think it is fixed now with the bugs found.

jfoug commented 8 years ago

Ok, I did the same thing for hmac-sha256 0289996 . That format 'may' have worked before. What it was doing was using crypt_out in 2 different manners, so I am not sure it was working properly EVER (we just got lucky with the limited ST vectors in the format).

Now, it keeps crypt_out in INPUT format all the way.

jfoug commented 8 years ago

I am going to get some jtrts.pl files build for arbitrary length salts (0 to max), and run against new versions, then run against prior versions.

jfoug commented 8 years ago

Ok, after making rand length salt input test, here are results

Current fixed code

$ ./jtrts.pl hmac-sha256
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2056-g8e47f6b+ OMP [cygwin 64-bit AVX-ac]
--------------------------------------------------------------------------------
form=hmac-sha256                  guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmac-sha256              guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

form=hmac-sha256                  guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmac-sha256              guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

$ ./jtrts.pl hmac-md5
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2056-g8e47f6b+ OMP [cygwin 64-bit AVX-ac]
--------------------------------------------------------------------------------
form=hmacMD5                      guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmacMD5                  guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

form=hmac-md5                     guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmac-md5                 guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

Here is the check with prior code. NOTE, the hmac-sha256 may have only been failing on salt lengths of 55, 119 and 183

$ ./jtrts.pl hmac-md5
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2056-g8e47f6b+ OMP [cygwin 64-bit AVX-ac]
--------------------------------------------------------------------------------
form=hmacMD5                      guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmacMD5                  guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

form=hmac-md5                     guesses:  472 -show= 472 0:00:00:00 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
.pot CHK:hmac-md5                 guesses:  472 0:00:00:00 DONE  [PASSED] (472 val-pwd)

$ ./jtrts.pl hmac-sha256
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2056-g8e47f6b+ OMP [cygwin 64-bit AVX-ac]
--------------------------------------------------------------------------------
form=hmac-sha256                  guesses: 1500 0:00:00:00 DONE  [PASSED]
.pot CHK:hmac-sha256              guesses: 1500 0:00:00:00 DONE  [PASSED] (1500 val-pwd)

form=hmac-sha256                  guesses: 1484 -show=1484 0:00:00:00 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
.pot CHK:hmac-sha256              guesses: 1484 0:00:00:00 DONE  [PASSED] (1484 val-pwd)

The new code corrects the problem, as far as I can tell

jfoug commented 8 years ago

I am now almost certain that both of these long salt hashes are working properly, but will wait until Frank (who has had other failing hardware), can test, and test against the latest jtrts with these changes.

Please test prior to the format changes with the updated jtrts.pl, just to see how things were working.

Then if all of your HW is working, we can close this bug.

magnumripper commented 8 years ago

Good stuff, thank you.

jfoug commented 8 years ago

Kind of a hard find. But once I got it to fail reliably in VC, then I could get down and debug a bit better. But still in the end, it ended up being that I spotted things that did not look right. VC help with the -8 vs -9 bug, but the other I simply stumbled across, and knew there was no way we could use 2 different sized output buffers with the same flags.

But I am really surprised about sha256 working as well as it did. It was mixing crypt_key usages. Sometimes using binary size, other times pad size. That it worked at all confounds me. I would have assumed that the pad buffer (needed for the last crypt) would have been smashed.

magnumripper commented 8 years ago

We should do this to HMAC-SHA1 and HMAC-SHA512 while we have this code fresh in our brains

jfoug commented 8 years ago

Do they need long salts? Btw, I tried to 'normalize' the other 2 hashes, so at least we have a working template. Also, what were the reason for SHA224/384? Were you just being complete when you built the others?

Note, 224 and 256 should probably be merged (with the type being added to the salt), and the same for 384/512. Again, 1 hash, that handles them both with a flag in the salt.

Just saying. If we go do sha1 and sha512, then if we merge, we get the other 2 for free.

magnumripper commented 8 years ago

Oh I see now I fixed all HMAC-SHA2 formats already. So we should check them for same bugs. They had salt length bumped to support JWT hashes. The MD5 format had it bumped to support CRAM-MD5 (it only supported a few ones with short length).

So HMAC-SHA1 is probably the only one left. Maybe it doesn't need support for longer salt. OTOH maybe JWT can theoretically be SHA-1?

jfoug commented 8 years ago

I have all sha2 done. sha224 and sha384 are not right yet (probably something change in the pclear code. But 512 is working fine.

I have normalized ALL formats, so that we can simply use diff to compare them. I really think we should merge the 32 bit sha (even sha1 if we want), and the 64 bit sha2 stuff. It should not be hard at all to merge the sha2 stuff. Putting sha1 in there might be overkill. Let me get these all working right, get jtrts.pl updated with long salts for all of them, and then get things checked in. Then we can see if we should drop 2 or 3 of the source files.

frank-dittrich commented 8 years ago

./jtrts.pl -stoponerror just ended with this (64 bit legacy avx build:

form=hmac-sha224-longsalt         guesses:  430 -show= 430 0:00:00:00 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
Exiting on error. The .pot file tst-.pot contains the found data
The command used to run this test was:

../run/john -ses=tst-  -pot=tst-.pot hmacSHA224_longsalt_new_tst.in --wordlist=pw-new.dic -form=hmac-sha224
and
../run/john -show   -pot=tst-.pot hmacSHA224_longsalt_new_tst.in -form=hmac-sha224
jfoug commented 8 years ago

I have not yet checked in code for these. The ONLY ones which should be trusted at this time are md5 and sha256. I am getting close on the others. I am working on a non-SIMD issue right now.

jfoug commented 8 years ago

Try after this. 1f3f878 I am hoping all formats work fine. NOTE, we do not have long salts for hmac-sha1 at this time (and possible will not, who knows).

frank-dittrich commented 8 years ago

With 1f3f878, that error is gone on 64bit linux. Will check arm later (currently running another test)

(master)test $ ./jtrts.pl -q
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2059-g1f3f878 [linux-x86-64-avx]
--------------------------------------------------------------------------------
All tests passed without error.  Performed 676 tests.  Time used was 1907 seconds

Before your latest fixes:

$ ./jtrts.pl -q
-------------------------------------------------------------------------------
- JtR-TestSuite (jtrts). Version 1.13, Dec 21, 2014.  By, Jim Fougeron & others
- Testing:  John the Ripper 1.8.0.6-jumbo-1-2058-gd37df04 [linux-x86-64-avx]
--------------------------------------------------------------------------------
form=hmac-sha224-longsalt         guesses:  430 -show= 430 0:00:00:00 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
form=hmac-sha384-longsalt         guesses: 1385 -show=1385 0:00:00:01 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
form=hmac-sha512-longsalt         guesses: 1393 -show=1393 0:00:00:01 DONE : Expected count(s) (1500)  [!!!FAILED1!!!  ret_val=0]
Some tests had Errors. Performed 676 tests.  3 errors                                   
Time used was 1908 seconds
frank-dittrich commented 8 years ago

Tests on my Raspberry Pi 2 were successful as well. Tested commit f61cf77.