Red Pike cipher

[Alfonso De Gregorio]

Le limited information available on the Red Pike cipher are quite
consistent with the code below: an ARX block cipher, no look-up
tables, virtually no key schedule, and requiring only few lines of
code [1].

With a 64 bit key size the Alleged Red Pike (ARP) is insecure by
modern standards. But it was possibly insecure also in the 1990s.

ARP suffers from a large number of semi-weak keys. Actually, each key
is a semi-weak key. A pair of ARP keys (K1, K2) is said to be
semi-weak if E_K1(E_K2(M)) = M (i.e., encryption with K1 operates as
does decryption with K2). With ARP Feistel structure and its key
schedule,there are 2^63 such pairs, reducing the size of the key space
to 2^63.

The relationship between each semi-weak pairs is:

  K2_L = K1_R - 2^32/phi * 17
  K2_R = K1_L + 2^32/phi * 17

where phi is the golden ratio.

Being semi-weak keys a large fraction of the ARP key space,
implementations cannot apply the standard countermeasures against this
undesirable property. Picking a semi-weak key is inevitable.


The question remains: Is the Alleged Red Pike the cipher designed by the GCHQ?


[1] Anderson, Ross; Kuhn, Markus,  "Low Cost Attacks on Tamper
Resistant Devices", in M. Lomas et al. (ed.), Security Protocols, 5th
International Workshop, Paris, France, April 7{9, 1997, Proceedings,
Springer LNCS 1361, pp 125-136, ISBN 3-540-64040-1,
http://www.cl.cam.ac.uk/~rja14/Papers/tamper2.pdf


On Thu, Feb 27, 2014 at 1:08 PM, Anonymous Remailer (austria)
<mixmaster at remailer.privacy.at> wrote:
>
> /* Red Pike cipher source code */
>
> #include <stdint.h>
>
> typedef uint32_t word;
>
> #define CONST 0x9E3779B9
> #define ROUNDS 16
>
> #define ROTL(X, R) (((X) << ((R) & 31)) | ((X) >> (32 - ((R) & 31))))
> #define ROTR(X, R) (((X) >> ((R) & 31)) | ((X) << (32 - ((R) & 31))))
>
> void encrypt(word * x, const word * k)
> {
>   unsigned int i;
>   word rk0 = k[0];
>   word rk1 = k[1];
>
>   for (i = 0; i < ROUNDS; i++)
>   {
>     rk0 += CONST;
>     rk1 -= CONST;
>
>     x[0] ^= rk0;
>     x[0] += x[1];
>     x[0] = ROTL(x[0], x[1]);
>
>     x[1] = ROTR(x[1], x[0]);
>     x[1] -= x[0];
>     x[1] ^= rk1;
>   }
>
>   rk0 = x[0]; x[0] = x[1]; x[1] = rk0;
> }
>
> void decrypt(word * x, const word * k)
> {
>   word dk[2] =
>   {
>     k[1] - CONST * (ROUNDS + 1),
>     k[0] + CONST * (ROUNDS + 1)
>   };
>
>   encrypt(x, dk);
> }
>