No key available for this passphrase

Hello,

I have quite a problem here with my notebook (debian squeeze and luks/dm-crypt encrypted LVM).
After shutting it down yesterday, it did not let me unlock the encrypted disk this morning.

I already found the post from September 2012 in the mailing list, but it did not exactly match my case (everything looks fine, not overwritten by SWAP data)

Header Information looks OK to me:

 # cryptsetup luksDump /dev/sda2
LUKS header information for /dev/sda2

Version:        1
Cipher name:    aes
Cipher mode:    cbc-essiv:sha256
Hash spec:      sha1
Payload offset: 2056
MK bits:        256
MK digest:      53 44 c2 4d b0 9e c5 73 ef fa d7 12 4f dd f0 75 64 3b 88 ad 
MK salt:        50 5f a9 69 21 6e 21 ac db 09 bd 79 b0 9b 9b 1e 
                14 2a 5d e4 46 2b 4d 9c 49 e3 9f 7d f9 d7 64 84 
MK iterations:  10
UUID:           b89fe8ad-3aea-4f27-9448-06e75fd8a05a

Key Slot 0: ENABLED
Iterations: 75899
Salt: 2d 2b 66 4c 57 eb ff e7 7f 63 14 8f c5 3b 6b aa
38 53 2d 52 52 b6 d9 cc 84 b0 1a 11 bd cf 88 70
Key material offset: 8
AF stripes: 4000
Key Slot 1: DISABLED
Key Slot 2: DISABLED
Key Slot 3: DISABLED
Key Slot 4: DISABLED
Key Slot 5: DISABLED
Key Slot 6: DISABLED
Key Slot 7: DISABLED

Looking closer to the header (exported to file via luksHeaderBackup), right after the initial information also shown by luksDump up to address 0x1000 (first keyslot) is filled with zeroes, from 0x1000 until the end of the file random data with no ASCII that would indicate files (e.g. header informations) or a partition table.

The key slot checker though, gives me this output:

./chk_luks_keyslots /home/r4pt0r/notebook/luksheader.img

Sectors with entropy below threshold (0.850000):

Keyslot 0: start: 0x1000
position: 0x10000 entropy: 0.625023

Keyslot 1: start: 0x21000
keyslot not in use

Keyslot 2: start: 0x41000
keyslot not in use

Keyslot 3: start: 0x61000
keyslot not in use

Keyslot 4: start: 0x81000
keyslot not in use

Keyslot 5: start: 0xa1000
keyslot not in use

Keyslot 6: start: 0xc1000
keyslot not in use

Keyslot 7: start: 0xe1000
keyslot not in use

So the entropy seems to be too low? But where does the address 0x10000 come from? shouldn't the key start at 0x1000 similar to its slot?

I HAD an backup of the header on USB stick - the Notebook was set up around 3-4 years ago but i really found my old backup-stick (32MB) where also gpg-keys and other small files were backed up.
BUT: the stick seems to be broken :( It's not recognized by any PC and the LED doesn't light up...

As the Notebook is usually put to sleep-mode I really can't remember what updates were installed since the last reboot.

Is there any possibility the key is not damaged and data can be recovered?

Thanks for any help!

Sebastian

Answer below inline.

That is far too low. Your key-slot has been compromised. Have a look specifically at offset 0x10000, the problem seems to be only in the 512 bytes starting there.

You can use option -v to get a hex-dump of that sector.

No. Sorry. Maybe professional data recovery for the stick?

The only thing without header backup is to find out what actually did the damage. Interesting in its own right, for prevention. Please post your findings here!

Arno

Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: [email protected]
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Well, it could have come to my mind to look at this address...

Offset 0x10000:

0000000 gpt LUKS�� ext4dev extended linux-swap(v1) linux-swap(new) linux-swap(v0) linux-swap(old) hfs hfs+ ReIsEr4 LABELONE LVM2 _BHRfS_M
- The file system is damaged linux-swap ufs create new %1 file system udevsettle udevsettle --timeout= udevadm settle --timeout= set partition type on %1 new partition type: %1 using libparted shrink file system grow file system resize file system delete partition Unable to find mount point ====================== libparted : ^(/[^ ]+) create empty partition path: %1 calW

How on earth did that end up here and what could have caused it? After this it looks perfectly random again...

Urks. Looks like a fragment from a menu or script?

No idea.

As expected. The entropy-test is pretty sensitive.

Arno

Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: [email protected]
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

Sorry to bother again, but I'm trying to understand the whole processing of keys/password/masterkey within the LUKS mechanism when unlocking/decrypting the disk.

I'm trying to understand it by using fugure 5 in this paper:
http://wiki.cryptsetup.googlecode.com/git/LUKS-standard/on-disk-format.pdf

Lets use my header as example (it's useless now anyways...)

LUKS header information for /dev/sda2

Version:        1
Cipher name:    aes
Cipher mode:    cbc-essiv:sha256
Hash spec:      sha1
Payload offset: 2056
MK bits:        256
MK digest:      53 44 c2 4d b0 9e c5 73 ef fa d7 12 4f dd f0 75 64 3b 88 ad 
MK salt:        50 5f a9 69 21 6e 21 ac db 09 bd 79 b0 9b 9b 1e 
                14 2a 5d e4 46 2b 4d 9c 49 e3 9f 7d f9 d7 64 84 
MK iterations:  10
UUID:           b89fe8ad-3aea-4f27-9448-06e75fd8a05a

Key Slot 0: ENABLED
Iterations: 75899
Salt: 2d 2b 66 4c 57 eb ff e7 7f 63 14 8f c5 3b 6b aa
38 53 2d 52 52 b6 d9 cc 84 b0 1a 11 bd cf 88 70
Key material offset: 8
AF stripes: 4000

So when I enter the Password, it is processed by PBKDF2:

pwdPBKDF2ed = PBKDF2 (
entered password,
Salt for Key Slot 0 as given by header (2d 2b 66 4c ....), iteration-count (=75899),
MasterKey lenth (256 bits)
)

Am I correct about MK-lenght = MK bits?

Then it reads the encrypted key aka payload:

encryptedKey = data from "payload offset (sectors*size)" * "key leghth" -> offset 8 sectors * 512 byte = 4096 = 0x1000
key lenght = 4000 * original key lenght of the master key (256bit) that would be 128000 byte -> address 0x1000 + 128 000 byte = address 0x20400 correct?

so "encryptedKey" = data from 0x1000 - 0x20400 (including 512 of crap from 0x10000 in my case...)

now we put those 2 together and add some magic:

splitKey = decrypt (
use aes/cbc-essiv:sha256 algorithm, pwd-PBKDF2ed calculated first by entered password, encrypted key data read from 0x1000 - 0x20400, "encrypted" ???
)

what is "encrypted"? The comment "content lenght" for it confuses me even more...

With this splitKey we now create a checksum:
masterKeyCandidate = AFmerge (
splitKey (ft. magic(TM) ),
masterKeyLength (256),
ks-stripes (4000)
)

And process the checksum to compare with the MasterkeyChecksum from header:
PBKDF2 (
masterKeyCandidate,
phdr.mk-digest-salt ( 50 5f a9 69 21 ....),
phdr.mk-digest-iter (10),
LUKS_DIGEST_SIZE (20)
)

if this processed Checksum is equal to the MK digest from header (53 44 c2 4d b0 9e c5 73 ef fa d7 12 4f dd f0 75 64 3b 88 ad ) the partition gets unlocked.

Oh, and just hypothetical:

If I would write a script to replace the broken 512 bits of the "encryptedKey" sequential from 00 00 00... up to FF FF FF... values, we would have 512^255 possible combinations.
Lets assume we can try 1000 combinations per second in one process (I have no idea whether this is realistic) and also assume we have a 8-core system available for running 8 processes, starting at different offsets, it would still take 2,896966378463778741e+679 years.... (OK, some factor for mathematical probability when starting at 8 offsets will be added, but i think it's negligible...)
Well, until theres a way to travel near speed of light to make use of time dilatation, the data is gone forever ;)

So i'm still grep-ing the disks of my network-fileserver, maybe i had another backup of the header... Lesson learned, new drives for the fileserver ordered so i can backup more complete and more often...

Don't worry, just ask. If it is redundant or documented, we will tell you were to look.

Yes.

Yes. But note that for XTS mode, the mode and the cipher each get half of the master key.

Yes, for the 1st slot.

Yes, again 1st slot.

Yes.

Now I am starting to have to look this up as well ;-) If you just AF-split the MK, everybody can recover it, as long as all bits are intact. The non-encrypted AF-split MK (spkitKey in Fig. 4/5) is still the MK, but represented in a "blown-up" form. Hence it is stored encrypted just the same as data in the data area gets encrypted later. The "encrypted" (content length) parameter just tells the decrypot function on how much data passed by reference in "encryptedKey" here, it is supposed to work, i.e. it is just the keyslot-lenght. Figure 5 is ommiting some details and has some fuzzyness, don't let it confuse you. The decryption in Figure 5 is exactly the reverse of the encrypt in Figure 4.

Yes.

Yes. The PBKDF2 iteration is necessary as otherwise the master-key might be brute-forced using this checksum.

Yes. Otherwise, try again with next key-slot.

256^512. It is a bit more, not that it matters ;-)

Depends on your hardware and the hardware the LUKS header was created on. The iterations are selected so that unlocking one key-slot takes 0.25 sec. (The master key needs less iteration than passphrases, as it is high-quality random material.)

That gives you 32 keys/second.

It is a factor of 2. The expected number of tries is that you have to search half the key-space.

This takes then 5.4*10^1223 years.
(With your 512^256 still 1.9*10^684 years, so your math is ok.)

Don't also foget that a typical CPU only has a lifetime of 30 years before it breaks down...

Second lesson: Flash-keys are unsuitable for long-term storage (has to tell that one customer already that wanted to store an important master key that way. Fortunately they asked us first...)

Here is a way for reliable long-term storage of small anounts of data:
Print it with a laser-printer as OCR-A/B on good paper. Adding per-line checksums might be a good idea.
Or print it as a sequence of QR codes - checksums and error correction already included.

The other oprion is to store it in multiple locations and check the date regularly.

Arno

Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: [email protected]
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

I like the idea of printing it as QR-code, never thought of using QR-Codes for backups ;)
I will consider it for the ne setup!
Should be also usable for gpg-keys...

Another idea I had yesterday evening:
I'm using a small ramdisk on my normal PC for playing minecraft - it meanwhile has a rather blown-up code and writes frequently to disk, causing slower machines to "hickup" every ~3 seconds. increasing read/write speed by using a ramdisk eliminates these symptoms.
I use a small shellscript for initiating the ramdisk, cloning the data and syncing it.

So, why not use such a mechanism (to ramdisk or normal disk) for backing up the header on boot time, and on shutdown comparing the backup with the current header. If equal -> everything is fine. If not - prompt either to restore it or leave it (when adde a new key e.g.), maybe even with a "diff"-output.

It won't replace the real backup(s), but will give a little more failure tolerance plus a warning on shutdown IF anything went wrong with the header, so e.g. when on travel far away from backups you could restore the header. As the backup won't contain anything else than the header already does, I don't think it adds vulnerability to the system. If anyone gets access to the running system he could gain access to the header (and the key in the memory!) anyways.

I think i will give this a try on the new setup on my Notebook. I can post the script here at the mailing list (it will be only a shellscript - my C has never evolved far over "hello world" ;) ), but a function like this or any other mechanism of header-protection would be nice to see as standard for LUKS. Especially because the first keyslot is so likely to be corrupted by partition managers (should be aroud the offset of keyslot 0 where they start to dump their data?).

Sebastian

[..]

has there been any study to find out which ones of the keyslots is most likely to get corrupted accidentally by various tools?

will adding keys from the last slot going backwards add some protection from keys being inaccessible due to accidental header corruption by various tools?

I do not think there is enough data. And there is the additional problem that corruption in others than slot 0 will not be noticed by most users. You are welcome to search the mai,ing-list archives and generate a statistic, of course.

I think most tools will kill the header. After that, damage to key-slots does not matter much, as the header carries the all-iportant salts. While it does happen occasionally that just a key-slot gets corrupted, it is rare. The keyslot-checker I wrote was not due to a dire need, but because I hacked together a version in Python that read the disk directly in a 2-3 hours, and then Milan (rightfully) asked me to do it right. Provided entertainment for me for a weekend and an opportunity to look at libcryptsetup. I think we may have seen someting like 5-6 cases altogether in the last few years. No idea how many people managed to kill their LUKS containers, but never reported it on the list.

And anyways, disks do die, so data-backup is mandatory even for encrypted volumes. See the FAQ for some suggestions.

Arno

Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: [email protected]
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
One of the painful things about our time is that those who feel certainty
are stupid, and those with any imagination and understanding are filled
with doubt and indecision. -- Bertrand Russell

As soon as I received my new harddrive for the notebook (the one delivered constantly makes fast scratching noises at idle...), i will start to write a small script that backups the header on the disk and frequently compares this backup to the disk/partition header. If changes are detected it will give a warning plus the option to restore the header.
Well - thats the plan. Will see what functions will make it to the script or will be added while writing it.

It will be only a shellscript ( need glasses - I can't C very good ;) ), but i will post it here (maybe new thread) as soon as it is working.

Sebastian

just added a functionality in my tool to check if a header on a device matches a header in back up file.

A test of the functionality is below.

1. Get a header backup
[ink@mtz ~]$ zuluCrypt-cli -B -d /dev/sdc1 -f headerbackup.luks
SUCCESS: header saved successfully

2. Check if the header on the device matches the one in a header file [ink@mtz ~]$ zuluCrypt-cli -H -d /dev/sdc1 -f headerbackup.luks header backup match the one on the device

3. Add a key to a volume to change the header. [ink@mtz ~]$ zuluCrypt-cli -a -d /dev/sdc1 -y xxx -l zzz
SUCCESS: key added successfully

4.Check if the header on the device matches the one in a header file [ink@mtz ~]$ zuluCrypt-cli -H -d /dev/sdc1 -f headerbackup.luks header backup does not match the one on the device

So far,it seem to be working as expected.

Your shell script will be much simpler if you use my tool :-)

The commit is at :
http://code.google.com/p/zulucrypt/source/detail?r=ee03cb7b3c0d698fb68de0591a192ce06009c550