[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20240602180625.GA16565@openwall.com>
Date: Sun, 2 Jun 2024 20:06:25 +0200
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: new external mode Shuffle
Hi,
Back in 2020, torerobo suggested a new word mangling rule - shuffle
characters in an input word, trying all possible permutations, but
exclude duplicates if the input word has a character appear more than
once. Our rules currently don't produce multiple outputs, but this
functionality could be implemented as a hybrid external mode. I just
took care of that, mostly as an interesting programming and algorithm
optimization puzzle to solve:
https://github.com/openwall/john/issues/4194
For example, for the word "password", it produces 8!/2!-1 = 20159
outputs, where 8 is the length, 2 is because the two instances of the
letter s should only be tried in one order, and -1 is because we exclude
the word as-is.
The code is now in bleeding-jumbo, usable via --external=Shuffle on top
of another cracking mode (usually wordlist).
I didn't expect this to crack a lot of passwords, but it nevertheless
does crack quite some. Most of those overlap with what our other modes
crack, but some don't (of course, in limited usage of the other modes).
Splitting of Shuffle by length (with command-line options) appears
necessary for it to perform well. Otherwise the slow progress at high
lengths (which produce a lot of candidates per input line) would
unnecessarily slow down progress and total number of inputs and outputs
processed for lower lengths.
There appears to be a cliff after length 10, so that is currently set as
the maximum in init(), but it can be slightly increased.
Testing with our default password.lst (~1.8M lines) against a 10M
representative sample from HIBPv8 (6969140 unique NTLM hashes), after
having excluded the same password.lst with --rules=best-by-score (which
cracked 3002693 unique hashes by maybe ~5G candidates), letting Shuffle
go for up to 100M candidates per run split by length:
Up to 6: 9661 (48.37% progress through password.lst)
7: 3366 (10.23%)
8: 1813 (1.08%)
9: 419 (0.38%)
10: 337 (0.18%)
That's 15596 unique Shuffle cracks for 500M candidates.
Instead of the Shuffle runs, continuing with --rules=worse-by-score for
500M candidates (dupe suppressor disabled) cracks 17695. Further rules
can be made more effective by running another ruleset rather than the
known-worse portion from the same original/split ruleset. 500M of
--rules=OneRuleToRuleThemStill (including dupes) cracks 26185. 500M of
default --incremental cracks 81403 (and the unique cracked by Shuffle
reduce to 10081). All of these 500M options were tried on their own,
never one on top of another (except for the retroactive comparison of
incremental significantly reducing Shuffle's unique).
For a further comparison, continuing the default --incremental for a
second 500M cracks 36535 more, which is 3.6x more than Shuffle's unique
by that point (after first 500M incremental).
Overall, not surprisingly Shuffle is less effective than the
alternatives, but maybe it adds some unique cracks on top of other
exhausted possibilities? Let's try 10G of incremental on top of the
best-by-score rules baseline. This cracks 314521. A further 500M of
incremental (10.5G total) cracks 6291. 500M Shuffle's remaining unique
after 10G were 4741. So even after 10G Shuffle is still less effective
than simply continuing with incremental.
Maybe 10G was not enough. Let's try 100G of incremental (still on top
of --rules=best-by-score), which cracks 634495. At this point, the
above 500M Shuffle would still add 2348 unique cracks, whereas another
500M of incremental (for 100.5G) adds only 548. Shuffle kind of wins.
I guess this advantage is very brief and wouldn't hold for much longer
Shuffle runs (less common and longer input passwords), but it does
indicate Shuffle can crack a bit more than other methods at some point.
Excluding lengths 8+ or 9+ from the Shuffle runs and instead doing more
for lengths up to 7 increases Shuffle unique cracks after the rules to
~23k (still in 500M, just different split by length), but decreases the
Shuffle unique cracks remaining on top of the 100G incremental. So
despite of their worse initial results, the higher length Shuffle cracks
eventually have less overlap with other modes' cracks.
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
