How hard is it to interpret binary data of a new and unknown format, if it's unknown what data is encoded?

Question

This question is based off of my answer to a world building question: https://worldbuilding.stackexchange.com/questions/30471/how-could-a-blind-alien-race-interpret-video-broadcast-into-space/30497?noredirect=1#comment80601_30497 In which I argued that aliens wouldn't be able to interpret out data because they couldn't reliably reverse engineer captured signals. I'm not asking anyone to answer that question in it's entirety, but I do want to check my basic assumption in one area; and besides I'm now curious as a programmer who keeps trying to come up with ways to solve the challenge lol.

Assuming that you were handed a huge collection of binary data in a completely foreign format, with no other knowledge about it other then the fact that it was not encrypted or intentionally obfuscated, and you don't know what is encoded (video, picture, executable program etc), how feasible is it to reverse engineer it to figure out the how to interpret the data? That is to say how hard is it to both 'crack' the encoding algorithm, and how hard is it to correctly identify what type of data was originally encoded to begin with?

Closely related, how likely is it to get a 'false positive' by coming up with an interpretation that looks valid but is not how the data was actually encoded? Or even come up with an entirely different type of encoded data (thinking an audio encoding was video etc)

Answer 1

Let's say this was the entirety of your random message:

01000001

Anyone familiar with ASCII would be able to tell you that is the binary representation of the letter 'A'. However, in your scenario there is no context to suggest that this is ASCII so it is just as likely to be an 8-bit representation of the following flags for a hamburger order:

• 0 = No cheese
• 1 = Add pickles
• 0 = No ketchup
• 0 = No mustard
• 0 = No onion
• 0 = No tomato
• 0 = No lettuce
• 1 = Double patty

And if the above is also not the case, maybe it is actually two separate 4-bit fields used in a multi-part messaging scheme. Or a 5-bit and a 3-bit right after?

Given the complexity of determining for certain what just a single byte means (assuming the message under examination actually knows what the concept of a byte is) imagine how difficult it would be to do this for a message of several kilobytes or larger.

You had also mentioned, however, that we would be given a large sample of data to work with. This would provide an analyst with more context, such as:

• Possible patterns in the bits
  • Certain bits that are always 0 or always 1
  • Repeating chunks of the same 20 bits
• Similarity to other well-known formats
  • The message may use frames
  • There may be identifiable headers and footers within the messages

Context is important, though in regards to false positives even with context you can come up with the wrong answer. In crypto terms, given a random ciphertext you can literally come up with any plaintext if you apply the right key. Similarly, going back to the top of my answer, the 8-bit message I posted could be interpreted in many ways, any of which could be valid in a given application.

Answer 2

Encodings of transmissions such as TV, radio, microwave data transmissions, occur at a number of different layers. Essentially there is a protocol stack.

Someone looking at a transmission can infer information in a lot of ways. The mere existence of a signal with enough pattern to suggest intelligent life communicates a lot - a lot more than just "there's other intelligent life". The volume of transmissions alone would say a lot, especially if observed across decades. The timing of transmissions would suggest things like: night and day correspond to different levels and kinds of activities.

Starting at the bottom of the transmission's "stack", a few suppositions could be made: light seems to be the only reasonable transmission medium at distances where "alien" makes sense. Up until 20 or so years ago, a good percentage of the transmissions from earth were analog.

At the lowest "protocol" level our methods for analog encoding info onto light were pretty simple: vary amplitude, vary frequency, vary phase. So it seems like most "aliens" capable of receiving electromagnetic (light) transmissions would be able to detect the fact that our transmissions varied one or two of these very basic properties. And with that they begin the decoding process. If they received an AM radio transmission, it would be easy to recover the original waves of what we call sound. Assuming the aliens had some sense that responded to our "sound" waves (or alternatively responded directly to the raw AM waves), they could "hear" the message pretty much the same way the radio station created it.

They would then have the problem of interpreting our language, but it's not much of a stretch (though it might take a long time) to imagine that happening, given what linguists on Earth are capable of.

Once they've decoded AM radio and some of our natural languages, then decoding something else, maybe FM radio, becomes much easier. From there, maybe not too hard to decode the audio portion of TV signals.

Decoding video would be greatly aided if the aliens had a sense(s) similar to (or the same as) sight and had similar persistence of vision. Someone analyzing a video transmission at the lowest level could piece together several layers of repetition: the scan lines repeat something like 15000 times a second and the frames repeat about 30 times a second and the frames might be interlaced. One could see that each scan line is usually pretty similar to the one before it. A map could be drawn that shows how each scan line morphs into the line that follows it. After drawing a few hundred of those a frame would appear. Also the vertical blanking interval would be a clue that would signal the end of one frame and the beginning of the next. Each frame would generally look similar to the previous one, but usually some changes. This would suggest a series of pictures of something that changes over time. In other words video. The accompanying audio could be easily correlated with the movement of mouths, things impacting each other, and so on.

With the decoding of analog TV, it then becomes possible to associate spoken language with written language, from both sub titles and TV ads. And a whole lot of cultural info could be gleaned by watching TV and listening to radio. It would become clear what kind of things we cared about in these transmissions.

So when it came to decoding digital transmissions a whole lot of groundwork would already have done. For example, seeing TV broadcasts with a lot of information about the stock market would go a long way towards decoding contemporaneous digital transmissions about the stock market.