A Reputation for HonestyWe thank Mehmet Ekmekci and Navin Kartik for helpful
comments, and National Science Foundation grants SES-1947021 and SES-1951056
for financial support.We thank Mehmet Ekmekci and Navin Kartik for helpful
comments, and National Science Foundation grants SES-1947021 and SES-1951056
for financial support. Drew FudenbergDepartment of Economics, Massachusetts
Institute of Technology. Email<EMAIL_ADDRESS>of Economics,
Massachusetts Institute of Technology. Email<EMAIL_ADDRESS>GaoDepartment
of Economics, Massachusetts Institute of Technology. Email:
<EMAIL_ADDRESS>of Economics, Massachusetts Institute of
Technology. Email<EMAIL_ADDRESS>PeiDepartment of Economics,
Northwestern University. Email<EMAIL_ADDRESS>of
Economics, Northwestern University. Email<EMAIL_ADDRESS>
We analyze situations in which players build reputations for honesty rather
than for playing particular actions. A patient player facing a sequence of
short-run opponents makes an announcement about their intended action after
observing an idiosyncratic shock, and before players act. The patient player
is either an honest type whose action coincides with their announcement, or an
opportunistic type who can freely choose their actions. We show that the
patient player can secure a high payoff by building a reputation for being
honest when the short-run players face uncertainty about which of the patient
player’s actions are currently feasible, but may receive a low payoff when
there is no such uncertainty.

Many economic actors have reputations for keeping or breaking their promises.
As a prominent example, Archibald Cox Jr’s default on his promise of paying
high bonuses in the early 90s triggered a massive defection of key personnel
from First Boston to its archrival Merrill Lynch.111 See “Taking the Dare” in
The New Yorker, July 26th, 1993. The departed individuals include leaders of
First Boston’s prestigious energy group, and more than a dozen managing
directors in its fixed-income and mortgage-backed-securities groups, triggered
by a lower bonus payment than what they had been promised. Many who departed
had been at First Boston their entire careers, including during its difficult
times in the 80’s. Similar logic applies to advertising and marketing, which
can set customers’ expectations about the types of interactions they are going
to have with the firm. If those expectations are not aligned with the actual
customer experience, the firm’s brand and business will suffer.

Motivated by these observations, we examine the reward for building a
reputation for honesty. Compared to reputations for taking specific actions, a
reputation for honesty can better adapt an agent’s decisions to the current
circumstances, which is valuable when the environment changes over time.
Moreover, it is unrealistic to make commitments based on future contingencies
that are hard to describe in advance, and the simplicity of a commitment to
honesty makes it more plausible.

In our model, a patient player (e.g., a firm) faces a sequence of myopic
opponents (e.g., consumers), each of whom plays the game only once. Each
period, before players act, the patient player privately observes an
idiosyncratic shock, which can affect their payoff (e.g., their production
cost) and which of their actions are currently feasible. Then the patient
player announces the action they intend to play. The myopic players cannot
observe the shocks, but can observe the announcement in the current period as
well as whether the patient player has kept their word in the past.

The patient player is either an honest type, who strategically chooses their
announcements but always keeps their word, or an opportunistic type, who
strategically chooses both the announcements and the actions. Both types have
the same payoff function. This contrasts to Kreps and Wilson (1982), Milgrom
and Roberts (1982), and Fudenberg and Levine (1989) in which with positive
probability, the patient player is a commitment type who mechanically plays a
particular action.

Theorem 1 shows that the patient player receives at least their expected
Stackelberg payoff in every equilibrium when the myopic players face a small
amount of uncertainty about the actions currently available to the patient
player.222In Section 4, we show that our reputation result extends when the
patient player observes which of their actions are feasible after making their
announcement, or when the patient player chooses an action (e.g., their
effort), observes their product quality, and makes an announcement about
quality before the myopic player chooses their action. A complication is that
the opportunistic type may announce certain actions with higher probability
than the honest type does, so the patient player’s announcement may adversely
affect their opponent’s belief about their type. As a result, both types of
the patient player may face a tradeoff between announcing actions that lead to
higher credibility and announcing actions that lead to higher commitment
payoffs (i.e., payoff conditional on being trusted).

To see why the reputation bound nevertheless obtains, suppose the honest type
announces their Stackelberg action whenever it is feasible. When a myopic
player does not best reply against the announcement, whether the patient
player keeps their word in that period is informative about their type.
Because the set of feasible actions is stochastic, the honest type announces
each action with strictly positive probability, which implies that observing
the current announcement leads to at most a bounded change in the myopic
player’s belief. Therefore, when the patient player behaves honestly, there
can be at most a bounded number of periods in which the myopic players do not
best reply to the announcement. As a result, the patient player receives at
least their expected Stackelberg payoff.

By contrast, Theorem 2 shows that when the patient player can choose from any
of their possible actions in every period, there are equilibria in which they
receive a low payoff, which can be as low as their minmax value in examples
such as the product choice game.

### Related Literature:

Our paper contributes to the study of reputation models where no types are
committed to specific actions. Schmidt (1993) characterizes the Markov
equilibria of finite-horizon repeated bargaining games in which a firm has
private information about its production cost. Pei (2020) characterizes an
informed player’s highest Nash equilibrium payoff when facing uninformed
opponents. Sugaya and Wolitzky (2020) constructs a cooperative equilibrium in
a community enforcement model with a type that communicates strategically but
is committed to playing always defect. By contrast, we provide a lower bound
on the patient player’s payoff for all Nash equilibria.

Our reputation result requires the uninformed players to face uncertainty
about the availability of the informed player’s actions, or more generally,
believe that the honest type makes every announcement with positive
probability. This is related to Celentani, Fudenberg, Levine, and Pesendorfer
(1996) and Atakan and Ekmekci (2015), which show that full support monitoring
can help reputation building when the uninformed player is long-lived. Their
results, unlike ours, require that the informed player cannot perfectly
observe the uninformed player’s actions.

Jullien and Park (2020) studies repeated buyer-seller games in which a seller
privately observes their product quality, which is a noisy signal of their
effort. It shows that cheap talk communication about quality improves the
maximum social welfare if and only if the seller’s cost of effort is
intermediate.333 Jullien and Park (2014) shows that communication accelerates
consumer learning when product quality is determined by the seller’s type, and
the high type seller is non-strategic and always tells the truth. Awaya and
Krishna (2016) identifies a class of games in which players can achieve
perfectly collusive payoffs with communication, but not without it. Our paper
examines a complementary question, namely, whether a patient player can
guarantee high payoffs in all equilibria by building reputations for honesty.
Successful reputation building in our model requires uncertainty about the
actions available to the patient player, but does not depend on the players’
payoff functions. Corollary 2 in Section 4 extends our insights to Jullien and
Park (2020)’s setting, which implies that a patient seller receives their
optimal commitment payoff in all equilibria when product quality (i.e., the
seller’s private signal) is a noisy signal of effort, but receives a payoff
lower than that in some equilibria when quality is a perfect signal of effort.

The fact that many people prefer to be honest has been established
experimentally by e.g. Gneezy (2005) and Gneezy, Kajackaite, and Sobel (2018).
Kartik, Ottaviani, and Squintani (2007) and Kartik (2009) show how costs of
lying change the equilibrium outcomes of strategic communication games.
Instead of positing that some players have a cost of lying, we follow Chen,
Kartik, and Sobel (2008) and Chen (2011) and assume that the patient player is
either an honest type who never lies, or an opportunistic type who faces no
cost of lying. Our results extend to cases with strictly positive and possibly
heterogeneous lying costs.

Our work is related to the literature on pre-play communication. Including an
honest type in our model is in line with the experimental finding of Charness
and Dufwenberg (2006) that some people keep their word in order to live up to
others’ expectations. Sobel (2017) allows one of the players to communicate
their intended action before playing a two-player complete information game,
and provides sufficient conditions under which the sender receives their
highest Nash equilibrium payoff.

##  1 Example: Product Choice Game with Stochastic Cost

Consider a game between a firm (row player) with discount factor
$\delta\in(0,1)$ and a sequence of consumers (column player), each of whom
plays the game only once. In every period, the firm privately observes its
i.i.d. cost of production $\theta_{t}\in\\{\theta_{g},\theta_{b}\\}$. Let
$p_{g}\in(0,1)$ be the probability that $\theta_{t}=\theta_{g}$. The players’
stage-game payoffs are:

$\theta=\theta_{g}$ | $T$ | $N$
---|---|---
$H$ | $1,2$ | $-1,0$
$L$ | $2,-2$ | $0,0$
$\theta=\theta_{b}$ | $T$ | $N$
---|---|---
$H$ | $-1,2$ | $-3,0$
$L$ | $2,-2$ | $0,0$

When $\theta=\theta_{g}$, the best pure-strategy commitment for the firm is to
action $H$, which yields payoff $1$.444A commitment to a mixed strategy is
even better in state $\theta_{g}$. We do not consider reputations for playing
mixed actions in this paper. When $\theta=\theta_{b}$, the firm’s optimal
commitment action is $L$, which yields payoff $0$. If the firm obtains its
optimal pure-strategy commitment payoff in every state, then its expected
payoff is $p_{g}$.

### No Announcement Benchmark:

Suppose the firm cannot make announcements about its intended actions, and
that with small but positive probability it is a commitment type that
mechanically plays $H$ in every period. Future consumers can observe the
firm’s effort in previous periods, but not the past realizations of
$\theta_{t}$.555This is a reasonable assumption given that $\theta$ only
affects the firm’s cost of supplying high quality. Then, there are equilibria
in which the patient firm’s payoff is $\max\\{0,2p_{g}-1\\}$, which is
strictly lower than $p_{g}$. For example, when $p_{g}\geq 1/2$, there is an
equilibrium where the opportunistic firm chooses $H$ in every period on the
equilibrium path, and each consumer chooses $T$ unless they observe $L$ in at
least one of the previous periods. Intuitively, when $\theta=\theta_{b}$, the
cost of playing $H$ outweighs the benefit from the consumer’s trust, and the
firm faces a tradeoff between sustaining its reputation for playing $H$ and
avoiding the excessive cost.

This low-payoff equilibrium motivates our interest in reputations for honesty.

### Reputation for Honesty:

Suppose that the firm can make an announcement $m_{t}$ about its intended
action $a_{t}$ to the current consumer after observing $\theta_{t}$, but
before players choosing actions.

The firm is either honest or opportunistic. In contrast to the commitment
types in canonical reputation models, the honest type is strategic when making
announcements and does not commit to any particular action. Instead, it
commits to play the action it announces in every period. The two types of the
firm have the same stage-game payoff function and discount factor, and
maximize their respective discounted average payoffs. The consumer in period
$t$ observes the firm’s announcement in period $t$, as well as the value of
$\mathbf{1}\\{a_{s}=m_{s}\\}$ for $s\in\\{0,1,...,t-1\\}$, i.e., whether the
firm’s announcements matched its actions in the previous periods.

As Theorem 2 shows, the firm’s equilibrium payoff can be low when all of its
actions are always available. To see how this works in the example, consider
the following strategy profile: Both types of the firm announce $L$ and play
$L$ at every history, and each consumer plays $N$ regardless of the firm’s
announcement. The consumers’ belief about the firm’s type never changes on the
equilibrium path. After the firm announces $H$, the current consumer believes
that the firm is opportunistic and will play $L$.666When future consumers only
observe whether $a_{t}$ coincides with $m_{t}$, but not the exact realizations
of $a_{t}$ and $m_{t}$, they do not observe deviations in the announcement
stage if the firm kept its word. We show that the firm can also receive a low
payoff when future consumers can observe both $a_{t}$ and $m_{t}$. This
strategy profile and assessment constitute a Perfect Bayesian equilibrium, in
which the firm’s discounted average payoff is $0$ regardless of its type.

This low-payoff equilibrium is driven by the honest-type firm’s strategic
concerns when making announcements. The consumers believe that the
opportunistic type is more likely to announce $H$, so the honest type faces a
trade-off in state $\theta_{g}$ between announcing an action that leads to
higher credibility (i.e., action $L$) and an action that leads to a higher
commitment payoff (i.e., action $H$). This motivates the honest type to
announce $L$, making consumers’ beliefs self-fulfilling.

In contrast, Theorem 1 shows that when some of the firm’s actions are
unavailable with small but positive probability, both types of the firm
receive at least their expected Stackelberg payoff in every equilibrium. For
example, suppose in every period the firm can choose between $H$ and $L$ with
probability $1-2\varepsilon$, can only choose $H$ with probability
$\varepsilon$, and can only choose $L$ with probability $\varepsilon$. Both
types of the patient firm receive payoff at least
$(1-\varepsilon)p_{g}-7\varepsilon(1-p_{g})$ when the feasibility of actions
is i.i.d. over time and is independent of $\theta$. This guaranteed payoff
converges to $p_{g}$ as $\varepsilon\rightarrow 0$.

### Remarks:

Our assumption that the consumers face uncertainty about which of the firm’s
actions are feasible fits situations in which the firm is a single contractor
who occasionally may be sick, and so unable to provide high-quality service.
It also fits cases where the firm faces occasional regulatory inspections, and
producing low-quality products in those periods can lead to fines and the risk
of being shut down. In this situation, the firm will always choose to supply
high quality, regardless of their discount factor.777Formally, if the firm
chooses $L$ when it is inspected, it faces a fine $f>0$ and a probability
$q\in(0,1)$ of shutting down. One can show that there exists $\underline{f}>0$
and $\underline{q}\in(0,1)$ such that when $f>\underline{f}$ and
$q>\underline{q}$, it is a dominant strategy for both types of the firm to
choose $a_{t}=H$ regardless of their discount factors and the equilibrium
being played.

Our reputation result (Theorem 1) extends to cases where the distribution of
the feasible actions varies exogenously over time or is correlated with the
current $\theta$. It also extends when $\theta_{t}$ is drawn from a
potentially different set $\Theta_{t}$ in every period, as long as the patient
player’s payoff is uniformly bounded for all $t\in\mathbb{N}$. This captures
situations in which the client’s demand varies over time and which of the
firm’s action benefits the client is known only after the client arrives.

In these situations, the advantage of establishing a reputation for honesty is
more pronounced. Due to the complicated nature of future payoff environments,
it is impractical for the firm to commit to state-contingent action plans. A
reputation for honesty allows the firm to communicate its intended actions
after observing the payoff environment, which sidesteps these complications.

##  2 Baseline Model

Time is discrete, indexed by $t=0,1...$. A long-lived player $1$ (e.g., a
seller) with discount factor $\delta$ interacts with an infinite sequence of
short-lived player $2$s (e.g., consumers), with $2_{t}$ denoting the short-
lived player in period $t$. Player $1$’s action set is $A$ and player $2$’s
action set is $B$.

Each period consists of an announcement stage and an action stage. In period
$t$, an i.i.d. random variable $(\theta_{t},\omega_{t})\in\Theta\times\Omega$
is drawn according to $p\in\Delta(\Theta\times\Omega)$, where
$\theta_{t}\in\Theta$ affects player $1$’s stage-game payoff (e.g., their cost
of supplying high quality) and $\omega_{t}\subset A$ is the set of feasible
actions, with $\Omega\equiv 2^{A}\backslash\\{\varnothing\\}$. Player $1$
privately observes $(\theta_{t},\omega_{t})$ and announces to player $2_{t}$
that they intend to play action $m_{t}\in A$. Players then simultaneously
choose their actions $a_{t}\in\omega_{t}$ and $b_{t}\in B$.

Player $1$’s stage-game payoff is $u_{1}(\theta_{t},a_{t},b_{t})$ and player
$2_{t}$’s is $u_{2}(a_{t},b_{t})$. Importantly, player $2$’s payoff does not
depend on $\theta_{t}$. Each player $2$ who arrives after period $t$ can
observe $y_{t}\in Y$, distributed according to $F(\cdot|a_{t},m_{t})$. A
leading example is when $y_{t}$ is the indicator function
$\mathbf{1}\\{a_{t}=m_{t}\\}$, that is, future short-run players observe
whether the patient player has kept their word in the past.

Player $1$ has private information about their type
$\gamma\in\\{\gamma_{h},\gamma_{o}\\}$, which is either honest ($\gamma_{h}$)
or opportunistic ($\gamma_{o}$). Both types share the same stage-game payoff
function. The honest type is restricted (i) to announce an action that is
currently available, i.e., $m_{t}\in\omega_{t}$, and (ii) to take an action
that matches their announcement, i.e., $a_{t}=m_{t}$. The opportunistic type
can announce any action (including ones that are not feasible that period) and
can take any action in $\omega_{t}$ regardless of their announcement. Let
$\pi_{0}\in(0,1)$ be the prior probability of the honest type according to
player $2$s’ prior belief.

For every $t\in\mathbb{N}$, player $2_{t}$’s private history is
$h_{2}^{t}\equiv\\{y_{0},y_{1},...,y_{t-1},m_{t}\\}$, with
$h_{2}^{t}\in\mathcal{H}_{2}^{t}$. Player $2_{t}$’s strategy is
$\sigma_{2}^{t}:\mathcal{H}_{2}^{t}\rightarrow\Delta(B)$, with
$\sigma_{2}\equiv(\sigma_{2}^{t})_{t\in\mathbb{N}}$. Player $1$’s private
history in the announcement stage of period $t$ is

$\widehat{h}_{1}^{t}\equiv\\{\theta_{s},\omega_{s},m_{s},a_{s},b_{s},y_{s}\\}_{s=0}^{t-1}\bigcup\\{\gamma,\omega_{t},\theta_{t}\\},$

with $\widehat{h}_{1}^{t}\in\widehat{\mathcal{H}}_{1}^{t}$ and
$\widehat{\mathcal{H}}_{1}\equiv\bigcup_{t=0}^{\infty}\widehat{\mathcal{H}}_{1}^{t}$.
Player $1$’s private history in the action stage of period $t$ is

$\widetilde{h}_{1}^{t}\equiv\\{\theta_{s},\omega_{s},m_{s},a_{s},b_{s},y_{s}\\}_{s=0}^{t-1}\bigcup\\{\gamma,\omega_{t},\theta_{t},m_{t}\\},$

with $\widetilde{h}_{1}^{t}\in\widetilde{\mathcal{H}}_{1}^{t}$ and
$\widetilde{\mathcal{H}}_{1}\equiv\bigcup_{t=0}^{\infty}\widetilde{\mathcal{H}}_{1}^{t}$.
The opportunistic type’s strategy is
$\sigma_{o}\equiv(\widehat{\sigma}_{o},\widetilde{\sigma}_{o})$, with
$\widehat{\sigma}_{o}:\widehat{\mathcal{H}}_{1}\rightarrow\Delta(A)$ their
strategy to make announcements and
$\widetilde{\sigma}_{o}:\widetilde{\mathcal{H}}_{1}\rightarrow\Delta(A)$ their
strategy to take actions, subject to a feasibility constraint that the support
of $\widetilde{\sigma}_{o}(\widetilde{h}_{1}^{t})$ is a subset of
$\omega_{t}$. The honest type’s strategy is
$\sigma_{h}\equiv(\widehat{\sigma}_{h},\widetilde{\sigma}_{h})$, with
$\widehat{\sigma}_{h}:\widehat{\mathcal{H}}_{1}\rightarrow\Delta(A)$ their
strategy to make announcements and
$\widetilde{\sigma}_{h}:\widetilde{\mathcal{H}}_{1}\rightarrow\Delta(A)$ their
strategy to take actions, subject to first, the support of
$\widehat{\sigma}_{h}(\widehat{h}_{1}^{t})$ is a subset of $\omega_{t}$, and
second, their action matches their announcement
$\widetilde{\sigma}_{h}(\widetilde{h}_{1}^{t})=m_{t}$.

A Nash equilibrium (NE) consists of $(\sigma_{o},\sigma_{h},\sigma_{2})$, in
which $\sigma_{2}^{t}$ maximizes player $2_{t}$’s stage-game payoff, and every
type of player $1$ chooses a strategy that maximizes their discounted average
payoff
$\mathbb{E}\Big{[}\sum_{t=0}^{\infty}(1-\delta)\delta^{t}u_{1}(\theta_{t},a_{t},b_{t})\Big{]}$.
We assume that $\Theta$, $A$, $B$, and $Y$ are finite sets, which together
with discounting of per period payoffs implies that a Nash equilibrium exists
(Fudenberg and Levine 1983).

##  3 Results

We show that when the short-run players face a small amount of uncertainty
about the feasibility of the patient player’s actions, and $y_{t}$ is
informative about whether the patient player has kept their word in period
$t$, the patient player can secure their expected (pure) Stackelberg payoff in
every equilibrium.888In what follows, we will simply say Stackelberg action
and Stackelberg payoff, with “pure” left implicit.  By contrast, the patient
player receives a low payoff in some equilibria when all of their actions are
feasible in every period.

Recall that $\omega_{t}\subset A$ is the set of feasible actions in period
$t$. For every $\varepsilon>0$, we say that player $1$’s action choice is
$\varepsilon$-flexible if the probability with which $\omega_{t}=A$ is at
least $1-\varepsilon$.

######  Assumption 1.

For every $a\in A$, $\omega_{t}=\\{a\\}$ with strictly positive probability.

Our next assumption requires $y_{t}$ to be informative about whether player
$1$’s action and announcement match. A leading example that satisfies this
assumption is $y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$.

######  Assumption 2.

If $a=m$ and $a^{\prime}=m^{\prime}$, then (i)
$F(\cdot|a,m)=F(\cdot|a^{\prime},m^{\prime})$, and (ii) $F(\cdot|a,m)$ does
not belong to the convex hull of
$\\{F(\cdot|a^{\prime\prime},m^{\prime\prime})\\}_{a^{\prime\prime}\neq
m^{\prime\prime}}$.

Let $\textrm{BR}_{2}:\Delta(A)\rightarrow 2^{B}\backslash\\{\varnothing\\}$ be
player $2$’s best reply correspondence. In state $\theta\in\Theta$, player
$1$’s Stackelberg payoff is

$v_{1}^{*}(\theta)\equiv\max_{a\in
A}\Big{\\{}\min_{b\in\textrm{BR}_{2}(a)}u_{1}(\theta,a,b)\Big{\\}},$

and their expected Stackelberg payoff is
$v_{1}^{*}\equiv\sum_{\theta\in\Theta}p(\theta)v_{1}^{*}(\theta)$.

######  Theorem 1.

Suppose the environment satisfies Assumptions 1 and 2. For every $\eta>0$,
there exist $\underline{\delta}\in(0,1)$ and $\varepsilon>0$ such that when
$\delta>\underline{\delta}$ and player $1$’s action choice is
$\varepsilon$-flexible, each type of player $1$ receives payoff at least
$v_{1}^{*}-\eta$ in every Nash equilibrium.999When
$y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$, a patient player $1$ can guarantee payoff
approximately $v_{1}^{*}$ in every weak rationalizable outcome defined in
Watson (1993) in the perturbed game where player $1$ is honest with positive
probability.

The proof is in Appendix A. For some intuition, consider the example in which
$y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$. Let $a^{*}:\Theta\rightarrow A$ be any
mapping such that $a^{*}(\theta)\in\arg\max_{a\in
A}\Big{\\{}\min_{b\in\textrm{BR}_{2}(a)}u_{1}(\theta,a,b)\Big{\\}}$ for every
$\theta$.

Fix any equilibrium, and consider the honest type’s payoff when they announce
$a^{*}(\theta_{t})$ in period $t$ whenever $a^{*}(\theta_{t})\in\omega_{t}$.
The second part of Assumption 2 implies that whether player $1$’s action
coincides with their announcement is informative about their type in the “bad”
periods where player $2$ fails to best reply to the announcement. Assumption 1
requires that for each $a\in A$, $\omega_{t}=\\{a\\}$ with positive
probability, which implies that the honest type makes each announcement with
positive probability in every period.101010Our reputation result extends when
$\omega_{t}$ is the set of feasible announcements. When the honest type
trembles and makes each announcement with positive probability, our result
also extends to settings where player $1$ makes their announcement before
knowing which of their actions are feasible. See Corollary 3 for details. The
first part of Assumption 2 guarantees that the honest type’s deviation
generates the same distribution of player $2$’s histories as the honest type’s
equilibrium strategy.

If player $2_{t}$ fails to best respond to the announced action, player $2$
must assign a significant probability to the event that player $1$ is
opportunistic and takes $a_{t}\neq m_{t}$. Hence, observing $a_{t}=m_{t}$
should increase the posterior probability with which player $1$ is honest.
Thus, there exists at most a bounded number of periods where player $2$
believes that player $1$ chooses $a_{t}\neq m_{t}$ with significant
probability. In other words, player $2$ must believe that player $1$ is honest
or opportunistic but keeps their word most of the time.

Theorem 1 requires that the patient player can choose any action in $A$ with
probability close to $1$. In fact, as long as the environment satisfies
Assumptions 1 and 2, one can establish a reputation result using the same
argument as the proof of Theorem 1 after adjusting the definition of expected
Stackelberg payoff. For every $(\theta,\omega)\in\Theta\times\Omega$, let

$u_{1}^{*}(\theta,\omega)\equiv\max_{a\in\omega}\Big{\\{}\min_{b\in\textrm{BR}_{2}(a)}u_{1}(\theta,a,b)\Big{\\}},$
(3.1)

and let

$u_{1}^{*}\equiv\sum_{(\theta,\omega)\in\Theta\times\Omega}p(\theta,\omega)u_{1}^{*}(\theta,\omega).$

One can show that when the environment satisfies Assumptions 1 and 2, a
patient player can guarantee payoff $u_{1}^{*}$ in all equilibria when
$\delta$ is close enough to $1$.

Assumption 2 rules out situations in which player $2$s can perfectly observe
player $1$’s past announcements, or more generally can observe signals that
statistically identify the content of player $1$’s past announcements even
when $a_{t}=m_{t}$. To study such situations, we extend our result when player
$2$s can observe informative signals $z_{t}$ about the past realizations of
$a_{t}$ and $m_{t}$, as long as each of them can only observe the realizations
of $z_{t}$ in a bounded number of previous periods.

Formally, let $z_{t}\in Z$, where $z_{t}$ is distributed according to
$G(\cdot|m_{t},a_{t})$. We make no restrictions on $G$ except that its support
$Z$ is a finite set. Suppose for every $t\in\mathbb{N}$, player $2_{t}$ can
observe player $1$’s announcement $m_{t}$, the history
$\\{y_{0},...,y_{t-1}\\}$, as well as a (possibly stochastic) subset of
$\\{z_{0},...,z_{t-1}\\}$ that has at most $K\in\mathbb{N}$ elements. Whether
player $1$ can observe $y$ and $z$ are irrelevant for our result.

Our assumption on the asymmetry between player $2$s’ observations of $y_{t}$
and $z_{t}$ is motivated by retail markets in developing economies. Due to the
lack-of record-keeping institutions, detailed information about sellers’
actions and announcements (e.g., the quality of their services, various
attributes of their products, the content of their advertisements, and so on,
which correspond to $z_{t}$) is likely to get lost over time. By contrast,
coarse information about sellers’ records, such as whether they have kept
their word (which corresponds to $y_{t}$), is likely to be more persistent due
to social learning and word-of-mouth communication. Corollary 1 extends
Theorem 1, with proof in Appendix C.

######  Corollary 1.

Suppose the environment satisfies Assumptions 1 and 2, and there exists
$K\in\mathbb{N}$ such that each player $2$ observes the past realizations of
$z$ in at most $K$ periods. For every $\eta>0$, there exist
$\underline{\delta}\in(0,1)$ and $\varepsilon>0$ such that when
$\delta>\underline{\delta}$ and player $1$’s action choice is
$\varepsilon$-flexible, each type of player $1$ has payoff at least
$v_{1}^{*}-\eta$ in every Nash equilibrium.

Now we show why uncertainty about which of player 1’s actions are feasible is
necessary for Theorem 1 to hold in general. We show this for situations in
which $\omega_{t}=A$ with probability $1$ and
$y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$.111111We can construct low-payoff
equilibria when $\omega_{t}=A$ with probability $1$ and player $2_{t}$ can
perfectly observe $\\{a_{s},m_{s}\\}_{s=0}^{t-1}$. We do not know how to
construct low-payoff equilibria when some actions are not available with
positive probability and player $2_{t}$ can perfectly observe
$\\{a_{s},m_{s}\\}_{s=0}^{t-1}$.

We start by introducing two auxiliary one-shot games that have the same payoff
functions as the original stage game. The first auxiliary game does not have a
communication stage: Player $1$ observes $\theta$, and then players act
simultaneously without any communication. Let $v_{1}^{min}$ be player $1$’s
lowest Nash equilibrium payoff in this game. The second auxiliary game has an
action recommendation stage: Player $1$ observes $\theta$, makes a
recommendation $\widehat{b}\in B$ to player $2$ before players take their
actions. Let $\widehat{v}_{1}$ be player $1$’s lowest pure-strategy
equilibrium payoff in this game. If there is no pure-strategy equilibrium in
this game, let $\widehat{v}_{1}=+\infty$.

Let $\mathcal{B}$ be the set of mappings $\beta:A\rightarrow\Delta(B)$ such
that $\beta(a)$ is a best reply to $a$ for every $a\in A$. Abusing notation,
let $p$ be the distribution of $\theta$. Let

$v_{1}^{\prime}\equiv\min_{A^{\prime}\subset
A,\beta\in\mathcal{B}}\sum_{\theta\in\Theta}p(\theta)\max_{a\in
A^{\prime}}u_{1}(\theta,a,\beta(a))$ (3.2)

subject to

$\sum_{\theta\in\Theta}p(\theta)\max_{a\in
A^{\prime}}u_{1}(\theta,a,\beta(a))\geq\min\\{v_{1}^{min},\widehat{v}_{1}\\}.$
(3.3)

Theorem 2 shows that when all of player $1$’s actions are feasible in every
period, there are equilibria in which both types of player $1$ have payoff no
more than $v_{1}^{\prime}$,

######  Theorem 2.

If $\omega_{t}=\\{A\\}$ with probability $1$ and
$y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$, then there exists
$\underline{\delta}\in(0,1)$ such that for every $\delta>\underline{\delta}$,
there exists an equilibrium in which both types of player $1$’s payoff is
$v_{1}^{\prime}$.

The proof of this result and a subsequent lemma are in Appendix B.

In order to understand the connections between the conclusion of Theorem 2 and
that of Theorem 1, we compare $v_{1}^{\prime}$ with player $1$’s expected
Stackelberg payoff $v_{1}^{*}$ and their minmax payoff. To start with, one can
verify that $v_{1}^{*}\geq v_{1}^{\prime}$ when players’ payoffs are generic
and the auxiliary game without communication admits a pure-strategy
equilibrium.121212The generic requirement is that player $1$ has a strict best
reply to every $b\in B$ for every $\theta\in\Theta$, and player $2$ has a
strict best reply to every $a\in A$. The existence of a pure-strategy
equilibrium in the auxiliary game without communication rules out zero-sum
games such as matching pennies, where the patient player cannot benefit from
committing to pure actions. Next, we introduce a class of games under which
$v_{1}^{\prime}$ is strictly less than $v_{1}^{*}$, and under an additional
supermodularity condition, $v_{1}^{\prime}$ equals player $1$’s minmax payoff.

######  Supermodularity Condition.

There exists a complete order on $A$ such that for every $\theta\in\Theta$,
$u_{1}(\theta,a,b)$ is strictly decreasing in $a$, and there exists
$\theta\in\Theta$ such that player $1$’s Stackelberg action in state $\theta$
is not the lowest element in $A$.

######  Lemma 1.

If every $\theta\in\Theta$ occurs with positive probability and the stage-game
payoffs satisfy supermodularity, then

  1. 1.

$v_{1}^{\prime}<v_{1}^{*}$.

  2. 2.

In addition, if there also exists a complete order on $B$ such that $u_{1}$ is
strictly increasing in $b$ and $u_{2}$ has strictly increasing differences in
$a$ and $b$, then $v_{1}^{\prime}$ is player $1$’s minmax payoff.

Condition 1 and the additional assumption in Lemma 1 fit applications such as
product choice games, where a firm finds it costly to exert high effort, can
strictly benefit from consumers’ trust, and can benefit from committing to
high effort in states where its production cost is low enough. The consumers
have stronger incentives to trust the firm when the latter exerts higher
effort. Our conditions also apply to games of entry deterrence (Kreps and
Wilson 1982, Milgrom and Roberts 1982), capital taxation (Phelan 2006),
monetary policy (Barro 1986), and trust games more generally (Liu and
Skrzypacz 2014).

##  4 Extensions

We note here that the conclusion of Theorem 1 extends to two alternative
scenarios.

### Announcing Product Quality:

Suppose that players move sequentially in the stage game. In period
$t\in\mathbb{N}$, player $1$ (e.g., a firm) chooses their effort $a_{t}\in A$,
privately observes the quality of its product $x_{t}\in X$ which is
distributed according to $g(\cdot|a_{t})\in\Delta(A)$, and makes an
announcement $m_{t}\in X$ about quality. Player $2_{t}$ (e.g., a consumer)
observes $m_{t}$ as well as whether $x_{s}$ coincides with $m_{s}$ for all
$s\leq t-1$ before choosing $b_{t}\in B$. We assume that $A$, $B$, and $X$ are
finite sets.

Player $1$ is either an honest type who strategically chooses actions
$a_{t}\in A$ but announces $x_{t}$ truthfully, or an opportunistic type who
strategically chooses both the actions and the announcements. Both types have
stage-game payoff $u_{1}(a_{t},b_{t})$ and discount factor $\delta\in(0,1)$.
Player $2_{t}$’s payoff is $u_{2}(x_{t},b_{t})$, i.e., their payoff depends
only on product quality and their purchasing decision. This fits the model of
Jullien and Park (2020) except that there is a positive probability of the
honest type, and the ex-post quality is not directly observed by subsequent
consumers. For every $x\in X$, let $\textrm{BR}_{2}(x)\subset B$ be the set of
pure best replies against $x$. Player $1$’s optimal commitment payoff is

$v^{**}\equiv\max_{a\in A}\Big{\\{}\sum_{x\in
X}g(x|a)\min_{b\in\textrm{BR}_{2}(x)}u_{1}(a,b)\Big{\\}}.$ (4.1)

######  Corollary 2.

If $g(\cdot|a)$ has full support for every $a\in A$, then for every
$\varepsilon>0$, there exists $\underline{\delta}\in(0,1)$ such that when
$\delta>\underline{\delta}$, every type of player $1$’s payoff in every Nash
equilibrium is at least $v^{**}-\varepsilon$.

The proof is in Appendix D, which uses similar ideas as the proof of Theorem
1.

Next we show that reputations for honesty cannot guarantee player $1$ their
optimal commitment payoff when product quality is a perfect signal of player
$1$’s effort. Suppose $X=A$ and $g(a|a)=1$ for every $a\in A$, and players’
stage-game payoffs are given by the following matrix:

$-$ | $T$ | $N$
---|---|---
$H$ | $1,2$ | $-1,0$
$L$ | $2,-2$ | $0,0$

Player $1$’s optimal commitment payoff is $1$, which can be obtained by
committing to play $H$.

We construct a Perfect Bayesian equilibrium in which player $1$’s payoff is
$0$. On the equilibrium path, both types of player $1$ play $L$ and announce
$L$ in every period, and player $2$s play $N$ at every on-path history. After
observing announcement $H$, player $2$s believe that player $1$ is the
opportunistic type and has played $L$ with probability $1/2$ in the current
period, and best reply by playing $N$. This equilibrium survives both when
player 2s can only observe whether $m_{t}$ matches with $x_{t}$ in all
previous periods, and when player $2$s can observe the values of $x_{t}$ and
$m_{t}$ in all previous periods.

### Making Announcements Before Knowing the Set of Feasible Actions:

In some applications, the patient player makes announcements before knowing
which of their actions are feasible, and an honest individual may break their
word when the action they announced turns out to be infeasible. Theorem 1
extends to this setting if (1) the honest type trembles and makes each
announcement with positive probability, and (2) the probability with which all
actions are feasible is close to $1$.

In period $t\in\mathbb{N}$, player $1$ observes $\theta_{t}\in\Theta_{t}$ and
makes an announcement about their intended action $m_{t}\in A_{t}$. Player
$2_{t}$ observes $m_{t}$, player $1$ observes the realization of
$\omega_{t}\in\Omega\equiv 2^{A}\backslash\\{\varnothing\\}$, and then both
players choose $(a_{t},b_{t})\in\omega_{t}\times B$ simultaneously. Future
player $2$s observe $y_{t}\equiv\mathbf{1}\\{a_{t}=m_{t}\\}$. We assume
$\\{\omega_{t},\theta_{t}\\}_{t\in\mathbb{N}}$ are i.i.d. over time, with
$p\in\Delta(\Omega\times\Theta)$ their joint distribution.

Player $1$ is either an opportunistic type who can take any action regardless
of their announcement, or an honest type who chooses $a_{t}=m_{t}$ as long as
$m_{t}\in\omega_{t}$. Both types of player $1$ tremble when making
announcements, i.e., there exists $\eta>0$ such that the probability with
which each type makes each announcement is at least $\eta$ at every
information set.

######  Corollary 3.

For every $\varepsilon>0$, there exist $\underline{\delta}\in(0,1)$,
$\overline{\eta}>0$, and $c\in(0,1)$, such that when
$\delta>\underline{\delta}$, $\eta\in(0,\overline{\eta})$ and the probability
that $\omega_{t}=A$ is at least $1-\eta c$, then each type of player $1$
receives payoff at least $v_{1}^{*}-\varepsilon$ in every Nash equilibrium.

The proof is in Appendix E. Unlike our baseline model and reputation models
with noisy monitoring such as Fudenberg and Levine (1992), when the honest
type uses the strategy of announcing their Stackelberg action and keeping
their word whenever it is feasible, their reputation may deteriorate in
expectation.

Our proof starts by showing that when $\omega_{t}=A$ with probability close to
$1$, the probability that the honest type keeps their word in equilibrium is
close to $1$, and for reputation to deteriorate when the honest type keeps
their word, the opportunistic type must also keep their word with probability
close to $1$. It implies that in those periods, player $2$ has a strict
incentive to best reply to player $1$’s announcement, and moreover, the amount
of reputation deterioration is small. By contrast, in “bad” periods where
player $2$ has a strict incentive not to best reply against player $1$’s
announcement, the probability that the opportunistic type breaks their promise
is large and keeping one’s word leads to a significant improvement in one’s
reputation. Although the number of bad periods can be unbounded, their
fraction goes to zero as the probability of $\omega_{t}=A$ goes to one.

##  Appendix A Proof of Theorem 1

Fix any Nash equilibrium $(\sigma_{o},\sigma_{h},\sigma_{2})$ and consider any
history $h^{t}$ that occurs with strictly positive probability under
$(\sigma_{o},\sigma_{h},\sigma_{2})$.

For $i\in\\{h,o\\}$, let $P^{\sigma_{i},\sigma_{2}}$ be the probability
measure over $Y^{\infty}$ induced by $(\sigma_{i},\sigma_{2})$. Denote player
2’s belief over player 1’s private history as a function of $h^{t}_{2}$ by
$\beta(\hat{h}^{t}_{1}|h^{t}_{2})$, and let $\sigma_{o}(h^{t}_{2})$ be the
expected distribution of opportunistic player 1’s joint announcement-action
pairs implied by $\beta(h^{t}_{1}|h^{t}_{2})$, with
$\hat{\sigma}_{o}(h^{t}_{2})$ and $\tilde{\sigma}_{o}(h^{t}_{2})$ the marginal
distributions of announcements and actions, respectively. Let $\pi_{t}$ be the
probability of the honest type according to player $2$’s belief in period $t$
after observing $\\{y_{0}...,y_{t-1}\\}$. According to Bayes rule,

$\pi_{t}=\frac{P^{\sigma_{h},\sigma_{2}}(y_{0},...,y_{t-1})\pi_{0}}{P^{\sigma_{h},\sigma_{2}}(y_{0},...,y_{t-1})\pi_{0}+P^{\sigma_{o},\sigma_{2}}(y_{0},...,y_{t-1})(1-\pi_{0})}.$
(A.1)

Let

$\alpha_{t}(m_{t})\equiv\pi_{t}\hat{\sigma}_{h}(h^{t}_{2})(m_{t})+(1-\pi_{t})\hat{\sigma}_{o}(h^{t}_{2})(m_{t}),$

which is the probability of announcement $m_{t}$ conditional on $h^{t}_{2}$.
Let $\xi_{t}(m_{t})$ be the probability that $a_{t}=m_{t}$ conditional on
$m_{t}$,

$\xi_{t}(m_{t})\equiv\frac{\pi_{t}\tilde{\sigma}_{h}(h^{t}_{2})(m_{t})}{\pi_{t}\hat{\sigma}_{h}(h^{t}_{2})(m_{t})+(1-\pi_{t})\hat{\sigma}_{o}(h^{t}_{2})(m_{t})}+\frac{(1-\pi_{t})\tilde{\sigma}_{o}(h^{t}_{2})(m_{t})}{\pi_{t}\hat{\sigma}_{h}(h^{t}_{2})(m_{t})+(1-\pi_{t})\hat{\sigma}_{o}(h^{t}_{2})(m_{t})}.$

Let $\xi_{t}$ be the unconditional probability that player $1$’s action
matches their announcement:

$\xi_{t}\equiv\sum_{a\in A}\alpha_{t}(a)\xi_{t}(a).$ (A.2)

Let $\underline{\rho}\equiv\min_{a\in A}\Pr(\omega_{t}=\\{a\\})$, which by
Assumption 1 is strictly positive. This implies that
$\alpha_{t}(m)>\underline{\rho}$ for every announcement $m\in A$. Let
$\overline{\lambda}\in(0,1)$ be the smallest real number such that for every
$\theta\in\Theta$, player $2$ strictly prefers one of the actions in
$\textrm{BR}_{2}(a^{*}(\theta))$ to all actions outside of
$\textrm{BR}_{2}(a^{*}(\theta))$ when they believe that player $1$ plays
$a^{*}(\theta)$ with probability strictly more than $\overline{\lambda}$.

Consider the honest type’s payoff when they use strategy
$\sigma_{h}^{*}\equiv(\widehat{\sigma}_{h}^{*},\widetilde{\sigma}_{h}^{*})$,
where $\widetilde{\sigma}_{h}^{*}(m)=m$ for every $m\in A$, and
$\widehat{\sigma}_{h}^{*}(\theta_{t},\omega_{t})=a^{*}(\theta_{t})$ when
$a^{*}(\theta_{t})\in\omega_{t}$ and is uniform over the actions in
$\omega_{t}$ when $a^{*}(\theta_{t})\notin\omega_{t}$. For any history
$h^{t}$, suppose there exists $m_{t}\in A$ such that
$\xi_{t}(m_{t})\leq\overline{\lambda}$, then $\xi_{t}\leq\xi^{*}\equiv
1-(1-\overline{\lambda})\underline{\rho}$. Let $d(\cdot||\cdot)$ denote the
KL-divergence, and let $F^{*}\equiv F(\cdot|a,a)$. Let

$D^{*}\equiv\min_{a\neq
m}d\Big{(}F^{*}\Big{\|}\xi^{*}F^{*}+(1-\xi^{*})F(\cdot|a,m)\Big{)}.$ (A.3)

Part 2 of Assumption 2 implies that $D^{*}>0$ and is independent of player
$1$’s discount factor $\delta$.

Part 1 of Assumption 2 implies that
$P^{\sigma_{h},\sigma_{2}}=P^{\sigma_{h}^{*},\sigma_{2}}$. Let
$F(y|h^{t}_{2})=\sum_{(a,m)\in A^{2}}F(y|a,m)\sigma_{o}(h^{t}_{2})(a,m)$ so
that $F(\cdot|h^{t}_{2}))$ denotes the distribution over $y_{t}$ induced by
$\sigma_{o}(h_{2}^{t})$.

Similar to Gossner (2011), the chain rule for relative entropy implies:

$\begin{split}-\log\pi_{0}&\geq
d\Big{(}P^{\sigma_{h},\sigma_{2}}\Big{|}\Big{|}\pi_{0}P^{\sigma_{h},\sigma_{2}}+(1-\pi_{0})P^{\sigma_{o},\sigma_{2}}\Big{)}\\\
&=d\Big{(}P^{\sigma_{h}^{*},\sigma_{2}}\Big{|}\Big{|}\pi_{0}P^{\sigma_{h},\sigma_{2}}+(1-\pi_{0})P^{\sigma_{o},\sigma_{2}}\Big{)}\\\
&=\mathbb{E}^{(\sigma_{h},\sigma_{2})}\Big{[}\sum_{t=0}^{\infty}d\Big{(}F^{*}\Big{|}\Big{|}\pi_{t}F^{*}+(1-\pi_{t})F(\cdot|h^{t}_{2})\Big{)}\Big{]},\end{split}$

where the first equality comes from the fact that $(\sigma_{h},\sigma_{2})$
and $(\sigma_{h}^{*},\sigma_{2})$ induce the same distribution over $y$ given
the first part of Assumption 2.

Therefore, $d(F^{*}||F(h^{t}))\geq D^{*}$ if $h^{t}$ is such that
$\xi_{t}(a_{t})\leq\overline{\lambda}$ for some $a_{t}\in A$, so the expected
number of such periods is at most

$\overline{T}(\pi_{0})\equiv\Big{\lceil}\frac{-\log\pi_{0}}{D^{*}}.\Big{\rceil}$
(A.4)

Hence the honest type’s payoff from $\sigma_{h}^{*}$ is at least

$\delta^{T(\pi_{0})}\Big{\\{}(1-\frac{\varepsilon}{\min_{\theta\in\Theta}p(\theta)})v_{1}^{*}+\frac{\varepsilon}{\min_{\theta\in\Theta}p(\theta)}\underline{v}_{1}\Big{\\}}+(1-\delta^{T(\pi_{0})})\underline{v}_{1},$
(A.5)

in which $\underline{v}_{1}$ is player $1$’s lowest stage-game payoff.
Expression (A.5) converges to $v_{1}^{*}$ when $\delta\rightarrow 1$ and
$\varepsilon\rightarrow 0$. Since the opportunistic type’s payoff is weakly
greater than the honest type’s payoff, their equilibrium payoff is also weakly
more than (A.5).

##  Appendix B Proofs of Theorem 2 and Lemma 1

### Proof of Theorem 2:

Suppose $(A^{\prime},\beta)$ solves (3.2) subject to (3.3), and consider the
following strategy profile: At every on-path history with $\theta_{t}=\theta$,
both types of player $1$ announce the same $a\in\arg\max_{a\in
A^{\prime}}u_{1}(\theta,a,\beta(a))$ and match their actions with their
announcements. Player $2$ chooses $\beta(a)$ following announcement $a$, and
chooses $\beta(a^{\prime})$ if player $1$’s announcement does not belong to
$A^{\prime}$, where $a^{\prime}$ is an arbitrary element of $A^{\prime}$. At
every $h^{t}$ where $y_{s}\neq 1$ for some $s<t$, player $2$ believes that
player $1$ is opportunistic. If $v_{1}^{min}\leq\widehat{v}_{1}$, then players
coordinate on the worst stage-game Nash equilibrium for player $1$. If
$v_{1}^{min}>\widehat{v}_{1}$, then players coordinate on the worst pure-
strategy Nash equilibirum in the second auxiliary game. Player $2$s’ incentive
constraints are trivially satisfied, and player $1$’s incentive constraint is
implied by (3.3).

### Proof of Lemma 1:

Let $\underline{a}\equiv\min A$ and let $\underline{b}$ be player $2$’s best
reply against $\underline{a}$. According to (3.2),
$v_{1}^{\prime}\leq\sum_{\theta\in\Theta}p(\theta)u_{1}(\theta,\underline{a},\underline{b})$.
According to (3.1),
$v^{*}\geq\sum_{\theta\in\Theta}p(\theta)u_{1}(\theta,\underline{a},\underline{b})$,
and the inequality is strict from the second part of Condition 1 and the fact
that each $\theta$ has strictly positive probability.

If $u_{1}$ is strictly decreasing in $b$ and $u_{2}$ has strictly increasing
differences, then $u_{1}(\theta,\underline{a},\underline{b})$ is player $1$’s
minmax payoff in state $\theta$. Since
$v_{1}^{\prime}\leq\sum_{\theta\in\Theta}p(\theta)u_{1}(\theta,\underline{a},\underline{b})$,
$v_{1}^{\prime}$ is player $1$’s minmax value.

##  Appendix C Proof of Corollary 1

Recall the definition of $\xi^{*}$ in the proof of Theorem 1. Let

$\widehat{\xi}\equiv 1-\underline{\rho}^{K}(1-\xi^{*}).$ (C.1)

Suppose the honest type announces the Stackelberg action whenever it is
available. By construction, if player $2_{t}$ believes that $a_{t}=m_{t}$ with
probability at least $\widehat{\xi}$ after observing
$\\{y_{0},...,y_{t-1}\\}$, then because $\omega=\\{a\\}$ with probability at
least $\underline{\rho}$, their posterior belief after observing at most $K$
realizations of $\\{z_{0},...,z_{t-1}\\}$ attaches probability at least
$\xi^{*}$ to $a_{t}=m_{t}$. This implies that player $2$ has an incentive to
best reply against player $1$’s announced actions. Let

$\widehat{D}\equiv\min_{a\neq
m}d\Big{(}F^{*}\Big{\|}\widehat{\xi}F^{*}+(1-\widehat{\xi})F(\cdot|a,m)\Big{)}.$
(C.2)

The same argument as in the proof of Theorem 1 implies that in expectation,
there exist at most

$\widehat{T}(\pi_{0})\equiv\Big{\lceil}\frac{-\log\pi_{0}}{\widehat{D}}\Big{\rceil}$
(C.3)

periods in which player $2$ believes that $a_{t}=m_{t}$ with probability less
than $\widehat{\xi}$ after observing $\\{y_{0},...,y_{t-1}\\}$. As a result,
the honest type’s payoff is at least $v^{*}$ when $\varepsilon\rightarrow 0$
and $\delta\rightarrow 1$.

##  Appendix D Proof of Corollary 2

Fix any equilibrium $(\sigma_{o},\sigma_{h},\sigma_{2})$ and consider any
history $h^{t}$ that occurs with strictly positive probability under
$P^{(\sigma_{o},\sigma_{h},\sigma_{2})}$. Let $\xi_{t}\in[0,1]$ be the
probability player 2 assigns to $\mathbf{1}\\{m_{t}=x_{t}\\}$ after observing
$(y_{0},...,y_{t-1})$ but before observing $m_{t}$. Let
$\xi_{t}(m_{t})\in[0,1]$ be the probability their belief attaches to
$\mathbf{1}\\{m_{t}=x_{t}\\}$ after observing $(y_{0},...,y_{t-1})$ and
$m_{t}$. Let $\alpha_{t}(m_{t})\in[0,1]$ be the probability of announcement
$m_{t}$ conditional on $(y_{0},...,y_{t-1})$. By definition,

$\xi_{t}=\sum_{m\in X}\alpha_{t}(m)\xi_{t}(m).$ (D.1)

Let $\underline{g}\equiv\min_{(a,x)\in A\times X}g(x|a)$, which is strictly
positive under the full support assumption. Let $\overline{\lambda}\in(0,1)$
be large enough such that for every $x\in X$, if player $2$ believes that $x$
occurs with probability at least $\overline{\lambda}$, then they strictly
prefer one of the actions in $\textrm{BR}_{2}(x)$ to all actions that do not
belong to $\textrm{BR}_{2}(x)$. Let $\xi^{*}\equiv
1-\underline{g}(1-\overline{\lambda})$. When $\xi_{t}\geq\xi^{*}$, they
believe that $m_{t}=x_{t}$ with probability more than $\overline{\lambda}$
after observing $m_{t}$. As in the proof of Theorem 1, one can show that the
expected number of periods in which $\xi_{t}\leq\xi^{*}$ is uniformly bounded
from above. Therefore, player $1$’s payoff is at least $v^{*}$ as
$\delta\rightarrow 1$.

##  Appendix E Proof of Corollary 3

For every $t\in\mathbb{N}$, let $\nu_{t}\in\\{0,1\\}$ be a random variable
such that

  1. 1.

$\nu_{t}=1$ if for every $a\in A$, when player $1$ announces $a$ period $t$,
player $2$ strictly prefers one of the actions in $\textrm{BR}_{2}(a)$ to all
actions that do not belong to $\textrm{BR}_{2}(a)$,

  2. 2.

$\nu_{t}=0$ otherwise.

There exists $\xi\in(0,1)$ such that for every $a\in A$, all actions outside
of $\textrm{BR}_{2}(a)$ are strictly inferior when player $2$ believes that
player $1$ plays $a$ with probability more than $\xi$. Let
$\pi_{t}\in\Delta\\{\gamma_{h},\gamma_{o}\\}$ be player $2$’s belief in period
$t$ after observing $\\{y_{0},...,y_{t-1}\\}$ but before observing $m_{t}$,
and let $\widehat{\pi}_{t}\in\Delta\\{\gamma_{h},\gamma_{o}\\}$ be player
$2$’s belief in period $t$ after observing $\\{y_{0},...,y_{t-1}\\}$ and
$m_{t}$. Let $l_{t}\equiv\log\frac{\pi_{t}(\gamma_{h})}{\pi_{t}(\gamma_{o})}$
and
$\widehat{l}_{t}\equiv\log\frac{\widehat{\pi}_{t}(\gamma_{h})}{\widehat{\pi}_{t}(\gamma_{o})}$.
Since player $1$ trembles with probability $\eta$, we have
$\widehat{l}_{t}-l_{t}\geq\log\eta$. As a result, there exists
$l^{*}\in\mathbb{R}_{+}$ such that $l_{t}\geq l^{*}$ implies that $\nu_{t}=1$.

Let $\Pr(\cdot|\sigma_{h})$ be the probability under the honest type’s
equilibrium strategy. Let $\Pr(\cdot|\sigma_{o})$ be the probability under the
opportunistic type’s equilibrium strategy. Let $\Pr(\cdot|\sigma_{h}^{*})$ be
the probability under the strategy of announcing the Stackelberg action in
each state, and keeps one’s word whenever it is feasible. Let $\rho\equiv
1-\Pr(\omega_{t}=A)$. We have

$\Pr(m_{t}=a_{t}|\sigma_{h})\in[1-\rho,1-\rho\eta],\quad\Pr(m_{t}=a_{t}|\sigma_{h}^{*})\in[1-\rho,1-\rho\eta],\quad\textrm{and}\quad\Pr(m_{t}=a_{t}|\sigma_{o})\leq
1-\rho\eta.$

In periods where $\nu_{t}=0$, the Markov’s inequality implies that
$\Pr(m_{t}=a_{t}|\sigma_{o})<1-\eta(1-\xi)$. When player $1$ plays according
to $\sigma_{h}^{*}$, Bayes Rule implies that

$\mathbb{E}[l_{t+1}-l_{t}|l_{t}]=D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{o}))-D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{h})),$
(E.1)

where $D(\cdot||\cdot)$ denoted the KL-divergence, and $p_{t}(\sigma)$ is the
distribution over $y_{t}$ under strategy $\sigma$. When $\nu_{t}=1$, we have

$D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{o}))-D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{h}))\geq-D(1-\rho||1-\eta\rho)\equiv-\beta.$
(E.2)

When $\nu_{t}=0$, we have

$D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{o}))-D(p_{t}(\sigma_{h}^{*})||p_{t}(\sigma_{h}))\geq
D(1-\rho||1-\eta(1-\xi))-D(1-\rho||1-\eta\rho)\equiv\alpha,$ (E.3)

where $D(x_{1}||x_{2})$ denotes the KL-divergence between a distribution that
attaches probability $x_{1}$ to $y_{t}=1$, and one that attaches probability
$x_{2}$ to $y_{t}=1$. When $\rho$ is small enough relative to $\eta$, the RHS
of (E.3) is strictly positive, and moreover, for any fixed $\eta>0$,
$\frac{\alpha}{\beta}\rightarrow+\infty$ as $\rho\rightarrow 0$.

We establish a lower bound for the expected value of
$\sum_{t=0}^{\infty}(1-\delta)\delta^{t}\nu_{t}$ when $\delta$ is close enough
to $1$. Recall that $y_{t}=\mathbf{1}\\{a_{t}=m_{t}\\}$. Let $Z_{t}$ be a
random variable such that

$Z_{t}=\log\frac{\Pr(y_{t}|\sigma_{h})}{\Pr(y_{t}|\sigma_{o})}\textrm{ with
probability }\Pr(y_{t}|\sigma_{h}^{*})\textrm{ for every }y_{t}\in Y.$

Our analysis above suggests that when $\nu_{t}=1$, we have
$\mathbb{E}[Z_{t}|\sigma_{h}^{*}]\geq-\beta$, and when $\nu_{t}=0$, we have
$\mathbb{E}[Z_{t}|\sigma_{h}^{*}]\geq\alpha$.

######  Claim 1.

For every $\varepsilon>0$, there exists $T\in\mathbb{N}$ such that for every
$t\geq T$, $\mathbb{E}[\sum_{s=0}^{t-1}\nu_{s}|\sigma_{h}^{*}]\geq
t(\frac{\alpha}{\alpha+\beta}-\varepsilon)$ with probability more than
$1-\varepsilon$.

Our proof uses the Azuma-Hoeffding’s inequality:

######  Lemma 2.

Let $\left\\{Z_{0},Z_{1},\cdots\right\\}$ be a martingale such that
$|Z_{k}-Z_{k-1}|\leq c_{k}$. For every $N\in\mathbb{N}$ and $\epsilon_{1}>0$,
we have

$\Pr[Z_{N}-Z_{0}\geq\epsilon_{1}]\leq\exp\left(-\frac{\epsilon_{1}^{2}}{2\sum_{k=1}^{N}c_{k}^{2}}\right).$

###### Proof of Claim 1:.

Construct a martingale process $\\{\widetilde{l}_{t}\\}_{t\in\mathbb{N}}$
recursively. Let $\widetilde{l}_{0}\equiv l_{0}$, and for every
$t\in\mathbb{N}$, let
$\widetilde{l}_{t+1}\equiv\widetilde{l}_{t}+Z_{t}-\mathbb{E}[Z_{t}|\widetilde{l}_{t}]$.
Suppose
$\frac{1}{t}\mathbb{E}[\sum_{s=0}^{t-1}\nu_{s}|\sigma_{h}^{*}]\leq\frac{\alpha}{\alpha+\beta}-\varepsilon_{1}$,
then

$\sum_{s=0}^{t-1}\mathbb{E}[Z_{s}|\sigma_{h}^{*}]\geq
t\varepsilon_{1}(\alpha+\beta).$ (E.4)

Therefore,

$\Pr(l_{t}\leq
l^{*}|\sigma_{h}^{*})=\Pr\Big{(}\widetilde{l}_{t}-\widetilde{l}_{0}\leq
l^{*}-l_{0}-t\varepsilon_{1}(\alpha+\beta)\Big{|}\sigma_{h}^{*}\Big{)}\leq\exp\Big{(}-\frac{(l^{*}-l_{0}-t\varepsilon_{1}(\alpha+\beta))^{2}}{2tC^{2}}\Big{)},$
(E.5)

where $C$ is the difference between the largest realization of $Z_{t}$ and the
smallest realization of $Z_{t}$. The RHS of (E.5) vanishes to zero
exponentially as $t\rightarrow+\infty$. Since $\nu_{t}=1$ when $l_{t}\geq
l^{*}$, we know that for every $\varepsilon_{0}>0$, there exists
$T_{1}\in\mathbb{N}$, such that for every $t\geq T_{1}$,
$\mathbb{E}[\sum_{s=0}^{t-1}\nu_{s}|\sigma_{h}^{*}]\leq
t\Big{(}\frac{\alpha}{\alpha+\beta}-\varepsilon_{1}\Big{)}$ implies that
$\nu_{t}=1$ with probability at least $1-\varepsilon_{0}$, and by setting
$\epsilon_{0}<\frac{\beta}{\alpha+\beta}$ we obtain in this case that
$\mathbb{E}[\sum_{s=0}^{t}\nu_{s}|\sigma_{h}^{*}]-\mathbb{E}[\sum_{s=0}^{t-1}\nu_{s}|\sigma_{h}^{*}]\geq
1-\varepsilon_{0}>\frac{\alpha}{\alpha+\beta}$. Then for every $t>T_{1}$, one
can show by induction that
$\mathbb{E}[\sum_{s=0}^{t-1}\nu_{s}|\sigma_{h}^{*}]\geq(t-T_{1}-1)(\frac{\alpha}{\alpha+\beta}-\varepsilon_{1})$,
and the claim follows by choosing any $\epsilon>\epsilon_{1}>0$, and $T\geq
T_{1}+1+\frac{\alpha}{(\epsilon-\epsilon_{1})(\alpha+\beta)}$. ∎

We use the following well-known equation:

$\mathbb{E}[\sum_{t=0}^{\infty}(1-\delta)\delta^{t}\nu_{t}|\sigma_{h}^{*}]=(1-\delta)^{2}\sum_{t=0}^{+\infty}\delta^{t}\underbrace{\sum_{s=0}^{t}\mathbb{E}[\nu_{s}|\sigma_{h}^{*}]}_{\geq(\frac{\alpha}{\alpha+\beta}-\varepsilon)(t+1)\textrm{
with probability close to 1}}.$ (E.6)

Claim 1 and (E.6) imply that for every $\widehat{\varepsilon}>0$, there exists
$\overline{\delta}\in(0,1)$, such that for every
$\delta\in(\overline{\delta},1)$, we have

$\mathbb{E}[\sum_{t=0}^{\infty}(1-\delta)\delta^{t}\nu_{t}|\sigma_{h}^{*}]\geq\frac{\alpha}{\alpha+\beta}-\widehat{\varepsilon}.$
(E.7)

Recall that $v^{*}$ is player $1$’s expected pure Stackelberg payoff. Without
loss of generality, we normalize player $1$’s worst stage-game payoff to $0$.
If $\nu_{t}=1$, then the honest type’s expected payoff from announcing their
Stackelberg action in every state is at least $(1-\rho-\eta)v^{*}$. If
$\nu_{t}=0$, then the honest type’s expected payoff is at least $0$. Pick
$\overline{\delta}\in(0,1)$ such that
$\mathbb{E}[\sum_{t=0}^{\infty}(1-\delta)\delta^{t}\nu_{t}]\geq\frac{\alpha}{\alpha+\beta}-\widehat{\varepsilon}$,
and pick $\rho$ small enough such that $\frac{\alpha}{\alpha+\beta}$ is
greater than $1-\widehat{\varepsilon}$, the honest type’s payoff is at least

$(1-2\widehat{\varepsilon})(1-\eta-\rho)v^{*}.$

There exists $c\in(0,1)$ such that the above expression is greater than
$v^{*}-\varepsilon$ when $\eta$ and $\widehat{\varepsilon}$ are small enough,
and $\rho\leq c\eta$.

## References

  * Atakan and Ekmekci (2015) Alp Atakan and Mehmet Ekmekci.  Reputation in the long-run with imperfect monitoring.  _Journal of Economic Theory_ , 157:553–605, 2015.
  * Awaya and Krishna (2016) Yu Awaya and Vijay Krishna.  On communication and collusion.  _American Economic Review_ , 106(2):285–315, 2016.
  * Barro (1986) Robert Barro.  Reputation in a model of monetary policy with incomplete information.  _Journal of Monetary Economics_ , 17(1):3–20, 1986.
  * Celentani et al. (1996) Marco Celentani, Drew Fudenberg, David Levine, and Wolfgang Pesendorfer.  Maintaining a reputation against a long-lived opponent.  _Econometrica_ , 64(3):691–704, 1996.
  * Charness and Dufwenberg (2006) Gary Charness and Martin Dufwenberg.  Promises and partnership.  _Econometrica_ , 74(6):1579–1601, 2006.
  * Chen (2011) Ying Chen.  Perturbed communication games with honest senders and naive receivers.  _Journal of Economic Theory_ , 146(2):401–424, 2011.
  * Chen et al. (2008) Ying Chen, Navin Kartik, and Joel Sobel.  Selecting cheap-talk equilibria.  _Econometrica_ , 76(1):117–136, 2008.
  * Fudenberg and Levine (1983) Drew Fudenberg and David Levine.  Subgame-perfect equilibria of finite and infinite horizon games.  _Journal of Economic Theory_ , 31(2):251–268, 1983.
  * Fudenberg and Levine (1989) Drew Fudenberg and David Levine.  Reputation and equilibrium selection in games with a patient player.  _Econometrica_ , 57(4):759–778, 1989.
  * Fudenberg and Levine (1992) Drew Fudenberg and David Levine.  Maintaining a reputation when strategies are imperfectly observed.  volume 59(3), pages 561–579. 1992.
  * Gneezy (2005) Uri Gneezy.  Deception: The role of consequences.  _American Economic Review_ , 95(1):384–394, 2005.
  * Gneezy et al. (2018) Uri Gneezy, Agne Kajackaite, and Joel Sobel.  Lying aversion and the size of the lie.  _American Economic Review_ , 108(2):419–453, 2018.
  * Gossner (2011) Olivier Gossner.  Simple bounds on the value of a reputation.  _Econometrica_ , 79(5):1627–1641, 2011.
  * Jullien and Park (2014) Bruno Jullien and In-Uck Park.  New, like new, or very good? reputation and credibility.  _Review of Economic Studies_ , 81(4):1543–1574, 2014.
  * Jullien and Park (2020) Bruno Jullien and In-Uck Park.  Communication, feedbacks and repeated moral hazard with short-lived buyers.  _Working Paper_ , 2020.
  * Kartik (2009) Navin Kartik.  Strategic communication with lying costs.  _Review of Economic Studies_ , 76(4):1359–1395, 2009.
  * Kartik et al. (2007) Navin Kartik, Marco Ottaviani, and Francesco Squintani.  Credulity, lies, and costly talk.  _Journal of Economic Theory_ , 134(1):93–116, 2007.
  * Kreps and Wilson (1982) David Kreps and Robert Wilson.  Reputation and imperfect information.  _Journal of Economic Theory_ , 27(2):253–279, 1982.
  * Liu and Skrzypacz (2014) Qingmin Liu and Andrzej Skrzypacz.  Limited records and reputation bubbles.  _Journal of Economic Theory_ , 151:2–29, 2014.
  * Milgrom and Roberts (1982) Paul Milgrom and John Roberts.  Predation, reputation, and entry deterrence.  _Journal of Economic Theory_ , 27(2):280–312, 1982.
  * Pei (2020) Harry Pei.  Trust and betrayals: Reputational payoffs and behaviors without commitment.  _Theoretical Economics, forthcoming_ , 2020.
  * Phelan (2006) Christopher Phelan.  Public trust and government betrayal.  _Journal of Economic Theory_ , 130(1):27–43, 2006\.
  * Schmidt (1993) Klaus Schmidt.  Commitment through incomplete information in a simple repeated bargaining game.  _Journal of Economic Theory_ , 60:114–139, 1993.
  * Sobel (2017) Joel Sobel.  A note on pre-play communication.  _Games and Economic Behavior_ , 102:477–486, 2017.
  * Sugaya and Wolitzky (2020) Takuo Sugaya and Alexander Wolitzky.  Communication and community enforcement.  _Working Paper_ , 2020.
  * Watson (1993) Joel Watson.  A“reputation” refinement without equilibrium.  _Econometrica_ , 61(1):199–205, 1993.


# Attacking Hardware AES with DFA

Yifan Lu This work was not supported and do not represent the approval or
rights of any third parties<EMAIL_ADDRESS>
###### Abstract

We present the first practical attack on a hardware AES accelerator with 256
bit embedded keys using DFA. We identify the challenges of adapting well-known
theoretical AES DFA models to hardware under attack from voltage fault
injection and present solutions to those challenges. As a result, we managed
to recover 278 real-world AES-256 keys from a secure computing system in a
matter of hours with minimal cost.

##  I Introduction

Although there is a wealth of work in differential fault analysis (DFA)
attacks on AES [8] and it is well understood that such attacks works on
hardware AES accelerators [10], there has been few practical attacks on real-
world targets. In 2012, Sony released their second hand-held gaming console,
the PlayStation Vita. Although it was not the runaway success of its
predecessor [13], Sony thoroughly improved the software and hardware security
features on their new console [15]. At the root of their secure boot system is
a cryptographic accelerator (only accessible by a dedicated security CPU) that
operates with keys embedded in the silicon which are not directly accessible
by software. The keys can only be referenced through hardware protected key-
slots. By obfuscating the keys this way, the designers hope that in the event
that the system is compromised and attackers wish to use the device as a
black-box to decrypt data, they can reference new key-slots in a firmware
upgrade and re-secure the system. This works as long as both of the following
points hold true:

  1. 1.

The system is not compromised before it locks out the important key-slots. The
Vita will always revoke the permission to use a key-slot when it is no longer
needed. Unused key-slots are also locked down early in the boot process.

  2. 2.

The keys themselves cannot be extracted by the attacker even if she
compromises the secure processor. Otherwise, the permissions enforced by the
cryptographic accelerator can be bypassed.

It has already been demonstrated [14] that assumption 1 is broken with fault
injection attacks on the secure processor (called “F00D”) and therefore the
security has already been defeated. However, we wish to go farther and break
assumption 2 as well. We do just that with a DFA attack on the Vita’s
cryptographic accelerator (which we nicknamed “Bigmac”).

###  I-A AES

The Rijndael cipher [9], known more commonly as AES, is a substitution
permutation based cipher that is widely used for encryption to ensure
confidentiality of data. The cipher operates in $N$ rounds where $N$ is $10$
for AES-128 and $14$ for AES-256. In each round except the last, there are
four operations performed on a $4\times 4$ state matrix which is initialized
before the first round by each plain-text byte XORed with the first round key.
There are $N+1$ round keys generated through a separate process not described
here. The state operations are defined briefly:

  1. 1.

SubBytes is the substitution step where a non-linear function is applied on
the input byte.

  2. 2.

ShiftRows performs a cyclic rotation on each row of the state.

  3. 3.

MixColumns linearly combines the elements in each column. It can be
represented as a multiplication of each column with a constant matrix. This
step is skipped for the last round.

  4. 4.

AddRoundKey ties the result to the key by XORing each element with an element
from the current round key.

###  I-B DFA

It would be remiss to not start with a reference to Boneh, Demillo, and
Lipton’s 1997 paper [6]. The authors described how an incorrect RSA signature
produced by faulty hardware can be used to retrieve the private key. Shortly
thereafter, Biham and Shamir [5] discovered that faulty results from symmetric
encryption systems like DES can also be used to extract the secret key. They
called the attack Differential Fault Analysis because they used the
information gleaned from related ciphertexts produced from good hardware and
faulty hardware to find the secret key.

DFA can also be applied to AES [10]. According to Dusart et al., if the fault
is modeled by a single unknown byte, $\epsilon$, which is XORed into a
specific element of the state matrix before MixColumns of round $N-1$, then
one can solve for four bytes of the round $N$ key. The high level idea is that
the non-linear structure of the S-Box can be abused to leak information about
the state. As an example, Dusart presented the following system of equations
for a fault $\epsilon$ at a fixed location in round $N-1$:

$\left\\{\begin{aligned} s(x_{0}+2\epsilon)&=s(x_{0})+\epsilon^{\prime}_{0}\\\
s(x_{1}+\epsilon)&=s(x_{1})+\epsilon^{\prime}_{1}\\\
s(x_{2}+\epsilon)&=s(x_{2})+\epsilon^{\prime}_{2}\\\
s(x_{3}+3\epsilon)&=s(x_{3})+\epsilon^{\prime}_{3}\\\ \end{aligned}\right.$
(1)

The S-Box of SubBytes is represented as $s(x)$ and the unknowns are
$x_{0},x_{1},x_{2},x_{3},\epsilon$. The observed faulty ciphertext difference
are
$\epsilon^{\prime}_{0},\epsilon^{\prime}_{1},\epsilon^{\prime}_{2},\epsilon^{\prime}_{3}$.
With each fault, we observe a different set of $\epsilon^{\prime}$ and assume
a different unknown $\epsilon$ but $x$ does not change. After enough samples,
we reduce the solution set to $1$ and solve for $x$. Once the state bytes are
revealed, it is easy to extract four bytes of the round $N$ key. Repeat the
whole procedure with faults at different offsets, and it is possible to
recover the entire round $N$ key and going from the round $N$ key to the
original key is just a matter of reversing the key scheduling algorithm (which
is not secret). Dusart et al. were able to extract an AES-128 key by
”analyzing less than 50 ciphertexts.”

Recent progress in AES DFA theory since then has been in reducing the number
of needed ciphertexts [1, 12, 23] as well as relaxing the fault model to
handle more faults (or earlier faults) [12, 16, 20]. There has also been
attacks targeting the key schedule rather than the round states [11]. In
practical attacks, AES DFA has been shown to work on ARM processors [4], on
FPGA [2], and on an ASIC [21].

###  I-C Prior Work

Our work is closest in design to Selmane’s [21] for a smart-card. Their target
was also a dedicated AES accelerator running alongside a CPU. They also used
Piret’s model [20] for performing the DFA attack. The method for inducing the
faults was timing violations. However, one key difference is that they created
the timing violations by under-powering the smart-card such that the AES
operations will be faulty but the CPU can still operate correctly. Our method
for creating timing violations is from voltage glitching [14]. Under-powering
does not work for us because the global critical paths are not inside Bigmac.
When we try to under-power the device, the F00D security processor will not
execute code, and we cannot control Bigmac. Additionally, by using a voltage
fault injection, we can create precise glitches that target specific AES
rounds. This is important for reducing the number of needed faulty
ciphertexts.

We used Piret’s model111It should be noted that more than a decade of work has
taken place since Piret’s results and there exists many AES DFA models that
have lesser requirements on the required faults. However, we were unable to
find any open-source implementation of the newer ideas. Because we can control
precisely where the fault takes place, we can make use of this constrained
model and it saves us the time of implementing our own DFA tool from scratch.
of a single fault between the MixColumns of round $N-3$ and $N-2$ (which
itself is an extension of the original model from Dusart described above).
This model only requires two faulty ciphertexts and the correct ciphertext to
recover the final round key. We used an implementation of the attack on this
model called phoenixAES [22]. This tool was developed as a way of attacking
white-box AES [7], but we find that it can also process hardware generated
faults without any modification.

Because it is not possible to characterize each faulty ciphertext as “good” or
not (i.e. fits the assumptions of the model) without knowing the key, we
developed a brute force approach to try every pairing of ciphertexts. We
believe this is similar to an approach taken by Riscure [24] but was unable to
verify this because they did not go into details about their implementation.

##  II Fault Injections

Piret’s fault model requires exactly one byte of the AES state to be corrupted
between the MixColumns operation of round $N-3$ and $N-2$ [20]. To recover the
round $N$ key, we need two different single-byte corruptions of this type. The
first practical challenge is to create fault injections that can meet this
requirement. We used voltage glitching to inject the fault because of previous
success [14] in voltage glitching the F00D processor on the same target.
Specifically, we applied the crowbar voltage glitching technique [19] because
of its low cost and high applicability.

###  II-A Hardware AES

Although we do not know the exact design of Bigmac’s AES implementation, we
can reasonably assume that it is optimized in some way. We know that SubBytes
and MixColumns (as well as their inverse) are the most expensive operation
[18] and therefore it is highly likely that the critical paths are within
those operations. This means that with the right timing, we can achieve a
glitch that only affects one operation and that it is possible to meet the
requirement for a one byte corruption.222Ideally we can glitch only for the
duration of one operation, but optimized AES implementations typically perform
all four operations of a round in one or two cycles. However, because we know
that the path length for each operation is not equal, we do not run into the
awkward situation of faults occurring in multiple operations, which does not
meet our requirement for a single byte fault.

From a software perspective, Bigmac has a simple command interface. It has
memory-mapped registers accessible only by the F00D security processor at
physical address 0xE0050000. The ARM based application processor cannot see
this address range at all and must interface with F00D to use Bigmac
indirectly. Only TrustZone on the ARM processor can communicate with F00D.
Bigmac has support for AES block modes CBC, ECB, and CTR, with key-sizes of
128, 192, and 256. In addition, it also supports AES-CMAC, HMAC-SHA, SHA,
memcpy, memset, and generating random numbers. To perform a Bigmac operation,
F00D passes in a source and destination address, the length of the data, the
operation, and (when required) the address of the IV. For keyed operations,
Bigmac accepts either a fixed key written to a set of input registers directly
or the index of a key-slot. It is also possible to set the output destination
to a key-slot instead of a memory address in some cases.

Each key-slot has a permission bit associated with it. Some key-slots are only
allowed to encrypt data to another key-slot. We call these “master” key-slots.
It is normally not possible to directly observe ciphertext produced by
encrypting with a master key. There are $30$ master keys in the PlayStation
Vita, some of which are device unique and others which are common to all Vita
devices. There are $250$ additional non-master key-slots (some device unique)
not derived by software that we can directly observe the ciphertext. Finally,
the remaining key-slots are either derived from the master keys along with
data from the firmware or loaded directly from software decrypted by Bigmac.
Key-slots can also be disabled such that they cannot be used until the next
reset. Most keys including all master keys are disabled early in boot before
the operating system is loaded.

The results of this paper include the procedure we devised to obtain $248$
non-master keys and all $30$ master keys by leveraging DFA, code execution
through voltage glitching, a hardware vulnerability, and the computation power
of about 500 core-hours.

###  II-B Glitch Parameters

The effects of crowbar voltage glitching depends largely on two factors: when
the crowbar circuit is activated and how long it stays activated [19]. To
reduce the variance in our measurements, we replace the target’s external
clock input with our own clock running at $f=$12\text{\,}\mathrm{MHz}$$.
Bigmac runs with a clock derived from the external clock with frequency
$f_{c}$. From measurement of Bigmac’s AES timing, if we assume that one AES
round takes one clock cycle, then $f_{c}=f$. Our glitching hardware also runs
with a clock derived from the same source with frequency $f_{g}=4f$. When we
refer to “cycles”, it is in units of $1/f$.

Since we are dealing with AES-256, it is necessary to retrieve two round keys
in order to recover the full key [10]. This means we need to find two sets of
parameters: $n_{N-2},m_{N-2}$ and $n_{N-3},m_{N-3}$. We define $n$ to be the
offset from a fixed trigger signal before the AES engine starts to the crowbar
activation and $m$ to be the duration of the crowbar activation. Since we are
applying Piret’s model, this means we have to target round $N-2$ and round
$N-3$.

##  III Setup

Boot time code execution is a prerequisite for interfacing with Bigmac before
the target key-slots are disabled. We reproduce the setup described in [14] to
achieve this. As such, we make use of the ChipWhisperer Lite, an open source
hardware fault injection and side channel analysis tool. We designate, through
a series of scripts, two separate modes of operation. In boot mode, we
configure the ChipWhisperer to perform the previously described voltage glitch
attack on F00D to gain early boot execution. Once that succeeds, we load an
RPC payload that interfaces with the ChipWhisperer through UART serial and
enter DFA mode. In DFA mode, we send the plaintext through the serial port and
use the RPC interface to set up Bigmac and toggle a GPIO pin before starting
the AES operation. Then we perform a voltage glitch using ChipWhisperer by
waiting $n$ cycles after a GPIO toggle to activate the glitch circuit and turn
it off after $m$ cycles. The device will then return the output ciphertext
through the serial port. The same glitching hardware is used with different
configurations for the two modes. We will only describe our setup for DFA
mode.

###  III-A Reducing Capacitance

To minimize the impact of the power distribution network (PDN), we make a
couple of modifications to the PCB. First, we trace and remove every
decoupling capacitor to the core 1.1V voltage domain. Figure 4 shows the
capacitors that were removed.

Next, we introduce a $10\text{\,}\mathrm{\SIUnitSymbolOhm}$ shunt
resistor333Originally we attempted to do a DPA attack but gave up after a
couple of months without any results. We believe that because the AES engine
was designed for power efficiency, the SNR was too low to get accurate
measurements for this device and $10\text{\,}\mathrm{\SIUnitSymbolOhm}$ was
the highest shunt we can choose that still allows the device to operate. The
same shunt resistor was used for the DFA attack because it was already in
place. There is no solid evidence that the shunt resistor is needed for DFA,
but empirical results show that without the shunt resistor in place, the
minimum width of the glitch needs to be about 3x as much for the system to
show any faulty behavior. by cutting the trace from the device’s own power
management chip to the main SoC (figure 5). We designed a simple board (figure
6) that contains the shunt resistor, a filter capacitor, and ports for an
external power supply, a measurement probe, and a SMA connector to the
ChipWhisperer to perform the voltage glitch.

###  III-B Measurements

On the target device, we use our RPC interface to toggle a GPIO pin and
immediately start the Bigmac AES operation. Using a CW501 differential probe
for ChipWhisperer sampling at $f$, we capture the power trace triggered by the
GPIO pin. Using these traces, we can get a rough idea of when the AES
operation takes place.444Another reason for the low SNR that made DPA
difficult was due to the fact that the DMA reads and writes dominates the
spikes we see (not AES rounds). We confirmed this by running AES-ECB and AES-
CBC and noticed that two extra spikes appear for reading and writing the IV
from memory. After setting the destination to a key-slot (instead of SRAM), we
observe half as many spikes. Figure 1 shows what the traces look like.

Figure 1: 1000 samples at $12\text{\,}\mathrm{MHz}$ done three times. The GPIO
toggles on at 0 and off at 600. The entire 14 rounds of AES takes place in the
“dip” around 250.

###  III-C Encrypt vs Decrypt

When we targeted the AES-ECB-256 encrypt operation, we ran into issues with
the corrupted ciphertext that we suspect was due to both the AES state
operation and the key scheduling being faulted at the same time.555Our simple
analysis fails if the key schedule was also faulty. It is likely that the key
scheduling was taking place in parallel with the encrypt operation. When we
target the AES-ECB-256 decrypt operation, the issues we observed dramatically
decreased, which confirms our hypothesis. As a matter of convention, we will
continue to refer to the AES engine output as the “ciphertext” and the round
number in reference to the encryption round even though our fault injection
was on the decrypt operation.

###  III-D Simple Analysis

By injecting faults at offsets $240<n<280$ and width $m=1$ we were able to
observe faulty ciphertexts. However, most of the faulty texts were not at the
right round and therefore cannot be used for Piret’s DFA model. Normally, this
would not be an issue as we can just throw out results that fail the attack,
however for reasons that will be made clear later, it is to our advantage that
we maximize the probability that each faulty ciphertext could be “useful.” To
do this, we need to constrain $n$ more and identify the precise round that
each $n$ value affects. Following the idea in [25], we setup Bigmac with a
known key and then perform a faulted decrypt operation. Then we try to encrypt
(the inverse operation) the faulty ciphertext with the same key and identify
the first step where the state got corrupted.

More specifically, we design an analysis script that performs two AES encrypt
operations in parallel: one on the expected ciphertext and one on the faulty
ciphertext. After each step, we count the number of bits that differ in the
state, and we return the round and step that has the least number of different
bits. This works with high probability because AES is designed to have
diffusion, so each step after the fault would, on average, be more different
from the step before it. Table I shows some example output from this analysis.
Figure 2 shows the distribution of where the fault was seen and figure 3 shows
the distribution of the number of bits corrupted.

Table I: Sample Analysis

Decrypt Output | $\boldsymbol{m}$ | $\boldsymbol{n}$
---|---|---
Corrupted Bit Mask | Round | Operation
9E8EDBEBE1CF276208912BB325CF6E7F | - | -
00000000000000000000000000000000 | - | -
5FF5D6AEADFF594817F4FB3F565EB5F1 | 282 | 1
00000000000000400000002000000000 | 3 | MixColumns
6D139A0FB71775A4C55F8E6C2B88162B | 281.5 | 1
00004000000000000000000000000000 | 4 | MixColumns
F3B414E25E4CF5B1D7CEA101C61A9A3C | 281.5 | 1
00014203000020200000000000000020 | 4 | MixColumns
9D7CEF8A3B9E222FAC826D6E21BC6BC3 | 279.5 | 1
00104000000000000004101200000060 | 7 | MixColumns
A1A68EFB05B99D0E7C1C18328265F2BD | 279.5 | 1
00104000000000000000000000000020 | 7 | MixColumns
621A9AE2F689F316DC1C8BA8F5794C4C | 277.5 | 1
00004000000000000000000000000000 | 10 | MixColumns
53BA4B36688166424E5E7ACEFBDF8357 | 276.75 | 1
18021209000000000000000000000020 | 11 | MixColumns
48E042EB3A7E7015C8293C85089F615E | 275.5 | 1
00000000000000000000000000000004 | 13 | MixColumns

  * •

Selected sample analysis results from AES-256 decrypting input
00000000000000000000000000000000 with key-slot 0x3FF. The first row is the
expected output while the remaining rows are results from a fault at offset
$m$ with width $n$. The mask shows which bits in the AES state was corrupted.
The round and operation is the step where the AES state was corrupted.

Figure 2: Distribution of the round operation faulted by the glitch. The
operation number is in order of an encrypt round. $1$ is SubBytes and $3$ is
MixColumns. Figure 3: Distribution of the number of bits in the state
corrupted. The majority of the corruptions are a single bit.

We notice that for certain value of $m$ (such as the ones shown in table I),
we are able to cause faults in the MixColumns of a specific round the vast
majority of the time. This is evidence that our glitching setup is robust and
precise enough to perform Piret’s DFA attack.

Table II: Glitch Parameters

| AES-128 | AES-256 | AES-256
---|---|---|---
| Fixed | Non-master Slot | Master slot
$n_{N-2}$ | $270.75$ | $271.5$ | $282.25$
$n_{N-3}$ | $270.25$ | $272.25$ | $281.5$

  * •

Offsets found for three kinds of operations: AES-128 encrypt with a fixed key
(only used for debugging our setup), AES-256 decrypt with a non-master key-
slot, and AES-256 decrypt with a master key-slot. Glitch width is $n=1$ for
all cases.

##  IV Attack

With the offsets found from the analysis (table II), we can collect faulty
ciphertext which are (with high probability) from the required round. However,
there is no guarantee that the faults are only a single byte or that we can
cause two different single byte faults per round. Therefore, we need to do
some post-processing.

###  IV-A Filtering out multi-byte corruptions

Recall that Piret’s model requires two different single byte corruptions to
recover a single round key. However, as observed in table I and figure 3, the
structure of our faults appear to be 1-5 bits flipped. If all the bits flipped
are inside a single byte, then we are good. However, it is clear that not
every faulty ciphertext has the bit flips confined to a single byte.

Fortunately, this is an easy problem to solve. The DFA attack will fail (no
solution to the equations) if the wrong faulty ciphertexts are used.
Therefore, if we collect $M$ faulty ciphertexts, we can just attempt the DFA
attack with all ${M\choose 2}=O(M^{2})$ possible pairings.

###  IV-B Using multi-byte corruptions

The above works well, and we were able to recover a many key-slots with enough
samples. For the remaining key-slots which we were unable to find a pair of
required faulty ciphertexts after hours of sampling. We have to improvise
another workaround.666We could have implemented a different DFA fault model
which is less constrained but it was easier to improvise a more inefficient
method.

First, notice from table I that the mask of corrupted bits show some bits are
more likely to be flipped than others—even if the fault happens in different
rounds. The explanation for this phenomenon is the physical hardware data path
for each bit of the state is not equal. We mentioned previously that certain
operations (such as MixColumns) are more likely to fault because the data
paths are longer than those of other operations and that makes a timing
violation more likely. However, even within MixColumns, there are differences
in the data path for each bit of the state.777Predicting which bit is more
likely to flip is difficult because it is data dependent as well as process
dependent.

Given a collection of faulty ciphertexts, we define a “static fault” to be any
bit corruption that is common to all the ciphertexts and a “dynamic fault” to
be the bit corruption(s) that only occur in only some faulty ciphertexts.

####  IV-B1 Second Order DFA

We claim that any number of static faults do not affect the results of DFA.
Taking any existing AES DFA technique and it is possible to relax the
requirement for a “correct” ciphertext to that of one that only contains
static faults.

We prove this claim for Dusart’s example DFA attack on round $N-1$. Let matrix
$S_{r,\text{Op}}$ be the correct state at round $r$ with operation Op and let
$F_{r,\text{Op}}$ be the faulty state matrix. Matrix $Z$ contains the static
faults (up to 16 bytes) and $A_{0}$ is the matrix constant for MixColumns.

$\displaystyle Z$
$\displaystyle=\begin{pmatrix}\zeta_{1}&\zeta_{2}&\zeta_{3}&\zeta_{4}\\\
\zeta_{5}&\zeta_{6}&\zeta_{7}&\zeta_{8}\\\
\zeta_{9}&\zeta_{10}&\zeta_{11}&\zeta_{12}\\\
\zeta_{13}&\zeta_{14}&\zeta_{15}&\zeta_{16}\\\ \end{pmatrix}$ (2)
$\displaystyle A_{0}$ $\displaystyle=\begin{pmatrix}2&3&1&1\\\ 1&2&3&1\\\
1&1&2&3\\\ 3&1&1&2\\\ \end{pmatrix}$

Let $\epsilon$ be a single dynamic fault at byte $0$. We show the effect of
the faults in the last two rounds:

$\displaystyle F_{N-1,\text{ShiftRows}}$
$\displaystyle=S_{N-1,\text{ShiftRows}}+Z+\begin{pmatrix}\epsilon&0&0&0\\\
0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{pmatrix}$ $\displaystyle
F_{N-1,\text{MixCol}}$ $\displaystyle=S_{N-1,\text{MixCol}}+A_{0}\cdot
Z+A_{0}\cdot\begin{pmatrix}\epsilon&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{pmatrix}$ $\displaystyle F_{N-1,\text{AddKey}}$
$\displaystyle=S_{N-1,\text{AddKey}}+A_{0}\cdot
Z+\begin{pmatrix}2\epsilon&0&0&0\\\ \epsilon&0&0&0\\\ \epsilon&0&0&0\\\
3\epsilon&0&0&0\end{pmatrix}$ $\displaystyle F_{N,\text{SubBytes}}$
$\displaystyle=S_{N,\text{SubBytes}}+\begin{pmatrix}\epsilon^{\prime}_{0}&0&0&0\\\
\epsilon^{\prime}_{1}&0&0&0\\\ \epsilon^{\prime}_{2}&0&0&0\\\
\epsilon^{\prime}_{3}&0&0&0\end{pmatrix}$ $\displaystyle
F_{N,\text{ShiftRows}}$
$\displaystyle=S_{N,\text{ShiftRows}}+\begin{pmatrix}\epsilon^{\prime}_{0}&0&0&0\\\
0&0&0&\epsilon^{\prime}_{1}\\\ 0&0&\epsilon^{\prime}_{2}&0\\\
0&\epsilon^{\prime}_{3}&0&0\end{pmatrix}$ $\displaystyle F_{N,\text{AddKey}}$
$\displaystyle=S_{N,\text{AddKey}}+\begin{pmatrix}\epsilon^{\prime}_{0}&0&0&0\\\
0&0&0&\epsilon^{\prime}_{1}\\\ 0&0&\epsilon^{\prime}_{2}&0\\\
0&\epsilon^{\prime}_{3}&0&0\end{pmatrix}$

With $s(x)$ being the AES S-Box, we can find the following equations (on
$x_{0},x_{1},x_{2},x_{3},\epsilon$)

$\left\\{\begin{aligned}
s(x_{0}+2\epsilon+2\zeta_{1}+3\zeta_{5}+\zeta_{9}+\zeta_{13})&=\\\
s(x_{0}+2\zeta_{1}+3\zeta_{5}+\zeta_{9}+\zeta_{13})+\epsilon^{\prime}_{0}&\\\
s(x_{1}+\epsilon+\zeta_{1}+2\zeta_{5}+3\zeta_{9}+\zeta_{13})&=\\\
s(x_{1}+\zeta_{1}+2\zeta_{5}+3\zeta_{9}+\zeta_{13})+\epsilon^{\prime}_{1}&\\\
s(x_{2}+\epsilon+\zeta_{1}+\zeta_{5}+2\zeta_{9}+\zeta_{13})&=\\\
s(x_{2}+\zeta_{1}+\zeta_{5}+2\zeta_{9}+\zeta_{13})+\epsilon^{\prime}_{2}&\\\
s(x_{3}+3\epsilon+3\zeta_{1}+\zeta_{5}+2\zeta_{9}+2\zeta_{13})&=\\\
s(x_{3}+3\zeta_{1}+\zeta_{5}+2\zeta_{9}+2\zeta_{13})+\epsilon^{\prime}_{3}&\\\
\end{aligned}\right.$ (3)

The trick here is that all the $\zeta$ terms are constant and with a change of
variable, we get Dusart’s original equations.

$\left\\{\begin{aligned}
s(x^{\prime}_{0}+2\epsilon)&=s(x^{\prime}_{0})+\epsilon^{\prime}_{0}\\\
s(x^{\prime}_{1}+\epsilon)&=s(x^{\prime}_{1})+\epsilon^{\prime}_{1}\\\
s(x^{\prime}_{2}+\epsilon)&=s(x^{\prime}_{2})+\epsilon^{\prime}_{2}\\\
s(x^{\prime}_{3}+3\epsilon)&=s(x^{\prime}_{3})+\epsilon^{\prime}_{3}\\\
\end{aligned}\right.$ (4)

The upshot is that any implementation of Dusart’s attack as well as Piret’s
improvements (which is what we used) can be applied unmodified888In this
attack, it is no longer true that invalid candidates will yield no solution.
We ran into this issue on a small percentage of key-slots we attacked. on
ciphertexts with static faults. This means we can make use of a greater number
of faulty ciphertexts without having to keep sampling and changing the input
until we hit a lucky 1 byte fault. Since we do not know which faulty
ciphertext has only static faults, we try every possible combination of
$3{M\choose 3}$ groupings with one candidate as the static-only faulty text.
With this one weird trick, we were able to fully recover the remaining non-
master key-slots.

###  IV-C Targeting master key-slots

Up until this point, we focused on non-master key-slots. Recall that master
key-slots have an additional level of obfuscation: the engine does not
directly reveal the ciphertext output. Instead, the engine writes the output
ciphertext to another key-slot (which is not readable) to be used as a new
key. Luckily, this security measure has already been cracked by David “Davee”
Morgan [17] who found a hardware vulnerability in Bigmac. The last ciphertext
is not cleared from the engine’s internal state and the next invocation of the
engine with an input of size $<16$ bytes will “borrow” the remaining bytes
from the ciphertext of the last successful operation. We can extract the
ciphertext output of a master key operation with the following steps:

  1. 1.

Perform a faulty AES-256 decrypt using the master key-slot and any slave key-
slot as the destination. Due to the vulnerability, a copy of the faulty
ciphertext will remain in the AES engine’s internal state.

  2. 2.

Using a known fixed key, AES-128 encrypt a buffer of 4 bytes of 00 to memory.
Save the resulting ciphertext, $C_{3}$.

  3. 3.

With the same fixed key, AES-128 decrypt $C_{3}$, which restores the internal
state.

  4. 4.

Repeat steps 2-3 with 8 bytes and 12 bytes of 00 to produce $C_{2}$ and
$C_{1}$.

  5. 5.

Finally, use the slave key-slot to encrypt 16 bytes of 00 to produce $C_{4}$

We can then do a $2^{32}$ brute-force on $C_{1}$ to find the first 4 bytes of
the faulty ciphertext (since we used a fixed key, and we know that 12 bytes of
the input are 00). Then we can use the 4 known bytes and $C_{2}$ to find the
next 4 bytes and repeat with $C_{3}$ to find the next 4 bytes. Finally we
brute force the “key” used to produce $C_{4}$ with the first 12 bytes we found
and a $2^{32}$ brute-force of the remaining 4 bytes. This gives a worst case
of $4*2^{32}=2^{34}$ AES operations to retrieve a single faulty ciphertext.

Using the c5.18xlarge instance on Amazon Web Services EC2 which provides 72
CPU cores [3], each faulty ciphertext retrieval takes an average of 15 seconds
and the worst case of under a minute. After obtaining the faulty ciphertexts,
we can perform the same DFA attack on the master slots as with other slots.

###  IV-D Results

With the phoenixAES library implementation of Piret’s attack along with our
brute-force enhancements, we able to use our round $N-2$ faults to obtain the
round $N$ key and then use the round $N-3$ faults to obtain the round $N-1$
key.999With the round $N$ key, we can reverse a single round of AES for the
correct ciphertext along with every faulty ciphertext. Then we just run the
same DFA attack with the new sample set to get the round $N-1$ key. Combining
both gives us the full AES-256 key.

We were able to carry out the attack successfully on all $278$ key-slots we
have access to (including all $30$ master key-slots). There are two key-slots,
used for the device unique eMMC full-disk-encryption, that are locked out
before we can gain code execution. In theory, it should be possible to perform
the same attack by writing to the eMMC with our RPC (the FDE is done in
hardware and is transparent to software) and dumping the result with an
external flasher. However, we do not attempt this because of the extra
overhead involved and the fact that the keys are device unique and therefore
not useful to have.

##  V Conclusion

We have demonstrated that AES DFA attacks do work well in practice, although
some extra work was required. It is particularly attractive for devices like
the PlayStation Vita where the software has been security-hardened. The entire
cost of this attack was surprisingly low. ChipWhisperer Lite and CW501
differential probe costs about $300. The custom boards and components for
glitching and triggering costs less than $10 total. 500 core-hours of partials
busting on AWS EC2 costed us about $10. Even including the extra equipment
used during the development and debugging such as a $100\text{\,}\mathrm{MHz}$
oscilloscope and extra Vita motherboards, the entire cost of the attack was
easily under $1000. We believe that all modern SoC should, if they do not
already, defend against DFA attacks because these attacks are not just
theoretical. The PlayStation Vita used hardware AES keys as a way of
protecting the software, but because they did not also protect the hardware as
well, all their defenses crumble with a precisely timed voltage spike.

## Availability

All our work are available as open source projects.

  1. 1.

The F00D RPC payload and ChipWhisperer scripts to run the RPC and collect
faulty ciphertexts: https://github.com/TeamMolecule/f00dsimpleserial/

  2. 2.

AES fault analysis script for finding where the fault occurs given a known
key:
https://github.com/TeamMolecule/f00dsimpleserial/tree/master/scripts/analysis

  3. 3.

DFA attack script based on phoenixAES including the second order DFA
enhancements:
https://github.com/TeamMolecule/f00dsimpleserial/tree/master/scripts/dfa_crack

  4. 4.

Master key-slot ciphertext brute force with AES-NI support (thanks to
“Davee”): https://github.com/TeamMolecule/f00d-partial-buster

## References

  * [1] Sk Subidh Ali, Debdeep Mukhopadhyay and Michael Tunstall  “Differential Fault Analysis of AES: Towards Reaching its Limits”, 2012
  * [2] Subidh Ali, Debdeep Mukhopadhyay and Michael Tunstall  “Differential Fault Analysis of AES using a Single Multiple-Byte Fault”, 2010
  * [3] “Amazon EC2 Instance Types”  URL: https://aws.amazon.com/ec2/instance-types/
  * [4] Ro Barenghi et al.  “Low voltage fault attacks to AES and RSA on general purpose processors.” Cryptology ePrint Archive, Report 2010/130”, 2010
  * [5] Eli Biham and Adi Shamir  “Differential Fault Analysis of Secret Key Cryptosystems”, 1997
  * [6] Dan Boneh, Richard A. Demillo and Richard J. Lipton  “On the Importance of Checking Cryptographic Protocols for Faults”  Springer-Verlag, 1997, pp. 37–51
  * [7] Joppe W. Bos, Charles Hubain, Wil Michiels and Philippe Teuwen  “Differential Computation Analysis: Hiding your White-Box Designs is Not Enough” https://eprint.iacr.org/2015/753, Cryptology ePrint Archive, Report 2015/753, 2015
  * [8] Jakub Breier and Dirmanto Jap  “A Survey of the State-of-the-Art Fault Attacks”, 2014
  * [9] Joan Daemen and Vincent Rijmen  “AES Proposal: Rijndael”, 1999
  * [10] P. Dusart, G. Letourneux and O. Vivolo  “Differential Fault Analysis on A.E.S.”, 2002
  * [11] N. Floissac and Y. L’Hyver  “From AES-128 to AES-192 and AES-256, How to Adapt Differential Fault Analysis Attacks on Key Expansion”  In _2011 Workshop on Fault Diagnosis and Tolerance in Cryptography_ , 2011, pp. 43–53  DOI: 10.1109/FDTC.2011.15
  * [12] Chong Hee Kim  “Differential fault analysis of AES: Toward reducing number of faults”  In _Information Sciences_ , 2012, pp. 43–57
  * [13] Matt Kim  “PS Vita Production in Japan Will End in 2019, No Successor Planned”  URL: https://www.usgamer.net/articles/ps-vita-will-cease-production-in-japan-in-2019-no-successor-planned
  * [14] Yifan Lu  “Injecting Software Vulnerabilities with Voltage Glitching”, 2019
  * [15] Yifan Lu  “Why hacking the Vita is hard (or: a history of first hacks)”  URL: https://yifan.lu/2013/09/10/why-hacking-the-vita-is-hard-or-a-history-of-first-hacks/
  * [16] Amir Moradi, Mohammad T. Shalmani and Mahmoud Salmasizadeh  “A Generalized Method of Differential Fault Attack against AES cryptosystem”  In _IN CHES_ , 2006, pp. 91–100
  * [17] David Morgan  “Extracting keys from F00D Crumbs”  URL: https://www.lolhax.org/2019/01/02/extracting-keys-f00d-crumbs-raccoon-exploit/
  * [18] C. Nalini, P.. Anandmohan, D.. Poomaiah and V.. kulkarni  “Compact Designs of SubBytes and MixColumn for AES”  In _2009 IEEE International Advance Computing Conference_ , 2009, pp. 1241–1247  DOI: 10.1109/IADCC.2009.4809193
  * [19] Colin O’Flynn  “Fault Injection using Crowbars on Embedded Systems.”  In _IACR Cryptology ePrint Archive_ 2016, 2016, pp. 810
  * [20] Gilles Piret and Jean-jacques Quisquater  “A Differential Fault Attack Technique Against SPN Structures, with Application to the AES”  In _and KHAZAD,”Fifth International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2003), Volume 2779 of Lecture Notes in Computer Science_ Springer-Verlag, 2003, pp. 77–88
  * [21] N. Selmane, S. Guilley and J. Danger  “Practical Setup Time Violation Attacks on AES”  In _2008 Seventh European Dependable Computing Conference_ , 2008, pp. 91–96  DOI: 10.1109/EDCC-7.2008.11
  * [22] Philippe Teuwen  “phoenixAES: a tool to perform differential fault analysis attacks (DFA) against AES”, 2016  URL: https://github.com/SideChannelMarvels/JeanGrey/tree/master/phoenixAES
  * [23] Michael Tunstall, Debdeep Mukhopadhyay and Subidh Ali  “Differential Fault Analysis of the Advanced Encryption Standard Using a Single Fault”  In _Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 224–233
  * [24] Marc Witteman  “Practical DFA on AES”, 2013  URL: https://www.riscure.com/uploads/2017/09/Practical-DFA-on-AES.pdf
  * [25] L. Zussa, J. Dutertre, J. Clédière and A. Tria  “Power supply glitch induced faults on FPGA: An in-depth analysis of the injection mechanism”  In _2013 IEEE 19th International On-Line Testing Symposium (IOLTS)_ , 2013, pp. 110–115  DOI: 10.1109/IOLTS.2013.6604060

##  Appendix A Appendix

###  A-A PCB Modifications

Figure 4: The decoupling capacitors for the core 1.1V voltage domain removed
are boxed in red. The two external clock input pads are boxed in yellow (the
clock synthesizer chip is removed). Figure 5: The back of the board where the
1.1V supply trace is cut in order to isolate the regulator from the SoC.
Figure 6: The psvcw board glued to the under-side of the Vita motherboard. SMA
connector goes to ChipWhisperer glitch module. The left pins go to an external
1.1V supply. The right pins go the differential probe. On the bottom of the
board are two wires that are soldered to ground and the top portion of the cut
trace. The shunt resistor is $10\text{\,}\mathrm{\SIUnitSymbolOhm}$ and the
bypass capacitor is $10\text{\,}\mathrm{\SIUnitSymbolMicro F}$. Boxed in
orange is the GPIO output from the device used as a trigger.