Subverting Backdoored Encryption

This is a really interesting research result. This paper proves that two parties can create a secure communications channel using a communications system with a backdoor. It’s a theoretical result, so it doesn’t talk about how easy that channel is to create. And the assumptions on the adversary are pretty reasonable: that each party can create his own randomness, and that the government isn’t literally eavesdropping on every single part of the network at all times.

This result reminds me a lot of the work about subliminal channels from the 1980s and 1990s, and the notions of how to build an anonymous communications system on top of an identified system. Basically, it’s always possible to overlay a system around and outside any closed system.

“How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts,” by Thibaut Horel and Sunoo Park and Silas Richelson and Vinod Vaikuntanathan.

Abstract: In this work, we examine the feasibility of secure and undetectable point-to-point communication in a world where governments can read all the encrypted communications of their citizens. We consider a world where the only permitted method of communication is via a government-mandated encryption scheme, instantiated with government-mandated keys. Parties cannot simply encrypt ciphertexts of some other encryption scheme, because citizens caught trying to communicate outside the government’s knowledge (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested. The one guarantee we suppose is that the government mandates an encryption scheme which is semantically secure against outsiders: a perhaps reasonable supposition when a government might consider it advantageous to secure its people’s communication against foreign entities. But then, what good is semantic security against an adversary that holds all the keys and has the power to decrypt?

We show that even in the pessimistic scenario described, citizens can communicate securely and undetectably. In our terminology, this translates to a positive statement: all semantically secure encryption schemes support subliminal communication. Informally, this means that there is a two-party protocol between Alice and Bob where the parties exchange ciphertexts of what appears to be a normal conversation even to someone who knows the secret keys and thus can read the corresponding plaintexts. And yet, at the end of the protocol, Alice will have transmitted her secret message to Bob. Our security definition requires that the adversary not be able to tell whether Alice and Bob are just having a normal conversation using the mandated encryption scheme, or they are using the mandated encryption scheme for subliminal communication.

Our topics may be thought to fall broadly within the realm of steganography: the science of hiding secret communication within innocent-looking messages, or cover objects. However, we deal with the non-standard setting of an adversarially chosen distribution of cover objects (i.e., a stronger-than-usual adversary), and we take advantage of the fact that our cover objects are ciphertexts of a semantically secure encryption scheme to bypass impossibility results which we show for broader classes of steganographic schemes. We give several constructions of subliminal communication schemes under the assumption that key exchange protocols with pseudorandom messages exist (such as Diffie-Hellman, which in fact has truly random messages). Each construction leverages the assumed semantic security of the adversarially chosen encryption scheme, in order to achieve subliminal communication.

Tags: , , ,

Posted on April 4, 2018 at 8:03 AM • 77 Comments

Comments

Winter • April 4, 2018 9:21 AM

We already knew this, more or less. The Chinese are using a similar scheme to subvert censorship on social media. Look for “Grass-Mud Horse”:

https://www.theatlantic.com/technology/archive/2012/03/slang-chinese-bloggers-use-subvert-censorship/330567/

Also, there is ubiquitous use of Homophonic Codewords:

https://medium.com/berkman-klein-center/the-chinese-language-as-a-weapon-how-chinas-netizens-fight-censorship-8389516ed1a6

It is nice to see a proof that there will always be such a way around censorship.

RonK • April 4, 2018 10:12 AM

The research, while interesting, appears to assume a rather peculiar adversary — one who is actively controlling the allowed encryption algorithm and actively decrypting all communication, but who is unwilling to MITM all communications. AFAICS, none of the findings are useful against a re-encrypting adversary, since they use the encrypted messages themselves as opposed to only their contents.

justinacolmena • April 4, 2018 10:40 AM

This paper proves that two parties can create a secure communications channel using a communications system with a backdoor.

That’s Eve listening in to Alice’s secret message to Bob.

There is no mathematical proof to any cryptographic system other than a one-time pad — and even those are highly vulnerable to inadvertent re-use.

We do not even have proof that P ≠ NP, or that easy-to-verify but difficult-to-compute functions exist at all under any circumstances. We do not know that it is difficult to compute the key of a block cipher such as AES given only the plaintext and ciphertext.

These are all assumptions, and they are not sufficiently self-evident to call them axioms, or to call what we base on them “proof.”

Humdee • April 4, 2018 11:49 AM

Of course this is both possible and practicable. It follows not from the nature of encryption but from the nature of language. To a rat, a cow, and a pig English or any human language just is encrypted marks and noises. Encryption isn’t a product of math; it is a product of human social relationships. I had thought Davidson established that back in the 1970s and @Bruce reiterated it back in the 1990s. So i am a little bit puzzled by why @bruce finds this interesting–maybe his mind is so big that he forgotten half of what he knows.

Bauke Jan Douma • April 4, 2018 3:43 PM

@Len Lattanzi
Is the misspelled title a a steganographic clue?

The excess ‘r’ has a subliminal working. It is meant to convey the existential doubt “Two are” or “Not Two Are“.

echo • April 4, 2018 5:03 PM

Given security and socity are key issues today (as expressed by attacking encryption and the derogatory “virtue signalling”) I wonder if work had been done on the use of coded language within organisations and collusion. I’m sure it has I just don’t know enough about the academic fields to know of any books or published papers.

AJWM • April 4, 2018 7:06 PM

Also, there is ubiquitous use of Homophonic Codewords:

I remember a short story in Analog SF magazine back in the late 60s, “Come You Nigh, Kay Shuns”. It’s predated by “Ladle Rat Rotten Hut”, a version of Little Red Riding Hood worth searching for.

I suppose a suitably clever pair of text-to-speech, speech-to-text programs might figure it out, though.

Winter • April 5, 2018 12:47 AM

“I suppose a suitably clever pair of text-to-speech, speech-to-text programs might figure it out, though.”

The key word is “suitable”. Just matching partial homophones gives an exploding search space. The system has to model human associations in memory. That is currently an unsolved problem.

Even with such a system, you enter a veritable arms race. You can envision a situation where language changes faster than the systems can collect data to train on.

Sarah • April 5, 2018 8:45 AM

Well yea, but if you roll your own, you wont have to worry about back doors of any kind.

Me myself • April 5, 2018 9:44 AM

Wow, what a useless research. I can’t believe anyone spent funding into stating something so obvious.

I remember in my teen years talking on the phone with a friend about a subject I didn’t want my parents to know about, I pretty much used the exact same technique. I stated ambiguous phrases that were enough for my friend to derive the intended meaning (although he also had the context of his side of the conversation, which my parents didn’t).

If you’re using this sort of concealment it doesn’t matter if the encryption is backdoored or not. The channel might as well not even be encrypted at all. My parents certainly didn’t have to decrypt my conversation to listen in, yet they were none the wiser.

Strange • April 5, 2018 10:07 AM

Just talk about how many roses you grew in your garden, and the receiver knows you’re actually talking about how many religious converts were made…

This is a real world example that has actually happened, such things are illegal in many places! And such analogies can be made up on the fly without even prearrangement… You might think, “how easy for the man in the middle to decipher, and change” but remember English is a second language for the man in the middle… plus there’s obvious plausible deniability if you really did grow a rose garden under the obvious surveillance…

Thoth • April 5, 2018 10:13 AM

@Clive Robinson

I guess the academics and spooks have been keeping an eye on the conversations and ideas in this forum and most have only got some half-baked product from the ideas we conceptualize and describe here.

The worst thing is when they take our ideas, not saying a thank you to the authors here and simply claiming them as their own and some have tried to commercialize and capitalize on half done implementations.

Meh • April 5, 2018 11:59 AM

Nobody connects this to ubiquitous data collection?
A database of all people you ever spoke to, all you ever read, saw or otherwise experienced has a good chance to aid detecting such subversive communications.

With money and laws against you, this is an arms race we’re actually losing.

. • April 5, 2018 12:15 PM

“The worst thing is when they take our ideas, not saying a thank you to the authors here and simply claiming them as their own and some have tried to commercialize and capitalize on half done implementations.”

Numerous articles in news about gov’t stealing ideas, denying patents then stealing, etc. One article sounded like bragging by FBI – that they stole ideas from others then took credit. Gov’t denies and courts no help.

. • April 5, 2018 1:22 PM

@Specifics

Just look up all the times the gov’t had to defend themselves in court. It’s not their money, what do they care?

NASA had to pay millions to Boeing after it was proven the gov’t infringed on their patent. The gov’t had to pay Hughes over 100 million after it was proven they stole their technology. The Army had to pay millions to a company Apptricity after swiping their software.

These companies also spent millions and years in court fighting the gov’t. What chance does an individual or a small business have? It’s like that episode in Star Trek when the ship is stuck in a force field that reflects all the energy back on them so the harder they try to break out the stronger it gets.

Of course, companies steal too. One very ugly public case involved Kidde. It was so blatant the inventors said they even copied the packaging! Like the Grinch who even took the little star.

See https://www.nytimes.com/2001/08/19/us/ladder-inventors-win-design-case.html

Clive Robinson • April 5, 2018 1:58 PM

@ Humdee,

One group of researchers says “we can build a secure golden key!” And another group goes, “and we can subvert it!” The cat and mouse game never ends.

Logic dictates that a “golden key” is by definition an insecurity, therefore you can not stop the “turtles all the way down” issuse of a golden key having a backdoor or front door or other golden key.

Either something is “secure” or “It is not secure” it’s a binary choice there is no NOBUS mid way as what is now almost an NSA back-doored PRNG demonstrated.

Oh and don’t forget the Benjamin Franklin maxim “Three can keep a secret if two of them are dead”.

Although he might have known it intuitively, it was for later generations to formulate what is now called “MICE”[1] which explains why people will “turn traitor”…

But there is another way that XKCD
fairly succinctly identified, which tends to get around most security systems,

https://www.explainxkcd.com/wiki/index.php/538:_Security

[1] https://en.m.wikipedia.org/wiki/Motives_for_spying

Clive Robinson • April 5, 2018 2:23 PM

@ Bruce,

Try going back to WWII… And I think SALT in the 1970’s as well as I know that you are not old enough to remember WWII 😉

Oh and there was that bloke called Bacon a bit before that I don’t think any of your readers have whiskers long enough to have been around then 0:)

@ ALL,

If you look back in this blog you will discover that I’ve shown repeatedly that it does not matter how much an adversary listens “They will not get the real message” providing two facts are true,

1, You and the second party had access to a secure side channel at some point to exchange the code and method.

2, You can put your and the second parties “security end points” beyond the third party adversaries “Communications end points”.

Those two constraints give you the level of security you wish to use. However if the “method” is insufficient then any “code” can be broken (ie re-use of One Time Pad).

There is also the “Staying off the enemy Radar” issue. If a third party adversary has reason by your or the second parties poor OpSec believe there is some form of code in use, then then the third party has the option to turn one of the first two parties against the other in some way.

Which means you can not use ciphers in the traditional manner, but you can use codes such as One Time Phrases. I’ve explained why this is in the past on this blog so either look them up or ask me nicely to give them again.

-stephen • April 5, 2018 2:24 PM

To AJWM et al., re: Homophonic Codewords, see also “Die Gesammelten Werke des Lord Charles” (“The Collected Works of…”) by John Hulme (Deutscher Taschenbuch Verlag 1984), in which the homophones are between languages. It’s a book of poems consisting of seemingly nonsense English words and phrases which, when spoken aloud, sound like sensible German.

An example which most even non-German speaking readers should recognize:

Ark do lea bear how Gus teen,
How Gus teen, how Gus teen,
Ark do lea bear how Gus teen,
Alice is tin.

Hulme apparently wrote another which I cannot locate, “Mörder Guss Reims – The Gustav Leberwurst Manuscript”, which goes in the other direction, i.e. nonsense German which when spoken, sounds like English.

Clive Robinson • April 5, 2018 2:28 PM

@ Thoth,

I guess the academics and spooks have been keeping an eye on the conversations and ideas in this forum and most have only got some half-baked product from the ideas we conceptualize and describe here.

Yup, not only is it happening a lot in recent times, but it has become embarrassing as to how they have not grasped the finer points…

It’s almost as if we have already given proof of what the paper is trying to say… Kind of gives you a warm fuzzy fealing occasionaly 😉

Clive Robinson • April 5, 2018 2:33 PM

@ Specifics,

How about you stick to a more consistant nick name?

I know it’s something that has been mentioned a few times in the past by our host.

Strange • April 5, 2018 2:44 PM

At least stick to a common nick name within a given conversation… it’s not that hard…

fa • April 5, 2018 3:13 PM

citizens caught trying to communicate outside the government’s knowledge (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested.

A statement like ‘I really do/don’t like the weather today’ can be used to transmit one chosen bit. It’s not difficult to imagine messages that could carry more hidden information.
To prevent this sort of thing, any expression of personal opinion would have to be made ‘illegal’.

Alyer Babtu • April 5, 2018 4:09 PM

Re homophonic code words

Then there is single text perfect in two languages

I vitelli dei romani sono belli

Italian

The calves of the Romans are beautiful

Latin

Go Vitellius to the sound of war of the roman god

(hope I didn’t mangle it !)

(required) • April 5, 2018 4:28 PM

“To prevent this sort of thing, any expression of personal opinion would have to be made ‘illegal’.”

Lighten up Francis.

D-503 • April 5, 2018 5:22 PM

any expression of personal opinion would have to be made ‘illegal’

And what’s your beef with this?

When every citizen is guilty of hundreds of ‘felonies’ per day, it provides governments and corporations a convenient way to bypass constitutional brakes on centralised power.

It’s great for political stability.

It’s great for getting unquestioning obedience from the entire population.

And it’s great for profits.

There’s really no downside.[1]

[1] unless, of course, you’re a terrorist, troublemaker, or paedophile.[2]

[2] While this comment is meant sarcastically, I know lots of people who think that way. China, the US, Canada, Russia and many other countries are headed in that direction.

@(required): What this comment section needs is more pessimism. That’s what I’m here for.

65535 • April 5, 2018 5:52 PM

@ RonK and others on the academic assumptions

“The research, while interesting, appears to assume a rather peculiar adversary — one who is actively controlling the allowed encryption algorithm and actively decrypting all communication, but who is unwilling to MITM all communications. AFAICS, none of the findings are useful against a re-encrypting adversary…”

Yes.

The MITM stuck out in my mind also. Since a cell phone or compute etc., has been compromised, there are other side channel attacks. There could be a key logger, screen scraper and on and on.

The Grass mud horse [FYM] system can be used successfully by key voice word, reputation techniques, physical drawings and maybe some good electronic steganographic techniques.

But “free” program like quick stego usually get caught by AV products. Only the quality stego products seem to work.

Does anybody have any good stego type programs that could be tested? Please speak up

Excuse my mistakes. I am not at my best.

RonK • April 6, 2018 1:13 AM

@ 65535

An even worse problem with the realism of situation hypothesized in the research is that given the opponent they assume, it’s extremely likely that the biggest risk to anyone attempting to use public-key steganography is that the other side of the conversation is also an adversary as opposed to someone really interested in secret conversation, and not that the steganography is weak.

Does anybody have any good stego type programs that could be tested? Please speak up

If you are willing to live with a very low data rate, it is trivial to come up with home-brew “undetectable” regular (not public-key) stego. For example, just run every sentence of your cover plaintext through a cryptographic hash function of your choice, and take the lowest bit. Since there are far more than 2 ways to express the meaning of any given sentence, generating any given stego text becomes merely a matter of trial-and-error with (expected) work linear in the length of the message you wish to “conceal”.

For public-key stego, we have some interesting research here, which doesn’t appear to have been published yet in any journal (YMMV, etc.).

chiraldude • April 6, 2018 10:28 AM

China is particularly interested in subverting this sort of thing. Their primary means of doing this is to provide incentives for reporting suspicious activity. With this sort of adversary, very high levels of trust is required before any stego messages can be sent.

RockLobster • April 6, 2018 10:52 AM

This reminds me of a small project a friend of mine coded based on a discussion we had about a similar scenario as described in the article, where being found to be in posession of encrypted data may not be an entirely good thing.
Our idea was to encode already encrypted data to an image format that might create abstract images that could not be proven to be encrypted data.
You can read our conversation (RockLobster and Stefan) On this forum thread,
wilders image secret
and see Stefan’s test programs, one of which encodes the encrypted data to a transparent image.

RobS • April 6, 2018 11:55 AM

Can’t we develop a ‘one time backdoor’ solution? That would reduce the risk of creating a backdoor and also keep supporting the wish of governments.

Humdee • April 6, 2018 3:25 PM

@RockLobster

While that is an interesting proof of concept I don’t understand the need for this type of gimmickry.

“Encryption is banned so you can’t transmit encrypted files, you can’t post encrypted messages, it is illegal to even posses encrypted data, so how do you get around that? One way might be, to make your encrypted data look like it is not an encrypted data at all, it appears to be just a PNG image.”

Well OK that is one way but the normal way one gets around that is to say “It’s not encrypted data, it is just random data.” How can anyone tell the difference between properly encrypted data and random data? One can’t. That’s where the deniability lies.

So any government that wanted to ban encryption would have to ban the production of random data or they would need to create a legal presumption that the possession of random data is evidence of the possession of encrypted data. But at least in the USA that would fly in the face of innocent until proven guilty since I would presume that the possession of random data is protected under the 1A.

Now perhaps that doesn’t work in $5 wrench countries but in those countries there are other, better ways to deal with that problem.

Jon (fD) • April 6, 2018 5:17 PM

@Humdee

For that you need plausible deniability. Why do you have just one random data file on your computer?

So you need lots of them, which is why I’m working on the “Random Data Email Exchange” wherein a few friends, at random intervals, send each other randomly sized files of random data.

Jon (fD)

PS – And it does, incidentally, provide a handy backchannel. “Hey, Joe, try XORing RDEE 8850154653 with RDEE 020211586647 together and see what happens…”

Again, only works if there’s a giant pile of data for the attacker to sift through – so it’s impractical for the attacker to XOR them all together in every combination.

Jon (fD) • April 6, 2018 5:19 PM

PS – Note that it doesn’t just have to be a combination of two. XOR two together, get something else, XOR that with a 3rd, get some more garbage, XOR that with a fourth, fifth, sixth, &c as long as your ‘Hey, Joe’ backchannel is secure. J.

Chris • April 6, 2018 5:43 PM

Hi havent been here in some time, but it seems that the propaganda war has arrived to this blog too. Its intresting though…

Anyways i hardly come here more than reading about strategies
and some intresting thougts especially i amuze myselfe reading Clive Robinson almost philisophically deep thoughts about not only security but life itselfe.

As and enduser and more, i can tell that, listening to the propaganda abt facebook google and more, has made myselfe think as well, strategy wise i am now moving away from commercial based linux to stuff like debian and slackware, i moved all of my servers from ubuntu to debian and i will not move back anywhere soon.I am also advising all of our customers to do the same.Surpricingly i have a couple of customers that i can influense not only on this matter.

If this continues it will be an intresting future for commercialism.
since it certainly isnt compatible with the land of the free.
Perhaps they havent understood what its about.

RockLobster • April 6, 2018 9:01 PM

@Humdee.
Gimmikery huh. Well I do not think understand the scenario.
You think when encryption is illegal you are going to send your “random data” around and it won’t attract attention?
Would you want to risk your own freedom on the chances that law enforcement wont be able to convince a judge that your “random data” is not encrypted data? Contempt of court sentances for refusing to obey an order to give up encryption keys can be a very long time.
Alternatively, posting or possessing an image that can be decoded to the encrypted data really could be considered random data if any normal image could also be parsed by the same application and would also create data that is random.

RockLobster • April 6, 2018 9:36 PM

Further to my previous comment, I think everyone needs to get past the random data == plausible deniability scenario which only has the potential to work while laws exist and are respected so that they can be used to that end. You can be sure any intent to make encryption illegal would include an attack on any such defence, not withstanding the fact, how many encryption applications do you know of, that actually even create true random data with no headers?
We are talking about tyrannical government here, the kind of government that would put an entire nation under surveillance to ensure they do not organise an uprising in response to a treasonous attack on their own nation by that government.
The kind of Government that would create fake incidents to highlight the need to trample all over such constitutional rights as defined by the 1A and go ahead and do it, because under that kind of regime congress is pwned and does what they are told because they know if they dissent, at the very least they will face the wrath of the entire mainstream media which is also pwned and they can kiss their next election goodbye.

Hmm • April 6, 2018 11:11 PM

“You think when encryption is illegal you are going to send your “random data” around and it won’t attract attention?”

Ken Thompson’s hand covers your mouth suddenly. Then poof, it’s as if it were never there.

You are stunned for 1 rounds.

Jon (fD) • April 6, 2018 11:43 PM

@ RockLobster

That’s why you need a history of throwing random data around, documented scripts that do exactly that, and lots of people joining in.

The idea isn’t to make encrypted communication undetectable, the idea is to swamp the spies in noise.

You don’t have to generate encrypted headers. Again, if you have another way of reasonably securely communicating (e.g. the “Hey Joe” over coffee) you can also mention “drop the first 81 bytes from File A” or something like that. Effectively you’re generating one-time pads, sending them all over, and never (or maybe once?) using them.

And we’re not trying to defend against the $5 wrench attack. Where the rule of law does not apply, there’s not much you can do about that (aside from stunts like splitting up the secret among many people, &c.).

Finally, it’s an interesting detail that if someone wants to frame you, it’s trivial. Any random file large enough can be made incriminating if the attacker has the random data and incriminating data and constructs a one-time pad such that, when XORed with the random data, yields the incriminating data.

That can be done for ALL data, plain, encrypted, or sheer random. Then they claim “That’s the key and you must have deleted it” and off you go.

Have fun,

Jon (fD)

RockLobster • April 7, 2018 12:50 AM

@jon (fd) I get your point and it is a good one if everyone dissented and filled the internet with noise but it wouldn’t work that way in practice.
Firstly what they would do in response to that is make scape goats of a few people and deliver hefty pubishments, and you would see all that noise evaporate as the vast majority will not risk their own freedom for a cause. That would leave you with just a hard core of dissenters still using “illegal encryption that get arrested in due course.
If you all want privacy and encryption to survive the impending assault by government and it is coming, all the signs are there, you have got to take it to another level where it is impossible to distinguish encrypted data from regular data.
Random data that cannot be explained, or proven not to be encrypted data will not be good enough and that is only about encrypted storage. The real issue is about private, encrypted communication in a potential and very likely near future scenario where doing so would risk imprisonment.
The convert to image format is just one idea that would work for both storage security and communication. An image can be sent directly or posted anywhere without standing out from the billions of regular images sent, received and posted.

Peter Quince • April 7, 2018 7:32 AM

“This result reminds me a lot of the work about subliminal channels from the 1980s and 1990s…”

Me too.

@ Me myself

I can see how you would think that this paper states the obvious. But it is so much more than that. What they are getting at is the fact that one can set up secure communications inside a compromised system by using the structure of that dorked system against itself.

Peter Quince • April 7, 2018 7:50 AM

@ RonK

Thanks for that interesting article!

“Does anybody have any good stego type programs that could be tested? Please speak up.”

People invent this stuff all the time, but, of course, they don’t talk about it. And such systems do not have to be based on public key cryptography.

Tualha • April 7, 2018 8:40 AM

@Sarah

Developing one’s own crypto software is highly deprecated. You may avoid other people’s backdoors, but unless you’ve been developing crypto software for years, you’ll almost certainly introduce backdoors of your own.

Clive Robinson • April 7, 2018 2:33 PM

@ 65535,

I’m sorry you are still not at your best, especially as the weather has now shown signs of improving. I would say “Get well Soon” but it sounds to much like an order 😉 So I hope your recovery is proceading at the rate you are hoping for.

With regards,

Does anybody have any good stego type programs that could be tested? Please speak up

I realy do not think there are any…

The reason I say that is that we do not know how the SigInt agencies “look for signals in the noise” and if a general program was written then I suspect they would have a “reverse engineered” version up and running in fairly short order…

Whilst Stego sounds very niche it actually is not, it realy is a game of looking for a signal in the noise, which is something that comms engineers do as a “bread and butter” part of their lives.

To try to describe the problem you have to think a little bit more than just Additive Guassian White Noise and code correlation.

From the users point of view they have a signal that is some fraction of a synthetic noise signal that in reality is highly organized and far from random by any meaning of the word. That is the “pretty lady picture” you are hiding your signal in has two distinct disadvantages.

1, It’s quite predictable.
2, It’s unlikely to be unique.

The first of these means there is little place to hide a signal, the second boils down to all the problems of re-using a One Time Pad.

But that is only half the problem, the other half is your signal. If you don’t encrypt or code it then it will be not just insecure but also stand out from the syatistics of the picture. But if you do use a standard encryption method then your signal will have swung the other way, it will stand out because it is to random…

Thus you have to apply a further transform based on the statistics of the picture you are using to carry your signal. After a moments thought you realise that such a transform has to be adaptive in nature, which brings up a whole other set of peoblems to do with signal detection and synchronisation.

We found out from the early Digital Rights Managment (DRM) wars in the late 1990’s that the person trying to inject and later detect a signal is always going to lose one way or the other. That is,

A, The adversary detects the signal.
B, The adversary corrupts the signal.

Ross J. Anderson and others showed that you could as a denial of service attacker apply very small changes to the combined picture and signal image. So small that to the human eye it made almost know visable difference, however to the Low Probability of Detection (LPD) signal it was a compleate killer.

And thereby hangs the problem… the more effort you put into making the signal undetectable, the easier you make it for the adversary to destroy the signal imperceptibly. The crossover point appears to be sufficiently high that the advantage is almost always with the adversary.

That is they do not have to detect a signal in a picture, they simply corrupt the image on the assumption there is one. This flips the usual security resource issue on it’s head. That is it is you as the individial trying to communicate covertly that needs the significant resources, not the adversary.

The way around the issue can be seen with linguistic codes that are not stylized. In effect you end up with a very large code book of One Time Phrases. That is there is no statistically determinable way to link plainly visble phrases in a message to any meaning they might convey.

One way to do this is to have a very long list of phrases. To send one bit of information you select either the first phrase as a “one” or the second as a “zero” and remove just it (not the pair) from the list. You then feed this phrase into a “generator” that builds the phrase into a sentence or paragraph based on previous and following sentences and paragraphs.

To avoid running out of phrases in the list you use a stream generator to decide where to insert the phrase back in the lower part of the list. Thus the list is continuously evolving based on the signal you are sending bit by bit but also by what is a stream cipher controlled slow shuffling algorithm.

Some years ago as an experiment I wrote code using two ARC4 stream ciphers to build the system. The first ARC4 was a standard implementation and was the stream cipher. The second in effect ran in a form of the key load algorithm to shuffle it’s state array the numbers within were used as pointers into a static word list.

It was justva bit of fun, but it showed that it was possible to do.

It also showed that you needed to treat the words in the list as “stop words” that you had to filter from the input stream. To do this you had to have a coresponding list of synonyms that would be sensible in all usages. Thus “Big,Large”, “Small,Little”. Coming up with such a list of “sensible under all uses synonyms” is actually harder than you would think…

As a variation that was simpler I used the list of synonyms as the way to encode bits. That is if the input contained one of the words on the list it would be used to encode the next bit. That is if you used the word “big” and a zero needed to be sent then it was not changed to “large”. If however a one was to be sent the “large” was sent instead. Obviously if the input contained “large” and a zero needed to be sent “big” was sent instead. Thus the stream cipher was responsible for swapping the order of the synonyms. That is “large” become zero and “big” one etc in the list. There were various ways that could be done, the trick was keeping the senders list and the receivers list in sync.

Humdee • April 7, 2018 4:23 PM

“Random data that cannot be explained, or proven not to be encrypted data will not be good enough and that is only about encrypted storage. The real issue is about private, encrypted communication in a potential and very likely near future scenario where doing so would risk imprisonment.”

If that is the “real issues” then the best solutions are to stop using digital entirely so mocking up pictures doesn’t work. What you suffer from is what I like to call “crazy dictator syndrome”. Crazy dictator syndrome is when a developer posits a dictator that is just crazy enough so that all the normal solutions don’t work yet the dictator is not so crazy that the developer’s preferred solution fails. There is, of course, no such crazy dictator in the real world. A dictator crazy enough to beat one because one has random data is crazy enough to beat when because he doesn’t like the pictures one possesses.

65535 • April 7, 2018 9:16 PM

@ jd

Picture => Particles

I like that demo.

I have downloaded the paper from cs Columbia edu. Very interesting
Here are a few links but not exactly like the Columbia paper.

http://w3schools.invisionzone.com/topic/57140-how-to-hide-text-in-image-using-php-mysqlfile-upload/

https://github.com/kzykhys/Steganography

Thanks

@ RonK

Converting your public key by stego is great idea! I didn’t think about It. I would probably help PGP users greatly and many others.

I down loaded the paper. It is a little heavy for most of use. But. I’ll give it a go.

Thanks

@ RockLobster

I copied the php code and book marked the page. It looks promising. I may have a few more Qs.

Good going.

@ Clive Robinson

Thanks for your concern. It is a ligament reattachment problem. I’ll give it another 3 weeks and the setting doesn’t take then I’ll see a orthopedic surgeon.
“…I say that is that we do not know how the SigInt agencies “look for signals in the noise” and if a general program was written then I suspect they would have a “reverse engineered” version up and running in fairly short order…”

Yes I see.

“…point of view they have a signal that is some fraction of a synthetic noise signal that in reality is highly organized and far from random by any meaning of the word. That is the “pretty lady picture” you are hiding your signal in has two distinct disadvantages.

“1, It’s quite predictable. 2, It’s unlikely to be unique.

“The first of these means there is little place to hide a signal, the second boils down to all the problems of re-using a One Time Pad… that is only half the problem, the other half is your signal. If you don’t encrypt or code it then it will be not just insecure but also stand out from the syatistics of the picture. But if you do use a standard encryption method then your signal will have swung the other way, it will stand out because it is to random…”-Clive R

Whoa, that is a huge problem. I’ll Stop hear and bring this over to squid thread. I have a few Ideas… It will take a day or so.

Thanks Clive R.

Excuse all of the mistakes.

Clive Robinson • April 8, 2018 1:35 AM

@ Humdee,

If that is the “real issues” then the best solutions are to stop using digital entirely

You are not the first to think that nor will you be the last.

If you look back Osama Bin Laden used to use various “technological tricks” to avoid giving his location away. After a few years he ended up using satellite phones untill a “rebel” who had been upsetting the Russians was on his sat phone one day when a “beam rider missile made him “End-Ex”. OBL did not take long to switch tactics.

Eventually as we know he ended up using the very old fashioned idea of couriers with USB sticks of digital data. Now we can not be sure but the story is told that OBL used “a lesser crime to hide a bigger crime”. Essentially the story is the couriers hid the USB sticks “in a lower body cavity” when crossing borders. This is an old smugglers trick[1] so is not exactly unknown to most border guards, who might just X-Ray a suspect, force feed them till things come to pass or just call upon the services of a medical PR surgeon etc. So to give the couriers some degree of deniability the OBL messages were encrypted, then using stego put inside fairly revolting porn. Hence the courier could claim he was just smuggling porn… Hence the lesser crime to try to cover the greater crime.

For all we know it may well have worked if it had been tested in action, but as such things often involve bribes or similar written records are unlikely to be available.

The real problem is not “using digital” but assuming high tech gives you new high tech solutions to an ages old problem, thus you can out smart / forget the lessons of the past. The reality is old school methods have been tried and tested and have survived the test of time, thus still work in many cases. Thus you should look to adding not replacing the old school methods. That is use the strengths of digital to augment the capacity of the Old school methods.

[1] As we also know all accessable body cavities have been used. The problem is generally not getting things in, but out again. You could hide a diamond in your ear cannal or up your nose in your sinuses that when retrieved could pay for a modest life style for quite a while. But it is worthless to you if getting it out requires second party intervention. I’ve yet to track down an original report, but it’s been said that some have found a way to beat the forced feeding. Apparently you tie what you are smuggling to a carefully measured length of dental floss which you tie the other end to one of your back teeth. You then swllow it. If you have the length right the object gets into your stomach but no further alowing you to drink normally as well as eat. When you want the object back you simply hook your finger behind the dental floss and pull it back up… Whilst it is possible, I’m not entirely certain people would use it due to the gag reflex amongst other reasons.

Gerard van Vooren • April 8, 2018 5:22 AM

@ Clive Robinson, about OBL,

“Eventually as we know he ended up…”

Yes, we know, pretty sure, that he ended up with a couple of bullets in his body, fired from a Navy Seal.

RockLobster • April 8, 2018 9:23 AM

@Gerard van Vooren I wouldnt be so sure of that.
According to Steve Pieczenik (who served in the administrations of Ford, Carter, Reagan and Bush Snr) OBL was a CIA asset the entire time and in 2001 while he was supposed to have been planning 911 in the ToraBora mountains he was actually in the American hospital in Dubai dying of Marfan syndrome where he was visited by CIA physicians and died shortly thereafter in 2002. Pieczenik said the entire story we have been told is a pack of lies.

Gerard van Vooren • April 8, 2018 2:37 PM

@ RockLobster,

I am not aware of the story of Steve Pieczenik, and although it could be true, it could have been false as well. It’s just the telling of people.

What I am talking about is the lack of any court (Den Hague?). It’s just that he was being murdered.

But that said I am interested in your facts.

Richard Moore • April 8, 2018 4:28 PM

Surely the ability to form a secure link over a backdoored channel is trivially true since we all rely on protocols such as TLS which can form a secure channel over an insecure network – how could a backdoored channel be worse than one that is accessible to all attackers?

Wesley Parish • April 9, 2018 2:27 AM

@Clive Robinson

re: Osama Bin Laden and smuggling, side chaqnnels, and the like

The Mullah Nasrudin would make the journey from his home village across the border every few weeks. He told the border guards repeatedly, “I am a smuggler.” And the border guards would search through the panniers of straw on the donkeys’ backs, then stand back, scratching their heads and let him pass. A few days later he would trudge back alone. Finally, a few years after he had gone bald and his bear white, he met one of the retired border guards in a coffee shop. The border guard offered him a coffee, then asked, “Now that we’re both retired, and you can’t be charged for anything, could you tell me just what it was you were smuggling?” The Mullah Nasrudin smiled and said, “Donkeys.”

Sarah • April 9, 2018 11:33 AM

@Tualha But do you know exactly how long I have worked in that field with any certainty? I’m just a name online.

But the comment does perfectly highlight why saying not to build your own software is problematic when used as a catch all phrase.

Also things like Ciphersaber: http://ciphersaber.gurus.org/ Were created for a reason. The point is in learning to be self-reliant.

Sarah • April 9, 2018 12:05 PM

Furthermore, how is one suppose to gain experience in the world of cryptography, being able to do it for years, if they’re constantly slapped down and told like a kid “Why don’t you stop that.”

Experienced and skill don’t come in a vacuum.

Alyer Babtu • April 9, 2018 2:15 PM

@Wesley Parish

I’ve always wondered how the customs guards never noticed the difference in mode of transport coming and going.

Jon (fD) • April 9, 2018 6:05 PM

@RockLobster

As another cute detail (which I sorta pointed out) it is impossible to prove that data is in fact random and not encrypted, because for any data, random or not, there exists a one-time pad that makes that data whatever the attacker wants it to be.

I could construct a one-time pad that made Microsoft Word (.exe) an encrypted version of a pornographic movie.

Not that I’d expect a typical judge to know that. Judge Posner might be an exception.

Jon (fD)

Jon (fD) • April 9, 2018 6:11 PM

PS – There is precedent for throwing around random data. It was much more popular during the height of the Cold War, but they still exist today. They’re called ‘numbers stations’ where a robotic voice reads out over the radio seemingly random numbers 24×7. Certainly some of those numbers mean something to someone – but to whom, where, and what?

And only a few stations sufficed to provide sufficient uncertainty.

J.

Ratio • April 9, 2018 7:00 PM

@Gerard van Vooren,

I am not aware of the story of Steve Pieczenik […] I am interested in your facts.

Those facts can be found on the appropriately titled Wikipedia page.

Facts of the more factual kind can be found in books like The Exile: The Flight of Osama bin Laden by Cathy Scott-Clark and Adrian Levy. (See this old comment for two reviews in The Guardian, and for news about some documents released by the CIA that may be of interest.)

RockLobster • April 10, 2018 3:07 AM

@Jon (fd)
I wasn’t disputing random data has it’s uses.
I was disputing it’s use in the scenario described in the article, which is also a likely to become a reality at some point in the not so distant future. That being, when the use of non state approved encryption is illegal.

I think it important to consider that very carefully. As we know already ALL properly encrypted data is random.
That means, the only way to enforce a law that criminalizes encryption would be to define what constitutes encrypted data.
The only way I can envision that is, they would have to say something along the lines of, data that can be forensically proven not to be of any known file type or part of any known application and is random in nature will be deemed to be illegal, encrypted data.
So for that reason, if we want to ensure encryption and privacy cannot be defeated by tyrannical government we MUST ensure it cannot be distinguished from unencrypted data.
The fact that it can should be considered a security flaw.
The fix is, to encrypt data then to convert the encrypted data to match known types of unencrypted data.
The image thing is just one idea to do that.
I liked it because you can post an image anywhere. That means it could be used to post a private key, or a message encrypted with the intended recipients public key.
Of course it would take some work on the algorithm that creates the image from encrypted data, to ensure firstly the image does not look like random noise, in other words it will need to create pseudo non-randomness and secondly, if the reverse operation is applied to a regular image, the output would be as random as when it is applied to the covert image because obviously the covert image really would output random data because it is encrypted data.

Wesley Parish • April 10, 2018 3:26 AM

@Alyer Babtu

I assume they weren’t expecting that donkeys were items to be smuggled. They were looking for other things, most probably: spices – which in the European Middle Ages cost a fortune; jewellery; gold; jewels; etc ad infinitum, ad nauseam ….

Besides, there are undoubtedly many ways in which a businessman can lose a donkey – it dies, it’s stolen, it’s eaten, it wanders … and they had far too much on their plate to bother about the miseries of poor Mullah Nasrudin.

RockLobster • April 10, 2018 3:37 AM

@ratio & @ Gerard von Vooren
Ok so who are you going to listen to, the authors of a wikipedia article written by who knows who, with the title “conspiracy theories”?
(conspiracy theories being a phrase coined by the CIA in the 1960’s to belittle and discredit those who disputed the oficial line regarding the Kennedy Assassination)
OR… are you going to listen to a man who served in 4 Presidential administrations, has a Harvard degree and a degree in psychology, was described by a nobel peace prize winner as “one of the most brilliant men in the field of anti terrorism”?
Also consider this. Pieczenik, in the context of what he said regarding OBL went a lot further than that. He publically, on video accused the Bush Administration of being complicit in the 911 attacks and named and accused several members of that administration, of treason. Yet not a single mainstream media reported that.
Just a wall of silence.
So if you want conspiracy theory, the entire mainstream media is involved in a cover up and that fact alone is a pointer to who were the real guilty party. All you have to do is figure out one thing.
Who owns the mainstream media.

Jon (fD) • April 10, 2018 11:03 AM

On Osama Bin Laden and tinfoil hats:

I’d rather ascribe it to incompetence. The SEAL Team Six went in and got the wrong guy. Some medical examiner on the aircraft carrier kept looking at the body and saying, “Um, guys? That’s not Osama Bin Laden. You got the wrong guy.”. He takes it to the captain, who says, “Bury him at sea and that will be the end of this.”

Anyhow, we’ve gotten a bit OT here. Carry on! J.

Sancho_P • April 10, 2018 3:36 PM

@RockLobster,

”As we know already ALL properly encrypted data is random.”

  • Depends on who’s “we”, but if true it would be a mistake.

Or would you define “encrypted data” by “whatever is random”?
And the opposite, not-random means clear text (not forbidden then in Paranoia)?

OK, but after agreeing on “encrypted data = random” we now have only to define “random” (and it’s opposite).
Easy, isn’t it?
(Hint: Try to leave binary thinking, go analog.)

RockLobster • April 10, 2018 4:15 PM

@Sancho_p
Ok well my assertion that we know properly encrypted data is random is based on my understand that in cryptanalysis, if anything not random is found, it is considered a flaw.
Would I define anything random == encrypted data? No.
I was trying to theorize how a ban on encryption would be enforced and it seems to me, it demands that encrypted data be defined otherwise how could you enforce a ban on something that has not been defined?

I don’t know what you mean by clear text not forbidden in paranoia.

Ratio • April 10, 2018 6:29 PM

@RockLobster,

Ok so who are you going to listen to […]?

Ehmm… the evidence?

@Jon (fD),

You got the wrong guy.

Minor unexplained detail: what happened to the right guy in this alternate reality?

@Sancho_P,

Try to leave binary thinking, go analog.

Typical binary thinking.

Clive Robinson • April 10, 2018 10:10 PM

@ RockLobster,

Ok well my assertion that we know properly encrypted data is random is based on my understand that in cryptanalysis, if anything not random is found, it is considered a flaw.

It’s best not to talk about “random” as it realy has no worthwhile meaning that is properly testable (hence the joke about 4 is a random number).

What people look for in data are patterns in various dimensions or other factors which will give them better than fifty fifty odds on the next bit. Unfortunatly that’s not the way nature works…

For instance if you take a crypto algorithm and just use it to encrypt data you won’t get anything close to random (see the picture of Tux the penguin after a little crypto, you can still see it’s Tux or a near equivalent.

It’s why we do not use crypto algorithms in “code book” mode but a chaining or other mode. Often these modes take a past output and mix it in with the data befor enciphering it etc in one of the “chaining” or “feedback” modes.

The thing is what you call “random” if generated by a stream cipher will almost certainly be “too random” which is more of a give away than most people realise.

You normally get told to “compress before encrypting” based on the idea the compression algorithm will “remove redundancy”.

However that is just part of the story… Back in WWII the German’s were regularly breaking “poem codes” that SOE had had inflicted on them by the likes of the British “Secret Service” who in general just wanted SOE personnel killed off as quickly as possible.

The thing about the SOE poem code was that it was fairly usless crypto wose for short messages and thus the operators had to send longer messages. The time it takes to send by Morse Code on a CW transmitter the required minimum of 250 characters at 12wpm / 60cpm the German SigInt people had your location locked down to under a mile and armed troops would have been on their way…

But the Germans were also breaking the poem code more often than they should have been… Because the plain text statistics came through in the cipher text frequency counts. When SOE started to switch over to One Time Pads (OTPs) the Germans were easily spotting the two decidedly seperate system, thus did not waste personeel trying to break the codes.

So somebody in SOE had to come up with a way to turn what looked like “true random” nearly flat statistics. Into what looked like the statistics etc of poem codes.

This they did which probably saved a good number of alied personnel’s lives, but by know means all.

So yes there is random data and not so random data, which is why cryptanalysis want to make “not so random data” look like it’s fully random, and fully random look like “not so random”…

Sancho_P • April 11, 2018 4:04 PM

@RockLobster

”I was trying to theorize how a ban on encryption would be enforced and it seems to me, it demands that encrypted data be defined otherwise how could you enforce a ban on something that has not been defined?”

I thought you were theorizing about the ban of the use of “private encryption”, which would be a double no, because “they” would then have to define both, encryption and private [1].

But also “they” would be to define, that leads to what I’ve called “Paranoia”:
The imaginary world-wide state where everybody is criminal per se, fears anyone, wears body armor, guns, surveillance equipment and doesn’t trust their personal lawyer, let alone their own family in the bedroom.

I think the whole discussion is only possible from the very narrow American-centered world view of some first graders (and their “allies”):

“Encryption is what we do not understand!”

So send the clear text message “I love you” to Christopher Wray or Theresa May and you’d go to jail because they don’t understand == it must be privately encrypted?

They can’t enforce a ban on something they don’t understand.
Not even in Paranoia.

But:
Be careful with hiding something in images or wherever:
If found, even in paradise, it will make you the suspect!

[1] Assume to be a business man and have to transmit proposals, financial and technical details for huge projects in the public sector (water, transport, energy) to foreign entities. Several foreign and local “institutions” would be interested in, so would “they” deem your encryption to be private?
And whose “they” (state approved = backdoored) encryption you’d have to use? USA, Russia, China, UK, France, Germany, Australia, SA, …
Or would they all (want to) use the same general key?

Jon (fD) • April 11, 2018 6:23 PM

@Ratio:

“Minor unexplained detail: what happened to the right guy in this alternate reality?”

He has discovered the basic movie plot of “Die Hard”, that if they think you are dead they stop looking for you. If I were Osama Bin Laden and thought to be dead, I’d be keeping a real low profile too.

And @Clive Robinson and @RockLobster:

The point is that well-encrypted data are indistinguishable from random noise.

Another point is that any data can be made incriminating with a carefully selected one-time-pad key.

We may be into ‘paranoid dictator’ fields here again.

J.

Garrett • April 16, 2018 1:59 PM

I used to work for a data storage company doing filesystems work. As a part of this I frequently needed to test performance of streaming reads and writes. Fortunately/unfortunately, the system supported deduplication. This meant that attempting to re-send the same data, even by a different filename, might get different performance characteristics as the data was deduplicated. Great for customers, terrible if you are attempting to benchmark disk write throughput.

dittybopper • April 17, 2018 7:29 AM

Meh. They’ve just discovered something that Leo Marks invented in WWII, a way of disguising encrypted information to make it look as if it’s a normal, banal, unencrypted connection. You can find a description of the method near the end of his book “Between Silk and Cyanide”.

Anomin • May 10, 2018 11:15 AM

I found this paper “How to Subvert Backdoored Encryption …’ fascinating as to how to surreptitiously embed “implied” bits within cibertext messages. Cibertext is manipulated plaintext that becomes manipulated ciphertext. I’m new to this, is “cibertext” new jargon?

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.