Cryptology, Academics, and Chaos

I saw an article the other day critical of the ACM (here also see this linked to in comments) and I have to say, I completely agree. As far as I can tell, the ACM, like the IEEE and other publishing houses, exists to leech off of the academic world, charging large amounts of money to view papers that their authors contribute for free. For example, for a research project I did in college, I was looking for papers on chaos theory. I had access to some publications, but not others. A typical paper may cite 20 different other articles, and I would have liked to look through many more to find useful research. Many papers reveal minor properties of a system in passing, and thus not in the abstract. But I was not going to pay $15-$30 each to read a paper that most likely doesn’t help my research. Instead I ended up looking at a published IEEE paper that someone had uploaded to a public website outside of the IEEE publications.

The paper, from the Nanjing University of Sci. & Tech. and the Nanjing University of Aviation & Astronautics in Nanjing, China, was titled “Design and FPGA Implementation of a Pseudo-Random Bit Sequence Generator Using Spatiotemporal Chaos.” It proposed a hardware-based PRBSG* using a chaotic** function as the basis of a cryptosystem inspired by the one-time pad. It proposed the system as an encryption device suitable for cell phones or PDA’s, along with a hardware implementation realized in an FPGA.

After analyzing the system, it became clear that one of the key points of the generation scheme (interleaving) made no sense and did basically nothing. Even apart from that issue, I discovered that although the generated bits pass basic statistical tests, they are too weak for use as a cryptographically secure PRBSG. Even without knowledge of 256 bits of internal state, with only 64 or 96 bytes of known plaintext, an attacker can break the system. I even wrote a complete distributed cracking system, and broke the encryption finding the key on a distributed cluster of commodity PCs. I will post more technical details along with my paper and slides explaining the system and the break in my next post.

Not only was the system vastly weaker than other cryptosystems, after performing more numerical experiments on the underlying system, I discovered that it was surprisingly not chaotic! After generating a few megabytes of pseudorandom data, the system began to approach equilibrium and generate a block of very similar 64 bytes again and again instead of continuing to generate random-looking bits. Apparently the authors did not verify the core assumptions of the paper.

And now I ask, supposing I had paid to obtain this paper, what exactly did the IEEE provide me for my money? The answer traditionally given is the reliability provided by peer review. In reality, almost everything the paper presents is false. I cannot believe any decent cryptologist signed off on this paper, and no chaos theorist has provided a theoretical basis for the “chaotic” system since there is none.

I thought about trying to get my paper refuting the orignal paper published in an IEEE journal or conference, but I was unable to reach the conference or to access any of the hundreds of journals. I could not look at other articles to see which journal would be most appropriate to submit to or see the accepted writing style to know how to rewrite my paper to aim at the journal instead of a collegiate audience. Eventually I got disgusted with the process, and I will release it here in my next post outside of the publishing houses freely available to all.

In case anyone comes to the defense of the IEEE/ACM crowd and insists the charges to get, for example, this conference paper are necessary, I point you to the Black Hat conference I recently presented at. The organization profits from selling expensive tickets, the standards for publication are high, and yet, mere hours after the event is over, the papers and presentations are available for free to all on the Black Hat website.

If you are in the academic club and are a member of the IEEE or ACM, see if you can get the behavior changed. Or at least put your own papers on your own websites to be available to others.

*Pseudo-Random Bit Sequence Generator, fancy precise mathematical term for what computer scientists usually refer to as a pseudorandom number generator or PRNG.

**Basic definition from Wikipedia: “Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions; an effect which is popularly referred to as the butterfly effect. Small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes for chaotic systems, rendering long-term prediction impossible in general. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved. In other words, the deterministic nature of these systems does not make them predictable.”


, , , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: