The TrueCrypt website has been changed it now has a big red warning stating "WARNING: Using TrueCrypt is not secure as it may contain unfixed security issues". They recommend using BitLocker for Windows 7/8, FileVault for OS X, or (whatever) for Linux. So, what happened? The TrueCrypt site says:
This page exists only to help migrate existing data encrypted by TrueCrypt. The development of TrueCrypt was ended in 5/2014 after Microsoft terminated support of Windows XP. Windows 8/7/Vista and later offer integrated support for encrypted disks and virtual disk images. Such integrated support is also available on other platforms (click here for more information). You should migrate any data encrypted by TrueCrypt to encrypted disks or virtual disk images supported on your platform.
Did the TrueCrypt devs (or SourceForge?) get a NSL? They are offering a "new" version (7.2), but apparently the signing key has changed and a source code diff seems to indicate a lot of the functionality has been stripped out. What's up?
(Score: 4, Interesting) by stormwyrm on Thursday May 29 2014, @07:55AM
Your Scenario A is complete bullshit. If it were true that TrueCrypt volumes could be brute forced, then that means that EVERYTHING can be brute forced. This is known to be false. Brute forcing 256-bit symmetric keys requires energy equivalent to that of an exploding star to do in a reasonable amount of time. Brute forcing a single 128-bit key will still require at least several hundred terawatt-hours of energy, assuming you had perfectly efficient computers capable of doing operations at the von Neumann-Landauer limit, and probably no one has those. In any case I'm pretty sure that everyone would notice if that data centre in Utah was gobbling hundreds of terawatt-hours of energy. It seems that the US consumes about 13,000 kWh of electricity per capita per year, so 100 TWh is the equivalent of a city with seven million inhabitants. It's like the energy consumption of a city almost the size of New York, and that much energy being consumed cannot go unnoticed.
I have argued on the other site why it seems unlikely that the NSA possesses some classified cryptanalytic result on AES/Rijndael (the most widely used block cipher in TrueCrypt), or that they modified the algorithm so it incorporates kleptography [wikipedia.org]. Among other arguments against the cryptanalytic breakthrough theory is that the NSA itself endorses its use by the Federal Government for classified information, when used by properly certified systems (which they've certified to contain no back doors). Against the kleptographic argument is the fact that the algorithm was designed by two Belgian cryptographers who are very well known in the academic cryptography world, and that no changes were made to the algorithm prior to it becoming a FIPS. I know from my own work being done around the time that there is no difference between Rijndael the AES candidate and AES as described in FIPS 197. I personally implemented Rijndael for an 8051-type microcontroller around 1999, and when it was announced AES in 2001, I compared FIPS 197 against Rijmen's and Daemen's spec from 1998 against which I based my code and found the two to be exactly the same. My old code also produced correct results against the known answer test vectors that are part of the standard. Kleptography seems rather unlikely given that.
Scenarios B or C are thus far more likely explanations than A in my mind.
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by juggs on Thursday May 29 2014, @08:32AM
EVERYTHING can be brute forced. That is not bullshit and it is not false.
NOTHING is impenetrable to brute force.
If you are a cryptographer you know the above to be true. Brute force implies throwing every possible solution at a problem - one will prove to be the key that unlocks the door.
I will leave aside your subsequent points about AES/Rjindael as I am not qualified to speak to their mathematical correctness nor TrueCrypt's implementation of them.
My point in Scenario A was that if TrueCrypt's developers had decided to cease work then from a security perspective it would be good practise to leave available source and binaries that can decrypt previous versions' encrypted volumes. Deleting the encryption code simply serves to prevent future adopters of the software using it to encrypt their files.
If one is walking away from supporting / developing an encryption software then it makes sense to do this. It is a delineation.
Regardless of the power / compute requirement to brute force something today, who knows what advances are around the corner. Hence why I alluded to only relying on encryption to keep your stuff safe for a finite period. It doesn't actually matter what that finite period is, but it is finite. Surely it is better to get users used to the concept rather than lull them into an encrypt now, secure forever utopia that may or may not be the case.
(Score: 2) by stormwyrm on Thursday May 29 2014, @09:04AM
So where's the supernova you can harness for the energy needed to break a 256-bit key? Or can you wait until the heat death of the universe? The theoretical minimum amount of energy based on arguments for computing using the known laws of physics requires at least that much energy to brute force a 256-bit symmetric key. Perhaps it might be feasible for a Kardashev Type 3 civilisation, but for us puny type 0 civilisations it is far beyond the realm of feasibility. As Bruce Schneier [schneier.com] put it:
Sure, anything can be brute forced. It just isn't practical to do so, which makes it practically bullshit to even try.
Numquam ponenda est pluralitas sine necessitate.
(Score: 4, Interesting) by edIII on Thursday May 29 2014, @09:27AM
That's just it though. You're missing the bigger point. Nobody is even trying to brute force anything .
At least not anymore. Once the permutations so strongly exceeded total processing power, attackers simply had no choice but to stop. They didn't even brute force Enigma the way you allude to. Take a deeper look at how Enigma was attacked. They had enough processing power during WWII to brute force Enigma *AFTER* they first reduced the keyspace with nifty mathematical analysis.
The real game, and real attack surfaces, are sophisticated analysis of the gestalt view of the ciphertext. It's a known process by which probabilities are understood, and the effective keyspace is reduced to a more viable level that can be brute forced in time periods acceptable to governments and LEO.
Technically, lunchtime is at any moment. It's just a wave function.
(Score: 4, Interesting) by edIII on Thursday May 29 2014, @09:16AM
Properly implemented OTP is mathematically proven to be immune to brute force attacks. You can literally generate ANY plaintext as long as it's the same length as the OTP ciphertext, and have absolutely no way whatsoever of knowing that you guessed the correct key. The key itself is supposed to be high entropy from preferably non-deterministically generated numbers. There is no math involved other than modular addition, and even then, it's a 1:1 relationship between each and every single bit of the plaintext and key. That's it. There is NO relationship between the 2nd bit and the millionth bit. Assuming a truly random key it's impossible to state beyond a reasonable doubt you found the key.
That's the most dangerous part of OTP. Information bias can lead you to assume that a generated plaintext from your chosen key was what you are looking for.
What do you want me to have been guilty of? Child pron? Just take any CP image bump it up against the ciphertext, obtain your key, and then claim the extra stuff was padding designed to confuse analysis. Industrial espionage? Same thing. A manifesto saying you are the one responsible for the bombs? Just as easy.
OTP is perfection as far as the method (maybe a slight addition to prevent stream attacks) is concerned. What is not perfected yet is the key exchange, and the enormously ridiculous requirement that key size be exactly the same length as the plaintext.
Otherwise, yes, OTP is specifically known to be immune toinfinite processing power.
Technically, lunchtime is at any moment. It's just a wave function.
(Score: 2) by FatPhil on Saturday May 31 2014, @05:07PM
>
> NOTHING is impenetrable to brute force.
>
> If you are a cryptographer you know the above to be true.
Any cryptographer who thinks the above is true is not a cryptographer at all, but delusional. As is any non-cryptographer who thinks it is true.
A OTP cannot be brute forced. Provably. Mathematically. And yes, I am a mathematician. Who knows a fair bit about cryptography.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 5, Interesting) by edIII on Thursday May 29 2014, @08:56AM
That's not entirely correct. In fact, it's much worse. You're correct about the physical limitations of classical computing though.
Bruce Schneier, Applied Cryptography, pp157-8:
This was written nearly 20 years ago. Since then, quantum cryptanalysis has become a lot more feasible. A proof of concept could be less than 10 years away from being public and in the known literature.
Schneier himself also states that the the whole point of cryptanalysis is to find shortcuts [schneier.com].
So relying on the brute force strength of 256-bit symmetric key alone is hubris. It's not simply a matter of permutations (which to be pedantic will be 1/2th of an order reduced in practice), but involves probabilities and attack surfaces beyond encrypted data at rest.
AES 256-bit has already been reduced by 7 orders below it's permutations. New attacks in the known literature go further than that. As the man said, "attacks only get better, not worse". We don't even begin to know what the NSA really has up it's sleeve. They really do employ the world's best cryptographers.
Cryptanalysis of at-rest ciphertext is only one tool. That usually involves working on the method itself. What about the RNG data being provided? It's almost *never* TRNG. Since, it isn't TRNG, that now allows the CSPRNG to be compromised. Knowing what CSPRNG was used, or likely used, could once again be used to identify valuable shortcuts shaving off the effective keyspace by several orders, or more.
Regardless of method and CSPRNG, you still have a weakness in key exchange. It matters not that your key was 256-bit. If the probabilities of the key exchange collapse that down to a 40-bit key, you're fucked.
I respect that you have implemented and coded the encryption algorithms and have experience, but I don't think it's anything but hubris to say that a 256-bit symmetric key encrypted ciphertext requires more energy than several stars to brute force. Seems reckless really.
In order to do that, you also need to show me a really impressive CSPRNG, or a massively insanely fast TRNG, *and* a truly solid and novel key exchange.
If you really wanted to impress me with bullet proof encryption you would either perfect OTP (which is not), or make quantum encryption possible. Most importantly, make it possible to have quantum encrypted data at rest and not just "cycling" in an active system. I'm betting that perfect cryptography will be solved by using quantum to provide the missing links in OTP myself.
We've been through all this before many times. People saying that a method was bullet proof, only to find a surprising and novel attack that somehow reduced the effort required by 99%. The most notable of them all *is* OTP, which is *mathematically* perfect. Except, that they found in order to be perfect in practice, you could never reuse the pad data. Damn... back to the drawing board...
(Score: 5, Interesting) by stormwyrm on Thursday May 29 2014, @09:45AM
We are discussing here the brute forcing of the key to a TrueCrypt volume. So everything else you've written about CPRNGs and key exchange isn't really germane to the discussion, as that isn't what I'm talking about. If you can find shortcuts, well, you aren't doing brute force any more right? You might as well have just spoken about the infamous $5 wrench [xkcd.com] to extract the key, and that qualifies as "brute force" only to the facetious. Quantum cryptanalysis changes Schneier's argument about brute force only a little. Apparently there's been analysis that shows that quantum mechanics can do no more than halve the effective keyspace, so a 256-bit keyspace becomes effectively 128-bit. Not a lot of help when you can do triple encryption, and you wind up at 768 bits, or effectively a 384-bit keyspace to a quantum computer.
Why do you think the NSA seems to be beefing up its ability to use exploits and put in back doors wherever they can? They cannot beat the mathematics, so they get around it by attacking the implementation rather than the mathematics. TrueCrypt may well have been on its way to becoming the sort of software that they couldn't touch in that way, and they couldn't have that.
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by edIII on Thursday May 29 2014, @10:27AM
No, we are talking about the same thing, even with the shortcuts. Brute forcing does not simply mean "trying all the keys that are possible". Brute force means that you don't possess a key, and you don't possess some mathematical insight that allows to you perform the reverse process with the same amount of effort regardless of key possession. Sufficient mathematical insight can allow you to break encryption without even finding the key. See frequency analysis among others IIRC. Whatever shortcuts are used, they only reduce effective keyspace. In the end, you are still brute forcing effective keyspaces. They just became much smaller.
CSPRNG is quite relevant to the discussion. Admittedly, key exchange is less important for TrueCrypt if we are going to strictly limit the discussion to it alone.
The CSPRNG is relevant because all encryption methods, including the ones employed by TrueCrypt, are used to provide random numbers that greatly influence key generation and routine encryption operations that generate ciphertext. If a CSPRNG is compromised this means you understand, and are able to better predict, the numbers that were used. A compromised CSPRNG is invaluable to ciphertext-only attacks, which is exactly the situation you present in TrueCrypt data at-rest. To say otherwise explicitly means you did NOT use a CSPRNG during ciphertext generation.
You are, in fact, talking about generating random numbers, following a method of encryption, and then generating ciphertext. How a CSPRNG is not critical in that undertaking is not something I can understand, or reasonably believe. The NSA *did* compromise a CSPRNG and paid very well (by their standards) to have it added to at least two different national standards for that very reason.
As for the quantum mechanics only reducing the effective keyspace by half, I cannot say anything about that but [citation needed]. I'm greatly interested in any papers that show any kind of effective limit for quantum mechanics. I don't know that is true, and by all other accounts it could allow one to slice through crypto like butter precisely because it bypasses brute force entirely in some cases.
At a very high level of abstraction, encryption is merely a simple mixing process by which it's vastly more expensive to perform de-mixing without some critical kind of knowledge. You're only arguing that a brute force defense against de-mixing without key possession is physically precluded in a very limited use case where the brute force is strictly limited to the keyspace provided by permutations alone. That's an oversimplification, and ignores whole hosts of ciphertext-only attacks, and the methods by which the keyspace for brute forcing, is reduced. Many of which focus on the random numbers used by the method, and not the method itself.
It's almost always about reducing effective keyspaces to be brute forced. That typically involves every step of the process, which by definition, includes random number generation and key exchange (where appropriate).
Technically, lunchtime is at any moment. It's just a wave function.
(Score: 4, Interesting) by stormwyrm on Thursday May 29 2014, @01:15PM
Just had to make a few simplifying assumptions. Cryptosystems are complicated beasts, as you evidently understand as well as I do, and any vulnerability in any one area can and probably will eventually be discovered and exploited if someone cares to do so. The OP I replied to was talking about brute force attacks, and was saying how those would all eventually become feasible given advances in computing power, and speculated that that could be one reason why TrueCrypt was abandoned, just when an auditing project has gone underway that is intended to ensure that the code is solid. I didn't buy it, and considered the OP's other two speculations to be far more likely, because a simple brute force attack on the underlying block ciphers is infeasible with our current knowledge of mathematics and physics. That was all I was trying to argue, and you had to go and muddy the waters with all this talk about other components of cryptosystems that might be the source of vulnerability. :) I was not trying to argue the about the security or lack thereof of TrueCrypt as a whole.
Note that I never disputed the assertion that there might be vulnerabilities in TrueCrypt that result in its being insecure. This is actually highly probable, as the codebase is complicated and has not been fully audited as of this writing, and the true authors are anonymous. But the fact that these vulnerabilities probably exist doesn't sound to me like a reason for the maintainers of TrueCrypt to completely abandon their work the way they have, which is the real topic of the discussion. Something smells very fishy here, and what's happened to their site makes something like an NSL or its equivalent a more likely explanation.
And you were asking for a citation for why I say quantum mechanics can probably only cut the key search space in half. Here it is: Bennett C.H., Bernstein E., Brassard G., Vazirani U., The strengths and weaknesses of quantum computation. [arxiv.org] SIAM Journal on Computing 26(5): 1510-1523 (1997).
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by edIII on Thursday May 29 2014, @06:47PM
Well, I do agree that right now attempting the entire keyspace without any shortcuts is highly likely precluded by physics. That's what has provided all the momentum to work against the other components.
I just to tend to disagree with the assertions that we should rest on our laurels so to speak and concentrate all of our efforts on shoring up implementations. To be completely honest, it just smells fishy and full of hubris. I'm suspicious and skeptical by nature and any time somebody seems to be saying something is near perfect and astronomical I tend to immediately wonder why it's being said, not that it was said. I have to muddy things up :)
Now on that, we agree completely. It's far more likely IMO, that government got involved at a low level to attack implementation or other components and backdoor it, as we are talking about spying, logistics, and human behavior, not mathematics.
Thank you very much for the citation. I got some reading to do...
Technically, lunchtime is at any moment. It's just a wave function.
(Score: 1) by Fry on Thursday May 29 2014, @09:13PM
quantum mechanics can do no more than halve the effective keyspace, so a 256-bit keyspace becomes effectively 128-bit.
2**128 != 2...
(Score: 1) by fnj on Thursday May 29 2014, @10:10PM
Unless, you measure keyspace in number of bits needed to represent all possible keys, rather than the number of all possible keys.
(Score: 2) by maxwell demon on Thursday May 29 2014, @09:24AM
I don't buy your energy limits (reversible computing can theoretically run on arbitrary low energy), but I agree on your conclusion that brute-forcing is impossible, just on different grounds:
Imagine you had a million computers where each single one is as powerful as the currently most powerful supercomputer. [top500.org] Let's further assume you can run it at peak performance. Imagine in addition that you have a super efficient algorithm which can test a single key as fast as multiplying two floats (so that the FLOPS are directly translated into Keys/s). So your million supercomputers are able to test about 5.5*10^19 keys per second.
The average number of tests you need to brute force a key (assuming you have no quantum computer, of course) is half the number of available keys. So for 128 bit keys, it's 2^127 ≈ 1.7*10^38 tests. That is, to brute force a 128 bit key, you'd need 3.1*10^18 seconds, or about 10^11 years. That's in the order of magnitude of the age of the universe.
To brute force a 256 bit key with the same setup, you'll need 2^128 times as much time, that is, more than 10^38 times the age of the universe.
OK, so there's Moore's law. Well, let's assume that it will hold indefinitely (which it certainly won't), and let's ignore that it's actually about transistor density. So if the available speed doubles every 1.5 years, this means that in 90 years, you'll be able to crack a 128 bit key in a year (but then, whatever I encrypt, I won't care about whether it is cracked in 90 years; and anyway, nobody will consider it important enough to spend a year on decrypting it), and in 192 years you will be able to crack it in a second (still assuming you have a million of the world's most capable supercomputers of the time). Of course, at that time the 256 bit key will still need a time comparable to the age of the universe. So unless you care about whether someone will read your stuff 400 years in the future, even unrealistically optimistic assumptions about computing power will keep your 256 bit encryption safe from brute-forcing.
OK, so what if we actually get a quantum computer? Well, since we are talking about brute-forcing, the algorithm of choice would be the Grover algorithm. The Grover algorithm gives a square root improvement, so it effectively halves the key length. Now the operations per second of a quantum computer may be different from a classical computer, but I think it can be assumed that it is never faster than a classical computer in that metric (after all, you can do classical computing on a quantum computer). So at worst the quantum computer would brute force the key as fast as a classical computer would for half the key length. In other words, even with quantum computers, your 256 bit key should be safe against brute-forcing for the next 200 years.
Note that all that only refers to brute-forcing; other methods to break the encryption may of course make your key unsafe much earlier (like e.g. public key encryption based on prime factorization is vulnerable to quantum computers using the Shor algorithm).
The Tao of math: The numbers you can count are not the real numbers.