lunes, 5 de mayo de 2014

Tuenti Challenge 2014 - 3ª Parte

Challenge 6 - Man in the middle

¿Pero esto que es? ¿Esto qué es?

Le voy a quitar a Matias Prats la frase de la boca, porque el problema 6 ya son palabras mayores. El primer problema que realizó una criba considerable entre los participantes. Y no es para menos, porque nos dan una dirección IP en tamaño XL, y adios muy buenas.

 Bueno pues si tenemos la invitación, qué menos que aceptarla. Allí que lanzamos nuestro cliente telnet/netcat/putty o similares para encontrarnos con lo siguiente:



hello? ¿Acaso hay alguien ahí detrás? Pues ahora te vas a enterar: te voy a contestar con tu misma moneda. "hello?"



¡Pero bueno! No... si cuando mi madre me dice que la gente se ríe de mi es por algo... 

Quizás es que el archivo mitm.zip tengo algo que ver. Me lo descargaré, por si acaso, quizás encuentre algo interesante:
  • Cliente.Js
  • Server.Js
Dos archivos, y parecen Javascripts! evidentemente esta es la clave. Los abro y me encuentro con esto:



Puff... tenía que haber hecho más caso a aquellas clases de jquery... Bueno, que remedio, me tendré que leer el enunciado xd.

Entiendo... Un Man in the middle, sí claro: Cain, Ettercap, Charlie Sheen,...

Pero, ¿cómo voy a realizar un man in the middle si estoy en el lado del servidor? Al parecer nuestro amigo Obama y sus secuaces tienen más armas que nosotros, así que utilicemoslas.

Dejando a un lado la coña, este es el primer desafío que me trajo de cabeza. No sé cuantas horas fueron, pero estoy seguro que más de 4 y más de 5. Por un lado tenemos el cliente, por otro el servidor, y en medio de estos dos estamos nosotros que podemos tanto ver como modificar la información del canal. Hasta ahí todo bien.

El problema radica en que el contenido de la comunicación esta cifrado con AES-256, y por tanto no entendemos nada de lo que pasa por delante de nuestras narices. ¿Y por qué no intentamos ver las claves de cifrado que utilizan? ¿Podríamos conseguirlo?

Pues no. Porque ahí unos tipos muy listos, que se autoproclaman matemáticos y que tienen la fea costumbre de entorpecer las actividades de los lammers tocapelotas como yo. Y en concreto un par de ellos Whitfield Diffie y Martin Hellman que inventaron un protocolo seguro de intercambio de claves en un entorno inseguro como el nuestro basado en clave pública, es decir, que una de las claves es conocida y la otra no, y que con una de ellas se puede descifrar y con la otra cifrar. Para más información http://es.wikipedia.org/wiki/Criptograf%C3%ADa_asim%C3%A9trica

 Realmente yo esto ya lo conocía, y además conocía que el protocolo Diffie-Hellman es vulnerable a un MITM activo, es decir, en el que se modifica la información. Para ello basta con modificar las claves que envía uno de ellos por unas nuestras, y las que envía el otro por otras también generadas por nosotros. Después deberemos volver a descifrar el contenido y volver a cifrarlo con la clave original de cada uno de ellos para que estos puedan decodificar correctamente su mensaje.

Todo parece tener su lógica. Pero ahora hay que hacerlo funcionar. Podría haber optado por utilizar PERL del cual si tengo bastante manejo, pero entonces no sería capaz de levantar minimamente mi marchitado ego. Así que opté por seguir el camino que se nos daba y utilizar javascript. Ahora solo nos queda aprender NODE.JS, o por lo menos el funcionamiento mínimo.

NODE.JS, con lo moderno que es eso y yo que soy de C y ensamblador. Si eso es dirigido a eventos (que son interrupciones como las de toda la vida, pero si digo que es un "paradigma" dirigido a eventos quedo como dios), y además corre tanto en el cliente como en el servidor. Puff rollo cuántico además

No se yo si voy  a poder ser capaz de enfrentarme a esto. Pero si quiero pasar no me queda más remedio... así que allá voy.


Y 12 horas después engendré esto:



/* CHALLENGE 6... o como aprender NODE.JS en unas horas xddd */

#!/usr/bin/env node

if ((process.version.split('.')[1]|0) < 10) {
 console.log('Please, upgrade your node version to 0.10+');
 process.exit();
}

var net = require('net');
var util = require('util');
var crypto = require('crypto');

var options = {
 'port': 6969,
 'host': '54.83.207.90',
}

var KEYPHRASE = '';


process.stdin.resume();
process.stdin.setEncoding('utf8');
 
process.stdin.on('data', function (chunk) {
 
 KEYPHRASE = chunk.replace(/[\n\r]/g, '');


 var dh1, dh2, dh, secret1, secret2, keyphrase, state = 0;

 var data1;

 var socket = net.connect(options, function() {
  //socket.write('');
 });

 var clientePrime, clientePublicKey, servidorPublicKeyModificada;

 socket.on('data', function(data) {

  data = data.toString().trim().split('|');

 

  if(state == 0){

   socket.write('hello?');
   state++;


  }else if(state == 1){
   socket.write('hello!');
   state++;

  }else if (state == 2) {

   //Interceptamos las claves del cliente
   clientePrime = data[1];
   clientePublicKey = data[2];

   //Generamos y enviamos nuestras propias claves al servidor
   dh1 = crypto.createDiffieHellman(256); //Numero primo longitud 256
   dh1.generateKeys();
   socket.write(util.format('key|%s|%s\n', dh1.getPrime('hex'), dh1.getPublicKey('hex')));

   state++;

  } else if (state == 3) {

   //Interceptamos la clave modificada enviada por el servidor
   servidorPublicKeyModificada = data[1];

   //Al cliente le tenemos que enviar la clave esperada
   dh2 = crypto.createDiffieHellman(clientePrime, 'hex');
   dh2.generateKeys();
   secret1 = dh2.computeSecret(clientePublicKey, 'hex');
   socket.write(util.format('key|%s\n', dh2.getPublicKey('hex')));

   state++;

  } else if (state == 4) {

   //Desciframos la keyphrase que envia el cliente con la clave secreta anterior
   var decipher = crypto.createDecipheriv('aes-256-ecb', secret1, '');
   var keyphraseTextoPlano = decipher.update(data[1], 'hex', 'utf8') + decipher.final('utf8');
   keyphraseTextoPlano = KEYPHRASE;


   //Y la volvemos a cifrar con la clave secreta
   secret2 = dh1.computeSecret(servidorPublicKeyModificada, 'hex');
   var cipher = crypto.createCipheriv('aes-256-ecb', secret2, '');
   var keyphraseCifrada = cipher.update(keyphraseTextoPlano, 'utf8', 'hex') + cipher.final('hex');
   socket.write(util.format('keyphrase|%s\n', keyphraseCifrada));

   state++;


  } else if (state == 5) {

   //Desciframos el resultado, que está cifrado 
   var decipher = crypto.createDecipheriv('aes-256-ecb', secret2, '');
   var message = decipher.update(data[1], 'hex', 'utf8') + decipher.final('utf8');
   console.log(message);
   socket.end();

  } else {
   console.log('Error');
   socket.end();
  }

 });
});

Al final, no es más que coger de un lado, coger de otro, cambiar un poquito... y listo! tenemos un frankestein cliente-servidor que nos realiza correctamente el proceso de modificación del tráfico. Como veis he respetado la misma estructura de estados que en los archivos originales. Y he hiper-comentado el código para poder entenderme a mi mismo, que no es fácil cuando no conoces algo en profundidad.

Mención aparte los problemas que he tenido para conseguir que se tragase la entrada estandar el script de pruebas. Pero al final tras un poquito de stackOverflow y un poquito de maldecir al creador de javascript y todos sus incondicionales que siguen promoviendo su uso (esto es un debate intenso en ciertos círculos: javascript=dios, javascript=*****), conseguí que el archivo funcionara como debía. Y lo mejor de todo, el desafío 7 ya no mencionaba javascript por ningún lado. Estaba salvado.


Challenge 7- Yes we scan

Bueno, tras abandonar las pantanosas aguas de javascript, por fin otro problema de los que me gustan a mí. Más tradicional, tal y como soy yo xd.

Seguimos con la NSA, pero en esta ocasión dejamos el espionaje en routers ajenos, para pedirle el listado de llamadas directamente a nuestros amigos en el poder. Y se nos pide que mirando dichos registros de llamadas, averigüemos si hay alguna conexión entre 2 terroristas dados y en caso afirmativo lancemos en cuanto antes una alerta.

Para la resolución de este problema pasé por varias fases. La primera, la fase de ingenuidad: "esto está tirado, como me dan ambas columnas ordeno en un lado y en otro, un poco de pegamento y está hecho". Error. Tras pensar un poco no tiene ni pies ni cabeza. Un extracto de mi primera intención:

vector<array<int,2>> calls;
    calls.reserve(1000000);

    ifstream file("phone_call.log");
    if (file.is_open()){
        for(int i=0; i<1000000; i++){
            file >> calls[i][0];
            file >> calls[i][1];

            //Primera ordenacion
            if(calls[i][0] > calls[i][1])
                swap(calls[i][0], calls[i][1]);
        }
    }

    sort(calls.begin(), calls.begin()+1000000);

    ofstream salida("salida.txt");
    for(int i=0; i<1000000; i++){
        salida << calls[i][0] << " " << calls[i][1] << "\n";
    }

    int terroristA, terroristB;

    cin >> terroristA;
    cin >> terroristB;

    return 0;

Tenemos que recordar que el problema nos pide el punto en que ambos terroristas se conectan. Pero este no tiene que contener a ninguno de los dos terroristas. Puede que sea una llamada entre dos contactos de estos los que finalmente los ponga en contacto.

Así que barajé otra posibilidad: tablas hash. Si al final las tablas hash lo arreglan todo. Error. Introducir una tabla hash aquí no iba a arreglar las cosas porque sí.

Pero si utilizo una búsqueda en anchura junto con 2 tablas hash, una cola y todo ello complicado a la enésima potencia con una búsqueda recursiva que ya no sé ni lo que hace, porque la verdad no sé con que intención pude llegar a pensar semejante cosa (la falta de sueño quizás), nos queda un borrador como este:


class BFS{

    private:

        multimap<int,int> calls;
        map<pair<int, int>, int> lines; //Asocia cada llamada con su linea

        unordered_map<int, bool> generados;

        void recursivo(queue<int> &nivel, int terroristB){

            queue<int>newLevel;

            while(!nivel.empty()){

                    auto its = calls.equal_range(nivel.front());

                    for(auto it = its.first; it != its.second; ++it){

                        //Evitamos generar aquellos nodos ya generados
                        if(!generados.count(it->second)){

                            generados[it->second] = true;
                            newLevel.push(it->second);

                            if(it->second == terroristB){
                                if(nivel.front() < terroristB)
                                    cout << "Connected at " << lines[make_pair(nivel.front(), terroristB)] << endl;
                                else
                                    cout << "Connected at " << lines[make_pair(terroristB, nivel.front())] << endl;

                                //exit(0);
                            }
                        }
                    }

                nivel.pop();
            }

            if(newLevel.size()>0)
                recursivo(newLevel, terroristB);
        }

    public:

        /* La creación de las tablas tiene un coste fijo, que amortizamos posteriormente al realizar las busquedas */
        BFS(){

            int num1,num2;
            ifstream file("phone_call.log");
            if (file.is_open()){
                for(int i=0; i<1000000; i++){

                    file >> num1;
                    file >> num2;

                    if(num1 > num2)
                        swap(num1, num2);

                    calls.insert({num1,num2});
                    calls.insert({num2,num1});

                    lines.insert(pair<pair<int, int>, int>(make_pair(num1, num2), i));
                }
            }
        }


        void buscar(int terroristA, int terroristB){

            queue<int>nivel;
            nivel.push(terroristA);
            generados[terroristA] = true;


            recursivo(nivel, terroristB);
        }
};



int main(){

    BFS mySearch;

    int terroristA, terroristB;

    cin >> terroristA;
    cin >> terroristB;

    mySearch.buscar(terroristA, terroristB);

    cout << "Not connected" << endl;

    return 0;
}  

Que funciona, lo peor de todo es que funciona. Pero claro, en cuanto el tamaño de la entrada comienza a crecer, el problema se vuelve cada vez más y más lento. Tras debugear un poco, veo que el problema se enfrenta a un muro tremendo poco antes de llegar a la linea 500000 del log telefónico.

Además, estaba convencido de que el test definitivo entraría en un estado perenne de ejecución, que lo mismo necesitaba algunos meses.

Opté entonces por cambiar el enfoque, y realizar un análisis lineal en el tiempo del archivo telefónico, desde el registro 1 hasta el registro 1000000. De este modo con cada linea enlazaba los nodos que aparecían y que almacenaba en un vector, y ahora sí, utilizaba la tabla hash para encontrar la posición del nodo al que enlazamos.

Comencé introduciendo en primera posición del vector (posición 0 y 1) a ambos terroristas, y para cada nuevo nodo que agregaba, solo realizaba comprobaciones de conexiones entre ambos terroristas si los nuevos nodos modificaban sus conexiones. De primeras quizás no os haya quedado muy claro, os dejo el código para que lo examinéis con más detenimiento. Cualquier duda la podéis preguntar en los comentarios:


/* C++ HEADERS */
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>

using namespace std;


#define NUMLINEAS 1000000


struct node{
    int num;
    vector<int> sig;
};

int num_llamadas=0;

class yesWeScan{

    private:

        vector<node> nodos;
        unordered_map<int,int> position; //Indica la posición de cada nodo en el vector


        bool recursivo(int posActual, int posB, unordered_map<int,bool> &recorridos){

            if(posActual == posB)
                return true;

            recorridos[posActual] = true; //Llevamos la cuenta de los nodos recorridos para no repetir ciclos

            int pos_sig;

            //Desde un nodo se puede saltar a distintos nodos
            int numConexiones = nodos[posActual].sig.size();

            for(int n=0; n<numConexiones; n++){

                pos_sig = nodos[posActual].sig[n];

                if(!recorridos.count(pos_sig)) //Si no hemos pasado ya por dicho nodo
                    if(recursivo(pos_sig, posB, recorridos))
                        return true;
            }

            return false;

        }


    public:

        yesWeScan(){

            nodos.reserve(NUMLINEAS*2);
        }


        bool comprobarConexion(int posA, int posB){

            unordered_map<int,bool>recorridos;

            return recursivo(posA, posB, recorridos);
        }


        void solve(int terroristA, int terroristB){

            int numNodos = 0;

            nodos[numNodos].num = terroristA;
            position[terroristA]=numNodos;
            numNodos++;

            nodos[numNodos].num = terroristB;
            position[terroristB]=numNodos;
            numNodos++;

            /* Para tareas de DEBUG */
            ofstream output("salida.txt");
            output << terroristA << " " << terroristB << endl;

            int num1,num2;
            ifstream file("phone_call.log");
            if (file.is_open()){
                for(int i=0; i<NUMLINEAS; i++){

                    file >> num1;
                    file >> num2;

                    bool check1=true;
                    bool check2=true;

                    if(!position.count(num1)){
                        nodos[numNodos].num = num1;
                        position[num1]=numNodos;
                        numNodos++;
                        check1 = false;
                    }


                    if(!position.count(num2)){
                        nodos[numNodos].num = num2;
                        position[num2]=numNodos;
                        numNodos++;
                        check2 = false;
                    }

                    //Enlaza el nodo1 con el nodo2
                    int pos1 = position[num1];
                    int pos2 = position[num2];

                    nodos[pos1].sig.push_back(pos2);

                    //Enlaza el nodo2 con el nodo1
                    nodos[pos2].sig.push_back(pos1);

                    //El terrorista A siempre esta en la posicion 0 del vector, y el terrorista B en la posicion 1

                    //Solo realizamos la comprobación si los nodos nuevos cambian las conexiones principales
                    if(check1==true || check2==true){
                        if(comprobarConexion(1, 0)){
                            cout << "Connected at " << i << endl;
                            return;
                        }
                    }
                }
            }

            cout << "Not connected" << endl;

        }
};


int main(){

    int terroristA, terroristB;

    cin >> terroristA;
    cin >> terroristB;

    yesWeScan iToo;

    iToo.solve(terroristA, terroristB);

    return 0;
}

No es el algoritmo más eficiente posible, y posiblemente dicho problema se preste a una solución con programación dinámica elegante, pero conseguí avanzar otra ronda más, y el tiempo de ejecución fue mínimo.

Challenge 8
http://programacioncompetitiva.blogspot.com.es/2014/05/tuenti-challenge-2014-4-parte.html 

No hay comentarios:

Publicar un comentario