The Perl Journal August 2003
Khazad is a new 64-bit block cipher that accepts a 128-bit key. Invented by Paulo S.L.M. Barreto and Vincent Rijmen, it is a finalist in the New European Schemes for Signatures, Integrity, and Encryption (NESSIE) Project.
In this article, I will show you how I implemented Khazad in Perl using XS programming. Using the techniques presented here, I hope that you will also be able to implement any block cipher that you fancy (or, perhaps, just create an XS-based Perl module).
At this writing, the current version of Crypt::Khazad is 1.0.3. It is available on CPAN at http://www.cpan.org/authors/id/J/JC/JCDUQUE/Crypt-Khazad-1.0.3.tar.gz. Files mentioned in this article are available in this module distribution. Also see http:// planeta.terra.com.br/informatica/paulobarreto/KhazadPage.html
The first thing to do is create a subdirectory where the module will be created and stored using the program h2xs, which converts C header files to Perl extensions. On the command line, type:
h2xs --omit-autoload --omit-constant --name=Crypt::Khazad
Refer to the h2xs man pages for explanation of the options --omit-autoload and --omit-constant. What's important here is the option --name=Crypt::Khazad. This tells h2xs to create a subdirectory Crypt/Khazad/.
The following files will be created in Crypt/Khazad/:
Changes Khazad.pm Khazad.xs MANIFEST Makefile.PL README ppport.h t
"t," which stands for tests, is a directory containing test scripts. For the moment, there's only one test script found here (1.t). All test scripts are placed in this directory and must be suffixed with '.t.'
Change directories (cd) into Crypt/Khazad. What is lacking in this directory is the typemap file. Create this file, and add the following line:
Crypt::Khazad T_PTROBJ
Note that the whitespace separating Crypt::Khazad and T_PTROBJ must be a tab.
The typemap file contains the mapping of Crypt::Khazad, an arbitrary data type, to its corresponding Perl value, T_PTROBJ, a type representing a pointer to a structure. Thus, we can set up an encryption/decryption routine like this:
use Crypt::Khazad; $cipherobj = new Crypt::Khazad $key; $ciphertext = $cipherobj->encrypt($plaintext); $plaintext = $cipherobj->decrypt($ciphertext);
Given an argument, $key, the new() function will create an object, $cipherobj, of type Crypt::Khazad (the data type we just declared in the typemap file).
Essentially, new() clones the object Crypt::Khazad. In most object-oriented languages, new() is already a built-in function. Unfortunately, there is no equivalent function in Perl. So, we have to create one ourselves. Since we are free to implement this function in any way we want, we could just as easily name it, say, clone(), and we would still get the same result.
Now, comes the fun part: XS programming!
Another missing file in Crypt/Khazad/ is the heart of the module, the Khazad C code. In our case, that file is named _khazad.c (it's available in the Crypt::Khazad module distribution on CPAN). So copy this file to Crypt/Khazad/.
The best way to understand C code is to study its main() function. In _khazad.c, we see how main() uses the other functions to perform the process of encryption and decryption. (See Listing 1.)
In Line 3, we see that variable subkeys is declared as data type NESSIEstruct. Lines 14-16 tell us that we have to initialize subkeys with a call to NESSIEkeysetup() before calling the functions NESSIEencrypt() for encryption, and NESSIEdecrypt() for decryption.
Now, open the file Khazad.xs. Initially, its content is just:
1 #include "EXTERN.h" 2 #include "perl.h" 3 #include "XSUB.h" 4 5 #include "ppport.h" 6 7 MODULE = Crypt::Khazad PACKAGE = Crypt::Khazad
Edit Khazad.xs so that it becomes:
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4
5 #include "ppport.h"
6
7 #include "_khazad.c"
8
9 typedef struct khazad {
10 NESSIEstruct key;
11 }* Crypt__Khazad;
12
13 MODULE = Crypt::Khazad PACKAGE = Crypt::Khazad
Notice that we have now #include-d the C code, _khazad.c (line 7). What about lines 9-11, starting with typedef struct khazad? Because the C code declares subkeys as type NESSIEstruct (line 3 of Listing 1), we have to declare the variable key in Khazad.xs (line 10) as type NESSIEstruct as well.
But there's a catch. When _khazad.c is compiled, everything is fine. But when the XS file is compiled by xsubpp, it complains. In fact, you are likely to get the following fatal errors:
Khazad.c: In function `XS_Crypt__Khazad_new': Khazad.c:64: `Crypt__Khazad' undeclared (first use in this function) Khazad.c:64: (Each undeclared identifier is reported only once Khazad.c:64: for each function it appears in.)
The solution is to look for the NESSIEstruct line in _khazad.c, and check how NESSIEstruct is declared. That code snippet is as follows:
struct NESSIEstruct {
u32 roundKeyEnc[R + 1][2];
u32 roundKeyDec[R + 1][2];
};
The xsubpp compiler does not like this code. So, revise this code into this:
typedef struct NESSIEstruct {
u32 roundKeyEnc[R + 1][2];
u32 roundKeyDec[R + 1][2];
} NESSIEstruct;
That will keep the xsubpp compiler happy.
Crypt::CBC is a module developed by Lincoln Stein to be used specifically in conjunction with block ciphers. As with all Perl modules, Crypt::CBC is also available from http://search.cpan.org/.
To be Crypt::CBC compliant, our block cipher must be able to return the block size it is using, as well as the length of its key, when Crypt::CBC asks for them. Edit Khazad.xs, adding the following lines:
int
keysize(...)
CODE:
RETVAL = 16;
OUTPUT:
RETVAL
int
blocksize(...)
CODE:
RETVAL = 8;
OUTPUT:
RETVAL
Our new Khazad.xs is transformed as shown in Listing 2.
The keyword int must be on a line by itself. RETVAL stands for "return value" and this is the data that Crypt::CBC needs. Read the perlxstut man pages for more details. The keysize() function returns a value of 16 bytes (the 128-bit key), while blocksize() returns 8 bytes (the 64-bit block length).
If we have the following code snippet:
use Crypt::Khazad; $cipherobj = new Crypt::Khazad $key; $ks = $cipherobj->keysize(); $bs = $cipherobj->blocksize();
$ks should hold the value 16, and $bs should be 8.
To implement the new(), encrypt(), and decrypt() functions, we must be familiar with perlguts and perlxs.
Edit Khazad.xs. It should now look like Listing 3. You'll want to consult the perlguts man pages for discussions of the following keywords:
SV* STRLEN SvPOK SvCUR Newz SvPV _nolen SvPV newSVpv
A couple of important things are worth mentioning here. The new() function actually calls the C function NESSIEkeysetup(). Similarly, encrypt() and decrypt() execute the C functions NESSIEencrypt() and NESSIEdecrypt(), respectively. Just refer to the main() function of _khazad.c (Listing 1) to learn how these functions are used.
The DESTROY() function is special. This function is called when the object, Crypt::Khazad, goes out of scope and needs to be destroyed. If the DESTROY() function does not exist, then nothing is done, and a memory leak could occur.
Delete the Khazad.pm generated by h2xs. We will make our own from scratch. Listing 4 is our new Khazad.pm.
It is worth noting that variable @EXPORT_OK (line 7) should list only those functions that we want to be visible from outside of the Khazad module. Line 7 tells us that keysize(), blocksize(), new(), encrypt(), and decrypt() are the only functions of Khazad that are accessible by other modules.
Delete the generated Makefile.PL. We'll make our own instead. The following is our hand-crafted Makefile.PL:
1 use ExtUtils::MakeMaker;
2
3 WriteMakefile(
4 'NAME' => 'Crypt::Khazad',
5 'VERSION_FROM' => 'Khazad.pm',
6 'PREREQ_PM' => {},
7 'AUTHOR' => 'Julius C. Duque',
8 'LIBS' => [''],
9 'DEFINE' => '',
10 'INC' => '-I.',
11 'dist' => {'COMPRESS' => 'gzip -9f', 'SUFFIX' => 'gz'}
12 );
Please read the perlxstut man pages for more details.
Every Perl module should be accompanied by at least one test script. A sample test script is shown in Listing 5. Place this script in the "t" directory. The test script must be suffixed with a ".t." (If you want to know more on how to make test scripts, read up on Test::More.)
This is the easiest part. Just type the following:
perl Makefile.PL make manifest make dist
The module is now bundled as a *.tar.gz file.
An example of using Khazad in a Crypt::CBC-compliant code is shown in Listing 6. The output should be:
plaintext1 : 0123456789abcdeffedcba9876543210 ciphertext : 1be2bb1a7b1bfa4227e33b06cf45c2d0f942f14a5b414e41 plaintext2 : 0123456789abcdeffedcba9876543210
In addition to Crypt::Khazad, I have created several other block cipher modules. All of these are available on CPAN:
Crypt::Misty1 Crypt::Anubis Crypt::Noekeon Crypt::Skipjack Crypt::Camellia Crypt::Square
The following man pages are essential reading: h2xs, perlxstut, perlxs, and perlguts.
The following books also got me going: Perl 5 How-To by M. Glover, A. Humphreys, and E. Weiss (Waite Group; ASIN 1571690581).
Perl Cookbook. T. Christiansen and N. Torkington (O'Reilly & Associates; ISBN 1565922433).
I am indebted to Marc Lehmann for his Crypt::Twofish2 module. I used his module as a skeleton for the Khazad implementation. Many thanks also go to the inventors of Khazad, Paulo S.L.M. Barreto and Vincent Rijmen. The Khazad home page is at http://planeta.terra.com.br/informatica/paulobarreto/KhazadPage.html.
TPJ
1 int main(void)
2 {
3 struct NESSIEstruct subkeys;
4 u8 key[KEYSIZEB];
5 u8 plain[BLOCKSIZEB];
6 u8 cipher[BLOCKSIZEB];
7 u8 decrypted[BLOCKSIZEB];
8
9 int v;
10
11 printf("Test vectors -- set 1\n");
12 printf("=====================\n\n");
13
14 NESSIEkeysetup(key, &subkeys);
15 NESSIEencrypt(&subkeys, plain, cipher);
16 NESSIEdecrypt(&subkeys, cipher, decrypted);
17
18 /****** more lines follow ******/
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4
5 #include "ppport.h"
6
7 #include "_khazad.c"
8
9 typedef struct khazad {
10 NESSIEstruct key;
11 }* Crypt__Khazad;
12
13 MODULE = Crypt::Khazad PACKAGE = Crypt::Khazad
14
15 int
16 keysize(...)
17 CODE:
18 RETVAL = 16;
19 OUTPUT:
20 RETVAL
21
22 int
23 blocksize(...)
24 CODE:
25 RETVAL = 8;
26 OUTPUT:
27 RETVAL
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4
5 #include "ppport.h"
6
7 #include "_khazad.c"
8
9 typedef struct khazad {
10 NESSIEstruct key;
11 }* Crypt__Khazad;
12
13 MODULE = Crypt::Khazad PACKAGE = Crypt::Khazad
14
15 int
16 keysize(...)
17 CODE:
18 RETVAL = 16;
19 OUTPUT:
20 RETVAL
21
22 int
23 blocksize(...)
24 CODE:
25 RETVAL = 8;
26 OUTPUT:
27 RETVAL
28
29 Crypt::Khazad
30 new(class, rawkey)
31 SV* class
32 SV* rawkey
33 CODE:
34 {
35 STRLEN keyLength;
36 if (! SvPOK(rawkey))
37 croak("Error: Key must be a string scalar!");
38
39 keyLength = SvCUR(rawkey);
40 if (keyLength != 16)
41 croak("Error: Key must be 16 bytes long!");
42
43 Newz(0, RETVAL, 1, struct khazad);
44 NESSIEkeysetup(SvPV_nolen(rawkey), &RETVAL->key);
45 }
46
47 OUTPUT:
48 RETVAL
49
50 SV*
51 encrypt(self, input)
52 Crypt::Khazad self
53 SV* input
54 CODE:
55 {
56 STRLEN blockSize;
57 unsigned char* intext = SvPV(input, blockSize);
58 if (blockSize != 8) {
59 croak("Error: Block size must be 8 bytes long!");
60 } else {
61 RETVAL = newSVpv("", blockSize);
62 NESSIEencrypt(&self->key, intext, SvPV_nolen(RETVAL));
63 }
64 }
65
66 OUTPUT:
67 RETVAL
68
69 SV*
70 decrypt(self, input)
71 Crypt::Khazad self
72 SV* input
73 CODE:
74 {
75 STRLEN blockSize;
76 unsigned char* intext = SvPV(input, blockSize);
77 if (blockSize != 8) {
78 croak("Error: Block size must be 8 bytes long!");
79 } else {
80 RETVAL = newSVpv("", blockSize);
81 NESSIEdecrypt(&self->key, intext, SvPV_nolen(RETVAL));
82 }
83 }
84
85 OUTPUT:
86 RETVAL
87
88 void
89 DESTROY(self)
90 Crypt::Khazad self
91 CODE:
92 Safefree(self);
1 package Crypt::Khazad;
2
3 use strict;
4 use warnings;
5 require Exporter;
6
7 our @EXPORT_OK = qw(keysize blocksize new encrypt decrypt);
8 our $VERSION = '1.0.0';
9 our @ISA = qw(Exporter);
10
11 require XSLoader;
12 XSLoader::load('Crypt::Khazad', $VERSION);
13
14 # Preloaded methods go here.
15
16 1;
17
18 __END__
19
20 =head1 NAME
21
22 Crypt::Khazad - Crypt::CBC-compliant block cipher
23
24 =head1 ABSTRACT
25
26 Put abstract here.
27
28 =head1 SYNOPSIS
29
30 use Crypt::Khazad;
31 $cipher = new Crypt::Khazad $key;
32 $ciphertext = $cipher->encrypt($plaintext);
33 $plaintext = $cipher->decrypt($ciphertext);
34
35 =head1 DESCRIPTION
36
37 Put description here.
38
39 =head1 COPYRIGHT AND LICENSE
40
41 Put copyright notice here.
42
43 =cut
1 use diagnostics;
2 use strict;
3 use warnings;
4 use Test::More tests => 2;
5 BEGIN {
6 use_ok('Crypt::Khazad')
7 };
8
9 BEGIN {
10 my $key = pack "H32", "80000000000000000000000000000000";
11 my $cipher = new Crypt::Khazad $key;
12 my $plaintext = pack "H16", "0000000000000000";
13 my $ciphertext = $cipher->encrypt($plaintext);
14 my $answer = unpack "H*", $ciphertext;
15 is("49a4ce32ac190e3f", $answer);
16 };
1 #!/usr/local/bin/perl
2
3 use diagnostics;
4 use strict;
5 use warnings;
6 use Crypt::CBC; # CBC automatically loads Khazad for us
7
8 my $key = pack "H32", "00112233445566778899aabbccddeeff";
9 my $IV = pack "H16", "0102030405060708";
10
11 my $cipher = Crypt::CBC->new({'key' => $key,
12 'cipher' => 'Khazad',
13 'iv' => $IV,
14 'regenerate_key' => 1,
15 'padding' => 'standard',
16 'prepend_iv' => 0
17 });
18
19 my $plaintext1 = pack "H32", "0123456789abcdeffedcba9876543210";
20 print "plaintext1 : ", unpack("H*", $plaintext1), "\n";
21
22 my $ciphertext = $cipher->encrypt($plaintext1);
23 print "ciphertext : ", unpack("H*", $ciphertext), "\n";
24
25 my $plaintext2 = $cipher->decrypt($ciphertext);
26 print "plaintext2 : ", unpack("H*", $plaintext2), "\n";