Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

A good block cipher e.g. AES running in counter mode is commonly considered to be secure. Assuming a perfectly random key, one could in this case from $128$ bits generate up to $2^{128}·128$ bits for stream encryption.

However, these bits could evidently have only $1/(2^{128})$ bit of entropy each on the average. Isn't it a paradox that such an encryption could nonetheless be secure?

share|improve this question

1 Answer

up vote 3 down vote

Summary: an entropy argument shows that block encryption in counter mode can't be perfectly secure.

The remark that any block cipher in CTR mode generates a keystream with very low entropy per bit of keystream is correct. That hints CTR mode is not secure against an hypothetical unbounded adversary. In fact that holds as soon as more bits of keystream are used than there are in the key (or sooner): that unbounded adversary could enumerate all the possible keys, and rule out some keystreams as impossible.

This does not contradict that AES128 is practically safe in most but not all situations, against a real bounded adversary.

As an example of why I write "most but not all situations", consider the feasible case where an exbibyte of data (a fraction of a day's worth of global internet traffic) is enciphered with AES-128 in CTR mode; that's $2^{56}$ blocks, and odds that two ciphertext blocks are exactly identical are a low but sizable $2^{-17}$; should that occur, an hypothetical adversary able to detect and locate that equality (which is much more difficult than the encryption itself, but might still be feasible) would have learnt one tiny bit of information about the corresponding plaintext blocks: they can't be exactly identical; and thus, assuming an all-zero plaintext was characteristic of non-activitly, the adversary would have learnt that there has been activity in at least one of the two spots where the equality is detected.

share|improve this answer
But do you consider my figure of entropy correct? If so, what is the magnitude of entropy that a key stream bit would need to have in practice for a more or less secure stream encryption? – Mok-Kong Shen Oct 1 '12 at 12:53
@Mok-Kong Shen: Yes, your figure of $1/{2^{128}}$ bit of entropy per bit of key stream, after $2^{128}$ 128-bit blocks, with a 128-bit key-entropy, seems fully correct to me. But I can't answer the rest, and rather would say that "bit of entropy per bit of key stream" is not a useful indication of practical security. – fgrieu Oct 1 '12 at 13:00
I surmise that it seems anyway difficult to characterize a nice goal of design for stream encryptions, noting on the other hand that the perfect security of OTP is based on the concept of entropy. – Mok-Kong Shen Oct 1 '12 at 13:35
@Mok-KongShen: when considering "perfect security" against an unbounded adversary, rather than "more or less secure" against a practical adversary, then "bit of entropy per bit of key stream" indeed matters: it must be at least 1. – fgrieu Oct 1 '12 at 13:39
Ok, but then how much security measures does one need in order to protect against a "practical" adversary? That's a rather fuzzy and hard to determine matter, isn't it? – Mok-Kong Shen Oct 1 '12 at 13:44
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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