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

Arnold Reinhold agr at me.com
Fri Aug 7 15:06:17 EDT 2020

> On Jul 29, 2020, at 8:17 PM, Peter Fairbrother <peter at tsto.co.uk> wrote:
> On 30/07/2020 00:06, Arnold Reinhold wrote:
>> On 28 Jul 2020 12:11 +0100 Peter Fairbrother wrote:
>>>> The security analysis then consists of estimating the likelihood of a cypherbyte already known to the attacker
>>> Oh no no no. That might be your analysis, but it isn't the only analysis.
>>> Suppose I am the NSA and manage to tweak the PRNG to my nefarious means.
>>> Perhaps I can arrange that 1 in 3 selections is to a limited set of
>>> terabyte bytes. After getting some known plain/cyphertext traffic I can
>>> read 1/3 of the plaintext characters - enough to do serious damage.
>> If the NSA can tweak my algorithm, they can make it emit rot13, or an apparently strong PRNG stream where they know most of the seed. That is true of any crypto system.  If I have somehow created the impression that I am proposing the PRNG be something that is negotiated between the parties, my fault for not being clear. I did not specify a specific PRNG because I wanted to consider ones that were reversible vs ones that were based on security primitives.  A Terakey system fielded would have a fixed PRNG.  If you like, the one specified in NIST SP 800-90A Rev 1, section 10.2, using a block cipher such as AES-256 or whichever block cipher is being used with key exchange mode.
> The NSA tweak was just an example to get you thinking in the right way. As were the chosen-key known-ciphertext attacks I mentioned, the second of which can be done with *any* prng - just find a key which outputs the same location ref as a location ref in the message to be broken, rinse and repeat.

What you are proposing are active attacks. The security model I used in my paper[1] for what I claim is a first-principles proof of confidentially is based on a passive attack. The attacker know all aspects of the basic Terakey system, including all past traffic, except the Terakey itself.  In particular, that means he cannot generate Terakey encrypted messages. 

I separately consider confidentiality for groups of key holders, but I do not claim a first-principles proof. An obvious problem with security among key holders is that they have some level of access to the Terakey. I propose using a processor interposed between the Terakey storage module and the rest of the system that monitors and limits the rate at which key material is extracted from the Terakey, so as to prevent users from recovering large portions the Terakey by generating large quantities of messages. Your suggestion of messages tailored to extract specific bytes would not be caught by this mechanism. A possible solution would be incorporating a secret as part of the seed that is not known to all users. I propose something like that to minimize damage if a Terakey is stolen, but you have provided another good reason for doing so. 

> What is important is that you cannot prove that the chosen prng is as-secure-as-random in this application - which you would need to do in order to analyse the method's security from first principles. And as far as I know that can't be done.
> "Providing a reasonable approximation of a uniform random sampling" is not enough for a proof of security.

The proof of security is simply that if a byte in the randomly generated Terakey is only used once, the resulting encryption is secure, as with an OTP. If it is used more than once, then security of the resulting encryption using that byte is not guaranteed  I am only using the uniform random sampling properties of the PRNG to calculate the probability that a given message will contain bytes encrypted by re-used bytes and, if so, how many. By keeping the size of the Terakey large compared to the volume of traffic that probability can be kept arbitrarily low. 

I’m not making any security assumptions about the selection process, only that the outputs, and hence selected key bytes, are distributed close to uniformly. There is a vast literature on the design of PRNGs that have this property on theoretical grounds, plus extensive efforts to verify those properties experimentally with a range of tests. Here is a 2006 paper that describes one family of such PRNGs with strong uniformity properties and very large period, with a review of the literature.

http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf  Panneton, et al,  "Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software. 32 (1): 1–16

There are many others. Can you clarify what your objections are?

Arnold Reinhold

[1] https://www.researchgate.net/publication/342697247 <https://www.researchgate.net/publication/342697247>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20200807/cb819a33/attachment.htm>

More information about the cryptography mailing list