Password-Managers: what is the IND-CDBA attack logic?

Question

In the work of Paolo Gasti and Kasper B. Rasmussen On The Security of Password Manager Database Formats, they describe two attack forms: IND-CDBA and MAL-CDBA.

While I understand the MAL-CDBA attack by modification of records in the DB, what is the attack logic of IND-CDBA?

Answer 1

Intuitively, IND-CDBA means an attacker cannot tell which of two databases contains a record he picked.

In other words even if you know the passwords in a database. And even if there are only two possible databases to pick from. An attacker still cannot figure out which one is the right one.

This is the formal definition from the paper:

Indistinguishability of databases game $\text{IND-CDBA}_{\text{Adv}_r, \mathcal{PM}}(\kappa)$:

A challenger $\text{Ch}$ running $\mathcal{PM}$ interacts with $\text{Adv}_r$ as follows:

• $\text{Ch}$ runs $\text{mp} \leftarrow \text{Setup}(1^\kappa)$
• $\text{Adv}_r$ outputs two record-sets $\text{RS}_0, \text{RS}_1$
• $\text{Ch}$ selects a bit $b$ uniformly at random and returns the database $\text{DB}_b \leftarrow \text{Create}(mp, \text{RS}_b)$ to $\text{Adv}_r$
• $\text{Adv}_r$ eventually outputs bit $b'$ and wins if $b = b'$

This is similar to the familiar IND-CPA definition where you pick two messages and then you get an encryption of one of them and you have to guess which one it was.

Of course what this tells you in the end, is that you cannot learn any information about the passwords in a password file if this game is hard to win.