This is a continuation of the previous post with details on breaking the cryptosystem in the paper “Design and FPGA Implementation of a Pseudo-Random Bit Sequence Generator Using Spatiotemporal Chaos,” which proposed a hardware-based PRNG 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.
I have had mathematics and computer science education but am not an expert in either chaos theory or cryptology. Nevertheless, breaking a custom cryptosystem like this requires only some basic knowledge and a logical thought process. Cryptography, designing cryptosystems, is best left to the pros. So as promised in the previous post, here is my paper and slides presenting "Chaos, Cryptology, and the Coupled Map Lattice." If you are interested in the cryptosystem break, you may want to skip the details about the lattice behavior in the paper, or just read this summary.
The cryptosystem proposed is really just a pseudorandom number generator (PRNG) since it is based on the one-time pad cryptosystem. The PRNG is seeded with the key. Then the output bits of the PRNG are XOR'd with the plaintext message to encrypt the data. To decrypt the data, the receiver starts the PRNG with the same seed, and XOR's the encrypted data to get back the plaintext. This also means that with a few bytes of known plaintext, we can recover the output of the PRNG.
Obligatory Debian random reference
The PRNG consists of a "coupled logistic map lattice." At each step of the algorithm, it stores 16 32-bit numbers, x1 through x16. It then outputs the least significant 16 bits of each of these numbers interleaved together. (The interleaving does nothing for the security of the system, as it is completely reversible) This also means that with 32 bytes of known plaintext, we can recover the least significant 16 bits of all x's for one step.
To get the next step, each x is replaced by 4 x(1 − x), the logistic map function, and then coupled with the neighboring x's. So for example, x3 = x3/2 + (x2 + x4)/4, or all together with map and coupling, x3 = (4 x3(1 - x3))/2 + (4 x2(1 - x2) + 4 x4(1 - x4))/4. The ends wrap around, so x1 is coupled with x16 and x2, for example.
Coupling
Taking the least significant bits of the x's was a good idea, since we can't use approximate solutions to break the crypto. But this coupling is weak since each x at one step is completely determined by three x's at the previous step. So if we have 64 bits of known plaintext, we know the lower 16 bits of each x for two consecutive steps. We can break apart the encryption, one block of three x's at a time and brute force (48 unknown bits to start, instead of 256 unknown bits). First the cracking algorithm finds all possible upper bits of x1,x2, and x3 that will generate the correct lower 16 bits of x2 for the next step. This takes a long time (O(2^48)) but leaves us with a reduced number of possible triples x1,x2,x3 and doubles x2,x3. We then use the reduced set of doubles x2,x3 to find possible triples x2,x3,x4 that generate the correct lower 16 bits of x3 for the next step and get an even smaller set of possible triples. We then use possibilities for x3 and x4 to find possibilities for x3,x4,x5 that generate the correct least significant 16 bits of x4 in the next step.
Again and again the algorithm narrows down possibilities for the first block, checking them against the next block until only one remains. We now know the complete internal state of the algorithm and can directly generate the rest of the PRNG bitstream and read the rest of the message, or calculate the previous steps and obtain the key.
Since this problem became just out of reach of my personal computer, I used it as an experiment into the idea of distributed computing. I decided to break the program into 10000 parts based on the initial conditions to try. I wrote client programs that would call to a central server to get a portion of the break to execute. The server then handed out a number between 0 and 9999 corresponding to an unfinished piece of work. The client then executed that section, and once results were sent back to the server, the piece was marked as complete. This continued until all possible initial conditions were tried. The clients then cleaned up after themselves and stopped.
Just for full disclosure/clarification, this is a proposed system, that, although it has been cited a number of times, hasn't been implemented in a significant manufactured mobile device to my knowledge. So sorry, it won't hack into your iphone.