Quasars Used for Encryption 53
space_mongoose writes "According to this NewScientistTech story, intergalactic radio signals from quasars could emerge as an exotic but effective new tool for securing terrestrial communications against eavesdropping"
Hmm (Score:2)
Anybody think this seem odd? An early April fools perhaps?
Re:Hmm (Score:2)
They only appear as quasars to us when the galaxy is pointing in the right direction.
Re:Hmm (Score:3, Informative)
Logic being that, any random number we create is *not* random. i.e all.
And most (all??) encryption (RSA onwards) is based on random numbers.
Even if there is only one quasar the freq of the signal at any time would be very random indeed. Even if it is as created using known scientific functions, chaos theory predict that we wont be able to regenerate the same any time soon.
For that matter, they could even use any of the natural p
Re:Hmm (Score:2)
Re:Hmm (Score:2)
Not sure how well it would work if both parties were on opposite sides of the world though...
Re:Hmm (Score:3, Informative)
Umeno believes astronomical cryptography could appeal to anyone who requires high-security communications. He adds that the method does not require a large radio antenna or that the communicating parties be located in the same hemisphere, as radio signals can be broadcast over the internet at high speed.
Basically, he just wants to use the quasars as a source of true randomness, instead of
Re:Hmm (Score:1)
Their signals can be sent across the internet in the same way.
There are no lack of random signals available at all points in life, however communicating that randomness is the problem.
I've always thought a brilliant random key would be taking a snapshot of a range of websites at a preselected time, that way 2 individuals anywhere could have their keys.
For instance, use the article headers from slashdot.org and bbc.co.uk at 11pm G
so... (Score:3, Interesting)
So if someone has a list of all quasars and their radio frequencies, can't they brute force the message and break it in, what, 20 seconds?
Re:so... (Score:2, Informative)
Re:so... (Score:1, Informative)
Re:so... (Score:1, Redundant)
Yeah, lets get our onetime pad data from a source that anyone can record! I mean...jesus christ.
can't btute force - intractable amount of data (Score:5, Informative)
Many perfectly good one time pads are drawn off of data "that anyone can record." For example, many pads are created from atmospheric noise. Anyone can record the same data, but unless you know exactly where and when the recording was done, it is computationally infeasible to record all possibilities, let alone brute force them.
There are many, many quasars that we record in the sky. All of them give off constant streams of random data. So it would be computationally intractable to record all possibilities or brute force a particulr message, because the attacker would have to know exactly which quasar was recorded, and exactly which instant the recording began. He would also have to know exactly which bit of the pad the sender was on when the sender started sending the message that he intercepted. All theoretically possible, but computationally intractable.
Re:can't btute force - intractable amount of data (Score:3, Insightful)
Record the signal of each of them at time T, also record the encrypted message at time T, and try them all out in a fast computer. Then you'll know which one you need to use for the rest of the encypted s
Re:can't btute force - intractable amount of data (Score:5, Informative)
Well, you have a big problem with your time T. How do you know it? If you do not know the source (which quasar is used), it is also unlikely that you know the exact time T used for the start of the random stream. It is unlikely that you know it with a better precision than a few seconds. If the two parties do not exchange messages frequently or do not re-negociate the start of the random stream frequently, then you may not even know T with a precision of a day.
The NewScientistTech article does not give details about the amount of data available from the quasars, but other articles mention that quasars are typically observed in relatively high frequencies (20-40 GHz). Even if the signal strength is sampled with a low resolution and only a few truly random bits are extracted from the stream, you would still have a stream of bits that is in the Gbps range. This is a reasonably large amount of random data.
So even if the number of usable quasars is rather low (say, a few thousands: 2^10 instead of 2^32 as you mentioned), you would need a lot of antennas and petabytes of storage to record all these random streams. You would have to store something in the order of 2^40 bits per second for several seconds or even days (the uncertainty on T). This is not impossible if you have a large budget, but this is difficult and expensive.
It could even be much worse than 2^40: a recent catalogue of quasars from March 2006 [obs-hp.fr] mentions 85221 of them, with new findings doubling this number every second year: 48921 in 2003 [obs-hp.fr], 23760 in 2001 [obs-hp.fr], etc. Let's say that 2^15 of them are usable (and that you have 2^15 antennas at your disposal). If the signal strength is sampled with a medium resolution of 8 bits at a frequency of 30GHz and your uncertainty interval on T is about one hour, you would need to store 2^15 * 2^3 * 2^35 * 2^12 = 2^65 bits of data before starting your brute force attack. Good luck!
Once you have all this data, you still have to do the brute force attack. You wrote "just try each of the available quasar signals." This is correct but you ignore the fact that the random stream is unlikely to be used as is. It will probably be used to seed a stream cypher. In the simplest case, the random stream would be hashed a couple of times before being xor'ed with the data. You will need a huge amount of computing power to perform all these operations and try each of the available signals at each possible time offset.
Note: it is unlikely that both parties can get the signal and be synchronized with a nanosecond or picosecond resolution. So they would probably negociate a time window (say, with a resolution of one second or so) and some kind of unique marker within that time window in order to know exactly when to start. If you are the attacker and you cannot know which source is used, you probably do not know the time window nor the marker. But even in the unlikely case that you would have a way to obtain one or both of these, you would still have the problem of storing the huge amount of data from all quasars until you know which part of it should be analyzed.
So although a brute force attack based on recording all qasars is not impossible, it is not really easy. And anyway, my first reaction when I started reading this story was exactly like the comment mad
Re:can't btute force - intractable amount of data (Score:1)
240,000,000,000 bps * 3600 = 864,000,000,000,000 bits of data
That is over 2^49 possible starting points for one antenna, given an hour of uncertainty
With 2^15 antennas you now have 2^64 possible starting points.
This still doesn't take into account that if 2 people are sampling the same random data at the same frequency they need to pick the data at exactly the same time. One person's 30 Ghz sample could be offset from another person's 30 G
Re:can't btute force - intractable amount of data (Score:2)
Wow. Thanks for the explanation.
That there is a damned brilliant idea. I wonder if there are any easier to observe atronomical sources that would be just as good? Neutron stars, perhaps? (strip out the pulses and use the noise and pulse variations?)
SB
Re:can't btute force - intractable amount of data (Score:2)
Perhaps radio-loud neutron star / binary systems? That fulfills the easy to observe requirement and the signal synch, I think.
SB
so how is this better... (Score:2, Insightful)
It is just as random and does not require a radiotelescope the size of a small house...
If I wanted gigabytes of random noise... (Score:2)
Radioactivity is about as random as you'll get in this universe, and it sure beats setting up a huge dish on the roof of the NSA building and pointing it at some quasar...
Re:If I wanted gigabytes of random noise... (Score:1)
Re:so how is this better... (Score:3, Informative)
There are two problems:
Re:so how is this better... (Score:1)
The only point is that the attacker need a telescope...
Re:so... (Score:2)
No, not good for "onetime pads". Since BOTH parties have to get the exact same signal, it can not include random noise. If it does not include random noise, then anyone can record the quasars and see what fits.
Even then, I'm sure using simple geometry and an ultra-precise laster rangefinder anyone could figure out where the dish is pointed.
Re:so... (Score:5, Informative)
Obviously, if one side of the cipher was intercepted, then the communication would be suspect - but for most communication, it was the most secure available to them. I don't see this quasar issue as being much different than that.
Now, if they were using quantum states to dynamically generate the ciphers in two seperate places at the same time, THAT would be something to behold.
Re:so... (Score:2)
Which dish? It'd be easy to set up an array of dishes, each following a different quasar. Second, exactly when does the recording start? Third, unless you intercept every single communication, you're not going to be in sync with the incription.
Re:so... (Score:2)
Quasars are currently believed to be massive black holes at the center of young galaxies which accelerate the incoming matter swirling to its doom up to relativistic speeds. The result is a broadband and powerful noise source.
Pulsars for position-finding (Score:2)
The other [Microcosm proposal] that appeared even more interesting to me was the idea (which I'll dub X-ray Pulsar Positioning System [smad.com] or XPPS for short) of using naturally occuring signals from X-ray Pulsars to provide positioning and attitude data anywhere in the solar system, not just inside the orbit of existing GPS satellites
Re:Pulsars for position-finding (Score:2)
The similarity is that they're both unexpected applications for astrophysical phenomena.
That is that the bit stream received from GPS is completely predictable and the sequence recovered from these celestial sources is supposed to be completely unpredictable. The information gained from a GPS signal is not so much the message itself as it is the time when the message was received.
'sides, the
Doh! (Score:2)
Don't blame me.
uh (Score:4, Insightful)
For those that don't know, the idea behind a one time pad is that your key is random, and the same size as the data being sent. For example, if binary data is sent, simple xor encryption can be used as follows
unencrypted data: 10110000
pad data : 10111001
xor the pad against the key and you get
encrypted data : 00001001
xor the same pad against the *encrypted* key again to get
original data : 10110001
tada
One time pads have two major problems
1. Both parties need the key.
2. The key is large, thus cumbersome to carry around and likely to be discovered.
Problem 2 can be solved, while losing some randomness, by using a popular book as the pad. Then you could just head down to the library and check out catcher in the rye, or whatever book you agreed upon beforehand, and begin decoding.
I suppose that this could be used in conjunction with public key cryptography, so that public key cryptography is used to encrypt the coordinates of the quasar you want to use... but I really don't see why you need the quasar at all. Also, aren't there only 12,000 of them visible? If this technology became widespread and quasars were persistently used as sources of random data... someone with enough resources could just monitor them all and decrypt any data transmitted by checking it against all the data received from pulsars at that time.
One time pads (Score:5, Informative)
One underappreciated assumption about one-time-pads is that the recipient will (and can!) destroy the keying material after use so thoroughly that the adversary can't reconstruct it. There are several other issues, of which key distribution is one of the easiest. Just put a 500GB external drive in the diplomatic bag once and you've covered communications for a long time.
Here's the problem. The only things secret here are which quasar (13, 14 bits of uncertainty), when the sampling started (?? There won't be very many possible seconds that the adversary has to scan but sampling could start on a fraction of a second), and the sampling algorithm (but you have to assume in crypto that the adversary knows your algorithms). It's going to be easier to brute-force than a 6-word Diceware [diceware.com] passphrase unless atmospheric effects somehow make the quasar signal look different everywhere on earth.
Re:One time pads (Score:3, Funny)
Anyway, once i've figured out all the parameters, all I need to do is send a box away from the origin of the quasar faster than the speed of light, so that it can effectively go back in time relative to the signal and capture it.
I believe that thi
Re:uh (Score:2)
which to my knowledge is unbreakable, although I am not particularly well versed in cryptography
That's right, it is unbreakable - provided you never use the same key twice. And here's why:
Any message is a series of bits which can be represented as a number. Any key of the same length is a series of bits that can be represented as a number. Therefore, we can define the following function that operates on the entire message at once:
CipherText = PlainText XOR Key
The first thing to notice about th
Re:uh (Score:2)
Believe it or not, there are still quite a few espionage-related radio transmissions - numbers stations [wikipedia.org] - in use today, particularly by Israel (Mossad), the UK (MI6), Cuba, and others. The transmissions consist of lists of numbers being read aloud (the process is usually automated today rather than read by an actual person), and it is assumed that the lists are messages encoded through the use of one-time pads. While the stations still exist and still tra
Re:uh (Score:2, Funny)
>pad data : 10111001
>
>xor the pad against the key and you get
>
>encrypted data : 00001001
>
>xor the same pad against the *encrypted* key again to get
>
>original data : 10110001
The final step is to subtract 00000001 from the decrypted data...
Re:uh (Score:2)
Lava Lamps (Score:3, Interesting)
Overlords (Score:1)
Quantum entanglement? (Score:3, Interesting)
All you have to do is ensure that both commnuicating parties sample ENOUGH of the particles arriving at earth, and presumably enough of them will be entangled such that any other observer would have a statistically observable effect on their communication, i.e. detectable as an interceptor.
OK, that's sounds hopeless.
How about if there was one day found to be a way of communicating via entanglement? Then perhaps quasars might well be great sources of entangled particles.
Remember, science is not advanced by claims of "Impossible!", but by "I wonder if..."
proof of alien life? (Score:1)
But what if they didn't left them, they could decrypt everything we send. Since they hold the master scramble key.
ohno I smell an evil alien ufo story here..
Wow! (Score:2)
Attacks on quasar encryption (Score:2)
If this were done (using quasar emissions as a random number source for encryption), what would prevent a third party from surreptitiously generating pseudonoise locally that would mask the quasar emissions? I.e.:
Assume a spy Alice and her controller Bob are both based in the city Xerces, and are using quasar emission encryption [QEE] (I'm copyrighting that acronym-- you have a non-exlcusive license to use it in any way you want). If Xercians broadcast an apparently random stream that drowned out the quas
Main key not the stream, but the star? (Score:1)
Isn't a problem with one time pads transmitting the large keys without raising suspicion? A smaller key can be embedded / transmitted without being detected (I realize this is security through obscurity which the purists will tear apart - but I'm sure its used more often then we realize). The smaller key could simply be the quasar and time to start recording the one time pad. Then both parties each have the key that is ultimately used to encrypt the message.
Isn't this a little bi
Radio Signals from Space (Score:1)