Our LUKS fde may not be enough anymore

General Privacy & Security
1

Here I want to report on an article https://mjg59.dreamwidth.org/#entry-66429 I read on Matthew Garrett’s blog https://mjg59.dreamwidth.org
In his post, he is telling the story of a French activist who was arrested and his laptop seized. The man thought he was safe because his data were LUKS2 encrypted, with a very strong passphrase - the kind that no ordinary people could ever remember: it was 20+ characters with a mix of cases, numbers, and punctuation.
But surprisingly so, the police was able to decrypt the FDE partition and could use the plaintext as evidence against him.
So, how could this have happened, considering that:

  • the guy never disclosed his password willingly or under threat
  • he was not “physically brute-forced” to do so (French don’t do this)
  • it doesn’t seem like there was any op-sec failure (e.g. his password written somewhere on a piece of paper or inside a smartphone, a keylogger, Evil Maid, stealth filming, password recycling, suspend-to-ram…)

Considering those facts, Garrett came up with a startling conclusion: the remaining possibility is that his high entropy passphrase was successfully brute-forced!
Now, if the French authorities can do this, we have to assume that just about any State actor can also do it (not that they would be considered particularly bad at cracking ciphers, but the implication is that this is now only a matter of shelling out millions $$ to buy loads of high-end GPUs.) If this is indeed the case, I would also suspect that very well resourced agencies have been able to do it for years.
To understand the problem, we have to look at how LUKS works: the final masterkey (AES) used to encrypt/decrypt the block device on-the-fly is encrypted via an intermediate key. This secondary key protecting the AES masterkey is itself the result (the output) of a computation called a Key Derivation Function (KDF) which takes a passphrase or a keyfile as an input. This scheme is so designed that when you want to change your passphrase (e.g. if you suspect it was breached), you can do so without having to re-encrypt the whole partition; same thing if you want to add another password or keyfile. Each password resides in a different key slot of the LUKS header, but the masterkey always remains the same.
When LUKS was first devised, it supported only one such KDF algorithm: PBKDF2, which is extremely “computationally expensive”. At the time, it was thought that brute-forcing it was realistically impractical. The technology just wasn’t there given the enormous number crunching involved. However later on with the LUKS2 specification, the designers took into account that ultimately sometime in the future this would become feasible; so they provided additional KDF algorithms that would be expensive not purely in computation but in other ways. One such new algorithm is argon2id - it is “memory expensive”.
To explain the concept, I am quoting Matthew Garrett who put it so clearly:

<<If the KDF algorithm requires a significant amount of RAM, the degree to which it can be performed in parallel on a GPU is massively reduced. A Geforce 4090 may have 16,384 execution units, but if each password attempt requires 1GB of RAM and the card only has 24GB on board, the attacker is restricted to running 24 attempts in parallel.>>

Looks like it may be time to switch to such safer KDF as argon2id. Unfortunately, it is not the default KDF when a LUKS2 container is first created - most likely all your active keyslots are still pbkdf2. In his article, Garrett then goes on explaining how to proceed. Be warned, though, that this is not for everyone to attempt if you don’t clearly understand what those cryptsetup cli do: it could quickly end up in a disaster, loss of partition or unbootable system.
I have tried his procedure on a Qubes laptop and this was easily done. There was no need to convert from LUKS to LUKS2, and only one keyslot was active (it was pbkdf2 although I had clean-installed v4.1)
It’s a different story for PureOS: there could be as many as 3 active keyslots, depending whether you ran the smartcard-key-luks script or not. I found it much trickier, because all keyslots have to be converted to argon2id or killed; and it is not obvious to determine which keyslot is what (in my case, slot0 could be killed - it was created at install time for purpose of having separate encrypted /home or other partitions; slot1 was the main passphrase and slot2 was the smartcard-key-luks unlock scheme)
Special care should be taken if you use GRUB2 as a bootloader (e.g. coreboot/seabios) and you have an encrypted /boot: it seems that GRUB2 is not [yet] able to handle argon2id - resulting in an unbootable system.

4 Likes
2

Hey, I’m a Librem 5 customer who really likes my Librem 5 but hasn’t totally escaped the dangerous ecosystem of nonfree software outside of that (and so you may wish to take everything I say with a grain of salt).
But I happened to see your post, and that left me wondering – should I always assume that the government of the country where I reside has more money and capabilities than I do, and accordingly will always be able to break into my computer if their goals truly depend on it?

Even if I have encrypted my hard drive, the software has to unencrypted the drive in order to run. What if this French activist forgot to power off his computer while he was being arrested? Is it possible that the primary gain of an encrypted hard drive is really only that if I lose my laptop at an airport, then by the time the thief can read about how LUKS works he will have already lost interest and focused onto something else?

1 Like
3

I don’t buy it.

Let’s try doing the math:

20+ characters with a mix of cases, numbers, and punctuation.

Okay, the alphabet has about 25 characters, that’s 50 is we include upper- and lowercase, plus 10 for the digits, plus say 10 punctuation characters, that gives us 60 characters.

With the length of 20 characters, the number of possible combinations becomes 60^20 = 365615844006297600000000000000000000 which is about 10^36 possible combinations.

Now assume a huge processor frequency of 10 GHz, and assume it takes only a single instruction to test a password. Of course in reality it takes more, depending on the key derivation function, so the brute-force attack is in reality harder than what we assume here.

Then using a single processor we could test 10^10 combinations per second.
Using a GPU with 100000 such processor cores → 10^15 combinations per second.
Using one million such GPUs → 10^21 combinations per second.
Running the brute-force attack for 24 hours (86400 seconds) → about 10^26 combinations.

We are then still a factor of 10^10 away from the needed 10^36 combinations.

If we run for a whole year, that’s 365 days, we’re still more than a factor of 10^7 away from the needed 10^36 combinations.

So using that setup with the one million GPUs assumed above, it would take 10 million years.

Did I get that right?

3 Likes
4

No, I don’t think you need to assume that, it depends on how well you protected your computer.

That is a possibility, then the police would not have needed to worry about the LUKS passphrase.

That is certainly one advantage :slight_smile: but I think that with strong enough passphrase(s) you can be protected also against a more patient thief.

3 Likes
5

Partly. There are a lot of passwords that can be ignored. You know the person has high security standards? Don’t even try all the passwords with only characters, only numbers, only upper characters, only punctuations etc or even those who are kinda short.

Another thing could be a trained AI that is trained by leaked passwords to create a list of passwords with higher and lower priority to raise the chance that the needed password will be found earlier of the brute force attack.

But that’s no magic. At the end it speeds up in theory, but in reality it shouldn’t make a huge difference to the result. I also had the thought that we’re missing an important information.

1 Like
6

Yes, this should be noted: the calculation I tried to do above assumed that all 60^20 combinations really need to be tested. So there is another assumption that I did not mention: when the password was created, each character was picked randomly from the set of 60 possible characters.

If the password included some parts that were dictionary words, or just sequences of digits, or whatever else that makes it easier to guess, then the number of combinations to test could be reduced a lot.

For example, picking randomly could give something for example like this:

N0e)hqKGa.ZbWvcEzb.R

and then the attacker would need to test all 60^20 combinations.

If the password had been built up from easy-to-guess parts as in the following example

732fruit#ACCORDINGLY

then instead of testing all 60^20 combinations the attacker could get away with far less. For an easy calculation, assume that the attacker somehow knows the pattern of “3 digits followed by lowercase dictionary word followed by punctuation char followed by uppercase dictionary word”, then the number of combinations to test would be something like 1000 * N * 10 * N where N is the number of words in the dictionary. If we take N to be one million words, then the number of combinations becomes about 10^16 so now the brute-force attack could easily succeed.

So if a password consists of “20+ characters with a mix of cases, numbers, and punctuation” as it was described in this case, it is important what kind of “mix” it is, to make it really strong it needs to be close to randomly picked characters. And why not also make it 30 characters instead of just 20.

7

I think it is dangerous to form any conclusion on such limited information. His conclusion is definitely a possibility but it is not where I would go first.

That substantially underestimates the number of punctuation characters. The number to use in this context is well known: 95

(assuming all printable ASCII characters are fair game - but no need to get fancy to get that number1 - and this does assume that space is a valid character)

So you are looking at 95^20 which is many orders of magnitude worse. In some respects, you should redo your calculations with that update. They would emphasise even more the scepticism that we should have about a claim that the key slot was brute-forced.

Against that, if the password is one that he has to type in, it may not be fully random.

If it were me trying to brute force, I would ignore that. For example, a randomly generated password may have a sequence of letters that do happen to be a valid dictionary word (in some language, be it French or English or something else).

I think you would spend more time trying to get clever and eliminate ‘weak’ passwords than just brute forcing them.

This is the part that is really difficult for us to know. Do we actually know that he was rigorous about keeping his laptop fully patched? etc.?

I’ll go with (NB: pure speculation): the activist had been in the sights of the authorities for a while. They had ample opportunity to cause some kind of op-sec failure.

Some op-sec failure possibilities are:

  • the authorities utilised a Linux 0-day
  • the authorities bugged his house (including optical surveillance)
  • or maybe they managed to get a bad update installed on his computer

Note that the first and third of these could mean a compromise of the LUKS encryption master key - and the authorities don’t even need to know the password for the keyslot.

That’s something of a heroic assumption though. Sure, under that assumption, you can calculate the number of passwords that need to be checked. If you only know that the pattern is “something like that” (for example, other passwords used by the activist do become known to the authorities and hence they can get some idea of the kind of passwords used by the activist) then you need to enumerate the patterns, calculate the number of passwords for each pattern, and add up to get the total - which makes it a lot more.

1: 95 = 128 - 32 - 1 i.e. 128 ASCII code points, minus the 32 control characters, minus the DEL character (code point 127).

1 Like
8

Okay let’s generate 4 passwords (with KeePassXC):

_@I$'=P5{:."&yv*6~Dfj3ur]/>n!&X&>OywLI?u+?f{XGe]mE1K2FY^i'#i+R2@[@e"ILMgC{,`_a].Zh#,F_+afr\N,vo5G.l)sQB#@pq6ZMR+.-s&_H*J;`'|C{r"
)LHp_53=pEeC,I^To&_+1,(Y:Bl$kY6}QJLa@-TQe1ku:f!-.sxtVo.c4?k:d=$sdj~Z1y}/MrGk"jkn_Ptfwz8d}[U3%oQX1Z|H:Kt>'N_.q.h1VwA,/`r]+pQ^6z0-
AtT2pR|bi,C(@B>-A'}HMd_P'DdzR#)JI|'_!PdsR4/+bY!--L`D1i`m_U>M\@_"+8~1'<]YGHx".P39i/Qo.&C,Bmo*@/k:d_qr:~tD3P1_Hp^xbdl-~>3@L?J68fL^
$Y@f>rpK/AA=&fjw>Dz:Sr0rA6U/K7N,ei-W7_&l&)<08\X!!j<!\R?kck<7T.{t.n/_'^0k'2`m{DJr&?/=@+dHS';Ufu"zBhqQ|E9d+1@PvSg'Ov@+](j6;@\4cu^c

4 passwords with 128 sign (512 in total) and I didn’t even find a password with 6 letters behind each other. Let’s look even deeper. From all the 5-letters-parts of those passwords, none was even close to a serious word. I found a German word “ei” (egg) with 2 letters, which I would expect as well as a word with 3 letters. But for 5 letters you already have to be very lucky. Even more lucky if higher and lower characters are correct and not mixed. So I can even remove passwords that contains minimum one word with 4 characters that are written correct with lower characters for example.
On “short” passwords with “just” 20 sign it’s even harder to get a password generated with words above 3 characters. Removing all those words from the brute force list (or at least to set them to the end of the array) can significantly reduce the amount of resources to find the password.

It’s all about mathematics. Of course you can try to break that on LUK with such a password and so you’re not successfully for sure. But as police you don’t just try to break one LUK, you’re trying to do it of a lot of devices each year. So with your method you have a chance to break 1000 of 1000 LUKS with a low chance or with my method I have a chance to break 999 of 1000 with higher chances, but it’s impossible to break that one person who was “lucky” on password generation with a 7 characters word. It’s still better for police to break more encryptions and definitely being unable to break that one out of 1000. All that matters is the overall probability.

And just in case you do not understand: which priority list I would use for brute force depends on the user. A hacker would use other passwords than non tech end-user or a semi tech user that think he’s smart using words like pur15m.

You forget that we’re speaking about police that takes huge amount of money to brute force devices. For one hack you’re right, but if it’s your job and you have nothing else to do than getting access to file systems, you will think in a different way.

1 Like
9

Fair enough. If it’s your job, you can justify the effort in attempting to optimise … but you still can’t exclude passwords that are weak just because they contain substrings that are dictionary words.

Just now I used the actual program that I use to generate (true) random passwords (that I don’t have to type in each time so they can really be random, but shorter than the ones you show) and it look me 7 runs to get a three letter word as a substring. The point here though is that I use the password ‘as is’ - whatever the program produces I use - so the intruder can’t infer anything about a password from the information that the password does or does not contain a dictionary word.

However maybe I am different in my pattern, as compared with the French activist.

With passwords that are fairly long, is it even going to be noticeable in the amount of time to brute force whether you exclude those passwords that happen to contain a valid three letter word?

What is a valid word also varies on context. I mean, putting aside what language we are talking about, some acronyms or initialisms or even abbreviations may be meaningful in the context even if not valid dictionary words. Example: luks

which obviously would not be good to include in a LUKS slot unlock password :wink:

10

As I said above, I would never exclude 3 letter words since they’re too short and therefore have a realistic high chance to be generated. But each letter more lowers the chance very much to get randomly generated.

To exclude completely has a reason: As Skalman calculated before you need millions of years to brute force every password (in his math requirements). So everything I would prioritize low I also just can get rid of, because my machine(s) will never be able to run it on life time. Even if I “just” need 1000 years, my machine won’t even run for 100 years, so I can get rid of 90% without any real loose.

In fact, it doesn’t matter if I exclude them or ordering them down the list.

Side note: if public get known of this behavior, people could think about “then I will create one longer word inside the random sign and wont be successfully brute forced”, but that’s a game of luck. Let’s say the PC get confiscated and 2 years later police get the knowledge that this (randomized password + common word) is the new “default”, they just will change their strategies and the “impossible to break” password is now much more easy to find. So completely random and long passwords are still the best in any case.

By the way (out of context), for L5 I would count with 107. The virtual keyboard includes other sign too. Even if they’re not official supported they can be used.

11

Well, indeed, we can go into all sorts of exotic characters … full Unicode including emojis, variation selectors, combining and joining characters, BOMs, surrogates, … However the LUKS documentation recommends sticking with ASCII.

It is therefore highly recommended to select passphrase characters only from 7-bit ASCII

So, as I’ve said before, by all means make your password stronger against brute forcing by going beyond ASCII but … understand how and why this might break, and know what to do about it if it does.

1 Like
12

That’s why I said this:

But thanks for making it more clear for others (I should have made it by myself).

13

Just for fun … I generated lots of random printable ASCII passwords and tested them for have a substring of length 4 that is a valid word. This was using an open source word list that contains over 500,000 words in total (i.e. does contain some fairly dubious and unusual words).

When using random passwords of length 32, about 2% contained a valid word. For random passwords of length 64, about 4% contained a valid word.

It would be my guess that if we dialed the password length back to 20 and increased the required word length to 7 … you would be right. The odds would be overwhelmingly in favour of “never” containing a valid word.

1 Like
14

Results as expected. Thanks for proofing my thoughts.

15

I agree that good opsec is difficult. In such cases as the one described here, most will privilege the thesis for an opsec failure of some sort.
But if you read the original article (in French) which Matthew Garrett based his post on (Une lettre d’Ivan, enfermé à la prison de Villepinte : perquisitions et disques durs déchiffrés » Indymedia Nantes); we can at least have doubts that this was really the case here. For two reasons: context and chronology.
This guy was arrested back in June 2022 and imprisoned. He was charged with setting 6 vehicles on fire, putting other people’s lives at risk and other related offenses.
He acknowledged knowing that he had been under close surveillance since January 2022. But the fact that evidences could not be entered immediately after his arrest should be an indication that they hadn’t compromised him or his computers to the point where they had obtained either passphrase to decrypt his disks. In fact, it is much later (10 months after his arrest) in April 2023 that they said they had decrypted his LUKS protected Ubuntu system.
They even gave lots of information: notably that they had been unable to crack his BitLocker Windows-based workstation (a good point for M$, here!) Proofs that the LUKS partition was successfully decrypted could not be contested: they showed emails, files (even deleted files, which is an opsec failure alright)
Context: on-going social unrest in France, frequent protests, violent clashes with police forces, demonstrators burning vehicles and buildings…
His arrest made the headlines in newspapers and on national TV channels; subsequent protests followed calling for his liberation. Public outrage, media attention: the French authorities were in a tricky posture and why in hell would they wait so many months to bring credible evidences to the case? They could have extinguished the fire right after his arrest in June 2022 and avoided all this turmoil. This speaks for the case that there was no opsec failure such that they could have supposedly obtained his passwords beforehand.
How did authorities crack his fde protected disk? They didn’t say. They don’t have to: secret services seldom reveal methods. They only said it was the BATCIAC (Brigade d’appui en téléphonie, cyber-investigation et analyse criminelle) that did the job - those guys are known to be really good at crypto. Hence all the speculations about PBKDF2 being too weak nowadays.

2 Likes
16

Do not think about it this way.

I am sure that they got that Information snitched by a third Way. Like a default Smartphone, a Telemetry-PC, a Bluetooth Keyboard, a Camera or some Apple and Google Device Nearby. Like a Nest Thermostat a Smart-TV or Teslar Car in Front of the Door. Or a Thermomix in the Kitchen, an Induction Cooking Field or a Smart Light Bulb or a Robot Vacuum Cleaner. The possibilities are Large.

And with A.I. You can do very fancy stuff. I am not sure if WLAN Hotspot devices/drivers can calculate the Water in your Body, which bends electronic Waves and Signal times, could get your finger position on your Smart-Phone to calculate your Password or something else. Because of a longer, calculated Signal time. Instead of the suggested one, knowing your Walls, your Positions, the Humidity and so on.

However i think its more likely because everything harvest Data as much in Realtime as it can.And Neural Networks, looking at that Date could tell your Position and your likes and wtf else about you…

So i would not be wondered if something like this is your Dataleak. If you will not have something colected. DO not communicate or have it happen near smart devices!

In near future, even your thoughts will get lost… and your EEG Neural Brain Information collected and Saved. If some Sensors to harvesting and using in Mobil apps, as a neural Link to your mmobile Computers. In this case its about the divers. However it will leak much private Data, too. In addition to smart Media and the devices which watching us…

Side Channel Attack on Keyboard:
https://arxiv.org/pdf/2308.01074.pdf

1 Like
17

Something to consider.

10 months is really not that long to go through the proper chain of custody requirements to clone a drive then go through the process of reviewing the content of the device with experts to validate that the data was recovered properly etc (the recovered deleted content). This isn’t 10 months to get into the device, this is 10 months to review the content and submit the relevant content as evicence. This is not a quick process when done correctly. It took over a year for this kind of information to be submitted in the Ross Ulbrect case and it’s well known that they seized his system while it was unlocked and powered on.

1 Like
18

(Thanks for the background.)

Note that the partition itself is encrypted using one technology (I believe that AES-XTS is the current default) while the slot is protected using a different technology (PBKDF2 and not sure of what actual encryption).

It may only be an assumption as to which of those was compromised.

If it’s the latter then you can override the default number of iterations in order to make it more robust against brute forcing. You trade-off your own convenience there of course i.e. it takes longer to unlock at boot time.

Also, PBKDF2 is actually parameterised with a hash function. So you can use PBKDF2 but use it with a more CPU-intensive hash function if you want. (However most people seem to be pushing just to move to the Argon family.)

Compromise also takes two forms - brute force v. cryptographic weakness. We can’t rule out the latter.

One complication is that security defaults tend to get baked in when the encrypted file system is set up. So if the guy had been using that file system for a decade, the security defaults reflect what was appropriate a decade ago and with the slot LUKS might not automatically recalibrate over time.

1 Like
19

Interesting article, Thank You - this adds to my knowledge.
Still…all this fancy stuff you mention: I mean this is France, it’s not Israel or US “Triple Fence”!

20

You may be right - I don’t really know the intricacies of the French judicial system, but I do know that they proceed strictly according to Law, otherwise they may loose in Court if a flaw in the procedures can be found.
But what is very unusual in his case, is to keep someone in jail for so long (there was no criminal record) without justifying such extreme measure or at least show some evidence of the “dangerousness” of the suspect.
They should have released him with some GPS ankle bracelet or something, and restrict his freedom of movement. This was one of the reason why many people protested and demanded his release.
For information, he was finally released in June 2023 under judicial supervision, with many restrictions and obligations to show up at police station at intervals, he can’t travel and he is especially forbidden to go anywhere near Paris…
He is awaiting trial.

1 Like