Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've read that a OTP is only perfectly secure if the key is perfectly random, and the pad is never reused.
If you encrypt documents using two keys, where one is random but stays constant for some period of time, and the other is only pseudo-random but unique to each message, is the security of the OTP better or worse than if you used only one key or the other?
And would it still be vulnerable to frequency analysis?
I've read that a OTP is only perfectly secure if the key is perfectly random, and the pad is never reused.
But you've left out the most important condition: the key space must be as large as the message space.
If you encrypt documents using two keys, where one is random but stays constant for some period of time, and the other is only pseudo-random but unique to each message, is the security of the OTP better or worse than if you used only one key or the other?
You don't specify how the keys are used to encrypt documents, but since you've been talking about one-time pads I will assume the keys are as long as the documents and the encryption works by XOR.
Encrypting messages with distinct pseudorandom key streams is called a stream cipher, and is already secure if the pseudorandom stream generator used is secure and the same keystream is not used twice. So we can refactor your idea into two components, applied in sequence:
This has to be at least as secure as the stream cipher is; even if the adversary knows the long-term key for step #2, they'd still have to break the stream cipher. This is theoretically less secure than the OTP's "perfect security," but can be plenty secure in practice; my browser session to this site, for example, is protected by such a stream cipher.
Now, the question is whether the addition of the reused long-term true random key enhances the security in any way. The answer is no, because an adversary who can break the stream cipher is able to exploit the reuse of the long-term key to break the composite system. Notating the long-term key as $K_L$, the pseudorandom key streams as $K_1, K_2$, the plaintexts as $P_1, P_2$ and the ciphertexts as $C_1, C_2$, the encryptions satisfy these equations (where $\oplus$ is bitwise XOR):
$$ \begin{align} C_1 &= P_1 \oplus K_1 \oplus K_L \\ C_2 &= P_2 \oplus K_2 \oplus K_L \end{align} $$
Solving both equations for $K_L$:
$$ \begin{align} K_L &= P_1 \oplus K_1 \oplus C_1 \\ K_L &= P_2 \oplus K_2 \oplus C_2 \end{align} $$
By transitivity of equality:
$$ \begin{align} P_1 \oplus K_1 \oplus C_1 &= P_2 \oplus K_2 \oplus C_2 \end{align} $$
And now I can solve for the XOR of the two plaintexts:
$$ \begin{align} P_1 \oplus P_2 &= K_1 \oplus C_1 \oplus K_2 \oplus C_2 \end{align} $$
This is significant, because obtaining the XOR of two plaintexts is the basis for the standard two-time pad attacks:
$K_1$ and $K_2$ are pseudorandom keystreams, I can use a brute force attack to enumerate possible values for them, and use statistics on the implied values $P_1 \oplus P_2$ to infer whether I've hit the right key. And then when I've found the value $P_1 \oplus P_2$, I can try the two-time pad attacks on it.
So your proposal's security is more or less the same as just using the stream cipher. Lesson: just use the stream cipher.
To start, this is not a one time pad implementation. The idea of a one time pad is that a key is generated randomly, it is at least as long as the plaintext. Once the key is used to decrypt the data, it is destroyed. This ensures there is no way to recover the key from the ciphertext, nor is the key repeated at any point; the entire plaintext is encrypted as one block.
In terms of your system, if the key stays constant over multiple encryptions/decryptions, the system has a weakness. If some third party has multiple ciphertexts encrypted with the same key, they can analyze it somehow.
The next part of your system depends on what you mean by 'pseudorandom'. I will assume you mean that the seed is based off of some value. If your seed can be found out by an attacker (e.g. time, data sent over a network, etc.) then the system is broken.
Essentially, this system should be quite easy to break. If the pseudorandom key becomes truly random instead, then the second pass would be a true OTP, and this would be secure (encrypting with a constant key becomes obsolete though).
I think that the issue with your scheme stems from your characterisation of the key material as perfectly random. Perfectly random suggests data with a uniformly distributed probability over the output bits. This uniformity requirement is fulfilled with all manner of PRNGs, CSPRNGs and various Frankenstein creations.
The perfect secrecy of the OTP originates in having truly random key material. This fact seems to be quite elusive. Even the famous atomic Hotbits site adds to the confusion with their OTP generator page that is powered by a PRNG. And they worryingly advertise this OTP page as being run off a L'Ecuyer's two-sequence generator!
There are many questions on this site (and some interesting ones here too in the comments) about improving or tweaking the OTP. The fact remains that to get the perfect secrecy benefit of the OTP, the key material has to be truly random. No ifs. No buts. It used to be secretaries hitting random keys on their typewriters. They then invented electrical spinning disks(ref). Currently this means that is has to be generated by some physical random process involving groovy lava lamps, diodes or lasers. It cannot be any form of algorithm, no matter how cunning or complex.
If you realise this true randomness requirement for a OPT, your question becomes moot as you have a stream cipher.
Ref.
