# 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 'SO- stop being evil' 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