[Feature Request] Add $keychain$ support

[adrastee]

Hi,

$ hashcat.exe --example-hashes | grep keychain -A 1
TYPE: 1Password, agilekeychain
HASH: 1000:d61a54f1efdfcf57:00......

TYPE: 1Password, cloudkeychain
HASH: 9b6933f4a1f65baf02737545efc8c1c.....

Look like hashcat does not support $keychain$ hash outputs from keychain2john.py .

This file is a keepass-like for Mac OS.
Could you please add this mode ? Based on PBKDF2-SHA1 3DES.
Thanks a lot.

Sample input file : https://openwall.info/wiki/_media/john/Keychain-Samples.zip
Sample hash:password : $keychain$*10f7445c8510fa40d9ef6b4e0f8c772a9d37e449*f3d19b2a45cdcccb*8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b:passsord

$keychain$*salt*iv*ciphertext

[Banaanhangwagen]

In 99,9% of the cases, this keychain-password is the same as the macOS login password, which is supported by Hashcat with -m 7100

It seems that macOS login is based on pbkdf2_sha512 and the keychain, like you mentioned, on PBKDF2-SHA1 3DES.

It would be interesting to see if there is a speed gain.

[adrastee]

I am not aware of this statistic, but from my experience, keychain passwords are always different from the login one.
Here is a c++ implementation of keychain cracking: https://github.com/macmade/KeychainCracker
Maybe it could help / speedup hashcat implementation ? :)

[Banaanhangwagen]

First phrase: https://support.apple.com/guide/keychain-access/if-you-need-to-update-your-keychain-password-kyca2429/mac
By default, your keychain password is the same as your user password (the password you use to log in to the computer)

The user can change the keychain-password, but this is a deliberate action what not much people tend to do...

I either way, I support you feature request :)

[philsmd]

I see three problems here:

First, the password for the above example hash is wrong. This is very bad, because developers might waste a lot of time with wrong examples ! Try to avoid to do these types of mistakes/typos. The password would be "password" (without quotes). The example is taken from the john the ripper (JTR) examples: https://github.com/magnumripper/JohnTheRipper/blob/2778d2e9df4aa852d0bc4bfbb7b7f3dde2935b0c/src/keychain_common_plug.c#L11

Second, the tool from above (KeychainCracker) seems to be non-cross-platform, only working on macOS and also not have any code dedicated to the hashing. It's basically just a GUI that uses the operating system (macOS's) APIs, in particular it's this (SecKeychainUnlock): https://developer.apple.com/documentation/security/1400341-seckeychainunlock .
Therefore, it's neither optimized for the hashing algorithm operations (because it repeatedly just calls the OS APIs again and again), nor does it illustrate how the algorithm works (there is absolutely NO code that has to do with the hashing operation, because it's just calling an API).

Third, the verification step for this hash format is actually not bullet proof. As you can see from here: https://github.com/magnumripper/JohnTheRipper/blob/2778d2e9df4aa852d0bc4bfbb7b7f3dde2935b0c/src/keychain_fmt_plug.c#L111 , we only test for 0x04040404 at a very specific location of the decrypted data. These are only 4 bytes / 32 bits... which is very bad / low. It would be much better if there wasn't that high chance of false positives, wrong passwords reported. The good thing is that with 1000 iteration it's slowed down a little bit, but maybe not too much and therefore this hash type would need to be used with --keep-guessing :(
I think the hash format that JTR uses, doesn't allow for any further verification check or "collision removal". You could, I agree, argue that it's still slow with 1000 iterations and that having 4 consecutive bytes at a very specific location all being 0x04 is kind of rare, but it happens unfortunately a lot with fast password cracking tools.

So here I will try to explain a little bit the algorithm and attach some POC (proof of concept) perl hash generation code:

1. it uses PBKDF2 with salt and pass, using 1000 iteration and an output size of 24 (for the 3DES key)
2. it decrypts the data with 3DES-CBC (but actually only the last block is needed !)
3. it checks if the password was valid by doing a padding attack (checking for 4 consecutive 0x04 bytes at the very end)

#!/usr/bin/env perl

# Author: philsmd
# Date: June 2020
# License: public domain, credits go to philsmd and hashcat

use strict;
use warnings;

use Crypt::PBKDF2;
use Crypt::CBC;

#
# Constants
#

my $ITERATIONS = 1000;

#
# Examples
#

# Example 1:

# $keychain$*10f7445c8510fa40d9ef6b4e0f8c772a9d37e449*f3d19b2a45cdcccb*8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b:password

my $pass = "password";
my $salt = pack ("H*", "10f7445c8510fa40d9ef6b4e0f8c772a9d37e449");
my $iv   = pack ("H*", "f3d19b2a45cdcccb");
my $data = pack ("H*", "8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b");


# Example 2:

# $keychain$*a88cd6fbaaf40bc5437eee015a0f95ab8ab70545*b12372b1b7cb5c1f*1f5c596bcdd015afc126bc86f42dd092cb9d531d14a0aafaa89283f1bebace60562d497332afbd952fd329cc864144ec:password

# my $pass = "password";
# my $salt = pack ("H*", "a88cd6fbaaf40bc5437eee015a0f95ab8ab70545");
# my $iv   = pack ("H*", "b12372b1b7cb5c1f");
# my $data = pack ("H*", "1f5c596bcdd015afc126bc86f42dd092cb9d531d14a0aafaa89283f1bebace60562d497332afbd952fd329cc864144ec");


# Example 3:

# $keychain$*23328e264557b93204dc825c46a25f7fb1e17d4a*19a9efde2ca98d30*6ac89184134758a95c61bd274087ae0cffcf49f433c7f91edea98bd4fd60094e2936d99e4d985dec98284379f23259c0:hhh

# my $pass = "hhh";
# my $salt = pack ("H*", "23328e264557b93204dc825c46a25f7fb1e17d4a");
# my $iv   = pack ("H*", "19a9efde2ca98d30");
# my $data = pack ("H*", "6ac89184134758a95c61bd274087ae0cffcf49f433c7f91edea98bd4fd60094e2936d99e4d985dec98284379f23259c0");


# Example 4:

# $keychain$*927717d8509db73aa47c5e820e3a381928b5e048*eef33a4a1483ae45*a52691580f17e295b8c2320947968503c605b2784bfe4851077782139f0de46f71889835190c361870baa56e2f4e9e43:JtR-Jumbo

# my $pass = "JtR-Jumbo";
# my $salt = pack ("H*", "927717d8509db73aa47c5e820e3a381928b5e048");
# my $iv   = pack ("H*", "eef33a4a1483ae45");
# my $data = pack ("H*", "a52691580f17e295b8c2320947968503c605b2784bfe4851077782139f0de46f71889835190c361870baa56e2f4e9e43");


# Example 5:

# $keychain$*1fab88d0b8ea1a3d303e0aef519796eb29e46299*3358b0e77d60892f*286f975dcd191024227514ed9939d0fa94034294ba1eca6d5c767559e75e944b5a2fcb54fd696be64c64f9d069ce628a:really long password -----------------------------

# my $pass = "really long password -----------------------------";
# my $salt = pack ("H*", "1fab88d0b8ea1a3d303e0aef519796eb29e46299");
# my $iv   = pack ("H*", "3358b0e77d60892f");
# my $data = pack ("H*", "286f975dcd191024227514ed9939d0fa94034294ba1eca6d5c767559e75e944b5a2fcb54fd696be64c64f9d069ce628a");


# Example 6:

# $keychain$*3a473dd308b1713ddc76fc976758eb543779a228*570b762ec2b177d0*a1f491231412ff74344244db4d98b1dab6e40a8fc63a11f0d5cdabf97fce5c4fa8ae0a1f95d0398d37e3d45e9fa07aa7:El Capitan

# my $pass = "El Capitan";
# my $salt = pack ("H*", "3a473dd308b1713ddc76fc976758eb543779a228");
# my $iv   = pack ("H*", "570b762ec2b177d0");
# my $data = pack ("H*", "a1f491231412ff74344244db4d98b1dab6e40a8fc63a11f0d5cdabf97fce5c4fa8ae0a1f95d0398d37e3d45e9fa07aa7");


#
# Start
#

my $pbkdf2 = Crypt::PBKDF2->new
(
  hasher     => Crypt::PBKDF2->hasher_from_algorithm ('HMACSHA1'),
  iterations => $ITERATIONS,
  output_len => 24
);

# slowest part of the algorithm:

my $key = $pbkdf2->PBKDF2 ($salt, $pass);


#
# Verification:
#

my $c1 = Crypt::CBC->new ({
  key         => substr ($key, 0, 8),
  iv          => "\x00" x 8,
  cipher      => "DES",
  literal_key => 1,
  header      => "none",
  padding     => "null",
});

my $c2 = Crypt::CBC->new ({
  key         => substr ($key, 8, 8),
  iv          => "\x00" x 8,
  cipher      => "DES",
  literal_key => 1,
  header      => "none",
  padding     => "null",
});

my $c3 = Crypt::CBC->new ({
  key         => substr ($key, 16, 8),
  iv          => "\x00" x 8,
  cipher      => "DES",
  literal_key => 1,
  header      => "none",
  padding     => "null",
});

# fixed 48 byte output (but we only need last block):

# my $data_decrypted = "";
#
# for (my ($i, $j) = (0, 0); $i < 6; $i += 1, $j += 8)
# {
#   my $d = substr ($data, $j, 8);
#
#   my $t;
#
#   $t = $c3->decrypt ($d);
#   $t = $c2->encrypt ($t);
#   $t = $c1->decrypt ($t);
#
#   $t ^= $iv;
#
#   $data_decrypted .= $t;
#
#   $iv = $d
# }

# shortcut for padding check/attack:

my $d;

$iv = substr ($data, 32, 8);
$d  = substr ($data, 40, 8);

my $t;

$t = $c3->decrypt ($d);
$t = $c2->encrypt ($t);
$t = $c1->decrypt ($t);

$t ^= $iv;

if (substr ($t, 4, 4) eq "\x04" x 4) # "\x04\x04\x04\x04"
{
  print "password found: '$pass'\n";

  exit (0);
}

exit (1);

So my questions basically are:

1. Could you verify that this perl code also works with a keychain that you newly created by changing the pass/salt/iv/data variables in the script above ?
2. Are we sure that the padding attack always works since even JTR wasn't really sure about it (https://github.com/magnumripper/JohnTheRipper/blob/2778d2e9df4aa852d0bc4bfbb7b7f3dde2935b0c/src/keychain_fmt_plug.c#L110 ) ? Could we maybe try with a lot of newly generated keychains and see if they all have those 4 bytes ?
3. I assume we will keep the JTR format for compatibility reasons, is there any other way to reduce false positives by still sticking to this hash format ?

Thanks

[Banaanhangwagen]

@philsmd Thank you for your reaction.

I tested successfully your script with 5 real-life login.keychains from different devices and macOS versions; they all give the expected output "password found"

2.&3.
JtR and also like documented in this paper on p3 (We have to learn an appropriate master key from the candidates by checking if there is a valid padding (in the form of PKCS#1) at the end of the excerpt), we see that they check for padding, namely \x04\x04\x04\x04.

I do not know if this will always work, the risk to have a collision exists but is - I think - negligible.
Like you mentioned, Hashcat supports the --keep-guessing, so if needed...

Let me explain something I noticed while testing.
Your Perl script transformed in Python is this :

import binascii

from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF2
from Crypto.Hash import SHA1
from Crypto.Util import strxor

password = "password"
salt = binascii.unhexlify('10f7445c8510fa40d9ef6b4e0f8c772a9d37e449')
#iv = binascii.unhexlify('f3d19b2a45cdcccb')
data = binascii.unhexlify('8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b')

key = PBKDF2(password, salt, 24, count=1000, hmac_hash_module=SHA1)
c = DES3.new(key, DES3.MODE_CBC, b'\x00' * 8)

iv = data[32:32+8]
d = data[40:]

t = c.decrypt(d)
t = strxor.strxor(t, iv)

print(binascii.hexlify(t))

This gives the following output :

b'fa53782504040404'

a) the IV as mentioned in the extracted hash is not needed, instead we use 8 times x00
b) at the end, we XOR the t with an iv that we got from data
c) we see the padding \x04\x04\x04\x04 in the output

So far, so good.

One of the authors of the paper is n0fate who wrote the tool chainbreaker. This tool expects the login.keychain and a password as input. Afterwards, it decrypts all the records in the file.

It would be interesting to see how his script does the password-check, right ?
After studying his code), we can resume it as follows:

import binascii

from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF2
from Crypto.Hash import SHA1

password = "password"
salt = binascii.unhexlify('10f7445c8510fa40d9ef6b4e0f8c772a9d37e449')
iv = binascii.unhexlify('f3d19b2a45cdcccb')
data = binascii.unhexlify('8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b')

key = PBKDF2(password, salt, 24, count=1000, hmac_hash_module=SHA1)
c = DES3.new(key, DES3.MODE_CBC, iv)
t = c.decrypt(data)

print(binascii.hexlify(t))

This gives the following output:

b'856eef4556b5858c15477db17b95c5cb015d510b9f3710ce9d44f65d8b6cbd5da066ee9dd085c20dfa53782504040404'

a) the IV as mentioned in the extracted hash is now used, even as the whole data
b) no more xor
c) we see the padding \x04\x04\x04\x04 in the output
d) correctly tested on all my real-life login.keychains
e) his script uses the output in order to decrypt the content of the full keychain; so we know that this is a good technique

So, in the two cases, there is padding which is checked in order to validate the user password.

I do not understand how it is possible that two completely different techniques give both an output with same padding. Maybe you know an explanation for this?
Should this second technique give a speed profit for Hashcat ?

[philsmd]

@Banaanhangwagen yeah, these are good observations, but it's actually all about what I emphasized with my comment around data_decrypted (the full data_decrypted approach would decrypt the whole data starting with the IV from the hash itself).

At the end, it's all about the CBC mode of operation (see https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher_block_chaining_(CBC) and https://upload.wikimedia.org/wikipedia/commons/2/2a/CBC_decryption.svg)

For the first block you need the initialization vector (IV) from the hash generated by keychain2john.py... but if you use the shortcut (again mentioned in my perl code as a faster alternative) you need the previous ciphertext block (block size is 8 bytes for DES).

Therefore, for the shortcut you use just the last block as data and the second to last block as an "IV", if you want to decrypt the whole data instead, you need to start from the beginning with the IV from the hash.

Of course the shortcut is (in theory) much faster... we do not decrypt the whole data, but just the last 8 bytes.... in practice this change/speedup is negligible for 2 reasons:

1. all OpenCL compilers (yeah, they are most of the time clever, even if you have not the most optimized code... this should also work for C code with -O2 optimization or similar) will immediately see that we only need/use the results of the last decrypted block and therefore won't even compute the previous blocks. They will be skipped and therefore data_decrypted won't be allocated/computed, but only 8 bytes (last block)... and we need this block to check the last 4 bytes.
   JTR interestingly also specifies the full 48 bytes (CTLEN) here: https://github.com/magnumripper/JohnTheRipper/blob/2778d2e9df4aa852d0bc4bfbb7b7f3dde2935b0c/src/keychain_fmt_plug.c#L108 , but again this is probably optimized by the compiler
2. Compared to the 1000 iterations of PBKDF2-HMAC-SHA1, the decryption step is just negligible. It's way too fast, like a NOP (https://en.wikipedia.org/wiki/NOP_(code)). Of course decryption makes still a difference, but that difference is more about the data needed and computer (input/output) and hash format etc... for instance if we only would have to check for the 24 byte key instead of decrypting data... we probably wouldn't have the "problem" with the high rate of collisions (see discussion below):

---

I've discussed the problem of the likelihood of collisions for this hash format actually just a couple of days ago on a private chat with @jsteube on IRC and we actually did try to do the math correctly and see how high the rate of collisions could be:

1. Unfortunately, my "gut feeling" was spot on... actually I did even underestimate the likelihood of collisions a little bit. 32 bit (4 bytes) just aren't enough to prevent collisions for a good GPU Cracking rig.
2. We did the math with a 8-GPU rig of 2080 (not 2080 TIs which would be even faster).
3. The speed would be estimated about 4 times faster than -m 2500 = WPA (which uses also PBKDF2, it's somehow comparable, but with 1000 iterations keychain it faster).
4. Funny enough, the only thing that could slow it a little bit down, compared to a "normal" PBKDF2-HMAC-SHA1 is the "uncommon" output length of 24 bytes (the 3 DES "keys", each of them 8 bytes, 8 * 3 = 24). All of these 24 bytes need to be computed for the decryption key, there is no shortcut here, otherwise the decryption would be wrong (one bit wrong in the key => wrong output, as simple as that)
5. for the 8 x 2080 GPUs we estimate a hash rate of about 29359360 H/s
6. with only 4 "random" (but positional !) bytes to check in the decrypted output, the estimate is 1 collision every 150 seconds (with the speed and rig mentioned above)

So there you have it, at least every 3 minutes you will find a new password that could likely be a wrong password with the system above (especially if you try random passwords, i.e. use mask attack, brute-force it... with dictionary based attacks, it's a little bit lower, because of the less randomness in the input and the "slighlty" slower speed in -a 0/-a 1).

I therefore wouldn't say collisions are rare with only 32 bits to validate and "only" 1000 iteration of PBKDF2-HMAC-SHA1 (and output length 24 !!! <- yeah, that's important for speed ;) ).

We could still implement it, but we actually should really emphasize the importance of using --keep-guessing with this format (and of course it would be better if we find some further check we can perform, but the other problem is that we won't really use an incompatible format compared to JTR.... but our collaboration between JTR<->hc is actually quite good... therefore if we find a further check we can do, we could suggest JTR to update keychain2john.py and we both could be happier and need to worry less about collisions)...

btw: even a slightly greater padding, e.g. if it would be instead of 4 bytes 04040404 6 bytes: 060606060606 would reduce the likelihood of collisions significantly. A LOT ! but of course this depends on the data that is stored by the keychain format (the file encryption key, or the decrypted data that contains a key again... that's why it's random except for the last 4 bytes ... to decrypt the underlying data)

[philsmd]

btw: I just noticed that I completely forgot to mention that there is actually a third (and actually the better way to decrypt the last block)... instead of setting the initialization vector to "\x00" x 8, you just set it to the last sector straight away (you do not need to do the XOR !).

I only did that strange way of setting the IV to the zero IV because it's sometimes easier in perl to avoid setting c3 = Crypt::CBC->new () within the loop with the new IV or last ciphertext block.... i.e. we would need to have Crypt::CBC->new () called again and again in the main loop where decrypted_data was set... therefore I just did a trick with the zero IV (xoring with zero doesn't change the data) and afterwards xor with the correct IV ($t ^= $iv).

That means in python it would also work like this:

#!/usr/bin/env python3
  
import binascii

from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF2
from Crypto.Hash import SHA1

password = "password"

salt = binascii.unhexlify ('10f7445c8510fa40d9ef6b4e0f8c772a9d37e449')
data = binascii.unhexlify ('8c3c3b1c7d48a24dad4ccbd4fd794ca9b0b3f1386a0a4527f3548bfe6e2f1001804b082076641bbedbc9f3a7c33c084b')

iv = data[32:32 + 8]
d  = data[40:]

key = PBKDF2 (password, salt, 24, count = 1000, hmac_hash_module = SHA1)

c = DES3.new (key, DES3.MODE_CBC, iv)

t = c.decrypt (d)

print (binascii.hexlify (t))

here you see immediately that the "correct iv" is used straight away (the ciphertext of the second to last block).

[philsmd]

Okay, I've now decided to try to implement this new hash type with -m 23100 = Apple Keychain anyways (regardless of the high possibility of collisions or false positives): #2472
Please test the hash type either by compiling it yourself or after a new beta will be available (not yet uploaded, must be greater than hashcat-6.0.0+4 from https://hashcat.net/beta/ ) . Thanks

[Banaanhangwagen]

Thank you for your time and effort (and the small masterclass in encryption ;) )
Much appreciated!

I successfully cracked all my examples with -m 23100.
As you have expected and well explained, when doing a bruteforce, there were some false positives.

Finally, when doing a benchmark, we see that -m 23100 is +/- 3 times faster than -m 7100.

[philsmd]

wow, thank you very much for this quick responds and intensive testing.

Yeah, I agree that the new keychain hash type could be a good/quick alternative to the "normal" macOS user hashes...
but I tend to also be very careful when comparing hashes that are parameterized (iteration count) like -m 7100 with hashes with a fixed iteration count like the new keychain hash mode -m 23100 (1000 iterations).

I'm not sure if we can directly compare them, because the iteration count matters a lot.

I'm actually curious how macOS chooses the default iteration count. Is this a fixed value (for -m 7100 iterations) ? does it depend on the hardware performance or specs ? does it depend on the macOS version (maybe newer macOS versions have higher iteration count) ? what is the current default ?

I know we have some default iteration count for -m 7100 and example hashes with (quite low ?) iteration count.... but I'm not sure if (new and) real word examples also have low iterations count and if they are "always the same" for -m 7100 hashes nowadays.

It would be actually great if we had a wiki page with this information, about how iteration counts are determined depending on the hash type, if they are fixed or user-configurable or hardware-dependent etc.... we actually have several supported hash types like this... most notable the password managers hashes (keepass etc)... they often depend on the initial computer the encrypted file that contains the passwords was generated with (but not always the case).

The problem with such a wiki page would be, that it could very soon be outdated and there is nobody that can test each and every of those listed hash type regularily (and maybe even on different operating systems etc)... so it would be interesting to know these details, but hard to maintain an up-to-date and correct list.

Thank you