[Next] [Up/Previous] [Index]


Panama

Panama is billed as a "cryptographic primitive". Designed by Joan Daemen, also responsible for 3-Way, and one of the collaborators in the design of Rijndael, Panama is essentially a stream cipher engine with a large state. It is, however, equally usable as a hash function.

The structure of a Panama iteration is illustrated by the following diagram:

Panama contains two main elements. A shift register, with 32 cells, each containing a vector with eight 32-bit words, and a recirculating mixing function, resembling the f-function in a block cipher, which operates on a "state" consisting of seventeen 32-bit words. (While it has been noted that SHA-1 inspired Panama, I do not find the resemblance obvious.)

There are three fundamental operations that form part of Panama.

When Panama is used as a stream cipher, first the key is input by one Push operation, and then an initialization vector is input by a second Push operation. Then, 32 Pull operations are performed, discarding their output, to allow the internal state of Panama to be fully mixed.

When Panama is used as a hash function, the message to be hashed, followed by a 1 bit and as many zeroes as are needed to cause the message to occupy an integer number of 256-bit blocks, is input to Panama through a series of Push operations. Then, after a number of Pull operations with their output discarded, so that the effects of even the last block of the message are fully diffused, the output from a final Pull operation constitutes the hash.

The state transition function of Panama operates on 17 32-bit words, numbered 0 through 16. Its steps are visible in the diagram, and are, in order:

The huge size of the internal state of Panama makes it look very impressive. Of course, one might want to add an extra XOR here or there, such as using the state function output during Push cycles. But Panama has been designed to be very efficient on internally parallel microprocessors, and thus throwing in extra operations would interfere with that.


However, a closer look at first creates the impression that Panama might be weak instead of strong. The problem for the cryptanalyst is to discover the internal state of the cipher, both the 17-word state and the shift register contents. But the state is used as the output of the cipher, and the state transition function has only a single round. Thus, knowing two successive 17-word states, one can easily discover the two 8-word inputs to the state transition function.

The only thing that prevents this from happening is that only eight of the seventeen words of the state are used as the output of Panama. At one point, having mistakenly thought that the first eight words of the state, words 0 through 7, were the output block, I worked out a simple way to find the value, with 75% probability, of one of the words in the buffer, but Panama does not in fact allow such a simple attack. Thus, the cryptographic strength of Panama seems to equal that of a two-round version of the state transition function, since just under half the state is used.

However, that attack involves reconstructing the internal state of Panama from known plaintext, which means that, knowing part of a message, one can find the rest of that message. What about attacking other messages with the same key, but a different initialization vector?

Unfortunately, this too is possible. The nonlinearity stage of the state transition function of Panama, resembling as it does the small S-Box of 3-Way, can be inverted (unlike the nonlinear part of the f-function of DES), so it is possible to run Panama backwards if one had a full knowledge of its internal state, and obtain the original 8-word key.


Tracing the path of information through the state transition function of Panama shows that a trivial application of differential cryptanalysis principles does not suffice to obtain some bits of the buffer by means of a known plaintext attack on Panama when used as a stream cipher. The following diagram illustrates what happens when an attack is attempted:

With known plaintext, one knows the value of the output bits from Panama. If one has two successive output blocks from Panama, tracing through the state transition function leads to the following results:

Initially, words 9 through 16 of the state are known.

After the nonlinearity step, words 9 through 14 of the state are still known for certain. The bits of word 15 which correspond to 1 bits in the former value of word 16 are known as well, but the other bits of word 6 are unknown. The bits of word 16 are, with a probability of 75%, the inverses of their former values.

After the bit dispersion step, the words known with certainty are words 2, 4, 9, 11, 14, and 16, and the words about which partial information is available are words 7 and 12. The right words in the right places are not available to allow a known or partly known word to exit the diffusion step for comparison with a word known from the current output block, by which means some buffer contents could be found.

Even so, the fact that it comes this close to solution makes one wary of the danger of a differential attack.

Panama is an impressive and promising design, but because of the superficial appearance that it is close to being susceptible to a differential attack, I have taken the liberty of proposing variant with a few modifications (so don't blame Joan Daemen if, instead of making it more secure, I've ruined it) which is illustrated in the conclusions section of this chapter.


[Next] [Up/Previous] [Index]

Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page