Given:
- The attacker can call PRP() and the inverse function prp() on any message of his choosing.
- PRP is a pseudorandom permutation indistinguishable to the attacker from a random permutation.
- Assuming R and K are "sufficiently large", perfectly random, and never leaked to the attacker -- in particular, during a chosen-ciphertext attack, the decryptor only gives the message M to the attacker, never leaking the value of R.
passive attacks
It appears at first glance that this construction is secure against a polynomial-time Eve, a passive eavesdropper, even under both a chosen-plaintext attack and chosen-ciphertext attack,
in the sense that the attacker can't decode any other encrypted messages
(other than the ones you allow him to decode during the chosen-ciphertext attack).
K
|
M||R----->[PRP]--->(+)---->C
active attacks
Because there is no message authentication code, an active attacker can conduct a replay attack.
If the "message" part is allowed to be short -- for example, 2 bytes long,
an attacker who can trick the system into encoding all possible 2 byte messages,
or decoding a few hundred thousand random values,
can make a collection of ciphertexts that he knows corresponds to each possible 2 byte message.
Because there is no message authentication code,
an active attacker can inject any such such message of his choosing -- "Ya", "No", "Hm", etc.
attacks on weakened variants
Alas, weakening any of the assumptions makes this almost trivial to break.
leaked R:
If R is ever leaked to a single known plaintext/ciphertext pair,
then the key can be recovered from that single message pair, allowing the attacker to decode all other messages encrypted with that key.
Key = PRP( R || plaintext ) xor ciphertext.
weak random-number generator
If the random number generator is "weak" for a single known plaintext/ciphertext message,
so it is known that the random number R for that message is one of N possibilities
(for example, if all but b bits of the number R are known,
so it is known that the random number for that message is one of 2^b = N possibilities),
and N is small enough for the attacker to try out all N possibilities,
then the attacker can narrow the key down to one of N possible keys.
With a single other known plaintext/ciphertext message, or a few more known ciphertext messages that decode to something that the attacker can recognize as plain text --
even if those other ciphertexts was built using a strongly-random number --
the attacker can narrow the possibilities down even further,
probably recovering the key.
weak PRP
If the function O() is statistically flawed,
the attacker may be able to recover the key.
For example, if the function O( R || M ) is truly awful and always returns ( R || Y),
where Y = R xor M,
then with enough ciphertext messages that were encrypted with some fixed key,
ciphertext-only techniques can be used to recover the re-used key
(see
How does one attack a two-time pad (i.e. one time pad with key reuse)?
).
other ideas
This construction reminds me of one round of a
Feistel cipher.
Perhaps a few more rounds would make it less fragile to weaknesses in the PRP and the random-number generator?
K
|
M||R---[PRP]---(+)--->[PRP]---->C
the Even-Mansour scheme:
K K
| |
M||R---(+)-->[PRP]--->(+)---->C
EDIT:
Rough draft of a proof
Let us imagine that Olivia implements the
random oracle
by sitting in a big isolated room with lots of filing cabinets.
Every time a piece of paper with a new red number comes in the red slot,
Olivia flips some coins to come up with a new black number.
(If that black number is the same as a black number already in her archives,
Olivia forgets that number and starts over, flipping all the coins again --
this is necessary to make this a random permutation,
rather than a random function.
).
Olivia writes down the results of the coin-flips in black ink twice --
once on a blank piece of paper that she shoves out the black slot,
and again on the incoming piece of paper next to the incoming red number,
which she then files.
When a piece of paper comes in with a previously-seen red number,
Olivia looks up that number in her files,
copies the corresponding black number to a blank piece of paper that she shoves out the black slot.
When a black number comes in the red slot, Olivia handles it similarly, writing with red ink and shoving a corresponding red number out the red slot.
Every time the the attacker feeds a red number directly to Olivia and gets the corresponding black number, if R is large and random enough, he's almost certainly getting the values of freshly-flipped coins -- practically the definition of useless information.
Every time the attacker feeds a black number directly to Olivia and gets the corresponding red number, if R is large enough, he's almost certainly getting the values of freshly-rolled dice -- practically the definition of useless information.
Every time the attacker tricks the system into encrypting some chosen-plaintext,
the system generates a fresh new random number R, Olivia flips her coins,
and the output ciphertext is the key encrypted by Olivia's new one-time coin-flips.
(Assuming R is large enough that Olivia actually does flip her coins again,
rather than re-use some previous number, the one-time-pad security proof
indicates that the attacker won't learn anything about the system key from that ciphertext).
Every time the attacker tricks the system into decrypting some chosen-ciphertext
that is different from any ciphertext generated in normal operation,
the "ciphertext" is run through the key,
again Olivia flips her coins,
and assuming the system throws away the many bits of "R" and only gives the decoded plaintext to the attacker,
the attacker only receives the values of freshly-flipped coins -- practically the definition of useless information.
user8911 pointed out a presentation about Even-Mansour:
Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".
2012.
which is apparently a summary of thier paper,
Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".
They prove that certain attacks require a certain number of operations.
It appears that all their proofs and attacks can be adapted to the randomized cipher machine proposed by udfrg2.
So any desired security level can be attained by fixing the message width |M| and the random width |R| wide enough.
As you may have already guessed, all these attacks rely on some kind of birthday attack --
after enough data runs through the system,
eventually the attacker gets lucky and Olivia re-uses some number rather than generating fresh coinflips.
