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

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?

-
Have you found material on what the Passtouch fingerprint is? I couldn't find anything on their minimalist website. They say there are a lot of possibilities, but it's completely dependent on how the fingerprints are calculated. – Gilles Mar 21 '12 at 22:56
Unfortunately not. It's a pretty new startup and I guess they don't want to reveal all yet. – Curiouzo Mar 21 '12 at 23:57
It also depends on how strict they are, vs. how different a fingerprint can be and still be accepted. (e.g. do they only count the circles you touch in order, or also which area / pixels you put your finger through? how many angle points do they take? Is speed taken into account? etc.) Without knowing this, it is impossible to tell. And what about sidechannels? does it leave a tell-tale smudge? etc. – AviD Mar 22 '12 at 13:19
Does look like very cool tech, though. Just don't know what kind of security it gives. – AviD Mar 22 '12 at 13:19
You're both quite right, that without the details we can't tell for passtouch, but how about for a generic implementation of a signature based system, how would you do it? – Curiouzo Mar 22 '12 at 18:05

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.

-
Hey thanks for the answer, your method makes much more sense. I don't quite see how you get 2^23 possibilities with a 5 point line though. If you can't double back over yourself, wouldn't it be 100 * 99 * 99 * 99 * 99 = 9.6 billion or 2^33.1 ? Excuse any horrendous mathematical misunderstandings, I'm really completely new to this. – Curiouzo Mar 23 '12 at 0:40
Mistakes on my part (sloppy math; bad editing). Fixed numbers. – dr jimbob Mar 23 '12 at 4:31
So with a bit more resolution (bigger grid, say 15*15) and a longer signature/more complex pattern matching (more points on a line, say 10) we are starting to get a decent search space, 2^78 no? What if we then added some basic speed testing as well? How might we test for additional entropy/search space there? – Curiouzo Mar 23 '12 at 19:32