SoylentNews is people
SoylentNews
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: 5, Interesting) by juggs on Thursday May 29 2014, @06:46AM
At least I wish the rumour / media mill had a TILT mode like old pinball machines - it should be invoked when the amount of speculation around a particular topic exceeds the availability of genuine attributable information by a certain factor (or in this case exponential factor).
Let's bring some rationality to proceedings.
What's the history?
TrueCrypt v7.1a has been around since early / mid 2012 (to my knowledge). It provides a tool for creating encrypted volumes as files as well as plausibly deniable hidden filesystems.
What's Plausible Deniability?
In this case it's an encrypted filesystem or volume that an adversary cannot prove exists. i.e. without the correct tool to access it and the correct passphrase to decrypt it, it is indistinguishable from random guff (or noise) on a hard drive. i.e. even in bastard countries (looking at you England) where failing to provide keys to unlock an encrypted volume is reason for jail time you have a way to secure your data.
Why Have TrueCrypt's Developers Remained Anonymous - That's Got To Be Dodgy Right??!
Think about this for a while. If you were developing a tool that enabled the ability to create entire computer filesystems that could be hidden from view from even the most well funded national intelligence agencies, what would you do?
If you make yourself known you open yourself to all manner of coercion from both state and criminal actors. If you coalesce as an incorporated business / not for profit / charity then you are subject to the whims of the jurisdiction(s) that a. your corporation coalesces in b. your developers and all associated reside in.
Why The Brouhaha now?
The TrueCrypt site www.truecrypt.org has been redirected to their project pages on Sourceforge at http://sourceforge.net/projects/truecrypt/ [sourceforge.net] which carries all manner of red text warning that Truecrypt 'may' contain unfixed security issues. Along with a massively cut down release of TrueCrypt v7.2 (source and binary) that offers the ability to only decrypt volumes.
What Does It All Mean?
In true QI fashion, I have to raise the table-tennis bat labelled "Nobody Knows".
OK - So Sum This Up Rather Than Wave Your "Nobody Knows" Card Around
If I must. This is speculation all the way down from here on out.
Scenario A
----------
Devolopers of TrueCrypt have had enough and want to give it up. Regardless how mathematically correct their choice of cryptography or perfect their implementation, the ever growing processsing power to brute force encrypted volumes means that anything encrypted today only has a limited lifetime before it is revealed. This is not anything new or stunning - encryption has never been a forever solution, always a "keep stuff safe until past the point it becomes useful" solution.
Leaving the scene with a source and binary that can decrypt all previously encrypted volumes while stripping out all encryption routines is laudable. It's only a matter of time before those encryption routines become brute forceable in minimal time. Best not to offer encryption at all than offer something easily broken.
Scenario B
----------
One or more developers received a secret court order (I'll use the US-centric NSL abbreviation henceforth) to allow access to subvert TrueCrypt to be more compliant to an agency's probing. Rather than take that NSL on face value, the developer(s) in question have taken the project suicide route in whatever fashion open to them that can alert the userbase whilst keeping them safe from a life time in some hell hole gaol for contravening non-disclosure of a NSL.
Scenario C
----------
A TrueCrypt developer was sloppy and an infiltrator managed to subvert every domain associated with TrueCrypt along with code signing keys etc. etc. to be able to pull this off. Even their mailservers are bouncing all messages with recipient unknown responses.
Given the relatively long history of TrueCrypt I am inclined to A > B > C at this point.
One thing is sure, TrueCrypt has passed a point of no return with this. As the developers are anonymous, there is no way for them to reclaim their ground if this was indeed an audacious hack.
The following as points of reference:
Linux Users
LUKS and EncFS - even EncFS within LUKS devices for some layering.
Windows Users
BitLocker (version restrictions apply) if you trust MS - which you must if you run Windows.
Apple Users
Not my thing, so can't help.
(Score: 2) by juggs on Thursday May 29 2014, @06:50AM
I'm sorry that post is so ugly. It was formatted better but I fell foul of slaschcode's "Junk Characters" filter on submitting and was to too ired to redo it all so stripped out my lazy underlining.
(Score: 2) by aristarchus on Thursday May 29 2014, @07:12AM
But the take-away from your post is that Windows users are hosed. But I repeat myself.
(Score: 5, Interesting) by juggs on Thursday May 29 2014, @07:47AM
Everyone is hosed if that is your take-away. Not just Windows users, Linux users, Apple users, Android users, ChromeOS users, ~everyone~.
Run encryption atop your OS, well you have to trust the OS provider and the encryption software provider.
Run OS provided encryption - now you only have one party to trust.
If the OS is complicit then it matters not a jot what the encryption layers on top of it do, you're hosed.
The actual take-away is..... file(system) encryption, fine for preventing casual thieves who purloin your mobile devices from gaining access to your files but it's not to be relied on for defeating snooping.
But then it was never supposed to be a panacea, it does what it says on the tin - encrypts your shit while at rest (for now).
Which makes me think - say you went to the bother of one of these TrueCrypt encrypted hidden partitions then installed OS of choice on it... what prevents the OS of choice giving away whatever crown jewels? Or the underlying hardware for that matter?
Maybe this is the take-away... TrueCrypt was over a decade old and pre-dated mass Internet usage, having a deniable OS then was useful. Now not so much, it is our online footprint that betrays us.
I honestly don't know.
(Score: 2) by Yog-Yogguth on Saturday May 31 2014, @04:07PM
You are largely right. The most important thing to grasp is that TILT is the new default courtesy first and foremost of the NSA: if you are running COTS hardware (as nearly everyone does) you can not trust your hardware. This fact is not because the NSA and others have hardware implants (which they have plenty of) and it is not because they could weaken specific logic gates in whatever chips you are using (they could, it's not science fiction), nor is it because of the efforts of the NSA's TAO and their software (which is likely best of the best and amazingly brilliant), it runs deeper and is because it has become more than apparent and verified that the NSA (and any other such organization whom we might not even know about) does not have any kind of apprehension against using their unlimited clout in order to sift and/or record all data in existence using any means possible.
Sure in exceptional cases that does mean they'll use the aforementioned. It has also been shown that they will use secret courts and secret court orders and "national security letters" and any "legal device" (even if illegal) and influencing industry standards (it doesn't matter all that much whether it strengthens or weakens said standards, since it is clear that what matters to them is that they'll do it to suit whatever they think is in their own interest).
There is no reason to assume that their efforts stops there! Social hacking is always easier. If one can manipulate the foundations of academic research or industry-wide best practices or technical practical solutions it is worth far more than millions of later weaknesses. If you think you own the rabbit hole you want to make it as deep as possible: all the way down for forever, because it becomes tremendously more efficient the deeper it goes, and they have the resources to do just that.
One should by now recognize that the NSA was and will always be a "bad faith" [wikipedia.org] actor (personally this is what hurts the most). This very fact is the negative ramification of the Snowden leaks that is almost suspiciously absent from the reports on the damages caused to the US: the leaks have removed any possibility of "good faith" status for the NSA (and also the US government) and this very "good faith" status was one of the most if not the most useful property/tool/attribute they had.
Why isn't this being spelled out by the reports on the consequences of the leaks? Because they're hoping people won't notice; they're trying to avoid the Streisand effect because they would like to cling on to the incorrect "good faith" status and have as many people as possible continue to assume that they are "good faith" actors.
They can't broadcast one of the most immediate and profound damages because it would exacerbate the troubling truth: they are not the "good guys", they are evil, and they represent the doom of humanity just like the Nazis and the Commies did only with vastly improved technology.
The classic solution to the problem of a needle in a haystack is to set fire to the haystack. It won't matter that the initial motivation was to find the needles to remove and/or destroy them in order to save the hay: the solution remains the same.
Bite harder Ouroboros, bite! tails.boum.org/ linux USB CD secure desktop IRC *crypt tor (not endorsements (XKeyScore))
(Score: 2) by NCommander on Thursday May 29 2014, @09:24AM
Which lazy underlining?; tags should "just work" We do at least know what the underlying issue is with UTF-8 support, though we haven't managed to fix it as of yet.
Still always moving
(Score: 2) by maxwell demon on Thursday May 29 2014, @10:30AM
I guess he didn't use proper HTML tags, but used lots of "-" or "=" for "underlining", causing a repetition filter to trigger
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by NCommander on Thursday May 29 2014, @11:17AM
The entire commenting engine needs a rework. Its on the TODO list, but ENOTIME. THe problem is slashcode basically uses HTML::Validater as its comment engine, and that wasn't really meant to be used in the way we're using it. Ideally, I'd love to rewrite it to use some bbcode based system (something we've gotten requests for), and make it a bit less stupid.
Still, it does work for 95% of comments but bleh.
Still always moving
(Score: 2) by maxwell demon on Thursday May 29 2014, @11:42AM
I don't get the advantage of bbcode. So you write [ and ] instead of < and >? I don't see the big difference (except that the bbcode keys are harder to type on my QWERTZ keyboard :-)).
Now if you supported Markdown for comments, that would IMHO be a true improvement. I have no idea whether it would be more work than bbcode, though.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by NCommander on Thursday May 29 2014, @12:51PM
I feel like an ID10T for asking, but what is Markdown?
Still always moving
(Score: 4, Interesting) by maxwell demon on Thursday May 29 2014, @01:54PM
It's a way to format texts. Unlike bbcode, it doesn't rely on tags. Some of the syntax will be familiar to people previously on Usenet (e.g. quoting by starting lines with > or emphasizing by enclosing in *asterisks*), other will be familiar to people used to Mediawiki (e.g. preformatted code a la <ecode> through indention).
See https://en.wikipedia.org/wiki/Markdown [wikipedia.org] for details.
One site I know using Markdown (with a few extensions) is Stackexchange.
I seem to remember something about plans of offering SoylentNews over NNTP; in that case, the fact that some of the Markdown syntax matches the syntax traditionally used in email and Usenet posts for the same purpose (as well as Markdown text being very readable by itself) might prove useful.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by NCommander on Thursday May 29 2014, @05:38PM
SN over NNTP is a reach goal; definately something I want to do, but no idea when it might happen. I'll look more into Markdown; thanks for the link.
Still always moving
(Score: 2) by juggs on Friday May 30 2014, @02:53AM
Exactly right, I used oodles of === for underlining. It was my own laziness that caused the problem rather than a Soylent code issue.
(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.