0
$\begingroup$

We have ciphers that handle small amounts of entropy, such as a 256 bit key for AES; and we have one time pads for enciphering 1:1 entropy, such as a 1GB key for a 1GB file if you could ever harvest enough decent random noise.

Now in theory you would imagine that there is a universal class or model of cipher that can scale smoothly from a single bit of entropy all the way upto a 1:1 one time pad.

If such an algorithm or cipher already exists - what is it called?

$\endgroup$
  • $\begingroup$ Three other regions along that continuum are honey encryption, entropically-secure encryption, and encryption that remains information-theoretically secure against key-dependent messages. $\endgroup$ – user991 Oct 15 '14 at 5:13
  • 2
    $\begingroup$ Note that the one-time-pad is not a cipher, by the modern definition, which requires key size to be fixed for arbitrary or much larger plaintext size. $\;$ I know no existing algorithm answering the question. It seems feasible to build one from existing primitives, but exactly what would be the desired security criteria? $\endgroup$ – fgrieu Oct 15 '14 at 13:12
  • 2
    $\begingroup$ @fgrieu I don't want to narrow the paradigm excessively; but I think the key criteria for genuinely scalable encryption is that an algorithm is honest in regards to information-theoretic security. If there is 1 bit of entropy then there are two (2^1) possible messages, if 2 bits then are 4 (2^2) possible messages, and so on. $\endgroup$ – LateralFractal Oct 15 '14 at 13:27
  • $\begingroup$ The criteria that given ciphertext and $b$-bit key, $2^b$ distinct plaintexts are possible $\;$ a) Can not be reached at all for key/plaintext ratio above 1, even though that is considered in the question. $\;$ b) Is NOT enough to give a useful level of confidentiality for other ratio (proof: consider encryption by XOR with key padded with zeroes up to plaintext length); that criteria can however be a compatible addition to more standard security criteria, at least if we allow about $2^b$ possible distinct plaintexts. $\endgroup$ – fgrieu Oct 15 '14 at 15:12
  • $\begingroup$ @fgrieu I'll drop the side note about key lengths above 1:1 as that's a logistical scenario rather than an algorithmic quality. $\endgroup$ – LateralFractal Oct 15 '14 at 23:53
0
$\begingroup$

Fix a $b$-bit string $k_0$ chosen uniformly at random. Let $k = \operatorname{SHAKE128-256}(k_0)$. Use $k$ as a key for a standard symmetric cryptosystem with a 128-bit security level, like AES-256-GCM.

The number $b$, up to 256, determines the minimum expected cost of an attack on this cryptosystem: ${\sim}2^b$, or ${\sim}2^b/t$ in a multi-target attack on the first of $t$ targets. You can set $b = 1$, and you get essentially no security; or you can set $b = 256$, and you get a 128-bit security level, which is more than humanity has the capacity to break; or you can set it anywhere in between to ‘smoothly’ scale the security.

But you should really just set it to 256, because why would you want anything less than a 128-bit security level if, as the omission of a budget in your answer suggests, you are unconstrained by cost?

$\endgroup$
  • 2
    $\begingroup$ SHAKE-128/256 use 1600-bit Keccak internally, therefore it cannot scale all the way up to OTP. $\endgroup$ – DannyNiu May 18 at 3:33
  • 1
    $\begingroup$ There's no meaning to a security level above 256 bits. I'm answering this question in practical terms, not in fantasy terms. $\endgroup$ – Squeamish Ossifrage May 18 at 4:11
  • $\begingroup$ Not the downvoter, but since when did AES-256-GCM have a 128-bit security level? I was under the impression that the random nonce defeated multi-target attacks. $\endgroup$ – forest May 20 at 0:07
  • $\begingroup$ @forest I generally recommend sequential nonces so you don't have to worry about collisions and can guarantee incorrect implementations will be immediately detected, and I generally recommend 256-bit keys so that you don't have to think about whether multi-target attacks might be relevant. $\endgroup$ – Squeamish Ossifrage May 20 at 0:10
  • $\begingroup$ Thanks, that makes more sense. I've added my +1. $\endgroup$ – forest May 20 at 0:12
-1
$\begingroup$

It's called a stream cipher, with re-keying. If you consider a stream cipher as $ \operatorname{E}_k(m) $, simply set $ \frac{|k|}{|m|} $ to your desired ratio. Then operate and repetitively re-key when $k$ is used up. So a 256 bit key might encipher 1024 bits of message (0.25 ratio). You can even achieve 1:1 for information theoretic security à la one time pad. It's not pretty and not very efficient, but works and is not a million miles away from unsalted key stretching. Clearly you wouldn't want the intrinsic delays of key stretching algorithms. This re-keying (re-seeding) technique is common in many RNG designs like Intel's RDRAND instructions, Raspberry Pi and similar to *nix's /dev/urandom, etc.

This all works mathematically for any $k$ but remember that irrespective of the $ \frac{|k|}{|m|} $ ratio, $|k|$ should really be at least 128 bits. So the cipher needs an internal state of at least 128 bits irrespective of the output length. You risk brute force attacks against smaller re-keys even if the scaling works. It may be honest in regards to information-theoretic security, but immediately leads to the question of why not simply have a conventionally small $ \frac{|k|}{|m|} $ ratio? I'll leave that hanging...

But just to address "if you could ever harvest enough decent random noise" for 2019: You can generate 1GB of entropy in less than 10 minutes with a €3000 commercial TRNG, and as much and as fast as you can write to any SSD with a laboratory TRNG.

$\endgroup$
  • 1
    $\begingroup$ A 256-bit key used to encrypt 256 bits of ciphertext through a stream cipher does not necessarily preserve information theoretic security! Your "ratio" calculations are incorrect and baseless. $\endgroup$ – forest May 19 at 2:34
  • $\begingroup$ @forest Oh- no they're not. $\endgroup$ – Paul Uszak May 19 at 12:08
  • 2
    $\begingroup$ Let's remember to keep comments productive and use them for their intended purpose - if you don't have an objective response to criticism, then don't post anything. $\endgroup$ – Ella Rose May 19 at 16:04
-2
$\begingroup$

I call an algorithm meeting this spec "rolling xor". It's only strong at the one-time-pad level though.

$\endgroup$
  • $\begingroup$ This doesn't really answer the question. $\endgroup$ – mikeazo Jan 30 '15 at 16:08
  • 1
    $\begingroup$ It is no more or less of an answer than the one that was upvoted. $\endgroup$ – Joshua Jan 30 '15 at 16:12
  • 1
    $\begingroup$ Yeah, that other one isn't very good either. $\endgroup$ – mikeazo Feb 2 '15 at 0:58
-2
$\begingroup$

Vigenere matches the description, though its security problems when the key is shorter than the message are well known.

$\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.