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

[Arnold Reinhold]

On Sat, 18 Jul 2020 00:41 +0100, Peter Fairbrother wrote:
> On 13/07/2020 16:43, Arnold Reinhold via cryptography wrote:
>> Terakey(tm) is a cipher that offers confidentiality properties provable 
>> from first principles. It employs a shared secret key substantially 
>> larger than the anticipated volume of message traffic. 
> 
> Ie an OTP.

Not quite. One-timeness is the issue we are dealing with. See below.

> 
> Key bytes are
>> extracted pseudo-randomly from the large key, using a message indicator 
>> as the seed. 
> 
> What is the advantage of the pseudo-random selection? That two stations 
> can use the terakey using some secret shared-to-them-only key to the 
> PRNG without any other stations seeing that traffic? [3]

   [moving your footnote in-line:]
> [3] that doesn't seem to be in your proposal, but I am assuming. If it 
> isn't then I see no advantage - bookeeping is reduced to "don't reuse 
> key" and if eg a part of the terakey is allocated to station 1 the 
> station just uses the next portion of its part for sending its next message.


> Well we know that the other stations know the secret terakey, so as far 
> as they are concerned the problem is reduced to breaking the PRNG.
> 
> That may be a little harder because of the added (I presume) XOR with a 
> selection from the OTP, as some methods may not work; but it is not 
> necessarily any harder.

The purpose of the PRNG is to generate a pad for encrypting each message. Ideally, one would want a one-time pad, but Terakey does not guarantee zero-reuse, instead it generates pads that promise individual byte reuse will be rare, if you like, a mostly one time pad (MOTP). My paper proposes various ways of dealing with the rare reuse. (https://www.researchgate.net/publication/342697247 <https://www.researchgate.net/publication/342697247>)

Terakey is intended to provide confidentiality in two situations, key holders vs. non-key holders, and between pairs or groups of key holders (for privacy or compartmentalization). For confidentiality between key holders and non-key holders (arguably the more important case), confidentiality is based on first principles, without any reliance on mathematical conjectures. For compartmentalization, security also depends on the PRNG, as you point out. My paper suggests using public key methods to agree on a seed for compartmentalization purposes, and for forward security, but, as you say, any method to agree on a shared secret will do.

However, even with a cryptographically weak PRNG, say one whose state is recoverable from N known outputs, it is not easy to recover the state as used in Terakey. Suppose Alice sends Bob a new password and Mel gets hold of the cyphertext. And suppose further that the standard form for transmitting a password has lots of boilerplate, so Mel knows most of the plaintext and hence the cypherbytes used to encrypt a large part of the message. With a one terabyte Terakey, there are about 4 billion possible PRNG outputs that could produce each 8-bit cipherbyte. If N > 3, trying all combinations in order to find the state that produces the known cipherbyte sequence has a work factor of least 2^128. 

There are two cases where a stronger assertion for compartmentalized security among key holders is possible.

1. When Terakey is used for distribution of symmetric keys. This would be the use case where Terakey is compared with Quantum Key Distribution. In both instances there is a presumption that the symmetric cipher can be relied on, at least with frequent key changes. Then that same cipher's use as a PRNG would at least as secure, since each seed is a new key.

2. Using Terakey itself as the PRNG (an idea stimulated by this discussion), After selecting a Terakey byte to use as the cipher byte, use the subsequent 6 bytes to address the next cipher byte. (6 bytes can address up to 280 terabytes).  Since most mass storage does block reads, this would be fast, The only downside is that under the most conservative assumption that any Terakey byte previously accessed is compromised, this PRNG uses up Terakey seven times faster than using a conventional PRNG, but mass storage is cheap and getting cheaper.

> 
> And having multiple stations all in possession of the same secret 
> terakey is a huge single point of failure - the probability of a 
> secret's compromise is, inter alia, proportional to the square of the 
> number of people who know it. [8]

You are correct that a shared secret is a single point of failure. There are many other single points of failure in our current security arrangements, conjectures on the difficulty of factoring and discrete logarithms, signing keys used by software vendors, CA root keys, private keys of government officials, etc. Because of its large size, logically and physically, a Terakey is more easily protected than conventional symmetric and asymmetric keys. I would envision each Terakey would be housed in a secure container with tamper detection and alarms, with one copy and a backup at each location. An interface processor could monitor the rate at which key bytes are extracted and sound an alarm if the rate exceed a threshold. 

Terakey is not a PKI replacement. I don’t envision it being used to protect very large networks.  More like different offices of an international bank, a large software organization with multiple locations, or coordinating security between different ISPs and browser makers. Multiple users at each site could use the same Terakey module. If nothing else, Terakey could serve as an independent secure communication method to facilitate rebuilding in the the event of a major system collapse or cyberattack.

> 
> 
> Two messages can occasionally use the same
>> key byte, violating the one-time use restriction. That risk can be 
>> quantified and various ways are proposed to deal with it.
> 
> So how do you analyse that? Just probability of collisions? If that's 
> all, who's to say the pseudo-random generator doesn't kick out 
> collisions at a more-than-random rate, or in some pattern? You have to 
> analyse the PRNG as well.
> 
> And if you then have a cryptographically secure PRNG …

Yes, probability of collisions. There is extensive literature on the statistical properties of PRNGs. A PRNG with good statistical properties need not be secure and there are many examples. In addition to theoretical analysis, many PRNGs have been subjected to exhaustive empirical tests, some of which could be incorporated as self-tests in a Terakey system. 

> 
> Going from the provably-secure OTP to analysable (if it is analysable, 
> which I doubt) doesn't seem like much of a gain.

Here are a few Terakey advantages I see:

1. Elimination of each station's need to track pad usage with absolute reliability (not so trivial, systems do crash, malware could move back the pointer). 

2. The ability to easily create private channels between any pair of key holders, again without bookkeeping, 

3. New stations can be added without coordination with all the other key holders, and, for the same reason, a backup Terakey can be brought on line without requiring a transfer of state from the previous Terakey system.

4. For straight OTP, one has to provision enough pad material for each station. In a crisis where one staton sees very heavy traffic, there would be no easy way to re-provision if they ran out of key. Terakey degrades gracefully and all the key material is effectively available to the stations that need it most. 

5. As an alternative to QKD. One has to admire QKD from an esthetic standpoint, finding a practical use for one of the most bizarre predictions of Quantum Mechanics, but an alternative that does not require precision optics and cryogenic refrigeration is at least worth considering.


Arnold Reinhold
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20200720/67f28cbe/attachment.htm>