Android Full Disk Encryption
#1
I was recently contacted by a person who at that point prefers to remain undisclosed and who provided me sample android encrypted disk images with the passwords to them.

I was able to identify the scheme use and write a fully-functional CPU plugin and GPU kernel in a day (mostly because it reused lots of my previous LUKS code).

The person wanted me to share the algorithm details with hashcat's community, so here are the details about that and here's how to validate the password.


* Needed data

The data needed is located in the image footer, exactly 16KB before the end of the file. It consists of the following:

4 bytes: "magic" should be 0xD0B5B1C4
2 bytes: major version (should always be 1)
2 bytes: minor version
4 bytes: footer_size
4 bytes: flags (unused)
4 bytes: spare1 (unused)
8 bytes: image size (unused)
4 bytes: failed password attempts (unused)
up to 64 bytes: ciphername (should be aes-cbc-essivConfusedha256)

Read the footer, skip (sizeof(footer_struct) - footer_size) bytes, then read the encryptedkey (16 bytes), skip 32 bytes, read the salt (16 bytes).

You should now have encryptedkey (16 bytes), salt (16 bytes)



* The algorithm:

It is a very very lightweight version of dmcrypt/LUKS with all the anti-forensic split/merge stuff removed, PBKDF2 iterations hardcoded to 2000 and block decryption mode of operation set to aes-cbc-essivConfusedha256. So here is how a password is converted to key and how the key is used to decrypt:

1) Password is passed through PBKDF2-SHA1 using 2000 iterations, the 16-byte salt found from the image footer. Output is 32 bytes, so in effect you have double the iterations because sha1 output is just 20 bytes, not 32.

2) Decrypt the encryptedkey using AES-128 in CBC mode with the first 16 bytes of PBKDF2 output as key and the next 16 bytes as IV. You will get the decrypted_key, 16 bytes long.

3) Using the decrypted_key you can now decrypt device from the byte 0, using CBC-ESSIV mode, which works like that:

3a) Get the SHA256 hash of the decrypted key
3b) Use it as AES256 key to encrypt a 4-byte integer, which is the sector number (each sector is 512 bytes)
3c) The result is the "sector key" which is then used to decrypt the sector data using AES128-CBC. You can decrypt at most 512 bytes, the next sector is encrypted with different key (which is derived from decrypted key and sector number).


* Password validation

That was a bit tricky and there is possibly a faster way, but here is what I came with (requires 2 sectors of 512 bytes to decrypt). It is based on the fact that only FAT and ext4 filesystems are supported. You can use the following documents:

http://www.nongnu.org/ext2-doc/ext2.html#SUPERBLOCK
http://www.tavi.co.uk/phobos/fat.html

So for the first case (FAT filesystem) you need to decrypt the first several bytes of sector 0, get the 8 bytes at offset 0x03, compare them with "MSDOS5.0" and you are basically OK.

For the ext3 case it is a bit more complicated. Read and decrypt sector 2 (1024-1536 bytes). Then take advantage of the fact that s_creator_os, s_rev_level are 32-bit values that should never be bigger than 4, s_minor_rev_level is a 16-bit value that should also never be higher than 4.


Voila. Speeds are over 250K c/s on 7970 and potentially can get much higher if we do everything on the GPU rather than transferring back to host to perform decryption and comparisons.

Hope that's helpful.
#2
It is indeed! Many thanks for sharing gat3way!
#3
If you decrypt the second AES block in the superblock, then you can test the following which gets you around 1 in 2 ^ 92.3:
Code:
Offset (bytes) | Size (bytes) | Description
---------------+--------------+---------------------
1040           | 4            | s_free_inodes_count
1044           | 4            | s_first_data_block
1048           | 4            | s_log_block_size
1052           | 4            | s_log_frag_size

Code:
// exact: s_first_data_block == 0 || (s_first_data_block == 1 && s_log_block_size == 0)
if ((unsigned int) s_first_data_block < 2)

// assumes max block size is 32MiB
if ((unsigned int) s_log_block_size < 16)

// assumes max fragment size is 32MiB and (min is 1 byte)
if ((int) s_log_frag_size >= -10 && (int) s_log_frag_size < 16)

// volume_size_KiB is 32 bit if the volume is less than 4 TiB
if ((unsigned int) s_free_inodes_count < volume_size_KiB >> s_log_block_size)

Also I think s_free_inodes_count is signed so that gives you another bits worth of validation.
#4
Hi gat3way,

This is great information. I just need to whether

Is the image provided by the undisclosed person from rooted device? If it is not then is it from a bootloader locked or unlocked device?

Best,
Jack
#5
I'm about to add this algorithm to oclHashcat.

Does anyone know if this algorithm has been changed in the meanwhile (new android versions)?
What about the FileSystems, any change here?
#6
I just finished a first working beta, speed ~ 364kH on 290x, stock clocked.

I'm using s_first_data_block, s_log_block_size and s_magic, which contains a static value:

EXT2_SUPER_MAGIC of value 0xEF53
#7
https://source.android.com/devices/tech/...ation.html hasn't changed that I know of except Android 4.3+ now enables the allow_discards dm-crypt parameter, which issues the TRIM command to underlying flash storage. Great beta, will try it out on the master branch build. Most Android FDE passwords are simple because its tied to the screen unlock password (unless user has root/SU) and nobody wants to enter a high entropy pword multiple times per day.
#8
Any info on what format v1.30 expects for Android FDE? Neither the full crypto footer, nor a hex encrypted key seem to work.
#9
What is hash format for Android FDE? Hash example wiki article says :"8800 Android FDE (to be added)"...
#10
You should read oclHashcat v1.30 release note's.