Ursula Menke n'en déconseille pas l'usage. "Nous suggérons des précautions, indique-t-elle. C'est une question de bien peser les risques et les bénéfices de ce genre de service."
Some friends and I are kicking off the holiday season early this year! Along with Jason Kealey and Etienne Tremblay of LavaBlast Software, as well as their better halves, I've arranged to rent a rather nice cottage in mid-December. We decided to hold a Secret Santa gift exchange over there, which brings us to this post.
How do you arrange a randomly-assigned Secret Santa event when the participants are geographically distributed?
Assignment of giver/recipient pairs is usually handled by drawing strips of paper from a hat, an approach that obviously won't work here, when planning over email. So I started to think about how one could do this without relying on a trusted third-party. Is it possible for a group of peers, communicating only through email, to each choose a random recipient and guarantee uniqueness of picks, while ensuring picks are not revealed to others, and no one ends up picking themselves? [My father, over dinner the other day, helpfully pointed out that this is known as a derangement problem.]
We ended up going with the very pragmatic approach of relying on a trusted third-party (in this case a simple computer program). I wrote a Java program that took the list (L) of 5 email addresses, shuffled it (using Collections.shuffle()), then sent an email to address L[i] containing address L[(i+1) % 5], all without printing to the screen what it was doing, or logging anything. Once the program exited, there was no way for anyone to recover who got what address, and it guarantees that the final assignment is a derangement: no person in the initial list gets themselves.
Now, this is all well and good, but it's a boring solution because of its reliance on software. Is this doable with only five people talking over email? (Yes, it's a mostly academic exercise.) I've had some ideas that go in the right direction, but haven't solved the problem of ensuring the final mapping is a derangement, other than running the process for multiple rounds, until no one declares they received themselves as an assignment.
The first primitive our protocol needs is a method of mapping an abstract identifier (say, a number) to an actual name. This is because since participants need to pick one of the 5 identifiers unsupervised, they must not know in advance which person this identifier will represent.
This is the easy part: have everyone pick a unique value i from the pool of identifiers [0-4] (randomly or not) and remember it without disclosing it. Your assigned name is then L[(i+d) % 5], where d is the integer part of the TSX composite index at market close the following day. The offset value d is the same for everyone, is not known in advance, and when we all exchange gifts we can audit that no one cheated and changed their chosen ID after knowing d.
The above relies on everyone having independently picked a unique value for i, and this is where things get interesting.
If a means of anonymously broadcasting a message to the whole list is available, we can rapidly constrain picks to the 120 cases where there are no duplicates. We'll then have a 36.7% chance [44/120] of having a derangement in each round, so we should be able to settle on a solution in very few rounds.
OK, so you don't have an anonymous remailer. No problem!
I've devised a method to ensure the picks are independent, but it can take many rounds to work, as the expected success rate is only 120/3125. (And after that you still have the problem of restarting if you don't have a derangement.)
I think the following should work, but YMMV, I haven't proven it:
We publish the list of 5 participants. Their order is unimportant.
We publish 5 IDs. Let's use 5 prime numbers {3, 5, 7, 11, 13}. I don't think they need to be prime, but they must be picked to ensure that their product, known by all (in this case, P=15015) can only be achieved if you pick EXACTLY one of each number, and this is easy to ensure if you take primes [I think].
Everyone independently picks an ID i from the list, keeping it secret.
I'm first on the list. I choose a random large integer s. I compute P' = i * s * P.
I hand off this product (P') to the second person on the list. The number she receives from me is evenly divisible by 3, 5, 7, 11, 13 and P, so she has no way of knowing what my chosen i is, or what value of s I picked (there are 5 equiprobable possible values for s, which tells her nothing).
She multiplies P' by her own chosen i, and gives that to the third person on the list, and so on.
The list wraps around and I'm sent a value from the 5th person on the list. If everyone picked a unique value for i, I get s * i0 * i1 * i2 * i3 * i4 * P or, succinctly, s * P2. If I get anything else, then I know there's a duplicate.
I announce whether or not there was a duplicate. (I, or anyone else, can always lie, but then when gifts are exchanged we'd know someone lied - in the spirit of the holidays, the participants in this protocol are honest.)
Phew. Each round has a 1.408% chance of working, so it could take a while. I have yet to find a much better approach, so I think our little 30-line Java program was appropriate in this situation.
I dropped off my car at the Honda dealership this morning to have them investigate the mysterious Check Engine light that came on yesterday. This post was inspired by what happened tonight when I swung by after work to pick up the car - I'm not chastising them for the security flaw, I mostly just find it charming and cute.
I was there about two minutes, and this is the conversation as I remember it, see if you can spot the tiny flaw:
[I enter the service area of the dealership and walk over to the clerk, then sit down in front of him. A car key is lying on the desk, sporting a little tag with my last name scrawled on it in big block letters: DAIGLE.]
- Clerk: Hi!
- JP: Hi, picking up my car...
- Name?
- Daigle
- Oh yeah, just closing that file now, here's your key.
- So what was wrong with it?
- Coolant temperature sensor failed.
- Huh.
- Yeah, it was under warranty, so you're good to go!
- Thanks, good night!
[I exit the dealership, key in hand, and drive off.]
Human beings are usually the weakest link in any security system :)
Yes, I think it is. Long-winded explanation follows.
Me: I'm a guy who loves to work on a laptop. I've owned my little Thinkpad since 2004. I have dragged it between Ottawa and Montreal dozens of times, hauled it through Spain and the United States while vacationing, it's been through several coffee shops in Ottawa, and even tonight, with three other computers in my apartment much faster than this one, I'm in the living room, writing this post on the faithful machine. If you call me up and need help with a build script or a complicated subversion operation, I'll run over to your cube with it and we can hack on the problem together, each on our own screen. Or anyway, I would if there were wireless network access points at the office.
Which there aren't.
(Yes, I'm well aware of the irony of working for a company that makes network equipment. No need to point it out.)
The subject came up on Friday evening, as a bunch of us engineers were sitting around having a beer before leaving for the weekend. Someone (I swear it wasn't me this time) wondered out loud why in this day and age, we didn't have wireless APs at the office. Asked our CTO: "Why don't we just drive to Futureshop and spend the fifty bucks?"
I suppose it's always been a "nice to have" feature of the office, never a true requirement, and commercial-grade WAPs are more expensive than the consumer versions from Linksys. I've also heard mentions that there might be concerns about the security of the setup, given that we lease a floor on a building housing a bunch of other companies. I realized after the discussion, however, that the security argument was bunk, and having no WLAN could actually put us at much greater risk than having one.
It is an oft-repeated saying in security discussions that humans are often the weakest part of a security system. In his book Secrets and Lies, security guru Bruce Schneier again reminds us, as he has before, that an inconvenient security system is self-defeating because humans will simply end up not using it. In Chapter 17, he relates this story:
It has been said that the most insecure system is the one that isn't used. And more often than not, a security system isn't used because it's just too irritating.
Recently I did some work for the security group in a major multinational corporation. They were concerned that their senior management was doing business on insecure phones - land lines and cellular - sometimes in a foreign country. Could I help? There were several secure-voice products, and we talked about them and how they worked. The voice quality was not as good as normal phones. There was a several-second delay at the start of the call while the encryption algorithm was initialized. The phones were a little larger than the smallest and sexiest cellular phones. But their conversations would be encrypted.
Not good enough, said the senior executives. They wanted a secure phone, but they were unwilling to live with inferior voice quality, or longer call setup time. And in the end, they continued talking over insecure phones.
This is exactly the risk that an office takes by not deploying secure, properly configured WAPs managed by the IT team. Wireless networks are a convenience for many. There are some (albeit still rare) laptops appearing that don't even have a network jack anymore; and this is just the beginning of that design trend. Sooner or later, someone will get fed up and install a rogue access point, connected to the corporate LAN, and quite possibly insecurely configured and allowing routing to every resource on the network. It may already have happened. Wishfully thinking otherwise is simply ignoring the human part of the equation, hardly good practice of security.
