Christopher Wellons
mosquitopsu@gmail.com
Public GPG Key
Post Index - see a list of all of the entries.
I am a computer engineer working at the Johns Hopkins University Applied Physics Laboratory. I love computers and free software.
Most of the topics you will find here are about hobby computing and programming with free software (and a few exceptions).
E-mail me: mosquitopsu@gmail.com
Projects:
- Brainfuck Compiler
- PNG Archiver
- BINI Tools
-
Parallel Mandelbrot Generator
Archives:
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
June 2008
July 2008
August 2008
At work they recently moved me to a new project. It is a Matlab-based data analysis thing. I haven't really touched Matlab in over a year (the last time I used Matlab at work), and, instead, use GNU Octave at home when the language is appropriate. I got so used to Octave that I found a pretty critical feature missing from Matlab's implementation: treat an expression as if it were of the type of its output.
Let's say we want to index into the result of a function. Take, for
example, the magic square function, magic(). This spits
out a
magic square
of the given size. In Octave we can generate a 4x4 magic square and
chop out the middle 2x2 portion in one line.
RSS Feed
octave> magic(4)(2:3,2:3)
ans =
11 10
7 6
Or more possibly clearly,
octave> [magic(4)](2:3,2:3)
ans =
11 10
7 6
Try this in Matlab and you will get a big, fat error. You have to assign the magic square to a temporary variable to do the same thing. I kept trying to do this sort of thing in Matlab and was thinking to myself, "I know I can do this somehow!". Nope, I was just used to having Octave.
Where this really shows is when you want to reshape a matrix into a
nice, simple vector. If you have a matrix M and want to
count the number of NaN's it has, you can't just apply
the sum() function over isnan() because it
only does sums of columns. You can get around this with a special
index, (:).
So, to sum all elements in M directly,
octave> sum(M(:))
In Octave, to count NaN's with isnan(),
octave> sum(isnan(M)(:))
Again, Matlab won't let you index the result of isnan()
directly. Stupid. I guess the Matlab way to do this is to
apply sum() twice.
Every language I can think of handles this properly. C, C++, Perl, Ruby, etc. It is strange that Matlab itself doesn't have it. Score one more for Octave.
Stream ciphers are one of the two types of symmetric key algorithms, which is when the same key is used for encryption and decryption. They follow this simple concept: take a good pseudo-random number generator and combine, usually by XOR, its output with your plaintext stream. This is very similiar to the one-time pad, but the random pad is pseudo-random rather than truly random. The key is the seed (or part of one) for the PRNG.
Probably the most well known stream cipher is the extremely simple, yet cryptographically strong, Arcfour algorithm. The official name is actually RC4, which comes from RSA Security where it was developed. It was a trade secret until someone anonymously leaked the algorithm to the public. The name RC4 is still trademarked, though, so Arcfour is generally used instead, meaning "Alleged RC4" (alleged because RSA Security never confirmed the algorithm as being RC4). You have almost certainly used the cipher yourself, because it is used in applications such as WEP and SSL.
The algorithm has two parts: the key schedule algorithm and pseudo-random generation algorithm. The key schedule uses the key, and possible a non-secret initialization vector, to set up the state of the PRNG. The state is an array of length 256 holding all of the values from 0 to 255 in some order, along with two integers (initialized to 0 after the key schedule). The algorithm looks like this,
for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap(S[i],S[j])
endfor
The PRNG deals with one byte at a time, emitting a stream of bytes,
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(S[i],S[j])
output S[(S[i] + S[j]) mod 256]
endwhile
If you implement this in C and use the char type, you can
toss the modulus parts because they will just work automatically.
Now you just XOR your message with the output of the PRNG. The Wikipedia article probably explains it better than I can, so check it out if you still don't follow.
Now, Arcfour has some flaws. Specifically, the algorithm itself
doesn't specify how an initialization vector is applied, which is
important. Using a plan key twice is bad it allows an adversary to get
information easily. For example, Lets say you have two
messages A and B. You use the same
key k, which will produce the same keystream K. Now, you
create your two ciphertexts CA
and CB
CA= A ^ KCB= B ^ K
But notice if the adversary has both ciphertexts,
CA^CB= A ^ K ^ B ^ K = A ^ B
They are left with your two original messages XORed together. Let me illustrate: we have two messages as bitmap images (here as PNGs for the web),
Encrypt them using the same key. In this case, my key was "somekey".
If the adversary has both of these second "images", she can XOR them together (having no knowledge of the key!) and get this,
An initialization vector (IV) is a set of bytes we combine with the key. The IV is not a secret, as it is sent plaintext with the ciphertext. If different IVs were used above with the same key, XORing the ciphertext would result in nothing, because the keystreams are totally different for each message.
However, the way the IV is combined is important too. Simply concatenating the IV and the key can lead to weaknesses due to the way the key schedule algorithm works. Something more secure would be a cryptographic hash of the key and the IV. The reason WEP is broken is because in its design the IV wasn't used properly.
Another weakness is that the initial bytes of the keystream have low entropy. That is, some bits tend to be 0's or 1's consistently, which can leak information to an adversary. This can be countered by tossing the first few bytes of the keystream. Often the first 768 bytes are dropped, but a conservative amount would be 3072 bytes. Another way to deal with this is running the key schedule algorithm 10 or 20 times (not reinitializing the S array between them of course) rather than just once, which is the way CipherSaber-2 does it.
Yet another weakness is that the keystream becomes distinguishable from random data after about a gigabyte of output. That is, after about a gigabyte, the entropy of the overall stream can become too low and compromise the security of the message. A solution might be to change the IV each gigabyte.
I wrote an implementation of Arcfour in C, which you can get from my Git repostiory with,
git clone http://git.nullprogram.com/arcfour.git
Or grab a snapshot.
It is written as a library that can be used in different applications. Included are a couple programs that make use of it. I strongly suggest writing your own implementation. It is really easy to do, and you will automatically have the algorithm memorized once you do it. The Wikipedia article has some test vectors you can use to test it.
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,
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.
char worst_case[9][9] =
{
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 3, 0, 8, 5},
{0, 0, 1, 0, 2, 0, 0, 0, 0},
{0, 0, 0, 5, 0, 7, 0, 0, 0},
{0, 0, 4, 0, 0, 0, 1, 0, 0},
{0, 9, 0, 0, 0, 0, 0, 0, 0},
{5, 0, 0, 0, 0, 0, 0, 7, 3},
{0, 0, 2, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 0, 0, 0, 9}
};
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.
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).
Get it: random.data (207kB). It looks kind of like this (hexdump),
f0a0 382b fdaf 6dff 5f15 0f2a 4634 f1c9 bf36 67f3 b896 7237 ac82 836b c906 e28f 2cea 8f06 b6a5 56f9 1faa 6dcb 06e6 f1e2 779f 728e ead1 b5ad fbb3 e615 9906 2006 f245 db61 8231 a2b7 2b10 37bb 5e48 8970 49b7 0856 c0e3 440f fde4 9e78 7384 3f5f 05c5 fed9 1c6e e5ac b85d cc7e fd20 a280 1688 3206 ddb5 5c47 9dfe df53 18ea df52 9b95 7e6b b76e c6c7 061c 43b8 f4f7 b3e3 4948 e543 d8f1 476d 0daf 400f d345 60f4 [...]
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).
# encrypt otp /dev/random random.pad < otp.c > otp.c.otp # decrypt otp random.pad < otp.c.opt > otp.c
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.
Copyright © 2008 Chris Wellons (mosquitopsu@gmail.com)
Copying, modification, and distribution of this page is permitted worldwide, without royalty, in any medium, provided this notice is preserved.
All source code displayed inline on this page is licensed under this BSD-style license.