4
$\begingroup$

Wikipedia claims that given an unkeyed permutation $p$ (presumably of the same size as the key) this is safe: $p(m \oplus k) \oplus k$ Why isn't this construction used instead of XEX? Surely unkeyed permutations should be faster than keyed ones since they do not have a key schedule, is there some issue not mentioned by the wikipedia page?

It also raises the question, given a block cipher $e$, would $e_{k_1}(m \oplus k_2)$ (without the outer xor) be safe? My interest is specifically about full-disk encryption.

$\endgroup$
  • $\begingroup$ This seems to be about Orr Dunkelman, Nathan Keller, and Adi Shamir. "Minimalism in Cryptography: The Even–Mansour Scheme Revisited". In how far does this answer your question? $\endgroup$ – Maarten Bodewes Feb 14 at 5:02
  • 1
    $\begingroup$ @MaartenBodewes I think that it fully answers the first part of my question. $\endgroup$ – Bob Semple Feb 14 at 5:18
4
$\begingroup$

Why isn't this construction used instead of XEX?

Because XEX takes a block cipher and constructs a tweakable block cipher out of it, whereas this construction, usually called Even-Mansour, takes a permutation and constructs a block cipher out of it.

Surely unkeyed permutations should be faster than keyed ones since they do not have a key schedule, is there some issue not mentioned by the wikipedia page?

This is a difficult question. This is because security models are way harder to construct for unkeyed permutations than for keyed ones - because you don't have a knowledge advantage over the adversary. Because of this lack of an advantage, public permutations tend to be slower in fact, e.g. the fastest one I know is Gimli which is still beaten by AES. Also note that the key-schedule is a one time cost and usually can be amortized quite well if you don't change the key often - which normally you don't do.

In fact this speed disadvantage is theoretically expected given that we can construct block ciphers from the most minimal cryptographic primitive - One Way Functions but cannot construct collision-resistant hash functions froms them which we can from publicly secure permutations. So there's something "intrinsic" that makes public permutations a stronger tool than block ciphers and this usually mean we have to do more computational work to construct it.

It also raises the question, given a block cipher e, would ek1(m⊕k2) (without the outer xor) be safe?

Yes, it would yield another block cipher (a PRP assuming the block cipher is a PRP itself) with a longer key. Though note that it does not yield a SPRP (a PRP where the inverse is also a PRP). If you were to take the $k_2$ as a tweak, I don't think this would yield a (strong) tweakable block cipher unlike XEX due to a lack of preprocessing of the tweak which may be non-random.

$\endgroup$
  • $\begingroup$ Aren't block ciphers with a publicly known constant key just unkeyed permutations? Is there a benefit from having a SPRP? As for Gimli, as far as I know that it is made for constrained systems, wouldn't chachacore be a faster permutation? $\endgroup$ – Bob Semple Feb 15 at 0:15
  • $\begingroup$ @BobSemple Block ciphers are designed to only provide security for unknown keys. They are technically allowed to fail horribly if the key is known (e.g. define a block cipher where the key is always a fixed-point, you can't guess the key so as long you don't know the key it's secure). Some constructions require SPRPs instead of PRPs (eg OCB). ChaCha core is a pseudo-random function from what I understand, that is it's not reversible. $\endgroup$ – SEJPM Feb 15 at 12:20
  • $\begingroup$ Apologies, I meant the internal chacha permutation. chachacore is just $p(x) \boxplus x$. $\endgroup$ – Bob Semple Feb 15 at 20:09

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.