need help with markov chain, or possibly another solution for decrypt of AES-256

[carmitchel]

I have a situation where the HEX key length is 32 bytes, however, these 32 bytes are simply eight repetitions of a 4 byte value (reducing the entropy source to a 32-bit value). This should be an instant brute force crack if I can figure out how I can instruct hashcat to use brute force, but repeat that 4 byte value to total 32 bytes.  I'd love to hear some suggestions.

As an example, some generated keys would look like this:

0100010001000100010001000100010001000100010001000100010001000100
7C687C687C687C687C687C687C687C687C687C687C687C687C687C687C687C68

6810681068106810681068106810681068106810681068106810681068106810

[undeath]

AES-256 is not a supported mode and what does this have to do with markov chains anyway?

[carmitchel]

AES-256 is not a supported mode and what does this have to do with markov chains anyway?

Ha, good point. I did not think to look since AES 256 is so common, I made an assumption. It will be easy to brute force manually I guess, by creating a dictionary of 4,294,967,296 sequential hex numbers. As I'm reading more about markov chains, you are right, it seems that it is the opposite of what I was thinking and certainly more complex. I'll look for a program that supports a dictionary attack of AES256. I'll probably code something to generate the hex number list, in case anyone needs that in the future

[undeath]

AES is a common encryption algorithm, not a hashing algorithm.

[carmitchel]

ô%ÝÏØXïþž¥åº‹q
G•¿ño\pnÔs¤o¨J…å„1hèá¨qφ)*EL››û|4ÁO­fëèSV"î"`¸ÁâOXþ0(òdË]#ÆIX†Ýj$úß

[atom]

If the keyspace is just 2^32 it would be easy to crack the key if you know the plaintext. The keyspace is so small, you wouldn't even need to do it on GPU, you can do it on CPU.

[carmitchel]

If the keyspace is just 2^32 it would be easy to crack the key if you know the plaintext. The keyspace is so small, you wouldn't even need to do it on GPU, you can do it on CPU.

I appreciate the reply. Excuse any improper terminology since I'm pretty new to the decryption community, but hashcat seems to be the most powerful tool out there and I've used it to decrypt LUKs volumes with great success. (whoops, excuse me undeath, automatically find the hash and produce the password so that I could decrypt in Linux)

In this case, there is no hash to find. The encryption was done by hardware directly to a hard disk and the sha1 hash which hid the key was lost due to a known bug in the hardware. I  know the plain text of the boot sector and NTFS boot record. Since we are not dealing with hashes and only decryption, what tool do you suggest to find the correct key and also to decrypt? I've started by creating a dictionary of 4,294,967,296 sequential hex numbers (all possible keys) and now I'm searching for a tool that could perform a dictionary attack, but maybe I am going in the wrong direction?  I'll definitely donate some btc for the help

[philsmd]

There are still some open questions here:
1. how do you know if the decryption worked correctly ? You at least need to know the key, the plain text and the cipher text (you didn't state that you have all of this information)
2. you didn't mention the details about the encryption algorithm e.g. the block cipher mode (ECB, CBC, OFB, CFB, CTR, XTS, OCB)

One straight forward way to find the correct key could be to just use the openssl command/executable or any scripting language (python/perl) to perform the decrypt+validate operations (hint: you could for instance divide the total keyspace 2^32 by the number of your cores - e.g. 8 or 12 or 16 etc - and let each "thread" compute just a subpart of the whole problem, like an external divide-and-conquer style)... or course this approach might not be the fastest one, but for this relatively small keyspace, it shouldn't take more than a few hours/days

of course you should first test if the approach you choose works with a known key+plaintext+ciphertext pair

BTW: your examples are really missleading (or at least not very clear), you say that the key is made of "eight repetitions of a 4 byte" but I think it is actually just 2 bytes repeated 16 times (at least that is what all of your examples look like, they all have 16 times the same byte values, i.e. if we assume that 0x7C is 1 byte and 0x68 another one).
Furthermore, you might also consider generating the keys on-the-fly without needing to read the disk all the time, this should be pretty fast and it might speed up the overall computation by removing the disk bottleneck

[carmitchel]

There are still some open questions here:
1. how do you know if the decryption worked correctly ? You at least need to know the key, the plain text and the cipher text (you didn't state that you have all of this information)
2. you didn't mention the details about the encryption algorithm e.g. the block cipher mode (ECB, CBC, OFB, CFB, CTR, XTS, OCB)

One straight forward way to find the correct key could be to just use the openssl command/executable or any scripting language (python/perl) to perform the decrypt+validate operations (hint: you could for instance divide the total keyspace 2^32 by the number of your cores - e.g. 8 or 12 or 16 etc - and let each "thread" compute just a subpart of the whole problem, like an external divide-and-conquer style)... or course this approach might not be the fastest one, but for this relatively small keyspace, it shouldn't take more than a few hours/days

of course you should first test if the approach you choose works with a known key+plaintext+ciphertext pair

BTW: your examples are really missleading (or at least not very clear), you say that the key is made of "eight repetitions of a 4 byte" but I think it is actually just 2 bytes repeated 16 times (at least that is what all of your examples look like, they all have 16 times the same byte values, i.e. if we assume that 0x7C is 1 byte and 0x68 another one).
Furthermore, you might also consider generating the keys on-the-fly without needing to read the disk all the time, this should be pretty fast and it might speed up the overall computation by removing the disk bottleneck

Thank you for responding. The encryption algorithm is AES 256-ECB You are correct that my examples are misleading, but the key length is definitely 8 repetitions of a 4-byte value (total of 32 bytes). A correct example would be: 7C6801007C6801007C6801007C6801007C6801007C6801007C6801007C680100  so I believe this reduces the entropy source to 32 bits. I thought that the AES key was all that is needed to decrypt the data if I know a portion of the unencrypted data. I do know a small portion of the data in plain text in it's unencrypted form.  I don't understand the ciphertext pair importance, so I am researching that now. Most documentation shows 0x20, but I have no idea how to use that.  I will post if I find more information.

[philsmd]

I was just trying to say that you should test your script/code/tool (that you use to decrypt+verify) with a sample data consisting of a key
with that specific pattern, the plaintext that you are searching for and the encrypted version of the plaintext.

Of course, just for testing if you approach/tool works, you do not need to try with all the 2^32 password candidates, but a very small subset of it (including the correct key) should suffice, just to make sure that your perl/python/C/whatever code works correctly.

... and yes, testing the decrypted data for a substring might work as well (but it shouldn't be too short, it should be at least 3-4 bytes long).

...
something like this might work to get an idea, linux bash shell script and/or perl version (don't blame me for this, it's just a very quickly coded POC, it could be that you might need to change some minor details about AES, padding etc)

Code:

#!/bin/bash

#
# Example (change these lines)
#

# example 1 (key is 7c6801007c6801007c6801007c6801007c6801007c6801007c6801007c680100):

#search_string="teststring"
#ciphertext="\x85\x8a\x32\xec\xea\xb9\x85\xdd\x89\x25\x47\xaa\xf6\x31\xe5\xb0"

# example 2 (key is 0000123400001234000012340000123400001234000012340000123400001234):

search_string="teststring"
ciphertext="\x29\x46\x14\x87\x62\x4a\xd4\x07\xcb\xbb\xb3\x6c\x87\x9c\x1c\xe4"

#
# Start
#

cores=$(grep -c ^processor /proc/cpuinfo)

keyspace=4294967296 # 2^32
part=$((${keyspace} / ${cores}))

offset=0

for i in $(seq 1 ${cores})
do
  begin=${offset}

  if [ "${i}" -eq ${cores} ]
  then
    end=${keyspace} # last one!
  else
    end=$((${offset} + ${part}))
  fi

  (
    #j=${begin}

    #while [ ${j} -le ${end} ]
    #do
    #  word=$(printf "%08x" ${j})

    #  echo -en "${ciphertext}" | openssl enc -d -aes-256-ecb -K ${word}${word}${word}${word}${word}${word}${word}${word} 2>/dev/null | fgrep -q "${search_string}"

    #  if [ "${?}" -eq 0 ]
    #  then
    #    echo "key found: ${word}${word}${word}${word}${word}${word}${word}${word}"
    #  fi

    #  j=$((${j} + 1))
    #done

    perl -MCrypt::Mode::ECB -e "my \$c = Crypt::Mode::ECB->new ('AES'); for (my \$i = ${begin}; \$i <= ${end}; \$i++) { my \$word = sprintf ('%08x', \$i); my \$key = pack ('H*', \$word x 8); my \$out = \$c->decrypt (\"$ciphertext\", \$key); if (\$out =~ m/${search_string}/) { print 'key found: ' . (\$word x 8) . \"\n\"; last; }}"

  ) &

  offset=$((${end} + 1))
done

echo "decrypting..."

for j in $(jobs -p)
do
  wait ${j}
done