2
$\begingroup$

Since I learned about one time pads in last security lecture, I'm quite fascinated how easy the concept is, but how it still is absolutely safe.

Learning from implementing a multi time pad attack, an OTP is not safe if the key is reused. I understand why this is the case. Also encoding large messages requires a large secret, so I tried to think about, how to solve this.

This is what I came up with:

Consider we have a Hash Function $H:= A^k \rightarrow A^l$ were $A$ is an alphabet, and $k$ and $l$ are arbitrary lengths. For example we can use md5 for my purpose. Next we have an secret $s_0$ with a length that is not sufficient to encode our message $m$. What if when I run out of characters/bytes of my secret to encrypt my message, I'll take the next characters/bytes from $s_1 = H(s_0)$. I could then repeat that process until I have a sufficient length of the secret $s_0 + s_1 + ...$.

Also a possible variant would be to generate $s_{i+1}$ by taking the concatenation of the hashed characters of $s_i$.

Example: $m = thistextistoolongforthesecret$ , $s_0=short$. I can encrypt t with s, h with h, and so on until I have no more characters left for the e. I would calculate $s_1=4f09daa9d95bcb166a302407a0e0babe$ (md5). Then I could use the 4 of $s1$ for encryption of the e.

What are the security implications of this? I have the feeling that this has some serious downside, that eventually will lead to a possible multi time pad attack, but I can't show any reason for that. My knowledge is only superficial, since I only heard about OTP 2 days ago.

$\endgroup$
  • $\begingroup$ As far as my research goes this would describe something that is called a stream cipher but a OTP by definition has a random secret with the length of the message. So my idea would be against the definiton of an OTP? $\endgroup$ – Strernd Nov 10 '17 at 18:51
  • $\begingroup$ Indeed… what you are describing is not a one-time-pad. Related (if not dupe): Mathematical formula for switching the key for OTP? The closest your description comes to is a hash-based stream cipher; and it's a bad one too (not only from a security perspective). You should at least use a HMAC construction, or simply use what would be logic — a dedicated stream cipher like ChaCha20 or a block cipher like AES in CTR mode. To avoid a long explanation, let me just say there are multiple reasons OTP is not used in practice $\endgroup$ – e-sushi Nov 10 '17 at 23:33
  • $\begingroup$ For encrypting messages longer than the secret we use different modes of operation. As e-sushi mentioned, you are intuitively aiming for it. For proper encryption you are still missing a key derivation function (don't use a password as a key) and a nonce. $\endgroup$ – gusto2 Nov 11 '17 at 8:01
5
$\begingroup$

Say the adversary is giving you $m_0$ and $m_1$, two arbitrary messages. You draw a random $sk$ and a random $b\gets\{0,1\}$ and output $E_{sk}(m_b)$.

So the adversary takes $ct=E_{sk}(m_b)$ and computes the XOR between the first $n$ bits of $ct$ and the $n$ first bits of $m_0$ (where $n$ is the original key length). Then, he does the same thing for $m_1$, so now he has two options for the secret key, $sk_0$ or $sk_1$. So far everything is good, because they are both equally possible, but now the problems begin: the adversary computes $md5(sk_1)$ and $md5(sk_2)$ and XOR the results with the bits $ct[n+1:n+\texttt{md5-length}]$. With a very high probability, only one of the options will make sense, meaning it would be the bits $m_i[n+1:n+\texttt{md5-length}]$ of some message, so he will know what you encrypted.

$\endgroup$
  • $\begingroup$ I can follow what you posted. But to me the premise does not make sense. Why would the adversary give me two messages? By having an $s_0$ of a sufficient length, the search space for all possible messages would be incredibly large. It still means that this is doable by exhaustive search, but isn't this secure in practice? $\endgroup$ – Strernd Nov 10 '17 at 18:48
  • $\begingroup$ What is your definition of security? Even if our attacker knows that we were asked "are you going to bomb them tomorrow?" and he knows that we can only reply with "yes" or "no", we still wouldn't want him to know what we sent. (this is something that OTP gives) I think this is a really common and basic definition. en.wikipedia.org/wiki/Ciphertext_indistinguishability By the way, there is a way to produce longer "randomness" from short secret keys, using pseudo-random generators. en.wikipedia.org/wiki/Pseudorandom_generator $\endgroup$ – Nathan Nov 10 '17 at 19:29
3
$\begingroup$

Welcome to the one time pad. Unfortunately and respectfully, all your scheming is wrong /insecure.

The problem is your equations. Recursive Hash(Hash(Hash...))) is simply a pseudo random number generator. Java's SecureRandom() is very similar, albeit there's a counter involved.

One basic non mathematical definition of a PRNG is that it involves an algorithm and equations. The OTP cannot have any equations whatsoever involved in generating it's original entropy. This is absolutely fundamental. If you have an equation, you can theoretically invert it and predict the key from what ever starting point (seed) you used. You are conflating complexity with entropy.

The key material for a OTP must be generated via a physical piece of hardware you can hold in your hand. It must be a physical process from the natural world, not the mathematical one. It can be levers in a double pendulum, thermionic valves or semiconductor junction breakdown. Everyone's favourite is radio active decay (although the only known instance of this is HotBits). It might actually be the hand itself. OTPs during WW2 were generated by ladies randomly typing at typewriters. But there has to be a hand involved somewhere. Oh, there's dice and dimes too, but you also use your hand.

Another way to look at it, is that entropy is handed to you. It comes in a physical piece of equipment, and all you do is measure it. You cannot make it yourself (not absolutely strictly true - but that's a more complex discussion). It has to look something like this:-

diode

or this:-

typewriter

It cannot look like: f'(blah) -> f(blah)

We get this type of question from time to time. Actually, surprisingly often. Clicking the OTP tag will highlight other attempts at improving the venerable OPT. All fail. Also look towards entropy discussions.

$\endgroup$
  • $\begingroup$ Thanks for pointing this out. But i though since hash functions are injective this prevents them from having an inverse? $\endgroup$ – Strernd Nov 10 '17 at 18:43
  • $\begingroup$ @Strernd You probably mean surjective which allows for collisions and the avalanche effect of crypto hashes. Even so, MD5 was overcome putting it beyond crypto usage. And now there are inroads against SHA1. Re-linearisation might ultimately overcome all crypto algos - we don't know for sure yet. The fact that there's an algo in the 1st place means it's theoretically possible. To the counter, it's theoretically impossible to break a OTP. See my tag suggestion. $\endgroup$ – Paul Uszak Nov 10 '17 at 21:50

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.