Linear Algebra - Authentication Challenge

> Linear Algebra

1 - Challenge

Password is an n-vector


over GF(2)

  • Send: Computer sends random n-vector a
  • Response: Human sends back <math>a · \hat{x}</math>


Repeated until Computer is convinced that Human knowns password



Eve eavesdrops on communication, learns m pairs:

<MATH> \begin{array}{c} a_1,b_1 \\ \vdots \\ a_m,b_m \end{array} </MATH>

such that


is the right response to challenge



<math>a · \hat{x}</math>


Then Eve can calculate right response to any challenge in

<math>Span \{a1, \dots , a_m\}</math>


<math>a = \alpha_1 a_1 + \dots + \alpha_m a_m</math>

Then right response is

<math>\beta_1 . b_1 + \dots + \beta_m . b_m</math>

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

Once m > n, probably

<math>Span \{a_1, \dots , a_m\}</math>

is all of



So Eve can respond to any challenge

Also: The password


is a solution to:

<MATH> \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} </MATH>

Solution set of Ax = b is

<math>\hat{x}+ \textrm{Null A}</math>

Once rank A reaches n, columns of A are linearly independent so Null A is trivial, so the only solution is the password


, 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.


3 - Documentation / Reference

linear_algebra/authentication.txt · Last modified: 2013/09/20 10:46 by gerardnico