Pico part IV – Somethings you have

A light-hearted look at the ideas presented a couple of weeks ago in a paper at the UPSIDE workshop in Seattle.

USS Enterprise going even more boldly than usual

One of the problems inherent in boldly going where no man has gone before is that, more often than you might imagine, you may be required to blow up the spaceship on which you’re travelling. James T Kirk was forced to do this at least once, and he and his successors came perilously close to it on several other occasions.

But who gets to make this decision? Given the likelihood that some members of the crew may be possessed by alien life-forms at the time, it seems unwise to leave such decisions to any single individual, even if he’s the captain. And you also can’t require any specific other staff-member to back him up, since they may have had to sacrifice themselves earlier for the good of the many. Auto-destruct sequences, therefore, can typically only be initiated when any three senior officers agree and give their secret passwords.

It is a wonderful sign of the times that, when the first Star Trek episode in which this happens was broadcast in 1969, the passwords required to detonate a spaceship with 400 passengers on board were noticeably weaker than those now required to log in to a typical Kickstarter project.

Secret sharing – background

Some of the most beautiful examples, I believe, of using a simple, readily-understandable idea to solve a complex problem can be found in the secret-sharing systems proposed almost simultaneously by Adi Shamir and George Blakley, way back in 1979. These are just the sort of thing you need to need to control self-destruct sequences, and are certainly better than the four-character passwords used by Kirk and Scotty.

Most readers of LBT will be familiar with this, but in case you aren’t, the underlying concept is to encode the secret you need to protect – for example, the auto-destruct code – as the coefficients of a particular quadratic equation. If you know any three points on the curve, you can deduce the underlying equation. So all you have to do is give each of Kirk, Scotty, Spock and Bones the coordinates of a point, and any three of these ’shares’ can then unlock the secret which will trigger the detonation. If you want to insist on four or more officers, you use a higher-order polynomial. This is Shamir’s algorithm; Blakley’s is similar, but whichever you use, there is, I think, a real elegance in solving a difficult technical problem using a concept that can be explained in a paragraph to anyone with high-school level maths.

A somewhat more down-to-earth example of its use can be found in the DNSSEC system used to secure the core servers of the DNS, on which so much of the internet depends. The master key needed to reset this, in the event of some global calamity, is divided up between seven keyholders based in different countries. One of them told me over a beer recently that it required any five of them to get together in the US to be able to reconstruct the system.

PICO

In the Pico project (see earlier posts), we’re exploring the same secret-sharing concepts but at a personal rather than a global or galactic level.

The idea is that your Pico device, which provides authentication on your behalf to a wide variety of systems, should only be able to do so when it is confident that you are present. There are several ways it might detect that – biometrics perhaps being the most obvious – but we wanted a system that would be completely automatic, continuous and non-intrusive: it wouldn’t require you to re-scan your retina every few minutes, for example.

So the Pico assumes that you are present only if it can detect, nearby, a sufficient number of other devices that you normally carry. These ‘Picosiblings’ may be special devices dedicated to this purpose – bluetooth-enabled cufflinks or earrings, for example – or the Picosibling functionality may be built into phones, smart watches, laptops and car key-fobs. But, together, a sufficient number of them constitute an ‘aura’ of safety in which the Pico feels comfortable about releasing your credentials when you use it to log in.

You could just program the Pico to make this decision, but a more secure approach is to use secret-sharing. Your Pico stores your credentials in encrypted form, and the Picosiblings actually enable it by each giving up a share of the secret used to do the encryption. Since this information is not cached, even the Pico cannot decide to expose the information when you are not around.

Some challenges

This basic Picosibling concept is not bad, but can we improve it? How well can we model real-world user behaviour using these ideas? Where might they fall down, and do we need to invent anything new to deal with the edge cases? And can it help us make better decisions about when to blow up a starship?

Let’s consider some scenarios.

1. My Precious

My car keys are with me about 30% of the time, and may occasionally be with someone else. My wedding ring, on the other hand, has been a 100% reliable indicator of my presence for the last 23 years. (It’s too bad my wife didn’t give me a Bluetooth-enabled one.) We all have different possessions which may be more or less reliable indicators that we are around, and we can represent this by giving them different numbers of shares. Most of my Picosiblings might have one share, but my wallet and phone might have two, and my wedding ring four. If my ring is absent, you’ll need significantly more confirmation from other sources, in the same way that you might need disproportionately more senior officers if the captain is absent.

2. Smarter Picosiblings

Is my watch a good indicator of my presence? Well, yes, when it’s with me, but not when it’s sitting on my bedside table. There may be occasions when Picosiblings are more or less confident that you are present. So we can give each sibling a certain number of shares, but it may not choose to release them to the Pico in all situations. A sibling that detects and recognises your heartbeat might give out differing numbers of its shares based on how confident it is about its recognition. Something you normally wear or carry might include an accelerometer, and give out fewer shares if it hasn’t moved in the last few minutes. The number of shares might decay over time, as the device gets further from the moment at which it was confident of your presence, so a fingerprint sensor might be sufficient to unlock your Pico on its own, if you’ve used it in the last ten seconds. Another metric might be proximity: if the Picosibling could detect the Pico was close by, it might be willing to hand over more shares than if it were on the other side of the room.

3. The trouble with Klingons

But suppose we need something more sophisticated than simply the raw number of shares to unlock the secret? If your starship has a large number of Klingon officers, who place a high value on dying honourably in battle, you might wish to insist that at least two races were involved in any major decision like this.

Fortunately we don’t need a new mechanism: we can just use our current system twice over. We split the core secret into several shares: one for humans, one for Vulcans, one for Klingons, one for Betazoids. Each of those shares can then be subdivided in the same way for the individuals concerned. Two or more Vulcans are needed to reconstruct the Vulcan share, and two or more such species actually to blow up the ship.

In the Pico world, suppose your shoes are all Picosiblings. If you have many pairs of shoes, someone entering your bedroom may find they have plenty of shares even if you aren’t around. We can use this method of creating ‘categories of shares’ to limit the effect that a particular class of device can have, to ensure that shoes alone can never be sufficient to do the unlocking.

4. Greater than the sum of its parts

Suppose my my car, my car keys, and my house keys are all Picosiblings, and they each have one share. Anyone inside my car is likely to have my car keys, including a thief who has just found them on the pavement. But we could reasonably argue that someone who is inside my car and has my house keys is more likely to be me; that a stranger is less likely to have this particular combination of Picosiblings, and so their conjunction should be worth more than might be indicated by a simple addition of their values.

We can achieve this in various ways; a simple approach is just to cut a share in half and give one half to each sibling. These would be sent to the Pico along with the complete shares, and if it receives matching halves from two devices, it would be able to construct extra shares which correspond to the value of their relationship.

5. You can’t take that away from me

Here’s a challenge for readers. Can you think of a good way to implement negative shares? Let me explain…

Suppose you are in an airport check-in queue and a significant number of your worldly possessions are in the suitcase beside you. Someone who pinches your Pico from your pocket will have plenty of shares accessible either by standing behind you, or by getting close to your suitcase at some later point in the baggage-handling process. Travelling is one of those situations when you might feel a bit vulnerable and so require more confirmation of your presence than you would in your home country. If your suitcase could emit negative shares, then it would raise the threshold of affirmation needed by your Pico when it was around.

There are many challenges here, both technical and practical: for example, anyone who knows that there is a negative influence nearby may be able to remove it, e.g. by tipping the items out of the suitcase. But it would at least deter subtle unobserved attacks in the check-in queue. It would be good if observers, and ideally the Pico itself, could not distinguish positive from negative shares except with regards to their final effect. And so on. As I said: a challenge for the reader!

Sharing options

So we’ve introduced several ideas which can help with some real-life scenarios, yet they’re all based on the same simple secret-sharing concept:

  • Variable numbers of shares per device (based on how reliable each device is as an indicator)
  • Dynamically-changing number of shares (allowing devices to indicate their confidence in your or the Pico’s presence)
  • Categories of shares (allowing us to restrict the influence of a single class of devices)
  • Split shares (allowing combinations of devices to contribute more than simply the sum of their shares)
  • Negative shares (to allow some devices to indicate situations of vulnerability)

Extending the tree

Let me finish with one last question. To what extent are Picos and Picosiblings fundamentally different? Picos gain confidence to submit your credentials to a service based on the reassurance they get from Picosiblings. But we’ve also discussed the idea of Picosiblings getting confidence to submit their shares to a Pico based on other factors in the environment. Perhaps we could extend this hierarchy in the other direction, too.

A company might need k-of-n shares from the major investors’ Picos to appoint their representative director to the board. The company Pico might then need k-of-n of the directors’ Picos to authorise a major decision or transaction. And a commercial building might need k-of-n of the companies’ boards to agree to the resurfacing of the parking lot. This could be extended to political, national, even global decisions.

Perhaps I’m pushing the simple secret-sharing concept too far. But at the very least it’s an interesting thought experiment to consider how much we can represent real-world situations with this one idea.

After all, we need a simple, reliable and secure way to make these decisions in our own back yard, before we start interacting with the rest of the universe.

14 thoughts on “Pico part IV – Somethings you have

  1. Isn’t that just complicating the issue? What is the difference between faking one or many devices? If all the links in the chain are weak ones then the chain isn’t.
    Hardly anyone wears cufflinks anymore. The one device people will most likely carry, is the mobile. They can even be ‘encouraged’ by making them useful. You need to be thinking about using the things people don’t carry.

  2. Hi Tim –

    I’m not quite sure I follow all of your points, but I agree – if that’s what you’re saying – that it’s unreasonable to expect people to carry a large number of extra devices just for the purpose of enabling their Pico.

    My expectation is that Picosiblings – or the Picosibling functionality – would generally be attached to, on incorporated in, things I already carry, rather than being distinct devices in their own right. For example, I already have a bluetooth-enabled watch, tiny bluetooth beacons in my wallet and on my keyring, and my phone, laptop, car keyfob and iPad all have radio capabilities of various sorts. I think a successful Picosibling model will depend on a minimally-intrusive detection of the things you already carry, rather than requiring you to carry many more.

  3. Hi, Quentin. I accept that I need to do more reading up on this, but, just as an overview, could you say what you are thinking of securing with Pico? I may be misunderstanding based on short acquaintance with the project, but it seems that you are envisioning securing devices with Pico/Picosiblings – e.g. phone, tablet, desktop. However, if that is the case, you end up with a circular process in which e.g. the tablet verifies the phone and the phone verifies the tablet, which seems wrong.

    In addition, I’m not sure what the fallback is if I need to use e.g. my mobile when separated from other Pico devices (e.g. working on the car where I’m not likely to have watch, wallet etc with me, or in bed at night). Unless my glasses, for example, can become a Picosibling, there are several instances I can think of where I would be unlikely to have any verification within (what I anticipate to be) the short range of the transponders.

    1. Thanks Jeremy –

      The eventual aim is that the Pico will be a separate device which you will use to authenticate sessions on your computers, tablets etc, but we hope might also start your car, open your front door, allow you to withdraw cash from an ATM. (If you haven’t seen it, the video at http://mypico.org might make some things clearer.)

      You raise a good point, though: if a device such as a tablet is also acting as a picosibling, we should perhaps ensure that its shares are not taken into account when logging into something displayed *on* that tablet.

      The expectation is that you’ll typically need a few other things as well – perhaps the shares from 3 or 4 Picosiblings, as well, of course, as the Pico – but we need to be careful if the share numbers required get low especially if the things that work as terminals also work as Picos or Picosiblings.

      As for the fallback question, yes, it may be that traditional passwords, PINs etc would need to remain for situations where you really can’t use Pico methods, but they all have limitations too – you may not want to use a PIN on your smartphone if your hands are deep in a greasy engine either! And if you are, say, in a swimming pool, it’s probably going to be pretty rare that you need to be authenticating yourself securely. But our aim is to design things so that situations when the Pico model doesn’t work will at least be rare.

      In general, I think, most authentication/authorisation in the rest of life is done through things you have with you – keys, wallets, employee badges, cash, tickets – so a Pico-enabled world isn’t the only place where a lack of possessions would be an inconvenience?

      Quentin

  4. An interesting thought experiment, and an interesting subdivision into categories with good analogies.

    The one thing I was left to wonder about appr. halfway through: How do you explain that to the user and expect him to set the parameters? If setting all the share and trust and categorie parameters for my new watch, key fob or tie bar becomes too cumbersome, wouldn´t I just set it to “If watch and car keys are present, go ahead”?

    (Assuming a personal environment where I buy and set up my own picosiblings, not a corporate one where picosiblings are handed out and managed centrally.)

    1. Hi Cristoph –

      Yes, you’re quite right: the real challenge here is how much the average user could, or would want to, cope with. I suspect only a small subset of the ideas here will make it into the real-life Pico deployment, but I wanted to push the ideas as far as I could in case they were useful in other scenarios!

      For Pico, we’re doing extensive user studies around each assumption that we (the techies) make, to check that we’re not too far out of calibration with the real world!

      Q

  5. Thanks, Quentin. I’m glad I made at least one good point in there re: circular verification!

    I do like the Picosibling idea, though it depends on how they will be implemented. I, personally, would prefer to buy sibling-tags, which I could attach to existing things that I have already – you mentioned wedding rings, I mentioned glasses, but my watch and penknife would also be really good indicators that I am me for the purposes of my gadgets. Others might have necklaces etc that would essentially signify that level of identification with little more needed. Certainly, they would fit the use-case when I am in the garden or garage, or in the middle of a wet forest where I don’t want to take my gloves off!What I really don’t want is to have to buy new Pico-enabled glasses, rings, watches, penknives etc. It seems to me that success of the project depends on people deciding for themselves what makes them different from others. I have just found out that RFIDs (since that is how I perceive the Pico hardware) can have ranges in terms of metres, which surprised me, so perhaps this wouldn’t be a problem as long as they are small and flexible enough to conform to simple curves, for instance?

    However, there then becomes the programming side – how do you envision the siblings being given the identification criteria and priority? If it is user-defined, then it becomes complex, and takeup will be slow; if it isn’t then it is complex and takeup will be slow 🙂

    1. Jeremy –

      Yes, I agree about tagging existing possessions being, in general, more attractive than purchasing new ones. We’ve been experimenting with bluetooth beacons like the Stick’n’Find. I’ve been carrying one in my wallet for a year or so without noticing it, and they’re also easy to attach to keyrings.

      We’ve also got some NFC tags, which have some very attractive characteristics. My understanding, though, is that the range of these and any passive RFID-type tokens, is highly dependent on the size of the antenna, which may make them impractical for Picosibling use. Active ones may be more possible.

      All of this, and the whole process of how we would distribute and manage the shares and credentials, is currently being researched.

      Q

  6. Hi Jeremy,

    the Pico idea is fascinating, but one question troubles me:
    How do you ensure (preferably by design of the pico system)
    that all these rfid-devices are _not_ used for surveillance?
    Thanks!

    1. Thanks Jeremy – I’m very much a part-timer on the Pico project, so I don’t get round to responding to things as quickly as I might otherwise!

      But yes, Frank’s comment addresses this. It’s a challenge for any radio network that has addressable endpoints: how to stop those addresses from being usable by anyone else. There is work on this being done by others, and we’re keeping an eye on it. But we should probably add a section about this to the project FAQ fairly soon!

      All the best,
      Quentin

Leave a Reply

Your email address will not be published.