(No, not like opportunistic infection.) We've been having some discussions
about Brad Templeton's
opportunistic encryption idea, which is approximately based on using
public key cryptography without PKI or formal key exchange or
key verification. It gives you security against passive eavesdropping,
but not against man-in-the-middle attacks. Brad argues that this is
still worthwhile because man-in-the-middle attacks against public-key
exchange in e-mail are rare, difficult, and expensive, and because most
people's privacy can be invaded in other ways. In addition, doing away
with key-infrastructure requirements would allow you to have a "zero UI"
system, which Brad thinks could dramatically increase the number
of people willing to use e-mail encryption, in that you could then have
e-mail encryption without needing to know about it.
One scheme which is along the lines of what Brad has in mind is called
Herbivore, and he also found one by the name of
Passive Privacy System, or PPS.
It seems that doing away with key verification is a cryptographic heresy
of the highest order: aren't we all supposed to be more worried,
not less, about key exchange? Aren't we supposed to become
more aware of the
risks associated with even sophisticated uses of PKI? How can we
throw away PKI, fingerprints, certificates, keysigning, and
webs of trust altogether?
Brad's answer is more or less that these things are solving different
sorts of problems: public key cryptography with something PKI-ish
protects you against certain kinds of adversaries, and public key
cryptography with automatic, unverified key exchange protects you
against fewer adversaries, but still against all the adversaries
most people are likely ever to encounter. (When was the last time
someone even attempted an active man-in-the-middle attack
against the average e-mail user? When was the last time a law
enforcement agency, intelligence agency, or criminal had a motive,
means, and opportunity to perform passive surveillance against such
a user? I guess my answers to those questions would be "never" and
"routinely".)
On the other hand, practical MITM tools are being published.
dsniff was
notable for containing convenient, practical, free MITM tools you
can use against popular public key cryptographic protocols. If
doing MITM is really becoming easier for attackers, won't it be
more and more important to defend against it?
There's a real conflict between the effort to devise simple schemes
which a novice computer user would feel comfortable using, and the
effort to devise truly secure schemes which an expert would feel
comfortable trusting.
Fred was talking about the conflict between the good system and the
perfect system -- he regrets that people have held off on deploying
good technology because they were waiting for perfect technology.
This argues for a cost-benefit analysis, in which passive eavesdroppping
appears as a huge risk and active eavesdropping as a relatively small
risk. On the other hand, frustratingly, we know how to solve active
eavesdropping too! We just make everyone go to keysigning parties!
We provide them with free beer and pizza!
I wrote some code (called 15.py) which simulates a 15 puzzle,
allowing you to generate puzzle instances, see the result of
particular moves, and scramble the puzzle (through a series of
random moves of a specified length).
The whole reason I really wanted to have code like that was to
do a brute-force or random search for a useful solution to the
puzzle form "15-13-14", or
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 11] [ 12]
[ 15] [ 13] [ 14]
which I've often obtained after solving the rest of the puzzle. The
15-13-14 has been particularly frustrating, because I've had no idea
how to solve it systematically, and usually had to resort to random
guessing to complete the puzzle.
I thought that I could ask the computer to search for solutions to
the 15-13-14 so that I might understand or memorize such a solution.
The key to an efficient computer search here is not to make moves
entirely at random, but to follow two constraints:
- Never immediately undo a move you've just done. For example, never
move up and then immediately down, or left and then immediately right.
(A stronger form of this constraint: never bring the puzzle into a
form which it has previously occupied. This constraint can be
implemented in software, but it needs a hash table in order to be
efficient; sequential comparison to items in a list would be
extremely slow. So I settled for "never undo your last move"; if we're
looking for solutions which are as short as possible, they shouldn't
contain any backtracking.)
- It is (according to my experiments) never necessary to move anything
in the top half of the puzzle in order to solve the 15-13-14. Therefore,
never move down if you've already moved down once (until your most
recent up or down move is an "up").
Implementing these two constraints, via a class called the
ConstrainedMoveGenerator (which remembers its own move-generation state, and
imposes the constraints mentioned above on its choice of new random moves),
made the search pretty quick. One result of this was the generation
of several different 18-move solutions to the 15-13-14. Another result
was an experimental conclusion that there are no shorter solutions
(unless the shorter solutions disturb the tiles in the top half of the
puzzle).
The 18-move solution I prefer so far is "R, R, R, D, L, U, L, L,
D, R, R, R, U, L, L, D, L, U". If we write "+" after a move to mean
that the move should be repeated as many times as possible (which I've
been calling a "column move" because the tiles of an entire row or
column move together), this can be expressed as "R+ D L U L+ D R+ U L L"
from which point the solution is obvious.
There is one other 18-move solution found by my program, and it is
"D, R, U, R, R, D, L, U, L, D, R, R, U, L, L, D, L, U"; this and my
favorite solution have their last eight moves in common, and differ
only in the first ten moves.
Here's a typescript of what the original solution looks like in practice:
>>> print a # FifteenPuzzle object preconfigured with 15-13-14
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 11] [ 12]
[ 15] [ 13] [ 14] [ ]
>>> a.right(); a.right(); a.right(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 11] [ 12]
[ ] [ 15] [ 13] [ 14]
>>> a.down(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ ] [ 10] [ 11] [ 12]
[ 9] [ 15] [ 13] [ 14]
>>> a.left(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 10] [ ] [ 11] [ 12]
[ 9] [ 15] [ 13] [ 14]
>>> a.up(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 10] [ 15] [ 11] [ 12]
[ 9] [ ] [ 13] [ 14]
>>> a.left(); a.left(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 10] [ 15] [ 11] [ 12]
[ 9] [ 13] [ 14] [ ]
>>> a.down(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 10] [ 15] [ 11] [ ]
[ 9] [ 13] [ 14] [ 12]
>>> a.right(); a.right(); a.right(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ ] [ 10] [ 15] [ 11]
[ 9] [ 13] [ 14] [ 12]
>>> a.up(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 15] [ 11]
[ ] [ 13] [ 14] [ 12]
>>> a.left(); a.left(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 15] [ 11]
[ 13] [ 14] [ ] [ 12]
>>> a.down(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ ] [ 11]
[ 13] [ 14] [ 15] [ 12]
>>> a.left(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 11] [ ]
[ 13] [ 14] [ 15] [ 12]
>>> a.up(); print a
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [ 10] [ 11] [ 12]
[ 13] [ 14] [ 15] [ ]
>>>
I'd like to publish my FifteenPuzzle class when I can get it a bit
cleaned up. I also have some card classes sitting around which are
supposed to simulate a spectator's behavior for a non-interactive
("batch" or "off-line") card trick described in Gardner. (You can search
for "casual_shuffle" in my Advogato diary to find some information
about that.) I should dig out some of that stuff and publish it
too, and then I fondly remember writing a Kruskal count simulator in
BASIC to test co-incidence rates with well-shuffled decks of various
sizes.
Computers are actually really neat for experimentation. Never let it
be said that computers are precise and logical and predictable; there
are so many things they can simulate for which you really don't
know the answers in advance.
If computers were predictable, people would probably not be interested in
them, much as if people were predictable, other people would probably
find them boring (so much so that "predictable" is often a synonym for
"boring"). To some extent, we like to interact with other people
because we don't know what they're going to do, and we want
to find out.
People are definitely better than computers for this.
I wonder what else might be in the off-line card trick genre. The particular
trick I'm thinking of is described in Mathematics, Magic, and
Mystery as "Magic By Mail"; do we know whether other off-line
card tricks exist? I guess this category could be further sub-divided in
various ways.
Ren and I went to Biella's place and watched Harold and Maude
there for the first time. It's a touching movie.
Some people said some very funny things, but they are attorney work product
privileged and I can't repeat them here. :-( :-(
43 successive column moves equal the identity -- or "there are only 42
different positions which can be reached on a 15 puzzle in its default
condition by successive column moves". Another nice appearance of
the number 42.
Argh, I noticed that there's also the 14-15-13, which is different from
the 15-13-14; how do you solve a 14-15-13 easily? Were some of my
automated solutions actually solutions to 14-15-13?
OK, if you take my standard solution and do it to a solved puzzle,
you get the 14-15-13. Then if you do it again, you get the
15-13-14. Then if you do it again, you get the solved puzzle.
This is to say that the standard solution (the 18-move "R, R, R, D, L, U"
thing given above) is a macro which swaps the leftmost tile in the bottom row
into the rightmost position (XYZ --> YZX), so it takes 13-14-15 to 14-15-13
to 15-13-14 back to 13-14-15 (and has a period of three). This also means
that the shortest solution to the 14-15-13 is the inverse of the shortest
solution to the 15-13-14, to wit:
D, R, U, RR, D, LLL, U, RR, D, R, U, LLL
or, with the "plus" notation,
D, R, U, R+, D, L+, U, RR, D, R, U, L+
Learning both of these would be marginally useful; I don't see any way to
predict whether you'll end up with 15-13-14 or 14-15-13 as the last step in
solving a 15 puzzle. On the other hand, if you can do either macro
quickly, you can solve either 15-13-14 or 14-15-13 by doing the
macro you know at most twice. I think I could do it in three or four
seconds, with practice, so maybe that's good enough.
By the way, this is the 15 puzzle I bought at
Restoration Hardware;
it's made by Binary Arts. Is
"leatherette" leather?
Thanks to Marc, I got two interesting pictures of me from when I was
much younger scanned in. (I'll probably make smaller versions and
put them up on my home page.)
This is the only existing picture of me and the New York World Trade
Center. My father carries me on the Brooklyn Promenade (1980?).
This is the first time my picture was published in the newspaper.
Daily Hampshire Gazette caption: "Seth Schoen got the best
job of the day -- watching the apples cook" [when my cooking-for-kids class
at the Northampton YMCA made applesauce] (1985?).
