Panama Stream cipher

Introduction:
Panama is a cryptography primitive which can be used both as a hash function and a stream cipher. Based on StepRightUp, it was designed by Joan Daemen and Craig Clapp and presented in the paper Fast Hashing and Stream Encryption with PANAMA on the Fast Software Encryption (FSE) conference 1998. The cipher has influenced several other designs, for example MUGI.
The primitive can be used both as a hash function and a stream cipher. The stream cipher uses a 256-bit key and the performance of the cipher is very good reaching 2 cycles per byte.
As a hash function, collisions have been shown by Vincent Rijmen et al. in the paper Producing Collisions for PANAMA presented at FSE 2001. The attack shows a computational complexity of 2^82 and with negligible memory requirements.
At FSE 2007, Joan Daemen and Gilles Van Assche presented a practical attack on the Panama hash function that generates a collision in 2^6 evaluations of the state updating function.
Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche proposed, at NIST's 2006 Second Cryptographic Hash Workshop, unveiled a Panama variant called RadioGatún. RadioGatún is strictly a hash function; it does not have the known weaknesses that Panama's hash function has.


Structure of Panama

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:

• Panama is reset by setting both the 17-word state and the contents of the shift register to all zeroes.
• A vector of eight 32-bit words is fed to Panama through a Push operation. Operations unique to the Push function are shown by the light dotted lines in the diagram. In a Push operation, the incoming vector is used as one of the inputs to the state transition function (the other input is the contents of one of the cells in the shift register), and is also used to XOR with the recirculating values in the shift register.
• A vector of eight 32-bit words is recieved from Panama by means of a Pull operation. The line of alternating dots and dashes shows the operations unique to the Pull function in the diagram. In a Pull operation, the 32-bit words numbered 9 through 16 in the state are used as the output, and words 1 through 8 are XORed with the recirculating values in the shift register. The inputs to the state transition function both come from stages in the shift register, one not used for any special purpose in the Push operation replacing the input, absent from a Pull operation.

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:

• Nonlinearity: each word is XORed with the OR of the previous values of the next word and the complement of the word after, going around the circle from word 0 to 16 and back to 0.
• Bit Dispersion: first, the words are transposed (by a simple decimation with interval 4), then the words undergo circular left shifts of different sizes.
• Diffusion: each word is XORed with both the previous values of the next word and the word four positions ahead, again going around the circle.
• Buffer Injection: Word 0 is XORed with 1; words 1 through 8 are XORed with the first input to the function, and words 9 through 16 are XORed with the second input to the function.

The Panama Stream Encryption Scheme
The stream cipher is initialized by first loading the 256-bit key K, the 256-bit diversification parameter Q, and performing 32 additional blank Pull iterations. During key-stream generation, an eight-word block z is delivered at the output for every iteration. In practice, the diversification parameter allows for frequent resynchronization without the need to change the key.

Vulnerabilities
The first thing to note is that the presence of the blank rounds makes it hard
to produce a collision in the digest if there is a difference in either the state or
the buffer after all the message blocks are input. Due to the invertibility of the
state updating function such a difference will not cancel out. Moreover, the lack
of external input and the propagation properties of the state updating function
give the attacker almost no control over the final difference. Therefore, our goal is to produce a collision in both the state and the buffer before the blank rounds.
We produce a collision by following a trail. Two instances of Panama process
two different messages (p and p + dp), which have a given difference (dp). The
trail also specifies the differences in the state (da) and in the buffer (db) between the two instances of Panama, at each round. So, not only the two messages must have the given difference, they must also produce the right difference in the state and in the buffer.
We shall now describe the general structure of the trail used in the scope of
this article. We will first talk about the sequence of message differences, then
about the differences in the state.
In the sequel, the round numbers are specified between brackets in super-
script: ·(i) . The convention is that p(i) is the message block processed during
round i, and a(i) is the value of the state after round i.



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.



References:
http://en.wikipedia.org/wiki/Panama_(cryptography)
http://www.quadibloc.com/crypto/co4821.htm
http://www.cosic.esat.kuleuven.be/publications/article-81.pdf