4 ms·

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, an

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?

lordgilman 13y ago
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.
- Xcelerate 13y ago
  > 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".
  - marssaxman 13y ago
    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.
    - ErsatzVerkehr 13y ago
      Would it be possible to improve the resolution of optical imagery using a synthetic aperture?
      - marssaxman 13y ago
        Beyond my knowledge, sorry.
        gregholmberg 13y ago
        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_interferometry https://en.wikipedia.org/wiki/Very-long-baseline_interferome... [0] "How VLBI Works" https://en.wikipedia.org/wiki/Very-long-baseline_interferometry#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_System https://en.wikipedia.org/wiki/Naval_Ocean_Surveillance_Syste...
      - 13y ago
- cube13 13y ago
  >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 http://en.wikipedia.org/wiki/Astronomical_seeing
  - Xcelerate 13y ago
    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.
    - makomk 13y ago
      Google Maps uses aerial photography from planes for the high-resolution layers of their maps, not satellite imagery.
      - Xcelerate 13y ago
        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.
        enoch-root 13y ago
        It probably was that you can see newsprint, not read it.
    - correctifier 13y ago
      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.
    - JshWright 13y ago
      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)
mey 13y ago
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/ http://xkcd.com/538/ See https://en.wikipedia.org/wiki/Key_size https://en.wikipedia.org/wiki/Key_size https://en.wikipedia.org/wiki/Brute-force_search https://en.wikipedia.org/wiki/Brute-force_search https://blogs.oracle.com/dcb/entry/zfs_boils_the_ocean_consumes 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/World_War_II_cryptography https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Elliptic_curve_cryptography https://en.wikipedia.org/wiki/Elliptic_curve_cryptography
- 13y ago
drzaiusapelord 13y ago
> 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.
- akira2501 13y ago
  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.
megablast 13y ago
> 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.
betterunix 13y ago
"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."
ErsatzVerkehr 13y ago
> 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?
rorrr2 13y ago
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.
B-Con 13y ago
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.

lordgilman 13y ago

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.

Xcelerate 13y ago
> 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".
- marssaxman 13y ago
  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.
  - ErsatzVerkehr 13y ago
    Would it be possible to improve the resolution of optical imagery using a synthetic aperture?
    - marssaxman 13y ago
      Beyond my knowledge, sorry.
      - gregholmberg 13y ago
        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_interferometry https://en.wikipedia.org/wiki/Very-long-baseline_interferome... [0] "How VLBI Works" https://en.wikipedia.org/wiki/Very-long-baseline_interferometry#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_System https://en.wikipedia.org/wiki/Naval_Ocean_Surveillance_Syste...
    - 13y ago
cube13 13y ago
>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 http://en.wikipedia.org/wiki/Astronomical_seeing
- Xcelerate 13y ago
  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.
  - makomk 13y ago
    Google Maps uses aerial photography from planes for the high-resolution layers of their maps, not satellite imagery.
    - Xcelerate 13y ago
      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.
      - enoch-root 13y ago
        It probably was that you can see newsprint, not read it.
  - correctifier 13y ago
    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.
  - JshWright 13y ago
    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)

mey 13y ago

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/ http://xkcd.com/538/ See https://en.wikipedia.org/wiki/Key_size https://en.wikipedia.org/wiki/Key_size https://en.wikipedia.org/wiki/Brute-force_search https://en.wikipedia.org/wiki/Brute-force_search https://blogs.oracle.com/dcb/entry/zfs_boils_the_ocean_consumes 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/World_War_II_cryptography https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Elliptic_curve_cryptography https://en.wikipedia.org/wiki/Elliptic_curve_cryptography

13y ago

drzaiusapelord 13y ago

> 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.

akira2501 13y ago
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.

megablast 13y ago

> 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.

betterunix 13y ago

"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."

ErsatzVerkehr 13y ago

> 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?

rorrr2 13y ago

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.

B-Con 13y ago

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.