Quasars Used for Encryption

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"

Comments

Re:so...

[B3ryllium]

The KGB used CBR (Cosmic Background Radiation) to produce reams and reams of codebooks/ciphers. They would create two copies, and dispatch one of the copies to the remote location for encryption, then keep one copy at Lubyanka Square.

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.

can't btute force - intractable amount of data

[lordcorusa]

All one time pads are recorded from random data. You record a long stream of truly random input, then make two copies of the recording. Tne sender gets one copy, the receiver gets the other. Starting at the beginning of the pad, the sender uses each bit of the pad exactly once, then discards it. When the sender runs out of bits, he can not send any more data. The receiver decrypts decrypts likewise, discarding each pad bit after it has been used once. As long as the sender and receiver start with the same pads and don't skip or reuse any bits, they stay in syncronization.

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

[Raphael]

The length of the "one time pad" is large, but the number of them available? I mean the number of quasars that are good enough receivable to use for this purpose. I have no idea, but I doubt if its more than 2^32. In that case, brute force would be quite easy: just try each of the available quasar signals.:
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.[...]

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 mentions 85221 of them, with new findings doubling this number every second year: 48921 in 2003, 23760 in 2001, 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

uh

[sentientbrendan]

There doesn't seem to be anything special about a quasar here... essentially all they are saying is that large amounts of random data can be used for quick and easy one time pad encryption, which to my knowledge is unbreakable, although I am not particularly well versed in cryptography...

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

[Beryllium Sphere(tm)]

They are indeed unbreakable, with a theoretical proof of unbreakability -- in the land of spherical horses, where you're allowed to make huge assumptions.

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 passphrase unless atmospheric effects somehow make the quasar signal look different everywhere on earth.