My fiancee, Kelsey, claimed that she could tell the difference between
Coke and Pepsi. I wanted to put this to the test. Since there were
only two of us, arranging the test wasn't a simple matter of asking
someone else to pour some cups. I also wanted to do this right:
testing must
be
double-blind. I devised a little scheme that allowed us to perform
two different tests.
The first test was seeing if Kelsey or I could determine which
beverage was Pepsi and which was Coke. The second was determining if
there was any distinction in taste between the two drinks at all,
which consisted matching two different samples together. The second
test also acts as a check on the first test.
We bought one bottle of each at CVS. Next, we labeled six different
cups with the numbers one though six. Each odd number is paired with
the following even number. Kelsey, who was alone, used a die with an
even number of sides (this includes a something as simple as a coin
toss) to put one beverage in cup #1 and the other in cup #2. In this
case, we used my 20-sided die I use for Dungeons and Dragons, because
using it for this purpose was just full of win.
The die is important here as a random number generator. If it is left
up to a human to decide what drinks go where, we may bias the
setup. For example, I may be more likely to put Pepsi in an
odd-numbered cup than an even-numbered one.
It is difficult for human beings to behave randomly. Try generating a
list of 50 coin tosses yourself. I mean, without a coin. Just type a
series of 50 H's and T's. If you examine your list of flips, you will
find that you often generate very improbable series of flips
(excessive heads or tails) and exhibit patterns. We need dice or
coins to make decisions for us in this experiment.
To do it right, the beverage must be chosen before the roll: "I will
be pouring Pepsi now.". Roll the die. If it rolls an odd number, pour
the drink into the odd cup (#1). Write this information down and keep
it secret.
Next, after allowing the foam to calm down (which might accidentally
reveal information to me), Kelsey leaves the room and I enter. I
perform a similar procedure to distribute the drinks into cups #3 and
#4, then #5 and #6. I keep track of what drink, #1 or #2, goes into
what cup. I keep it secret. These last two cups are for the purpose of
the second experiment.
At this point Kelsey knows what was in cups #1 and #2, but not where
they went. I know where they went, but not what was in the
cups. Together we know everything, but individually we know
nothing.
In order to make the second test double-blind, and allow me to
participate, I leave the room. Kelsey rolls the die. If it rolls odd
she switches the label on cups #5 and #6. It is important that these
cups are identical. One flaw potential, however, is that the liquid in
each cup may look unique. One may be more fizzy or one cup a little
more full. Noticing this may happen subconsciously, which is the whole
point of doing double-blind tests.
Ok, we didn't actually do this last part because I didn't think of it
till later.
We sample all four cups (#3 - #6) in pairs, alone, making notes on
what beverage we think is in what cup. Once we are both done we share
our secrets and see how well we did.
Our results? Neither of us could tell the difference between Coke and
Pepsi.
I was at my fiancee's parent's house over Fourth of July weekend. Her
family likes to leave plenty of reading material right by the toilet,
which is something fairly new to me. They take their time on the john
quite seriously.
While I was in there I saw a large book
of Sudoku
puzzles. Since the toilet is a good spot to think (I like to call it
my
"
thinking chair"), I thought out an algorithm for solving
Sudokus. I then left the bathroom and implemented it in order to
verify that it worked.
The method is trial-and-error, which it does recursively: fill in the
next available spot with a valid number as defined by the rules
(cannot have the same number in a column, row, or partition), and
recurse. The function reports success (true) when a solution was
found, or failure (false), which means we try the next available
number. If no more valid numbers are available for testing at the
current position, then the puzzle is not solvable (we made an error at
a previous position), so we stop recursing and return failure.
More formally,
Find an open position.
Look at that position's row, column, and partition to find valid
numbers to fill in.
Fill the position with one of the valid choices.
Recurse using the new change.
If the recursion reports a problem (returns false), try the next
valid number and repeat.
If recursion reports success (true), stop guessing and return
success.
If the list of valid numbers is exhausted, return failure (false).
Note that the recursion depth does not exceed 81, as it only recurses
once per blank square. The "game tree" is broad rather than deep. It
doesn't have to duplicate the puzzle matrix in memory either because
all operations can be done in place.
Here is the implementation in C I typed up just after I left the
bathroom,
int solve (char matrix[9][9])
{
/* Find an empty spot. */
int x, y, i, j, s = 0;
for (i = 0; i < 9 && !s; i++)
for (j = 0; j < 9 && !s; j++)
if (matrix[i][j] == 0)
{
x = i; y = j; s = 1;
}
/* No empty spots, we found a solution! */
if (!s)
return 1;
/* Determine legal numbers for this spot. */
char nums[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
for (i = 0, j = y; i < 9; i++)
nums[(int)matrix[i][j]] = 0; /* Vertically */
for (i = x, j = 0; j < 9; j++)
nums[(int)matrix[i][j]] = 0; /* Horizontally */
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
nums[(int)matrix
[i + ((int)(x / 3)) * 3]
[j + ((int)(y / 3)) * 3]
] = 0; /* Within the partition */
/* Try each possible number and recurse for each. */
for (i = 1; i < 10; i++)
if (nums[i] > 0)
{
matrix[x][y] = i;
if (solve (matrix))
return 1;
}
/* Each attempt failed: reset this position and report failure. */
matrix[x][y] = 0;
return 0;
}
I assumed that it would be slow solving the puzzles, having to search
a wide tree, but it turns out to be very fast. It solves normal
human-solvable puzzles in a couple of milliseconds. Wikipedia has a
near-worst case Sudoku that is designed to make algorithms like mine
perform their worst.
On my laptop, my program solves this in 15 seconds, which means that
it should take no more than 15 seconds to solve any given Sudoku
puzzle. This provides me a nice upper limit.
There is a way to "defeat" this particular puzzle. For example, say an
attacker was trying to perform a
denial-of-service (DoS) attack on your Sudoku solver by giving it
puzzles like this one (making your server spend lots of time solving
only a few puzzles). However, these puzzles assume a certain guessing
order. By simply randomizing the order of guessing, both in choosing
positions and the order that numbers are guessed, the attacker will
have a much harder time creating a difficult puzzle. The worst case
could very well be the best case. This is very similar to how
Perl
randomizes its hash array hash functions.
Now suppose we kept our guess order random then "solved" an empty
Sudoku puzzle. What we have is a solution to a randomly generated
Sudoku. To turn it into a puzzle, we just back it off a bit. A Sudoku
is only supposed to have a single unambiguous solution, so we can only
back off until just before the point where two solutions becomes
possible. If you imagine a solution tree, this would be backing up a
branch until you hit a fork.
Normally, Sudokus are symmetric (in the matrix sense), but completely
randomizing the position guessing order won't achieve this. To make
this work, the randomizing process can be adjusted to only select
random points on the upper triangle (including the diagonal). For each
point it selects not on the diagonal, the mirror point is
automatically selected next. This will preserve symmetry when
generating puzzles.
One issue remains: there seems to be no way to control the difficulty
of the puzzles it generates. Maybe a number of open spaces left behind
is a good metric? This will require some further study (and another
post!).
A co-worker asked me a question today about C/C++ pointers,
If a pointer is declared inside a function with no explicit
initialization, can I assume that the pointer is initialized
to NULL?
We were down in the lab and, therefore, he had no Internet access to
look it up himself, which is why he asked. When I code C, it is just a
sort of mental habit to not use a non-static function variable without
first initializing it, but is this accurate? I knew the answer
was "no", but I wanted to be able to explain the "why".
Anyway, I quickly recalled some of my experimental C programs and
thought carefully about the mechanics of what is going on
behind-the-scenes, allowing me to confidently give him a "no"
answer. I then threw this together in a few seconds to prove it,
#include <stdio.h>
void a ()
{
int * x = (int *) 0x012345FF;
double y = -63454;
(void) x;
(void) y;
}
void b ()
{
int * x;
double y;
printf ("%p, %f\n", x, y);
}
int main ()
{
a ();
b ();
return 0;
}
When you compile it, make sure you don't use the optimization options
(-O, -O2, or -O3
for gcc) because they change the inner-workings of the
program. It might do things like make those functions inline (so they
won't be on the stack as I am intending), or even toss
out a(), as it appears to do nothing. The compiler sees
that, even though I "used" variables in a() by casting
them to void, nothing is really happening,
so a() can be ignored. We can probably get around this
with a tacked
on
volatile declaration, which you might see a lot of in a
micro-controller program. In a micro-controller, some memory addresses
are mapped to registers external to the software, so, from the
compiler's point of view, access to these locations may look like
nothing is really happening. Optimizing away variables that point to
these memory locations will lead to an incorrect binary, so your robot
or laser guided shark or whatever won't work.
Anyway, compiling with optimization will break my example! So don't do
it here.
When compiling, you should get some warnings about using uninitialized
variables, which is kind of the point of my example. Ignore it. That
warning alone gives away the answer to the main question, really, but
this example is a bit more fun!
Before you run it, study it and think about what the output should
look like. When a() is called, its stack frame goes into
the call stack, which contains the two declared variables. These
variables are then assigned as part of the function
execution. When a() returns, the frame is popped off the
stack. Then b() is called, and, as the variable
declarations are exactly the same, it will fit right over top
of a()'s old stack frame, and its variables will line
up. x and y are not assigned any value, so
they pick up whatever junk was lying around, which happens to be the
values assigned in a().
When you run the program, this is the output,
0x12345ff, -63454.000000
The pointer is not initialized
to NULL. If x is passed back uninitialized
under the assumption that a NULL is being passed, some
other poor function that handles the return value may dereference it,
resulting in possibly
some
nasal demons, but most likely an annoying segmentation
fault. Worse, this error may occur far, far away from where the actual
problem is, and even worse than that, only sometimes (depending on the
state of the call stack at just the right moment).
Note here that I am talking about non-static function variable
declarations. Global variables and static function variables will not
be on the stack. They are placed in a fixed location (in the data
segment), and their values are implicitly initialized to 0
at compile time.
In a
previous post I discussed one-time pads. Note: this is about a
cryptosystem, not some kind of menstruation disaster. The information
for this post comes
from
a little gem I saw on the xkcd
forums. I generally don't lurk around there because it suffers
from the same disease most non-self-moderating forums suffer from:
anal retentive, power-abusing, whiny moderators. I lucked out this
time.
The user Berengal posed the question,
One thing I've been wondering about is if you can use a single
one-time-pad to encrypt other one-time-pads to send around.
My first though was, "Hey, why didn't I think of this?". Then,
after a moment, I realized that it was the sort of thing that is too
good to be true. This is along the lines of ideas that break the laws
of thermodynamics. We are looking at a perpetual motion machine
here. Just as you cannot create or destroy energy, neither can you
use a one-time pad to distribute more than one other equal length
one-time pad. Let's make it formal,
In any closed one-time pad cryptosystem, the total number of
one-time pad bits in the system remains the same.
Also, if something like this could work, people would be using it
already everywhere. Before I got a chance to think too much about it,
user AJR spoiled it with an excellent proof on why it won't
work.
Note below that I use ^ to indicate
exclusive or
(XOR).
Suppose you have a master pad, K, that you use to
distribute two message pads, k1
and k2. You have two
messages, m1
and m2. We then have four transmitted texts:
two encrypted message pads e1
and e2, and two
ciphertexts c1
and c2. We define these as,
e1 = K ^ k1e2 = K ^ k2c1 = k1 ^ m1c2 = k2 ^ m2
Suppose an adversary is able to record all four transmitted texts. He
can apply them like so,
e1 ^ c1 = K ^ k1 ^ k1 ^ m1 = K ^ m1e2 ^ c2 = K ^ k2 ^ k2 ^ m2 = K ^ m2
This cancels the original message keys and effectively leaves you
encrypting two messages with the same pad, which is exactly the wrong
thing to do when using one-time pads. Once that is done, the adversary
can do tricks like,
e1 ^ e2 ^ c1 ^ c2 = m1 ^ m2
What is left is the two messages XORed together with no keys/pads
involved, which, depending on the messages, might reveal
something. Don't make this mistake.
Update: My friend Gavin thought he discovered a way to make
one-time pads useful, but I was able to show him that it simply
reduces to the same situation here. His
website details the algorithm and the crack that breaks it.
In a
previous post I discussed one-time pads. The information for this
post comes from Bruce
Schneier's
Applied Cryptography (section 10.8).
One-time pads are great for something
called
plausible deniability. With plausible deniability, when a person
holding encrypted data is coerced into decrypting their data, the
interrogator will not be able to tell if the person is complying with
the decryption order or not. For example, the victim could provide an
alternate key that decrypts the ciphertext into some harmless dummy
plaintext. To make this more plausible, the plaintext would probably
be something potentially embarrassing, such as pornography or secret
love letters.
We have a one-time pad K, a plaintext P, a
dummy plaintext (the pornography or love letters) D, a
dummy key K', and a ciphertext C. Below, I
denote XOR with ^.
To encrypt our plaintext, its the normal one-time pad algorithm,
P ^ K = C
Bob and Alice share K, so decryption works like,
C ^ K = P
However, the secret police come along with
their
thumbscrews and demand that Alice and Bob give them the one-time
pad K. Instead, they will provide K'. How is
K' defined? Like this,
K' = C ^ D
Because K is a one-time pad and is randomly generated,
there is no way to prove that K' is not the real
key. Alice and Bob give up K'. The secret police decrypt
it,
C ^ K' = C ^ C ^ D = D
"See? We were just keeping our love affair a secret from our spouses!"
Example code:
otp.c,
Makefile
(this Makefile may be useful)
The one-time
pad (OTP) is an encryption algorithm that provides perfect
secrecy, provided it is implemented properly. The pad, which is
essentially a key that is the same length as the message, must be used
only once (hence the name), kept secret, and, the hard part, generated
using some truly random
method. It works by XORing the pad and the message
together, which makes the ciphertext indistinguishable from randomly
generated data.
I want to be clear with the terms here. A one-time pad is not
"random". Numbers aren't random. It's just not a property numbers can
have. To be pedantic, what is random is the method by which the
numbers are generated. Think "random number-generators", not
"random-number generators".
A pseudo-random number generator (PRNG), like what your computer
normally uses to randomly generate numbers for games, will not work
here. Your computer is mindlessly deterministic and is not capable of
being a true random number generator by itself. PRNGs exhibit patterns
and eventually loop, spitting out the same numbers in the same order
as it did when it started. When the pad is generated randomly, each
bit in the pad will be
statistically independent from every other bit. That is, one value
of one bit has no affect on the value on other bits. Because of this,
the ciphertext encrypted from a one-time pad is equally likely to
decipher into any possible plaintext of the same length. This makes it
immune to brute-force attacks. The bits in a PRNG are not
statistically independent, making them vulnerable to attack. If you
know the value of one bit of the key, you also know something about
other bits in the key.
Generally, two parties wanting to communicate using a one-time pad
will exchange a large pad, such as a CD filled with randomly generated
data, in person before one of them travels somewhere, say another
country, where data needs to be sent back securely. As bytes from the
pad are used, they are destroyed and never used again. If the pad is
100kB in length, only up to 100kB in data can be transmitted
securely. Like most forms of encryption, key management is one of the
trickiest parts.
I have provided a simple little C program for encrypting a message
using a one-time pad (download link at the top). It
encrypts stdin using the one-time pad provided in the
file indicated as the first argument. Ciphertext is sent
to stdout. As an added bonus, when a second argument is
provided, the used bits of the key are written to the file provided in
the second filename. I will show you why I added this in a moment.
I have provided an example pad for you, generated from my
own /dev/random,
which provides a true random number generator (RNG).
Here is how you put it to use in encrypting the source code for this
program,
otp random.data < otp.c > otp.c.otp
If you shared the pad random.data with your friend, whom
you are trying to communicate with, she can decrypt it with a similar
command,
otp random.data < otp.c.otp > otp.c
random.data is only 207kB, so your message cannot be any
longer than that. Additionally, once 207kB has been sent, you must
exchange a new pad before more ciphertext can be transmitted. If you
re-use your pad, you compromise the security of the new ciphertext as
well as the old ciphertext.
The reason I provided the second option was this: you can
use /dev/random directly without losing the pad (assuming
you have a operating system that has a /dev/random, as
all decent operating systems do).
This is only academic, as the one-time pad is generally exchanged
before the plaintext exists. Otherwise you can just exchange the
plaintext when you would have normally exchanged the one-time pad!
Also, /dev/random is slow. It generates numbers
using environmental noise, which is only available at a trickle. If
you want to encrypt a 1MB message, it could take days. With shorter
messages you can usually speed things up by moving the mouse around or
mashing the keyboard (this can be fun).
More on one-time pads next. In particular, I will present two tricks:
one that works and one that does not work.
Don't stop here! This isn't everything. Check out the archives
(on the left) for more posts. Or just have a look at
the index.
My fiancee, Kelsey, claimed that she could tell the difference between
Coke and Pepsi. I wanted to put this to the test. Since there were
only two of us, arranging the test wasn't a simple matter of asking
someone else to pour some cups. I also wanted to do this right:
testing must
be
double-blind. I devised a little scheme that allowed us to perform
two different tests.
Next, after allowing the foam to calm down (which might accidentally
reveal information to me), Kelsey leaves the room and I enter. I
perform a similar procedure to distribute the drinks into cups #3 and
#4, then #5 and #6. I keep track of what drink, #1 or #2, goes into
what cup. I keep it secret. These last two cups are for the purpose of
the second experiment.
I was at my fiancee's parent's house over Fourth of July weekend. Her
family likes to leave plenty of reading material right by the toilet,
which is something fairly new to me. They take their time on the john
quite seriously.
