Difficulties translating XTea encryption to Pascal

[Robert Kosek]

For a simple overview and pseudocode on XTea, you can wiki-it.

XTea is supposed to be a simple encryption algorithm, and it is mathematically. But my implementation is going wrong somewhere in the encryption and possibly decryption phases. Very wrong. Like it could simply crash silently on me, or the encryption "halts" part way through. It seems to be something in relation to password length and content length. It might work with a 16 character password, and a short paragraph, but change either around and it'll go screwy in no time flat!

As you can guess it's got me fairly confused. ops: I have to thank Lifepower a lot just for helping me this far along! Any further help from ya'll will really be appreciated. I'll be trying to juggle the discussion here and at Afterwarp, so just know that unless you check the thread there, you might not be up to date on the problem.

Here's the source. To use it just make a TXTea object, create it, Init the key, Encrypt/Decrypt then burn it.

(******************************************************************************)
(*  Translated from C into Object Pascal by Robert Kosek with much help from  *)
(*  Yuriy Kotsarenko. Please leave this header in any subsequent distribution *)
(*  and maybe mention us in the credits of whatever uses this.  Especially    *)
(*  Yuriy, he did the majority of the work in the end. ;-)                    *)
(*                                                                            *)
(*  My only stipulation to this is that if you use it, adapt it or change it, *)
(*  please let us know and post your changes here:                            *)
(*    http://www.afterwarp.net/forum/thread460.html                           *)
(******************************************************************************)
(*  Original code taken from:                                                 *)
(*    http://en.wikipedia.org/wiki/XTEA                                       *)
(*    http://www.irnis.net/soft/xted/                                         *)
(*                                                                            *)
(*  Our Sites:                                                                *)
(*    http://afterwarp.net/                                                   *)
(*    http://thewickedflea.com/                                               *)
(******************************************************************************)
unit xtea;

interface

uses SysUtils;

type
  PKey128 = ^TKey128;
  TKey128 = array [0..3] of longword;
  
  PBlock64 = ^TBlock64;
  TBlock64 = array [0..1] of longword;

  TXTea = class(TObject)
  private
    FKey: TKey128;
    FInitialized: Boolean;
  public
    property Initialized: boolean read FInitialized default false;
    procedure Burn;
    procedure InitKey(const Key: string);
    function Encrypt(const Input: string): string;
    function Decrypt(const Input: string): string;
    destructor Destroy; override;
    constructor Create;
  end;

const
  DELTA = $9e3779b9;
  XTEA_BLANK: TBlock64 = (0,0);
  XTEA_BURN: TKey128 =(0,0,0,0);

implementation

destructor TXTea.Destroy;
begin
  Burn;
  inherited Destroy;
end;

constructor TXTea.Create;
begin
  inherited Create;
  Burn;
end;

procedure TXTea.Burn;
begin
  FKey := XTEA_BURN;
  FInitialized := False;
end;

procedure TXTea.InitKey(const Key: string);
var L: integer;
begin
  if Length&#40;Key&#41; <= SizeOf&#40;FKey&#41; then
    L &#58;= Length&#40;Key&#41;
  else
    L &#58;= SizeOf&#40;FKey&#41;;

  Move&#40;Key&#91;1&#93;,FKey&#91;0&#93;,L&#41;;
  
  FInitialized &#58;= True;
end;

function TXTea.Encrypt&#40;const Input&#58; string&#41;&#58; string;
var i,l,n,b&#58; integer;
    v&#58; TBlock64;

  procedure CipherXTea&#40;v&#58; PBlock64; key&#58; PKey128&#41;;
  var sum&#58; longword;
      i&#58; integer;
  begin
    Sum&#58;= 0;

    for i&#58;= 0 to 31 do
    begin
     Inc&#40;v&#91;0&#93;, &#40;&#40;v&#91;1&#93; shl 4 xor v&#91;1&#93; shr 5&#41; + v&#91;1&#93;&#41; xor &#40;Sum + Key&#91;Sum and 3&#93;&#41;&#41;;
     Inc&#40;Sum, Delta&#41;;
     Inc&#40;v&#91;1&#93;, &#40;&#40;v&#91;0&#93; shl 4 xor v&#91;0&#93; shr 5&#41; + v&#91;0&#93;&#41; xor &#40;Sum + Key&#91;Sum shr 11 and 3&#93;&#41;&#41;;
    end;
  end;
begin
  if not Initialized then
    raise Exception.Create&#40;'Error&#58; You must define a password.'&#41;;

  b &#58;= SizeOf&#40;v&#41;;
  l &#58;= Length&#40;Input&#41;;
  SetLength&#40;Result,l&#41;;

  i &#58;= 1;
  while i < l do
    try
      v &#58;= XTEA_BLANK;
      n &#58;= l - &#40;i-1&#41;;

      if n > b then
        Move&#40;Input&#91;i&#93;,v&#91;0&#93;,b&#41;
      else
        Move&#40;Input&#91;i&#93;,v&#91;0&#93;,n&#41;;

      CipherXTea&#40;@v,@FKey&#41;;

      Move&#40;v&#91;0&#93;,Result&#91;i&#93;,b&#41;;
      inc&#40;i,8&#41;;
     except
       raise;
     end;
end;

function TXTea.Decrypt&#40;const Input&#58; string&#41;&#58; string;
var i,l,n,b&#58; integer;
    v&#58; TBlock64;

  procedure DecipherXTea&#40;v&#58; PBlock64; Key&#58; PKey128&#41;;
  var
     i&#58; Integer;
     Sum&#58; Longword;
  begin
    Sum&#58;= $C6EF3720;

    for i&#58;= 0 to 31 do
    begin
      Dec&#40;v&#91;1&#93;, &#40;&#40;v&#91;0&#93; shl 4 xor v&#91;0&#93; shr 5&#41; + v&#91;0&#93;&#41; xor &#40;Sum + Key&#91;Sum shr 11 and 3&#93;&#41;&#41;;
      Dec&#40;Sum, Delta&#41;;
      Dec&#40;v&#91;0&#93;, &#40;&#40;v&#91;1&#93; shl 4 xor v&#91;1&#93; shr 5&#41; + v&#91;1&#93;&#41; xor &#40;Sum + Key&#91;Sum and 3&#93;&#41;&#41;;
    end;
  end;
begin
  if not Initialized then
    raise Exception.Create&#40;'Error&#58; You must define a password.'&#41;;

  b &#58;= SizeOf&#40;v&#41;;
  l &#58;= Length&#40;Input&#41;;
  SetLength&#40;Result,l&#41;;

  i &#58;= 1;
  while i < l do
    try
      v &#58;= XTEA_BLANK;
      n &#58;= l - &#40;i-1&#41;;

      if n > b then
        Move&#40;Input&#91;i&#93;,v&#91;0&#93;,b&#41;
      else
        Move&#40;Input&#91;i&#93;,v&#91;0&#93;,n&#41;;

      DecipherXTea&#40;@v,@FKey&#41;;

      Move&#40;v&#91;0&#93;,Result&#91;i&#93;,b&#41;;
      inc&#40;i,8&#41;;
    except
      raise;  
    end;
end;

end.

[Sly]

From a brief look over both your code and Lifepower's, I have these comments.

In your Encrypt and Decrypt methods, you are setting Result to the length of the input string, but inside the loop you overflow the buffer allocated for Result in the last call to Move by up to seven bytes (your last Move is always the size of TBlock64). What you should do is set the length of Result to be the next highest multiple of eight over the length of Input. This is easily achieved with the following

l := (Length(Input) + 7) and (not 7);
SetLength(Result, l);

Edit: Incidentally, the Pascal code linked from that Wiki page does the same thing (in a different way). I'm not sure why you didn't use that code in the first place.

Lifepower's latest version makes a few assumptions about the strings which is why it does not work with ansi or wide strings.

This line

 // Step 3. Encrypt source string.
 Move(Source, Result, Length(Source) + 1);

is not the correct way to copy a string. This is the primary reason why this routine will not work with ansi or wide strings. Using Result := Source will not work with ansi or wide strings either, because you want Result to be a unique copy of Source (because the Result copy gets modified). Hence you should use a function that generates a unique copy of the string. I believe there is a UniqueStr() function in the RTL or something similar.

In CipherDataXTEA, the loop will not execute at all for strings with less than 8 characters. It will also not encrypt any remaining bytes after the last eight-byte block. The same goes for DecipherDataXTEA.

Also, and this might affect both, I believe that the C >> operator is a logical shift (bits fall off the end) and the Delphi shr operator is an arithmetic shift (bits wrap around). I seem to remember we found this when porting Quake 2 to Delphi.

[Robert Kosek]

Thanks very much, you've helped me quite a bit. I did not want to use the linked unit because it was really messy and confusing, on top of being non-standard for the encryption. It's not true XTea, but some kind of variant. You can compare the math to the main code on the Wiki page.

I have one question though, and it's really puzzling me. I take and encrypt a block of text bigger than 256 in length, such as your post, and just encrypt with "0123456789abcdef" and the text gets garbled something odd in the middle of the decryption. The encryption stops somewhere in the middle, then during decryption the very last 8 character block is not decrypted. Like so:

Start:

is not the correct way to copy a string. This is the primary reason why this routine will not work with ansi or wide strings. Using Result := Source will not work with ansi or wide strings either, because you want Result to be a unique copy of Source (because the Result copy gets modified). Hence you should use a function that generates a unique copy of the string. I believe there is a UniqueStr() function in the RTL or something similar.

In CipherDataXTEA, the loop will not execute at all for strings with less than 8 characters. It will also not encrypt any remaining bytes after the last eight-byte block. The same goes for DecipherDataXTEA.

Also, and this might affect both, I believe that the C >> operator is a logical shift (bits fall off the end) and the Delphi shr operator is an arithmetic shift (bits wrap around). I seem to remember we found this when porting Quake 2 to Delphi.

Encrypted:

Àú¬æ?ª{?î?? uqo-?é+L‚Äú?ü?±?üBd
I?Ǭºu¬¨V‚ÄôS?éol&?õ¬æ?ïM?å¬?¬æ/b¬±¬êo¬¨‚Ä¢N.\r07‚Äò1S¬§¬æ?ìa?•Ç ?ø[?ß?µ?¢?Ç?æt!‚Ćb¬®‚Ä°Àú^M¬??í(¬±?î??LH¬??ìÀú6KGÀ ܬÅ7?Ä?£¬æ‚Äô?°RaN¬±‚Ä°T>h¬±?ä?º?£?ɂĢ?ë?û‚Ǩ?Ü?ü‚ÄìOKJ?ØR¬£‚Ä°Àú^M¬??í(¬±?î??LH¬ ??ìÀú6KGÀܬÅ7?Ä?£¬æ‚Äô?°Ra e0¬ê¬??º?ë?™$?ëy‚Äì2¬¨¬çg?ô?¨?™?ɂ݂Ģ?â¬?E¬£+ ‚ÄòE‚Ä?Pu?¥d‚Äî
s_EL¬®?ø??¬µ?æd¬øz?ç[¬µ¬Åd‚Ñ¢l¬?P
?ñ¬º¬¨+P¬?+,?µ?í‚Ǩa?í?á2&}1‚Ä??± ?㬵r¬?5c??¬?¬?m82¬??å?ûf?ä‚Äî#??W:?í'-¬±l=¬è?ô?î?ê‚Äù?ô¬•c??li¬?9?ô(?Ü,a?®M¬?*¬??º!3‚Ä°?Ü<6Vui"?åG?• ??¬µ?æd¬øz?ç[?úK6??~?£?®‚Äî?¨?嬮¬èf2nO?Ä??.YR9|??g>+?° ?•)?í?ç{?ø¬?¬?=nY?Ƭ±??xc?éCJ!N¬±?†(¬º&?}?â?¨?æ? ±‚Äú?ÇEE #

Decrypted:

is not the correct way to copy a string. This is the primary reason why this routine will not work with ansi or wide strings. Using Result := Source will not work with ansi or wide strings either, because you want Result to be a unique copy of Source (because the Result copy gets modified). Hence you should use a function that generates a unique copy of the string. I believe there is a UniqueStr() function in the RTL or
‚Äù¬?¬°?®??

What might be going on here? I really don't get how that thing could happen. Even with the length change you gave me, which slightly helped, the algorithm is not working right. Even odder is that with the same password and longer text, the result sometimes is a cryptic 2 characters. I don't even know what they were. An attempt at decryption results in a crash, as you'd expect.

In the loop should I use the n/b comparison to assign to a temporary value for the 2 Move calls and the ending increment? Would that help, perhaps?

[Sly]

Sorry I haven't got back to you on this. I have had a quick look at it under the Delphi 2005 debugger (I every time I use the Delphi debugger reminds me just how brilliant the VS debugger is) and I haven't come up with anything yet.

[User137]

lol, after lots of various testing here comes my conclusion... The text happens to have a block that encrypts into somekind of ending character that simply refuses to print any more characters after it :twisted: And with all certainty i found out that is chr(0). So.. if string is not allowed to contain #0 in between text you need an alternate type for storing the encrypted data.

[Sly]

I had thought about that, and had wondered if XTEA had the trait of not producing any NUL bytes in the output. Apparently not.

[Robert Kosek]

Hmm, I see how that is a problem. Is there a possible way to fix or work around this? I am curious about it. Perhaps an array of bytes would be better for encryption/decryption, seeing that a 0 byte is valid. :?

[Sly]

You could input a string to encrypt and get a block of bytes back, then pass the block of bytes in to decrypt and get a string back. That should work.

[Robert Kosek]

True.

It should work dandy as-is for stream/binary encryption though. Perhaps an XOR of byte 1 would alleviate the problem with strings?

[Sly]

Then might turn a $01 into a $00.

The essence of it is that the encrypted data should never be passed around as a string.