PerpetualCrypto.txt

PerpetualCrypto.txt 0.0.2           UTF-8                         2024-11-20
*---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--*


                              GitHub orcmid/docEng
                              ====================

                        Perpetual Encryption Notes
                        --------------------------

    This is a placeholder of notes from the [Cryptography] list that I wrote
    on a proposed "Perpetual Encryption."  It was intended as an nfoWorks
    topic, and I thought of it applying to documents at rest as well as for
    streams where the unfortunate expansion is tolerable.

    The scheme does not provide for great entropy. It is an elaborate scheme
    where, apart from the initial key, which is exchanged however it can be,
    followed by paired variable-length blocks that involve permuted data and
    a reseed amount in a shared RPG. The shared RPG generates a key stream for
    deciphering the next block, etc.

    So all of the security depends on the initial key.  The perpetual scheme
    is more of a broad obfuscation that makes discovery of patterns and
    supposed repetitions very difficult to discover and act upon.  I don't
    think this qualifies as a one-time-pad stream cipher situation.

    There might be application for nfoLocker,
    <https://nfoworks.org/notes/2012/05/n120501.htm>, although I had
    considered that as a variation on the ODF Package and maybe here on
    docEng, although that's pretty low-level.

    The following notes are from the indicated emails, in chronological order.

2017-03-28 RICH SALZ NOTeE ON "PERPETUAL ENCRYPTION"
====================================================

Any comments?  http://perpetualencryption.com/

“No keys.  Encryption based on a perpetual OTP designed to be secure.                “

--
Senior Architect, Akamai Technologies
Member, OpenSSL Dev Team
IM: richsalz@jabber.at Twitter: RichSalz

2017-03-29 PHILIP HALLAM-BAKER WRAPS IT UP
==========================================
I note (2024-03-18) that the web site is still there.  However, there is no
description of the methodology and the claim of 10^&2158 times more secure
than existing industry standards and Quantum / AI security is achieved, along
with the option of infinite bit encryption.
===========================================

From: cryptography <cryptography-bounces+dennis.hamilton=acm.org@metzdowd.com>
      On Behalf Of Phillip Hallam-Baker
Sent: Wednesday, March 29, 2017 14:03
To: Bill Cox <waywardgeek@gmail.com>
Cc: Allen <allenpmd@gmail.com>; Patrick Chkoreff <patrick@rayservers.net>;
    Crypto <cryptography@metzdowd.com>
Subject: Re: [Cryptography] "Perpetual Encryption"



On Wed, Mar 29, 2017 at 10:41 AM, Bill Cox <waywardgeek@gmail.com> wrote:
This scheme scores highly, except that it has no web site:

I invented an amazing truly unhackable super-encryption algorithm.  It is also
super-simple:

1) Generate n bits of true random data that have no bias or any detectable
   non-randomness
2) Manually deliver this OTP random bits to the recipient, then go home.

There are two tests that are critical. Attackers being unable to break the
system and users being able to use it in practice.

Any system that claims to have a one time pad is either utterly impractical
or not a one time pad. Thus the claim is a near infallible indicator of
bogosity.


The one class of system involving an OTP that could arguably be harder to
break (but not impossible) is to mix a random stream of bits into the stream
in a fashion that effectively increases the key length.

So lets say your initial key is k.

We encrypt the first AES block as follows.

Generate a random value the same size as the block. R
Let RH, DH be the high bytes of the random and data blocks respectively and
RL, DL be the low.

Output = AES (DH+RH, k) + AES (DL+RL, k)
    k' = AES (R, k)


What this achieves is it doubles the size of the cipherstream and stalls the
AES encryption every two blocks.

What it might achieve is some degree of additional work factor but I doubt it.


A more difficult to break arrangement might be

Output = AES (R, k) + AES (D^R, k')
    k' = AES (R, k)


It is of course total bollocks though. It is not making the cipher unbreakable
and the work factor is actually unchanged.

There are infinitely many similar schemes. And they all fall short because the
width of the key isn't increased.



2017-03-29 INITIAL RESPONSE TO ALLEN ABOUT THE PROPOSED METHOD
==============================================================
The Phillip Hallam-Baker rejoinder didn't stop me from running through this
analysis and proposal.

> -----Original Message-----
> From: cryptography [mailto:cryptography-
> bounces+dennis.hamilton=acm.org@metzdowd.com] On Behalf Of Allen
> Sent: Wednesday, March 29, 2017 08:27
> To: Dave Howe <davehowe.pentesting@gmail.com>
> Cc: Crypto <cryptography@metzdowd.com>
> Subject: Spam (7.183):Re: [Cryptography] "Perpetual Encryption"
>
> > if you have (Mi XOR Ri) and (Pi XOR Ri) the logical next step is (Mi
> > XOR Ri) XOR (Pi XOR Ri) leaving you with Mi^Pi
>
> I simplified some--the scheme may use something more complicated than
> an XOR, something like reversibly mixing bits in blocks (as in a block
> cipher)--it's not at all clear though from the whitepaper.
> Fundamentally, this scheme may be equivalent to a block or stream
> cipher with a random IV that is the same length as the message.

Alan, I tend to agree.

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.

2017-04-06 FOLLOW-UP WITH EXPANDED TREATMENT

[ ... ]

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 -

2017-04-06 FIRST TYPO CORRECTION
================================

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

Serious typo.  This should be

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

2017-04-06 ANOTHER CORRECTION
=============================

> 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.
[orcmid]

Another goof.  The last paragraph above should commence

This sketch does not address how the Ci.size and Bi.split values are  ... .

[clearly over-engineering if I can't keep these straight in my head 😊.]

 - Dennis

2017-04-07 CODA
===============

[ ... ]
>
> 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.
>
[ ... ]
[orcmid]

Having provided a Conceptual Pilot, CP, that demonstrates the procedure can
be implemented, we can now argue that, despite all of that, the entropy-based
argument must fail.

STRETCHING OF AN OTP STREAM IS MAYBE NOT AN OTP STREAM?

The perpetual equivocation argument presumes a sequence

  K1 || X1 || X2 || ... || Xn

 derived from "truly random" sources.  If this stream be exchanged entirely
 and independently in secret, it would serve as an OTP.

The proposed methodology depends on *deterministic* derivation of a definite
stream

  XK1 || XK2 || ... || XKn || XK[n+1]

 claimed to be a cryptographically-sufficient OTP stream cipher.  This is the
 cipher stream applied to a same-sized plaintext stream that conveys chunks of
 a message M *and* the X1, ..., Xn.

In theory, the XK1 ... XK[n+1] stream must be compressible to at least the
K1 || X1 ... || Xn stream for a message longer than K1.  Whatever the
feasibility of breaking that, it points out that there cannot be any more
entropy in the key stream than that of the K1 || ... || Xn stream.

In fact, the theoretical compressibility is to merely K1.  That's because the
Xi are conveyed in the plaintext.

  XK1 depends on K1 only,
  XK2 depends on K1 || X1 (as *given*),
   ..., and
  XK[n+1] depends on K1 || X1 (as *given*) ... || Xn (as *given*)

Since the Xi are conveyed in the plaintexts of earlier blocks, they are
effectively unsurprising and it all depends on K1, the only secret not carried
in the ciphertext.


RACING TO THE FINISH

Accepting that an argument from compressibility is not the same as a break, it
should be worrisome with respect to claims of increasing entropy beyond
whatever that means for K1.

There is another problem.  The preamble to the Perpetual Encryption White
Paper states that ideal secrecy is achieved if entropy is added to the
cryptosystem at a faster rate than it is consumed.

It seems clear that if the message, M, is longer than the initial key, K1,
it is not possible to catch up before the last bit of M is transmitted.  It's
not even possible to break even.  (Sound familiar?)  And that's assuming
introduction of the Xi in earlier parts of the plaintext amounts to something,
cryptographically.

Whether the scheme has practical value despite its questionable
characteristics, it would seem that there are better-understood systems, with
hardware-assisted implementations, that also have better general-purpose
application.

 - end -

2017-04-08 CODA ENCORE
======================

> In theory, the XK1 ... XK[n+1] stream must be compressible to at least
> the K1 || X1 ... || Xn stream for a message longer than K1.  Whatever
> the feasibility of breaking that, it points out that there cannot be
> any more entropy in the key stream than that of the K1 || ... || Xn stream.
[orcmid]

I have fallen into the bad habit of using entropy improperly, something I
believe also infects the Perpetual Encryption White Paper.

Also, arguments around compressibility are applicable in all manner of
pseudo-random situations.  I want to explain better why I believe that is
appropriate here.

Consider this in terms of unpredictability/indistinguishability (what
equivocation seems related to) as well.

For me, the key point is that if the stream K1 || X1 || X2 || ... || Xn is
from a "truly random" source then it is not compressible and X[n+1] is not
predictable.  I.e., it qualifies as a One-Time Pad.

The greater the length increase for XK1 || XK2 || ... || XK[n+1] the more it
becomes pseudo-random and suspect as cryptographically-distinguishable from an
OTP.  That's concerning because part of the expansion is for encrypting the
Xi as well as Mi message chunks in producing the XKi-corresponding Ci.  I see
two kinds of difficulties here:

 a. Corruptions of single frames (e.g., single octets) have very serious
    consequences when they apply to octets that are encryptions of Xi frames
    embedded in the plaintext stream, ruining the decryption of C[i+1],
    et.seq.

 b. The assurance that the result of encryption of a message portion is as
    indistinguishable as the corresponding cipher portion may be inadequate
    with respect to equivocation.

>
> In fact, the theoretical compressibility is to merely K1.  That's
> because the Xi are conveyed in the plaintext.
>
>   XK1 depends on K1 only,
>   XK2 depends on K1 || X1 (as *given*),
>    ..., and
>   XK[n+1] depends on K1 || X1 (as *given*) ... || Xn (as *given*)
>
> Since the Xi are conveyed in the plaintexts of earlier blocks, they
> are effectively unsurprising and it all depends on K1, the only secret
> not carried in the ciphertext.
[orcmid]

Put another way, knowing K1 is sufficient to decrypt the ciphertext no matter
what the Xi are.  K1 is sufficient to produce the XKi.  It is difficult to
see how this approaches anything like a cryptographically-indistinguishable
OTP.

Any cleverness of variable chunking and chunk rearrangements strikes me as
not measuring up to what is achieved far better with a highly-trusted block
cipher in most applications.

>
>
> RACING TO THE FINISH
>
> Accepting that an argument from compressibility is not the same as a
> break, it should be worrisome with respect to claims of increasing
> entropy beyond whatever that means for K1.
[orcmid]

Better to say increasing unpredictability, essentially by perturbing RNG2.


*---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--*

                      Copyright 2017, 2024 Dennis E. Hamilton

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

        http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.

*---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--*

 ATTRIBUTION

   Hamilton, Dennis E. Perpetual Encryption Notes, version 0.0.2 dated
   2024-11-10.  GitHub docEng file PerpetualCrypto.txt available on the
   Internet as a version of
   <https://github.com/orcmid/docEng/blob/main/PerpetualCrypto.txt>

*---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--*

  0.0.2 2024-11-10T20:19Z Clean up *.text layout
  0.0.1 2024-09-22T18:42Z Connect to nfoTools nfoLocker
  0.0.0 2024-03-18T19:57Z Initial Capture of notes from email list where I
        provided a simple analysis of how such a scheme might work.


                   ***** end of PerpetualCrypto.txt *****