9

While doing some encryption work on drives I found that BitLocker keeps making these "recovery keys". No other encryption software I used did that so it annoyed me and made me biased perhaps.

While laboring with safe storage of these "recovery keys", I suddenly realized how small they looked and now I started suspecting a more serious problem.

I searched for how they worked and found the post How does Microsoft's BitLocker Recovery Code work?. It says it is just another encryption key, like the password.

Now my passwords are 128-character alphanumerics with special characters that I generate using algorithms with some random input (e.g., my mouse movements). My estimate is that it is 7 bit per character = 896 bits. If half of it is random, the key is way above 256 bits and suits the industrial standards.

The recovery key on the other hand is 48 digits, at most log2(10^49) = 163 bit, if my math is correct. A 163-bit key seems mighty small and is certainly not up to an industrial standard of 256 bit.

But then something else struck me. When generating the key I didn't move neither my mouse, nor pressed keys, nor was my computer connected to the Internet. What else could Windows use for randomness? Thermistors on the chipset? Too slow, the key was printed out within a few seconds. So it must be a pseudorandom 163-bit key. The time to crack anything below 128 random bits falls off the cliff so under the worst case scenario it could be cracked very quickly using regular GPUs. So it adds up to two questions:

  1. Can a BitLocker-locked drive be brute-forced within hours by guessing the recovery key by an actor with a supercomputer? With a couple of GPUs? (assuming Microsoft put as much effort as possible into that pseudo-random recovery key and didn't insert any back doors by reducing the already-miserable amount of randomness there)

  2. Is there an option to disable BitLocker recovery keys?

Answer to question 2. (I hope) I found a way to disable the recovery keys!

In Windows, search Rungpedit.mscComputer ConfigurationAdministrative TemplateWindows ComponentsBitLocker Drive EncryptionFixed/Removable Data DrivesChoose how fixed/removable drives can be recovered. Reboot. Recreate the drives.

I was happy about my discovery for a minute, but I realized if the answer to question 1 is yes, it might just create the recovery key in the background, but never display, save, or log it. The vulnerability would work just the same.

I was actually not able to disable the recovery key entirely. BitLocker just fails with an error saying there is no option to create a recovery key. I did switch to the 256-bit recovery key, which somebody on some forum says ought to be FIPS compliant. It saves it as a hidden system file on a USB disk.

13
  • 5
    The recovery keys are crucial if you use Bitlocker with a TPM. Every update (e.g. of BIOS or another boot-related component) can change the TPM state and thus make the Bitlocker drive undecryptable. For such cases an alternative unlock option like recovery key is required.
    – Robert
    Aug 26 '21 at 7:30
  • 20
    128 bits of security is provided by 3072 bit RSA, Ed25519, P-256 curves and many state-of-the art algorithms. Who told you that 163 bits of security is too low? Aug 26 '21 at 8:17
  • 8
    Which organizations require 256 bits? Even AES, the state of the art block cipher only has a block size of 128 bits. The difference between 128 and 192 bits is already astronomical. You are right that a pseudo random source with low entropy seed might be a problem as we can brute force the seed but it is usually accounted for. /dev/random generally produces pseudo-random sequence with high entropy seed. I personally don't know of any organization that requires 256 bits of security as they don't even have much options available. Aug 26 '21 at 9:23
  • 5
    requiring 256 bits of security means requiring at least 512 bit curves (p-521). It is not even defined yet if you want to use EdDSA ,max being Ed448 providing 224 bits. Or 15k bit RSA (does that exist yet)? Aug 26 '21 at 9:32
  • 6
    "Thermistors on the chipset? Too slow, the key was printed out within a few seconds." - How do you know thermistors on the chipset are too slow? 163bits in one second is... 163bits/sec. Hardware RNGs can typically generate several 100 bit/s to several 100 kbit/s, depending on their design. Seems plenty fast for your key.
    – marcelm
    Aug 26 '21 at 18:53
54

Can a Bitlocker-locked drive be brute-forced within hours by guessing the recovery key by an actor with a supercomputer? With a couple of GPUs? (assuming Microsoft put as much effort as possible into that pseudo-random recovery key and didn't insert any backdoors by reducing the already-miserable amount of randomness there)

Not even remotely. First of all, you say "miserable amount of randomness" but that, frankly, just belies that you have no idea what large amounts of entropy are like. 256-bit encryption is common not because 128-bit is insecure, but because 256-bit is fast enough on modern CPUs that there's no reason to use smaller keys. It is, however, an ABSURD amount of overkill from a security perspective, at least against conventional computers (it might be meaningfully more secure against quantum computers, if those ever get anywhere). 128 bits of entropy means 2^128 possibilities, and 128 bits of entropy is still an extremely common cryptographic key strength (though depending on the algorithm, this sometimes requires the keys to be longer than 128 bits). 2^128 is about 3.4 * 10^38 (EDIT: fixed a typo in the math). To consider how many that really is, in terms of total computation required, consider:

  • For certain kinds of operations, the most common supercomputers today are GPUs; for example, a high-end modern GPU can compute tens of billions (10^10) of cryptographic hashes per second.
  • Let's suppose, for the moment, that you could break a BitLocker recovery key by computing 2^128 SHA1 cryptographic hashes. (This is almost certainly false, even if the keys actually only have 2^128 entropy, much less any more.)
  • Let's further suppose that you are the NSA or some such, and can buy up the entire annual production of high-end GPUs (somebody is buying them all, these days...). Let's say it's about 38 million (this is actually almost certainly too high; it's a decent guess for the total number of GPUs, most of which are way less powerful than the high-end ones).
  • So, 38M (3.8 * 10^7) powerful GPUs, each capable on average of 10^10 SHA1 operations per second. That's a total of 3.8*10^17 hashes per second.
  • That's still about a factor of 10^21 seconds! How long is that? Almost 32 trillion years, which is roughly 2500 times as long as the universe has existed so far.

Let's be honest, you can't afford to wait 2500 times the current age of the universe. Nor can your attacker. They might be able to shave a couple orders of magnitude off that estimate by buying specialized hardware rather than off-the-shelf processors, but even if they manage a speedup of 1000x... that's still multiple age-of-the-universe lifetimes. Just to perform one operation 2^128 times. Using several billion dollars worth of hardware. I think your recovery key will be OK.


Is there an option to disable Bitlocker recovery keys?

In addition to the option you already found that makes Windows not force there to be a key created each time you use the BitLocker GUI, you can also delete "protectors" including the recovery key using the command-line manage-bde.exe tool.

manage-bde -protectors -delete C: -Type RecoveryPassword

Just, before you run off to execute that little command, take a break to consider. After all, you've got more than a few age-of-the-universe timescales to consider it in.

10
  • 27
    You missed the entire point of his answer. Aug 26 '21 at 22:07
  • 24
    @ArthurTarasov If you're worried about backdoors or bad random number generators then deleting the recovery key will do nothing to protect you. If the RNG is bad or if there's a backdoor you're screwed whether you have a recovery key or not.
    – eesiraed
    Aug 26 '21 at 23:58
  • 4
    And a 256 bit key is not just twice the difficulty, but exactly 2^128 more difficult, so it'll take 2500 * 2500 ~ 6 million times the current age of the universe.
    – Nelson
    Aug 27 '21 at 8:30
  • 6
    @ArthurTarasov, remember that the recovery key just encrypts the real private key that the data is actually encrypted with. If you're so worried about someone breaking the recovery key through means that are considered to be practically impossible, you should probably worry about the underlying key via practically-impossible means too. Or, y'know, you could worry only about realistic attacks. Aug 27 '21 at 21:56
  • 5
    @Nelson You're right that a 256-bit key is 2^128 times as hard, but you're wrong about the ~6 million. Just because one value A is the square of another value B, does NOT mean that if B/N=X that A/N=X^2!! (Here A is 2^256, B is 2^128, N is [3.8e17 Hz * seconds/year * years/universe-lifetime], X is 2500). The correct thing to do is multiply 2500 universe-lifetimes by 2^128 - that being the actual product of A/B - which is 7*10^41 universe-lifetimes (quite a bit more than 6 million!). Which is in fact roughly 2500 * 3.4*10^38 = 8.5*10^41 (some rounding occurred). As I said: OVERKILL
    – CBHacking
    Aug 28 '21 at 8:58
21

Can a Bitlocker-locked drive be brute-forced within hours by guessing the recovery key by an actor with a supercomputer? With a couple of GPUs? (assuming Microsoft put as much effort as possible into that pseudo-random recovery key and didn't insert any backdoors by reducing the already-miserable amount of randomness there)

I think you're vastly underestimating just how big 2^163 is. If we do some crude maths and take an Intel i9-9900K (16 threads, 3.6GHz), and assume that it can try one AES key per cycle (because it has AES-NI), that gives us 57,600,000,000 keys per second, or 1,816,473,600,000,000,000 (1.8 × 10^18) per year. Which means that brute-forcing a 163 bit key would take 55,051,722,194,035,743,997,062,743,766,462,087,395,540 (5.5 × 10^40) years on a single high-end CPU.

Sure, you can throw more CPUs at the problem (GPUs probably won't help that much, because they won't have AES in hardware like CPUs do) - but you still not going to get anywhere near feasible.

So yes, a 48 digit key is less that 256 bits, but it's still in the realm of being completely uncrackable. As a general rule, 128 bits is considered completely impossible to brute-force, and that's unlikely to change.

But then something else struck me. When generating the key I didn't move neither my mouse, nor pressed keys, nor was my computer connected to the internet. What else could Windows use for randomness? Thermistors on the chipset?

Exactly how Windows generates random numbers is complicated, but Microsoft published a whitepaper on it that would be worth reading if you want to know the details.

The short version is that you're not going to guess them, and I don't believe that there have been any serious flaws highlighted in their approach.

Is there an option to disable Bitlocker recovery keys?

This is a bad idea - there are all kinds of circumstances when you might need them (BIOS updates, some firmware updates, TPM issues, motherboard failure). If you do this, then I hope that you have good backups of your data (and that you've encrypted them with something just as strong).

5
  • The whitepaper is great but doesn't prove they actually used all that when generating this shady key. The hardware failure and backups and even TPS use-case scenarios are just use cases. The bottom line is why not let me use my own key or disable it entirely then? Why obfuscate so hard? By the way, if you know how to disable it for fixed drives, please let me know and I'll accept the answer Aug 26 '21 at 8:32
  • 35
    If you don't trust Microsoft not to implement "shady" backdoors in one part of their crypto, then why do you trust that they're using your password securely to generate an AES key? Why do you trust that the TPM is in any way secure? Why do you trust that BitLocker is even implementing AES encryption?
    – Gh0stFish
    Aug 26 '21 at 8:44
  • Their group policy interface says they are using AES 256 CBC algorithm. They have my full trust there. They don't claim TPM is secure and I don't use it in this case. Yet, the recovery key, the weakest spot, is so unclear. I will go with their 256-bit key option (they don't say how they make it though in this case) but I would be so much more trustful if they just had an option to disable it entirely or let me use my own. Aug 26 '21 at 8:52
  • 15
    @ArthurTarasov if you think Microsoft's encryption is backdoored, you should switch to Linux :) and use LUKS which you can verify is implemented as claimed. (Also, there is no recovery key by default) Aug 26 '21 at 16:24
  • 1
    @NonnyMoose there's still an option to disassemble (for research purposes, etc) if you really want to know what happens in the bg of Bitlocker, though once the trust is at least slightly nudged with the closed source, it won't come back easily (if at all). So there are two secure options: 1) wait/insist for MS to publish their source and have it properly audited - which if you are a large enough corp with a lot of future revenue for MS, you might actually have a chance to have a look legally 2) switch to Linux and hope it's been properly audited. For a non-corp 2) is the most probable.
    – KeyWeeUsr
    Aug 27 '21 at 8:41
2

48 digits, at most log2(10^49) = 163 bit, if my math is correct.

Your math is a few bits off: it's at most log2 1048 ≈ 159 bits.

However, since it's meant to be typed in by hand, some of the digits are probably check digits. Looking online, it appears it's a 128-bit key, divided into 8 chunks of 16 bits each, and each chunk converted to decimal and multiplied by 11 (to catch single-digit errors and transpositions). The key is really 128 bits.

Which is plenty, as other answers have said.

What else could Windows use for randomness? Thermistors on the chipset? Too slow, the key was printed out within a few seconds.

Windows has an entropy-gathering service in the kernel which starts when the OS boots and runs as long as the system is running. It's the time since boot that matters, not the time since you asked it to generate the key.

Microsoft's own description of the system (for Windows 10) is here. It says the primary source of entropy is cycle-precise interrupt timings (via the RDTSC instruction). They estimate there is more than one bit of entropy per timestamp and there are hundreds of interrupts per second.

Even if you generate the key almost immediately after booting the system, you're probably okay because on startup it reads 256 bits from the CPU hardware RNG (RDRAND/RDSEED) among various other sources.

my passwords are 128-character alphanumerics with special characters that I generate using algorithms with some random input (e.g., my mouse movements). My estimate is that it is 7 bit per character = 896 bits.

Without knowing more about your generation method, it's hard to know how much entropy these passwords have, but it could be far less than you think. It's easy to screw up homebrew security.


Fundamentally, you need to think about who your enemies are. Even if some problem with the entropy gathering limited a recovery key or password to 264 possibilities, and even if the attacker could figure out which possibilities those are (which would seem to require a level of knowledge of your system that would render a lot of these other safeguards pointless), it's still very expensive and time consuming to try them all. If somebody is that motivated to crack your encryption then you have a lot of other things to worry about. They may break into your house (undetectably) and install a hardware keylogger, or find the piece of paper you wrote the 128-character password on since it's too long to memorize, etc.

1
  • I wonder how could I get this information without this forum. It wouldn't hurt Microsoft to document these parts with links in BitLocker interface. I do this type of encryption for off-site backups that end up in those clouds that have as much security as bins in public parks. I apologize for my strong opinions, but just clarifying my perception of attack vectors. Aug 29 '21 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.