A "spread spectrum" cryptosystem

Howard Gayle

unread,

Jun 26, 1993, 11:39:40 AM6/26/93

to

In one of the replies to my previous article about a
"rubber-hose-resistant" cryptographic file system,
m...@FUZINE.MT.CS.CMU.EDU (Michael Mauldin) asked why not "use
something similar to spread spectrum techniques." In this
article I sketch a cryptosystem that might be described as
"spread-spectrum-like." Unfortunately, it has a risk of losing
or corrupting plaintexts, though the risk can be made
arbitrarily small.

GOALS

My goal here is to encrypt zero or more plaintexts into a
single cyphertext. Each plaintext is encrypted using a
different key, and can be decrypted by anyone who knows that
key, but only by someone who knows that key. Plaintexts can be
encrypted incrementally. In other words, it is not necessary
for the encryption function to have all plaintexts and keys
available to it at one time. An opponent should be unable to
discover the total number of plaintexts encrypted in the
cyphertext, even if some of the keys are compromised.

NOTATION

p[0..m] An array of bits representing a plaintext
message. The initial bits encode the length of
the plaintext in some way, e.g. a 16-bit binary
number.

c[0..n] An array of bits representing the cyphertext.
It is initialized with true random bits from an
appropriate distribution. n is much greater than
m.

j The number of copies of p[] to encrypt into c[].
j is an odd integer greater than 2.

q() A function that returns the next number in a
deterministic sequence of numbers. The number
returned is in the range 0..n. The sequence
depends only on a given key. q() might be
implemented by running a single-key encryption
algorithm in feedback mode.

ENCRYPTION

for x in 0..m
for y in 1..j
c[q()] := p[x];

In words, j copies of p[] are spread throughout c[]. Where
they go is entirely determined by the key.

DECRYPTION

Given the key, generate the sequence of numbers by calling q().
Retrieve all j copies of each bit. Use majority voting to
determine the correct value of each bit. Once the initial
length field is recovered, keep going until the whole plaintext
has been recovered.

OBSERVATIONS

For clarity, I've simplified the scheme as much as possible.
In this form it doesn't appear to have any practical value. I
have no idea if a more refined version could be useful.

Some optimizations do suggest themselves, such as:

1) Operate on larger quantities than single bits.

2) Use an error-correcting code, or at least a CRC to detect
corrupted plaintexts.

3) Sort all the changes to c[] and apply them sequentially,
to reduce I/O.

4) Pre-encrypt the plaintexts with some single-key
encryption algorithm whose cyphertext has an even
distribution of 0 and 1 bits.

By picking big enough values for j and n the probability of
corrupting plaintexts can be made arbitrarily small, but it
will always be nonzero.

In the simplest scheme, it is not possible to detect a
corrupted plaintext.

The period of the sequence generated by q() should be much
longer than n.

The random distribution for the initial value of c[]
should be that of the plaintexts.

A NOT TOTALLY IMPLAUSIBLE APPLICATION

Alice has agreed to water the plants in the houses of Bob and
Carol. Both houses have burglar alarms with "duress" codes.
(Entering the duress code instead of the normal code appears to
turn off the alarm normally, but it also silently signals the
alarm company. Some alarms really have this feature.) Alice
thus needs to store two codes for each house. She sets up the
following cyphertext in her personal digital assistant (PDA):

Key Phrase Plaintext Comment
--------------------------------------------------------
Bob:Dorothy 0123 Bob's normal alarm code
Bob:Hillary 3210 Bob's duress alarm code
Carol:Dorothy 6789 Carol's normal alarm code
Carol:Hillary 9876 Carol's duress alarm code

This application is somewhat plausible because the plaintexts
are short, so the cyphertext doesn't have to be huge to still
give a very low probability of corrupting a plaintext. Alice
only has to remember one normal password (Dorothy) and one
duress password (Hillary), plus the rule for generating key
phrases.

A SLIGHTLY LESS IMPRACTICAL SCHEME

This scheme uses a large array of bytes b[] that is initialized
with true random bytes. b[] wraps around, so b[0] comes after
the last byte. To encrypt a plaintext:

1) Use the user-supplied key to generate a sequence of j
indices into b[]. For each index, execute all the following
steps.

2) Pick a random session key. Use it to encrypt the plaintext
with some single-key algorithm. A different session key is
used for each copy.

3) Create a block containing the session key, a
CRC of the plaintext, and the length of the plaintext.
Encrypt this block with the user-supplied key. This is the
encrypted header.

4) Copy the encrypted header and then the encrypted plaintext
into b[] starting at the index computed in step 1.

To decrypt, generate the first index, retrieve the encrypted
header block, decrypt it, and use the session key and length to
decrypt the encrypted plaintext. If the CRC matches, the
decryption was a success. Otherwise, try the next index. If
all j indices fail, the plaintext has been lost.
--
Howard Gayle
HAL Computer Systems, Inc.
1315 Dell Avenue
Campbell, California 95008
USA
how...@hal.com
Phone: +1 408 379 7000 extension 1080
FAX : +1 408 379 5022

Steve Brinich

unread,

Jun 26, 1993, 6:24:06 PM6/26/93

to

Sounds like the simplest solution would be to provide a simple "duress"
pass phrase which starts to display something that looks plausible while
wiping the file.

Steve Brinich
<ste...@access.digex.com>

* Never mind MST3K -- what I want to see is C-SPAN3K. *

Marc Thibault

unread,

Jun 28, 1993, 9:46:15 PM6/28/93

to

ste...@access.digex.net (Steve Brinich) writes:

> Sounds like the simplest solution would be to provide a simple "duress"
> pass phrase which starts to display something that looks plausible while
> wiping the file.

Suppose also that it mimics the behavior of a moderately
well-known virus, thus providing plausible deniability for the
damage.

This is one for the white hunters. How about some code that,
while not viral itself, "virusizes" a disk, ensuring that
particular files are quickly targetted and that leaves
convincing debris when it's done? Done well, it could also
include "personality modules" allowing the user to choose
which virus is to be simulated.

Cheers,
Marc

---
Marc Thibault | ma...@tanda.isis.org
Automation Architect | CIS:71441,2226
R.R.1, Oxford Mills, Ontario, Canada | NC FreeNet: aa185