[Cryptography] "Perpetual Encryption"

[Dennis E. Hamilton]

> -----Original Message-----
> From: cryptography [mailto:cryptography-
> bounces+dennis.hamilton=acm.org at metzdowd.com] On Behalf Of Dennis E.
> Hamilton
> Sent: Wednesday, March 29, 2017 15:16
> To: 'Crypto' <cryptography at metzdowd.com>
> Cc: 'Allen' <allenpmd at gmail.com>
> Subject: Re: [Cryptography] "Perpetual Encryption"
> 
[ ... ]
> On first impression, the scheme struck me as reducible to something like
> this:
> 
>      Ci = E(Ki, Mi || Ri)
> 
> Where E is a block cipher and length(Mi || Ri) is the block size.  The
> 100% expansion case is where Mi and Ri are each half the block size.
> There are arguments in the paper about how one can adjust the length of
> the R blocks to safely decrease the size expansion, and the M can also
> be compressed to gain further leverage (with care about compression
> failures, including information disclosure, that are not mentioned).
> 
> The trick seems to be simply that given Ki, you need to decrypt Ci to
> know not only Mi but the Ri so you can derive K[i+1] = f(Ki, Ri).
> 
> What E(k, b) and f(k, r) can be that safely minimize re-keying per block
> and also keep R simple enough to satisfy the constraint conditions is
> not something I looked at.  I also did not break down the proposed
> scheme to confirm how it satisfies the above pattern and be OTP-
> congruent.  This is what I made out of the prose description.
> 
> It seems to me that the paper explicitly states that authentication is
> not handled (yet), and I didn't see anything about padding.

[orcmid] 

There are two papers on the Perpetual Encryption approach and the arguments about Perpetual Equivocation: "The Perpetual Equivocation Method (White Paper)",
<http://perpetualencryption.com/ThePerpetualEquivocationMethod(WhitePaper)Final.pdf>, of 2016 and the 2017 Blue Paper, "The Nino Cipher: The Foundation to Next-Generation Security", <http://perpetualencryption.com/BluePaper-NinoCipherv1.pdf>.  The links to those PDFs are a pop-over on the map at <http://perpetualencryption.com/> that does not always appear, depending on browser and its window size.

I have looked deeper to understand the scheme.  My impression is that the system (at least, as approached by me) is a bit brittle.  There may also be some over-engineering and simplifications that do not weaken security are desirable.  

In the following Concept Pilot (CP), I've introduced illustrative specifics as demonstration that under-specified conditions suggested in the White Paper and its Figure 3 can be honored.  This is not intended to match the Perpetual Encryption approach, only to demonstrate one possible embodiment of the essential concept.

DECRYPTION

CP decryption is characterized first, since the interdependencies and pass-ahead behavior stand out better.  In this formulation, it also illustrates the complexity involved in finalizing a stream (my bad).

 1. KEY OBSERVATION: The CP cipher-text recipient need have no knowledge of the "True RNG", RNG1, that is used as the source of "entropy-injection" that is piece-wise delivered via the cipher stream. There *is* dependency on a common PRNG, RNG2, that must be correctly implemented and used synchronously to accomplish encryption and decryption.  RNG2 must have a means to accept "entropy injections" via variable-length binary strings that are obtained from RNG1, whatever it is, and used to modify the RNG2 state.  These RNG1 strings are passed from encryption to decryption within the cipher blocks.  In this way RNG1 can be replaced, upgraded, enhanced, etc., since RNG1 itself is not required for decryption.

 2. RANDOMIZED CHUNKING: For CP, cipher-text blocking is not conveyed in the cipher-text.  This is accomplished by the decryption for an incoming (variable-length) CP cipher-text block, Ci, already having (a) the length of the block, Ci.size, (b) the position of the boundary between Ri and Mi in the decrypted Ci buffer Bi = (Ri||Mi), Bi.split, (c) a "minor key", Ki, and (d) [P]RNG2 in the same state, S[i-1], that it was after the encryption/decryption of C[i-1] and readied for use in encryption/decryption of Ci.  (The synchronization of Si between encryption and decryption procedures need not be literal, but it must be effectively the case. Treat it as literal for simplicity.  Assume that Ci.size and Bi.split, if variable, are derived by an extraction from RNG2 already and that is reflected in the current state S[i-1].   (See steps 7-10 below.)  For technical simplicity of CP, the Ri precede the Mi in CP buffer Bi.  The (a-b) parameters are not conveyed in the cipher stream in any form.

 3. On arrival of block Ci, the "super key" XKi of the same length as block Ci is extracted from RNG2.  This is where a Vigenère procedure is appropriate.  XKi is posited to be a cryptographically-random string and it is only used this once, qualifying as a candidate [cryptographically-]OTP key-stream segment.  

 4. Additional parameters can be extracted along with XKi.  For CP, a rotation factor, Bi.rotate, is extracted from RNG2 prior to XKi.  Encryption rotates the encrypted Bi into Ci by Bi.rotate positions, encrypting Octet Bi[j] to position Ci[(j + Bi.rotation) mod Ci.size], j = 0 to Ci.size-1.  Decrypt Ci by rotating the bytes back into their Bi position as they are decrypted in Bi sequence.    

 5. [*At*no*point*do*the*fingers*leave*the*hand* department.  The parameters 2(a-d), Bi.rotate, and XKi do not depend on any knowledge that can only be known by decrypting Ci.  In particular, S[i-1] is the state from which ROTi and XKi and any additional parameters are derived.  

 6. SIGNALLING STREAM COMPLETION. Ideally, the decrypted buffer has nothing in it but (Ri||Mi) and everything in it is obtained by decrypting Ci in (3-4).  For CP, there *is* an initial flag byte on Ri.  The flag byte is needed, in this formulation, to identify Bi blocks with exceptional structure as part of finalizing the stream (11, below).  

 7. CONTINUATION OF THE STREAM. For normal blocks, as distinguished by the flag that begins Ri, Mi is now extracted.  The remainder of Ri, if any, provides any "entropy injection" for RNG2.  That portion of Ri was encrypted using Ki. It is decrypted to Xi.  Inject Xi into the RNG2 as more entropy pool.  

 8. Derive (2c) X[i+1] = f(Ki, Xi). 

 9. Use RNG2 extraction to derive (2a) the prospective length of block C[i+1].size and (2b) B[i+1].split, the boundary between M[i+1} and R[i+1] in that block.

10. At this point, (2d) RNG2 is at state Si and the preconditions of (2) are satisfied.  On to C[i+1] (step 3, above).

11. STREAM FINALIZATION. If the block is determined to be a final one, Bf, at step (6), the block and possibly following ones are designed for finalization: obtaining any remainder of M and also providing padding and authentication to wrap everything up. If there are also B[f+1] and more, the scheme should create the continuations for finalization in the same manner as normal blocks, but the Ri flag byte and other structure can vary.  The design of such an arrangement for CP is omitted.

ENCRYPTION 

The encryption process is straightforward.  Finalization starts when the remaining unencrypted part of message M is less than the amount provided for Mi in Bi.

INITIALIZATION

To start, all that is given is (2c) K1, the secret key that must be exchanged.  Use it to seed RNG2.  Perform step (9), giving us C1.size and B1.split for B1.  RNG2 is now at state S0.  

Note that everything, at this point, including XK1, is completely determined by K1.  When M1 is encrypted as part of C1, the only thing that depends on anything else will be R1, and that will not normally have any impact apart from its unpredictability in C1 until the production of C2, etc.  

OTHER CONSIDERATIONS

It is crucial that K1 be cryptographically-random and not be reused.    

Considering that K1 is proposed to be of any length and that the Xi may also be any length within a buffer size, it is unclear what is required for the seeding of RNG2 and the encryption of X1 by K1 to work well.  It is also unclear how derivation of K[i+1] = f(Ki, Xi) is assured to work well.  This is left unspecified in CP, above.

This sketch does not address how the Ci.size and Bi.rot values are determined in a manner that will provide sufficient "equivocation" in terms of demand for RNG1 Xi contributions.  There also needs to be a practicable upper-limit on Ci.size.

With respect to the security model, RNG2 is essentially a means for stretching the (K1, X1, ...) stream for some operationally-valuable purpose (including hiding of that stream) in producing (XK1, XK2, ...) and the associated parameters.  

The choppiness of CP operation in producing/consuming a cipher stream is a likely concern with respect to attacks based on covert observation of processing patterns.  There are also performance concerns if RNG1 is used heavily enough that it stalls as part of being "truly-random."

 - end -