14
$\begingroup$

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?

$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$
    – Aaron F
    Aug 31 at 8:28
  • $\begingroup$ @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. $\endgroup$
    – Joshua
    Sep 1 at 20:07
  • 1
    $\begingroup$ @AaronF Also, don't forget clouds. $\endgroup$ Sep 2 at 20:50
  • $\begingroup$ 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: beacon.nist.gov/home $\endgroup$
    – LeoDucas
    Sep 4 at 6:33
  • $\begingroup$ Isn't this an astronomical analogy to the 'wall of lava lamps' (nerdist.com/article/wall-of-lava-lamps-protect-internet-traffic) bitstream? $\endgroup$
    – warren
    Sep 22 at 14:24
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Aug 31 at 21:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – AnoE
    Sep 1 at 6:57
14
$\begingroup$

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 :)

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 1 at 17:28
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 1 at 21:18
  • 2
    $\begingroup$ 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 $\endgroup$ Sep 1 at 21:20
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 1 at 21:49
  • 2
    $\begingroup$ Did you have a look at the references? The first one is especially relevant $\endgroup$ Sep 1 at 21:57
10
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 30 at 22:20
  • 1
    $\begingroup$ 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). $\endgroup$
    – fgrieu
    Aug 31 at 7:33
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 31 at 7:37
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 31 at 9:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Aug 31 at 14:41
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hi and welcome. $\endgroup$
    – Paul Uszak
    Sep 27 at 2:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.