RC4 in Delphi and C?

Question

I've managed to port RC4 implementation from PolarSSL to delphi, since I need an encrypted communication between 2 applications (C and Delphi), but the problem is, the encrypted data is never the same, both codes encrypt and decrypt data on their own successfully but not the data encrypted by the other.

Here are both codes:

C Code (Taken from PolarSSL)

typedef struct
{
    int x;                      /*!< permutation index */
    int y;                      /*!< permutation index */
    unsigned char m[256];       /*!< permutation table */
}
arc4_context;

void arc4_setup(arc4_context *ctx, unsigned char *key, int keylen)
{
    int i, j, k, a;
    ctx->x = 0;
    ctx->y = 0;
    for( i = 0; i < 256; i++ ) ctx->m[i] = (unsigned char) i;
    j = k = 0;
    for( i = 0; i < 256; i++, k++ )
    {
        if( k >= keylen ) k = 0;
        a = ctx->m[i];
        j = ( j + a + key[k] ) & 0xFF;
        ctx->m[i] = ctx->m[j];
        ctx->m[j] = (unsigned char) a;
    }
    return;
}

void arc4_crypt( arc4_context *ctx, unsigned char *buf, int buflen )
{
    int i, x, y, a, b;
    unsigned char m[256];

    x = ctx->x;
    y = ctx->y;

    for (i = 0; i < 256; i++) m[i] = ctx->m[i];
    for( i = 0; i < buflen; i++ )
    {
        x = ( x + 1 ) & 0xFF; a = m[x];
        y = ( y + a ) & 0xFF; b = m[y];

        m[x] = (unsigned char) b;
        m[y] = (unsigned char) a;

        buf[i] = (unsigned char)
            ( buf[i] ^ m[(unsigned char)( a + b )] );
    }
    return;
}

My Delphi Code:

type
  arc4_context = packed record
    x, y: integer;
    m: array[0..255] of byte;
  end;

procedure arc4_setup(var ctx: arc4_context; key: PChar; keylen: Integer);
var
 i, j, k, a: Integer;
begin
 ctx.x := 0;
 ctx.y := 0;
 for i := 0 to 255 do ctx.m[i] := Byte(i);
 j := 0;
 k := 0;
 for i := 0 to 255 do
 begin
   if (k >= keylen) then k := 0;
   a := ctx.m[i];
   j := (j + a + Byte(key[k])) and $FF;
   ctx.m[i] := ctx.m[j];
   ctx.m[j] := a;
   Inc(k);
 end;
end;


procedure arc4_crypt(ctx:arc4_context; var buf:string; buflen:integer);
var
 i, x, y, a, b: Integer;
 m: array [0..255] of byte;
begin
 x := ctx.x;
 y := ctx.y;
 for i := 0 to 255 do m[i] := ctx.m[i];
 i := 0;
 while (i < buflen) do
 begin
  x := (x + 1) and $FF;
  a := m[x];
  y := (y + a) and $FF;
  b := m[y];

  m[x] := b;
  m[y] := a;

  buf[i+1] := Char(Byte(buf[i+1]) xor Byte(m[a + b]));
  inc(i);
 end
end;

Reinertson

That translation looks excellent. What is your question? – Exterior

the Encrypted Data is never the same, so the Data encrypted with the C code cant be decrypted by the Delphi code. – Reinertson

I'm pretty sure there are some array index issues. Are Delphi arrays always zero-based? – Fibula

@entity The arrays in this code are defined to be zero-based. buf is a string which is 1-based. key[i] is a little odd since it uses pointer indexing syntax which I'm not used to, but that too is zero based. I honestly believe that the two codes are equivalent. – Exterior

Seems that ctx.m[j] := a; is not cropped to a byte. You might also want to add explicit cast for m[x] := b; and m[y] := a; – Hallelujah

@too, the compiler handles these conversions fine. – Peevish

There is one more thing, as a + b might exceed the size of buffer, you might want to cast it as well: Byte(m[a + b]) -> Byte(m[Byte(a + b)]) – Hallelujah

@LU RD: I am aware of it, but explicit cast adds a bit of safety for a reader. – Hallelujah

I always wonder why people tend to use "packed" when translating from C headers. There is absolutely no need for it and it is often wrong. – Marmara

@Rudy There is need for it when the C code was compiled with #pragma pack(1), but granted that's rare. In this code it looks like that record is private to the Delphi module in which case it doesn't even matter which order you declare the fields. – Exterior

Do both compilers treat hex constants the same? Do both interpret the FF constant as an 0x00FF integer? – Aniakudo

FWIW, I would make the PChar parameter in the first function, arc4_setup, a PByte, because that is what unsigned char * actually is, and to avoid problems with Unicode. I also wonder why in the second function a while loop was used, instead for for i := 0 to buflen - 1 do. – Marmara

@killer Finally I think I have found the difference between the two codes! – Exterior

Answer 1

I have (finally) found a difference between the two codes.

The following line of the Pascal translation is incorrect:

buf[i+1] := Char(Byte(buf[i+1]) xor Byte(m[a + b]));

The C version reads:

buf[i] = (unsigned char) ( buf[i] ^ m[(unsigned char)( a + b )] );

Note that a + b is truncated into a single unsigned char, whereas the Pascal version above says m[a + b] and so the index of a + b can exceed 255.

You should translate this line as:

buf[i+1] := chr(ord(buf[i+1]) xor ord(m[Byte(a+b)]));

I've changed to use Chr and ord which are cosmetic changes but I feel they are cleaner. The substantive change is in m[Byte(a+b)] where I force the a+b addition to be in the context of a byte data type.

Rather tellingly, this bug results in an out of bounds array access of the array m. If you had been running with range checking enabled, the bug would have been highlighted immediately. I can't stress enough how valuable Delphi's range checking feature is.

Exterior

+1 +10 for persistence and detection! And for stressing the importance of range checking. – Aniakudo

Answer 2

A suggestion: look at the contents of the m[] arrays on both systems after you have processed the key but before you have encrypted any data. Obviously the two should be identical. If not then the problem lies in the key processing.

You might also want to XOR the two differing outputs to see if any pattern emerges that might point you to the problem.

Kelcey

Answer 3

Here is a delphi implementation of the algorithm, translated from .Net:

unit uRC4;

interface

uses Windows;

type
  TuRC4 = class
    public
      class function RC4(data, key:string):string;
  end;

implementation

class function TuRC4.RC4(data, key:string):string;
var
  x, y, j: Integer;
  box: array[0..255] of Integer;
  i: Integer;
  s: String;

begin
    for i := 0 to 255 do
      begin
        box[i] := i;
      end;

    for i := 0 to 255 do
      begin
        j := (Ord(key[i Mod Length(key) + 1]) + box[i] + j) Mod 256;
        x := box[i];
        box[i] := box[j];
        box[j] := x;
      end;

    for i := 0 to Length(data)-1 do
      begin
        y := i Mod 256;
        j := (box[y] + j) Mod 256;
        x := box[y];
        box[y] := box[j];
        box[j] := x;
        s := Char(Ord(data[i + 1]) xor box[(box[y] + box[j]) Mod 256]);
        Result := Concat(Result, s);
      end;
end;

end.

Ojeda

Answer 4

Why reinvent the wheel?*

I know that DCPCrypt supports RC4.

*) allowed for academic purposes

Edit removed.

Centralization