Advertisement
GStreamer Conference 2013, 22-23 Oct, Edinburgh
GStreamer, Embedded Linux, Android, VoD, Smooth Streaming, DRM, RTSP, HEVC, PulseAudio, OpenGL. Register now to attend.
Weekly Edition
Return to the Security page
| |||||||||||||
Security quotes of the week
In seeking a balance that puts liberty first, my administration will unwind
the surveillance apparatus to a substantial degree. Some surveillance is
necessary, to be sure. But we will have clear rules and boundaries, and we
will punish those in government who go beyond them. As we have seen
repeatedly in recent years, without genuine accountability, rules and laws
mean nothing.
— Dan
Gillmor hopes for a 2016 US presidential candidate with a focus on privacy
Right now the upper practical limit on brute force is somewhere under 80
bits. However, using that as a guide gives us some indication as to how
good an attack has to be to break any of the modern algorithms. These days,
encryption algorithms have, at a minimum, 128-bit keys. That means any NSA
cryptoanalytic breakthrough has to reduce the effective key length by at
least 48 bits in order to be practical.
— Bruce
Schneier is skeptical of claims of NSA decryption superpowers
There's more, though. That DES attack requires an impractical 70 terabytes of known plaintext encrypted with the key we're trying to break. Other mathematical attacks require similar amounts of data. In order to be effective in decrypting actual operational traffic, the NSA needs an attack that can be executed with the known plaintext in a common MS-Word header: much, much less.
Most internet users would like to be anonymous online at least occasionally, but many think it is not possible to be completely anonymous online. New findings in a national survey show:
— Anonymity,
Privacy, and Security Online, a survey by Pew Internet
(Log in to post comments)
Security quotes of the week Posted Sep 6, 2013 10:25 UTC (Fri) by dps (subscriber, #5725) [Link]
One fact that Bruce Schneier failed to mention is that there is non-negotiable mathematical evidence that no quantum computer could do exhaustive search of n possible keys in less than n^{1/2} time. There is a known way of achieving this limit.
Actually establishing and maintaining a big enough coherent state for long enough to crack a 80 bit key, or factor a 1024 bit RSA key, would imply technology lots of orders of magnitude better than is publicly known.
Disclaimer: I am do not know quantum physics and am not familiar with the current state of the art. I have seen the mathematical evidence that O(n^{1/2}) is the best a quantum key search machine can do.
Security quotes of the week Posted Sep 6, 2013 15:32 UTC (Fri) by intgr (subscriber, #39733) [Link]
I think the way you phrased this is misleading. Yes, there may be no *generic* quantum algorithm that can do better than n^(1/2) complexity in exhaustive search. For breaking symmetric algorithms it may be impossible to do better than that.
But there are specialized quantum algorithms (Shor's algorithm in particular) against the closely related DLP and RSA problems, upon which all current public-key cryptography is based on. Given a quantum computer with enough coherent memory, it would render RSA, DSA, ElGamal, Diffie-Hellmann and their elliptic curve counterparts very weak, at a compliexity of (log n)^3.
It's true that currently existing quantum computers are orders of magnitude less powerful still, but their potential effect on public-key algorithms is certainly scary.
There are some research public-key cryptosystems that resist quantum attacks, but they tend to be a lot less practical than the ones currently in use: https://en.wikipedia.org/wiki/Post-quantum_cryptography
Security quotes of the week Posted Sep 7, 2013 6:24 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link]
You are thinking about a quantum search in an unstructured database ( http://en.wikipedia.org/wiki/Grover%27s_algorithm ), which indeed is at most O(sqrt(N)) efficient.
However, encryption algorithms have a lot of structure and it's not impossible that there are more efficient algorithms. Just like in the classic case, sometimes a cipher has a vulnerability that might allow to lower the brute-force complexity from O(2^keybits) to something lower.
In fact, I totally expect such breakthroughs once quantum computers become more available.
Security quotes of the week Posted Sep 7, 2013 15:43 UTC (Sat) by Karellen (subscriber, #67644) [Link]
For a brief moment there, I thought Gillmor was planning to run for president.
Ah, wishful thinking, making me read what I wanted to read, rather than what was actually there. :-/
Security quotes of the week Posted Sep 7, 2013 21:11 UTC (Sat) by storner (subscriber, #119) [Link]
Seems Bruce Schneier changed his mind about this.
https://www.schneier.com/blog/archives/2013/09/the_nsa_is...
Security quotes of the week Posted Sep 8, 2013 9:09 UTC (Sun) by ras (subscriber, #33059) [Link]
Not really. He says he believes the NSA hasn't broken any of our favourite cyphers (which are oddly the cyphers blessed by NSA). Here "broken" means reduce the work required to below brute force.
He says in your link he believes the NSA is reading most encrypted communications.
Both things can be true, and indeed it plain from the article Schneier thinks they are. Off the top of my head, two ways they can be both true are:
1. They somehow got hold of the keying material. Eg, they asked your encrypted cloud based email provider for them, or they inserted a backdoor into your software.
2. They can get hold of unencrypted text. For example, even though GMail imap access insists on you using SSL, a good deal of the data transmitted between google's data centres in unencrypted.
So we know for example that Microsoft provides unrestricted access to Skype data when they receive a lawful request, even though it is encrypted at both ends.
Security quotes of the week Posted Sep 11, 2013 13:02 UTC (Wed) by ssam (subscriber, #46587) [Link]
So they need large amounts of known plaintext encrypted with the key. If you use full disk encryption, then they have have a few GB standard OS files.
Security quotes of the week Posted Sep 11, 2013 17:57 UTC (Wed) by intgr (subscriber, #39733) [Link] That's still many orders of magnitude from 70 terabytes. :) Schneier's point is that we now have many decades worth of experience in cryptanalysis and lots of practice in seeing how ciphers break. The breaks are usually quite far-fetched, like requiring lots and lots of memory, lots of known plaintext, multiple "related keys" used to encrypt the same data, etc. Interesting fact about cracking DES: despite its known flaws, the requirements to pull off an attack against its weaknesses probably make it more expensive than a straight brute-force attack, using a massively parallel computer (this one alleged to have sold at $10,000 in 2006) to brute force through the 2^56 key space. For brute force, you only need 1 known plaintext and (on average) 2^55 computations, unlike fancy cryptanalysis attacks.
Security quotes of the week Posted Sep 11, 2013 18:08 UTC (Wed) by intgr (subscriber, #39733) [Link]
Another interesting data point, the current publicly best known attack against AES: http://research.microsoft.com/en-us/projects/cryptanalysi...
Brute force requirements against AES-256: 1 known plaintext, 2^255 computations (average)
The attack against AES-128 requires even more, 2^88 known plaintexts.
Security quotes of the week Posted Sep 11, 2013 21:52 UTC (Wed) by mathstuf (subscriber, #69389) [Link]
I didn't read the PDF, but are you saying AES-128 needs more known plaintexts than AES-256?
Security quotes of the week Posted Sep 12, 2013 0:21 UTC (Thu) by intgr (subscriber, #39733) [Link]
Yes, that's what it says. Probably due to the fact that AES-128 has better key schedule.
|
|||||||||||||