Re: [dm-crypt] LUKS header recovery attempt, bruteforce detection of AF-keyslot bit errors

[protagonist <listdump@depressiverobots.com>]

On 22.04.2017 20:02, protagonist wrote:

> I've manually compiled https://github.com/mbroz/pbkdf2_cryptsetup_test
> as well as cryptsetup itself to find possible improvements with
> different crypto backends, gcc optimizations such as -Ofast and
> -march=native, but I've been unsuccessful to improve on the 1.25M/s
> number so far. Openssl beats gcrypt, but the default kernel backend
> still seems faster.

Update: the nettle library is the fastest crypto backend by a
significant margin according to my tests. Also, contrary to my previous
remark, the kernel crypto appears to be slower than openssl, at least
under Debian Jessie with 3.16.
The sha1-performance can be grouped like this:
nettle > openssl > kernel 3.16 > gcrypt > nss

cryptsetup benchmark with libnettle runs at 1.68M/s:
PBKDF2-sha1      1680410 iterations per second for 256-bit key

This value includes benefits by switching the CFLAGS from "-O2" to
"-Ofast -march=native", which are mostly insignificant (<1% improvement)
and probably rarely worth the effort.

Switching from libnettle 4.7 to freshest libnettle 6.3 brings only minor
improvements:
PBKDF2-sha1      1702233 iterations per second for 256-bit key
Given that they provide hand-optimized x86 assembler code for the sha
computation, this is not entirely surprising.

> One could go even further and replace the time-consuming steps 5) and 6)
> with a routine that decrypts an encrypted part of the disk with the
> masterKeyCandidate and compares it to a known plaintext (or a more
> elaborate heuristic, such as several entropy checks looking for
> "correctly" decryptable areas on disk leading to low-entropy output),
> which might be a lot faster given AES-NI support and AES-xts throughput
> speeds, but since we don't know much about actual disk content, this
> seems to be too much of a gamble to be worth the effort at this point.
> It's easily thinkable one tests against several areas containing a
> well-compressed movie or a similarly high-entropy area, leading to a
> false-negative and missing the only correct master key.
Correction: I meant omitting steps 4) and 5).

While thinking about the disk layout, I've realized that the encrypted
storage almost definitely contains a LVM scheme commonly used by
full-disk encryption installer setups to store separate logical volumes
for both root and swap. In the related case of a manual setup of an
external storage device, this would often be plain ext4.

Now, there is more "known plaintext" available than I initially
suspected: both LVM and ext4 don't just contain special headers with
magic numbers, labels and checksums in well defined positions, but they
actually include at least one unused sector right in the beginning.
According to my tests, those bytes are set (or kept) to 0x00.

For LVM this is implied with the following specification:
"The physical volume label is stored in the second sector of the
physical volume." [^1]
Given the SSD sector size of 512 bytes and the fact that they reserve
four sectors for the label, we have at least three sectors à 512 bytes
of known zeros at sector #0, #2 and #3, which should be more than plenty
for some fast & simple decryption check that doesn't assume much about
the specific version and configuration of the logical volumes.

For ext4, the "Group 0 Padding" of 1024 Bytes would serve a similar
purpose. [^2]

Now that this shortcut seemed attractive, I've started cannibalizing the
LUKS_open_key() function in lib/luks1/keymanage.c to host my bruteforce
approach and made some progress already.
Small-scale benchmarking with 10000 rounds of AF-decryption, AF_merge
and (unfinished) block target decryption calls take about 50s combined,
including "normal" cryptsetup program initialization, initial disk reads
and most other necessary computations.
This sets overall performance at something in the order of 150 to 200
individual checks per second and core for the final routine, which is a
good improvement over the naive bruteforce version once it's ready.

Regards,
protagonist

[^1]
https://github.com/libyal/libvslvm/blob/master/documentation/Logical%20Volume%20Manager%20%28LVM%29%20format.asciidoc#2-physical-volume-label
[^2] https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Layout