As part of my current necessity-driven foray into modern-day cryptography, I got to play around with... serpents. Or more precisely a very specific Serpent1, designed in 1998 as a candidate for the competition2 to select an "Advanced Encryption Standard". It's totally unclear really where does that "advanced" come from given the total absence of any sort of mathematical proof regarding the actual desired effect of all those algorithms (as in: actual proof of strength). A more honest approach would note instead that absent such proofs, Serpent and all other current hash algorithms are essentially snake-oil magic promises rather than advanced anythings and therefore correctly described in simpler words such as... voodoo.3
So to put this in context: I'm talking here of a sort of Serpent that essentially plays around in a deterministic way with an input string and spits out a different string that is *hoped* to be... confusing enough for an attacker. Yes, I know there are quite a lot of discussions and claims regarding various very specific attacks. Still, those are not in any way actual proof of strength, no.
Getting back to our snake and its oil here, the task at hand is to... tame it. The approach is relatively simple and in any case straightforward: go through the detailed description of the design, try to fit it in own head4 aka try to understand the specific way in which this particular bit-mixing algorithm works and then test a reasonable existing implementation in Ada5. While it's not very clear *what* does Serpent exactly achieve (other than lots of bit mixing, hoping that's confusing enough), it's at least quite clear *how* it achieves it. So I'll focus on this *how* from here on. Note that this is effectively Serpent 1 (as opposed to Serpent 0, the first proposal of the same authors). The difference between the two as far as I understand it is that Serpent 0 used directly the same S-boxes as DES while Serpent 1 uses a derivate set of S-boxes (obtained from those of DES through a fixed, deterministic method).
The core of Serpent consists of 8 predefined permutations (S-boxes), let's call them S0 to S7. Each of those permutations describes a fixed way of mixing precisely 4 bits of input and obtaining as result... another 4 bits of output. For example, first permutation S0 taking as input bits X0, X2, X2 and X3 will spit out corresponding bits W,X,Y and Z where:
W = not ( (X0 xor X3) xor ( (X1 or X2) xor (Y and (X0 xor X1) and (X1 or X2))))
X = (X2 xor X3) xor (W xor (X1 and (X0 xor X3)))
Y = ( (X0 xor X2) and (X1 or X2)) xor (X3 and (X2 or Z))
Z = (X0 or X3) xor (X1 xor X2)
Does that *look* confusing? Well, to me at least it does, I'll admit to it plainly. Trouble is, looks are not worth much, but that's about all we actually have so far, better admit it at least. I will spare you however the transcription of the other 7 S-boxes - you can of course extract them yourself from the original Serpent description.
A permutation such as S0 above is applied to all slices of 4 bits from a block of input. For instance, when applying Serpent on blocks of 128 bits, there will be 128/4 = 32 copies of S0 applied at the same time to ensure that all 128 bits are effectively touched. Serpent applies its 8 different permutations several times (in same order though, so S0, S1 .. S7), iteratively, so that in total each permutation is applied 4 times (resulting in 32 iterations overall).
At each iteration, Serpent also uses a different sub-key (so 32 sub-keys in total) that gets effectively xor-ed with the input. However, all those 32 different subkeys are related because they are obtained by mixing the bits of a single initial key (256 bits in length, potentially padded to this length if needed). Those 32 sub-keys are obtained through a specific application of the same 4-bit permutations on the 256 bits of the initial key.
In addition to the above, Serpent also uses one special initial permutation (IP) applied only once in the very beginning, its inverse permutation (FP) applied only once at the very end and a linear transformation L that is applied between iterations (so it gets applied 31 times in total).
To gather all this together in a more readable and concise form:
- Serpent uses 8 permutations S0 to S7, 1 linear transformation L, 1 initial permutation IP and one final permutation FP.
- Serpent takes 128 bits of input, B, 256 bits of key K and produces 128 bits of output O.
- To obtain O = f(B, K), Serpent first calculates 32 sub-keys of K, each having 128 bits in length and denoted here by K0 to K31. Then, Serpent performs 32 iterations (rounds) as follows:
- B0 = IP(B) , where: B are the initial 128 bits of input
- Bi+1 = L( Sj( Bi xor Ki )), with i = 0 .. 29 and j = i mod 8; the input of each iteration is a xor between the output of the previous iteration and the current sub-key; the output of each iteration is the linear transformation of the result of applying the current permutation to all bits of input.
- B31 = S7( B30 xor K30); the last iteration does not apply the linear permutation since there will be instead the final permutation applied to obtain the output:
- O = FP(B31); the final output is the result of applying the final permutation to the output of the last (32nd) iteration.
Once the above was digested (as well as one can), the next step is of course implementation. While prototypes were made, the focus was in this case on an existing implementation, since a reference Ada implementation was in principle available. So the next step was rather to read this implementation comparing it with the specification and then, once satisfied that it does implement the actual Serpent, to test it on the existing test vectors.
At this testing point I stumbled a bit on the rather weird (to my mind) situation that the test vectors are given in "nessie" format meaning something more fit for human reading than direct food for Serpent code. So I first put together a bit of Ada code (useful exercise anyway since I'm only learning Ada really) to eat that whole file, run the Serpent on each test vector, compare result with expected one and report back to user whether test passed or failed. I'm rather happy to report that all tests passed indeed and therefore we have - as far as I can tell at the moment - a reasonably healthy Serpent-in-Ada.
You can download the file with the test vectors here. And here's the testing code6, feel free to use it on your own Serpent or improve it as you see fit:
test_serpent.ads
with Ada.Strings.Fixed; use Ada.Strings.Fixed; package Test_Serpent is procedure test_from_file(filename: String); procedure test_one; end Test_Serpent;
test_serpent.adb
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_Line; use Ada.Command_Line;
with Serpent; use Serpent;
with Interfaces; use Interfaces;
package body Test_Serpent is
Test_Fail : exception; -- raised if a test fails
procedure test_from_file (filename: String) is
file: FILE_TYPE;
keylen, blocklen, octets: Natural;
K: Key;
P, P2: Block; --plain text
C, C2: Block; --cipher (encrypted) text
times100: Block; --value after 100 iterations
times1k: Block; --value after 1000 iterations
W: Key_Schedule;
Test_No : Positive := 1;
begin
begin
open(file, In_File, filename);
exception
when others =>
Put_Line(Standard_Error, "Can not open the file '" & filename & "'. Does it exist?");
Set_Exit_Status(Failure);
return;
end;
keylen := 256;
blocklen := 128;
octets := 16;
loop
declare
Line: String := Get_Line(file);
Line1: String := Line;
key1, key2: String(1..octets*2);
len: Natural := 0;
begin
--check if this is test data of any known kind
if index(Line, "key=", 1) > 0 then
Line1 := Get_Line(file);
key1 := Tail(Line, octets*2);
key2 := Tail(Line1, octets*2);
for jj in 1..octets loop
K(jj-1) := Unsigned_8'value("16#" & key1((jj-1)*2+1..jj*2) & "#");
K(jj+octets-1) := Unsigned_8'value("16#" & key2((jj-1)*2+1..jj*2) & "#");
end loop;
elsif index(Line, "plain=", 1) > 0 then
key1 := Tail(Line, octets*2);
for jj in 1..octets loop
P(jj-1) := Unsigned_8'value("16#" & key1((jj-1)*2+1..jj*2) & "#");
end loop;
elsif index(Line, "cipher=", 1) > 0 then
key1 := Tail(Line, octets*2);
for jj in 1..octets loop
C(jj-1) := Unsigned_8'value("16#" & key1((jj-1)*2+1..jj*2) & "#");
end loop;
elsif index(Line, "100 times=", 1) > 0 then
key1 := Tail(Line, octets*2);
for jj in 1..octets loop
times100(jj-1) := Unsigned_8'value("16#" & key1((jj-1)*2+1..jj*2) & "#");
end loop;
elsif index(Line, "1000 times=", 1) > 0 then
key1 := Tail(Line, octets*2);
for jj in 1..octets loop
times1k(jj-1) := Unsigned_8'value("16#" & key1((jj-1)*2+1..jj*2) & "#");
end loop;
--at this stage we should have ALL needed, so run test
Put("-----Test " & Positive'Image(Test_No) & ": encryption...");
Prepare_Key(K, W);
Encrypt(W, P, C2);
if C2 /= C then
raise Test_Fail;
else
Put_Line("Passed-----");
end if;
Put("-----Test " & Positive'Image(Test_No) & ": decryption...");
Decrypt(W, C2, P2);
if P /= P2 then
raise Test_Fail;
else
Put_Line("Passed-----");
end if;
Put("-----Test " & Positive'Image(Test_No) & ": 100 iterations...");
for jj in 1 .. 100 loop
Encrypt(W, P, C2);
Decrypt(W, C2, P2);
if (P2 /= P) then
raise Test_Fail;
end if;
P := C2;
end loop;
Put_Line("Passed-----");
Put("-----Test " & Positive'Image(Test_No) & ": 1000 iterations...");
for jj in 1 .. 900 loop
Encrypt(W, P, C2);
Decrypt(W, C2, P2);
if (P2 /= P) then
raise Test_Fail;
end if;
P := C2;
end loop;
Put_Line("Passed-----");
Test_No := Test_No + 1;
end if;
exit when End_Of_File(file);
end;
end loop;
Close(file);
end test_from_file;
procedure test_one is
K: Key;
P, P2: Block;
C: Block;
W: Key_Schedule;
begin
K := (16#80#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#);
P := (16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#);
Serpent.Prepare_Key(K, W);
Encrypt(W, P, C);
if C /= (16#A2#, 16#23#, 16#AA#, 16#12#, 16#88#, 16#46#, 16#3C#, 16#0E#,
16#2B#, 16#E3#, 16#8E#, 16#BD#, 16#82#, 16#56#, 16#16#, 16#C0#)
then
raise Test_Fail;
end if;
for I in 1 .. 100 loop
Encrypt(W, P, C);
Decrypt(W, C, P2);
if (P2 /= P) then
raise Test_Fail;
end if;
P := C;
end loop;
if C /= (16#73#, 16#9E#, 16#01#, 16#48#, 16#97#, 16#1F#, 16#D9#, 16#75#, 16#B5#, 16#85#, 16#EA#, 16#FD#, 16#BD#, 16#65#, 16#9E#, 16#2C#) then
raise Test_Fail;
end if;
for I in 1 .. 900 loop
Encrypt(W, P, C);
Decrypt(W, C, P2);
if (P2 /= P) then
raise Test_Fail;
end if;
P := C;
end loop;
if C /= (16#BE#, 16#FD#, 16#00#, 16#E0#, 16#D6#, 16#E2#, 16#7E#, 16#56#, 16#95#, 16#1D#, 16#C6#, 16#61#, 16#44#, 16#40#, 16#D2#, 16#86#) then
raise Test_Fail;
else
Put_Line("PASSED: test single case.");
end if;
end test_one;
end Test_Serpent;
Ross Anderson, Eli Biham and Lars Knudsen, "Serpent: A Proposal for the Advanced Encryption Standard", NIST AES Proposal, 1998 ↩
The nature of this "competition" is dubious as discussed more in detail in logs, for instance here and here. ↩
This is not to say that voodoo can't be or indeed isn't useful, of course. ↩
It's a TMSR term of art already. ↩
Implementation in Ada by Markus G. Kuhn, serpent.adb and serpent.ads ↩
As a warning: the test code trusts that the given file contains indeed what it is looking for; run it on nonsense and you'll get idiocy as always, absolutely. ↩
Comments feed: RSS 2.0