2
$\begingroup$

I have a couple of related questions:

I read about an estimate, ascribed to Shannon, of the entropy of English text to be between 0.6 and 1.3 bits per letter. The modern day corpus, including the huge and exponentially ever expanding volume of materials accessible via the Internet, is different from the one available a century back. Is there a revised estimate?

If one simply takes two books from one's small private library (that contains e.g. only very common novels) and arbitrarily select two starting points to combine with xor the letters, then the resulting pseudo-random sequence presumably could be argued to have a non-negligible risk of being attacked through brute-force by a knowledgeable opponent. But the actual choice of materials (including especially those via the Internet) to be combined is nowadays virtually unlimited. If one could thus appropriately choose a sufficiently large number of text sources to be combined, wouldn't the result be practically secure for crypto usages in view of the combinatorial explosion of the complexity that the attacker has to deal with? One could certainly also employ some more complex operations than xor and even a couple of different operations either simultaneously or in variations. Are some good schemes in this direction already being used in non-trivial practical applications?

[Added on edit:] A later work of Cover and King give an estimate of 1.34 bit per letter, which implies that appropriately combining 4 text files should lead to sequences of full entropy. Several weeks ago I wrote a software for that but unfortunately, due to a bug in codes used in its design, it had to be retracted for not being satisfactory. I have just released a carefully tested replacement, named TEXTCOMBINE-REV, in which I wrote in Prologue:

What has been achieved by the present software can be tersely summarized as follows, assuming the general case where the text files are sufficiently large:

(1) The generated byte sequences pass, via design specifications of the software, Maurer's universal test and the autocorrelation test for all d in the range [1, 16] as well as the ENT test with an entropy value according to it of at least 7.99 bits per byte. The software is namely coded such that it would give up, reporting failure, after a certain specified maximum amount of processing has been done without finding a solution.

(2) An extensive expermiment of the present author done on all different combinations, totalling 3060 in number, of 4 source materials (of size 600 KB each) taken from 18 different books of English literature downloaded from Project Gutenberg resulted in the following:

(a) No case of failure was ever encountered. On the contrary, the above mentioned processing limit, which is in terms of rounds of certain preprocessing of source materials before they are xor-ed together, was by far not being approached in the experiment. For details, see Epilogue.

(b) The worst case of entropy according to ENT in the experiment was higher than 7.995 bits per byte and the average CPU-time was less than 15 sec on author's PC.

The software (new version 1.1) is available at http://mok-kong-shen.de

$\endgroup$
7
  • $\begingroup$ But since you - obviously - no longer have unconditional security, what advantages does this awkward and complicated scheme have over just using generic cryptographic primitives? $\endgroup$
    – Thomas
    Feb 4, 2013 at 11:58
  • $\begingroup$ For practical applications, one commonly doesn't always necessarily require theoretical unconditional security. No crypto algorithm used in practice is absolutely theoretically secure IMHO. In other words, one does compromises to achieve one's purposes in some presumably optimal way. $\endgroup$ Feb 4, 2013 at 12:30
  • $\begingroup$ Which is exactly what I said. What advantage does your scheme have over, say, using AES? And what advantages does AES have over yours? In your application, that is. $\endgroup$
    – Thomas
    Feb 4, 2013 at 12:43
  • $\begingroup$ Firstly, it could serve other purposes than "directly" for encryption, for example to generate keys for ciphers. Secondly, if it turns out to be a satisfactory way to obtain entropy-rich sequences, than its usage as key stream for stream encryption would also be practically feasible. Awkwardness you mentioned is a rather subjective issue. What really counts would be simplicity and that is the case with the scheme IMHO. $\endgroup$ Feb 4, 2013 at 12:56
  • 1
    $\begingroup$ How is collecting a huge library of texts, and generating something that sort-of kind-of looks random from it, simpler and less awkward than generating 128-256 pseudorandom bits from a well-vetted and easily accessible source of entropy? Your scheme doesn't even let you measure the amount of entropy you're collecting to any degree of accuracy ("entropy" is a lot more than just "english text has 0.6 to 1.3 bits of entropy per character"). $\endgroup$
    – Thomas
    Feb 4, 2013 at 13:00

2 Answers 2

2
$\begingroup$

Shannon's paper Prediction and Entropy of Printed English details the experiment to determine the entropy of English. Without getting into too much detail, it's only really proper to talk about the entropy of a source of information. You can estimate the entropy given a sample of the source's output and it's fair to say that Shannon's method gives an estimate for the upper bound. A more sophisticated experiment would give a lower estimate for the upper bound. Another way to arrive at an upper bound would be to look at the results of a competition to compress a portion of wikipedia which shows that 100M of English can be compressed into 16M.

I'm reminded of a similar scheme I read about which relied on a long stream of publicly available bits derived in this case from digitizing a picture of the surface of the moon. I can't find the reference but I'm sure it would be relevant, although of purely academic interest.

There are no practical schemes that I am aware of which use your idea or anything similar. You would have to ask yourself what security guarantees you're trying to achieve and whether this really is the best way of obtaining them. I believe that it should always be preferable to implement your system using established cryptographic primitives in the prescribed fashion.

$\endgroup$
1
  • $\begingroup$ I meant that, if a good lower estimate is known, one could, to be conservative, use a somewhat still smaller value and thus be able with a rather simply coding to obtain letter sequences that achieve sufficiently high entropy value for practical use. (The main point is simplicity.) $\endgroup$ Feb 4, 2013 at 14:44
0
$\begingroup$

What you've found is the superposition effect due to overlaying multiple entropy streams. I'm very surprised that they pass the randomness tests though. 8/1.34 =~ 6 not 8. They generally have to be from significantly different distributions. I can only assume that the variations in style between authors create adequate difference. Unfortunately 600KB isn't really enough for a Diehard test, but I would expect it to conclusively fail.

The real issue here is that what ever you use your entropy sequence for, it relies on the not so cunning and discredited security through obscurity. The true cryptographic key to the encryption is your choice of books. It's not their content; that's fixed and in the public domain.

Let's assume you've done something more sophisticated than simply XORing the sources together. Say you Pearson hashed them so that order was preserved. 4 from 18 leads to 73440 permutations. That's an equivalent key length of ~16 bits if someone knows you've done it this way. And unfortunately they will know as you just told us. What might have been if only you'd kept stumm! However, you xored them didn't you [ C(18,4) = 3060 ]? Therefore the true key you used was only ~12 bits.

I won't say anything more regarding alternative true or pseudo entropy sources. I'll let your 12 bit key encryption speak for itself.

PS. I'm not sure where you get the 0.6 bits /letter number from. I'd appreciate a reference as I can't find anything near that value. Even Shannon's 1950 paper only got down to ~1 bit /letter and he admitted sampling errors. There is this from

entropy

Thomas Schürmann and Peter Grassberger, Entropy estimation of symbol sequences.

I can beat this chart, and achieve 1.68 for Shakespeare and 1.73 for War & Peace using strong compression. That's still miles away from 0.6 however...

$\endgroup$
5
  • $\begingroup$ I don't understand your last paragraph. You achieve 1.68 etc. Aren't these higher than 0.6? My 0.6 came from Schneier's cryptography book. $\endgroup$ Sep 5, 2017 at 16:56
  • $\begingroup$ @Mok-KongShen Schneier's a bit of a showman isn't he? Thanks for the reference though. I'll look, but I don't believe it at face value. Four people have independently achieved ~1.7. And Shannon estimated ~1 with errors. Of course it depends on whose English, and you could argue that the Bible isn't written in English. $\endgroup$
    – Paul Uszak
    Sep 5, 2017 at 17:09
  • $\begingroup$ Allow me a 2nd question. Why do you consider the true key is only 12 bits (i.e from 3060). That would IMHO be true if the adversary knew which 18 books I use, but there are a really huge number of books from Project Gutenberg and books from other sources. Further, for each book I can cut away head and tail parts, rotate it, choose a starting point (a utility is in my software for doing these) and these data are also unknown to the adversary. BTW, Schneier has given literature references to Shannon's values. $\endgroup$ Sep 5, 2017 at 17:14
  • $\begingroup$ @Mok-KongShen Well the 12 bits arose from the details in your question. I guess if you get more books and manipulate them (randomly - how?) then it's more secure. But to what practical end? Ultimately if you want real true, God can't predict it randomness, shove a diode up an Arduino. $\endgroup$
    – Paul Uszak
    Sep 5, 2017 at 23:16
  • $\begingroup$ I explained in the Prologue of my softwawe that it is a viable, under circumstances valuable, alternative to other well-known means. Analogy: A bicyle for a car owner. Another purpose is to exterimentally give support to an entropy estimate given by Cover, akin to what you do to determine entropy in texts. My earlier comment on 0.6 from Schneier's book is not correct. I previously looked up in a reference to Shannon given by Schneier and found a smallest lower bound given on a page there to be 0.6. $\endgroup$ Sep 7, 2017 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.