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

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

[Jindrich Kolman]

[-- Attachment #1: Type: text/plain, Size: 604 bytes --]

About a week back, i was suddenly unable to open my luks-encrypted
partition. Mysteriously, a day later, it then worked again, but since
two days ago, i an again locked out. Would you be willing to share
your code, protagonist?


>My current memcmp of the first 512 bytes therefore works just as well on
>LVM as on ext4 and has managed to find a bit flip on a deliberately
>corrupted key slot.

>However, this is bad news for my ultimate target of recovering the
>actual master key of the SSD in question, as it seems my previous
>1-error checks have been unsuccessful, but valid.
>Regards,
>protagonist

[-- Attachment #2: Type: text/html, Size: 689 bytes --]

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

[protagonist]

Hello Jindrich,
could you get in direct contact with me and send some further technical
information regarding the affected drive / partition info / filesystem /
SMART values / .. ?
I'd be happy to help.
protagonist

On 24.11.2017 12:57, Jindrich Kolman wrote:
> About a week back, i was suddenly unable to open my luks-encrypted partition. Mysteriously, a day later, it then worked again, but since two days ago, i an again locked out. Would you be willing to share your code, protagonist?
> 
> 
>>My current memcmp of the first 512 bytes therefore works just as well on
>>LVM as on ext4 and has managed to find a bit flip on a deliberately
>>corrupted key slot.
> 
>>However, this is bad news for my ultimate target of recovering the
>>actual master key of the SSD in question, as it seems my previous
>>1-error checks have been unsuccessful, but valid.
>>Regards,
>>protagonist

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

[Arno Wagner]

On Sun, Apr 30, 2017 at 17:06:57 CEST, protagonist wrote:
> As a short update, I can confirm that when run with the default options,
> pvcreate initializes the first 512 bytes of the LVM header block with
> 0x00, similarly to ext4, creating excellent known plaintext that is easy
> to spot during debugging of decryption routines.
> 
> This is documented in the manpage of pvcreate:
> "-Z, --zero {y|n}
> Whether or not the first 4 sectors (2048 bytes) of the device should be
> wiped. If this option is not given, the default is to wipe these sectors
> unless either or both of the --restorefile or --uuid options were
> specified."  https://linux.die.net/man/8/pvcreate
> 
> My current memcmp of the first 512 bytes therefore works just as well on
> LVM as on ext4 and has managed to find a bit flip on a deliberately
> corrupted key slot.
> 
> However, this is bad news for my ultimate target of recovering the
> actual master key of the SSD in question, as it seems my previous
> 1-error checks have been unsuccessful, but valid.

Still impressive work. But it was a 10% thing at best.

Regards,
Arno

-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
A good decision is based on knowledge and not on numbers. -- Plato

If it's in the news, don't worry about it.  The very definition of 
"news" is "something that hardly ever happens." -- Bruce Schneier

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

[protagonist]

As a short update, I can confirm that when run with the default options,
pvcreate initializes the first 512 bytes of the LVM header block with
0x00, similarly to ext4, creating excellent known plaintext that is easy
to spot during debugging of decryption routines.

This is documented in the manpage of pvcreate:
"-Z, --zero {y|n}
Whether or not the first 4 sectors (2048 bytes) of the device should be
wiped. If this option is not given, the default is to wipe these sectors
unless either or both of the --restorefile or --uuid options were
specified."  https://linux.die.net/man/8/pvcreate

My current memcmp of the first 512 bytes therefore works just as well on
LVM as on ext4 and has managed to find a bit flip on a deliberately
corrupted key slot.

However, this is bad news for my ultimate target of recovering the
actual master key of the SSD in question, as it seems my previous
1-error checks have been unsuccessful, but valid.
Regards,
protagonist

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

[protagonist]

Good news:
my improvised simulate-AF-bitflip-and-decode bruteforce program based on
cryptsetup core code is working since yesterday. After finding several
issues in my initial code, including a failing call to the kernel crypto
API asking for a aes "xts-plain64" cipher (instead of the correct aes
"xts" version) that had me scratching my head and looking at strace
outputs for a while, I've managed to run it successfully against a
specially corrupted LUKS-encrypted disk containing an ext4 filesystem
(the first 512 bytes are guaranteed to be 0x00, as noted before) and
detected the error that was deliberately written to one of the AF
keyslot bits.

A run against the actual target device was unsuccessful, which could
have several reasons, including the fact that the LVM header might not
start with 512 bytes of 0x00, which is part of the decryption check
currently used. I will add a test against the magic "LABELONE" bytes in
the header for LVM-specific, but given the presence of ECC on most SSDs,
it's very unlikely I'll actually manage to find any undetected simple
error pattern and recover the disk data.

--

The brute force speed yesterday was 250 AF-keyslot changes per second
and core against the target.
Today I've managed to further improve this up to about ~285 iterations /
second and core by limiting the first-stage decode of the AF-keyslot
sectors to exactly those that were influenced by the bit flip. These
values are for aes-xts plain64, sha1 and a 512 bit masterkey.

Given that a 512-bit masterkey leads to 4000 * 512 bits of AF-keyslot
data, this gives (4000⋅512)/(285⋅60⋅4) = ~30 minutes of total bruteforce
duration on a modern quadcore CPU using four threads for trying a fixed
localized error pattern such as a single bit flip against the disk, as
long as the partial contents of a fixed sector are known, such as
ext4/LVM file header constants in sector #0 and #1.

The main processing time during bruteforce is spent on AF_merge(), which
in turn spends most of it's time on the diffuse() function that is
concerned with hashing the AF-key data (with the sha1 hash, in our
case). Note that there is no adjustable number of hashing operations for
this step, as opposed to other steps of the LUKS header decryption. It
is therefore obvious that a adversary with access to hashing
accelerators (GPU, FPGA, ASIC, see bitcoin hardware developments for
specialized hashing) can easily benefit from several magnitudes of
performance gain over the speed obtainable on a CPU without any
parameter to make this harder except changing to a more demanding hash
algorithm. (This has little impact on a CPU, as their speed differences
are within a factor of two)

IMHO this approach is only interesting for recovery purposes, but not a
real attack vector in terms of opportunity for significantly improved
offline attacks against a drive, as it only applies for the very rare
cases where an attacker has the complete password as well as almost all
of the AF data in their original form but lacks a few bits or bytes
(depending on his knowledge of the corrupted sections) that he now has
to test against.
If the diffuse() function and therefore the hash have excellent
cryptographic properties (which might not be the case), "reconstructing"
AF-sections on disk that were properly overwritten on the physical level
is be exponentially hard in a sense that quickly makes a brute-force
attack against the actual symmetric XTS key the better choice, at least
for this "naive" way of regarding the AF-keyslot as a large symmetric key.

A quick example of this:
* overwriting the first 4 bytes of your AF-keyslot with 0x42 0x42 0x42
0x42 with the intention to make it unusable will allow a break it within
~43 days ( (255^4)/(285⋅4⋅60⋅60⋅24) ) on a single desktop machine and
the current performance, and half that time that on average
* overwriting the first 64 bytes will lead to a similar complexity for
this bruteforce algorithm as trying the masterkey from null.
Note: There are likely other shortcuts, as hinted at before, so be sure
to overwrite as much of the LUKS header bytes in practice if you have
the intention of destroying it.

Looking for further opportunities at optimizing this bruteforce process,
it is clear that given the highly-optimized hashing code of the nettle
library mentioned before, we're unlikely to push significantly more
unique hash operations through a given core. But most of the hashing
operations and their results will be identical between the different
fault positions we're testing, at least as long as the processed data
hasn't changed yet compared to the last iteration (the simulated fault
is further down in the AFkeyslot), they don't all have to be performed
again each time. Maybe I'll manage to squeeze even more performance out
of this...

Regards,
protagonist

On 23.04.2017 22:03, protagonist wrote:
> 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
> 
> 
> _______________________________________________
> dm-crypt mailing list
> dm-crypt@saout.de
> http://www.saout.de/mailman/listinfo/dm-crypt
> 

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

[Milan Broz]

On 04/26/2017 04:45 PM, Hendrik Brueckner wrote:
> Hi Sven,
> 
> On Tue, Apr 25, 2017 at 07:09:35PM +0200, Sven Eschenberg wrote:
>> Am 25.04.2017 um 18:30 schrieb Milan Broz:
>>> On 04/25/2017 06:16 PM, Sven Eschenberg wrote:
>>>>
>>>> Furthermore, everyone who had access to /dev/mem and was able to locate
>>>> the keys knows, them. On second thought, this holds certainly true for
>>>> the 'new central kernel key storage' (Forgot the name), depending on the
>>>> allover kernel configuration and userspace, that is.
>>>>
>>>> At the end of the day dm-crypt (etc.) needs to store the key somewhere,
>>>> where it can be accessed at all times when an IO-Request comes in. There
>>>> is not that many options for that ;-).
>>>
>>> Crypto API stores the key in memory as well (even the round keys etc), obviously.
>>>
>>> We have already support for kernel keyring in dm-crypt (so the key will
>>> not be directly visible in dmsetup table), this will be supported in next major
>>> version of cryptsetup/LUKS.
>>>
>>> But as you said, if you have access to the kernel memory, it is there anyway...
>>>
>>
>> Ah, thanks Milan, kernel keyring it is called. Anyhow, the only
>> solution would be, to store the key in some device and retrieve it
>> for IO-Ops, but then again, it would make more sense, to pass the io
>> blocks to that (secured blackbox) device. Which would in turn mean
>> that such a device needs computational power and massive
>> IO-bandwidth.
> 
> a colleague of mine and I investigated in this kind of topic. For strong
> security, having the clear key accessible in the memory is not an option.
> Of course, the alternative, is to deal with hardware security modules (HSM)
> to perform the cryptographic operations by having the clear never leaving
> the HSM.
> 
> We worked on this area and provided some cryptsetup enhancements to support
> wrapped keys for disk encryption to prevent having keys in clear text in the
> memory of the operating system.  Recently, we submitted this merge request:
> https://gitlab.com/cryptsetup/cryptsetup/merge_requests/19

It would be better if you start new thread here about this because this
thread is really about something else.

Anyway, I will handle that merge request later but in short - your
approach works only IBM zSystem (no other system implements this
wrapped encryption, so it is very platform specific).

LUKS1 is portable format, we cannot bind the format to specific hardware.

So do not expect this to be merged as it is and specifically not to
LUKS1 format I consider stable and where it major advantage is
portability among all possible Linux distributions and architectures.

Anyway the discussion could be interesting. But I do not think
the mainframe approach can be applied to low-end systems where this kind
of FDE is mostly used. The FDE threat model is also usually focused
to offline systems (stolen disk) so here we do not need to care
if key is in memory when system is online.

Milan

> 
> Basically, it seamlessly integrates support for ciphers that can use wrapped
> keys instead of clear keys.
> 
> For Linux on z Systems (our background), there is a tamper-safe hardware
> security module (HSM) that provides "secure keys".  Secure keys are BLOBs
> containing the clear key wrapped with a master key of the HSM. Of course,
> the overhead is typically considerable because each cryptographic operation
> comes at the cost of an I/O operation to the HSM.  However, the z Systems
> firmware provides acceleration for this by re-wrapping a secure key to a
> protected key (that is valid for the Linux instance (LPAR) only).  Then,
> you can use some special instructions to perform, for example, AES with a
> protected key at CPU speed. In both cases, the clear key resides in the
> HSM/firmware only and is exposed to the OS in a wrapped form only.
> 
> The merge request above, also introduces this protected-AES (paes) as
> sample for a wrapped key cipher. (paes itself is an in-kernel crypto module).
> 
>>
>> Maybe crypto acceleration cards with PCIe3 and 8+ Lanes would be an
>> option, if they provide a secured keyring storage etc. . I am
>> thinking of something like the Intel QA 8950 with respects to the
>> concept. (The QA 8950 aims rather at communication streams, AFAIK, I
>> am not sure how keys are handled, i.e. if they are passed into the
>> adapter during engine initialization or if an additional permanent
>> secured keyring service is offered, or if the key needs to be passed
>> in for every block together with the data)
> 
> I am not familiar with the QA 8950, but there might be a similar approach
> possible as we did with paes. Perhaps, another kind of wrapped key cipher
> that fits into concept.
> 
> Thanks and kind regards,
>   Hendrik
> 

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

[Hendrik Brueckner]

Hi Sven,

On Tue, Apr 25, 2017 at 07:09:35PM +0200, Sven Eschenberg wrote:
> Am 25.04.2017 um 18:30 schrieb Milan Broz:
> >On 04/25/2017 06:16 PM, Sven Eschenberg wrote:
> >>
> >>Furthermore, everyone who had access to /dev/mem and was able to locate
> >>the keys knows, them. On second thought, this holds certainly true for
> >>the 'new central kernel key storage' (Forgot the name), depending on the
> >>allover kernel configuration and userspace, that is.
> >>
> >>At the end of the day dm-crypt (etc.) needs to store the key somewhere,
> >>where it can be accessed at all times when an IO-Request comes in. There
> >>is not that many options for that ;-).
> >
> >Crypto API stores the key in memory as well (even the round keys etc), obviously.
> >
> >We have already support for kernel keyring in dm-crypt (so the key will
> >not be directly visible in dmsetup table), this will be supported in next major
> >version of cryptsetup/LUKS.
> >
> >But as you said, if you have access to the kernel memory, it is there anyway...
> >
> 
> Ah, thanks Milan, kernel keyring it is called. Anyhow, the only
> solution would be, to store the key in some device and retrieve it
> for IO-Ops, but then again, it would make more sense, to pass the io
> blocks to that (secured blackbox) device. Which would in turn mean
> that such a device needs computational power and massive
> IO-bandwidth.

a colleague of mine and I investigated in this kind of topic. For strong
security, having the clear key accessible in the memory is not an option.
Of course, the alternative, is to deal with hardware security modules (HSM)
to perform the cryptographic operations by having the clear never leaving
the HSM.

We worked on this area and provided some cryptsetup enhancements to support
wrapped keys for disk encryption to prevent having keys in clear text in the
memory of the operating system.  Recently, we submitted this merge request:

https://gitlab.com/cryptsetup/cryptsetup/merge_requests/19

Basically, it seamlessly integrates support for ciphers that can use wrapped
keys instead of clear keys.

For Linux on z Systems (our background), there is a tamper-safe hardware
security module (HSM) that provides "secure keys".  Secure keys are BLOBs
containing the clear key wrapped with a master key of the HSM. Of course,
the overhead is typically considerable because each cryptographic operation
comes at the cost of an I/O operation to the HSM.  However, the z Systems
firmware provides acceleration for this by re-wrapping a secure key to a
protected key (that is valid for the Linux instance (LPAR) only).  Then,
you can use some special instructions to perform, for example, AES with a
protected key at CPU speed. In both cases, the clear key resides in the
HSM/firmware only and is exposed to the OS in a wrapped form only.

The merge request above, also introduces this protected-AES (paes) as
sample for a wrapped key cipher. (paes itself is an in-kernel crypto module).

> 
> Maybe crypto acceleration cards with PCIe3 and 8+ Lanes would be an
> option, if they provide a secured keyring storage etc. . I am
> thinking of something like the Intel QA 8950 with respects to the
> concept. (The QA 8950 aims rather at communication streams, AFAIK, I
> am not sure how keys are handled, i.e. if they are passed into the
> adapter during engine initialization or if an additional permanent
> secured keyring service is offered, or if the key needs to be passed
> in for every block together with the data)

I am not familiar with the QA 8950, but there might be a similar approach
possible as we did with paes. Perhaps, another kind of wrapped key cipher
that fits into concept.

Thanks and kind regards,
  Hendrik

-- 
Hendrik Brueckner
brueckner@linux.vnet.ibm.com      | IBM Deutschland Research & Development GmbH
Linux on z Systems Development    | Schoenaicher Str. 220, 71032 Boeblingen


IBM Deutschland Research & Development GmbH
Vorsitzender des Aufsichtsrats: Martina Koederitz
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294

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

[Sven Eschenberg]

Am 25.04.2017 um 18:30 schrieb Milan Broz:
> On 04/25/2017 06:16 PM, Sven Eschenberg wrote:
>>
>> Furthermore, everyone who had access to /dev/mem and was able to locate
>> the keys knows, them. On second thought, this holds certainly true for
>> the 'new central kernel key storage' (Forgot the name), depending on the
>> allover kernel configuration and userspace, that is.
>>
>> At the end of the day dm-crypt (etc.) needs to store the key somewhere,
>> where it can be accessed at all times when an IO-Request comes in. There
>> is not that many options for that ;-).
>
> Crypto API stores the key in memory as well (even the round keys etc), obviously.
>
> We have already support for kernel keyring in dm-crypt (so the key will
> not be directly visible in dmsetup table), this will be supported in next major
> version of cryptsetup/LUKS.
>
> But as you said, if you have access to the kernel memory, it is there anyway...
>
> Milan

Ah, thanks Milan, kernel keyring it is called. Anyhow, the only solution 
would be, to store the key in some device and retrieve it for IO-Ops, 
but then again, it would make more sense, to pass the io blocks to that 
(secured blackbox) device. Which would in turn mean that such a device 
needs computational power and massive IO-bandwidth.

Maybe crypto acceleration cards with PCIe3 and 8+ Lanes would be an 
option, if they provide a secured keyring storage etc. . I am thinking 
of something like the Intel QA 8950 with respects to the concept. (The 
QA 8950 aims rather at communication streams, AFAIK, I am not sure how 
keys are handled, i.e. if they are passed into the adapter during engine 
initialization or if an additional permanent secured keyring service is 
offered, or if the key needs to be passed in for every block together 
with the data)

And yes, I know, it would increase the IO Latency a bit, but offload the 
CPU at the same time.

Regards

-Sven

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

[Milan Broz]

On 04/25/2017 06:16 PM, Sven Eschenberg wrote:
> 
> Furthermore, everyone who had access to /dev/mem and was able to locate 
> the keys knows, them. On second thought, this holds certainly true for 
> the 'new central kernel key storage' (Forgot the name), depending on the 
> allover kernel configuration and userspace, that is.
> 
> At the end of the day dm-crypt (etc.) needs to store the key somewhere, 
> where it can be accessed at all times when an IO-Request comes in. There 
> is not that many options for that ;-).

Crypto API stores the key in memory as well (even the round keys etc), obviously.

We have already support for kernel keyring in dm-crypt (so the key will
not be directly visible in dmsetup table), this will be supported in next major
version of cryptsetup/LUKS.

But as you said, if you have access to the kernel memory, it is there anyway...

Milan

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

[Sven Eschenberg]

Am 25.04.2017 um 15:44 schrieb Dominic Raferd:
>
>
> On 25 April 2017 at 14:14, Robert Nichols <rnicholsNOSPAM@comcast.net
> <mailto:rnicholsNOSPAM@comcast.net>> wrote:
>
>     On 04/24/2017 06:49 PM, protagonist wrote:
>
>         However, I assume it is likely that a determined attacker running as
>         root might be able to extract the master key from RAM if the
>         encrypted
>         volume in question is still open at the time of attack, so
>         technically,
>         there would be a way to do this without the password.
>
>
>     It's trivial. Just run "dmsetup table --showkeys" on the device.
>
>
> Wowzer. 'cryptsetup luksDump <device> --dump-master-key' can also
> provide this info but it requires a passphrase, which 'dmsetup table
> --showkeys' does not. So must we assume that anyone who has ever had
> root access while the encrypted device is mounted can thereafter ​break
> through the encryption regardless of passphrases? At least until
> cryptsetup-reencrypt is run on the device, which is a big step.
>

Furthermore, everyone who had access to /dev/mem and was able to locate 
the keys knows, them. On second thought, this holds certainly true for 
the 'new central kernel key storage' (Forgot the name), depending on the 
allover kernel configuration and userspace, that is.

At the end of the day dm-crypt (etc.) needs to store the key somewhere, 
where it can be accessed at all times when an IO-Request comes in. There 
is not that many options for that ;-).

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

[Ondrej Kozina]

On 04/25/2017 04:37 PM, Robert Nichols wrote:
>
> BTW, it's "--showkey", not "--showkeys". Minor typo there, sorry.

In fact, it doesn't matter. As long as it's a unique substring of 
"--showkeys" (unique wrt to other --options known to dmsetup) dmsetup 
accepts even shorter version: i.e.: --showk

my 2 cents:)

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

[Robert Nichols]

On 04/25/2017 09:37 AM, Robert Nichols wrote:
> BTW, it's "--showkey", not "--showkeys". Minor typo there, sorry.

Upon review, "dmsetup" accepts option abbreviations as long as there is no ambiguity, so just "dmsetup table --sh" is sufficient.

-- 
Bob Nichols     "NOSPAM" is really part of my email address.
                 Do NOT delete it.

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

[Robert Nichols]

On 04/25/2017 08:44 AM, Dominic Raferd wrote:
>
>
> On 25 April 2017 at 14:14, Robert Nichols <rnicholsNOSPAM@comcast.net <mailto:rnicholsNOSPAM@comcast.net>> wrote:
>
>     On 04/24/2017 06:49 PM, protagonist wrote:
>
>         However, I assume it is likely that a determined attacker running as
>         root might be able to extract the master key from RAM if the encrypted
>         volume in question is still open at the time of attack, so technically,
>         there would be a way to do this without the password.
>
>
>     It's trivial. Just run "dmsetup table --showkeys" on the device.
>
>
> Wowzer. 'cryptsetup luksDump <device> --dump-master-key' can also provide this info but it requires a passphrase, which 'dmsetup table --showkeys' does not. So must we assume that anyone who has ever had root access while the encrypted device is mounted can thereafter ​break through the encryption regardless of passphrases? At least until cryptsetup-reencrypt is run on the device, which is a big step.

It's in the FAQ, section 6.10, so not really a great revelation.

BTW, it's "--showkey", not "--showkeys". Minor typo there, sorry.

Also, anyone who has had access to the device has had the ability to save a copy of the LUKS header, so the ability to revoke passphrases really isn't as great as it cracked up to be.

-- 
Bob Nichols     "NOSPAM" is really part of my email address.
                 Do NOT delete it.

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

[Dominic Raferd]

[-- Attachment #1: Type: text/plain, Size: 905 bytes --]

On 25 April 2017 at 14:14, Robert Nichols <rnicholsNOSPAM@comcast.net>
wrote:

> On 04/24/2017 06:49 PM, protagonist wrote:
>
>> However, I assume it is likely that a determined attacker running as
>> root might be able to extract the master key from RAM if the encrypted
>> volume in question is still open at the time of attack, so technically,
>> there would be a way to do this without the password.
>>
>
> It's trivial. Just run "dmsetup table --showkeys" on the device.


Wowzer. 'cryptsetup luksDump <device> --dump-master-key' can also provide
this info but it requires a passphrase, which 'dmsetup table --showkeys'
does not. So must we assume that anyone who has ever had root access while
the encrypted device is mounted can thereafter ​break through the
encryption regardless of passphrases? At least until cryptsetup-reencrypt
is run on the device, which is a big step.

[-- Attachment #2: Type: text/html, Size: 1498 bytes --]

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

[Robert Nichols]

On 04/24/2017 06:49 PM, protagonist wrote:
> However, I assume it is likely that a determined attacker running as
> root might be able to extract the master key from RAM if the encrypted
> volume in question is still open at the time of attack, so technically,
> there would be a way to do this without the password.

It's trivial. Just run "dmsetup table --showkeys" on the device.

-- 
Bob Nichols     "NOSPAM" is really part of my email address.
                 Do NOT delete it.

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

[protagonist]

On 24.04.2017 19:00, Dominic Raferd wrote:
> You seem to have considered the options pretty thoroughly. ​If the
> original owner has come to you, so s/he knows they have been typing in
> the same passphrase until one day it stopped working - and they have
> told you that passphrase, then an error in recording the passphrase can
> be discounted.
This is the case. The disk had been used in a privately owned laptop.

> Is there any possibility that a malicious third party (disgruntled
> ex-sysadmin perhaps) gained root access to the machine during its last
> session and changed the passphrase? As an aside, of no help to OP I'm
> afraid: is a prior backup of the LUKS header a protection against this
> scenario (i.e. against a subsequently deleted, or changed and now
> unknown, passphrase)?

If a malicious program had been able to run as root and deliberately
wrote into the LUKS header sectors to corrupt them, it definitely did so
in a very "plausible" fashion in terms of writing pseudo-random values
in the allowed areas. Given the fact that this was a fairly low-value
target, I doubt there was any reason to do this in such a "stealthy"
fashion if making the disk unusable had been the intention of such a
hypothetical malware. It's basically impossible to find out at this
point whether or not that was the case, but it's a scary thought that
should make everyone do header backups.

Regarding a "change" of passphrases:
A program would need access to the master key of the disk to create a
new, working key slot. As far as I know, a valid passphrase would be
needed during the normal cryptsetup procedures to open one of the
existing key slots, extract the master key and build the new keyslot
data containing a new copy of the master key.
However, I assume it is likely that a determined attacker running as
root might be able to extract the master key from RAM if the encrypted
volume in question is still open at the time of attack, so technically,
there would be a way to do this without the password.

I've asked the owner about mnemonics for the password, and they indeed
checked out, so I'd consider the passphrase integrity question as
settled in this case.

Regards,
protagonist

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

[Michael Kjörling]

On 24 Apr 2017 18:00 +0100, from dominic@timedicer.co.uk (Dominic Raferd):
> Is there any possibility that a malicious third party (disgruntled
> ex-sysadmin perhaps) gained root access to the machine during its last
> session and changed the passphrase?

Does that not require knowledge of a current passphrase? I believe it
does. Which of course said third party _could_ have.

> As an aside, of no help to OP I'm afraid: is a prior backup of the
> LUKS header a protection against this scenario (i.e. against a
> subsequently deleted, or changed and now unknown, passphrase)?

Yes. A copy of the LUKS header and a passphrase that was valid at the
time the header copy was made will allow access, as long as the master
key is unchanged (no cryptsetup-reencrypt in the interim). The only
way to mitigate this threat AFAIK is to change the master key of the
container.

-- 
Michael Kjörling • https://michael.kjorling.se • michael@kjorling.se
                 “People who think they know everything really annoy
                 those of us who know we don’t.” (Bjarne Stroustrup)

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

[Dominic Raferd]

[-- Attachment #1: Type: text/plain, Size: 1811 bytes --]

On 24 April 2017 at 14:26, protagonist <listdump@depressiverobots.com>
wrote:

>
>
> On 24.04.2017 07:50, Dominic Raferd wrote:
> >     On 22.04.2017 20 <tel:22.04.2017%2020>:02, protagonist wrote:
> >
> >     > I've manually compiled
> >     ​...​
> >
> >
> as the password has been written down on
> paper the old-fashioned way, I have decided to take it as a "known good"
> value.
> One can speculate about the password being wrong on paper, or some
> laptop-specific oddity, but as the owner had been entering it daily for
> more than a year, I don't think a simple single-character swap for
> neighboring keys or capitalization changes will help. In other
> situations, they might, and  bruteforce complexity only grows linearly
> with the number of changes and password length, respectively, if one
> looks for a single error, so it's definitely something to consider for
> passwords that can't be remembered perfectly.


You seem to have considered the options pretty thoroughly. ​If the original
owner has come to you, so s/he knows they have been typing in the same
passphrase until one day it stopped working - and they have told you that
passphrase, then an error in recording the passphrase can be discounted. If
the situation is otherwise then a wrong passphrase still seems to me more
likely than a corrupted LUKS header, especially when everything you can
test on the disk seems ok.

Is there any possibility that a malicious third party (disgruntled
ex-sysadmin perhaps) gained root access to the machine during its last
session and changed the passphrase? As an aside, of no help to OP I'm
afraid: is a prior backup of the LUKS header a protection against this
scenario (i.e. against a subsequently deleted, or changed and now unknown,
passphrase)?

[-- Attachment #2: Type: text/html, Size: 2603 bytes --]

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

[protagonist]

On 24.04.2017 07:50, Dominic Raferd wrote:
>     On 22.04.2017 20 <tel:22.04.2017%2020>:02, protagonist wrote:
> 
>     > I've manually compiled
>     ​...​
> 
> 
> ​This is pretty impressive stuff to someone like me who is new to
> dm-crypt. 
Thanks.

> But I wondered if the chances of the passphrase being
> misrecorded or misread have been fully considered.

You make a good point, but as the password has been written down on
paper the old-fashioned way, I have decided to take it as a "known good"
value.
One can speculate about the password being wrong on paper, or some
laptop-specific oddity, but as the owner had been entering it daily for
more than a year, I don't think a simple single-character swap for
neighboring keys or capitalization changes will help. In other
situations, they might, and  bruteforce complexity only grows linearly
with the number of changes and password length, respectively, if one
looks for a single error, so it's definitely something to consider for
passwords that can't be remembered perfectly.

> As it happens a single capitalisation error would be picked up by a
> brute force method that tests for a single bit flip...

This is not the case for any of the bit error tests discussed earlier,
as they concern the necessary "decryption ingredients" on disk where bit
errors may have occurred, which of course don't include the password itself.

Regards,
protagonist

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

[Dominic Raferd]

[-- Attachment #1: Type: text/plain, Size: 1500 bytes --]

On 23 April 2017 at 21:03, protagonist <listdump@depressiverobots.com>
wrote:

> On 22.04.2017 20:02, protagonist wrote:
>
> > I've manually compiled
> ​...​
>

​This is pretty impressive stuff to someone like me who is new to dm-crypt.
But I wondered if the chances of the passphrase being misrecorded or
misread have been fully considered. In your OP you wrote: 'The password is
fairly simple and contains no special characters or locale-sensitive
characters and had been written down... none of the characters change
between a US layout and the DE layout that was used. There are also no
characters that can be easily confused such as O/0.'

I note the 'written down' but if by this you meant 'recorded in a Word
document', say, then perhaps a capitalisation error has crept in. By far
the most likely is that the first character is recorded as capitalised when
it isn't (as Word likes to capitalise the letter at the beginning of a
sentence).​ Other possibilities include an extra space or spaces (at the
beginning or end?), or a period being read as part or not part of the
passphrase. It would also be worth re-reviewing the possibility that some
characters have been confused - if the passphrase was written down by hand
the chances greatly increase. And to be quite sure it isn't a keyboard
issue, can you try with a DE keyboard?

As it happens a single capitalisation error would be picked up by a brute
force method that tests for a single bit flip...

[-- Attachment #2: Type: text/html, Size: 2336 bytes --]

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

[protagonist]

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