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

[Peter Fairbrother]

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 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.

Peter Fairbrother