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$
2
  • $\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, 2020 at 5:02
  • 1
    $\begingroup$ @MaartenBodewes I think that it fully answers the first part of my question. $\endgroup$
    – Bob Semple
    Feb 14, 2020 at 5:18

1 Answer 1

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$
3
  • $\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, 2020 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, 2020 at 12:20
  • $\begingroup$ Apologies, I meant the internal chacha permutation. chachacore is just $p(x) \boxplus x$. $\endgroup$
    – Bob Semple
    Feb 15, 2020 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.