openwall / openwall/john

Better handling of eg. different length buffers

Open
#3,907 3 comments 0 reactions 1 assignee View on GitHub

@magnumripper is already working on this.

Since May 9, 2019.

enhancement RFC / discussion
Dominant language
C
Stars
13.6k
Forks
2.6k
PR merge metrics
No merged PRs in 30d

Description

Note to self, and RFC.

This just hit me. It's by no means a candidate for 1.9.0-Jumbo-1, but later.

For several formats, and per recent discussion of md5crypt enhancements, we're buffering many more passwords than needed because we actually have two or more code paths within crypt_all() for eg. different lengths. This is quite ineffective and sometimes even a large number isn't enough. Worst examples are formats like RAR3 that [for best SIMD or OpenCL efficiency] needs a different code path or buffer for every password length...

Here's how we can do it instead (I think) using "recently" added (as in 2013) functionality to crypt_all. Let's take md5crypt as example with the simplest case of this: One code path (SIMD) for length up to 15 and another (scalar) for over 16. For simpler explanation, I here leave OpenMP out of the discussion:

  1. We set max_keys_per_crypt to no more than the actual SIMD max, i.e. SIMD_COEF_32 * SIMD_PARA_MD5.
  2. We have a SIMD key buffer of twice that size, and another buffer for scalar (of just once the size).
  3. Once in crypt_all(), we look at the SIMD buffer. If it's not complete, we just post-pone it. Then, in this case we can always process any keys in the other buffer, so we do.
  4. We change *pcount to the actual number of processed keys. From this point, the format needs to be able to map eg. a cmp_*_(N) or get_key(N) call to what keys were actually processed.

So, in some calls to crypt_all(), nothing is processed. In some, only a number of >16 are processed. In others, a full SIMD batch of <=15 is processed. Sometimes both buffers are processed.

Pros: We keep mkpc down to a minimum, which is always a good thing. This also means we keep memory use down. All in all I believe we might even end up with lower complexity but that's yet to prove.

Cons: Every time we ended up with nothing processed, given a large number of salts we'll get quite some time wasted in the set_salt(), crypt_all() loop. Also, if we have a half-filled SIMD buffer and then get no more such keys for a long time, that processing will be delayed. On the other hand, given this scheme it would be trivial to keep a limit of how much we allow to wait with processing them - we can always opt to process the incomplete buffer at will.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.