4
$\begingroup$

One-Time-Pad is information theoretically secure as long as the random number stream is evenly long or longer than the data stream it encrypts, for a "deciphered" message could have been any message with the same length as the given with the same probabillity. Does the same apply to symmetric ciphers, too?

For instance if I have 1024 bits to encrypt, break it into chunks 128 bits and encrypt it with AES-128, each with a different (assume: true) random key, will that be information theoretically secure just as OTP? Or would a hypothetical algorithm (let's assume it would be as quick as the encryption function) impact the (theoretical) security?

In other words: Does using a symmetric encryption algorithm (such as AES) lower the probabillity of a ciphertext being originated from a specific plaintext even if the used key has "OTP-length" and is completely unknown?

$\endgroup$
  • 2
    $\begingroup$ I don't have a proof but my guts tell me the answer is "no", because it does not seem esufficient that the family of functions $f_k$ used by the generalization of the OTP be all bijective, they also have to satisfy the criteria that $\{ f_k(x) \mid k \in \Sigma \}$ be a permutation of $\Sigma$ for all $x \in \Sigma$ (where $\Sigma$ is the relevant alphabet, e.g. the set of all 256-bit strings). XOR, modular addition and other simple constructs trivially satisfy this through symmetry, but AFAIK it is unknown whether there exist $k_1$, $k_2$ such that $AES_{k_1}(x) = AES_{k_2}(x)$ for some $x$. $\endgroup$ – Thomas Mar 12 '14 at 23:06
  • $\begingroup$ I could be way off, though, because I just confused myself. Anyway good question, looking forward to the answers $\endgroup$ – Thomas Mar 12 '14 at 23:08
  • $\begingroup$ To be fair, though, at the point where you have a truly random (not simply from a seeded CSPRNG), why bother with the overhead of a symmetric cipher like AES instead of simply XOR? $\endgroup$ – Stephen Touset Mar 12 '14 at 23:22
  • $\begingroup$ It's about a QKD solution. The question is, as the QKD keys applied with OTP are theoretically secure, would they also be with IPsec? $\endgroup$ – Marste Mar 12 '14 at 23:27
  • 1
    $\begingroup$ Do you mean Rijndael? $\:$ (AES's block size is 128 bits.) $\;\;\;\;$ $\endgroup$ – user991 Mar 12 '14 at 23:39
2
$\begingroup$

AFAIK, no one has proven that AES on a single 128-bit block with a true-random 128-bit key does not provide information theoretic security (such a proof would probably be the end of AES as it would demonstrate a weakness). OTOH, no one has proven that it does. I suppose it is possible that it does, but such a proof is likely to be extremely difficult. Just look at the simplicity of the ciphers which do provide information theoretic security. The simplicity of the cipher is part of what made it possible to prove. Therefore, due to the lack of a proof showing such a high level of security, and the perceived difficulty of formalizing such a proof, I'm going to have to say the answer is no.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Given $c_i=AES(k_i,m)$, do we know that all $c_i$ are unique for all $k_i$? $\endgroup$ – Stephen Touset Dec 7 '16 at 21:53
  • $\begingroup$ No, and if they were it would imply a weakness in AES: for an ideal block cipher with n-bit keys you'd expect to see a repeated $c_i$ after $2^{n/2}$ $k_i$s. $\endgroup$ – pg1989 Jun 18 '17 at 0:12
  • $\begingroup$ @pg1989 How would that be a weakness? $\endgroup$ – Melab Dec 28 '17 at 23:10
3
$\begingroup$

No, using any keyed permutation with key length equal to the block size reduces the number of possible plain texts by ~1/3

Assume first that AES reasonably approximates a pseudorandom permutation, for each block of the message, the attacker (assuming unbounded computing power) can calculate the plain text for all keys. This is equivalent to throwing 2^128 balls into 2^128 baskets randomly. There will be collisions. The chance that any plain text is not a valid solution is approximately 1/e

filled fraction = 1-((n-1)/n)^n , n=2^128

this converges to 1-1/e

this reduces the effective number of plaintexts by about 1/3 (=0.63 ~= -0.66 bits). The reduction also tells the adversary about the probablity of any ciphertext being correct since about half the remaining plain texts got two hits instead of one with 2x the probability of being correct.

A problem with this scheme is that fooling the observer into accepting a plausible fake message requires solving for the key K which would connect the plaintexts and ciphertexts, fortunately, thanks to the recent SHA3 competition the cryptanalysis to do so has been mostly done.

|improve this answer|||||
$\endgroup$
2
$\begingroup$

If you have a keyed family of $2^b$ distinct permutations $E_k(p) : \{0,1\}^b \times \{0,1\}^b \to \{0,1\}^b$ over $b$-bit blocks, and select an independent, uniform random key for each plaintext block, then your proposed mode is perfectly secure for the same reason that one-time pads are: for any candidate plaintext/ciphertext pair $(p, c)$, there exists a key $k$ such that $E_k(p) = c$. You securely show $c$ to an adversary, because given that $k$ was selected uniformly at random, with the information they have every possible plaintext is equally likely.

We don't even have to assume that the family $E_k$ is pseudorandom for the above to work. For example, $E_k(p) = k \oplus p$ is not a pseudorandom family, but is perfectly secure when used in the mode that you propose. We just need $2^b$ distinct permutations—it doesn't matter what those permutations are!

However, if your blockcipher provides fewer than $2^b$ distinct permutations, then you no longer have perfect security. In this case for some ciphertext/plaintext pair $(c,p)$, there is no key $k$ such that $E_k(p) = c$. A computationally unlimited adversary that observes $c$ can therefore learn that $p$ is not the corresponding plaintext, and this violates perfect security.

So your question comes down to whether your blockcipher has equivalent keys. Some do! For example, the Tiny Encryption Algorithm (TEA):

TEA has a few weaknesses. Most notably, it suffers from equivalent keys—each key is equivalent to three others, which means that the effective key size is only 126 bits.

TEA does have a 64-bit block size, though, so having "only" $2^{126}$ distinct permutations would not render it insecure in the mode you propose. But AES has a block size of 128 bits; therefore if AES-128 has even just one pair of duplicate keys, then your AES-based proposal is not perfectly secure. (See also: "Do all ciphers have equivalent decryption keys?")


So the big lesson here is this: blockciphers are designed to be pseudorandom permutation families, but this property is neither necessary nor sufficient for perfect security in the mode you propose. Apples, meet oranges...

|improve this answer|||||
$\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.