UFSM > Ciência da Computação > ELC139 - Programação Paralela

1) Preparação

1. Escolha uma API/biblioteca de programação com troca de mensagens (sockets, MPI, zeromq, etc.) na sua linguagem preferida. Instale o que for necessário e configure um "cluster" de no mínimo 2 máquinas.

2. Faça um programa que efetue a comunicação entre 2 processos no estilo ping-pong, ou seja: um processo faz envio-recepção, o outro faz recepção-envio. O programa deverá repetir essa comunicação várias vezes, medindo o tempo do lado do processo que fizer o primeiro envio, para depois calcular a taxa de transmissão.

3. Execute seu programa para diferentes tamanhos de mensagem, começando em 0 bytes. Apresente os resultados em uma tabela.

2) Programa sequencial

A quebra de senhas é uma operação que pode ser utilizada para detectar vulnerabilidades de segurança em sistemas. De fato, se uma senha pode ser facilmente quebrada, é preferível que isso seja detectado preventivamente pelos administradores do sistema, antes que invasores explorem essa vulnerabilidade.

Para este trabalho, você poderá escolher qualquer programa sequencial de quebra de senha, que possa ser invocado pelo programa que você irá desenvolver. O programa (executável) será chamado diversas vezes, em paralelo, para tentar quebrar um lote de senhas.

Como sugestão, indica-se o programa MDCrack, que emprega o método da força bruta para quebrar senhas baseadas em algoritmos de hash comuns (MD5, por exemplo). Os passos abaixo referem-se à compilação e uso deste programa:

1. Obtenha os fontes do programa MDCrack 1.2 em http://c3rb3r.openwall.net/mdcrack/download/mdcrack-1.2.tar.gz. Descompacte o arquivo em uma pasta acessível a todos os computadores que serão utilizados na execução paralela:

   tar xzvf mdcrack-1.2.tar.gz
   

2. Obtenha o patch disponível em mdcrack-1.2p.patch e salve-o na pasta mdcrack-1.2. Este patch faz uma pequena alteração no código para ele ser compilado sem problemas. Para aplicar este patch, digite:

   cd mdcrack-1.2
   patch -p1 < mdcrack-1.2p.patch
   

3. Compile o programa seguindo as instruções fornecidas com o código-fonte:

   cd mdcrack-1.2
   make little
   

4. Teste o programa da seguinte maneira:

   cd mdcrack-1.2
   bin/mdcrack -M MD5 -s abcdefghijklmnopqrstuvwxyz 5e394281dfac81c1e7dddcaf4d35d1f6
   

   Neste exemplo, o conjunto de caracteres possíveis na senha é abcdefghijklmnopqrstuvwxyz e o código MD5 a quebrar é 5e394281dfac81c1e7dddcaf4d35d1f6. Este comando deve produzir uma saída indicando que a senha foi quebrada e é igual a aabb:

   <<System>> MDcrack v1.2 is starting.
   <<System>> Sorting custom charset ... done
   <<System>> Using custom charset : abcdefghijklmnopqrstuvwxyz
   <<System>> Max pass size = 12 >> Entering MD5 Core 1.
   Password size: 1
   Password size: 2
   Password size: 3
   Password size: 4
   ----------------------------------------
   Collision found ! => aabb
   Collision(s) tested : 36532 in 0 second(s), 17 millisec, 216 microsec.
   Average of 2121979.5 hashes/sec.
   

5. Para testar o programa com outras chaves, pode-se usar o comando md5sum, conforme o exemplo abaixo:

   echo -n aabb | md5sum
   

   Esse exemplo produz o código 5e394281dfac81c1e7dddcaf4d35d1f6 usado no exemplo acima.

3) Programa distribuído

Nesta parte do trabalho, o objetivo é desenvolver um programa paralelo, usando a interface de comunicação escolhida na parte 1, que use o programa escolhido na parte 2 para tentar quebrar um lote de senhas. O programa deverá rodar no "cluster" montado na parte 1.

1. O programa paralelo deverá receber como entrada um arquivo contendo uma lista de senhas a quebrar. Se você usar MDCrack, pode usar o arquivo crackme.txt, que contém várias senhas codificadas como hashes MD5.

2. O programa deverá distribuir o trabalho de quebra das várias senhas entre processos trabalhando em paralelo. Os processos serão lançados sobre as máquinas disponíveis. Cada processo deverá processar uma ou mais senhas. Atenção: este trabalho não visa paralelizar o programa MDCrack para quebra de uma única senha em paralelo.

3. O programa poderá ser implementado segundo um modelo mestre-trabalhador, em que o processo mestre distribui as tarefas dinamicamente entre os processos trabalhadores (Foster, seção 2.5). Cada processo trabalhador deverá chamar o programa escolhido para tentar quebrar cada senha fornecida.

4. O programa deverá funcionar para diferentes números de processos.

5. O desempenho do programa paralelo deverá ser analisado levando em conta diferentes dados de entrada e diferentes números de processos.

Entrega

1. Este trabalho pode ser feito individualmente ou em dupla.

2. Até dia 10/05 (sexta), envie e-mail à professora indicando: (1) a API de comunicação que será usada e (2) se o trabalho será individual ou em dupla.

3. Até dia 16/05 (quinta), publique na sua página todo o material produzido para a parte 1 e indique à professora o programa que será usado na parte 2.

4. Até dia 22/05, 23:59, publique o material da parte 3 e compareça à aula do dia 23/05 para apresentar o trabalho à professora.

Material de apoio

• MDCrack
  Programa usado neste trabalho, de autoria de Gregory Duchemin.

• Brute force attacks on cryptographic keys
  Texto de Richard Clayton, University of Cambridge, 2001.

• MD5 (Message Digest Algorithm 5)
  MD5 na Wikipedia.

• RFC 1321 The MD5 Message-Digest Algorithm
  Referência oficial do algoritmo MD5, padronizado pela IETF (Internet Engineering Task Force).

• Designing and building parallel programs: concepts and tools for parallel software engineering.
  Livro-texto da disciplina. Ver seção 2.5, Mapping.

• Message Passing Interface (MPI) - Lawrence Livermore National Laboratory
  Tutorial sobre MPI com vários exemplos.