I wouldn’t say it was a vulnerabiltity. Any decryption effort needs a crib or, like the infinite monkeys typing Hamlet, a near-infinite number of attempted keys can yield a number of different plaintext messages.
You are right in that the same header using the same machine settings would yield the same output. Enigma countered that by having some settings stay the same for the day – which rotors use and in which order, the ring setting of the rotors, and the plug board setting – then have the operator set the rotors’ start position differently for each 250-character group in a long message.
The problem then was that the start positions had to be sent with the block itself. They would be encrypted, of course, using rotor start positions that were also the same for the day which was used as a point of attack.
This is only a solution if Mallory performs the re-encryption in the presence of the other recipients. If they can’t observe her performing the re-encryption, they have no way to confirm that she didn’t just forward Bob’s ciphertext again.
This would prove that Mallory had the ability to encrypt messages as Bob. But it would not prove the actual fact that she produced that ciphertext, unless she could produce it while being observed by others.
And then having done so, the observers would (should) ask how they can be certain that Bob and Mallory are 2 distinct and real individuals, that neither is a sock puppet. This would be very difficult to prove unless the public keys were obtained in the physical presence of both Bob and Mallory, or distributed by a source who is fully trusted to have done so.
To get around the issue that Mallory could have stolen the text, you would need her to successfully decrypt something that you had encrypted with the public key. And, to prove that the original text was real, she would need to demonstrate that it encrypts to the original cypher text.
This doesn’t rule out that she stole the original text through some physical means, entirely, but if she provably has the private key then it’s somewhat immaterial if she decrypted the original message through cryptography or simply purloined a physical, pre-encryption, plaintext copy while breaking and entering, to steal the private key. It’s interesting if you want to know how she accomplished the decryption, but doesn’t change the correctness of the message decoding nor her ability to decrypt more messages.
With problems like this, the verifier is allowed to require Mallory to perform certain operations, like decrypt ciphertext that you provide.
Or compare the standard protocol (RFC 2945) used to verify that Mallory knows a secret password: the password is never revealed, nor is it (or even a hash of it) ever stored in non-encrypted form on the server, and the authentication process involves a secure key exchange where a shared session key is computed using the encrypted value; in other words, an interactive procedure.
Everyone including Mallory already possesses the ciphertext (by virtue of being a recipient) and the plaintext (by virtue of having decrypted it with Bob’s public key). What privileged information is Mallory then able to produce?
No. Alice has the plaintext because she created it. Mallory has it because she decrypted it, and anyone else who has it has it because Mallory shared it with them. The public key does not decrypt the ciphertext to plaintext. Only the private key does that.
The two questions asked in the OP are
And the answer is that the process by which you prove that a given plaintext can be decrypted from a given ciphertext is that you encrypt the plaintext again and you get the same ciphertext out.
Mallory would have to demonstrate that she can produce the ciphertext in the presence of others. Otherwise she’s not providing any new information, because everyone already has the ciphertext.
Mallory wouldn’t need to reveal the key, but she’d have to reveal that she possesses Bob’s secret key (the OP didn’t say whether that was important, but it seems like it might be).
No. She doesn’t. As I pointed out a few posts above, anyone can take the plaintext and Bob’s public key and confirm that the plaintext encrypts to the ciphertext.
The information that Mallory provides is the plaintext. The verification that it is correct is inherent in the way that public key cryptography works.
I thought that part was pretty much a given. If any of those Eves shares this fact with Bob, he would be wise to revoke his public key and generate a new keypair.
This was all about Mallory and the Eves doing their thing without Alice and Bob’s knowledge or participation.
Not quite. This is merely a quibble; you’ve got the 99% case covered.
If Mallory has Bob’s private key, then she can decrypt the ciphertext to a plaintext that the other Eves can prove to themselves will encrypt with Bob’s public key to the same ciphertext they all have a copy of. So far so good. And so far so conventional.
What Mallory cannot do with just the above and nothing more, is prove that she has Bob’s private key, versus the possibility that she stole the corresponding plaintext from Alice (or Bob) via other means and is just pretending to have derived it from the commonly known ciphertext via Bob’s private key.
To be sure, any Eve can discover if Mallory is lying by sending Mallory some other plaintext, asking Mallory to encrypt it using Bob’s private key, then send the corresponding ciphertext back to that Eve. Which Eve can then try decypting it using Bob’s public key. If that succeeds to return the sample plaintext Eve supplied, Mallory has proven, at least to that one Eve’s satisfaction, that Mallory has Bob’s private key.
But what if Mallory refuses to play along? “I, Mallory, have Bob’s private key and you must just take my word for it. I’ve shown you all that I can decrypt a message, that should be good enough. Neener neener!” The Eves (any or all) have no way to prove or disprove Mallory’s contention.
At least not that I can see. IANA professional at this.
Having a crib, like a large proportion of messages starting with the same known text, makes it much easier to crack an Enigma message. It does not make it any easier at all to crack an RSA message. The fact that this makes Enigma easier to crack, but does not make other encryption schemes easier to crack, absolutely is a vulnerability for Enigma compared to those other schemes.
The Eves can verify that Mallory’s plaintext maps to the original cypher - so they can confirm that it was a correct decryption - and they could continue to do that with any future texts that Mallory claims to have decrypted.
If Mallory can successfully continue to decrypt each text from Bob then, at some point, the question of whether they’re doing it by using the private key, having a camera hidden in his room, or exploiting a flaw in the encryption algorithm all becomes a bit moot. That said, until Mallory cooperates in proving that they can decrypt any arbitrary text, there’s the risk that they are using a camera and will lose connection to it at some point in the future. The Eves will need to verify every text that Mallory gives them, even after they’re long-since confident that Mallory has the goods.
Then again, that verification is fairly simple. And even if Mallory did prove that she had the private key, you’d still want to verify all of her claims.
The idea that comparing the original encrypted file to a file redoing the encryption from an identical plain-text will show that the 2 sources were the same is fine. But never mind salting/padding, timestamps are often used by encryption tools. In this case you would gave to redo the encryption on a system set to exactly the same date and time as the original event. That might present some issues.
I said “might”, would depend on the encryption system used. If an external timestamp server is used, then not trivial.
Even if using the system time, spoofing the exact time could be challenging for all or any of the “Eves”.
Suppose that the timestamps are kept to millisecond precision, and suppose that you can determine the timestamp to within a precision of an hour. That leaves only a few million possibilities to try and see which one works, which for encryption purposes, isn’t all that much. If you want something like this, you’d be much better served by using some sort of true random number generator. Which is expensive, computationally speaking, but ultimately any encryption scheme absolutely depends on having good random numbers, so you’d have to have one anyway. And the amount of randomness needed is certainly achievable: Rolling an ordinary six-sided die 16 times would give you several trillion possibilities, much more difficult to brute-force.