Score:14

Crypto

Could celestial objects be used in cryptography?

user1551817

12/30/22, 6:13 PM

If it were possible to receive a string of numbers from a celestial object (by anyone on the Earth who knows which object to look at, and what time to look) could this be of any use in cryptography?

Or would it be useless, because if a bad-actor knew which object you were looking at and at what time, they could find the key?

6230

5 + 4

encryption

Aaron F

12/31/22, 8:28 AM

One practical issue is that not all objects are visible by all people on Earth. Some depend on latitude and others depend on time of day.

6

Reply

Joshua

1/1/23, 8:07 PM

@AaronF: If you set your system up right you can cause it to pick up also the atmospheric brownian motion and mix that into the bitstream.

0

Reply

Paŭlo Ebermann

1/2/23, 8:50 PM

@AaronF Also, don't forget clouds.

1

Reply

LeoDucas

1/4/23, 6:33 AM

I think the notion you are looking for is "a randomness beacon". One difficulty if it comes from an analogue source is the fact that it is an analog signal, that needs to be "rounded" (or more technically "quantized") to a discrete one, but with noise it is not easy to make sure everyone round to the same value. Hence the man-made NIST randomness beacon: https://beacon.nist.gov/home

0

Reply

warren

1/22/23, 2:24 PM

Isn't this an astronomical analogy to the 'wall of lava lamps' (https://nerdist.com/article/wall-of-lava-lamps-protect-internet-traffic) bitstream?

0

Reply

Score:14

Crypto

Marc Ilunga

12/30/22, 7:53 PM

I believe a potential application can be found in the so-called "bounded storage model" introduced by Maurer here:

https://crypto.ethz.ch/publications/Maurer92b.html

In summary, the bounded storage model is a theoretical research direction that studies cryptographic constructions where one assumes that only the adversary's storage is limited. This is in contrast with current (practical and safe to use) cryptographic schemes where we assume that the computational resources of the attacker are limited, e.g., Hardness of factoring for RSA or discrete logarithm for (Elliptic-Curve)Diffie-Hellman problem.

Interestingly, it can be shown that Information-theoretically secure cryptographic schemes exist if the bounded storage assumption is correct.

So, in this case, a celestial object could be seen as a public satellite that emits random bits; it is conceivable that the attacker doesn't have enough storage to store all of this data, whereas the users only need to store a fraction of all the bits and will achieve a secure key for example.

This more recent paper shows a few interesting constructions based on the bounded-storage model: https://eprint.iacr.org/2019/507.pdf.

Note: So far, this line of research is still a theoretical curiosity; perhaps it will become practical one day. However, "computational" cryptosystems we have today, including the post-quantum ones, are just fine :)

0 + 7

Chthonic One

1/1/23, 5:28 PM

I'm not an expert, but I believe that such a cryptographic method would be vulnerable to timing problems as both members would need to know when to start looking at the celestial body to receive the key, and man-in-the-middle attacks, if someone were to hear about the plan, the celestial body, and the timing, they could also get the key as well and thus be able to decode the transmissions. You'd need a secure way to transmit this data between the two parties, which is a problem in itself.

1

Reply

Marc Ilunga

1/1/23, 9:18 PM

Hi. Regarding security, please note that this is not a security by obscurity situation. In fact it is assumed that the attacker receives the same data as the end users. So in this case, it is allowed that the attacker knows the time when this operation will take place and also that they can read the data for the celestial object.

1

Reply

Marc Ilunga

1/1/23, 9:20 PM

Even more fascinating(to me at least, previous work showed that it was possible to construct this type of schemes even when end user have a noisy channel to the satellite and that the attacker has a better channel

2

Reply

Chthonic One

1/1/23, 9:49 PM

All I know is that when dealing with one time pads and similar measures in the military, these were considered secure so long as all parties involved kept the pad secret, and it was never intercepted. This is the same concept in my head, I can't see how it'd be much different. Am I mistaken and this is this not a method for increased security? If so what is it's purpose in cryptography? Perhaps that should be explained as well in the answer too.

1

Reply

Marc Ilunga

1/1/23, 9:57 PM

Did you have a look at the references? The first one is especially relevant

2

Reply

Chthonic One

1/1/23, 10:18 PM

Yes, but that just leaves me wondering how can this even possibly be used as a tool for communication in the first place? The secret key is used to decode the message, and if the attacker has the secret key and the message, and he cannot decode it, how can the intended recipient decode it? Without the full paper, I'm afraid I don't understand what they are getting at really. It seems very crazy.

1

Reply

Marc Ilunga

1/1/23, 10:22 PM

Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/129182/discussion-between-marc-ilunga-and-chthonic-one).

1

Reply

Score:10

Crypto

Geoffroy Couteau

12/30/22, 9:52 PM

A standard candidate that I mentioned recently here is to setup a common reference string, assuming (1) the string received from the celestial object contains randomness, and (2) the observation of this string can be reliably made by distant parties. This gives an untamperable common random string, a very useful object for cryptographic protocols (in contrast, setting such a common reference string on earth requires either a large scale distributed protocol, or a trusted setup assumption).

0 + 10

user1551817

12/30/22, 10:16 PM

Thank you. So if we assumed that the sunspot technique (that you mentioned in the other post) was perfect, then two parties at different parts of the Earth would be able to receive the same random number. I'm new to cryptography, but would they not have to communicate with each other to say WHEN they would observe the sunspots? And if so, doesn't them having to pass a message to each other defeat the purpose of having this celestial random number always available to both parties?

0

Reply

Geoffroy Couteau

12/30/22, 10:20 PM

The information about when to observe can be part of the specification of the protocol (e.g. "at 1pm GMT"). Also, in many scenario being allowed to communicate does not at all trivialize anything, and in particular does not replace having to find a *trusted* way to jointly generate this random string. In any use of the CRS, the parties will have to communicate afterwards anyway; the first party to send a message can just clarify what day the protocol starts.

1

Reply

fgrieu

12/31/22, 7:33 AM

I have no doubt about (1), but I need to be convinced (2) is possible for the kind of signal we can get from celestial objects, with an acceptable error rate (say 0.001) for sizable (say 200-bit) entropy gathered thru (1). In fact I don't know any naturally-occurring phenomena where this is done (for some practical meaning of error rate needing to be defined carefully; in particular reference time-frame of participants might come into play).

1

Reply

Geoffroy Couteau

12/31/22, 7:37 AM

Yes, this is a bit idealistic (note that the other answer suffers from the same issue). But in several scenarios, it turns out that a common random string can be actually replaced by "sufficiently correlated random strings" (see the pointer in the answer I point to), in which case the issue goes away.

2

Reply

user1551817

12/31/22, 8:16 AM

Thank you. In his nice answer here, Marc Ilunga at one point mentions "a public satellite that emits random bits". I hadn't really thought about that, but wouldn't that do the job instead of having to find a reliable celestial object?

0

Reply

Geoffroy Couteau

12/31/22, 9:09 AM

Yes, but then you need a trust assumption again: someone constructed the satellite, this someone might have kept a trapdoor to anticipate the random string or bias it.

1

Reply

Maarten Bodewes

12/31/22, 2:41 PM

One problem is that we assume that these kind of phenomena are largely random now. But is that because we as a general species do not understand them yet, or are they inherently random? What keeps me from choosing a phenomena for which I have more information than others? There is a difference between the human understanding of what "random" means and a good entropy source.

2

Reply

user1551817

1/1/23, 8:40 AM

I understand that a public satellite could potentially have a trapdoor to anticipate / bias the random string, but I suppose that the same could be true of your receiver that is used to to collect data from the astronomical object, no?

0

Reply

user1551817

1/1/23, 8:44 AM

Could you use random stock market fluctuations instead of monitoring the celestial object? If so, that would obviously be cheaper and easier. I suppose that this could be open to manipulation, but if you took the average price of hundreds of stocks then it's very difficult for someone to make this a value that they want.

1

Reply

Geoffroy Couteau

1/1/23, 9:00 AM

Question (1): if a single receiver is trusted to collect the "celestial random string", then sure. Avoiding trust requires that you "do the work yourself". Question (2) on stock market fluctuations: it is also a natural and well known alternative, yes. It should indeed be near infeasible to bias low order bits of the values of the stock market at opening time.

0

Reply

Score:6

Crypto

Radovan Garabík

12/31/22, 8:16 AM

Absolutely. Rather successful TOTP algorithm as implemented depends on current time being common for the two parties. Going to the foundations, calendar and time reckoning is ultimately based on astronomy observations.

Granted, currently we mostly keep the time by following some number of independent time sources; but rather ironically, if we (as end users) need to synchronize our computing equipment clocks, we do it increasingly more often than not by receiving a string of numbers from a man-made celestial object.

0 + 0

Score:3

Crypto

Paul Uszak

12/31/22, 12:39 PM

I would suggest that the best fitting use case is to use the signal for your own cryptographic keys, and not as part of a commonly verifiable reference.

Stars twinkle due to various optical effects including pollution. General radio sources produce entropic noise into the 100's GHz. When sampled, you'll get lots of quantization noise and other measurement errors riding the fluctuating signal. That's exactly what one budding cryptographer can use to generate private keys (after a little randomness extraction).

It's also what prevents bad actors from generating the same keys, even if they're stood next to you (but with their own equipment). Measurement errors will always mean the two of you will digitise different signals. 256 different bits are easily obtained from 12 bit samples at 10,000 samples/s (schoolboy Arduino type kit).

Where it's not indicated is for distributed randomness. You'd need lots of clever de-noising, Fourier transforms, fuzzy extraction, an agreed consensus protocol and hardware. So the operators of the consensus scheme will be requiring the users to trust them, defeating the objective.

0 + 0

Score:2

Crypto

AnoE

12/31/22, 2:57 PM

Any cryptographic protocol must have:

Some (public) algorithm which explains what to do. (Depending on secret algorithms would be called "security by obscurity" and can usually be discarded as inherently insecure.)
Some secret information (i.e., one or several keys).

To be of any practical use, the key space needs to be large enough to make brute force attacks (especially when knowing the complete algorithm) infeasible.

It is important to keep in mind that when thinking about a cryptosystem like this, the problem of "losing the secret" is out of scope. I.e., the secret is supposed to be really secret, you can and must assume that the attacker does not know the secret before starting his attack.

The arguably most secure and at the same time trivial algorithm would be the usage of a one-time-pad; i.e. the secret is a (possibly very large) integer; and the algorithm simply is to XOR the secret and the plaintext for encryption, and to XOR the secret and the ciphertext for decryption.

This could be used thusly with celestial objects:

The key is the ID of a star.
The algorithm:
- There is a constant-bandwith stream of ciphertext being transmitted all the time, in fixed-size blocks. Assume that this transfer works reasonably well, i.e. no significant pauses, and roughly known latency.
- Both the sender and receiver constantly monitor the star and draw random bits from it in some form or fashion. I do not know if there are any practical measurements that actually work today, but one could imagine that the brightness of certain stars "flickers" enough to draw something from it.
- The sender keeps XORing their next plaintext block, checksummed and padded to the required length, with the current batch of realtime random bits (i.e., one-time-pad) and sends it.
- The receiver decodes this using the same XOR operation. To be a bit more safe against timing issues, it can keep the last N one-time-pads around and just try to decode with all of them; with the checksum and considering how fast the XOR is, it is feasible to have a sliding window of pads to find the correct one.

The strength of the algorithm depends on whether there are enough possible stars to pick from, and that the measurement is hard enough so that it is infeasible for an attacker to scan very many stars at a time.

There you have a basic idea of how you could use celestial objects in cryptography. At the end of the day it boils down to generating truly random bits, and you don't even need the time if you are able to have a constant connection. You can refine this as necessary; i.e. you could avoid having to constantly send ciphertext if you have some kind of shared time source (and it only needs to be roughly in sync, depending on how much buffer space you will want to use for your bits). There are plenty of practical problems to solve (e.g. how to generate the bits reproducible in the first place, avoiding phase shifting due to minute divergences and thus), but not unsolvable in principle.

0 + 2

user1551817

12/31/22, 9:15 PM

Thank you - that's really useful; I'm a beginner so still trying to get my head around some of these concepts. If this celestial system *was* possible, was created and shown to work, would there be much interest in it, or would it just be one of many systems that can do equivalent things and so only of academic interest?

0

Reply

AnoE

1/1/23, 6:57 AM

@user1551817, mainly academic interest, I believe. Our current public-key algorithms work well enough for the foreseeable future, unless you are ultra paranoid and are fearing sudden huge leaps of progress for quantum computing or something along that line.

1

Reply

Score:2

Crypto

TasAstroSpacial

1/26/23, 11:47 PM

I come at this from the astronomers point of view who has worked in X-ray astronomy which is closely related to the study of cosmic rays. Cosmic rays (high energy particles from space) are one source of random events. A google search will show many articles. I believe using a geiger counter as a random seed generator was implemented many years (1970's 80's) by a large computer company. My memory says Burroughs. However I can't find a reference.

0 + 0

Paul Uszak

1/27/23, 2:45 AM

Hi and welcome.

0

Reply

Score:1

Crypto

Thomas Anderson

1/23/23, 3:45 PM

There is a nice paper at https://ro.ecu.edu.au/cgi/viewcontent.cgi?article=1190&context=ism that describes the applicability of celestial background radiation as a source of randomness. This seems like a much more practical use case, rather than trying to leverage the source at the higher level of incorporating it into any specific cryptographic algorithms.