Re: Memorizable pen and paper systems (the system)

From: Jim Rootham (jimNOSPAM.rootham_at_utoronto.ca)
Date: 02/18/04 

Date: Wed, 18 Feb 2004 10:53:31 -0500

I was obviously being too cute with my subject line previously.
What follows is what I put up under "Reinventing the wheel" and got
no responses.

I read "Cryptonomicon" and got re-inspired abut cryptology. I
decided to try to invent a new cyryptosystem. I cannot imagine
that what I came up with is actually new but the closest thing in
the literature (Kahn and Singh) I could find was the Thwaites
challenge to Babbage which used a ridiculously short key (from "Mr
Babbage's Secret").

System requirements:

Pencil and paper system.
Simple enough to memorize.
Useful for many messages.
Adjustable for convenience vs security tradeoffs.

I started by trying to model rotor systems but when I built it I
realized that it was actually multiple Vigenere. In poking at it I
noticed that if you knew the lengths of the keys you could
construct a synthetic key (by subtracting out characters) that was
the sum of the lengths rather than the product. Given that,
Babbage-Kasicki works so I concluded that the principle key was the
set of key lengths. What text you put in them was secondary. This
is of course assumes there is sufficient encrypted text to analyze,
a fixed set of lengths with arbitrary text can be used to generate
a small number of random characters or numbers.

The first decision to make to generate an implementation is to
decide how high (number of superenciperments) and how wide (set of
lengths of the individual keys) you want to make it. This is the
convenience vs security tradeoff. I conjecture that 10 high by
between 10 and 114 wide is secure for the forseeable future.

Next choose a memorable phrase of at least 28 characters, and a
memorable piece of text (almost certainly poetry, I have been using
"Jabberwocky") of 200-1000 characters (about 4-20 lines). How long
this needs needs to be depends on the first phrase and will
probably be close to 600 characters.

Break the first phrase up into lengths of 2, 3, 5, 7, and 11
characters and use each string as a vigenere key to generate an
arbitrary (and expected to be random) set of numbers modulo 26.
Use this set to compute 10 numbers between 10 and 114 by computing
10+((n1/6)*26)+n2, skipping any n1's that are greater than 23.
Test this set of numbers to see that the group they make
(size=size*n/gcd(size,n) for each number) is suffiently large for
the number of messages you wish to encrypt (1000 10k messages needs
10**7). Use another phrase if it fails this test (exceedingly
unlikely).

To encrypt a message first compute a message key by multiplying the
message number by the maximum message size. Break up the poem into
the lengths generated by the phrase and rotate each subkey by the
message key modulo that length. Use the resulting strings to
multiply vigenere encipher the plaintext. Given the additive
nature of vigenere it does not matter what order the keys or
plaintext is enciphered.

Decryption is left as an exercise for the student :).

There are some open questions about filtering out numbers in the
key and what it does to the cryptanalytical search space (a divisor
of another key can be ignored). The best search strategy I can
come up with is to test for high and low values and recurse. This
reduces the proposed scheme's search space by about a factor of
1000. Given that the test at each point in the space (repeated
subtraction) is about 1000 steps the whole search should be about
100**10 or 10**20.

The major technical weakness that I can see at this point is
reusing message numbers. I believe that only gets the repeated
messages, not the key. Are there standard transposition ciphers
designed to protect messages from repeated keys?

I can only assume that anyone who invented this previously thought
it was too unwieldly to use.

Does it appear in the open literature anywhere?

If not, are my analyses correct?

Jim Rootham

PS

I have computed the expected values of the single characters,
digraphs, and trigraphs and they look flatter than 1 part in 10**-7
at 10 high.

Since I put it up this message I tripped across a passphrase
security analysis which indicates that the passphrase is a
relatively weak part of the above system. Is 27 memorable
characters enough? I can see a few methods for beefing this up.

JR

Relevant Pages

  • Reinventing the wheel
    ... the sum of the lengths rather than the product. ... a small number of random characters or numbers. ... this needs needs to be depends on the first phrase and will ... key and what it does to the cryptanalytical search space (a divisor ...
    (sci.crypt)
  • Re: CONTAINS and non-wildcard asterisk
    ... >> wildcard it, and you wrap it in single quotes. ... >> If you wrap the phrase with double quotes you will get wildcarding, but it>> will still match with test*. ... >> alphanumeric characters it strips them out and indexes the alphanumeric ... >> Looking for a book on SQL Server replication? ...
    (microsoft.public.sqlserver.fulltext)
  • Re: opinions on password policies
    ... On Mon, 15 Jan 2001, David Talkington wrote: ... Pick a very long phrase or ... Now choose 8 or 10 characters from it at ... > PGP key: http://www.prairienet.org/~dtalk/dt000823.asc ...
    (FreeBSD-Security)
  • Re: ALERT: WPA-TKIP isnt secure - use WPA2 instead
    ... USE WPA-AES or WPA2 instead of WPA-TKIP ... USE A PASSPHRASE WITH MORE THAN 20 CHARACTERS. ... remember this phrase, type it in more than once, or otherwise make it ... I once tested this method various password crackers. ...
    (alt.internet.wireless)
  • Re: Problem setting up Encryption with Wireless Network
    ... When you turn on WEP - it will ask you to enter a passcode.. ... characters (could be mixture, could be all numbers, could be all letters - ... describes a point in their life and then turning that phrase into their ...
    (microsoft.public.windowsxp.basics)
Quantcast