-2
$\begingroup$

Hi i am trying to build a key stream generator for my homemade stream cipher.The key stream output has a close to maximum entropy value and a large periodicity. What does it take for this generator to be secure from various attacks?

What does a high entropy mean security wise? I am confused with this at the moment.

Thank you for spending your time.

$\endgroup$
7
  • $\begingroup$ Your stream cipher is supposed to generate the key stream, not consume it. For that it needs to have a (relatively small, say 128 to 256 bits) key that is indistinguishable from random to an adversary. It can be generated using a secure random bit generator, key agreement, key derivation etc. depending on how and where the stream cipher is used. $\endgroup$ – Maarten Bodewes Jul 20 '17 at 21:13
  • $\begingroup$ I am sorry if this is a dumb question.But what do you mean by 'generate the key stream, not consume it' ? My stream cipher is fully capable of generating a different key stream for each different key.The key stream is generated and stored separately from the plain/cipher text and then used when needed by the program, is that what you mean by consume? $\endgroup$ – Christian Shelton Jul 20 '17 at 21:22
  • 1
    $\begingroup$ You are trying to "build a key stream generator", but in general, that's what a stream cipher is itself: a stream cipher is a key stream generator. So the question becomes what are you asking for? Are you asking if your stream cipher is secure or are you asking how to generate keys for your stream cipher? $\endgroup$ – Maarten Bodewes Jul 20 '17 at 21:34
  • 4
    $\begingroup$ output has a close to maximum entropy value - what do you mean by entropy value? And how are you measuring it? $\endgroup$ – Ella Rose Jul 20 '17 at 21:51
  • 3
    $\begingroup$ The only way to really know how much security your stream cipher has is to write a paper and ask knowledgeable people take a look at it. Or you could study cryptanalysis yourself and apply attacks on other stream ciphers to your cipher. No generic tool will give you an answer on how strong your cipher / generator is. $\endgroup$ – Maarten Bodewes Jul 20 '17 at 23:07
5
$\begingroup$

Entropy is a property of a physical process or a state of knowledge, not a property of a deterministic function such as a stream cipher, or of a value such as a specific password.

A stream cipher—a deterministic mathematical function—is considered secure if an adversary who does not know the $k$-bit key chosen uniformly at random and can only do a limited amount of computation, but has seen some sequence of output from the stream cipher, can't guess the next bit with probability better than $1/2 + n/2^k$, where $n$ is the number of times they can evaluate the stream cipher within their computational limits.

The adversary's state of knowledge has min-entropy $k$ bits in this case: the key is one of $2^k$ possibilities, and each possibility has equal probability $1/2^k$ as far as the adversary knows. Without knowing any cryptanalytic technique to break the stream cipher, the adversary's best strategy is to guess the key correctly with $1/2^k$ chance of being right, compute the stream cipher, check to see whether it produces the observed outputs, and if so guess the next bit it produces; if the key is wrong, the adversary's guess for the next bit is no better than a fair coin toss.

This strategy sounds stupid. But statistical tests of random number generators such as dieharder use an even stupider strategy than what the adversary's best strategy is in the generic case: they hypothesize some generating process with simple deviations from uniform, such as a different frequencies of one bits and zero bits, and typically perform a frequentist statistical test for the hypothesis. These tests are stupider because unlike the best generic attack on a stream cipher, they are written without even the generic knowledge that the output is produced by a stream cipher with an unknown key that a smarter adversary could evaluate with any candidate key.

Sometimes cryptanalysts find better attacks. For example, within days of the original publication of RC4 on sci.crypt, Bob Jenkins reported, in a post dated 1994-09-16 with message-id 359qjg$55v$1@mhadg.production.compuserve.com, a technique to predict the next bit with significantly better probability using a computation that was possible to do on a 1994-era laptop—thus breaking RC4, which would go on to be used in practice for two decades before anyone in a position to make decisions decided that it was a bad idea for TLS. But seldom is a seriously proposed stream cipher so hopelessly broken that generic statistical tests for random number generators like dieharder make a better attack.

In cryptography engineering, it is expedient to treat every $\ell$-bit output of a secure stream cipher under a key not known to an adversary as if the adversary's knowledge of it had, a priori, at most $\min(\ell, k)$ bits of min-entropy independently. This abuse of language is justified because a real computationally bounded adversary's best guess about the stream cipher output is, in practice, essentially the same as if it really were $\min(\ell, k)$.

We usually choose $k$ so that $n/2^k$ is negligible for any realistic values of $n$—e.g., if we pick $k = 100$, then we probably thwart any adversary whose energy budget for computation isn't enough to boil Lake Geneva. Standard cryptography errs on the side of safety by picking $k \geq 128$. Sensible cryptography also avoids multi-target attacks and potential future quantum cryptanalysis by picking $k \geq 256$.

$\endgroup$
3
  • $\begingroup$ Boiling Lake Geneva should take about $2^{99}$ SHA-256 invocations using custom hardware, not $2^{80}$. (Using SHA256 because getting efficiency data is easy for it) $\endgroup$ – CodesInChaos Jul 21 '17 at 13:38
  • $\begingroup$ Oops. You're right: I erred on the wrong side of that estimate. I should have said, say, $k = 100$ or picked a lower cost like boiling an Olympic-size swimming pool, which Lenstra figured to be around a 65-bit security level. $\endgroup$ – Squeamish Ossifrage Jul 21 '17 at 15:06
  • $\begingroup$ Also I suppose I should clarify that the success probability is bounded not by $1/2 + 1/2^k$ but rather by a function of the amount of work the adversary can put into it, say $1/2 + n/2^k$ for the cost of $n$ trials, so we usually pick $k$ large enough that for any imaginable values of $n$, $n/2^k$ is still negligible. $\endgroup$ – Squeamish Ossifrage Jul 21 '17 at 15:16
2
$\begingroup$

Starting at the end, high entropy (unpredictability) can mean two things with a key stream generator.

Firstly, you can measure the entropy of the generated bit stream coming out of your code. If it's maximum, it's 1 bit /bit, 8 bits /byte or 100% depending on your measurement scale. I take it you allowed for the stream being ASCII rather than binary. These entropy values will mean that your stream is totally random and unbiased. I'm unfamiliar with cryptool, but I hope that it doesn't use the basic Shannon entropy formula as that doesn't really work if there's any form of correlation within the test sample. I've only found compression estimation to be reliable for unknown data samples. Bias /correlation allows prediction which broke the RC4 cipher. Not sure how you determined periodicity. That can be very hard and is not always evident by inspection. And empirically measuring periodicity can also be very difficult.

If you have a sufficiently large sample of (binary) stream data, you could use something like dieharder to check the entropy quality of data. Even ent is reasonable for files up to 2GB.

Secondly, there's the entropy of the seed for the generator. Random looking output is useless if your generator started from a 32 bit seed. That would mean there were only 2^32 possible sequences at best. With bad seeding /algorithm Finney like states (RC4) can develop truncating the length of the output cycles. Consequently, the maximum cycle from a 32 bit seed might only be 2^16. So it is suggested that the seed for the generator should be at least 128 /256 bits of entropy. If you can't input this directly and are using seeds like "My birthday" then you should at least use a key derivation algorithm like Argon2 or bcrypt to introduce a long time delay trying when trying to brute force your password.

It's also surprisingly difficult to determine the entropy of a password. The difficulty extends well beyond the simple algebraic calculation of it's entropy. Social and psychological factors come into play as well as which characters you used, or how many letters. This is where social engineering attacks can be successful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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