Key Coercion after encrypted message transmission.

81 views
Skip to first unread message

7CF5...@nowhere.pa.dec.com

unread,
Aug 9, 1994, 1:33:18 AM8/9/94
to

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

There seems to be much written about key coercion lately. It seems to
me that the key coercion problem can be divided into two
problems. First, there is the problem of Princess Leia storing data on
her computer disk for later reference. Then Darth Vadder seizes the
disk and the Princess and coerces the Princess for the encryption
key. This problem may be called the static storage coercion problem
(SSCP). I am not sure that there is a good way of addressing this
problem short of dividing the key in some way among multiple people so
that Darth has a hard time seizing them all. This idea has already
been discussed elsewhere.

The second problem is the case where the Princess wants to send a
secret message to Hans Solo in the horsehead nebula. She sends the
message encrypted to Hans, but the encrypted message is intercepted by
Darth. Hans decrypts the message, but unfortunately six months later
Hans is captured by Darth who tortures him for the decryption key.
Note the Hans is in a worse position than if he were tortured for the
content of the message, because if he were merely asked the contents
of the message with no way to verify, he could simply lie. But Darth
can verify if any keys that Hans gives really does decrypt the
intercepted cipper-text to a sensible message. This problem could be
called the transmission retroactive coercion problem (TRCP). Unlike
the static storage coercion problem, the transmission retroactive
coercion problem does have a technical solution.

If Hans and the Princess were using a public key encryption system
that stores secret keys on disk as a conventionally encrypted file,
like PGP, then Hans could create a separate key pair for each message.
Hans has one long term public/secret key pair which never changes. He
could send temporary public keys in advance to the Princess as a
signed (using his long term public key) message. Then when the
Princess needs to send him a message she chooses one stored temporary
public keys and sends Hans the message using that key. She then throws
the key away and never uses it again. When Hans receives and decrypts
the message, he destroys the secret key stored on disk by overwriting
it. Then when Darth goes to torture Hans six months later for the
secret key, Hans can only tell him the passphrase for the now
non-existent key.

People can use this protocol right now with PGP to protect themselves
against this kind of retroactive coercion. It will work. However, the
problem of manually generating the keys and sending them to the other
party and the whole bureaucratic hassle of keeping track of everything
makes it unlikely that anyone would actually do so.

Software to the rescue! Suppose that Hans runs a mail server on his
account which recognizes certain messages as requests for new public
keys and responds by sending back unused temporary public keys to the
requester. It could work similarly to some cypherpunk remailers which
look for some special characteristic in the message to be responded
to, letting the rest pass normally to the owner of the account. The
Princess could also have a mail server on her account which looks for
returned temporary public keys and automatically stores them in her
database after checking for the correct signature without bothering
her. Further, whenever she sends a message, a program could check her
database of unused temporary keys, and if it is low, a request for
more keys could automatically be sent. It seems clear that the whole
protocol could be made largely automatic with no constant intervention
required by the parties concerned once the system was set up. It works
best if Hans has a hardware random number generator. Then the key
generator part of the process could be set up to run when no one is
using the computer. (Modifications to PGP have been published that
use hardware RNG's for their Random numbers.) Since in this case, the
computer is unattended, the PGP passphrase associated with the secret
key must be assumed to be known. To protect the secret keys against
theft in this case, the temporary secret key file could be encrypted
using Hans' long-term Public key. If there is no Hardware RNG
present, then Hans must be present at temporary key generation time,
to type in all of the stupid keyboard timing strokes! In this case,
Hans will want to create a number of keys in advance to be stored in a
database so that the mailserver can dole them out when people request
them.

A little thought shows that such a system could be used in some
applications of interest to cypherpunks. The ability to implement such
a system is clearly within our grasp. Therefore, the cypherpunk CODE
requires that the cypherpunks analyze, design, code and make such a
system widely available according to the grand traditions established
by previous cypherpunks.

Here are some beginning questions to get the ball rolling. How many
different CPU's Operating systems, mail transport mechanisms and mail
programs can such a program be adapted to? Should such a program use
PGP to do its encryption, or should it have its own built in
encryption routines. What Language should such a program be written
it? I think the program should be portable to all computers for which
the program is technically possible. Can someone outside the U.S. be
persuaded to code such a program? It would be best if such a person
could be found.

What do our fellow cypherpunks think?

Remember that when disusing this or any other encryption software on
the net, it is important that our usages be defensively
formulated. Encryption technology should always be used against evil
and for good.

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAgUBLkA6ug2Gnhl89QSNAQFEwwQAv00ZbSiZnFSEg/hBZvFX6RMAAt6uqa2y
UACKlf235ShWff0J2jk6tt2LjrZzoNr1J2qBpaeuXgRqj5zIN3vrvxlW3m9ntlSb
BgLLZbpSjt8FcgWOxDPIIo6bp4U4Qh2NzkNl77kKInpquYmnn3WYZl+KQdwRlsf+
VC3zCfh966M=
=pzkq
-----END PGP SIGNATURE-----

Derek B. Noonburg

unread,
Aug 9, 1994, 11:27:19 AM8/9/94
to
In article <199408090533.AA06475@xtropia>, 7CF5...@nowhere.pa.dec.com writes:

> Hans has one long term public/secret key pair which never changes.
> He could send temporary public keys in advance to the Princess as a
> signed (using his long term public key) message. Then when the
> Princess needs to send him a message she chooses one stored
> temporary public keys and sends Hans the message using that key. She
> then throws the key away and never uses it again. When Hans
> receives and decrypts the message, he destroys the secret key stored
> on disk by overwriting it. Then when Darth goes to torture Hans six
> months later for the secret key, Hans can only tell him the
> passphrase for the now non-existent key.

Maybe I don't fully understand, but... If Darth suspects that Hans is
using this scheme, he can torture him for the long-term key
(meta-key?). Please correct me if I'm wrong.

I'm not sure there's any way around this kind of thing. If Person A
has the capability (code book, password, computer disk, magical black
box, whatever) of decrypting a message, and Person B can physically
grab Person A and torture him, what can Person A do?

Replace "torture" with "court order" and this will likely become very
relevant in the near future.

- Derek

--
Derek Noonburg der...@vw.ece.cmu.edu
Electrical & Computer Engineering Dept., Carnegie Mellon University

Derek B. Noonburg

unread,
Aug 9, 1994, 11:35:55 AM8/9/94
to
In article <DEREKN.94...@vw.ece.cmu.edu>, der...@vw.ece.cmu.edu (Derek B. Noonburg) writes:

> Maybe I don't fully understand, but... If Darth suspects that Hans
> is using this scheme, he can torture him for the long-term key
> (meta-key?). Please correct me if I'm wrong.

Whoops, I'll correct myself. I did misunderstand what you were doing.
Darth could get the long-term key, but that wouldn't help him decipher
*old* messages.

I guess the only disadvantage to your scheme is that messages can only
be read for as long as the associated short term key is kept.

However, if Darth has the ability to grab people at will and torture
them, it doesn't really matter, since he can get the content of any
message he wants. I suppose the solution here is to get rid of Darth.

William Unruh

unread,
Aug 9, 1994, 2:31:41 PM8/9/94
to
der...@vw.ece.cmu.edu (Derek B. Noonburg) writes:
>I'm not sure there's any way around this kind of thing. If Person A
>has the capability (code book, password, computer disk, magical black
>box, whatever) of decrypting a message, and Person B can physically
>grab Person A and torture him, what can Person A do?

The idea is that he had the ability to decode it but no longer has it.
Ie the key was destroyed after the message was read. After the key is
destroyed, there is no way he can be forced to reveal it, esp since most
modern crypto never lets the person see the key ( and noone could or
woule memorize 56 0r 80 bits of random junk anyway)
They use a public key pair so the decryption key is not part of any
other message that could be decrypted.

--
Bill Unruh
un...@physics.ubc.ca

Paul Rubin

unread,
Aug 9, 1994, 9:54:05 PM8/9/94
to
In article <199408090533.AA06475@xtropia>, <cyphe...@toad.com> wrote:
>The second problem is the case where the Princess wants to send a
>secret message to Hans Solo in the horsehead nebula. She sends the
>message encrypted to Hans, but the encrypted message is intercepted by
>Darth. Hans decrypts the message, but unfortunately six months later
>Hans is captured by Darth who tortures him for the decryption key.
>Note the Hans is in a worse position than if he were tortured for the
>content of the message, because if he were merely asked the contents
>of the message with no way to verify, he could simply lie. But Darth
>can verify if any keys that Hans gives really does decrypt the
>intercepted cipper-text to a sensible message. This problem could be
>called the transmission retroactive coercion problem (TRCP). Unlike
>the static storage coercion problem, the transmission retroactive
>coercion problem does have a technical solution.

The attribute you are looking for in an encryption system is
called forward secrecy. Diffie-Hellman key exchange is one
way to accomplish it, for example. It is a lot less complicated
than the methods you suggest.

Ken Pizzini

unread,
Aug 10, 1994, 5:58:10 PM8/10/94
to
In article <328i2d$o...@nntp.ucs.ubc.ca>,

William Unruh <un...@physics.ubc.ca> wrote:
>( and noone could or
>woule memorize 56 0r 80 bits of random junk anyway)

It's quite possible to remember 80 bits of information,
suitable recoded for human memory (i.e. the actual datum
memorized is more than 80 bits long, such as a nonsense
poem which codes for the 80 bits). But I agree that
there are few cases where one would be inclined to bother.

--Ken Pizzini

Jeff Caruso

unread,
Aug 11, 1994, 9:54:51 AM8/11/94
to
In article <phrCuA...@netcom.com> p...@netcom.com (Paul Rubin) writes:

>In article <199408090533.AA06475@xtropia>, <cyphe...@toad.com> wrote:
>>The second problem is the case where the Princess wants to send a

>>secret message to Hans Solo in the horsehead nebula....


>
>The attribute you are looking for in an encryption system is
>called forward secrecy. Diffie-Hellman key exchange is one
>way to accomplish it, for example. It is a lot less complicated
>than the methods you suggest.

Please help me here. Isn't it true that if the opponent has the
entire ciphertext, including the Diffie-Hellman negotiations,
together with the secret key of one party, then he can reconstruct
the cleartext?

Isn't this one of the worries of the opponents of Clipper, that
conversations recorded now would be decipherable years in the
future under some possibly unrelated warrant?


- Jeff C.

******************************************************************
* Dr. Jeffrey L. Caruso 617/ 937-9400 x227 *
* Information International j...@triple-i.com *
* 10 Commerce Way *
* Woburn, MA 01801 617/ 937-0303 fax *
******************************************************************

- Jeff C.

******************************************************************

Ken Pizzini

unread,
Aug 12, 1994, 5:50:57 PM8/12/94
to
[alt.security.pgp removed from Newsgroups]

In article <1994Aug11.0...@lloyd.camex.com>,


Jeff Caruso <j...@lloyd.Camex.COM> wrote:
>In article <phrCuA...@netcom.com> p...@netcom.com (Paul Rubin) writes:

>>The attribute you are looking for in an encryption system is
>>called forward secrecy. Diffie-Hellman key exchange is one
>>way to accomplish it, for example. It is a lot less complicated
>>than the methods you suggest.
>

>Please help me here. Isn't it true that if the opponent has the
>entire ciphertext, including the Diffie-Hellman negotiations,
>together with the secret key of one party, then he can reconstruct
>the cleartext?

In DH, you have a system-public modlus P and generator a.
Alice and Bob each choose a random exponent (x and y, respectively)
and exchange a**x and a**y (both mod P). Alice and Bob can
now each calculate a**(xy) to obtain the session key, and
then destroy x and y, and when the session is over they should
destroy the session key also. The only public keys are
the public keys of the whole system (P and a). The only secret
keys are the transient x, y and a**(xy).


>Isn't this one of the worries of the opponents of Clipper, that
>conversations recorded now would be decipherable years in the
>future under some possibly unrelated warrant?

Yes.

--Ken Pizzini

Bryan G. Olson; CMSC (G)

unread,
Aug 15, 1994, 6:40:46 PM8/15/94
to
7CF5...@nowhere.pa.dec.com wrote:

[...]
: The second problem is the case where the Princess wants to send a

[...]

If you want a public-key system, then I think there are two ways to
go: some kind of one-time key exchange, or keys with very short
validity periods. Key exchange can provide shorter windows of
vulnerability, but requires Hans to be on-line when Lea sends the
message. Hans could use one long-term signing key to certify many
public encryption keys, each valid for one day. If he destroys keys a
couple days after they expire, then he has a modest window of
vulnerability, and a small chance that he will get late messages and
be unable to read them. The short-term keys do require many more
messages and storage at the server.

If you are only considering communication between Hans and Lea, they
don't have to be public keys at all. You can also save space by
deriving the next key from the previous key using some one-way
function f(). Lea gets a single conventional key k from Hans, using a
public key system or key exchange. She sends the first message
encrypted with k, computes k'=f(k) and destroys k. The next message
she encrypts with k', she computes k''=f(k') and destroys k'. After
Hans decrypts a message with k[i], he computes k[i+1] and destroys
k[i].

Can we create a public key system where you can derive the next keys
from the current keys but not go backwards ? Say you had
public/private key pairs (x,y) and pairs of functions f() and g()
where (f(x),g(y)) is always be a valid key pair for valid (x,y), and
g() is one-way. Then the server would only have to store one key per
user, but each user could have a new key every day.

Here's an example that doesn't quite work: Suppose we use
Diffie-Helman as a public key system. I register my public key y[0] =
a^x[0] mod p with a server, along with an iteration exponent e. Each
day the public key changes from y[i] to y[i+1] = y[i]^e mod p, and my secret
key changes from x[i] to x[i+1] = x[i]*e mod p-1.

(This fails because g(x) = x*e mod p-1 is not one-way, so I can still
retrieve old keys).

: Software to the rescue! Suppose that Hans runs a mail server on his


: account which recognizes certain messages as requests for new public
: keys and responds by sending back unused temporary public keys to the
: requester.

[...]

If Hans runs the server, I don't see any advantage over key-exchange
protocols. If a third party runs the server, I don't see much advantage
over short-term keys.

--Bryan

Reply all
Reply to author
Forward
0 new messages