Rubber-Hose Cryptanalysis

Cryptographers have long joked about rubber-hose cryptanalysis: basically, beating the keys out of someone. Seems that this might have actually happened in Turkey:

According to comments allegedly made by Howard Cox, a US Department of Justice official in a closed-door meeting last week, after being frustrated with the disk encryption employed by Yastremskiy, Turkish law enforcement may have resorted to physical violence to force the password out of the Ukrainian suspect.

Mr Cox's revelation came in the context of a joke made during his speech. While the exact words were not recorded, multiple sources have verified that Cox quipped about leaving a stubborn suspect alone with Turkish police for a week as a way to get them to voluntarily reveal their password. The specifics of the interrogation techniques were not revealed, but all four people I spoke to stated that it was clear that physical coercion was the implied method.

Posted on October 27, 2008 at 12:45 PM • 70 Comments

Comments

CameramanOctober 27, 2008 12:50 PM

Oh, dear. Slippery slope and so forth.

Remember that one sys admin from Sacremento or someplace who sat in the slammer for some time before he sang?

I just reread that sentence, and while it wasn't coherent at all, I'm leaving it unedited because the alliteration is wonderful.

Ed T.October 27, 2008 1:08 PM

I doubt they used a rubber hose. After all, the Turks really don't give a damn whether they leave marks or not.

~EdT.

Nick LancasterOctober 27, 2008 1:09 PM

I wonder what interrogators would do if the keyphrase was something offensive? Continue beating the suspect for the 'real' keyphrase?

SOctober 27, 2008 1:14 PM

There's a bunch of things wrong with password-based access controls. And not because I am afraid of Turkish officials, or that I could be thrown in a dungeon in some faraway place. It's because 1)the password challenge immediately flags the attacker there is something behind there, and 2)it's a human weak link, and 3)it's too easy to snoop on using other tools with a presence you are unaware of.

The first line of defense - deniability. I want a potential attacker to remain oblivious of the information as long as possible.
The second line of defense - don't use access controls with a single point of failure.
The third line of defense - don't depend on encryption. The size and reputation of the vendor does not matter (ie MS), and you have no way to know that just because they say they use such and such algorithm blah blah blah, that it is being applyied correctly.

BTW - an inadvertent development which is emerging from the security community is that all thinking is being pushed off onto a handful of gurus. What ever they say or don't say is being written in stone. I am running into more and more bigshots that should know better, but have instead abdicated their mind to what so and so said in an interview, or at some show. This is really dangerous. Not because the gurus are necessarily wrong. One person I heard plain laughed when shown something extremely powerful. He laughed because he was immediately sure it was a scam and genuinely impossible. Worse, he wasn't even correct about what was or was not possible. So, now we have this very powerful thing out there that no one even believes COULD exist.

nothingnewOctober 27, 2008 1:16 PM

Nothing new in Turkey. I don't know why so many tourists visit such countries every year.

xOctober 27, 2008 1:26 PM

"Seems that this might have actually happened in Turkey"

Might?

Might?

This is Turkey. Torture is as much of a secret as Israel's nukes.

Come to think of it, name *any* country you're *sure* doesn't torture people.

CurmudgeonOctober 27, 2008 1:42 PM

Step back for a moment.

Yastremskiy is suspected of conducting very large scale organized identity theft and credit card fraud. That he was apparently tortured at the implicit behest of the DoJ indicates that US use of torture has slid down the slippery slope from terrorism cases to the prosecution of mundane criminal activity.

The real security issue here isn't the vulnerability of FDE but rather the creeping institutionalization of torture in criminal cases. Words cannot describe the extent to which this is a vile perversion of justice.

dimrubOctober 27, 2008 1:58 PM

The corresponding russian mot is thermorectal cryptanalysis, relating to the use of hot soldering iron by the criminals to extract secrets out of their victims.

Clive RobinsonOctober 27, 2008 1:59 PM

@

"The real security issue here isn't the vulnerability of FDE but rather the creeping institutionalization of torture in criminal cases."

And this surprises you?

I think it goes under the polite term of "mission creep".

It is clear the US people accept that human rights are being abused by US service personnel and they likewise accept rendition flights. After all was there realy much protest at the humiliation of ordinary Iraq men in Iraq prisons by US personel?

It was fairly clear from what came out that it is institutionalised from the very top. And with US police claiming that ordinary US citizens are terorists for what would be at best misdemenours pre 9/11 is it any surprise this has come out let alone been happening.

Now there will probably be a little noise but acceptance is what those in charge will expect to happen. As was once remarked,

"Seldom is freedom lost..."

CurmudgeonOctober 27, 2008 2:24 PM

@Clive Robinson:

I'm appalled but absolutely not surprised. The historical evidence made it clear that the use of state sanctioned torture in ordinary criminal cases was entirely inevitable once extraordinary rendition became an accepted practice.

And no, I don't expect Obama to do anything about it either.

Baron Dave RommOctober 27, 2008 2:55 PM

A similar plot has been the story arc of the last few episodes of The Unit: The Bad Guys kidnap the family of a Secret Service agent, get the codes and passwords, and successfully attack the vice-president elect and nearly get the president elect. And The Unit families have to go into hiding.

mcbOctober 27, 2008 2:56 PM

@ x

"Come to think of it, name *any* country you're *sure* doesn't torture people."

Hmmn, I'll bet dollars to doughnuts that Iceland and Norway are in the clear...not sure about Sweden and Finland though.

nickOctober 27, 2008 2:57 PM

Remind me never to set my passphrase to: "please, for the love of god, stop beating me!"

Davi OttenheimerOctober 27, 2008 2:57 PM

Here's the 2007 HRW report on Turkey:

http://hrw.org/englishwr2k7/docs/2007/01/11/...

"Reports of torture and ill-treatment remain much lower than in the mid-1990s. However, during the March disturbances in Diyarbakýr, hundreds of people were detained and allegedly tortured, including approximately two hundred children."

I guess you could say that was related to cryptanalysis too...as we all know children are the key to the future.

Martin SeebachOctober 27, 2008 3:13 PM

My immediate though from reading the article was that it was actually just a joke. We should at least consider the very obvious possibility that it was actually a joke. It would hardly be the first time law enforcement personnel was caught joking about using violence against a suspect, and then not actually doing it.

John CampbellOctober 27, 2008 3:49 PM

Some cute ones I heard for a root password:

ida know

beats me

i dunno [it]

you're ki[dding]

though all of those date back 20+ years when we didn't worry as much as we do today (only insidered could get at the boxes at all).

Nowadays? No way can these be used... but, think about it... they were kind of funny.

john campbellOctober 27, 2008 3:55 PM

Actually, you can drop "rectal" from thermo-rectal... since cryptanalysis already has the word "anal" in it.

CurmudgeonOctober 27, 2008 3:57 PM

@Vigdís, mcb:

Iceland and Norway have provided material support to CIA rendition flights carrying suspected terrorists to be tortured.

@Martin Seebach:

You're giving far more credit than is due.

Clive RobinsonOctober 27, 2008 4:26 PM

@ x, Vigdis, mcb,

I know of one place in europe that can claim it does not tourture, which is the Principality of Sealand.

Which as I'm reasonably certain you will not of heard of it (it's the trouble with these little places) I've included a link to it's official website,

http://www.sealandgov.org/

It has an interesting history which is why I'm fairly certain it does not partake in unsavoury practices (but I can check next time I'm down that way)

alethiophileOctober 27, 2008 4:27 PM

Plausible-deniability is good, especially the dual-possible-password idea used in Truecrypt and other things. When facing an adversary that is in a position to use rubber-hose cryptanalysis, then security isn't enough-you need obscurity.

AndrewOctober 27, 2008 6:35 PM

The real security issue with rubber-hose crypto is to make sure that you don't actually know anything worthy of the rubber hose treatment!

Ignorance can truly be bliss. It may or may not save you from thermo-rectal cryptanalysts, but at least gives you the high ground to not-sit upon.

Henning MakholmOctober 27, 2008 6:57 PM

Clive: "... the Principality of Sealand. Which as I'm reasonably certain you will not of heard of it ..."

I wouldn't be so certain of that. Quite a number of people must have first discovered Bruce Schneier through Neal Stephenson's "Cryptonomicon" -- that's what I did. About at the same time, www.eruditorum.org redirected to people who offered server hosting outwith the reach of law enforcement, to wit, at the Principality of Sealand.

Doug RansomOctober 27, 2008 9:28 PM

Good thing he wasn't using biometrics. I bet he stilll has his fingers and eyes.

neillOctober 27, 2008 11:08 PM

very sensitive passwords should always have several components, one you can remember, and one you can't:
e.g. use a 40 letter password, where the last 20 digits are your vaccum-cleaners and coffee-makers serial numbers
easy to look up, but safe even with lie-detectors/brainscanners (like in india)

Orlando StevensonOctober 27, 2008 11:29 PM

Yes- in a twisted way, reafirms that people remain the weakest link to security.

Turkey doesn't treat their own much better- fficers have been known to perform on the spot, make 'em an example "head shot" executions of enlisted not performing up to standards – definitely not on my top 10 foreign travel spots.

SparkyOctober 28, 2008 3:47 AM

I'd think using Truecrypt would be a very bad idea, because the "accused" can never prove or even plausibly claim that there are no more hidden partitions, which probably means that the attacker will continue the torture, while the accused doesn't have any more passwords. There is no need for the attacker to prove that there is a hidden partition. The cost of the attack, for the attacker, is sufficiently low that they can easily continue the torture.

The best thing would be to make sure the attacker does not have any reason to believe that you are hiding anything. Another method could be to prove to the attacker that you do not have the means to decrypt the information, either without the help of others, or after a certain point in time.

Perhaps the best way would be to make sure the attacker destroys the information in the attempt to retrieve it, like physically breaking the chip holding the key when the computer containing the information is moved.

All the current methods fail if the suspect doesn't get a fair trial by western standards (excluding the UK and possibly the US).

A nonny bunnyOctober 28, 2008 4:10 AM

The best security measure is probably to just forget your password. And is it happens, scientists have just recently found out how to selectively erase memories. http://www.news.com.au/couriermail/story/...
Of course, that doesn't mean they won't beating you until you give them the password. It just means your secrets are save even if you break down completely.

BillOctober 28, 2008 4:40 AM

@neill

Have you ever tried to board an aircraft with a laptop, Dyson and a Tefal as carry-on?

:)

TroyOctober 28, 2008 5:21 AM

I'm quite impressed at the suggestions regarding how to avoid giving away your password even under torture. But remember that security is a tradeoff...

How long do you think your torturers will continue before believing you that you can't comply with their requests, even after you are broken?

Of course, if you're fighting for your people or your country, and you're willing to go to those lengths to protect sensitive information, then I have nothing but respect for you.

RickOctober 28, 2008 8:01 AM

Countries don't torture, people do. Even if the people concerned are senior in government, the country itself is still not evil.

true thatOctober 28, 2008 10:04 AM

The main problem with forcing a password from someone with violence is that, if the password only works with a USB token (which has been destroyed), the interrogators will not understand and will continue to do violence to the individual.

dogOctober 28, 2008 11:04 AM

@true that at
That's why it's always a good idea to use two factor authentication: a password and a key file stored on an easy to destroy media.
If the tiny media is destroyed in time, all the data is lost for everyone (unless a copy is given to a trusted third part to the other side of the world) and the interrogators will no longer have any advantage nor point in rubber hosing the subyect... at least no one for the survey...

A nonny bunnyOctober 28, 2008 12:10 PM

@ dog

But how will the interrogators know this? Even if they have evidence of a medium having been destroyed, it might just have been a decoy. You can't prove that the data is lost, that you don't have the second key, that there even was a second key.
They'll just beat you up some more to make sure; and perhaps to dissuade anyone else from trying "plausible deniability". --> "If you carry any encrypted material, you'd better be able to give us the password or we'll beat you till you die."

Pat CahalanOctober 28, 2008 12:11 PM

@ Sparky

> The best thing would be to make sure the attacker does not have any
> reason to believe that you are hiding anything.

The flaw in this thinking is that you're assuming that the attacker doesn't come into the scenario assuming that you *are* hiding something. Then, even if you're not hiding something, you're pretty much screwed :)

> Another method could be to prove to the attacker that you do not have
> the means to decrypt the information, either without the help of
> others, or after a certain point in time.

This isn't a half-bad idea, but again assumes that this is sufficient payoff for the torturer to stop torturing you, which is sort of unlikely.

If there is no barrier to the torturer to continue torturing you, he (or she) is likely to continue until you give them information that they find interesting; there is no other reason for them to stop.

This means that I'd generally consider it to be a better idea to give an agent a local copy of marginally useful encrypted information, and remote access (or at least remotely revoke-able access) to the really useful stuff. If the agent is compromised, you revoke the ability to access the sensitive data, and let the agent disclose the marginally useful data if and when it becomes necessary for he or she to do so. Then the torturer gets a reward (suitably scaled to show that the agent is low-value), and the new value of the captured agent is now in trade or ransom.

neillOctober 28, 2008 3:13 PM

@bill
good point, haven't tried it yet, but you're surprised what people carry around with them!

other suggestion would be certain phone numbers (read backwards) from your cell, you could even bring a hardcopy and nobody would know which numbers or digits to choose

billswiftOctober 28, 2008 3:21 PM

"Countries don't torture, people do. Even if the people concerned are senior in government, the country itself is still not evil."

The people are at least passively complicit in anything "their" government does. See Modesitt's novel "The Ecolitan Enigma" for one extreme fictional example. See Nazi Germany, Maoist China, and the Khmer Rouge for real world examples.

fuchikomaOctober 28, 2008 5:19 PM

That's why I think we have to remove people from the loop for extremely high security issues. Sure it's hard to do, but look at timed bank vaults. You'll shoot if I don't open it? Sorry, it only opens at 4:33pm! You'll have to wait a few hours...

I'm also wary of things like fingerprint scans as all it takes to defeat it is an assailant with a cleaver... if your data/access is worth enough, people will be ruthless.

Duress pins are good in some cases, if the original can't be easily derived from it, and if they don't immediately appear to fail.

But really, I'm not a security expert so I don't have a real solution to things like this - just don't rely on a password that can be beaten out of someone...

JoshOctober 28, 2008 8:14 PM

my root password on my iphone is "notalpine" so if anyone asks, I can tell them what it is safely....

HarryOctober 29, 2008 8:41 PM

@fuchikoma - the timed bank vaults work because the bad guys know about them and that the clerk absolutely cannot open the vault.

There's nothing similar - no gateway or blockage - that torturers know about. So they'll just keep torturing. Not till you tell them the password but till they *think* you've told them the password.

This sort of torture mission creep keeps me up at night. Identity theft does not, in any way, qualify for the bomb threat test (would you torture to learn the location of the bomb that's going to explode in 10 minutes?).

And any law official who says he didn't know that Turkey tortures detainees is lying.

Sodim PentathalOctober 29, 2008 9:14 PM

After giving name, rank and serial number for as long as I can, my answer goes something like this:

"There are three keys. Bruce has one key. Bob and Alice have the other two."

TonOctober 30, 2008 3:23 AM

Have you ever heard what a Black Site is?

That is an American invention, to outsource torture, to countries which are viewed as "legitimate sources of torture"

http://en.wikipedia.org/wiki/Black_site

By the way, why would they need Turkish Police to get the cypher? The LA Police Dept would do that for just the fun of it. They would not even mind it to be recorded on tape.

hamdyOctober 30, 2008 12:55 PM

I understand how fun it is to blame "uncivilized" countries for the lack of "human rights" or "democracy".
But u guys should better give us some time till the goals of US goverments are accomplished in Iraq. We(Turkey) will learn those echical or virtuous acts better from our neighbor.

Mikael AunoOctober 31, 2008 6:36 PM

@S

> The third line of defense - don't depend on encryption.
> The size and reputation of the vendor does not matter
> (ie MS), and you have no way to know that just because
> they say they use such and such algorithm blah blah
> blah, that it is being applyied correctly.

Yes you have, it's called open source.

mooNovember 1, 2008 12:37 AM

@x: I'm sure that Canada doesn't torture people.

It has occasionally allowed them to be diverted through the U.S. to places like Syria which are willing to torture them, but after it became emarassingly public knowledge I think the government is trying hard not to let it happen again.

dogNovember 4, 2008 1:54 AM

@A nonny bunny
They can do it anyway, and can do it regardless they find information or no, just for ideological / mediatic purpouse.
But this solution of a multiple phisical, destructible key ay least let open the way to both render the data useless for the attacker and let the recover possible from people owning the key in other states (or in a distant future, to don't let a piece of history disappear).

wangyongSeptember 27, 2009 12:58 AM

On Key Authentic Degree of Cryptosystem
WANG Yong WANG Huangdeng
(School of Computer and Control, Guilin University of Electronic Technology, Guilin 541004, China)
hellowy@126.com

Abstract:Against such attacks as rubber-hose attack, key authentic degree of cryptosystem is expatiated in detail, and the important significance of key authentic degree of cryptosystem is pointed out. And the key authentic degrees of modern cryptosystem under different conditions are given. Research shows that under most realistic situations, the key authentic degree of modern cryptosystem is high, this means that modern cryptosystem is threatened by such as rubber-hose attack and so on. Feasibility of low key authentic degree reliability is analyzed, and the implementing of low key authentic degree algorithm is studied.
Keywords: key; probability; rubber-hose; redundancy; cryptology

1. Introduction
Rubber-hose attack is a kind of attack without technique, but it is very effectual. The cryptanalysts obtain the key via threatening, extorting or afflicting the key holder until he gives it out. The kindred attack is key purchase based on bribery. These all are very effective attacks and they are often the best approaches of breaking a cipher [1]. The holder has to give the key to someone who want the key not only for being controlled, but also sometimes for fear of hurting somebody's feelings, even for being stressed by power or interests. Assume a ciphertext may have a meaning using more than one key. The wrong keys are called spurious key (pseudokey). There are mostly few spurious keys for the common modern cryptosystems, what’s more, it is difficult to find the spurious keys. According to Shannon's theories, when the lengths of the keys are fixed, the amount of the spurious keys will gradually decrease along with the increase of the ciphertext length. The modern cryptographic algorithms are all based on the fixed length keys, the amount of the spurious keys will be decreased along with the increase of the ciphertext, and the authentic plaintexts decrypted from the spurious keys may be eliminated because possibly they entirely don't correlate with the communication background at that time, so the spurious keys that can be trusted by the cryptanalysts are very few. The most modern cryptographic algorithms use bits or chars of the data as the computational unit, and after complicated computation, the spurious keys are difficult to find out even though they are existent. This means that in the condition of modern cryptographic algorithms, if a key holder randomly offers a key when facing the rubber-hose attack, obviously the cryptanalyst can easily find that the key is wrong, because the plaintext can be found to have no semantic meaning in most situations. If the key holder cannot withstand the rubber-hose attack, finally he will have to surrender and provide the real key. Because of these reasons, designing encryption algorithms whose spurious keys can be easily found out is very significative, especially in military fields. The concept of the key authentic degree was proposed in [3]. The key authentic degree of cryptosystem means the difficulty of finding out the spurious keys which we can decrypt to obtain semantic meaning plaintexts without flaws under a certain conditions. Essentially it is used to weigh the degree of the trustworthiness of the key provided by a key holder who is intimidated but not willing to leak the plaintext under the condition that the ciphertext and the algorithm are known, assuming that the key holder tries his best to provider a spurious key without flaws to misguide people who intimidate him. The key authentic degree is high if the spurious keys of the cryptographic algorithms are hard to find out. The reason why we named it as authentic degree is that when the algorithm whose spurious keys are hard to find, then a key that can decrypt the ciphertext to a meaningful text is mostly authentic. If what we get is not a real key, the plaintext decrypted from the key is mostly meaningless code. On the contrary, if the plaintext has semantic meaning, the key is the right key in most cases.

wangyongSeptember 27, 2009 1:00 AM

2. The significance of the research of key authentic degree
In cryptography, Kerckhoffs' law (also called Kerckhoffs' assumption or Kerckhoffs' principle) was stated by Auguste Kerckhoffs in the 19th century: a cryptosystem should be secure even if everything about the system, except the key, is public knowledge that means all the security must lie in the choice of key. Now the protection of the keys still relies on such passive measures as encryption, multistage encryption, or even hardware protection. But there is no effective methods for the direct rob of the keys and the intimidation to the key holders. Many existent attacks under rigorous conditions are studied in the modern cryptanalysis, but there are still no precautionary measures for the rubber-hose attacks and the rob of the keys. The spurious keys of most current cryptographic algorithms are very few, moreover there is no effective method to find out spurious keys, and these increase the risks of the intimidation and interception of key. Under this situation, it is very difficult to find out a spurious key to educe a semantic meaning plaintext, therefore to a great extent we can estimate whether a key is the real key according to whether the plaintext educed from the key has semantic meaning. Namely, the key is authentic if the plaintext educed has semantic meaning. For a cryptosystem which is difficult for us to find out the spurious keys, the plaintext can be directly decrypted from the key, and then we can estimate whether the key is the real key according to whether the plaintext has semantic meaning. Hence it is necessary to establish and consummate the concept the key authentic degree of cryptosystem. We should also study the corresponding influencing factors and design a low key authentic degree cryptosystem whose spurious keys is easy to be found out.
Moreover, many modern cryptosystems or algorithms such as DES and RSA can be broken by quantum computers in very short time. With the increased speed of computers, modern cryptosystem is also threatened by high performance computer. Even under the ciphertext-only attack, because the spurious keys are very few and the semantic meaning plaintexts we obtained may be eliminated by the cryptanalyst according to background information, and then finally very few keys or one key may be at the waiting list of the right key. This also may cause the leakage of part or all of the information.
The security of modern cryptosystems relies entirely on the security of key. But in the situation that the key authentic degree is high (namely the spurious keys are very few and difficult to find out), we can exclude large numbers of keys only according to whether the plaintext decrypted from the ciphertext has semantic meaning. This influences the security of the cryptosystem. And in some situations, we can reduce the uncertainty of the key and even can directly certain the key in conjunction with other conditions. Even in the situation that the computing power is finite, the cryptanalysts also may possibly obtain the key of a semantic meaning plaintext by chance through brute force. And if luckily they find no flaws and the plaintext matches the context of the communication, to a great extent we can believe that the key is the real key.
This consideration is not hairsplitting. Modern cryptosystems have proposed complete analyses for many attacks whose precondition is hard to appear, for example the conditions of chosen message attack is that the cryptographic machine is captured and the key inside it is not destroyed, or the cryptanalysts can momentarily use the cryptographic machine. The current cryptanalysis mainly considers the situations of finite computing power. Now the computational security of the algorithms is studied in depth, not only the algorithms, but also the realization of the algorithm and other factors are considered. The analysis technologies of ciphers are unprecedentedly developed, and now there are many analysis technologies of block ciphers such as brute force attacks(including exhaustive searches attack, dictionary attack, look-up table attack and time-storage balance attack),differential cryptanalysis and its generalization, differential linearity cryptanalysis, interpolation attack, correlational key attack, multi-set attack, reflection attack, self similarity attack, energy analysis, error attack, timing attack and so on. The main attacks of stream ciphers are differential cryptanalysis, linearity consistency testing cryptanalysis, divide-and-conquer (DAC) attack, algebraic attacks, and so on[4]. The analysis methods of public key cryptosystems mainly decrease the difficulties of the intractable problems. Many of these analysis methods are put in practice under conditions of small probability (such as the interceptions of cryptographic machine, the cryptanalysis is near to the cryptographic machine and so on), and these researches are very intensive. But in our consideration, if cryptanalysts get enough ciphertext and know the cipher algorithm, the wrong key can be excluded by redundancy, but these two preconditions generally are necessary to the modern cryptanalysis, because according to Kerckhoff’s assumption, the encryption algorithms may be public, and the ciphertext is indispensable for the cryptanalysis.
3. The key authentic degree of modern cryptosystem under different conditions
In 1949, C.E.Shannon published "Communication Theory of Secrecy Systems"[2], and it transformed cryptography from an art to a science. Shannon's paper introduced the information theory into cryptography, and from the view of statistics to make a mathematical description and a quantitative analysis for the information source, the cipher and others. Shannon made a very penetrating analysis and research of the problem of spurious keys. He defined the spurious key (pseudokey), ideal secrecy, the unicity distance and the perfect security according to the information theory and redundancy. But most cryptosystems cannot approach ideal secrecy, the number of spurious keys (except the right key) will finally reduce to 0 along with the increase of the length of the ciphertext, and this will intimidates the security of cryptosystems. Shannon studied on the cryptanalysis under the conditions of ciphertext only attack, he pointed out that the number of spurious keys will gradually reduce along with the increase of the length of the ciphertext. Although the above analysis of Shannon is of great value, but cryptanalysts seldom do research from this aspect.
The measurements of the key authentic degree of cryptosystems can also refer to Shannon's theories. But in reality the measure of the key authentic degree of cryptosystems will differ because of the restriction of conditions and background information. We define the key authentic degree of cryptosystem as the probability of the correctness of key that the key holder gave cryptanalyst under the restriction of conditions although the key holder tries his best to find out a wrong spurious key. We think the cryptanalyst estimate whether the key is reliable according to whether the plaintext has semantic meaning and whether there are flaws in the plaintext, if there are any flaws in the plaintext or the plaintext has no semantic meaning, the cryptanalyst will continually intimidate the key holder into surrendering the real key, so finally the key holder either surrender the real key or surrender a spurious key without flaws.
We will discuss the following situations:
Firstly, when a cryptanalyst knows nothing about the content of communication and the communication background, and he have infinite computing power, and that the key holder has infinite computing power to use, the key authentic degree is closely related to the redundancy of encoding. When the number of spurious keys is 0, if ciphertext may have a meaning using a key, then the probability that the key is the right key is 1, so key authentic degree will be 1 at that condition.
When the length of ciphertext greatly exceeds the unicity distance of some kind of encoding of the corresponding language, statistically there is no spurious key, then the key holder has to surrender the real key and the key authentic degree will be 1. It is easy to obtain the corresponding length ciphertext in reality. For example, for a message with a 56 bit key and represented with ASCII characters, the unicity distance of DES are about 8.2 ASCII characters(about 66 bits)[5]. For the ciphertext less than the unicity distance, it was pointed out that the approximate number of spurious keys N should be averagely 2H(k)-nD-1 according to the corresponding redundancy of language[6,7]. We have pointed out that N would averagely be between 2H(k)-nD-1 and 2H(k)-nD, as the right key will exist for ever and its existence is almost not affected by the redundancy of language. In most cases, N would averagely be more near 2H(k)-nD. Here D is redundancy rate of language, H(k) is the entropy of cryptosystem, generally amounts to the length of the key. If N is equal or greater than 1, on average we can find out a right key and a spurious key at least. And then because of the infinite computing power, the key holder can figure out all the keys which can be used to obtain semantic meaning plaintexts. The key holder can rationally give a spurious key to the cryptanalyst. When there is a spurious key without flaw, the key authentic degree will be 0. What we discuss is an ideal situation, in reality the semantic meaning plaintext is also restricted by the background information and other conditions. Sometimes because of inconsistent factors or antilogy, the spurious key can be found out to have flaws and be excluded. Sometimes a meaningful plaintext is totally unrelated to the background information, the corresponding spurious key will be excluded, so the spurious key without flaw would be very few. In most cases, there is no spurious key without flaw and the key authentic degree will be 1. In fact the cryptanalysts are impossible to have infinite computing power, and they also impossibly allow the key holder to compute spurious key for a long time. Therefore the situation that the key authentic degree is 0 is purely ideal.
Secondly, considering practical conditions, for example the cryptanalysts generally know something about the communication, and the computing power is finite, and the key holder can beforehand figure out a spurious key to prevent being intimidated, under such conditions, the key authentic degree is related to the redundancy of the language encoding, the length of the ciphertext, the computational time, the number of the keys, the context of the communication and the complexity of the algorithm. Theoretically speaking, the spurious keys without flaws and match the communication context are few. There are two situations: 1)If the number of spurious keys which match the conditions is 0,and there is only one right key, well then the key authentic degree is 1,because the cryptanalyst cannot found out any flaws only when the key holder surrender the key. Because of finite computing power, the cryptanalysts may cannot decrypt and test the keys one by one to find out all the spurious keys and the real keys, then they can preliminarily estimate whether the number of spurious keys is 0 according to the unicity distance and the amount of background information, under these situations the key authentic degree is higher if the background information is more and the key authentic degree approximates 1. 2) If there are more than one spurious key without flaws and match the communication background, we need to estimate whether the key holder can find out effective spurious keys according to the computing power which the key holder can user. If the probability of finding out effective spurious keys is r, the key authentic degree is 1-r. Modern cryptosystem such as AES is designed based on many rounds of complex operations on the data, the design criteria of modern cryptosystem can ensure that the cryptosystem is secure under known plaintext attack and chosen plaintext attack, so it is computational infeasible to get keys for given plaintext-ciphertext pairs. If the key holder design a ‘plaintext’ to mislead the cryptanalysts, it is hard to get the corresponding spurious key even if the spurious key is existent. Therefore under these conditions, the key authentic degree is mostly 1.
Thirdly, if we cannot compute in reality, as long as the length of the ciphertext is not very short, all the key authentic degrees of general modern cryptosystems approximate 1. It is very difficult for almost all of modern cryptosystems to find out the spurious keys because of the complicated operations. So if the key holder doesn’t prepare a spurious key beforehand, once he is controlled under duress and the cryptanalyst don't allow the holder to compute, the key holder will have to surrender the real key.
According to the above analyses, we can find that for modern cryptosystems, if other conditions are the same, the more powerful the computing power, the more possible the spurious key is to be found out and the lower the key authentic degree. And the more background information the cryptanalyst holds, the higher the key authentic degree, even though the key holder cheats, it is easier to be found out and he will continue to be grilled. The longer the ciphertext is held, the higher the key authentic degree, and as long as the unicity distance is exceeded, then the key authentic degree will approximate or be 1. In fact the unicity distances of most modern cryptosystems are very short. For example, for 256-bit-key block cipher algorithm, the unicity distance of ASCII text encryption algorithm is only 37.6 characters, obviously it is easy to obtain the ciphertext with more than 37.6 characters, and because of the finite computing power, the restriction of background information and so on, the key authentic degree of modern cryptosystem under most conditions approximates 1. Thus it can be seen, for modern cryptosystems, the key authentic degree generally reaches the upper limit 1, and this brings very great hidden theat.

4. The feasibility analysis of algorithm with low key authentic degree
The above researches indicate that the key authentic degree of modern cryptosystem is very high. But whether it really cannot be lowered? In fact it is possible. As is mentioned above, the approximate number of spurious keys N should be gained by
N=2H(k)-nD-1
From this formula we can know that if we want to increase the number of spurious keys, H(k) must increases with the increase of n, which means the length of the key will increase. One-time system in classical cryptography is such a cryptosystem. In one-time system, if we casually give a plaintext with a same length as the ciphertext (the real plaintext), then we can get a corresponding spurious key according to the XOR operation of the plaintext and the ciphertext. The question in one-time system is that the key and the ciphertext are of the same length, and the increase of the length of keys is mostly unpractical, unless QKD (Quantum Key Distribution) is used.
Whether there are any other methods to reduce the key authentic degree? The lack of spurious keys is because of the redundancy of languages, and we can reduce redundancies by many ways, for example, data compression can reduces data redundancies and increases the number of spurious keys, but modern cryptography cannot provide effective methods to find out spurious keys. Furthermore we can anew encode all possible messages, for example, we can sequentially encode all the messages with a fixed length binary number, but the workload of encoding is heavy and it is very unpractical.
The redundancy of languages has to do with lingual characteristics such as grammar, so we hopefully realize low key authentic degree algorithms from this aspect. Tremendous developments of modern natural language processing are also helpful for corresponding encryptions and decryptions. But because of the complexity of natural language, some measures should be taken to ensure reliable decryption of ciphertext.
We designed a cryptosystem with low key authentic degree via an extension method like multiple-choice. The cryptosystem with low key authentic degree can effectively solve the above problems, and the plaintext obtained from the spurious key entirely accords with the communication background. These plaintexts we obtain perhaps are opposite or similar to primary meanings, and such spurious keys are easier to believe compared with general spurious keys. Because of the need of low key authentic degree, our algorithm is comparatively complex and the encryption progress is also more complex than traditional encryption. When encrypting with our method, we fill in the keywords in original texts, for example, for "sunny", we can append "cloudy", "rainy" and so on to extend, and mark them according to the key to ensure the recovery. The original right plaintext is "Today is Sunday ", but the ciphertext may be decrypted as "Tomorrow is Monday" using a wrong key, and this will misguide the cryptanalysts. This kind of algorithms has limitations, and they can be used in conjunction with traditional cryptosystems.

5. Conclusions
In this paper, we expatiated on the origin and concepts of the key authentic degree of cryptosystem, pointed out the significance of the research of key authentic degree, analyzed the key authentic degree under different conditions in modern cryptosystems, and pointed out that the key authentic degree is high in most practical situations, this means that the modern cryptosystems can be intimidated by rubber-hose attacks. We also analyzed the feasibility of the cryptosystems with low key authentic degree, and illustrated it with several examples. The cryptosystems with low key authentic degree are not only used when one is intimidating, but also can be used to mislead the cryptanalysts or attackers, and we can consciously use spurious keys to misguide the cryptanalysts who attempt to obtain sensitive messages. Of course the similar algorithms are not only used for encryption but also can be effectively applied in special situations such as steganographic method and so on. As a new research field, more cryptosystems of low authentic degree and more applications remain to be found out, and the limitations of these algorithms also remain to be found out and improved.

References
[1]. Bruce Schneier,Applied Cryptography Second Edition: protocols, algorithms, and source code in C,John Wiley &Sons, Inc,1996
[2]. C.E. Shannon, Communication theory of secrecy systems, Bell System Technical journal, v.28, n.4, 1949, 656-715.
[3]. Yong Wang,Study of Some Problems of Quantum Cryptography and Theoretical Security of Cryptosystem [D],Southwest Jiaotong University,2005(in Chinese)
[4]. Dengguo Feng. Cryptanalysis. Beijing: Tsinghua University Publishing House, 2000(in Chinese)
[5]. C. A. Deavours. Unicity points In cryptanalysis," Cryptologta v.1, n.1, 1977, 46-68
[6]. M. E. Hellman, An extension of the Shannon theory approach to cryptography, Information Theory, IEEE Transactions on, May 1977, Volume: 23, Issue: 3: 289- 294
[7]. Beauchemin P, Brassard G A, Generalization of Hellman s extension to Shannon s approach to cryptography , Journal of Cryptology; 1988


wangyongSeptember 27, 2009 1:10 AM

A Cryptosystem of Low Key Authentic Degree



Abstract—This paper analyzes the meaning and significance of key authentic degree of cryptosystem under the threat of the rubber-hose attack and ciphertext only attack. A novel cryptosystem of low key authentic degree is designed. The inner encryption is an extension like multiple-choice questions with keywords similar and contrary to the keywords in the plaintext. The corresponding decryption is like doing multiple-choice questions and the answers are decided by key. It is easy to find pseudokeys of the cryptosystem that can confuse and mislead cryptanalysts.
Keywords- rubber-hose attack; cryptography; language; pseudokey
I. INTRODUCTION
The present cryptosystems are mostly of computational security. The pseudokeys are few, and it is hard to find pseudokeys. Rubber-hose attack is a kind of attack without technique, but it is very effectual. The cryptanalysts obtain the key via threatening, extorting or afflicting the key holder until he gives it out. It is very effective and is often the best approach of breaking a cipher [1]. The holder has to give the key to someone who want the key not only for being controlled, but also sometimes for fear of hurting somebody's feelings, even for being stressed by power or interests. If the key he gives is not the right key, as the characteristic of modern cryptosystem, it can mostly be found to be false key for the plaintext decrypted from the key is mostly not meaningful. In the limited time, it is hard to find pseudokeys, According to Shannon's theories, when the length of the keys are fixed, the amount of the pseudokeys will gradually decrease along with the increase of the ciphertext length [2]. The modern cryptographic algorithms are all based on the keys of fixed length, the amount of the pseudokeys will be decreased along with the increase of the ciphertexts, and the authentic plaintexts decrypted from the pseudokeys may be eliminated because possibly they entirely don't correlate with the communication background at that time, so the pseudokeys that can be trusted by the cryptanalysts are very few. The most modern cryptographic algorithms use bits or chars of the data as the computational unit, and after complicated computation, the pseudokeys are difficult to find out even though they are existent. This means that in the condition of modern cryptographic algorithms, if a key holder randomly offers a key when facing the rubber-hose attack, obviously the cryptanalyst can easily find that the key is wrong, because the plaintext can be found to have no semantic meaning in most situations. If the key holder cannot withstand the rubber-hose attack, finally he will have to surrender and provide the real key. Because of these reasons, designing encryption algorithms whose pseudokeys can be easily found out is very significative, especially in military fields. The concept of the key authentic degree was proposed in [3]. The key authentic degree of cryptosystem means the difficulty of finding out the pseudokeys which we can decrypt to obtain semantic meaning plaintexts without flaws under a certain conditions. Essentially it is used to weigh the degree of the trustworthiness of the key provided by a key holder who is intimidated but not willing to leak the plaintext under the condition that the ciphertext and the algorithm are known by cryptanalysts, assuming that the key holder tries his best to provider a pseudokey without flaws to misguide people who intimidate him. The key authentic degree is high if the pseudokeys of the cryptographic algorithms are hard to find out. The reason why we named it as authentic degree is that we can judge the correctness of the key by using the key to decrypt ciphertext and finding out whether the corresponding plaintext has semantic meaning if the algorithm whose pseudokeys are hard to find. If what we get is not a real key, the plaintext decrypted from the key is mostly meaningless code. On the contrary, if the plaintext has semantic meaning, the key is the right key in most cases. Under ciphertext only attack, the existence of pseudokeys can ensure the cryptanalyst does not know which the right key is and then which the right plaintext is. As the growth of computational power, the ciphertext only attack to modern cryptosystem may be realized one day. We gave an idea to make the cryptosystem easy to find pseudokeys by extension method like multiple-choice [4]. In this paper, we will implement a cryptosystem using the idea.
II. ENCRYPTION METHOD
The method is similar with doing multiple-choices questions: we should build a database of keywords, every keyword is grouped with the keywords which are homoionyms or antonyms of this keyword, for instance, sunny is grouped with rainy and snowy, today is grouped with tomorrow and yesterday. Just like doing the multiple-choices questions. When encrypting, the keywords are replaced by an extend item, for example, keyword 'rainy' is replaced by an extend item '[(a) sunny (b) rainy (c) snowy]', here symbol '['and']' express the beginning and the end of an



Figure 1. Flow chart of encryption


extend item, symbol '('and')' express the beginning and the end of a number of every keyword. In real encryption, these symbols should be replaced by symbols that do not appear in the text of plaintext files so that decryption is feasible and exclusive. The numbers used to sign keywords are consecutive integers from 0 to n-1 like "abcd" in the multiple-choices questions which can ensure the information is secretive and we can get different plaintexts when using different keys to decrypt, here n is the number of keywords in one group.
Because this method processes the keywords of the text content of the plaintext file but not the file, so the step should include opening the document (or file), the process is as figure 1: the system firstly opens a word or text document, reads its text content of the document, then extends the keyword, and saves the file at last.
In this paper we do not focus on the opening, reading and saving the file. We just consider the part of extending keyword of the text content. The processes of this part are listed as follows:
The cryptosystem scans the text read from the file and finds out the keyword in the text one by one according to the keywords database. If a word is a keyword in the keywords database then cryptosystem read the number ‘n’ of the corresponding group of the keyword in the database which is the number of the keywords of the group and ‘a’ which is the serial number of this keyword in the corresponding group in the database. The keyword will be replaced by an extension item which is made up by a series of symbols, keywords in the group and their corresponding numbers. The numbers of the keywords are determined by the secret key, the number of the keywords of the group and the original numbers in the database. If the receiver and sender have shared a secret key k, and the largest number of keywords is not larger than 2m,then we orderly choose m bit digits in stream cipher sequence which is generated by the stream cipher algorithm and the secret key when finding a keyword. Suppose at the s time, the value we transfer the corresponding m bits of the stream cipher sequence to decimal digits is ds, the number of the keyword K in the corresponding group in the extension item is gained by the following formula:
b=(-a+o+ds)mod n
Here a is the original number of the keyword in the plaintext in the group, o is the original number of the keyword K in the group.
When decrypting, the cryptosystem find the extension item in the text, and compute:
e=ds mod n
and find the keyword in the extension item whose number is e, then replace the extension item with the keyword.
Because of the same key, the reciever and sender will get the same stream cipher sequence if they adopt same stream cipher algorithm, for code sequence value correspondingly in the s time ds.
e=ds mod n =(-a+o+ds)mod n
so a=o, then the keyword is the right keyword in the plaintext.
The purpose of adopting stream cipher algorithm is to avoid attacks using plaintext and ciphertext pairs to find keys. Although adopting modular arithmetic in number computation process, stream cipher algorithm can efficiently prevent potential attack.
III. OUTER ENCRYTION
The above method is not secure enough for some conditions. Sometimes the discernment of the system may be deficient, some word that is not replaced may disclose information. To get better security, we can use modern cryptosystem to encrypt the file, so in the whole encryption process, the cryptosystem should firstly open the file, then read the text of the file, do inner encryption(replacing keywords of the text), save the file and finally do the outer encryption. The decryption process is reversed. The above process can ensure security under different conditions. When encountering rubber-hose attack, the key holder can give pseudokey to the cryptanalyst. When encountering technical attack, the outer encryption can keep secret.
IV. GETTING PSEUDOKEY
In this cryptosystem, there are two keys to encrypt and decrypt. The key of the outer encryption should be unchanged. The key of the inner encryption is random under perfect conditions. But due to the complexity of language, sometimes system may misjudge keyword and the some key of the inner encryption may get plaintext that is meaningless, so we can get pseudokey by trying several times. When controlled, the key holder can give the same key of the outer encryption and give a key of the inner encryption that can get meaningful plaintext. If the cryptanalyst do not know the key is not right, he may be misled, otherwise, he can not believe whether the key is right, so he confuses whether the plaintext decrypted from the key is the right one.
V. CONCLUSIONS
We design a novel cryptosystem. The character of this cryptosystem is that pseudokeys can be easily found, and the meaning of decrypted plaintexts using pseudokeys may be similar to or opposite to that of the right plaintext, thus it is easy to mislead the attacker. While traditional cryptographical algorithm is hard to find pseudokeys when it comes to rubber-hose attack. This cryptosystem is a very simple model. Using this method, we can design many similar cryptosystems that can enhance the performance of the system, such as compressing the length of ciphertext, judging the keyword by rule and line. The cryptosystem is realized by Delphi and it is easy to find pseudokeys. The cryptosystem is slower than modern cryptosystems. It is suitable to be used in the case of high confidentiality and military affairs.
REFERENCES
[1] Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code in C, John Wiley &Sons, Inc, 1996.
[2] C.E. Shannon, Communication theory of secrecy systems, Bell System Technical journal, 1949, 28(4), pp. 656-715.
[3] Yong Wang, Study of Some Problems of Quantum Cryptography and Theoretical Security of Cryptosystem, Southwest Jiaotong University, 2005.
[4] Yong WANG, Security of One-time System and New Secure System, Netinfo Security, 2004, 7, pp. 41-43.

any comments and criticisms would be more than welcome

Clive RobinsonSeptember 27, 2009 3:39 AM

@ wangyong,

"any comments and criticisms would be more than welcome"

The idea of expanding one space to give greater uncertanty in another space is not new.

One common system using this idea is Spread Spectrum systems.

This in turn gave rise to the ideas behind Digital Watermarking.

There are a number of ways that you can get the required level of uncertainty but the big issue with natural language is it's iregularity of size.

Several hundred years ago this problem was adressed with code books where words were replaced with numbers of a uniform size. The uniform numbers where then super encrypted.

It can be seen that to maximise the effect you are looking for the "block size" of the encryption should be as small as is reasonably feasable which usually is a single bit.

You then expand either the key space or message space or both in such a way that you increase the number of possible message solutions.

This is usually considered an undesirable method simply because it decreases the utility of the communications channel (unless as is the case of Spread Spectrum you gain other advantages).

Further such systems as you note have to have meaningfull solutions for each key, this has the consiquence of making the system sensitive to the plaintext statistics which is again considered to be too constrained for general use.

That asside you then have the issue of key managment to deal with.

It is in this area that direct rubber hose techneiques become impractical simply because the human mind cannot deal store the amount of key material reliably.

Which means all the meaningfull message keys have to be "written down" and some reliable method used to determin which is the valid key.

It is this area the analysts would devote their attention to and use as leverage against an individual.

wangyongOctober 6, 2009 4:03 AM

Steganographic Method Based on )
Abstract
By borrowing ideas from a cryptographic algorithm of low key authentic degree, a novel steganographic method based on keyword shift is presented. The master key of the method is to shift the sensitive keywords in the text. The conditions to guarantee the reversibility of the method are analyzed and found out, the serviceability of the method in some situations is pointed out. The strong points and weak points of the method are analyzed.
Keywords: steganography; rubber-hose; digital signature; subliminal channel; information hiding

1. Introduction
Steganography is a technology and science about information hiding, which can ensures any unauthorized receivers cannot discover the secret message except the authorized receiver. Nowadays information hiding technology mainly depends on large capacitance files such as images, audio files, videos files [1]. Another special information hiding technology is subliminal channel proposed by Simmons in 1983, in a narrow sense the subliminal channel is using digital signature to realize the information hiding [2], nevertheless subliminal channel can be sealed, and meanwhile the subliminal information using the digital signature is often very short. It is obvious that information hiding either depends on large files as carrier or merely transfers short messages. Covertext is very larger than stegotext, the utilize efficiency is low. Once large files and digital signature are forbidden to be sent, the information hiding of the secret can not be realized whereas information hiding and subliminal channel problems are always aiming at the prisoner problem, supervisor can forbid any transmission that may hide secret information absolutely. This paper proposes a new kind of steganography by borrowing ideas from a cryptographic algorithm of low key authentic degree.

2. Principle of the keywords shift steganography
We have designed a cryptographic agorithm against rubber-hose attack which adopted a method similar with doing multiple-choices questions [3]: this method has a database of keywords, every keyword is grouped with the keywords which are homoionyms or antonyms of this keyword , for instance, sunny is grouped with rainy and snowy, today is grouped with tomorrow and yesteday. Just like doing the multiple-choices questions, when encrypting, the keywords are replaced by an extend item, for example, keyword ‘rainy’ is replaced by an extend item ‘[(a)sunny (b)rainy (c) snowy]’, here symbol ‘[‘ and ‘] ‘ express the beginning and the end of an extend item, symbol ‘(‘ and ‘)’ express the the beginning and the end of a number of every keyword. In real encryption, these symbols should not appear in the text of plaintext files so that decryption is feasible and exclusive. The numbers used to sign keywords are consecutive integers from 0 to n-1 like “abcd” in the multiple-choices questions which can ensure the information is secretive and we can get different plaintexts when using different keys to decrypt, here n is the number of keywords in one group.
The character of this algorithm is that pseudokeys can be easily found, and the meaning of decrypted plaintexts using pseudokeys may be similar to or oppisite to that of the right plaintext, thus it is easy to mislead the attacher. While traditional cryptographical algorithm is hard to find pseudokeys, when it comes to rubber-hose attack, there is defect in traditional cryptographical algorithm. If the key holder gives a key using which attacher can decrypt and get a meaningful text, then the attacker may believe that the key is right. This traditional algorithm has high authentic degree, contrarily the previous algorithm can easily find pseudokeys, so the authentic degree of the key of the algorithm is low[4].
We use similar method to hide information. Unlike encryption, steganography should be disguised as ordinary unencrypted communication, so the extend item cannot appear in the covertext and the covertext should like normal text. Therefore in steganographic method the sensitive keywords should be directly replaced by other keywords. When hiding, sensitive keywords are identified, according to key that receiver and sender shared and the initial number of the keyword in database we can compute another covertext number, then this number is used to ascertain which keyword should replace the sensitive keyword correspondingly. In the example above, “today is sunny” may be shifted to “tomorrow is sunny”, which has a misapprehend meaning.

3. Design of the steganographic method based on keywords shift
For this method shift the keyword of the text content of the stegotext file but not the file, then the step should include opening the document(or file), for example opening a word or text document, reading its text content of the document, then shift the keyword, saving the file at last.


1. flow chart of steganographic method

In this paper we do not focus on the opening, reading and saving the file. We just consider the part of shifting keyword of the text content. The processes of this part of the steganographic method are listed as follows:
The steganographic system scans the text read from the file and finds out the keyword in the text one by one according to the keywords database. If a word is a keyword in the keywords database then system reads the number ‘n’ of the corresponding group of the keyword in the database which is the number of the keywords of the group and ‘a’ which is the serial number of this keyword in the corresponding group in the database. The keyword will be replaced by another keyword in the group. Which keyword in this group will replace the original keyword is determined by the secret key. If the receiver and sender have shared a secret key k, we can use stream cipher algorithm to determine how to replace the keywords. If the largest number of keywords is not larger than 2m,then we orderly choose m bit digits in stream cipher sequence which is generated by the stream cipher algorithm and the secret key when finding a keyword. Suppose at the s time, the value we transfer the corresponding m bits of the stream cipher sequence to decimal digits is ds, the number of the keyword in the corresponding group which replaces No. s original keyword is gained by the following formula:
b=(a+ds)mod n.
In this way steganographic system finds the keywords which replace original keywords in stegotext and generates the covertext.
The extraction of stegotext is similar, the words are the same with covertext if they are not keywords, the keywords are replaced according to the secret key orderly. This process is opposet to the hiding process.
Because of the same key, the reciever and sender will get the same stream cipher sequence if they adopt same stream cipher algorithm, for code sequence value correspondingly in the s time ds , after querying keywords database we can find number b, then using a=(b-ds)mod n, after querying keywords database about number a, we will gain keyword correspondingly and extract stegotext.
In order to be synchronous, either in steganographic process or in extraction we compute and shift keywords according to the text orderly. The purpose of adopting stream cipher algorithm is to avoid attacks using stegotext and covertext to find keys. Although adopting modular arithmetic in number computation process, stream cipher algorithm can efficiently prevent potential attack[5].
4. Reversibility conditions of the steganographic method
In the above steganographic method if a keywords is contained by another, for example, in keyword database there are keyword ‘China’ and ‘People’s Republic of China’ or there is a multivocal keyword in two different groups, the reversibility is hard to guarantee because there maybe different extraction results. Considering these conditions we should improve the algorithm and restrict the keywords. In the algorithm we can stipulate that a keyword should appears in no more than one group and any keyword should not be contained by another.
Steganography is different from encryption in order to preserve no flaw of the disguised covertext. Ciphertext can be unmeaning, but covertext should have meaning. Therefore steganographic method should get rid of the symbols used in our cryptographic agorithm that can avoid different interpretations when decrypting for the symbols differentiate the shifted words and unshifted words availably. As steganographic method gets rid of the symbols, that cause the following problems: the shifted words and unshifted words in the covertext may make up a new keyword that may generate a stegotext different from the original stegotext when extracting from the covertext. Although this case rarely happens, the deep reason of this problem is intersection of keywords. If there is no intersection between keywords, this problem will be solved. To this problem there are some solutions: 1). As this case rarely happens so we do not need to give limitations about keywords that require there is no intersection between two keywords in the database. We send messages if extracted stegotext is the same with the original stegotext. If not, stegotext should be improved or abondoned. 2). Searching keywords in series to find if there are two or more result, for example if there is “ is not her” in the covertext, if both “is not” and “not her” are keywords in the database, then system gives two kinds of extract results. 3). Restrict keywords to avoid intersection. This solution is more efficient to english words, whereas in chinese this limitation may reduce the number of keywords greatly and effectiveness of the method. There are other methods by coding to ensure the reversibility of the method.
According to the method, in the covertext there are no complete keywords in unshifted paragraph, limitations we give above can make sure there are no intersections between any keywords. By the above methods, we efficiently avoid or solve the keywords intersection between unshifted paragraph and shifted part, so there are no misjudgement in other keywords and it can ensure the reversibility of our steganographic method.

5. Applications of the steganographic method
The steganographic method can be applied as subliminal channel, when two prisoners try to communicate with each other and do not want guards who can see the letters know the true meaning of the letter, then two prisoners could adopt steganographic method to shift keywords in their stegotext, then turnkey can only see the covertext whose meaning may be opposite or similar to the stegotext. That can mislead the turnkey.
This steganographic method is more suitable to encrypt communications or falsify communications between computers or systems. For example, in internet, according to network protocols and communication mechanisms, we can shift keywords such as URL, IP, commands, file names etc. The covertext also matches the mechanisms and protocols accordingly, so it can be processed availably and seems to be right. There are two uses for this: Firstly, this method can mislead the sniffer. Secondly, an attacker on the internet may falsify data using this steganographic method, and receiver is hard to find the data is changedand that lead to false operation of the computer or system.

6. conclusion
A steganographic algorithm based on keywords shift is proposed, which is is quite other than the conventional steganographic method. Compared with conventional steganographic method, this steganographic method has its strong and weak points. This method has a value of a wide range of applications. By using similar method we can design many relevant steganographic and cryptographic algorithms. This algorithm can be used in steganographic method and subliminal channel, also can be used as cryptographic method.

wangyongOctober 6, 2009 4:10 AM

to clive

most Spread Spectrum systems are hard to find "spurious key"
about Digital Watermarking.
see the paper above.


wangyongOctober 6, 2009 4:20 AM

to clive
thank you for your disccussion, it seems some spelling mistakes. you are right some places, but are inequitable some places. I have pointetiond out the limitations of my cryptosystems.
but they are one and only at some characters.not only rubber-hose attack, can be used to mislead.

key managment is limited, the key is always to be accessed by someone, or some persons and devices. If they are all controlled?

Matthew ElveyOctober 22, 2010 10:14 PM

Prelude: Please nuke the other 2010 comments; they're spam.

Comment: Surprised there's been no mention of a good (but still partial) solution to rubber-hose cryptanalysis: Advanced secret sharing (http://en.wikipedia.org/wiki/Secret_sharing). Even a naive secret sharing scheme is useful, e.g. when going through US gov't security. It's not hard to ask a few geeky friends to store and give back a string when I contact 'em if they verify it's me and I claim not to be under duress. Publishing and using a warrant canary helps.

Many years ago, I had a laptop with my PGP secret key on it. The laptop was obtained by an untrusted group and then recovered. (Specifically, it disappeared, and was reported 'recovered' by 'security' from a thief whose identity, suspiciously, was withheld from me.) I was surprised when I transferred the secret key to a still-trusted system, and found that my passphrase (as I recalled it, at least) did not work on the secret key. Definitely set off some warning bells.

PauliDecember 28, 2011 3:38 PM

Shouldn't it be obvious that rubber-hose mechanisms have already been, and will be, used? Today's cryptography is darn strong, but a chain is only as strong as its weakest link is.

This is obvious, and those that need to crack crypted data know it. If they don't hesitate torturing and it's easier than trying to crack the passwords, they will be beaten out of the people holding them for sure. As long as they can torture freely.

codeJanuary 5, 2013 11:29 PM

Well,
in the process of preparing an exam, I wonder...
Is thermo-rectal cryptanalysis considered a side-channel attack ?...

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..