# Secure Sketch Construction

I would like a user to choose a point on an image which is represented by (x,y). This is meant to be a security token. When a user uses this location to login they are unlikely to to choose the exact same (x,y), rather they will choose a point nearby (x_g, y_g). The user may also be required to enter a password.

ATM I'm thinking of using a simple modulus function that will round (x,y) => (x mod 16, y mod 16). Other ideas include:

• multiplying x,y prior to applying the modulus function, (x,y) => x*y mod 16
• adding a salt to x and y prior to applying the modulus function, (x,y) => (x+salt mod 16, y+salt mod 16)
• adding the numerical representation of a hashed password to x and y. (x,y) => (x+pwordHash mod 16, y+pwordHash mod 16)

I'm also considering how this maybe extended to more than one point.

Problem

I wish to know if any of the above ideas are suitable or if there exists better better solutions for calculating a secure sketch. It is assumed that an attacker will have access to the salt and the secure sketch. The system will not store any record(i.e hash) of the actual point. The user will need to verify that the system has found the correct point.

-
Interesting description, but what is the actual question? –  owlstead Jul 21 '13 at 20:54
@owlstead Hopefully the edits help. –  Kurent Jul 22 '13 at 10:31

One standard solution is described in the following research paper:

That paper shows how to deal with the problem that the user's second point might be close to, but not exactly the same as, their original point. In other words.... exactly your problem.

There might be more recent work on this problem. You could do a literature search, starting from the above paper (e.g., looking at other papers that cite it) to see whether there are other better solutions.

-
Thanks, very helpful. –  Kurent Jul 22 '13 at 9:47

We select an even "precision" value (how far away from the point we will allow)

Given a password (X, Y) we calculate

Password = X div precision + (width div precision) * (Y div precision)

Given a password attempt (x, y), calculate the following values:

x'0 = (MAX(0, x - precision / 2)) div precision
x'1 = (MIN(width - 1, x + precision / 2)) div precision
y'0 = (MAX(0, y - precision / 2)) div precision
y'1 = (MIN(height - 1, y + precision / 2)) div precision

You can then form the pairs: (x'0, y'0), (x'1, y'0), (x'0, y'1), (x'1, y'1)

For each of these values you then calculate s = x' + (width div precision) * y'

You then get the values s00, s01, s10, s11.

Compare all of these values against the password, and if any of them match, you have a successful login.

You can also invert this thinking by storing 4 passwords.

-
So... You would only check the minimum and maximum values? And you start off from coordinate x and y instead of using it as the center of a circle? –  owlstead Jul 21 '13 at 20:53
@owlstead I updated my answer somewhat. But basically I want to take the grid width x height and reduce it to width / precision x height / precision. If we imagine each selection being precision x precision large, then they will reduce to 4 points on the reduced grid. Alternatively you don't reduce the grid and simply check against all precision x precision points. You can use a circle too of course, that would be more exact, although less efficient to calculate - and more useful when you don't reduce the grid. –  Nuoji Jul 22 '13 at 9:35
@owlstead the reason why I suggest this, is because we can scramble the password using a hash and the algorithm would still work as long as we then scramble s00, s01, s10 and s11 in the same manner. –  Nuoji Jul 22 '13 at 9:38
I understand where you are going, I was just questioning the method of reducing the location to a one of several points on the image. Glad you fixed it. –  owlstead Jul 22 '13 at 14:25