Chaffing and deniability in pencil-and-paper ciphers

Although pencil and paper ciphers are entirely impractical these days,
they do provide good mental fodder while standing in line or trying to
fall asleep. During one of those times, I got to wondering about the
following scenario: Assume that a computer could be used during the
_encryption_ step. During decryption, you would still be limited to
pencil and paper, and perhaps a calculator. (Others here have proposed
starting with those assumptions.) Could encryption be beefed up in
some manner that would make cryptanalysis more difficult, without
adding an equivalent effort to decryption? (Such a scenario might
occur with HQ communicating [one-way] to an agent in the field.) The
possibilities here are interesting. Again, this is just a mental
exercise.

Two things in particular occurred to me. The first was that Rivest's
chaffing and winnowing idea is just a special case of the general idea
of peppering a message with nulls to foil cryptanalysis. The second
was to add a fake message to the mix, so if you are questioned, you can
reveal the fake message. These things led me to the following idea:

The encryption step (done via software) would take 3 "messages" as
input:
1. The real message
2. The fake message, which could be revealed
3. A garbage message

The real message is encrypted using your best algorithm, known to the
recipient. The fake message can be encrypted in a weaker cipher, and
can even be in a cipher unknown to the recipient, since they are not in
need of decrypting it. The garbage message is not encrypted at all,
but is computed to have statistical properties similar to that of the
encrypted real message. That way, if the fake message is revealed, the
remaining ciphertext (the real message plus the garbage) will look as
uniform as possible. All of these steps are done in software. (As you
will notice, I do not mention a particular pencil and paper cipher, as
that is not my main point.)

In what follows, I assume that the ciphertext has been grouped--a la
the good old days--into something like blocks of 5 digits.

Next, we need a way of attaching message authentication codes (MACs) to
the three streams, so the streams can be separated later. I have not
researched any specific proposals yet, but am considering two digits
that would be appended to each block of 5 digits. When the MAC
function is evaluated, it would give a particular number, k, if the
block is part of the real message. Otherwise, it evaluates to some
other value. Since such a MAC would be a many-to-one mapping, the two
appended digits could be chosen (by the encryption software) in such a
way as to yield the correct values when run through the correct MAC,
but the values 0, 1 and 2, for example, under one or more
computationally simple MACs that an attacker might attempt first.

Before transmitting the message, the encryption software would
intersperse the blocks from the three streams in a semi-random fashion.
I.e., it would not always send one real block, one fake block and one
garbage block per trio of blocks. The recipient only has to winnow the
full message and decrypt the real message within.

In summary, this approach adds complexity up front, where it can be
done easily via software. Encryption will be error-free (assuming the
software works right). Decryption is still fraught with all the usual
perils: effort-intensive, prone to propagating errors, too much to
memorize. And the system as a whole suffers from its well-known
drawbacks: bad news if you're caught with sheafs of paper with letters
and numbers all over them, an insecure underlying encryption algorithm,
too much to memorize, and so on. But, it's an interesting exercise...

.

Relevant Pages

  • Re: Should Initialization Vectors be public ?
    ... CBC XORes every previous cipher block with next plain text block before ... encryption key on the same plain text, ... add them at the beginning of your plaintext data ...
    (microsoft.public.dotnet.security)
  • Re: Should Initialization Vectors be public ?
    ... > CBC XORes every previous cipher block with next plain text block before ... Chaining and feedback modes does provide extra strength to ... > encryption key on the same plain text, ... >>>> then to decrypt. ...
    (microsoft.public.dotnet.security)
  • Re: cryptoloop CBC mode
    ... >> identical it could be the case that two would get same encryption. ... For such blocks you will know exactly which bits differ ... and the two IVs are different. ... > the key will still be the same (ok, different cipher output, but the ...
    (comp.os.linux.security)
  • Re: Break This
    ... I'd guess that you're trying to ascertain if your cipher is ... > against your attackers? ... > engineer your encryption algorithm, they'll try and stick a trojan on ... This is I think the only secure way. ...
    (sci.crypt)