Is just a bit of random, “fully random”?

I understand that hashing a datetime is a pseudo-random number, and not good in a security context.

But what about hashing a datetime plus a truly-random but constant string (just a string that an "attacker" could not possibly guess)?

This is not a question for a practical implementation, just a theoretical question.

Is pseudo-random plus a bit of "true random", "fully-random"?

(p.s.: I'm not a security specialist, so please don't use overly-complex terms if possible.)

-

migrated from security.stackexchange.comJul 27 '12 at 13:11

This question came from our site for Information security professionals.

Let's look at this from the bottom ("what is random?") to the top (is that secure?).

When we talk about "random" in cryptography we almost always prefer to talk about "entropy". The intuitive and concise definition of cryptographic entropy is that it is a measure of how much information the attacker does not know about the target message. When you hear about, for example, "128 bits of entropy" in cryptography, it essentially means that the message has 128 bits of information that the attacker is expected to not know about, and thus a total $2^{128}$ possible values that, from the attacker's perspective, could be the one they're looking for. For example, a 100-bit string might be generated by always prefixing a 1 and then having the remaining 99 bits filled in from a perfect random number source. This string would have 99 bits of entropy, since the first bit is known by the attacker to always be 1 and thus all strings starting with 0 are invalid. (This is all fairly simplified, by OP's request.)

So then, what's the entropy of "pseudo-random"? A pseudo-random string is just something that looks random (ie, passes all good tests for randomness) but is deterministically derived from an input. So the amount of cryptographic entropy in a pseudo-random string is actually the amount of entropy in the seed input that was used to create the pseudo-random string. This is because if the attacker can determine the seed, then they too can generate the resulting pseudo-random string. So from the attacker's perspective, the number of possible pseudo-random strings is simply the number of possible inputs that could have been supplied. (This fits with the above notion of cryptographic entropy.)

Why the distinction between "entropy" and "random"? Because we have have strings that look very random but actually have low entropy. (Such as a pseudo-random generator that always looks random regardless of the input.) In cryptography we don't usually care how random a secret looks but rather how hard it would be to re-create, and as far as vocabulary goes, "entropy" is more explicitly a measure of the source of the string, not the content. (However, for what it's worth, the terms "random" and "very high entropy" often seem to be used interchangeably amongst those familiar with the concepts.)

So what does your proposed scheme do with entropy? Your time-stamp will have some entropy, but it's unclear how much. The attacker will likely know something about the time-stamp (such as the year it was generated) but not everything (such as the exact millisecond). So the entropy won't be maximal or minimal for that source. For your secret string, it will have entropy because it has some information unknown to the attacker. If it's a string you hand-designed then it is highly unlikely it has full entropy, but it does likely have some entropy if you put any effort into designing it. (Without knowing more we can't estimate how much entropy your string has.)

The fact that you hash the concatenation of your strings does not change the amount entropy. The attacker still needs only to guess the input to the hash function. The hash will act similar to the pseudo-random generator above in that it will provide random-looking output that conceals the content of the input. But the attacker's job is simply to guess the input to that hash and so the measurement of cryptographically secure entropy is the same despite the use of the hash. The same number of original message possibilities remain, from the attacker's perspective.

To address your italicized question: A message that is "fully random" is going to have entropy the same size as the message. For example, a truly random 128-bit key will have 128 bits of entropy, but 128-bit key with 127 bits of entropy is probably not going to be considered "fully" random.

But practically speaking, we actually don't really care about having full entropy, we care about having enough entropy. A 128-bit string with 128 bits of entropy is, in theory, just as secure as a 500-bit string with 128 bits of entropy, especially if you're going to put it through some sort of function like a hash or a PRG. If security is your goal, be primarily concerned with how much entropy you collect and less so with how many bytes it took to do so.

The summary here is that a string has at least as much entropy as its highest entropy source. If you concatenate a weak string with a strong string, your result is a strong string. If you have a weak string and add a strong string and hash the two, the hash output should be a strong string.

-
Ah, certainly accepted, this is an excellently detailed answer :) I'm curious however. What about two (different) strings with "no entropy", hashed (separatedly) alongside a common string with 128 bits of entropy (and resulting in two 128-bit hashes). Will both have 128 bits of entropy, or 64 bits, or something else? –  Camilo Martin Jul 27 '12 at 18:49
If you view the separate hashes side-by-side they will only have 128 bits of entropy total because you need only discover 128 bits in order to learn their combined initial state. Taken individually, however, we would probably still think of each hash as the having 128 bits of entropy because that's the work factor for an attacker. No matter which string they choose they still have 128 bits of work to do. But since their entropy is not, shall we say, "distinct", you can't add the entropies when you combine the strings (so you don't get a paradox by copying and concatenating entropy). –  B-Con Jul 27 '12 at 21:47
I see, I think I understand it better now. Thanks! –  Camilo Martin Jul 28 '12 at 9:43
But what if you had a lot of pseudo-random numbers with just a bit of random numbers actually generated from something like static noise? if someone can't guess the random part, wouldn't that mean he/she would not be able to guess the whole thing either? I don't know much about the subject but just /dev/urandom seems pretty unbreakable by anything non-brute. –  Camilo Martin Jul 27 '12 at 13:34