Nice Security Mindset Example

A real-world one-way function:

Alice and Bob procure the same edition of the white pages book for a particular town, say Cambridge. For each letter Alice wants to encrypt, she finds a person in the book whose last name starts with this letter and uses his/her phone number as the encryption of that letter.

To decrypt the message Bob has to read through the whole book to find all the numbers.

And a way to break it:

I still use this example, with an assumption that there is no reverse look-up. I recently taught it to my AMSA students. And one of my 8th graders said, “If I were Bob, I would just call all the phone numbers and ask their last names.”

In the fifteen years since I’ve been using this example, this idea never occurred to me. I am very shy so it would never enter my mind to call a stranger and ask for their last name. My student made me realize that my own personality affected my mathematical inventiveness.

I’ve written about the security mindset in the past, and this is a great example of it.

Tags: , , ,

Posted on April 9, 2013 at 1:49 PM • 46 Comments

Comments

Brandioch Conner • April 9, 2013 2:22 PM

I think that your “attack trees” model would be a good way to visually demonstrate some of the gaps in examples such as this.

Or, to quote from the evil overlord manual:

One of my advisors will be an average five-year-old child. Any flaws in my plan that he is able to spot will be corrected before implementation.

Simon S. • April 9, 2013 2:57 PM

If anyone called me out of the blue and asked for my last name, they’d have to conclude that my last name was “Who is this?” unless it was just “click“.

Tom S. • April 9, 2013 3:15 PM

RE Simon S.–If I didn’t get your name on the first call, I would call back at 3 AM and hope to either get your name from the answering machine, or at least wake you up for the aggravation you caused me 🙂

Angus S-F • April 9, 2013 3:22 PM

And of course in the current world, whitepages.com/reverse_phone would be all you would need.

dho • April 9, 2013 3:24 PM

It wouldn’t take longer than looking them up, unless the procured book was available in digital format. Bob literally has to scan the entire book looking for the next number. This is O(MN) where M is the number of letters in the message and N is the number of names in the book. (In the worst case, no number is ever reused for the same letter). We can probably even assume this function is dominated by N.

In the student’s example, Mallory’s worst case time is O(M). Indeed, Mallory doesn’t even need to attack every letter. Letter context will allow for guessing missing letters. And it is fair to assume that 5 minutes per letter per call is less time than it takes to scan every number in the book. I certainly couldn’t go through even a small city’s phone book in 5 minutes.

david • April 9, 2013 3:40 PM

And it is fair to assume that 5 minutes per letter per call is less time than it takes to scan every number in the book. I certainly couldn’t go through even a small city’s phone book in 5 minutes.

On average, you’d find it halfway through your search, if it was uniformly distributed. If it is not uniformly distributed, you could speed things up substantially by exploiting that – run through the E’s first, for instance.

MangoLiger • April 9, 2013 3:47 PM

Purposely include your own phone number in the message, and if someone calls asking for your last name, you know your message is about to be compromised!

Clive Robinson • April 9, 2013 3:49 PM

The “human world” analogy of a One Way Function I first heard of was an English-French dictionary with the French to English section removed…

And like the 8th grader I put a spoke in the wheel of the person explaining by pointing out that English-French and back again did not have a one to one maping because there are cases of two words in English (Security / safety) having just one in French (Sécurité)…

Sometimes it’s easier to just use a real mathmatical example of a simple OWF.

Noxonomus • April 9, 2013 4:03 PM

@Simon S

“Hi I’m [fake first name] a [grade level] student from [local school name] and I have to make a histogram from real world data for my math class what is the first letter of your last name?”

Nick P • April 9, 2013 4:25 PM

Bruce showing how ineffective SmartWater was for its primary use is probably the best one I know of.

And, of course, they’re still in business.

mikeash • April 9, 2013 4:45 PM

For people talking about refusing to give your name over the phone, it’s important to realize that you don’t need to extract every single letter of the secret message. Even with a 50% success rate, you’ll probably have no trouble figuring out the entire message. English typically has only about one bit per letter of entropy. I bet half the population would give out their name over the phone, probably in response to a simple direct question, let alone with some slight social engineering.

boog • April 9, 2013 4:47 PM

@Simon S.

Do you assume that your response* is pretty average – that most people are likely to react the same way? If so, why?

My point: I expect one might not get all the letters, but if one got most of them it could still make the message significantly easier to crack.

*I admit my response to such a phone call would be much like yours. Or I’d just lie.

martin • April 9, 2013 5:07 PM

Maybe I am being pedantic here, but while this is one-way, I don’t think it is a function in the sense that it is not mapping an input onto a unique output.

I realise the purpose of the exercise is to teach a concept to 12 year olds, but often being correct is as important as being simple.

Brian • April 9, 2013 5:13 PM

You’re assuming that the person that answers the phone is the person to whom that number is registered to.

GAZZA • April 9, 2013 8:56 PM

Couldn’t you just use everything but, say, the last 4 digits of each phone number? That’s 10 000 numbers per letter that Bob would have to check, and (assuming an 8 digit phone number) still fairly collision resistant for a decent length word.

voltaire • April 9, 2013 10:15 PM

Apparent poor assumptions:
(0) Nobody else knows about the scheme.
(1) Nobody else has or can acquire (a copy of) the book (through any means).
(2) The keyspace (~10 digit numbers) is large. (It’s not really)
(3) Entities throughout the keyspace are something-like-randomly distributed. (They are not; they are most likely heavily weighted toward certain patterns, for example known exchange prefixes or the more recently mandated leading digits after the exchange prefix readily guessable, roughly the keyspace is then probably more like ~7 digits or less)
(4) Nobody has a list of the most popular surnames.
(5) The number-groups encoding specific letters are vulnerable to basic frequency analysis as per all simple substitution ciphers, ie. in any English
(6) The participants can’t represent characters outside of the 26 letters of the alphabet (owing to the encoding methodology) so the frequency analysis methodology becomes obvious to basic inspection as the unique number-groups approach 26.
(7) There are no collisions between multiple persons in the phonebook having the same phone number listed.

The point is: calling people is a really expensive and loud attack. There are far better and more effective ones, requiring less time and effort for an attacker, that don’t compromise their interest in the scheme.

sparkygsx • April 10, 2013 1:36 AM

Voltaire: you have your fair share of poor assumptions.

The scheme assumes everyone has a copy of the book, it’s all about the (assumed) huge effort for the (manual) reverse lookups.

The keyspace is the number of entries in the book, the length of the numbers is irrelevant, assuming it doesn’t impact the speed of the lookups.

But the biggest of all: obviously, numbers wouldn’t be reused! It would be rather stupid to use the same number repeatedly for the same letter. If a new, randomly selected number is used for every letter, frequency analysis will get you nowhere, because not a single number would have been

Christian • April 10, 2013 2:05 AM

One of the things people did here when the first telephone books on CD-ROM came out and reverselookup of addresses was forbidden (Name -> Address+Tel ok, Tel -> Name not ok)
,was simply looking at the cd and noticeing that the entries were all kept in an easily readable format. So it was not hard to implement reverselookups yourself once you were not restricted to the proprietary software that came with the telephonebook.

Usecase: you could be at a flat being empty and for rent before anyone else!

Martin P • April 10, 2013 2:54 AM

I think the point is being missed – it’s true the solution is flawed – just as the cipher is ludicrous. The point is though that the ‘suggested’ solution wasn’t even considered because of personality traits of the analyst

Autolykos • April 10, 2013 4:27 AM

@mike: Yep, even slightly varying your question might get you success rates well over 90%. People are trained to correct mistakes, and usually don’t start to think unless they are surprised. So instead of asking “What’s your last name?”, you ask “Am I speaking to Mr. Robert Johnson?”. You’ll either get “No, you’re speaking to [insert name here]” or a flat “No.”. Asking for the name now will probably have a very good chance of success (and if they still don’t give it, there isn’t much hope they’ll ever).
And while reading a letter with 50% of the characters is hard but possible, having 75-90% makes it trivial.

Jasper • April 10, 2013 4:37 AM

Great story Bruce. And it makes people think… That’s what’s most important. Get it across, make it well thought.

All in all, keeping the key secret is what is most important, and difficult.

People will always be people, there will be a way to find out… That’s where the risk discussion comes in. How must effort to protect is it worth.

My 2 cents (that’s all for today)…

Jon • April 10, 2013 8:49 AM

As I recall, some years ago the telephone company used to sell phone books where the numbers were in sequential order and everything else was jumbled up.

They may have only been available to law enforcement and such, but that’s hardly ‘security’.

J.

Spaceman Spiff • April 10, 2013 10:28 AM

  1. Scan book into computer.
  2. Apply and OCR tool to extract last names and phone #s into table indexed on phone #.
  3. Scan encrypted text into computer.
  4. Look up each number in turn in table, writing data to a file.
  5. Read file.

Obviously, #1 is the slowest part of this process, unless as noted by dho that the book is already available in digital format. Once the book is digitized, the rest should take a very short period of time.

Carl C. • April 10, 2013 10:45 AM

Actually, it’s possible that the phone-book example has actually gotten CLOSER to a one-way function over time.

Now that it’s become more common for women to keep their maiden names when they marry, there are collisions in the phonebook lookup: two different last names frequently map to the same phone number.

Of course, the number of colliding letters on a single number is still really low…

Andy • April 10, 2013 11:44 AM

I must be missing something.

A one way function, at least one that has practicable uses, should result in the same answer.

If both people run the same message through the function, they will likely get different results. So its use to verify the message doesn’t work.

Bob T • April 10, 2013 1:02 PM

One way function example:

Present a security mindset example using a very simplified one way function to a bunch of math/crypto enthusiast and see how long it takes the discussion to get back to the security mindset example. 🙂

Murray • April 10, 2013 6:14 PM

@ Bob T
Yes, I agree. Everyone was missing the point.
It was not a problem to be solved, but an example of differing thought processes.

Clive Robinson • April 10, 2013 7:46 PM

I was doing a little research this PM for a talk I have to give on computer design fundementals and I was looking up the British Camb Comp Labs founder Maurice Wilkes who first talked about and named the concept of microprograming CPUs.

Well it turns out he was probably also the first person to come up with using One Way Functions for security. He designed the basic passwoord system that was later taken up and used in Unix.

Figureitout • April 11, 2013 12:21 AM

Good engineering involves thinking about how things can be made to work; the security mindset involves thinking about how things can be made to fail.
@Bruce S.
–That’s your biggest “meta-meta” point. I remember your ant story but not that statement, I weirdly came to that conclusion on my own. Of the engineers I know (not security people), they tend to be more optimistic and cheery; but will get irritated if you start telling them security vulnerabilities. They’re creative, but in the sense of “making things work”, not fail. And actually I kind of wish I was more that way…

Figureitout • April 11, 2013 12:27 AM

@Clive Robinson
–I’d definitely pay to hear a talk by you (and if you brought some papers, even better). I don’t know if you’ve linked in the past (still haven’t read all the archives), but I’d like to read some papers by you if any are freely available.

Clive Robinson • April 11, 2013 6:16 AM

@ figureitout,

I’d like to read some papers by you if any are freely available

I don’t publish “papers” in the academic way I produce “reports” for others “up the chain” and as it’s their shilling that pays for them by way of employment etc…

Like academics have problems with publishing houses claiming all the IP rights for the papers themselves, employers likewise claim all IP rights for themselves over all works by their employees irrespective of if it’s related to the employers line of business or not [1].

I once had a bad experiance over a book I was writing many many years ago (on serial communications) and my then employer gave me a choice hand over all the royalties copyright etc or be sued and have my house etc taken away from me. On checking with a lawyer I found that the only wriggle room I had was to resign and in effect destroy the “work” by making it unpublishable and return the advance fee to the publisher.

For a while there after when I went to new jobs I made the employer sign in advance a limitation or waiver into the employment contract such that I could release unrelated work and retain the IP restriction free. However I found when working for a small employer that got taken over, that the new employer (part of a major publishing organisation) had different ideas, ie accept a new employment contract without the waiver or legaly make myself redundant…

Much of this problem in the UK can be traced back thirty odd years to political influence under Maggie Thatcher (recently deceased) of both Norman Tebbit and Michael Hesaltine (who as well as being a minister of state also owns several publishing interests).

You quickly get the idea that the “free market” they espoused then and worse today is two level, freedom for those with power to exert compleat exploitation of those without power or independance.

Academics have woken up to this fact and they are now kicking back against various “publishing concerns” however the same is not yet happening in other areas such as employment especialy where a profit might be made such as patents and published works [2].

Also there is a naive belief that authors get payed lots of money, it’s realy not true most authors of technical books would be unable to earn a respectable living from writing even if they put out a new book each year. The big sums of money you hear about for advanced fees are paid to what you might call “vanity names” that is those who’s names look good on a publishers list of authors. Some of these names do earn the publishers real money but (don’t win the Booker etc) most like celebs and politico’s lose the publisher considerable sums of money, but gain the publisher other benifits or influence (one of which might be favorable legislation over IP).

If you want an idea of what the real cost of publishing technical books of limited market are go and have a look at the prices for those books from the likes of Artech House Publishers or to a lesser degree Butterworth-Heinemann.

[1] Worse the custom and practice of law is such that it does not have to be written into your employment contract, and it can be enforced against any works you subsequently produce for a minimum of six months but often longer.

[2] Arguably this state of affairs is what Aaron Swartz was fighting in his own way, befor the forces that be had influance applied via IP holders of various forms to make him a criminal [3].

[3] People tend to forget just what a blight having been convicted has on your life, it is in effect the equivalent of “the curse of Cain”. For instance in future times when arguing your opponent simply has to say “Mr Smith who is a convicted…” to remove almost all credability/sympathy with others for your argument [4].

[4] Figures from the US show that even successfully clearing your name leaves you badly damaged with significant loss of assets and little chance of regaining any kind of status and earnings potential you might have had prior to the erroneous conviction [5].

[5] Such behaviour is just one part of the legal practice of “striping of rights” whereby a defendent has the means to defend themselves stripped away not just prior to prosecution but subsiquently. And in the UK we have such delightful methods such as the Proceeds of Crime Act (POCA) various parts of Company and Tax law as well as now having no limit on how often or how long tthe Government can prosecute you over the same offence whilst you have strict time limitations on appeals and seeking restitution for wrongfull acts of prosecution, as well as the usual shenanigans over costs liabilities.

htom • April 11, 2013 12:34 PM

@Spaceman Spiff — step 3.5, sort once by telephone number. I’m not sure what the optimal storage structure is for the search in step 4.

paul • April 11, 2013 4:07 PM

The nice thing about the asking algorithm is that the answer is easily checked. So it’s essentially a fallible oracle for a one-way function. (Which in turn has properties you can reason with.)

Marc • April 12, 2013 1:22 PM

@Brian –
“Does your dog bite?”
“No.”
(Aaaaaaigh!)
“I thought you said your dog did not bite!”
“He is not my dog.”

alex • April 13, 2013 12:17 PM

Social engineering has long been a hacker’s favourite tool. It often is the fastest and least noticed route for getting past security systems.

Ultimately, this scheme is just a one-time-pad, but with a huge vulnerability: there are multiple ways to verify the pad.

Jarda • April 14, 2013 7:36 AM

“I still use this example, with an assumption that there is no reverse look-up.”

Yes, but calling the number and asking the name is a reverse look-up. So next time just add the condition that someone has blown-up the telephone exchange 5 minutes ago.

Jonadab • April 16, 2013 6:26 AM

Thirty years ago, that would work very well. As others have said, you’d get enough letters to be able to work out the rest easily. Today, however, the average household has somewhere between 3 and 5 distinct last names in it, and I can’t think of any way to know which of your acquired data are valid.

mapping an input onto a unique output.

If it did that, it would be a one-to-one function; but if it does not, it’s still a function.

The point is though that the ‘suggested’
solution wasn’t even considered because
of personality traits of the analyst.

Indeed. In some ways, it’s akin to the ant farm story, except from the opposite perspective (showing how a person can be blind to obvious things rather than how a person can see less obvious things).

a • April 16, 2013 8:48 AM

Maybe I’m different but any given time anyone has tried on my private phone any of the above to get the name has failed.
(Reverse lookup fails when the number is secret so if my number was on that list and someone called me to get the name, good luck).
“Is this Bob?” “No.” (No more info given)
“Is this Mr Johnson?” “No.” (No more info given)
And any variation of it. If you call me, you better know who you are calling and why.

Phocks • April 17, 2013 9:11 PM

You’re missing the obvious reason that this would, in actuality, work. Old phone books. Assuming my partner and I both know to use the Spring, 1977 edition for example, there are suddenly a number of strong protections built in.
1. Unless you know which specific edition to use, good luck. Back then, numbers didn’t follow subscribers, at least not commonly.
2. The chance of the correct letter still having that number are essentially random. Good luck calling the numbers.
3. In some instances the information might be obtainable online, but I pretty much doubt it.
4. If you want to go back significantly further (and really, why not for our scenario) older phone numbers are not even obviously phone numbers.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.