News for hackers. Stuff that matters.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by Xcelerate on Friday June 14, 2013 @01:53PM (#5881316)
I have a question that perhaps a cryptography expert could answer for me.

My father told me when he was young, he visited Oak Ridge National Labs on a trip, and while there, they told him they had satellites that could read the print on a newspaper. At the time, it wasn't classified information; it was just something that nobody knew. Approximately 15-20 years later, satellites with that capability became well-known. This indicates to me that top secret technology is probably somewhere around 15-20 years ahead of what the general public knows about. This may be less true today than it was back then since nowadays the equipment and factories to develop state-of-the-art technology run in the billions of dollars.

Where I'm going with this: is it reasonable to assume that "future technology" 20 years from now could crack AES-256 or PGP? If so, it seems reasonable to me that the NSA could already crack today's encryption for high-priority data. Add that to the fact that they tend to hire the very best experts in the field (mathematicians and cryptographers) and it doesn't seem entirely unreasonable to me that their decryption technologies are pretty good. Of course, I'm not talking about better technology in a brute-force sense; it would still be impossible to crack 256-bit encryption. I'm talking about algorithmic weaknesses.

But then again, I have only a basic knowledge of cryptography. Would any experts like to comment?

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by lordgilman on Friday June 14, 2013 @01:58PM (#5881356)
This has come up in the past on HN. As I understand it the newspaper story is bull. As for advancements in technology the answer is likely no - producing that technology requires an entire toolchain/industry that the NSA is unlikely to replicate with its size. The only shot the NSA has at pulling ahead of us is with entirely mathematical things like crypto (which they did at least in the 70s with differential cryptanalysis). With math you can simply hire a bunch of smart people and throw them in a room together which is much less capital intensive than the massive, fundamental research needed to advance technology ahead of the industry.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by cube13 on Friday June 14, 2013 @02:05PM (#5881391)
>This has come up in the past on HN. As I understand it the newspaper story is bull.

Pretty much. The same effect that causes stars to twinkle limits the resolution of space-based spy satellites imagery of the ground.

http://en.wikipedia.org/wiki/Astronomical_seeing

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by Xcelerate on Friday June 14, 2013 @02:16PM (#5881464)
That's for distant stars though, isn't it? I mean, just with Google Maps you can see the mirrors on a car. Newsprint isn't that much of a step up.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by makomk on Friday June 14, 2013 @02:25PM (#5881521)
Google Maps uses aerial photography from planes for the high-resolution layers of their maps, not satellite imagery.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by Xcelerate on Friday June 14, 2013 @02:33PM (#5881578)
Huh, interesting! I never knew that. So then I'll need to ask my father about what he was told again. Maybe something got misinterpreted along the way.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by enoch-root on Friday June 14, 2013 @05:58PM (#5882760)
It probably was that you can see newsprint, not read it.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by JshWright on Friday June 14, 2013 @03:36PM (#5881986)
While it's true that the stars are very distant, the only atmosphere that the light passes through is same atmosphere the satellites have to peer through (resulting in the same amount of distortion)
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by dllthomas on Friday June 14, 2013 @05:47PM (#5882709)
Hm, but with angles, distance matters to right? Bending light 10 degrees will mean a much bigger difference light-years away than a couple hundred miles away. That said, I could easily be missing something...
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by mediaman on Friday June 14, 2013 @08:59PM (#5883389)
The light isn't being bent light-years away. It is being bent at the beginning of the atmosphere, resulting in the same degree of bending as the satellite has to deal with.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by correctifier on Friday June 14, 2013 @02:30PM (#5881557)
All of the detailed views in Google Maps are actually aerial photography rather than satellite images. Much easier to get that kind of detail from 1500ft.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by ErsatzVerkehr on Friday June 14, 2013 @04:10PM (#5882181)
Not just "seeing" (atmospheric turbulence), but also diffraction.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by Xcelerate on Friday June 14, 2013 @02:05PM (#5881384)
> As I understand it the newspaper story is bull

Could you clarify what you mean by this?

And yeah, I should have been more clear in my original question; I was lumping mathematical advances under "technology".

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by marssaxman on Friday June 14, 2013 @03:05PM (#5881796)
The resolution of a lens at a given wavelength is determined by its diameter (Rayleigh function). We know how big the launch vehicles are, so we can estimate the largest size a spy satellite's mirror could be, and we can use that to compute the maximum resolution a satellite could have; it turns out to be something around 5-10 cm. In order to resolve a newspaper from near-earth orbit, you'd need a lens bigger than the ISS, and if such an object existed it would be one of the brightest objects in the sky.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by ErsatzVerkehr on Friday June 14, 2013 @04:12PM (#5882196)
Would it be possible to improve the resolution of optical imagery using a synthetic aperture?
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by jlgreco on Friday June 14, 2013 @05:43PM (#5882692)
Yes, aperture synthesis is possible with optical wavelengths. I don't know how practical it would be to actually use with spy satellites, or how much of an improvement they could see with it.

Keep in mind that there are a lot of people that track satellites, even spy satellites, as a hobby. I haven't heard of anyone discovering two or more satellites orbiting in the sort of tight formation you would expect would be required for this.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by marssaxman on Friday June 14, 2013 @04:44PM (#5882377)
Beyond my knowledge, sorry.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by gregholmberg on Friday June 14, 2013 @05:40PM (#5882683)
Yes, much finer optical resolution is possible if you use multiple instruments separated by a controlled interval.

In radioastronomy, there are arrays of dishes that use this technique. There are good pictures in the Wikipedia article. [0]

One military implementation was a connected three-satellite constellation, built by the US Navy for scanning the surface of the world's oceans. [1]

But those tools work in (relatively) long wavelengths.

I have never heard of free-flight multi-aperature interferometry that works in optical or near-optical wavelengths.

.

[0] "Very-long-baseline interferometry" https://en.wikipedia.org/wiki/Very-long-baseline_interferome...

[0] "How VLBI Works" https://en.wikipedia.org/wiki/Very-long-baseline_interferome...

[1] "White Cloud | PARCAE | NOSS" https://en.wikipedia.org/wiki/Naval_Ocean_Surveillance_Syste...

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by drzaiusapelord on Friday June 14, 2013 @02:26PM (#5881531)
> This indicates to me that top secret technology is probably somewhere around 15-20 years ahead of what the general public knows about.

Err, maybe in optics at the time, but you can't just generalize like this. You can't consistently be ahead of everything all the time. More than likely the NSA suffers under Moore's law like everyone else.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by akira2501 on Saturday June 15, 2013 @12:34AM (#5884055)
I wouldn't be that sure. The NSA made DES _more_ secure in the 1970s by influencing IBMs design of the S-Boxes, regular cryptography research didn't even discover this until 1992.

This means that the NSA understood differential cryptanalysis 22 years before non-NSA researchers did. Their ability to brute force is meaningless if they have techniques to obviate it's necessity.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by betterunix on Friday June 14, 2013 @03:36PM (#5881983)
"Where I'm going with this: is it reasonable to assume that "future technology" 20 years from now could crack AES-256 or PGP?"

There are a few related issues here, and so the answer is a bit complicated.

The only evidence for the security of AES is heuristic, based on testing the output of the cipher to check for properties that secure block ciphers should have. Some new attack strategy could completely undermine AES. Similarly, PGP relies on block ciphers and hash functions that are based on such evidence.

On the other hand, public key cryptography has proofs of security under certain assumptions about the complexity of certain problems. A proof that P != NP is necessary to prove that PKE is secure, but it is not sufficient on its own and we do not even have that much.

Now, assuming that (a) the heuristic evidence for AES and various hash functions is a reliable indicator of security and (b) that the assumptions are computation complexity are correct, then both AES and PGP can be used essentially indefinitely. The reason is that your key size can continue to increase -- for AES, you can iterate the cipher (e.g. "triple AES"), and for PGP you can keep making your keys larger (16384-bit ElGamal?), and you will always be able to stay ahead of your opponent. There are issues with this approach, of course -- it would take a lot of computing power to actually use 16384-bit ElGamal, and eventually it would become impractical, which is why there is so much interest in elliptic curve crypto (which allows shorter keys to be used for the same level of security).

So the answer is, "Yes, from one perspective, No from the other."

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by megablast on Friday June 14, 2013 @02:42PM (#5881636)
> My father told me when he was young, he visited Oak Ridge National Labs on a trip, and while there, they told him they had satellites that could read the print on a newspaper.

It might be easy to find out. Just check when the NSA cancelled their newspaper subscriptions.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by B-Con on Saturday June 15, 2013 @12:58AM (#5884111)
There's a general question among cryptographers: How far ahead of the general public is the NSA?

The answer: We don't know. Interestingly, back in the early 90s they were maybe 15ish years ahead of us. Decisions they made back then weren't understood until the 2000s. However, the gap may have been closed somewhat as of late. The public found flaws in SHA-1 (an algorithm by the NSA) in the 2000s that we believe the NSA didn't actually know about yet.

A general note on cryptography security margins (not really an answer, sorry, just some thoughts): The margins are designed to take into account future advances in technology. The community chooses the problems with the most conservative, best understood parameters, and that seem to be the least-likely to experience a break-through. As well, it tends to pick things with margins like "40+ years", meaning that even if we continue to improve our attacks and computing power at the same rate we have been, it is generally expected that it'll take at least 40 years before we're good enough to break it. (Obviously the experts turn out to be wrong sometimes.)

The community thinks very long term and tries to avoid ever picking anything that is very possible to be broken in just 20 years. It takes (in rough terms) at least 5 just to get through the review process and get the algorithm into standards, another 5 to get it into wide-spread usage, and another 5 to transition away from it. So a very popular crypto algorithm probably needs at least 15 years from its introduction run its life cycle, assuming theres no lull of happiness where it's just existing as a secure, commonly used standard. So there's little point in introducing any algorithm that is anything but a very low likelihood of being broken in 20, because it would spend only a fraction of it's lifespan serving as a widely-used, secure standard.

Last point: Breaks tend to be slow, and big breaks are usually smelled very far in advance. When we're 10 or so years out from a big break, we have a good chance of knowing it and we can start to transition away. Someone 20 years ahead of us may very well only find big breaks just before we start to migrate away from the algorithm.

Due to that, we might optimistically (optimism has no place in crypto, I know ;-)) think that an adversary 20 years ahead of us has relatively minimal advantage.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by ErsatzVerkehr on Friday June 14, 2013 @04:09PM (#5882173)
> they had satellites that could read the print on a newspaper.

This is physically impossible, for the reasons given by marssaxman below; specifically, the resolution of an imaging system is limited by diffraction. In order to read a newspaper from orbit, you would need a ridiculously large aperture. Furthermore, you've certainly seen declassified Cold War satellite and aerial (U-2) imagery. You know what it looks like. Do you seriously believe they had something else that could read newspapers?

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by mey on Friday June 14, 2013 @02:25PM (#5881522)
Assume that over some time frame a crypto solution (the entire system matters as it's very easy to use encryption insecurely) will be compromised. You are essentially buying yourself time. So the question is how much time do you need to buy yourself.

Ok, so even if you select a key length of something very large which depends not only on bytes of the key but also the encryption algorithm as well. For a 4096 bit key that would be 1.0443888814131525066917527107166e+1233 combinations, assuming someone tried to brute force this at 100000 checks per second (a low estimate) it would take roughly 1.655867708988382335571652572800330388413185326368886003... × 10^1220 years to crack on average assuming the birthday paradox.

2^4096 / 2 / 100000 / 60 / 60 / 24 / 365

So that's a freaking long time to keep that data secure. Even radically scaling up the brute force attack across the entire world would be akin to boiling the oceans. (Not going to do out the cpu/watt/check number calculation to determine how much energy it would actually take compared to boiling the oceans...)

So are you safe? No because starting in WWII very smart mathematicians were finding ways to crack the algorithms and find patterns and holes in the encryption solutions that made the search space orders of magnitude smaller. So the best thing we can do is select well attacked, well researched but still secure systems, use a good key length and pray (I am not a religious man).

Edit: If you wish to be truly paranoid (don't recommend it), most of the important crypto research has been done by state organizations, this is how AES was selected from a group of submitted designs to NIST. Conversely there are few still secure and well researched algorithms besides AES out there, (Elliptic Curve basically, but those designs are under patents so not widely available etc)

Edit 2: Also wikipedia is a great starting point for understanding, but is not always complete. Still haven't seen it probably explain initialization vector or nounces before.

Oh and one last thing http://xkcd.com/538/

See

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

https://en.wikipedia.org/wiki/Brute-force_search

https://blogs.oracle.com/dcb/entry/zfs_boils_the_ocean_consu...

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

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

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

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by Xcelerate on Friday June 14, 2013 @02:35PM (#5881600)
I'm not sure you saw the last part of my post :) I mentioned the same thing about brute-forcing and focused on the mathematical weaknesses aspect of it. I have written some ECDSA code myself from scratch so I am familiar at least with the very basics of it.
Re:NSA-proof encryption exists. Why doesn’t anyone use it? by mey on Friday June 14, 2013 @02:43PM (#5881641)
Yeah I think I started writing before I really got your question, my apologies :)

It is very possible that government based research on crypto cracking is several years ahead of the rest of the world, but the attitude to these systems around the time of the dot com bubble was switching from security through obscurity to working in the open. The reason is the research cuts both ways, the US relies on AES as much as you or I. If there is a problem with it, they would be burned as well.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by jlgaddis on Saturday June 15, 2013 @02:17PM (#5885827)
> the US relies on AES as much as you or I

Yes, but the government also has other (non-public) algorithms/ciphers/etc. that are used internally.

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by enoch-root on Friday June 14, 2013 @06:09PM (#5882803)
I don't know why you're saying Elliptic Curve is not widely available, here is an Elliptic Curve Diffie-Hellman implementation guide from the NSA itself: http://www.nsa.gov/ia/_files/SuiteB_Implementer_G-113808.pdf

Those patents are quite questionable anyway: https://en.wikipedia.org/wiki/ECC_patents

Re:NSA-proof encryption exists. Why doesn’t anyone use it? by rorrr2 on Friday June 14, 2013 @07:16PM (#5883092)
If you really feel paranoid, why not use 3-4 different encryption algos in a chain? The probability of ALL of them being broken is extremely low.