<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">On Sat, 18 Jul 2020 00:41 +0100, Peter Fairbrother wrote:<div class=""><blockquote type="cite" class="">On 13/07/2020 16:43, Arnold Reinhold via cryptography wrote:<br class=""><blockquote type="cite" class="">Terakey(tm) is a cipher that offers confidentiality properties provable <br class="">from first principles. It employs a shared secret key substantially <br class="">larger than the anticipated volume of message traffic. <br class=""></blockquote><br class="">Ie an OTP.<br class=""></blockquote><div class=""><br class=""></div>Not quite. One-timeness is the issue we are dealing with. See below.</div><div class=""><br class=""><blockquote type="cite" class=""><br class="">Key bytes are<br class=""><blockquote type="cite" class="">extracted pseudo-randomly from the large key, using a message indicator <br class="">as the seed. <br class=""></blockquote><br class="">What is the advantage of the pseudo-random selection? That two stations <br class="">can use the terakey using some secret shared-to-them-only key to the <br class="">PRNG without any other stations seeing that traffic? [3]<br class=""></blockquote><br class=""> [moving your footnote in-line:]</div><div class=""><blockquote type="cite" class="">[3] that doesn't seem to be in your proposal, but I am assuming. If it <br class="">isn't then I see no advantage - bookeeping is reduced to "don't reuse <br class="">key" and if eg a part of the terakey is allocated to station 1 the <br class="">station just uses the next portion of its part for sending its next message.</blockquote></div><div class=""><br class=""><blockquote type="cite" class="">Well we know that the other stations know the secret terakey, so as far <br class="">as they are concerned the problem is reduced to breaking the PRNG.<br class=""><br class="">That may be a little harder because of the added (I presume) XOR with a <br class="">selection from the OTP, as some methods may not work; but it is not <br class="">necessarily any harder.<br class=""></blockquote><div class=""><br class=""></div><div class="">The purpose of the PRNG is to generate a pad for encrypting each message. Ideally, one would want a one-time pad, but Terakey does not guarantee zero-reuse, instead it generates pads that promise individual byte reuse will be rare, if you like, a mostly one time pad (MOTP). My paper proposes various ways of dealing with the rare reuse. (<a href="https://www.researchgate.net/publication/342697247" class="">https://www.researchgate.net/publication/342697247</a>)</div><div class=""><br class=""></div><div class="">Terakey is intended to provide confidentiality in two situations, key holders vs. non-key holders, and between pairs or groups of key holders (for privacy or compartmentalization). For confidentiality between key holders and non-key holders (arguably the more important case), confidentiality is based on first principles, without any reliance on mathematical conjectures. For compartmentalization, security also depends on the PRNG, as you point out. My paper suggests using public key methods to agree on a seed for compartmentalization purposes, and for forward security, but, as you say, any method to agree on a shared secret will do.</div><div class=""><br class=""></div><div class="">However, even with a cryptographically weak PRNG, say one whose state is recoverable from N known outputs, it is not easy to recover the state as used in Terakey. Suppose Alice sends Bob a new password and Mel gets hold of the cyphertext. And suppose further that the standard form for transmitting a password has lots of boilerplate, so Mel knows most of the plaintext and hence the cypherbytes used to encrypt a large part of the message. With a one terabyte Terakey, there are about 4 billion possible PRNG outputs that could produce each 8-bit cipherbyte. If N > 3, trying all combinations in order to find the state that produces the known cipherbyte sequence has a work factor of least 2^128. </div><div class=""><br class=""></div><div class="">There are two cases where a stronger assertion for compartmentalized security among key holders is possible.</div><div class=""><br class=""></div><div class="">1. When Terakey is used for distribution of symmetric keys. This would be the use case where Terakey is compared with Quantum Key Distribution. In both instances there is a presumption that the symmetric cipher can be relied on, at least with frequent key changes. Then that same cipher's use as a PRNG would at least as secure, since each seed is a new key.</div><div class=""><br class=""></div><div class="">2. Using Terakey itself as the PRNG (an idea stimulated by this discussion), After selecting a Terakey byte to use as the cipher byte, use the subsequent 6 bytes to address the next cipher byte. (6 bytes can address up to 280 terabytes). Since most mass storage does block reads, this would be fast, The only downside is that under the most conservative assumption that any Terakey byte previously accessed is compromised, this PRNG uses up Terakey seven times faster than using a conventional PRNG, but mass storage is cheap and getting cheaper.</div><div class=""><br class=""></div><blockquote type="cite" class=""><br class="">And having multiple stations all in possession of the same secret <br class="">terakey is a huge single point of failure - the probability of a <br class="">secret's compromise is, inter alia, proportional to the square of the <br class="">number of people who know it. [8]<br class=""></blockquote><div class=""><br class=""></div>You are correct that a shared secret is a single point of failure. There are many other single points of failure in our current security arrangements, conjectures on the difficulty of factoring and discrete logarithms, signing keys used by software vendors, CA root keys, private keys of government officials, etc. Because of its large size, logically and physically, a Terakey is more easily protected than conventional symmetric and asymmetric keys. I would envision each Terakey would be housed in a secure container with tamper detection and alarms, with one copy and a backup at each location. An interface processor could monitor the rate at which key bytes are extracted and sound an alarm if the rate exceed a threshold. </div><div class=""><br class=""></div><div class="">Terakey is not a PKI replacement. I don’t envision it being used to protect very large networks. More like different offices of an international bank, a large software organization with multiple locations, or coordinating security between different ISPs and browser makers. Multiple users at each site could use the same Terakey module. If nothing else, Terakey could serve as an independent secure communication method to facilitate rebuilding in the the event of a major system collapse or cyberattack.</div><div class=""><br class=""></div><div class=""><blockquote type="cite" class=""><br class=""><br class="">Two messages can occasionally use the same<br class=""><blockquote type="cite" class="">key byte, violating the one-time use restriction. That risk can be <br class="">quantified and various ways are proposed to deal with it.<br class=""></blockquote><br class="">So how do you analyse that? Just probability of collisions? If that's <br class="">all, who's to say the pseudo-random generator doesn't kick out <br class="">collisions at a more-than-random rate, or in some pattern? You have to <br class="">analyse the PRNG as well.<br class=""><br class="">And if you then have a cryptographically secure PRNG …</blockquote><div class=""><br class=""></div>Yes, probability of collisions. There is extensive literature on the statistical properties of PRNGs. A PRNG with good statistical properties need not be secure and there are many examples. In addition to theoretical analysis, many PRNGs have been subjected to exhaustive empirical tests, some of which could be incorporated as self-tests in a Terakey system. </div><div class=""><br class=""><blockquote type="cite" class=""><br class="">Going from the provably-secure OTP to analysable (if it is analysable, <br class="">which I doubt) doesn't seem like much of a gain.<br class=""></blockquote><div class=""><br class=""></div><div class="">Here are a few Terakey advantages I see:</div><div class=""><br class=""></div><div class="">1. Elimination of each station's need to track pad usage with absolute reliability (not so trivial, systems do crash, malware could move back the pointer). </div><div class=""><br class=""></div><div class="">2. The ability to easily create private channels between any pair of key holders, again without bookkeeping, </div><div class=""><br class=""></div><div class="">3. New stations can be added without coordination with all the other key holders, and, for the same reason, a backup Terakey can be brought on line without requiring a transfer of state from the previous Terakey system.</div><div class=""><br class=""></div><div class="">4. For straight OTP, one has to provision enough pad material for each station. In a crisis where one staton sees very heavy traffic, there would be no easy way to re-provision if they ran out of key. Terakey degrades gracefully and all the key material is effectively available to the stations that need it most. </div><div class=""><br class=""></div><div class="">5. As an alternative to QKD. One has to admire QKD from an esthetic standpoint, finding a practical use for one of the most bizarre predictions of Quantum Mechanics, but an alternative that does not require precision optics and cryogenic refrigeration is at least worth considering.</div><div class=""><br class=""></div><div class=""><br class=""></div>Arnold Reinhold</div></body></html>