Hacker News Reader

Comment by orlp | Hacker News Reader

> His encryption password was supposedly greater than 20 characters and included a mixture of cases, numbers, and punctuation, so in the absence of any sort of opsec failures this implies that even relatively complex passwords can now be brute forced.

Sorry but there's no world in which this password was bruteforced in 2023, even if they were using just SHA1 as their PBKDF. Even assuming just upper/lowercase and 20 characters you are looking at 114 bits of entropy. To put this in perspective, if you could use the entire global bitcoin mining equipment (estimated at 350 million terahashes / second) right now without modification to bruteforce this one password it would still take you 4 x 10^37 centuries. The author of the article failed to do this basic math.

The dude reused passwords, got keylogged, powned some other way, was coerced, had something unencrypted, or something else happened. But his password did not get bruteforced.

View on HN

Here's how it works: When the gov wants to crack a password, they gather all of your digital life (phone, computers, thumb drives, etc.) and basically run "strings" on all of the hard drives / data they have of you.

They then use that strings output as input into the password cracking rig. They are happy to let it churn for months / years (because the case is working through the system).

So its far more likely this individual hibernated his PC with the password in memory or reused the password elsewhere than it was cracked.

> They are happy to let it churn for months / years (because the case is working through the system).

Is that the case? I would be surprised. I would assume success ratio does not change much by checking say 10^4 more combinations (it's either a simple combination of these strings and common prefxies/suffixes or if it's complex then the amount of combinations grows so fast that you are unlikely to get a hit)

No. Resources are always limited. Forensic investigators will not be running things on server farms for years. People who think such things really do not understand how many cases are "in the system" at any one time. Even for something relatively serious like CP, drug smuggling or lower-end terrorism, there are literally thousands of cases in-the-system. The server farms infrastructure (ie hiring cloud capacity) would be reserved for national security, foreign intelligence and stopping Magneto. The contents of your laptop are not worthy of such treatment.

Not sure how it's done in the US but an effort to crack it like this would happen only on very high profile cases in France which is not the case of this one.

I'm betting on the second option, he reused the same password somewhere else or they just got lucky and seized the computer already unlocked

The presumption that 20 characters is any meaningful amount of entropy is based on the password actually being somewhat random, and there's no fundamental reason to believe that that's true. I tend towards brute forcing not being the most likely reason for this, but the indisputable reality is that any combination of weak passwords and PBKDF2 makes it plausible (if not necessarily likely) that an adversary with a sufficiently large hardware budget can break disk encryption.

You don’t need to merely tend towards. You just can’t brute force a random 20 characters password of the type that he mentioned. Brute force is almost never used, even with half of entropy of such password.

His password was intercepted, or was embarrassingly deterministic.

I didn't see anyone mention a random 20 characters password. I saw 20 character password with symbols and upper and lower case. That might be 4 words strung together "correct horse battery staple" style.

Or something like, notebook still had the keys in memory when it was recovered

Though from this description it looks like they read the disk (trivial) but it's not sure if they actually pulled anything from it (at least it seems they didn't pull anything incriminating if I read it correctly).

A stronger KDF would plausibly have protected him even if his password was embarrassingly deterministic.

Maybe. But probably not.

If they were using a crib sheet to the point of only trying 1m attempts, this can be done in “days” with one CPU even if PBKDF2 is set to take one second each attempt on that CPU.

A “better” KDF isn’t fundamentally going to change this. It’s just going to enforce stricter limits on any time-memory trade offs and require more memory. Neither of these are going to be meaningful differences when you’re cracking a single password for a single user with a crib sheet, unless you’re in the realm of billions or more guesses.

If the computer is suspended at the time it's seized, does it become easier to recover the FDE key from the computer's memory? Or is that encrypted with the user password, or something like that? (On stock ubuntu, say.)

If the DRAM is powered on at the time of seizure, recovering the key is eminently possible. If this is an issue for you, completely power off the laptop when transiting customs.

https://en.wikipedia.org/wiki/Cold_boot_attack

If you can dump the contents of memory then you have the key (after all, the CPU has to be able to encrypt and decrypt the material, so it has to be available).

Pedantically, if there's an HSM/similar hardware in play, the CPU only asks for material to be encrypted/decrypted and doesn't have the key in system RAM to be able to do so itself.

MacOS machines with a T2 chip keep the encryption key in the T2 chip so it isn't in system RAM.

Apparently it's possible to keep the key in the debug registers: https://en.wikipedia.org/wiki/TRESOR

Making this bit mor concrete: luks1 uses pbkdf2 with sha1 and minimum iteration count of 1000 as far as I can tell. Looking at random hashcat benchmark for rtx 4090, the closest thing is about 20MH/s. If we assume attacker spends a month with 1000 gpus, they will have bruteforced 20e6×86400×30×1000 combinations. Log2 of that rounds up to 56 bits.

https://gist.github.com/Chick3nman/32e662a5bb63bc4f51b847bb4...

You're underestimating the default PBKDF parameters used by LUKS1, `cryptsetup luksFormat` [1] benchmarks the `--pbkdf` function at runtime when configuring the keyslot, and the default iteration count is based on a target `--iter-time` [2], which is either 1s or 2s [3], unless overridden by the distro. I'm not entirely sure about the PRF (SHA1/256) used by LUKS1, it might be SHA-1 or SHA-256 [4].

For a LUKS1 image created with Ubuntu 18.04 on a i5-8265U ( Q3'18) CPU, that appears to result in an iteration count on the order of 1-2M. Assuming those hashcat benchmark numbers scale linearly on the iteration count, you're down to about 10kH/s for PBKDF2-HMAC-SHA1 or 5kH/s for PBKDF2-HMAC-SHA256.

Assuming 10kH/s, that drops you down to roughly 45 bits of entropy for 1k gpu-months, or 250k gpu-years to net 56 bits of entropy. Those would be on the order of [a-z0-9]{8} (41 bits), [a-zA-Z0-9]{8} (47 bits) or [a-z]{12} (56 bits).

OTOH it's easy to generate a 20-character password with far less entropy.

[1] https://man7.org/linux/man-pages/man8/cryptsetup-luksformat.... [2] https://wiki.archlinux.org/title/dm-crypt/Device_encryption#... [3] https://mirrors.edge.kernel.org/pub/linux/utils/cryptsetup/v... [4] https://gitlab.com/cryptsetup/cryptsetup/-/wikis/FrequentlyA...

The author clearly meant "cracked" rather than "brute forced".

Password/passphrase cracking is done with sophisticated (and in cases like this one, likely tailored to the target) strategies that try more likely possibilities first. In such a scenario, "supposedly greater than 20 characters and [including] a mixture of cases, numbers, and punctuation" tells us little about how difficult it was to crack.

For example,

    A11 y0ur b4s3 4r3 b3l0ng 70 u5!

would be trivial to guess.

They used chatGPT, trained on this user's emails, posts, data!

(not many know this, but gpt secretly is french for Government Person Trained!

The eventual goal, is that the gubberment will have mental maps of us all, and even use that to test meme class mental manipulation techniques on this simulated populous, to best determine those sweet words to control us.

Rebels will become loyalists, anarchists state advocates, our very natures used to control us!)

A previous letter[1] supposedly from the same person stated that he was under surveillance before arrest, and thus "black-bag cryptanalysis"[2] is quite probable, particularly due to SDAT being a well resourced domestic spy agency.

"the SDAT explains that they began to tail me and the other comrade (quickly exonerated) starting last January"

[1] https://anarchistnews.org/content/update-letter-ivan-alocco

[2] https://en.wikipedia.org/wiki/Black-bag_cryptanalysis

While I agree in the specifics the overall message still stands IMO: Update your KDF going forward if you care about this kind of security.

English has ~1 bit of entropy per character. Replacing a character with a similar symbol adds ~1.5 bits to that character (there aren't leetspeak substitutions for every letter, so I am being a little generous). Random symbol insertions between words adds ~5 bits per ~5 characters (10 numbers, their shift-codes, and the punctuation, average word length is ~5). If every letter of the password is randomly leetspeak that yields 50 bits. If symbols are inserted between each word (average of ~4 in 20 characters) that yields 70 bits, which is barely greater than the 68 bits of entropy per second equivalent of 300M TH/s

> English has ~1 bit of entropy per character.

I think the discrepancy here is coming from the fact that you are assuming the password is using English words, where others are assuming completely randomly selected characters from the set /[a-zA-Z0-9]/, plus some special characters, which yields substantially more than 1 bit per character.

Please explain the math behind a 26 letter alphabet having 1 bit per character

I was also skeptical of this claim. It seems to come from Schneier's "Applied Cryptography" and assumes you are using whole words in the password.

https://en.wikipedia.org/wiki/Entropy_(information_theory)#c...

> English text, treated as a string of characters, has fairly low entropy, i.e., is fairly predictable. We can be fairly certain that, for example, 'e' will be far more common than 'z', that the combination 'qu' will be much more common than any other combination with a 'q' in it, and that the combination 'th' will be more common than 'z', 'q', or 'qu'. After the first few letters one can often guess the rest of the word. English text has between 0.6 and 1.3 bits of entropy per character of the message.[6]: 234

Grammatical English is an extremely restricted subset of all strings of characters. You can actually see for yourself that it's in the ballpark of a bit by going to a book, covering up a line, reading the context, and trying to guess the next letter one at a time. I get it 3/4 times, and would probably be down to 1/2 if I had to do it the right way.

Consider the difference in entropy between this totally randomly generated password, consisting of 4 words each from a pool of 100,000:

Correct Horse Battery Staple 4lg(100000) = 33

And this one of the same length where each character was chosen from a bank of 68:

VIW&jubiHZUgBrFA8PI9Vy1E(%G 28*lg(68) = 170

French dude gets in trouble with the law and has his encryption cracked. Hackernews goes into an extended (and extremely interesting) thread about the entropy content of grammatical English. Probably not that different in terms of entropy content per character, though.

That being said I don't understand your calculation of 4lg(100000). That seems like it can't possibly be correct. For starters it is entirely independent of the entropy content of the words in the dictionary. I could have 100000 strong random passwords of 1000 characters each in my dictionary. Could you explain this a bit, please because there's obviously something I'm missing?

Edit: Aah I think I get it - the assumption is both me and the attacker know the dictionary so the entropy content of the words doesn't matter, the only thing that matters is the joint probability distribution of the combinations I'm choosing. Is that correct?

Oh yeah, my assumption is that it's 4 words chosen from a 100,000 word dictionary. I honestly have no idea if it's a reasonable estimate but it stuck in my head from XKCD's original correct-horse-battery-staple comic. Of course in real life an attacker won't know necessarily the distribution you've pulled your password from, but by using the exact distribution in your calculations you have an ironclad lower bound.

Diceware uses 7776 word dictionary, xkcd uses a shorter dictionary.

My God, where on Earth did I get 100,000? I mean that's a lot of words, plausibly more than I will ever hear. And how did it just cancel out anyway so I got roughly the right entropy? This will frustrate me until I understand how I fucked it so totally

> Correct Horse Battery Staple 4 lg(100000) = 33

I think you mean 66. More realistically, 52 for Diceware's 7776-word dictionaries, or 44 for XKCD's 2000 common words.

Yep, I somehow internalized that there were 100,000 words (on reflection, I couldn't name a tenth of that in one sitting), but also halved the result, and the error canceled out a bit. Terrible.

> As an example of a numerical value, GPT-2 achieves 1 bit per character (=token) on a Wikipedia data set

https://towardsdatascience.com/perplexity-of-language-models...

(I have not checked this claim, it's just what I found from googling "best large-language model character-perplexity 2023".)

A token in a LLM is generally more than one character, so I would guess that the entropy is a bit lower than that. Shannon estimated it at 0.6-1.3 bits/character in 1950 (https://mattmahoney.net/dc/entropy1.html)

You are confusing the fact that you can store in some encodings one character per byte, 8 bits, with a bit of entropy.

Grammatical English has about a bit of entropy per character (Wikipedia has it between 0.6 and 1.3). Most passwords won't be fully grammatical, or even close, but it's a decent worst-case bound for passwords chosen by English speakers to be memorable. If you have a specific scheme it obviously goes out the window.

with all the password leaks I wonder if you could determine the likely scheme used by a given user by the leaks associated with their email address.

I don't follow your math. If we assume the cost of your password hash matches the cost of a bitcoin hash, I arrive at 2 * 10^6 years, not 4 * 10^39 years.

2^114/350e18/3600/24/365 = 1.9e6

Even 2^114 itself is only 2 * 10^34

I... don't know what the hell happened. I was doing the calculation on mobile while on the move and I must've screwed up the parenthesis in the denominator. Embarrassing...

Your calculation is correct. My point still stands (2 million years is plenty of time), but my number given was completely off. I can't edit it anymore though.

Yeah, I'm not following that calculation either. Adding to that:

> Even assuming just upper/lowercase and 20 characters you are looking at 114 bits of entropy.

Upper/lowercase are already 52 characters. If we add digits (0-9) we are already looking at log_2(62^20) = 119 bits of entropy.

On that note: Let's assume the password were indeed purely random and had 119 genuine bits of entropy. If you're the attacker and your goal is to do 1000 (≃ 2^10) rounds of SHA1 for each of those 2^119 potential passwords, couldn't you then just try to brute-force the 128-bit key directly, since 119 + 10 >= 128?

Put differently, wouldn't the statement "A fully random 20-character alphanumeric password has been brute-forced" amount to saying "AES-128 can be brute-forced"?

> so in the absence of any sort of opsec failures [...]

The original sentence already came with this disclaimer.

Agreed. Annoyingly the author does split up a very core idea to the next paragraph:

> and we should be transitioning to even more secure passphrases. [newline] Or does it? Let's go into what LUKS is doing in the first place.

That sentence really should have been put into the introductory paragraph, instead of being the start of the 2nd.

Disagree, long paragraphs are more annoying than breaking up thoughts like this. I think it's reasonable to expect a reader to continue to the next paragraph, and corrosive to start writing for poor readers (distracted, skimming, etc - let people who do this bear the risk and consequences of their actions rather than changing writing to make this behavior less risky)

> absence of any sort of opsec failures

There is no such thing.

> Even assuming just upper/lowercase and 20 characters you are looking at 114 bits of entropy.

Careful, that math assumes each character was chosen randomly, which isn't how people usually pick passwords. If the password contains words and patterns, then it was much weaker. "Passwordpasswordpass" matches those requirements, and is decidedly weak.

But I agree, password reuse or other similar mistake seems likely.

> it would still take you 4 x 10^37 centuries.

This calculation is for exhausting the entire search space, right? Not guessing at random (which would invoke the birthday paradox?). For block solving on Bitcoin, clients don't search the whole space. They try random values and check if it's right.

The birthday paradox only applies when you're trying to find any pair of inputs with the same output, because then the probability of success scales with the number of pairs ≈ guesses^2. If you're trying to find an input with a particular output (in this case one that results in the same key as their password), then on average you'll have to try half the search space (divided by the number of correct answers in the search space, but that should be one in this case)

I'd assume the random guesses for bitcoin miners is because with a deterministic chunk of the search space you risk the possibility that someone else chose the same chunk and so already tried all the values you're trying

a) The part you quoted stipulated "...in the absence of any sort of opsec failures this implies...". You might be surprised to learn that some folks _can_ run really, really tight opsec.

b) The first two sentences of the next paragraph read:

> Or does it? Let's go into what LUKS is doing in the first place

Someone who doesn't know in detail the math of how this stuff works but _does_ know how to run tight opsec could very reasonably assume that now fairly long passwords can be brute-forced. That's like, the entire point of the article, innit? Describing how this almost certainly _wasn't_ an attack on the password, but almost certainly an attack on the mechanisms that use that password as an input to crypto.

I don't want to overstate this - it's absolutely possible that the password was obtained through some other mechanism. But a weak password (even if it's 20 characters long!) as the input to PBKDF2 is something that can plausibly be broken in a reasonable timeframe using realistic hardware, and there's a really easy way to fix that, and people who care about this should protect themselves.

> ...it's absolutely possible that the password was obtained through some other mechanism.

To be clear, the person I was replying to was all like "You _idiot_. Obviously the plaintext of the guy's password was in the possession of the attacker!", when the primary (if not the entire) _point_ of the article was to set up and answer the question "Well, what if it _wasn't_? Is it possible using default settings to brute-force a password?".

NSA agent spotted /s

Reply on news.ycombinator.com