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

[Arnold Reinhold]

> On Jul 14, 2020, at 5:12 PM, Seth David Schoen <schoen at loyalty.org> wrote:
> 
> Arnold Reinhold via cryptography writes:
> 
>> 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. Key bytes are extracted pseudo-randomly from the large key, using a message indicator as the seed. The extracted bytes can then be used one-for-one to encrypt message bytes. Terakey allows multiple stations that share the large key to communicate amongst each other without the elaborate bookkeeping required for one time pads. 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.  

>> https://www.researchgate.net/publication/342697247 

> This is a neat idea which would probably be useful in some scenarios.

Thanks. An architect proposing a skyscraper with a structural design based on an unproven mathematical theory, would ridiculed. But a large part of the world economy is secured based on mathematical conjectures and no one seems to mind.

> It's interesting to think about its overlap with other ideas.
> 
> I saw three ways that the security argument could fail in particular
> circumstances (one of them already discussed in the paper):
> 
> (1) Since "the attacker also knows both R and v" the
> information-theoretic or first-principles security argument breaks down
> slightly here if v is obtained "by hashing the message", because then
> you need to make assumptions about preimage resistance of the hash.
> (Even an attacker's ability to estimate a non-uniform probability
> distribution over hash preimages will remove the information-theoretic
> security of the system.)  I realize that this is only one of the methods
> given for choosing a value v and that the other methods don't have this
> limitation.

It’s a good point. Choosing v in a minimalist way may be better, perhaps just station of origin and date and time, with a log of message v’s to detect any duplication. More generally, it’s not sound to use widely assumed, but unproven, properties of a hash function in a first-principles security assertion. 

> 
> (2) If the method used to transmit v is not authenticated, an active
> attacker (who knows R) can perform an attack to try to deliberately cause
> particular Terakey bits to be reused by the message recipient.  The
> consequence of that may depend on whether the recipient can also
> successfully authenticate the decrypted plaintext somehow, and whether
> or not the recipient takes any observable action on the basis of
> decryption errors.  (For example, just indicating over an observable
> channel that a decryption succeeded or failed creates an oracle which an
> attacker might be able to use to test a hypothesis about whether or not
> two bytes of the Terakey are equal.)  In order to make a strict
> information-theoretic security argument here, you probably need to
> conclude that the recipient will never take an observable action on the
> basis of a calculated plaintext, or that the recipient has an
> information-theoretically secure way to authenticate either plaintexts
> or values of v.           

I’m not sure I see the problem here. An attacker who does not know the Terakey would have no way to accompany a chosen message indicator with a message body that decrypted into anything sensible or even predictable. So almost any sort of checksum would detect a failed decryption. What information would the attacker gain from the inevitable message rejection?

> 
> (3) The paper notes that
> 
>> The full security proof for Terakey assumes that the entire Terakey
>> is random. Creating a Terakey therefore requires large quantities of
>> fully random data. While the needed engineering is not trivial, this
>> article assumes it is possible to generate enough such data of
>> sufficient quality to assure security.  

> 
> If people using this system use a regular CSPRNG at some point in the
> Terakey generation, they may accidentally be reducing the system to
> a very unusual stream cipher, as this section warns "without the
> first-principles Terakey security proof”.

Right. I included the CSPRNG key generation method for completeness, with the warning. It’s at least conceivable that someone might want a key that could be regenerated in an emergency and be willing to give up first-principle security to have that. 

> 
> That section refers to using a 14-bit 200 million samples/second ADC
> to generate random noise.  On that device, even if all 14 bits of every
> sample were directly usable as physical randomness, it would take a
> month to generate the largest suggested size Terakey (one petabyte).
> People may be sorely tempted to use /dev/urandom instead.

A petabyte key would presumably have a cryptoperiod much greater than a month, so taking that long to generate the key is not a deal breaker. But realistically, a petabyte (Petakey) array would be constructed of smaller memory modules and these could be loaded with random key in parallel using multiple ADC modules.  For example, Samsung currently offers a 30.72 TB solid state module. If 32 of these are used to build a petabyte storage, then 16 ADC rigs could generate a Terakey in a couple of days.

> On July 13, 2020 at 15:38, Jerry Leichter wrote:

> Gee, sounds like an old idea to use a high-resolution photo of the moon.  The way that was set up, the underlying random-looking database - in this case, the brightness values of the picture - didn't even have to be private.

Sorry, I don’t understand the connection to what I am proposing. A photo of the Moon or pretty much anything else is highly non-random, except perhaps for low order bits which might encode digitization noise, and even a 10,000 by 10,000 pixel image would be much smaller than secret keys I am suggesting. Am I missing something? If there was an earlier proposal similar to mine, I’d like to include a reference.

Arnold Reinhold