Tiny Encryption Algorithm (TEA).
I had fun this weekend. Some time passed since I coded (or better said modified) some low level code like this. I mean really low level, not Win32 API. And encryption in its true form is low level coding (and much more than just coding behind the screen).
The initial problem that led to me to this task, was the need for an encryption algorithm that would work in all Delphi versions I use. BDS 2006 Win32, BDS 2006 .NET, BDS 2006 .NET Compact Framework and RAD 2010. I maintain an application written under BDS 2006 .NET for compact framework. It works just fine, but the users wanted some new features for it. And one of the features was data encryption, so the data would be safe if somebody stole the PDA. Initial search for CF compatible code revealed a CryptoAPI wrrapper. While it worked just fine, it had some problems. I had no desire to play with the C# code. I do not have the environment set up to compile and build it. And the second more serious problem was, that this worked under CF, but not under Win32 (it workes under Win32, .NET and .NET CF as pointed out). My plan was to always have the data encrypted outside the application. So when data is stored on the PDA, it is encrypted and when it is read by the application, it is decrypted. The application communicates with a central server and sends data to the server now and then. The server is written in Delphi Win32. I had two ways to solve this problem:
- Before sending the data, decrypt it to some temp path, then send it decrypted and delete it afterward.
- Send the data encrypted and decrypt it on the server side.
I did not like the first approach as the data would be temporarily visible (and would be transferred in plain HTTP over the GPRS). So I opted for second approach. This way I would have to use an algorithm, that would give the same results on all platforms. After some digging around I found a perfect candidate. XTEA is an improved TEA (Tiny Encryption Algorithm) and is very easy to implement and hard enough to break. I looked for solution that has reasonable strength but does not need to be unbreakable. Also the algorithm is very fast and has small memory footprint and that is another bonus on the PDA devices. Happy with this I looked if there already was a Delphi implementation of the algorithm. And I found one such implementation.
It looked promising, no pointers (good for .NET) and simple implementation. So I took this as a base and modified it to work under .NET and CF. I also made it Unicode and Ansi compatible. Yes, encryption is meant to work on raw data not strings, but the reality is that we often have to encrypt strings, text and other similar data that is sensitive to encoding. Doing this I had to think about the correct approach to Unicode handling. If something is encoded as a string under Unicode enabled compiler the I expect the same result on the other side that is Ansi enabled. If I encode something under Delphi 2010 I want the same result under Delphi 2006 and vice verse. Naturally if I encode Chinese text I cannot represent it in the same way on the other side, but that is obvious (unless I use WideStrings). I took the following solution to which I will stick until somebody proves me wrong or I find a better one:
function XTeaEncryptStr(const Data, Key: string): AnsiString; function XTeaDecryptStr(const Data: AnsiString; const Key: string): string;
The idea is that input Data for encryption should always be declared as string (for string encryption that is). We should always get back the AnsiString as this is the actual representation of the encrypted data as bytes. It has no meaning at all. On the other hand decryption is symmetric. It takes AnsiString and returns a string. Key to this is that internally we do UTF8 encoding / decoding (not blind AnsiString casting). This way we will get the same byte representation internally, no matter if we have Delphi 2006 or 2010. Yes not for Chinese characters because we cannot represent them with AnsiString.
All that said, wrapping encryption / decryption should look like this:
function XTeaDecryptStr(const Data: AnsiString; const Key: string): string; var KeyBuf: TTeaKey; DataBuf: TTeaData; ResultAsUTF8: AnsiString; begin StrToKey(Utf8Encode(Key), KeyBuf); StrToData(Data, DataBuf); XXTeaDecrypt(DataBuf, KeyBuf); DataToStr(ResultAsUTF8, DataBuf); {$IFDEF UNICODE} Result := UTF8ToString(ResultAsUTF8) {$ELSE} Result := UTF8Decode(ResultAsUTF8); {$ENDIF} end; function XTeaEncryptBytes(const Data: TTeaBytes; const Key: string): TTeaBytes; var KeyBuf: TTeaKey; DataBuf: TTeaData; begin StrToKey(Utf8Encode(Key), KeyBuf); BytesToData(Data, DataBuf); XXTeaEncrypt(DataBuf, KeyBuf); DataToBytes(Result, DataBuf); end; function XTeaDecryptBytes(const Data: TTeaBytes; const Key: string): TTeaBytes; var KeyBuf: TTeaKey; DataBuf: TTeaData; begin StrToKey(Utf8Encode(Key), KeyBuf); BytesToData(Data, DataBuf); XXTeaDecrypt(DataBuf, KeyBuf); DataToBytes(Result, DataBuf); end;
I also included the raw byte counterparts to be complete. Now all that is left to show is the reminder of the XTEA algorithm:
type TLong2 = array[0.. 1] of Longword; // 64-bit TTeaKey = array[0..3] of Longword; // 128-bit TByte16 = array[0..15] of Byte; // 128-bit TByte4 = array[0..3] of Byte; // 32-bit TTeaData = array of TLong2; // n*64-bit TTeaBytes = array of Byte; // byte array const cTeaBlockSize = 4; function CardinalToBytes(const Data: Cardinal): TByte4; begin {$IFDEF CLR} Result := BitConverter.GetBytes(Data); {$ELSE} Result := TByte4(Data); {$ENDIF} end; function BytesToCardinal(const Data: TByte4): Cardinal; begin {$IFDEF CLR} Result := BitConverter.ToUInt32(Data, 0); {$ELSE} Result := Cardinal(Data); {$ENDIF} end; {$OVERFLOWCHECKS OFF} procedure XTeaEncrypt(var Data: TLong2; const Key: TTeaKey; N: Longword = 32); var y,z,sum,limit: Longword; begin limit := Delta * N; y := Data[0]; z := Data[1]; sum := 0; while sum <> limit do begin Inc(y, (((z shl 4) xor (z shr 5)) + z) xor (sum + Key[sum and 3])); Inc(sum, Delta); Inc(z, (((y shl 4) xor (y shr 5)) + y) xor (sum + Key[(sum shr 11) and 3])); end; Data[0] := y; Data[1] := z end; procedure XTeaDecrypt(var Data: TLong2; const Key: TTeaKey; N: Longword = 32); var y,z,sum: Longword; begin y := Data[0]; z := Data[1]; sum:= Delta * N; while sum <> 0 do begin Dec(z, (((y shl 4) xor (y shr 5)) + y) xor (sum + key[(sum shr 11) and 3])); Dec(sum, Delta); Dec(y, (((z shl 4) xor (z shr 5)) + z) xor (sum + key[sum and 3])); end; Data[0] := y; Data[1] := z end; procedure XXTeaEncrypt(var Data: TTeaData; const Key: TTeaKey); var I: Integer; begin for I := 0 to Length(Data) - 1 do XTeaEncrypt(Data[I], Key); end; procedure XXTeaDecrypt(var Data: TTeaData; const Key: TTeaKey); var I: Integer; begin for I := 0 to Length(Data) - 1 do XTeaDecrypt(Data[I], Key); end; {$OVERFLOWCHECKS ON} function SameKey(const Key1, Key2: TTeaKey): Boolean; var I: Integer; begin Result := False; for I := 0 to 3 do if Key1[I] <> Key2[I] then Exit; Result := True; end; procedure StrToKey(const S: AnsiString; var Key: TTeaKey); var TempBytes: TByte4; I, N, K: Integer; SB: AnsiString; begin SB := UTF8Encode(StringOfChar(' ', 16)); N := Min(Length(S), 16); for I := 1 to N do SB[I] := S[I]; for I := 0 to 3 do begin TempBytes := CardinalToBytes(Key[I]); for K := 0 to 3 do TempBytes[K] := Ord(SB[I * cTeaBlockSize + K + 1]); Key[I] := BytesToCardinal(TempBytes); end; end; function KeyToStr(const Key: TTeaKey): AnsiString; var I, K: integer; TempBytes: TByte4; begin SetLength(Result, 16); for I := 0 to 3 do begin TempBytes := CardinalToBytes(Key[I]); for K := 0 to 3 do Result[I * cTeaBlockSize + K + 1] := AnsiChar(Chr(TempBytes[K])); end; end; procedure StrToData(S: AnsiString; var Data: TTeaData); var I, N, M: integer; TempBytes1: TByte4; TempBytes2: TByte4; begin N := Length(S) div (cTeaBlockSize * 2); M := Length(S) mod (cTeaBlockSize * 2); if M <> 0 then begin Inc(N); S := S + AnsiString(StringOfChar(' ', (cTeaBlockSize * 2) - M)); end; if N < 2 then // n = 1 begin N := 2; S := S + AnsiString(StringOfChar(' ', cTeaBlockSize * 2)); end; // set buffer length SetLength(Data, N); for I := 0 to Length(Data) - 1 do begin for M := 0 to 3 do begin TempBytes1[M] := Ord(S[(I * 2) * cTeaBlockSize + M + 1]); TempBytes2[M] := Ord(S[(I * 2) * cTeaBlockSize + M + 1 + cTeaBlockSize]); end; // put data to longword and back to buffer Data[I][0] := BytesToCardinal(TempBytes1); Data[I][1] := BytesToCardinal(TempBytes2); end; end; procedure BytesToData(S: TTeaBytes; var Data: TTeaData); var I, N, M: integer; TempBytes1: TByte4; TempBytes2: TByte4; begin N := Length(S) div (cTeaBlockSize * 2); M := Length(S) mod (cTeaBlockSize * 2); if M <> 0 then begin Inc(N); SetLength(S, Length(S) + (cTeaBlockSize * 2) - M); end; if N < 2 then // n = 1 begin N := 2; SetLength(S, Length(S) + cTeaBlockSize * 2); end; // set buffer length SetLength(Data, N); for I := 0 to Length(Data) - 1 do begin for M := 0 to 3 do begin TempBytes1[M] := S[(I * 2) * cTeaBlockSize + M]; TempBytes2[M] := S[(I * 2) * cTeaBlockSize + M + cTeaBlockSize]; end; // put it back to longword Data[I][0] := BytesToCardinal(TempBytes1); Data[I][1] := BytesToCardinal(TempBytes2); end; end; procedure DataToStr(var S: AnsiString; const Data: TTeaData); var TempBytes1: TByte4; TempBytes2: TByte4; I, N, M: integer; begin N := Length(Data); SetLength(S, N * (cTeaBlockSize * 2)); for I := 0 to N - 1 do begin TempBytes1 := CardinalToBytes(Data[I][0]); TempBytes2 := CardinalToBytes(Data[I][1]); for M := 0 to 3 do begin S[(I * 2) * cTeaBlockSize + M + 1] := AnsiChar(Chr(TempBytes1[M])); S[(I * 2) * cTeaBlockSize + M + 1 + cTeaBlockSize] := AnsiChar(Chr(TempBytes2[M])); end; end; S := AnsiString(Trim(string(S))); end; procedure DataToBytes(var S: TTeaBytes; const Data: TTeaData); var TempBytes1: TByte4; TempBytes2: TByte4; I, N, M: integer; begin N := Length(Data); SetLength(S, N * (cTeaBlockSize * 2)); for I := 0 to N - 1 do begin TempBytes1 := CardinalToBytes(Data[I][0]); TempBytes2 := CardinalToBytes(Data[I][1]); for M := 0 to 3 do begin S[(I * 2) * cTeaBlockSize + M] := TempBytes1[M]; S[(I * 2) * cTeaBlockSize + M + cTeaBlockSize] := TempBytes2[M]; end; end; end;
I had to turn overflow checks off for the portion of the code, because I don’t know how to avoid them. The XTEA code is designed to work this way I think. It is also important to mention that the algorithm works with 8 byte aligned blocks of data. So if the actual data is not a multiple of 8 bytes in length, we have to pad it. This can be a problem, because this way we introduce noise into the data which is decrypted on the other side. I could write the actual data size as the first 8 bytes (1 block). Then on the other side I could read that and trim the noise from the data. But the algorithm would not be XTEA compatible anymore. I still have to think about this and what to do. Another interesting problem was a Cardinal to Bytes conversion and vice verse. I had problems with that in .NET. By asking on SO I proved that you have to think outside the box sometimes and that there are always people out there that know the problem better than you do
Well quite a lot of work yes, but now I have a fast cross Delphi platform encryption algorithm.
Edit:
The CryptoAPI works on Win32, .NET and .NET Compact Framework platforms, so there is no problem with cross platform (windows that is) encryption. I did not know that at the time of the writing. But this still makes XTEA an excellent choice for Compact Framework because of its speed and simplicity. After all the mobile devices are not as powerful as other devices with Windows installed. But it is a viable solution for the next time I need encryption services.