domingo, 27 de noviembre de 2011

3rd Practical Assignment - Encryption

Hi, in this post I'll explain how does our encryption algorithm work in NachOS.

The algorithm we used is RC4, a formal definition of the algorithm is:

"RC4 is a stream cipher designed by Rivest for RSA Data Security (now RSA Security). It is a variable key-size stream cipher with byte-oriented operations. The algorithm is based on the use of a random permutation. "

Before adding code to NachOS, we'd already tested the algorithm in python, using the following code:
#! usr/bin/python  
class RC4:  
 def __init__(self:(  
  print 'RC4'  
 def ksa(self, llave:(  
  self.S = range(256) # crea un vector de 256 numeros  
  for i in range(0,256:(  
                        # Escoje dos números para mezclarlos usando los números de  
                        # la llave como semilla. En este caso los caracteres de la  
                        # llave se convierten en un numero entero usando ascci.  
   j = ( j + ord(llave[ i % len(llave)]) + self.S[i] ) % 256  
   (self.S[i], self.S[j] ) = ( self.S[j], self.S[i] )  
 def prga(self, texto:(  
  temp = ""  
  j = 0  
  for i in range(len(texto):(  
                        # Utiliza la llave de 256 numeros para crifrar el texto.  
   j = (j + self.S[i+1]) % 256  
   (self.S[i+1], self.S[j] ) = ( self.S[j], self.S[i+1])  
                        # La variable temp se usa para guardar el resultado del  
                        # crifrado y convertir el número a hexagesimal  
   temp = temp + hex(self.S[(self.S[i+1] + self.S[j])%256]^ord(texto[i])).split('x')[1]  
  print "%s -> %s"%(texto, temp)  
rca = RC4()  
print "key -> LLave"  
rca.prga("Este texto es muy importante") 

And with that tested, we proceeded to program it in C++. To do that, we added new files to the NachOS Makefile in order for it to compile with all NachOS. We called them and encrypt.h. In encrypt.h we just defined the method prototypes and the class itself. The code looks like this:

class Encrypt{
  //Destructor not used
  //Constructor, takes a key and a string to convert.
  Encrypt(char *key, char *str);
  //Method to swap places in an array of characters.
  void swap(char *s, unsigned int i, unsigned int j);
  //Method to do the key scheduling algorithm
  void ksa(char *key, unsigned int key_length);
  //Method to do the pseudo-random generation algorithm
  char prga();

So that's the header file, now the .cc file in which all the methods are elaborated, contains the previous defined methods in the header file:

  • swap: method to swap values from the S array.
  • ksa: method that initializes the array, and does the key-scheduling algorithm to generate a key from a given string.
  • prga: method that does the pseudo-random generation algorithm, which pretty much mixes the array with the previously generated key and outputs the keystream
The code is the following:

#include "encrypt.h"

char S[256];
unsigned int i, j;
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
Encrypt::Encrypt(char *key, char *str){
    unsigned int x;
    char *string;
    char contenido[100];
    unsigned int y;
        this->ksa(key, strlen((char*)key));
        printf("\nKey: %s, Message: %s\nEncrypted Message: \n", key, str);
        for (y = 0; y < strlen((char*)str); y++){
        printf("%x", (str[y] ^ this->prga()));
Encrypt::swap(char *S, unsigned int i, unsigned int j) {
    char temp = S[i];
    S[i] = S[j];
    S[j] = temp;
Encrypt::ksa(char *key, unsigned int key_length) {
    for (i = 0; i < 256; i++)
        S[i] = i;
    for (i = j = 0; i < 256; i++) {
        j = (j + key[i % key_length] + S[i]) & 255;
        swap(S, i, j);
    i = j = 0;
Encrypt::prga() {
    i = (i + 1) & 255;
    j = (j + S[i]) & 255;
    swap(S, i, j);
    return S[(S[i] + S[j]) & 255];

So, now to call our class, there are two things we did, first one, initialize an object in main and give the parameters there, so we can test it running nachos. The second one, which I'm going to explain, is to test it directly with the messages used in the file in the network directory.

To do this, we needed to import encrypt.h in the file. With that done, we just created an object in the MailTest function with the syntax: Encrypt *encrypt. Then we modified the messages just to test with something different, and used the encryption algorithm with them.

Compiling everything from the beginning gave this output:

With everything compiled and ready, we proceeded to execute two nachos machines to connect them with the simulated network, with the commands: ./ -m 0 -o 1 & ./ -m 1 -o 0 & (each one in a different terminal, but I understand it can be done in the same one).

That gave us the following output:

Which as we can see, its a little odd, because it adds some F's to the keystream. We couldn't fix that but we think the reason was because we used a char * instead of an unsigned char * for the key and the string parameters, but using unsigned char * just caused a lot of errors to pop out, so we couldn't change it.

Anyway, removing the F's we can see the output is the same as the python output with the same message and key:

And that's it, if you have any suggestion or question feel free to comment.:)

1 comentario: