[Cryptography] Terakey, An Encryption Method Whose Security Can Be Analyzed from First Principles

[Arnold Reinhold]

On Jul 21, 2020, at 12:18 AM, Whitfield Diffie <whitfield.diffie at gmail.com> wrote:
> 
>    Turkey immediately reminded me of two things.  The British
> introduced a merchant-marine ``code'' in about 1942.  It consisted of
> a book of groups to be added to code text.  The indicator was a page
> and line pair.  I don't know if the code was one-part or two parts and
> to what degree it was secret.  This worked fine for about a year and a
> half. until they to to about the square root of the size of the code
> book; then it began to leak and the British began losing ship.  The
> scheme will work fine if the additive book is large enough.
> 
>    The way the additive has been made large enough is to stop wanting
> information theoretic security and use a long-cycle system, keyed by
> the starting point, like A5.  That particular one has only a
> $2^{64}-bit sequence so it will begin to leak in reasonable time but
> it could be made of size $2^{128}$ or larger and that problem would go
> away.
> 
>    Terakey, run with a starting place as indicator and the PRNG as a
> 1-up counter is this same approach.  I presume it will now be argued
> that the PRNG can be more complex than a 1-up counter.  If that is the
> idea, you are back to doing computational cryptography.  Using a large
> body of key in addition may be a worthwhile idea --- and I salute the
> notion of mixing information theoretic and computational approaches
> --- but it doesn't seem like a slam dunk argument for security.
> 
>                           Whit

Hi Whit,

Thanks for your comments. What I am doing is quite similar to the additive books you describe, with the important difference that because mass storage has gotten so cheap, we can afford to make the “book” tens of millions of times bigger than what was possible in WW II. Most of the security of Terakey is based on this fact alone.

The analysis of Terakey (https://www.researchgate.net/publication/342697247) consists of a series of levels. For the basic level, the attacker is assumed to know the PRNG algorithm and the message indicators, ciphertext and plaintext of all past traffic. Under these assumptions, the attacker would therefore know the locations and contents of all the Terakey bytes used for past traffic. The only thing relied on from the PRNG is providing a reasonable approximation of a uniform random sampling of the Terakey. It is well established that PRNGs can do that. 

The security analysis then consists of estimating the likelihood of a cypherbyte already known to the attacker being used in a new message of a given size. As long as the volume of traffic is kept low compared to the size of the Terakey, only a small number of bytes in a message will potentially be compromised. Various ways to deal with this potential leakage are presented, including classical methods like message padding and folding. 

The use of a cryptographic PRNG is later introduced as one way to deal with the occasional byte leakage. In addition, it offers a subset of key holders privacy from the other key holders, a secondary security objective. In terms of protecting Terakey-encrypted traffic from non-key holders, the information theoretic approach is doing the heavy lifting, with the computational approach only dealing with rare collisions. There is also synergy between the two, as I pointed out in my previous post, in that an attacker who even knows most of the plaintext of a new message gets very little to work with in finding the PRNG seed.

Back in WW II, it would have been unreasonable to ask a code clerk to go to a different page and line for each code group, and so adjacent strings of additives were used, a weakness Allied cryptanalysts took advantage of.  Liza Mundy, in her excellent book Code Girls, describes interviewing one of the elderly veterans of Arlington Hall who is at long last able to say out loud her top secret wartime job title: she was an overlapper.

>   ``Turkey'' was provided by the Gmail spelling corrector not my
> snide sense of humor. I caught the second one but did catch the
> outgoing message in time to get the first one.

Thanks for clarifying that. I am convinced that World War III will be started by a spell checker autocorrecting a diplomatic note.

Arnold Reinhold