My speculation: NSA can break AES crypto

It's entirely possible (and even likely, since AES took performance into account so much) that TwoFish is more secure than AES. That's very different from saying that AES is not secure, or that it can easily be bruteforced.

We still haven't reduced the 128bit key space enough, even with theoretical attacks, let alone the 256bit key space.

 

I never said it's not secure (although the evidences might not be public yet).
I said it's one of the most unsafe regarding the AES finalists

 

Just going by the context of the topic.

 

Others have touched on different flaws in this reasoning, but there hasn't been a comprehensive debunking.

1) First of all, as I pointed out here, brute force does not count as "breaking" a cipher. You simply guessed enough combinations and stumbled across the correct key. That has absolutely nothing to do with the strength of the algorithm.

2) Second, we've already discussed this "AES broken" stuff ad nauseam. Here's one recent one. And here's another where I link Schneier on AES.​

This is basically the sum of it: It's all matter of simply running the numbers. You can easily calculate roughly how long it would take to brute force an encryption. You hear stuff like your OP all the time: "supercomputers this, quantum computing that, you can break any encryption, blah blah blah."

Nonsense. Just do the math. I went into this and offered a great tool for this here. Anyone can download the spreadsheet and plug in the numbers. See how long it would take. It's simply a matter of the number of possible combinations from the keyspace used, divided by 2 (Law of Averages), divided by the number of guesses you can make over a given time period.

Just do the math
Of course the root of your argument is "with computing power these days, the number of guesses is astronomical, so you can crack anything". Again, bologna. As touched on in the Ars Technica password article, (and the 25 GPU cluster article linked within) the two main factors are the hardware at the attacker's disposal, and the hashing algorithm used. So just as an example, the 25 GPU cluster last year was a pretty big deal. But while the cluster could bust out 350 billion-guess-per-second on NTLM...that drops down to 71,000 guesses when Bcrypt is used instead.

At that rate it would take literally almost 49 YEARS to crack even just an 8-character random alpha-numeric password. (And remember this is all that computing power running nonstop, 24/7, that entire time.)

But just for fun we can bump it up. Let's hypothetically, just for the sake of this demonstration, to show you just how bogus your claim is, pretend there is a system out there that can make 100 Trillion guesses per second. That's 360,000,000,000,000,000 guesses per hour. (I'm pretty sure that even on the fastest (i.e. weakest) hashing algorithm, there is no system out there that can achieve this speed.) But let's just do the math.

At that many guesses per hour, it would still take almost 32 years to crack just a 13 character random alpha-numeric password. Bump it up just one more character to 14, and you're looking at 1,966.29 years.

Just 14 characters, at 100 trillion guesses per second. TrueCrypt recommends passphrases be more than 20 characters.

Conclusion
So the moral of the story is, just use a strong passphrase, and unless someone actually does break the cipher (i.e. finds a way to decrypt ciphertext faster than brute force), then you pretty much have nothing to worry about. And as others have said, there are a number of strong ciphers that have had no successful cryptanalytic attacks in years of scrutiny. All three of the AES finalists are in this category. Use any one of those, with a good hashing algorithm (and proper implementation, of course), and a strong passphrase, and security is all but 100% guaranteed.

Epilogue
As for quantum computing, I know I've stated at least once before a quantum computer will simply reduce the complexity of an attack by a factor of a square root. So effectively it's only going to cut the keyspace in half. That's it.

 

You can have 5.000 Mhash/s @ 5W power-consumption for about USD 270 .
It's called ASIC, these are specifically made for hashing in bitcoin-mining,
but nothing prevents the NSA from having their own (crypto) ASIC's made :
http://www.bitcoinx.com/bitcoin-mining-hardware/

I don't think NSA can 'break' AES,
but I do believe they can bruteforce almost any password/phrase that most humans can actually remember,
if they really want to !

(That's quite a lot of passwords you can not use if you start doing the math ..)

Also assume that any password/phrase, in any language (including '1337' and 'klingon'),
contained in any 'leaked' pw-lists, or any combination of passwords/phrases from any leaked list,
can not be used.
You can not use any part of any password you have used online,
to 'construct' a 'secure' password for 'off-line' (disk/file) encryption with AES .
And even worse, you can't use any part of any password anybody else has used on-line,
because 'they' have those in the dictionary to !
'They' also have every book ever written in that list,
books are after all a classic cryptographic tool .

This practically leaves you with PRNG's, another area that NSA has had their
dirty hands on, with the result that they can now (2010)
read huge amounts of illegally intercepted, stored, encrypted transport-data 'protected' with 1024 bit RSA-keys or smaller .
As can any other 3 letter agency in any country .

 

I guess that all depends on what you think "most humans can actually remember", doesn't it? As mentioned in one of the links here, there are multiple ways to create strong passwords that one could remember.

For one thing, just make it a passphrase (that isn't found in any public text, of course...A phrase doesn't have to be a nursery rhyme or a bible verse for a human to remember it).

Remember "ACollectionOfDiplomaticHistorySince_1966_ToThe_PresentDay#"?

I think most people could remember that even in just a few minutes. I'd also consider that pretty darn strong.

What's with all this "part" stuff? So because the word "diplomatic" is an actual word...I can't use it in any passphrase, ever? Because they'd be able to guess that entire phrase above...simply because all or some of the words appear in the dictionary?

That makes absolutely no sense.

 

Re - Dictionary words.

Using them "supposedly" reduces the attack to reveal time ! So better to use garbage etc, or a very Long passphrase.

 

That's basically my point.

Again, see the third link here.

 

My favorite method is first letters from memorable quotations.

For example ...

... becomes ...

whtttbsetamacettaebtcwcurtatalelatpoh

In practice, I wouldn't use such a famous quotation. But I'd use one that I could find somewhere, in case I forgot part of it.

 

Most humans can't reliably remember something like this :
"ElQzDk80YmUd9cAJmuuhUFW9LMVd40Tny_ZulKBXMXJn0Bbg6j"
If you want to be 'safe' against the NSA, you can not use a passwords that contains actual words, even if you try to obfuscate with '1337' or substitution .

But my point is : 'They' do not just blindly run a bruteforce attack,
'they' have vast knowledge of the passwords actually used 'in the wild' plus all their psychologists and linguistic experts know a lot about how people construct passwords . And since 'they' can monitor all your on-line activity, they can learn quite a lot about how your brains work and how you normally construct passwords for on-line use .
(As you are probably aware, humans suck even more than a NSA-weakened PRNG at creating anything that really IS 'random' )

If Snowden is right and 'they' can perform a trillion (US) guesses/s, there are
A LOT of passwords you can not use, just to stay 'safe' for one hour !

 

This was the system Beale used to compile the key of his first cryptogram, which was broken in early 1900.
The other 2 are still to be broken though...

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

 

by the time they have broken anything they will had dug up and arrested a skeleton

 

My speculation is that the NSA doesn't have the time or resources to even attempt to bruteforce AES or PGP for people unless they have strong evidence the person could be a terrorist or hactivist or otherwise a high value target, whereas they probably scan all unencrypted traffic for keywords and what-not because that's the low hanging fruit and they need to do something to justify the billions of $ spent on collecting all the information.

 

My point is your passphrase doesn't have to be something like that to be virtually unbreakable. Again, just look at the links.

Or, tell me what dictionary is going to contain:

"Enigm from WildersSecurityForums doesn't know what he's talking about"

I guarantee that passphrase will never be brute-forced.

Bologna. Sure leetspeak is a waste of time, but again, even if you combined all the computing power and all the dictionaries in the world...the phrase I posed above is more than likely still never going to be brute forced.

No one ever said they did. I think you'd be hard pressed to find someone here who wasn't aware of password dictionaries. Again, my point is, it doesn't matter. Just because your passphrase contains words that are found in the dictionary, that doesn't automatically mean it can be brute forced.

Again, find me a dictionary that contains:

"If you think this is in 1 of your NSA dictionaries, you've got another thing coming"

You show me someone who brute forced that, and I'll start to listen.

First of all, the resident expert feels that that's an exaggeration. (Which makes sense, as that's some serious computing power (even for a govt agency)...and if that was the actual capability, one would think Snowden would say something much higher, to make sure they're on the safe side.)

Second, once again, I already did the math (in this very thread, and elsewhere) for one hundred trillion guesses per second.

So unless you can find me a dictionary that contains the passphrase:

"Even at 100 Trillion guesses per second, you will NEVER guess this passphrase. Ha-ha-ha."

...then you're simply wrong that a human couldn't remember a virtually uncrackable password.

 

I wonder how uncrackable this might be ?

"Looks like maybe PooseyII is back posting again under a different username"

 

You can remember 20 random (maybe more, depends on you) with practice.

For example:

6^rc, ISPTBU urju7 #~'y

I just committed to memory after 5 minutes.

I use KeePass to generate, and then go to "Preview" Then I pick one that has some "rhythm" to it, to memorize. Do it in chunks.

6 "up" rc comma SPACE "ISPTEEBOO" SPACE "urjoo7" SPACE #~'y

KP gives it 137bits for what that's worth.

You can probably learn a few strings and combine if you want, for 40. Obviously, you can't learn hundreds, but these are good for KeePass/LastPass and then use those for everything else.

It just takes some work and the desire to do it.

PD

 

Because even $10 billion dollars won't buy you anywhere near the computing power needed to brute-force a 128 bit cipher before the sun burns out. The math is simple really. A 128 bit key has 2^128 possible values. To convert it into base 10, it would be 3.4 x 10^38. This is an astronomical number. Only 2^61 seconds have passed since the big bang (13.7 billion years). Of course, you probably wont have to search the entire key space to find they key. You will find the key, on average, 50% of the way through the search. 50% of 2^128 is 2^127. So basically you subtract only one bit.

Here's a hypothetical to consider: We all know they are building a massive data center in Utah. But, let's don our tin-foil hats for a minute and suggest that with the help of ET beings from the constellation Orion that they have built a vast underground lair in Utah that is the size of the entire state of Utah itself (84,899 sq. miles). Now let's say they, with the help of ET, have fitted every single last square inch of this massive facility with one high powered ASIC chip built specifically to do AES computations. So doing the math that would mean they are able to fit 3.4 x 10^14 computer chips in this facility.

Now let's assume each chip can calculate 1 trillion AES keys per second (very generous even by NSA and ET standards). Doing the math: 1 trillion X 3.4x10^14 = 3.4 x 10^26 calculations per second if all these chips run in parallel. This computer would make IBM's Jaguar look like a 2 bit pocket calculator.

Now we know they need to search through 2^127 keys on average, so let's see how many seconds it would take to search this space: 2^127 / (3.4x10^26) = 500,415,245,472 seconds. Let's convert this into years: 500,415,245,472 / 31536000 seconds in 1 year = 15,868 years.

Bottom line: it ain't happening. And that is with me assuming one chip can do a trillion checks a second. In reality, even the world's largest supercomputer (with thousands of processors) can barely do that many combined. The math (not to mention energy requirements) are not on NSA's side.

We knew this before the Snowden leaks. All the leaks did was confirm to the skeptics out there that things are far worse than they had imagined. Now even the people who made fun of the "tin-foil-hatters" are having to change their tune. Even Bruce Schneier, who has never been a conspiracy theorist, is basically saying that nothing in the public crypto world can be trusted. He thinks the math is still good, but that the code is subverted. Either one is as bad as the other as far as practical security is concerned. I mean if the math is still good, that's great. But it doesn't mater if all our software are belong to NSA.

But what is for certain is if NSA has broken algorithms they are not doing it by brute force (as I proved above). This doesn't mean they don't have shortcuts, however.

It's certainly possible they have, but I doubt it. Why? Because AES is not a big target. I say that because if you understand how most encryption on the Internet works, the AES key is protected by public-keys (it's called a hybrid cryptosystem). Break the public-key and you get free access to the AES key by default. Thus, if I worked at the NSA I would tell my cryptologists to focus on breaking RSA and solving the discrete log problem. Forget AES, you don't *need* to break it.

Besides, it is widely known that block ciphers are a much tougher nut to crack than public keys because the "proofs" behind public keys are, well, absent. We simply do not know if it is truly "hard" to factor large integers. We think it is, but there is no mathematical proof that it is hard. There is more evidence that block ciphers are more difficult to break due to the sheer effort that has went into it with very little (practical) headway. On the other hand, there have been big advances in integer factoring over that same time span, with a breakthrough in discrete logs announced just a few months ago.

It's highly doubtful they are using brute-force to do anything as I proved above. They know, as well as I, that it's simply not a mathematical reality and is a futile endeavour to even try.

What they *might* be able to do is find some weakness with AES that reduces its complexity from 2^128 to, say, 2^80. That would be a monumental break, but I doubt even NSA with its expertise has managed it. The public crypto world has only been able to shave off 2 bits from AES in about 15 years of trying. I am sure NSA can do better than 2 bits, but they would need a very large break to make brute-forcing practical.

No, what's going on here is they have given us weakened standards (weak RNG's, weak protocols) and have worked with industry to backdoor pretty much any software of any interest (Windows and Apple are both owned, as is most hardware).

 

I think 128bit is reduced to 1^119 or something like that.

 

The best publicly known attack has reduced AES-128 to AES-126. See "Biclique Cryptanalysis of the Full AES." It's the first key-recovery attack on all rounds of AES that doesn't require weird scenarios like related keys. This is after almost 15 years of trying by the world's best cryptanalysts (at least the best publicly known cyptanalysts), and all they have managed is 2 bits.

NSA can probably do better, but I doubt they have reduced the security to below 100 bits. To be practical (even with NSA's computational resources), you would need to bring it closer to 80 bits.

 

But if NSA have a largescale, working, quantum computer, then they also may be capable to reduce AES-128 to a 2^64 attack. But then we have AES-256, which should protect against a quantum computer attack

 

They don't. That's one of the few things I will bank on. If they did, they wouldn't need that massive Utah facility (which is going to use a lot of its space for classical supercomputers). Also, if they had working QC, they would have no reason to be stealing everyone's crypto keys and to be inserting weaknesses into crypto standards..

 

lol so true. Here's another thing. If they think your HDD is too difficult to crack they could simply use Rubber-hose Crypto-analysis on you. They could beat the password out of you, without having to break your unbreakable cipher and encryption.

Torture works very well as it will make all but the most hardened people crack under pressure...hell even they may crack under enough torture. And all effective torture is psychological...you can cut a man and whip a man to death and he could in fact be feeling immense pleasure. That's a textbook masochist. But if you threaten to inflict unimaginable pain to his family and loved ones, he will feel the pain and start giving you in the information you seek.

 

QC can not crack all decryptions, far from that, it will only split the bitstrength in symmetrical encryption. They will still need backdoors and such things: http://en.wikipedia.org/wiki/Post-quantum_cryptography

Some crypto libraries have already implemented McEliece asymmetric encryption. Keccak for hashing etc.