2
$\begingroup$

We all know the OTP is unbreakable and we all love the OTP (judging by the amount of question on this site).

The strength of the OTP is not that it is unable to find a word without the key but you can find any word. Now obviously if we could create a cipher which output would be only letters and several keys would output several grammatically correct sentences (or what ever output you would expect to be a valid output). But is such a thing possible?

I find it odd the OTP is the only one with this characteristic. If we would take AES with a 128 bit key and encrypt hello world" with AES-CBC and key "Acknowledgement" (nvm the IV)

9e 6c d3 86 33 aa fa 09 59 b1 75 86 85 e1 5a ea

why wouldn't there be keys in the 128 bit space which could decrypt this to valid plain texts other than hello world.

With my above example if there are multiple valid decryptions for the given ciphertext then it won't be every single possibility which would make it weaker than the OTP since an attacker could sort the valid plain text on relevance. But when the valid plain texts are many (just not all possibilities) the chances of an attacker finding the right one are negligible.

lets disregard OTP for a second.

Is it possible to create a cipher with the following requirements: For each N keys and X valid plaintexts there is a X/N chance of the decryption of the ciphertext resulting in a valid plaintext. Where 1 key can be used to encrypt multiple plaintexts where the key is smaller than the overall lenght of all plaintexts without posing a weakness. (similar to a block cipher) and X/N is sufficiently large for it to be impossible to determine what the correct plain text is.

Example:

Key K = "secret"
Plaintext p = "hello"
Plaintext p2 = "noway"
Ciphertext c = "aqfum"
RandomKey N = "wrong"

Encrypt(p, k) = c;
Decrypt(c, N) = "array"
Decrypt(c, N2) = "pozdi"
Decrypt(c, N3) = "bonus"

Encrypt(p2, k) = C2 = "almost"

Scheme(C2, C) != K

Has anything ever been tried or am I wrong in assuming that this is possible with reuse of the key?

NOTE
With cipher I mean an algorithm in the sense of something similar to a block cipher.

$\endgroup$
  • $\begingroup$ You can decrypt the given ciphertext with other keys and get "possible" plaintexts, but it is infeasable to find such a key for a given plaintext different to the first plaintext - that is intended. $\endgroup$ – Nova Apr 30 '15 at 13:07
  • 1
    $\begingroup$ "we all love the OTP" Wrong. No one does, becaus 99% of the time people don't get that OTP is only of theoretical interest. It has (almost) no practical applications. It's like saying "Stop killing animals for their meat! If you want meat, buy it from the supermarket." OTP shifts the problem from encryption to key management. That's it. $\endgroup$ – tylo Apr 30 '15 at 13:23
  • $\begingroup$ @tylo i wanted to create a popular intro to my question, but you're quite right. $\endgroup$ – Vincent Apr 30 '15 at 13:34
  • $\begingroup$ @tylo There are cases where it's useful, especially before there was goot not-secret crypto. $\endgroup$ – cpast Apr 30 '15 at 22:07
  • $\begingroup$ @cpast That's why I said "almost". In very specific circumstances, it can be useful. For example if you have the possibility to exchange arbitrary amounts of data now safely, and want to exchanges messages later. However, key management and secure storage are still major issues, and many of the "oh let's use OTP" ideas disregard this entirely. $\endgroup$ – tylo May 4 '15 at 10:32
2
$\begingroup$

You need to understand that any variation on the OTP would ultimately be equivalent to the OTP security-wise, since it is unconditionally "secure" (the ciphertext leaks zero information about the plaintext or the key), and so you'd just making it harder to compute for now reason. So, sure, you can use the OTP, or some variant thereof, on 128-bit messages with a 128-bit key, but once you use up that key it's gone. With AES you can encrypt way more data with a single key.

So, looking at your question, you could, conceivably, design a cipher that takes in a 128-bit key and a 128-bit plaintext block, and encrypts it so that the 128-bit ciphertext provides exactly zero information on the plaintext or key (making it unconditionally "secure"). AES probably does not quite satisfy this condition, but the OTP does, and you can certainly design (redundant; see above) variants that could achieve the same thing. But the point is that you can only encrypt a single 128-bit block of plaintext with that 128-bit key. Encrypt any more than that, and the multiple ciphertext blocks must together leak sufficient information on the plaintexts for a (computationally unbounded) attacker to retrieve the corresponding key, no matter what cipher you use.

Basically, there is nothing to improve on; what you are asking for is impossible, and you cannot "work around" the OTP's key reuse problem by chopping the plaintext up into 128-bit (or any size) blocks.

$\endgroup$
  • 1
    $\begingroup$ @VincentAdvocaat I have looked at your updated question. The answer is still no, for the same reason: if your key is $k$ bits long, there is no way to encrypt more than $k$ bits of data without losing unconditional security. Encrypt even a single bit more and the ciphertext begins leaking information about the plaintext (and hence the key) and the cipher is no longer unconditionally secure. $\endgroup$ – Thomas Apr 30 '15 at 14:00
  • 1
    $\begingroup$ Hmm so unconditional security is only possible where the plaintext is smaller than the key (and of course the key is completely random). bummer, so all my theoretical algorithm would do is achieve security through obscurity. $\endgroup$ – Vincent Apr 30 '15 at 14:03
  • 2
    $\begingroup$ @VincentAdvocaat Smaller or equal in length to. And, yes, unfortunately. But fear not, modern cryptography has evolved past the OTP, your data can be made secure in practice! Just not unconditionally :-) $\endgroup$ – Thomas Apr 30 '15 at 14:04
  • 3
    $\begingroup$ @VincentAdvocaat We will adapt; necessity is the mother of invention, especially when it comes to protecting sensitive information. Google for "post-quantum cryptography" if you're interested in learning more! $\endgroup$ – Thomas Apr 30 '15 at 14:09
  • 2
    $\begingroup$ @VincentAdvocaat The current expectation is that QCs: 1) halve the effective key length of symmetric ciphers (so 256 bit ciphers should still be fine). 2) totally break RSA, DH/DSA and ECC 3) Only offer a small advantage (similar to the one against symmetric crypto) against certain more experimental asymmetric algorithms. So the common conclusion isn't switching to OTPs, but to develop those alternative asymmetric algorithms until they're ready for production. $\endgroup$ – CodesInChaos May 1 '15 at 9:39
1
$\begingroup$

With a OTP you need at least as much key material as you have plaintext. See Thomas' answer. That means you need a way to distribute as much key material as you have plaintext, securely. If you can do that, you can just distribute the plaintext over the same channel, and dispense with the OTP.

The one situation where OTPs make sense is in time-delayed communications: eg a field agent has a book of pads, and uses them one at a time to send messages as needed. They take the code book with them when they leave the secure region to go to the field assignment.

$\endgroup$
  • $\begingroup$ Then if they capture the agent they will have his notebook and can decipher all intercepted messages, but ye i get OTP has no real implementations. $\endgroup$ – Vincent Apr 30 '15 at 14:23
  • $\begingroup$ @Vincent Generally, agents burn each pad after they use it, so they can't decipher old intercepts. $\endgroup$ – cpast Apr 30 '15 at 22:19

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.