2
$\begingroup$

I have a question regarding the security definition of deterministic authenticated encryption (DAE) as defined by Bellare and Shrimpton. Their definition is reproduced below, and my question pertains to the emphasized part.

Definition 1 Let $\Pi = (\mathcal K, \mathcal E, \mathcal D)$ be a DAE scheme with header space $\mathcal H$, message space $\mathcal X$, and expansion function $e$. The DAE-advantage of adversary $A$ breaking $\Pi$ is defined as

$$\mathbf{Adv}_{\Pi}^{\mathrm{dae}}(A) = \Pr[K \gets \mathcal{K} : A^{\mathcal{E}_K(\cdot, \cdot), \mathcal{D}_K(\cdot, \cdot)} \Rightarrow 1] - \Pr[A^{\\\$(\cdot, \cdot), \bot(\cdot, \cdot)} \Rightarrow 1] $$

On query $H \in \mathcal H,X \in \mathcal X$, the adversary’s random-bits oracle $\\\$(\cdot,\cdot)$ returns a random string of length $|X|+e(H, X)$. As always, oracle queries outside the specified domain return $\bot$. The $⊥(\cdot,\cdot)$ oracle returns $\bot$ on every input. We assume that the adversary does not ask $(H, Y)$ of its right (ie, second) oracle if some previous left (ie, first) oracle query $(H, X)$ returned $Y$; does not ask $(H, X)$ of its left oracle if some previous right-oracle query $(H, Y)$ returned $X$; does not ask left queries outside of $\mathcal H \times \mathcal X$; and does not repeat a query. The last two assumptions are without loss of generality, as an adversary that violated any of these constraints could be replaced by a more efficient and equally effective adversary (in the $\mathbf{Adv}_{\Pi}^{\mathrm{dae}}$-sense) that did not. The first two assumptions are to prevent trivial wins

Basically, I don't see how the last assumption (i.e., no repeated query) is without loss of generalization? More specifically, isn't this assumption needed for any deterministic scheme to be considered secure according to this definition?

Here is how you could break any deterministic scheme according to Def. 1, if queries could be repeated. First, repeat the same query $(H,X)$ to the left oracle (either $\mathcal{E}_K(\cdot, \cdot)$ or $\\\$(\cdot, \cdot)$) and get back $Y_1$ and $Y_2$. If $Y_1 = Y_2$ return 1. It's trivial to see that this attack has DAE-advantage $1-2^{-|X|-e(H,X)}$.

As justification for their WLOG claim, I imagine they had the following reduction in mind. Let $A$ be a DAE-adversary that repeats queries, and let $B$ the following DAE-adversary that doesn't. It runs $A$ and forwards all of $A$'s queries to its own oracles, except whenever $A$ repeats a query, where $B$ instead returns the same response back for that query (which $B$ cached). $B$ outputs the same as $A$. However, this reduction doesn't work! (In particular, it doesn't properly simulate the DAE game).

$\endgroup$
6
  • $\begingroup$ I think the key thing to note here is that we're talking about deterministic authenticated encryption and therefore the encryption function is deterministic, meaning equal inputs lead to equal outputs? $\endgroup$
    – SEJPM
    Dec 28 '20 at 19:05
  • $\begingroup$ Yes, exactly. That's the heart of the issue. $\endgroup$
    – hakoja
    Dec 28 '20 at 20:19
  • $\begingroup$ Short answer: the random-oracle also returns the same result if queried with the same input, so your attack does not work. $\endgroup$
    – Aleph
    Dec 28 '20 at 22:28
  • $\begingroup$ Hmm, interesting. I've never thought of a random-bits oracle as caching its results (like a normal random oracle does). Do you have any references for this interpretation elsewhere in the literature? Of course, in the context of DAE this interpretation makes sense, but isn't odd that they don't call out this behavior explicitly? $\endgroup$
    – hakoja
    Dec 28 '20 at 23:33
  • $\begingroup$ @hakoja In this case the ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say "uniform random function" rather than "random-bits oracle". (For example, see Definition 1 in tosc.iacr.org/index.php/ToSC/article/view/7296/6470.) $\endgroup$
    – Aleph
    Dec 28 '20 at 23:55
1
$\begingroup$

As I wrote in a comment, the reason your proposed attack does not work is that the random oracle also returns the same result when queried with the same input.

The ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say "uniform random function" rather than "random-bits oracle". For example, see Definition 1 in this paper.

$\endgroup$

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.