Deniable Cryptography [was winnowing, chaffing etc]

mgraffam@mhv.net writes:

> I figure the best we can do is to hide the contents of S with crypto and
> hide its existence through other means. Traditional stego works well 
> for this latter goal, but it does not give us a way to cough up something
> meaningful in place of S, which could be very handy.
> 
> In short, certainly the existence of S needs to be hidden, and it would be
> best to do hide it in plain sight as it were, in a big junk pile with
> everything else on the drive. 
> 
> Indexing this huge mess of data to allow for a practical system to work
> with is certainly a challenge, and in all likelyhood impossible given the
> parameters of the system.
> 

Marutukku (my rubber-hose proof filing system) addresses most of these
technical issues, but I'd like to just comment on the best strategy
game-theory wise, of the person wielding the rubber-hose.

In Marutukku the number of encrypted extents (deniable "virtual"
partitions) defaults to 16 (although is theoretically unlimited). As
soon as you get over about 4 pass-phrases, the excuse "I can't recall"
or "there's nothing else there" starts to sounding highly plauseable.

Ordinarily best strategy for the rubber-hose wielder is to keep on
beating keys out of (let us say, Alice) indefinitely till there are no
keys left. However, and importantly, in Marutukku, *Alice* can never
prove that she has handed over the last key. As Alice hands over more
and more keys, her attackers can make observations like "the keys
Alice has divulged correspond to 85% of the bits". However at no point
can her attackers prove that the remaining 15% isn't simply
unallocated space, and at no point can Alice, even if she wants to,
divulge keys to 100% of the bits, in order to get the un-divulged
portion down to 0%. An obvious point to make here is that
fraction-of-total-data divulged is essentially meaningless, and both
parties know it - the launch code extent may only take up .01% of the
total bit-space.

What I find interesting, is how this constraint on Alice's behaviour
actually protects her from revealing her own keys, because each party,
at the outset can make the following observations:

Rubber-hose-squad: We will never be able to show that Alice has
		   revealed the last of her keys. Further, even if
		   Alice has co-operated fully and has revealed all of
		   her keys, she will not be able to prove it.
		   Therefor, we must assume that at every stage that
		   Alice has kept secret information from us, and
		   continue to beat her, even though she may have
		   revealed the last of her keys. But the whole time
		   we will feel uneasy about this because Alice may
		   have co-operated fully. Alice will have realised this
		   though, and so presumably it's going to be very hard
		   to get keys out of her at all.


Alice:		   (Having realised the above) I can never prove that I
		   have revealed the last of my keys. In the end I'm
		   bound for continued beating, even if I can buy
		   brief respites by coughing up keys from time to
		   time. Therefor, it would be foolish to divulge my
		   most sensitive keys, because (a) I'll be that much
		   closer to the stage where I have nothing left to
		   divulge at all (it's interesting to note that this
		   seemingly illogical, yet entirely valid argument of
		   Alice's can protect the most sensitive of Alice's
		   keys the "whole way though", like a form
		   mathematical induction), and (b) the taste of truly
		   secret information will only serve to make my
		   aggressors come to the view that there is even
		   higher quality information yet to come, re-doubling
		   their beating efforts to get at it, even if I have
		   revealed all. Therefor, my best strategy would be
		   to (a) reveal no keys at all or (b) depending on
		   the nature of the aggressors, and the psychology of
		   the situation, very slowly reveal my "duress" and
		   other low-sensitivity keys.

Alice certainly isn't in for a very nice time of it (although she
she's far more likely to protect her data).

On the individual level, you would have to question whether you might
want to be able to prove that, yes, infact you really have surrendered
the last remaining key, at the cost of a far greater likelihood that
you will. It really depends on the nature of your opponents.  Are they
intelligent enough understand the deniable spect of the cryptosystem
and come up with the above strategy? Determined to the extent they
are will to invest the time and effort in wresting the last key out of
you? Ruthless - do they say "Please", hand you a Court Order, or is it
more of a Room 101 affair?

But there's more to the story.

Organisations and groups may have quite different goals in terms of
key retention vs torture relief to the individuals that comprise them,
even if their views are otherwise co-aligned. I'm not talking about
some mega-complex multinational 8 level hierarchy. A simple democratic
union of two or more people will exhibit this behaviour.

When a member of a group, who uses conventional cryptography to
protect group secrets is rubber-hosed, they have two choices (1)
defecting (by divulging keys) in order to save themselves, at the cost
of selling the other individuals in the group down the river or (2)
staying loyal, protecting the group and in the process subjugating
themselves continued torture.

With Marutukku-style deniable cryptography, the benefits to the
individual derived from choosing tactic (1) are largely
eliminated. Individuals that are "otherwise loyal" to the group, will
realise this and choose tactic (2).

Presumably most people in the group do not want to be forced to give
up their ability to choose defection. On the other hand, no one in the
group wants anyone (other than themselves) in the group to be given
the option of defecting against the group (and thus
themselves). Provided no individual is certain* they are to be
rubber-hosed, every individual will support the adoption of a
group-wide Marutukku-style cryptographically deniable crypto-system.

* Actually a complicated threshold.

Cheers,
Julian

On Sat, Mar 28, 1998 at 05:53:36PM -0500, mgraffam@mhv.net wrote:

> I've never really fully understood this assumption. It seems to me
> that any person or group that would beat a person isn't going to
> care much if Alice cooperated or not. 
> 
> All things considered, a group with enough power to grab Alice and
> beat her probably has ways to escape punishment from the law, or
> doesn't care about the law in the first place. 

Generally speaking, you bind attackers with constants (or else, most of the
cryptography we are using is pretty much useless). Why won't you bind
physical attackers with constants just as well?

The longer you are kept alive, the higher the chance you'll be released, be
it because your attackers run out of resources, suddenly feel guilty, find
out the information some other way or being caught by law enforcement (or
your friendly rebel group).
If your attackers can prove they've gotten all they need from you during the
first week, you might be killed or released (this might be a political
issue, at times. Prisoners of war will generally be kept alive, for various
purposes, such as gaining some more when an agreement is signed).
If they can't, they are bound to beat you, or try various other methods -
but they won't kill you right away. This is a good thing, for most people
(others might wish to end the torture, even by being killed, but they can't
do that. Tough luck).

True, if you are kidnaped by a very large organization, like a country, you
don't stand a chance - you will either give up your secrets, and/or die 
(history generally tells us that people can't stand torture. The exceptions
are remarkable, and probably indicate a certain level of mental illness,
before or after the act <g>). Smaller organizations are bound by constants
that might eventually be in your benefit.

> down and gave them her most important secrets. Even if she can't prove
> it.. so what? The rubber-hose group isn't exactly the boy scouts. They
> beat her the next day too, this time a little harder.

Excluding external influences, if the group isn't presenting any rewards,
every logical system against them is quite useless. It doesn't matter whether
you tell the secret or avoid telling it - it makes no difference. A function
with no parameters, and hence a constant outcome.

That's why I consider dynamic secret sharing a better approach.
Make certain the attackers need to catch a group of people in order
to gain the secret, and change the partial secrets every short period of time.
This isn't always practical, of course.

> So, the only way for Alice to win is to do the impossible (because this
> is reality, not TV) and that is to grab the rubber hose and beat them
> with it.

(Alice can always fascinate her attackers with a new and exciting
cryptosystem, and while they are busy studying it, sneak behind and hit
them on the heads with a selected cryptography oriented book).

                                                   Nimrod

On Mon, 30 Mar 1998, Nimrod Zimerman wrote:
> Generally speaking, you bind attackers with constants (or else, most of the
> cryptography we are using is pretty much useless). Why won't you bind
> physical attackers with constants just as well?

True, we impose limits on our hypothetical attackers. Eve can listen, but
not modify.. but we assume Mallory has the ability to do both. 
Systems that are safe against Eve are exploitable by Mallory. I see
no reason why we can not also assume more powerful physical attackers.

I do not deny the use of deniable crypto :) .. it is useful against
certain attackers. Certainly it is useful against the majority of
attackers we are likely to encounter, for the dexact reasons that you
site.

However, my point is that just as public key exchange is attackable
by Mallory in some circumstances, deniable crypto is useless against
certain physical attackers.. namely O'Brian and room 101.

This is not to say that public key crypto or deniable crypto is useless.

> True, if you are kidnaped by a very large organization, like a country, you
> don't stand a chance - you will either give up your secrets, and/or die 
> (history generally tells us that people can't stand torture. The exceptions
> are remarkable, and probably indicate a certain level of mental illness,
> before or after the act <g>). Smaller organizations are bound by constants
> that might eventually be in your benefit.

This is exactly my point. For the average guy in America, deniable crypto
is probably irrelevent (unless he happens to be an average criminal too).
But in a state where the law is wrong (we never heard of anything like
that,  have we?) there is probably a use.

> That's why I consider dynamic secret sharing a better approach.
> Make certain the attackers need to catch a group of people in order
> to gain the secret, and change the partial secrets every short period of time.
> This isn't always practical, of course.

Yeah, I agree. For some secrets it might be the best approach, say for
the codes to launch a nuclear weapon.. but for others it probably does
not work.

> (Alice can always fascinate her attackers with a new and exciting
> cryptosystem, and while they are busy studying it, sneak behind and hit
> them on the heads with a selected cryptography oriented book).
> 
>                                                    Nimrod

Hehe.. :) I like that.

Michael J. Graffam (mgraffam@mhv.net)
http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc
"Act only according to that maxim by which you can at the same time will that
it should become a universal law.." - Immanuel Kant "Metaphysics of Morals"

-----BEGIN PGP SIGNED MESSAGE-----

On 28 Mar 1998, Julian Assange wrote:
> Rubber-hose-squad: We will never be able to show that Alice has
> 		   revealed the last of her keys. Further, even if
> 		   Alice has co-operated fully and has revealed all of
> 		   her keys, she will not be able to prove it.
> 		   Therefor, we must assume that at every stage that
> 		   Alice has kept secret information from us, and
> 		   continue to beat her, even though she may have
> 		   revealed the last of her keys. But the whole time
> 		   we will feel uneasy about this because Alice may
> 		   have co-operated fully.

I've never really fully understood this assumption. It seems to me
that any person or group that would beat a person isn't going to
care much if Alice cooperated or not. 

All things considered, a group with enough power to grab Alice and
beat her probably has ways to escape punishment from the law, or
doesn't care about the law in the first place. 

In this case, I figure that their best option is to beat Alice everyday
forever or until she dies. Whichever comes first.

The longer they beat her, the better chance there is that she broke
down and gave them her most important secrets. Even if she can't prove
it.. so what? The rubber-hose group isn't exactly the boy scouts. They
beat her the next day too, this time a little harder.

Alice may hold up, she may not.. I don't really see the cryptosystem
helping here. You can't win a game when the other player doesn't use
your rules. You have to use the same set of rules. We know that
the rubber-hose wielding guys aren't going to play by Alice's rules.
So, the only way for Alice to win is to do the impossible (because this
is reality, not TV) and that is to grab the rubber hose and beat them
with it.

I don't think that any crypto can defend this sort of attack, because
it has nothing to do with crypto. Consider even a one-time pad. Alice
could calculate the needed pads that would turn her ciphertext into
other meaningful plaintext messages. So they beat her. She gives them
a pad.. and they beat her again. It won't end. They can never know
if they got the "right" pad. But it doesn't really matter, does it?

In my opinion deniable encryption is only valuable against a more or
less civil entity. 

Now, what might be useful is some sort of biometric info that is part
of the key material. Heart rate, brain wave patterns, maybe biochemical
information. As Alice gets beat the fluctuations in her body could make
it impossible for her to reveal the information. A sensitive enough
system might even stand up against stuff like intimidation and
nervousness.. a polygraph test can supposedly detect this.

If such a system were implemented, then this could render rubber-hose
cryptanalysis useless, or at least much harder to put into effect.

Michael J. Graffam (mgraffam@mhv.net)
http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc
Let your life be a counter-friction to stop the machine.
				Henry David Thoreau "Civil Disobedience"


-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv

iQCVAwUBNR1/dgKEiLNUxnAfAQF5vwP+Mfykp2hNTgItZpgq5GXPoPwQl0enJv40
C+q43NSvaOzO3t+DAjfJj2IJuqDKXRy5FZikkCvOvr1cadJMbhqliKIrOHC1fkeB
ElDnx+7LxzlGsgieAxGFI8JvEB685VY8qsprYFzfI2hQitvztPccpQE/Xvr0ftZi
3meDBzVLq8A=
=0bdE
-----END PGP SIGNATURE-----

mgraffam@mhv.net writes:
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> On 28 Mar 1998, Julian Assange wrote:
> > Rubber-hose-squad: We will never be able to show that Alice has
> >                  revealed the last of her keys. Further, even if
> >                  Alice has co-operated fully and has revealed all of
> >                  her keys, she will not be able to prove it.
> >                  Therefor, we must assume that at every stage that
> >                  Alice has kept secret information from us, and
> >                  continue to beat her, even though she may have
> >                  revealed the last of her keys. But the whole time
> >                  we will feel uneasy about this because Alice may
> >                  have co-operated fully.
> 
> I've never really fully understood this assumption. It seems to me
> that any person or group that would beat a person isn't going to
> care much if Alice cooperated or not. 
> 
> All things considered, a group with enough power to grab Alice and
> beat her probably has ways to escape punishment from the law, or
> doesn't care about the law in the first place. 
> 
> In this case, I figure that their best option is to beat Alice everyday
> forever or until she dies. Whichever comes first.

"Rubber hose" cryptanalysis needn't involve actual beatings in secret
underground cells. Simple example: Cops raid your house, rough you up
a little bit (not much) and toss your ass in a cell with "real '
criminals. 12 hours later they take you into a room and play good
cop/bad cop with you. Maybe you're not sure you could stand up to
this, and might panic and reveal more than you have to (remember, you
haven't been charged with a crime yet). However, if you do hold out,
the chances that you'll be let go, and get your stuff back in a few
years, are pretty high. In this case, being able to spill a key that
revelas harmless stuff is good, since the police are unlekely to hold
you for a long time.

"Dissapearing" is the regressive case, and there's not a whole lot you
can do in regressive cases. If someone really wants to defect, they
will.

Jer

"standing on top of the world/ never knew how you never could/ never knew
 why you never could live/ innocent life that everyone did" -Wormhole

On Mon, 30 Mar 1998, Jeremiah Blatz wrote:
> "Rubber hose" cryptanalysis needn't involve actual beatings in secret
> underground cells. Simple example: Cops raid your house, rough you up
> a little bit (not much) and toss your ass in a cell with "real '
> criminals. 12 hours later they take you into a room and play good
> cop/bad cop with you. Maybe you're not sure you could stand up to
> this, and might panic and reveal more than you have to (remember, you
> haven't been charged with a crime yet). However, if you do hold out,
> the chances that you'll be let go, and get your stuff back in a few
> years, are pretty high. In this case, being able to spill a key that
> revelas harmless stuff is good, since the police are unlekely to hold
> you for a long time.

Absolutably. I understand that deniabled crypto will help against
a civilized enemy, but it is not an answer for the worst case scenario.

I maintain that algorithms aren't what we really need for this type
of key management. It is nice to be able to give up less important
keys as a matter of convienence, but as long as the user can get
the data so can an attacker.

If we have a physical system that gets key information from the user
through biological feedback that takes stress conditions, blood
pressure, etc into account then if any of these signs are out of the
norm the device can generate bad key information as a result of
this. This insures that the user will not be able to get the information
if he is being physically manipulated. This also has use in areas where we
dont want the user to be authenticated when he is in an odd
state of mind, such as when dealing with weapons systems.

I dont think that biofeedback technology is at the point to make this
usable yet, but I hope that advances are made quickly. The firearms
maker Colt has explored authentication devices for their weapons,
but I dont know the details.

Michael J. Graffam (mgraffam@mhv.net)
http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc
"..subordination of one sex to the other is wrong in itself, and now
one of the chief hindrances to human improvement.." John Stuart Mill
"The Subjection of Women"