Tanya Khovanova has a fascinating and illuminating story about the
blind-spots that can leave security systems vulnerable. She describes a
clever one-way function using real-world tools:
Silvio Micali taught me cryptography. To explain one-way functions, he
gave the following example of encryption. 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. The decryption will take a lot more time than the
encryption. If the book increases in size the time it takes Alice to do
the encryption almost doesn’t increase, but the decryption process
becomes more and more draining.
This example is very good for teaching one-way functions to
non-mathematicians. Unfortunately, the technology changes and the
example that Micali taught me fifteen years ago isn’t so cute anymore.
Indeed you can do a reverse look-up online of every phone number in the
white pages.
Then she explains how a student pointed out her own blind-spot that made the system trivial to defeat:
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.
As Bruce Schneier points out, the young student is demonstrating
"security mindset," imagining an attack on a security system that works
on the weakest flank.
One-Way Functions
No comments:
Post a Comment