openwall / openwall/john

Concurrent hashing for many salts

Open
#4,035 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

In #4033, I implemented advance start of processing for the next salt before we're done with the current salt. This can be taken further: crypt_all can walk up to the entire salt list and start hashing for up to all salts. Then subsequent calls to crypt_all would quickly return the already-computed results. This can be beneficial for very slow hashes when the salt count is large, in order to allow for efficient use of tiny wordlists (fewer lines than we have compute cores, etc.) and to have the run proceed across the list of candidate passwords in their proper order (perhaps sorted for decreasing estimated probability of successful guess) rather than in large chunks for each salt (which results in suboptimal order if the list was sorted optimally).

It can also help with medium speed hashes combined with relatively high latency communication to compute device(s), to let them start processing for multiple salts without having to tell them about each next salt individually (where with enough concurrent compute devices per host process it might happen that telling them just one more salt in advance isn't enough to fully cover the communication latency). This idea is from an e-mail @Apingis sent me.

For either purpose, we need to dynamically lower max_keys_per_crypt as we'd partially start distributing (or/and buffering) salts rather than candidates. @Apingis confirmed in an e-mail to me that adjusting max_keys_per_crypt from clear_keys works.

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.

Research direction

Start by reading the existing crypt_all, max_keys_per_crypt, and clear_keys handling, then compare the approach described in issue #4033. Determine where salt processing and candidate distribution are coordinated. Done means concurrent processing can cover multiple salts while preserving candidate order and dynamically adjusting max_keys_per_crypt.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
cryptography, performance, security
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.