Linear Algebra - Authentication Challenge

1 - Challenge

Password is an n-vector $\hat{x}$ over GF(2)

• Send: Computer sends random n-vector a
• Response: Human sends back $a · \hat{x}$.

Repeated until Computer is convinced that Human knowns password $\hat{x}$.

Eve eavesdrops on communication, learns m pairs: $$\begin{array}{c} a_1,b_1 \\ \vdots \\ a_m,b_m \end{array}$$ such that $b_i$ is the right response to challenge $a_i$ (ie $a · \hat{x}$).

Then Eve can calculate right response to any challenge in $Span \{a1, \dots , a_m\}$

Suppose $a = \alpha_1 a_1 + \dots + \alpha_m a_m$ Then right response is $\beta_1 . b_1 + \dots + \beta_m . b_m$

Fact: Probably rank [a1, . . . , am] is not much less than m.

Once m > n, probably $Span \{a_1, \dots , a_m\}$ is all of $GF(2)^n$.

So Eve can respond to any challenge

Also: The password $\hat{x}$ is a solution to: $$\underbrace{ \begin{bmatrix} \begin{array}{r} a_1 \\ \hline\\ \vdots\\ \hline a_2 \end{array} \end{bmatrix} }_{A} \begin{bmatrix} x \end{bmatrix} = \underbrace{ \begin{bmatrix} \begin{array}{r} b_1 \\ \hline\\ \vdots\\ \hline b_m \end{array} \end{bmatrix} }_{b}$$

Solution set of Ax = b is $\hat{x}+ \textrm{Null A}$ Once rank A reaches n, columns of A are linearly independent so Null A is trivial, so the only solution is the password $\hat{x}$, so we can compute the password using solver.

2 - How to improve the scheme ?

The way to make the scheme more secure is to introduce mistakes.

• In about 1/6 of the rounds, randomly, Human sends the wrong dot-product.
• Computer is convinced if Human gets the right answers 75% of the time.

Gaussian elimination (of any other method) does not find the solution when some of the right-hand side values are wrong.