Out-of-bounds array access in genmkvpwd

Out-of-bounds array access in genmkvpwd

Hi, we have found an out-of-bounds array access and would like to report this issue.
We're running the proposed fix locally but haven't tested thoroughly. Please make any needed corrections and push.

Summary

When max_len and start are specified, if max_lvl is too small, invalid memory access occurs.

Reproduction

• Operating System: Ubuntu 24.04 LTS
• Architecture: x86_64
• Compiler: GCC 14.2.0

Reproduction Steps

git clone https://github.com/openwall/john
cd john/src
./configure --enable-asan
make
../run/genmkvpwd  ../run/stats 1 1 1
# another pattern
# ../run/genmkvpwd  ../run/stats 27 3 1

Output

allocated 8 KB for nbparts
1 possible passwords
starting with  (1 to 1, 0.000000% of the scope)
AddressSanitizer:DEADLYSIGNAL
=================================================================
==1052493==ERROR: AddressSanitizer: SEGV on unknown address 0x525000080100 (pc 0x5fc83236e9d5 bp 0x7ffc29dd8fb0 sp 0x7ffc29dd8f80 T0)
==1052493==The signal is caused by a READ memory access.
    #0 0x5fc83236e9d5 in show_pwd_r /tmp/john/src/genmkvpwd.c:61
    #1 0x5fc83236f8cb in show_pwd /tmp/john/src/genmkvpwd.c:121
    #2 0x5fc832370787 in main /tmp/john/src/genmkvpwd.c:301
    #3 0x792cb422a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #4 0x792cb422a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #5 0x5fc83236e7e4 in _start (/tmp/john/run/genmkvpwd+0x47e4) (BuildId: b4e075dafb2127c3f70d28cd97c5c1dcc7034212)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /tmp/john/src/genmkvpwd.c:61 in show_pwd_r
==1052493==ABORTING

Another case also exists:

allocated 224 KB for nbparts
5 possible passwords
starting with c (1 to 5, 80.000000% of the scope)
=================================================================
==1083890==ERROR: AddressSanitizer: unknown-crash on address 0x712f75f18340 at pc 0x61645a65db8e bp 0x7fff5698a890 sp 0x7fff5698a880
READ of size 8 at 0x712f75f18340 thread T0
    #0 0x61645a65db8d in show_pwd_r /tmp/john/src/genmkvpwd.c:68
    #1 0x61645a65e8cb in show_pwd /tmp/john/src/genmkvpwd.c:121
    #2 0x61645a65f787 in main /tmp/john/src/genmkvpwd.c:301
    #3 0x712f7542a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #4 0x712f7542a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #5 0x61645a65d7e4 in _start (/tmp/john/run/genmkvpwd+0x47e4) (BuildId: b4e075dafb2127c3f70d28cd97c5c1dcc7034212)

Address 0x712f75f18340 is a wild pointer inside of access range of size 0x000000000008.
SUMMARY: AddressSanitizer: unknown-crash /tmp/john/src/genmkvpwd.c:68 in show_pwd_r
Shadow bytes around the buggy address:
  0x712f75f18080: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18100: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18180: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18200: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18280: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
=>0x712f75f18300: fe fe fe fe fe fe fe fe[fe]fe fe fe fe fe fe fe
  0x712f75f18380: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18400: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18480: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18500: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
  0x712f75f18580: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==1083890==ABORTING

Root Cause Analysis

[src/genmkvpwd.c:61](https://github.com/openwall/john/blob/5baa3c47dbef1466b106a5894e3096b13a8c22f1/src/genmkvpwd.c#L61)
When pwd->level is greater than max_level, it exceeds the nbparts array bounds and causes invalid memory access.
This code path is triggered when start > 0 (src/genmkvpwd.c:112).

[src/genmkvpwd.c:68](https://github.com/openwall/john/blob/5baa3c47dbef1466b106a5894e3096b13a8c22f1/src/genmkvpwd.c#L68)
Similarly, when the value of (pwd->level + proba2[pwd->password[pwd->len-2]*256 + curchar]) is greater than max_level, it exceeds the nbparts array bounds and causes invalid memory access.

[src/genmkvpwd.c:84](https://github.com/openwall/john/blob/5baa3c47dbef1466b106a5894e3096b13a8c22f1/src/genmkvpwd.c#L84) has the same issue.

[src/genmkvpwd.c:274](https://github.com/openwall/john/blob/5baa3c47dbef1466b106a5894e3096b13a8c22f1/src/genmkvpwd.c#L274)
Note: The size allocated for nbparts is 256*(max_lvl+1) * (max_len+1).

[src/genmkvpwd.c:125](https://github.com/openwall/john/blob/5baa3c47dbef1466b106a5894e3096b13a8c22f1/src/genmkvpwd.c#L125)
Note: In code sections that work regardless of whether the start command line argument is present, the level value is checked and no crash occurs.

Proposed Fix

diff --git a/src/genmkvpwd.c b/src/genmkvpwd.c
index de62d0330..3a987ab51 100644
--- a/src/genmkvpwd.c
+++ b/src/genmkvpwd.c
@@ -63,7 +63,8 @@ static void show_pwd_r(struct s_pwd * pwd, unsigned int bs)
 	lvl = pwd->level;
 	if (bs)
 	{
-		while( (curchar=charsorted[ pwd->password[pwd->len-2]*256 + k ]) != pwd->password[pwd->len-1] )
+		while( (curchar=charsorted[ pwd->password[pwd->len-2]*256 + k ]) != pwd->password[pwd->len-1] &&
+			   (pwd->level + proba2[ pwd->password[pwd->len-2]*256 + curchar ]) <= gmax_level)
 		{
 			i -= nbparts[ curchar + pwd->len*256 + (pwd->level + proba2[ pwd->password[pwd->len-2]*256 + curchar ])*256*gmax_len  ];
 			k++;
@@ -81,6 +82,9 @@ static void show_pwd_r(struct s_pwd * pwd, unsigned int bs)
 	{
 		pwd->password[pwd->len-1] = charsorted[ pwd->password[pwd->len-2]*256 + k ];
 		pwd->level = lvl + proba2[ pwd->password[pwd->len-2]*256 + pwd->password[pwd->len-1] ];
+		if (pwd->level >= gmax_level){
+			break;
+		}
 		i -= nbparts[ pwd->password[pwd->len-1] + pwd->len*256 + pwd->level*256*gmax_len ];
 		if (pwd->len<=gmax_len)
 		{
@@ -118,8 +122,10 @@ static void show_pwd(uint64_t start, uint64_t end, unsigned int max_level, unsig
 			i++;
 		pwd.len = 1;
 		pwd.level = proba1[pwd.password[0]];
-		show_pwd_r(&pwd, 1);
-		printf("%s\n", pwd.password);
+		if (pwd.level <= max_level){
+			show_pwd_r(&pwd, 1);
+			printf("%s\n", pwd.password);
+		}
 		i++;
 	}
 	while(proba1[charsorted[i]]<=max_level)

Start with src/genmkvpwd.c, especially show_pwd_r at lines 61, 68, and 84, the start-handling path near line 112, and the nbparts allocation near line 274. Build with ./configure --enable-asan and reproduce the commands shown for max_lvl 1; done means the reported inputs no longer trigger AddressSanitizer invalid-memory-access errors.