5
$\begingroup$

The one-time pad is often described with a simple XOR cipher.

This is nice for showing the theoretical strengths of the one-time pad, but not so great in real-world scenarios where key reuse is a danger.

So, is it feasible to use an n-bit block cipher with an n-bit key to replace the XOR operation (which itself is a 1-bit block cipher with a 1-bit key)?

So the encryption operation becomes

for each pBlock is n bits of plaintext
     take kBlock as the corresponding n bits of the key
     encrypt pBlock with kBlock as key using the block cipher and the result is cBlock
     append cBlock to the ciphertext

Decryption is the same.

Am I correct that this will make it more resistant (but not fully) to key reuse and known plaintext attacks than using the simple XOR? Or did I add a big vulnerability into the scheme?

$\endgroup$
  • 5
    $\begingroup$ Congratulations, you have discovered block cipher modes of operation. :) $\endgroup$ – fkraiem Mar 9 '16 at 11:32
  • $\begingroup$ @fkraiem they are hardly one time pads though at best those are a stream cipher, All those do is add a bit of entropy to avoid repeats. $\endgroup$ – ratchet freak Mar 9 '16 at 11:54
  • 3
    $\begingroup$ Then please describe more precisely what you mean in your question. A one-time pad, as properly defined, does not use a block cipher, so the obvious answer to the question of whether you can "use a one-time pad with a block cipher" is no. $\endgroup$ – fkraiem Mar 9 '16 at 12:01
  • $\begingroup$ @fkraiem Ah I see where people got mistaken; I meant using a key as large as the plain text (like happens with one time pad) $\endgroup$ – ratchet freak Mar 9 '16 at 12:19
  • $\begingroup$ By its list view, if I'm interpreting this correctly, the the possibilities for 2-bit blocks are all "equivalent" to the trivial ones (bitwise and mod 4), but there are lots of inequivalent possibilities for 3-bit blocks. ​ ​ $\endgroup$ – user991 Mar 9 '16 at 23:07
3
$\begingroup$

Well, no.

What you are describing is ECB mode of operation. ECB mode of operation is insecure as repeats of plaintext blocks leads to repeats of ciphertext blocks. This is a leak of information so it breaks confidentiality. So even if you would leak less information because of key reuse, you would still leak information if it happens.

Furthermore it is possible to find out if a key is (likely) correct by validating a ciphertext block against partial information within plaintext blocks. To that breaks the perfect secrecy provided by a One Time Pad.


I'll try and explain that last section further.

Note that there aren't $2^n$ possible permutations, there are $2^n!$ possible permutations. To be perfectly secure you should allow each one of them (with the same probability, no less).

That would mean that for any sensible $n$ the key size would grow out of proportion. Furthermore, you would have to have a cipher that would map all those keys to exactly one permutation, something that is not true for usual block ciphers.

So even if you have a key of n bits with m < n bits of known plaintext then it is likely that you can tell with a probability higher than $0.5$ if it is the correct one or not, breaking perfect secrecy for the remaining n - m bits.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think the OP is not asking for "classic" ECB mode (encrypt each block by itself with the same key), but rather a variation of ECB mode where you use a different ( / random) key for each block you encrypt. $\endgroup$ – SEJPM Mar 9 '16 at 12:22
  • $\begingroup$ @SEJPM What do you think about it after the adjustment? $\endgroup$ – Maarten Bodewes Mar 9 '16 at 13:35
  • 1
    $\begingroup$ As long as there are no collisions in the block cipher (there is no plain/cipher block pair that have multiple possible keys) and per-block key size is equal or larger than block size then perfect secrecy is preserved assuming no key reuse. $\endgroup$ – ratchet freak Mar 9 '16 at 13:58
  • $\begingroup$ @ratchetfreak: You are correct, but the question stipulates that no key reuse cannot be assumed. $\endgroup$ – Henrick Hellström Mar 9 '16 at 14:07
  • $\begingroup$ Besides, in general you would expect a key to select a unique permutation. But permutations may still share plantext : ciphertext mappings. So your assumption may not hold. $\endgroup$ – Maarten Bodewes Mar 9 '16 at 14:11
1
$\begingroup$

I think Maarten Bodewes' last comment is crucial. Even with uniformly chosen keys, since a random permutation on $\{0,1\}^n$ has roughly $2^n/e$ fixed points, the "block OTP" property will be lost relatively quickly, regardless of key reuse.

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