How to estimate the number of entropy bits & search space of a signature system like passtouch?

Question

Apologies if I'm using the wrong lexicon, I'm just reading up about password systems out of interest.

After seeing the xkcd strip on passphrases and coming across the passtouch system (youtube demo) that uses an abstract signature to login to sites, I just wondered how the company, or anyone might estimate or predict the randomness of the signatures people would use?

Off the top of my head it seemed like something that could have a huge amount of theoretical possibilities (search space?), but due to human psychology actually have a lot of people drawing remarkably limited signatures and so few entropy bits (?).

So how might one go about estimating this (using psychological theory or prior studies or maths or whatever)?

EDIT ********

Ok I realise that without knowing the exact system that passtouch implements we can't know how large the search space is to any accuracy. But theoretically maybe we can give a guess as to what ballpark number of possibilities a similar signature based system could generate?

So imagining that the screen is divided into a 20 x 20 grid, each square is assigned a unique id and as you touch a certain square, that id is added to your "personal passkey".

• From any starting square your next move can go up, down, left or right as long as your not on the side or in a corner.
• When you move diagonally, I'm assuming you actually touch another square first, so move in an L shape.
• You can't immediately backtrack to the same square you just came from, but you can go back later.

From a quick test on my notepad, I estimated a signature to cover approx 40 squares (edit: at least 40 squares as I was originally allowing diagonal moves as well).

So how can we work out the number of unique 40 square long "signatures" on a 20x20 grid?

I did some very rough calculations and got something like 2^113 possibilities (edit: that was allowing diagonal moves) but couldn't work out how to deal with the size limitations of the grid. Still I'm guessing such a system could easily give more than 2^100 possibilities...

Anyone got a better estimate?

Answer 1

Your very rough calculations seem to be a gross overestimate, as the line has to be continuous. For simplicity let's first neglect curved lines.

Then since it is one continuous line, let's imagine it as a 10x10 continuous grid (my finger widths on an ipad; I doubt it will be more sensitive in rejecting passwords until its more than a half-fingers width of error) over the section covered by the passtouch logo. A possible password is then a series of points (starting point and each point where it changes direction). So that all matters is starting location and then travelling to a few points. For example, dropping the circle at the end of the demo video the demo password there were 5 points. If the points were randomly chosen (probably a bad assumption as humans are poor random number generators), you'd have ~2^33 possibilities.

Now there's the question of how much entropy does making a curve add? You could approximate as each new direction of a curve (change in concavity) is equal to an additional new point (the point the curve must go through to go from the start point to the end point) as if you only had a straightline. So the demo password with the curve at the end counts as 7 points with ~2^46. This is roughly equal to a password with 8 upper/lower case letters chosen at random. I personally wouldn't trust encrypting other passwords (I hope it encrypts) by protecting with a key that's this weak. There's further weakness in that people will probably not randomly choose circle widths; but instead choose width to circle/weave around circles already in the figure.