dynamic's valid is too permissive

[AlekseyCherepanov]

Working on #5031 for PHPS that relies on pDynamic_6->methods.valid, I found that dynamic's valid is quite permissive.

It does not reject garbage after $HEX$:

$dynamic_6$612f95cf86c4e196f6b627bab3f01b62$HEX$$$$$$$

Is it ok?

I tried to make samples expecting that salt is HEX$$$$$$$ or salt is empty. I could not crack them.

It affects PHPS format allowing it to load such hashes while it should not (its salt is 3 chars exactly).

[AlekseyCherepanov]

Also fuzzing phps yielded 2 samples that crash dynamic_6 when in ASan build:

$dynamic_6$ad14afbbf0e16d4ad8c8985263a3d051$HEX$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$247824
$dynamic_6$ad14afbbf0e16d4ad8c8985263a3d051$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$HEX$247824

They produce similar outputs from ASan:

$ ./run/john --format=dynamic_6 t.pw
[...]
==26330==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x63300001ac00 at pc 0x556af7e5b60a bp 0x7fff7fbed1c0 sp 0x7fff7fbed1b8
WRITE of size 4 at 0x63300001ac00 thread T0
    #0 0x556af7e5b609 in __SSE_append_string_to_input /home/user/john/src/dynamic_fmt.c:3327
    #1 0x556af7e62c2a in __append_string /home/user/john/src/dynamic_fmt.c:3375
    #2 0x556af7e63134 in DynamicFunc__append_salt /home/user/john/src/dynamic_fmt.c:4940
    #3 0x556af7e7f02c in crypt_all /home/user/john/src/dynamic_fmt.c:1898
    #4 0x556af822283c in crk_password_loop /home/user/john/src/cracker.c:894
    #5 0x556af8224de3 in crk_salt_loop /home/user/john/src/cracker.c:1065
    #6 0x556af8225457 in process_key /home/user/john/src/cracker.c:1148
    #7 0x556af8291973 in do_wordlist_crack /home/user/john/src/wordlist.c:1349
    #8 0x556af820c344 in do_wordlist_pass /home/user/john/src/batch.c:40
    #9 0x556af820c486 in do_batch_crack /home/user/john/src/batch.c:60
    #10 0x556af8243318 in john_run /home/user/john/src/john.c:1841
    #11 0x556af8243318 in main /home/user/john/src/john.c:2082
    #12 0x7ffae5e5009a in __libc_start_main ../csu/libc-start.c:308
    #13 0x556af7db34b9 in _start (/home/user/john/run/john+0x2d14b9)

0x63300001ac00 is located 0 bytes to the right of 107520-byte region [0x633000000800,0x63300001ac00)
allocated by thread T0 here:
    #0 0x7ffae6904018 in __interceptor_posix_memalign ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:155
    #1 0x556af8267ddd in mem_alloc_align /home/user/john/src/memory.c:268
    #2 0x556af8267efd in mem_calloc_align /home/user/john/src/memory.c:310
    #3 0x556af7e6feb2 in init /home/user/john/src/dynamic_fmt.c:873
    #4 0x556af822d6ea in fmt_init /home/user/john/src/formats.c:438
    #5 0x556af824ce39 in ldr_split_line /home/user/john/src/loader.c:780
    #6 0x556af824d53a in ldr_load_pw_line /home/user/john/src/loader.c:958
    #7 0x556af8248611 in read_file /home/user/john/src/loader.c:255
    #8 0x556af8250848 in ldr_load_pw_file /home/user/john/src/loader.c:1198
    #9 0x556af823fadd in john_load /home/user/john/src/john.c:1134
    #10 0x556af823fadd in john_init /home/user/john/src/john.c:1578
    #11 0x556af823fadd in main /home/user/john/src/john.c:2065
    #12 0x7ffae5e5009a in __libc_start_main ../csu/libc-start.c:308

[AlekseyCherepanov]

Crackable md5(md5($pass).$salt) with password test and salt $$$$$$:

$dynamic_6$f8055d63608f56ab8a90d49f751d1dc7$HEX$$$$$$$

It can be cracked as dynamic_6. But phps cannot crack it.

$HEX$ gets replaced with $. Actually $HEX$ may be at any position. So the following works too (phps cannot load it):

$dynamic_6$f8055d63608f56ab8a90d49f751d1dc7$$HEX$$$$$$

Code in split in phps suggests that it expects either $ + salt as is or $HEX$ + salt in hex after digest for $dynamic_6$ ciphertexts. I guess many thin formats expect something easy if they try to load hashes with $dynamic_N$ tag. (Though there is phps2 that is just phps implemented with builtin dynamic script, but phps2 does not load anything other than $PHPS$.)

Dynamic hashes are parsed this way approximately (at least now):

• check tag
• replace $HEX$ + hex up to next $ or to end of string with $ + decoded hex everywhere in string
  • $HEX$ + hex + garbage are not replaced
  • if there is unprintable char (only null byte in get_salt) in decoded data then original string is used without any changes
  • decoding is done in prepare, valid, get_salt and maybe some other places
• check digest to be in hex (or in base64 if format uses base64 like dynamic_19) with correct length
• then the first $ is excluded, the rest is salt and/or fields if particular dynamic format uses respective features: there may be $$2, $$F + digit and/or $$U treated as separators (I am not sure about the first $ in case of start with $$2 for instance)

Crackable dynamic_6 with password test and salt $$$:

$dynamic_6$c2d3a9825e492db99b44c429eb744861$HEX$$HEX$$HEX$$HEX$

Same with double encoded digest and not encoded salt:

$dynamic_6$HEX$6332643361393832356534393264623939623434633432396562373434383631$$$$

Triple encoded (value in hex is substring HEX$623...31 from above):

$dynamic_6$HEX$4845582436333332363433333631333933383332333536353334333933323634363233393339363233343334363333343332333936353632333733343334333833363331$$$$

Deeper level did not work for me. But it might be allowed for salts.

Password test, salt 1NOTHEX, not crackable:

$dynamic_6$a3baf611b9a12f2cae642f49be7d018c$HEX$31NOTHEX

Using printf in __SSE_append_string_to_input I see 1oo_ as salt.

[AlekseyCherepanov]

Crash in dynamic can happen without $HEX$. Dynamic is intended to check lengths of salts pretty well. But $$ in salt disables checks.

Crasher without $HEX$:

python -c 'print "$dynamic_6$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$" + "$" * 100' > t.pw

Dynamic has dynamic_FIXED_SALT_SIZE -23. Negative value means variable length up to abs() of value (inclusive).

Respective part of valid:

	else if (!regen_salts_options && pPriv->dynamic_FIXED_SALT_SIZE < -1 && strlen(&ciphertext[pPriv->dynamic_SALT_OFFSET]) > -(pPriv->dynamic_FIXED_SALT_SIZE)) {
		char *cpX;
		// first check to see if this salt has left the $HEX$ in the string (i.e. embedded nulls).  If so, then
		// validate length with this in mind.
		if (!memcmp(&ciphertext[pPriv->dynamic_SALT_OFFSET], "HEX$", 4)) {
			int len = strlen(&ciphertext[pPriv->dynamic_SALT_OFFSET]);
			len = (len-4)>>1;
			if (len > -(pPriv->dynamic_FIXED_SALT_SIZE))
				return 0;
		} else {
			// check if there is a 'salt-2' or 'username', etc  If that is the case, then this is still 'valid'
			cpX = mem_alloc(-(pPriv->dynamic_FIXED_SALT_SIZE) + 3);
			strnzcpy(cpX, &ciphertext[pPriv->dynamic_SALT_OFFSET], -(pPriv->dynamic_FIXED_SALT_SIZE) + 3);
			if (!strstr(cpX, "$$")) {
				MEM_FREE(cpX);
				return 0;
			}
			MEM_FREE(cpX);
		}
	}

[AlekseyCherepanov]

Dynamic has dynamic_FIXED_SALT_SIZE -23.

I mean dynamic_6, of course.

[AlekseyCherepanov]

$ run/john --format=dynamic --list=format-tests | grep '2424'
dynamic_15	6	$dynamic_15$6093d5cb3e2f99d9110eb9c4bbca5f8c$HEX$6161615358422424556a6f65626c6f77	test1
[...]

That's a hash embedded into src/dynamic_preloads.c. And according to --show=formats that's the canonical form.

dynamic_15: md5($u.md5($p).$s). There is 1 $HEX$ with both username and salt: aaaSXB$$Ujoeblow. So username is joeblow and salt is aaaSXB.

>>> md5('joeblow' + md5('test1').hexdigest() + 'aaaSXB').hexdigest()
'6093d5cb3e2f99d9110eb9c4bbca5f8c'

Code in valid suggests that $$U would not be found if hex is not decoded due to null byte:

	if (pPriv->nUserName && !strstr(&ciphertext[pPriv->dynamic_SALT_OFFSET-1], "$$U"))
		return 0;

[AlekseyCherepanov]

I dislike encoding fields together into hex. There is opportunity to implement correct support for arbitrary data: field delimiters are not encoded, hex is used to protect them when delimiters occur in data. Particularly if just $ happens in data, then data should be encoded.

Or maybe $$, so user would be able to build correct ciphertext manually in most cases (then $HEX$ may occur in data and be confusing; so maybe $HEX$ should be encoded too).

[AlekseyCherepanov]

It looks like most dynamic formats can handle long strings without crash. Overflow happens in __SSE_append_string_to_input that is used by some formats only.

I have a fix to reject overly long salt if there is only regular salt (aka $s). But it is not enough.

I found these format to call the problematic function and use username:

dynamic_1015 [md5(md5($p.$u).$s) (PostgreSQL 'pass the hash') 128/128 SSE4.1 4x3]
dynamic_1034 [md5($p.$u) (PostgreSQL MD5) 128/128 SSE4.1 4x3]
dynamic_1506 [md5($u.:XDB:.$p) (Oracle 12c "H" hash) 128/128 SSE4.1 4x3]
dynamic_1550 [md5($u.:mongo:.$p) (MONGODB-CR system hash) 128/128 SSE4.1 4x3]
dynamic_1551 [md5($s.$u.(md5($u.:mongo:.$p)) (MONGODB-CR network hash) 128/128 SSE4.1 4x3]

A crasher for dynamic_1015:

python -c 'print "$dynamic_1015$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$" + "$" * 100 + "$$Uuser"' > t.pw

[AlekseyCherepanov]

It turned out that there is no way to distinguish dynamic with both $s and $u and dynamic using $u only. Any salt is accepted for $u-only formats. And it is not removed, pot entries do not match.

Example with dynamic_1034: md5($p.$u):

$ echo '$dynamic_1034$5d9c68c6c50ed3d02a2fcf54f63993b6$$Uuser' > t.pw
$ run/john t.pw
[...]
test             (?)     
[...]
$ echo '$dynamic_1034$5d9c68c6c50ed3d02a2fcf54f63993b6$ignored_salt$$Uuser' > t.pw
$ run/john t.pw
[...]
test             (?)     
[...]
$ cat run/john.pot
$dynamic_1034$5d9c68c6c50ed3d02a2fcf54f63993b6$HEX$245575736572:test
$dynamic_1034$5d9c68c6c50ed3d02a2fcf54f63993b6$HEX$69676e6f7265645f73616c7424245575736572:test

[AlekseyCherepanov]

This one gets rejected while it should not ("u" * 26 as username):

$dynamic_1506$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$$Uuuuuuuuuuuuuuuuuuuuuuuuuuu

It has SaltLen=-27. So there should be some miscalculation of length in valid.

[AlekseyCherepanov]

dynamic_1551 is a problem: its max username length is 7 (55 minus 32 for md5() minus 16 for salt). But there is no info about it formally. But there is slower dynamic_1552 equivalent made with flat buffers and no overflows.

# MONGODB-CR network hashes  (user name < 8 bytes long)
# Input hash format => username:$dynamic_1551$hash$salt$$Uusername
[List.Generic:dynamic_1551]
Expression=md5($s.$u.(md5($u.:mongo:.$p)) (MONGODB-CR network hash)
[...]
MaxInputLen=23
MaxInputLenX86=110
# note, saltlen + length(:mongo:) + length(plain) must stay <= 55 for SIMD
#   so 25+7+23 == 55
SaltLen=16

[AlekseyCherepanov]

dynamic_1551 can crash in 2 places: overflowing $u.:mongo:$p or $s.$u.md5(...).

The first case:

$ python -c 'print "$dynamic_1551$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$" + "s" * 16 + "$$U" + "u" * 100' > t.pw && ./run/john t.pw
[...]
WRITE of size 4 at 0x63300001ac00 thread T0
    #0 0x560e1dab0609 in __SSE_append_string_to_input /home/user/john/src/dynamic_fmt.c:3362
    #1 0x560e1dab98c2 in __append_string /home/user/john/src/dynamic_fmt.c:3411
    #2 0x560e1dad2759 in DynamicFunc__append_userid /home/user/john/src/dynamic_fmt.c:6712
    #3 0x560e1dad4329 in crypt_all /home/user/john/src/dynamic_fmt.c:1933

The second case (16 is max for safe $u in the first concatenation):

$ python -c 'print "$dynamic_1551$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$" + "s" * 16 + "$$U" + "u" * 16' > t.pw && ./run/john t.pw
[...]
WRITE of size 4 at 0x633000036c00 thread T0
    #0 0x5558d2b80e86 in __SSE_append_output_base16_to_input_semi_aligned_0 /home/user/john/src/dynamic_fmt.c:3273
    #1 0x5558d2ba1e6d in DynamicFunc__append_from_last_output_to_input2_as_base16 /home/user/john/src/dynamic_fmt.c:6331
    #2 0x5558d2ba5329 in crypt_all /home/user/john/src/dynamic_fmt.c:1933

[AlekseyCherepanov]

I renamed the issue because all above crashes in existing formats were fixed in #5047.

Remaining problems:

• I would prefer to encode fields separately and check them strictly.
  • Current implementation decodes hex multiple times, so it would be tricky to encode $HEX$ to be a part of salt.
  • Similarly it should be tricky to pass $$U as a part of username or salt (not sure which one).
• Formats do not know their limitations on supported length of username. So breaking the limit results into uncrackable hashes now. It would be better to reject such hashes in valid().
• Any salt is accepted for $u-only formats.

[solardiz]

all above crashes in existing formats were fixed in #5047.

If so, I think there's no reason to treat the remaining aspects of this issue as a priority, so I've just removed the milestone.