Author(s):
Lopes, José Manuel Sá
Date: 2013
Persistent ID: http://hdl.handle.net/10451/9658
Origin: Repositório da Universidade de Lisboa
Subject(s): Códigos de erro; Forward error correction; Foutain codes; Resiliência; RaptorQ; Teses de mestrado - 2013
Description
Tese de mestrado em Segurança Informática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2013
A teoria de códigos é o estudo das propriedades dos códigos e sua adequação para uma aplicação específica. Um dos usos dos códigos é a correcção de erros. A técnica de Forward Error Correction (FEC) é utilizada para recuperar de erros na transmissão de dados, quando canais de comunicação não fiáveis são utilizados. A ideia central de FEC é o transmissor codificar a sua mensagem de uma maneira redundante, utilizando um código error-correcting code (ECC), conhecido por código auto-corrector. Como exemplo, temos os códigos de Hamming, desenvolvidos por Richard Hamming na década de 40. A redundância permite (idealmente) ao receptor detectar erros que ocorreram durante a transmissão e corrigi-los. Assim, o receptor pode corrigir os erros sem a necessidade de retransmissões (com um custo adicional de largura de banda). Deste modo, a técnica de FEC é normalmente utilizada em cenários onde as retransmissões não são admissíveis em termos de custos ou mesmo impossíveis, como em ligações unidireccionais ou quando se transmite para vários receptores em multicast. O FEC também é utilizado em sistemas de armazenamento, para recuperar informação corrompida. Os fountain codes representam uma classe de códigos com a propriedade de produzir uma sequência potencialmente infinita de símbolos codificados, a partir dos símbolos originais (i.e., os dados a serem transmitidos). Para explicar os fountain codes é normalmente feita uma analogia com uma fonte de água: qualquer pessoa pode encher um copo na fonte, não importa quais as gotas de água que enchem o copo, apenas quantas gotas estão no copo, porque no final o resultado é o mesmo – um copo cheio de água. Analogamente, o mesmo se passa numa tranmissão que use fountain codes: não importa o conjunto de símbolos codificados que são recebidos, apenas a quantidade de símbolos recebidos: após a descodificação, o resultado são os símbolos originais. Um fountain code é ideal se os K símbolos originais podem ser recuperados a partir de quaisquer K símbolos codificados. Geralmente, na prática, os fountain codes são conhecidos por terem algoritmos de codificação e descodificação muito eficientes, e por conseguirem recuperar os K símbolos originais a partir de qualquer conjunto de K. símbolos codificados com alta probabilidade (com K. apenas ligeiramente superior a K). Estes códigos foram idealizados como a codificação ideal para transferir ficheiros (especialmente ficheiros grandes) para mais do que um receptor, provando ser uma maneira muito mais escalável do que por exemplo usando TCP. Os LT codes representam a primeira realização praticamente viável de fountain codes. Subsequentemente, os Raptor codes foram desenvolvidos, baseados em parte nos LT codes, para melhorar (diminuir) a complexidade computacional e a probabilidade de falha. Para tal, aplicam um “précódigo” aos símbolos originais antes de codificá-los. Os Raptor codes já foram usados em vários standards, nomeadamente de streaming de vídeo em redes broadcast, e também são utilizados em sistemas militares e de comunicação de emergência após desastres. O primeiro Raptor code a ser adoptado em vários standards, foi o R10. Entretanto, na vanguarda dos Raptor codes está o standard RaptorQ. Dada a natureza crítica dos sistemas onde estes códigos são utilizados, nós achámos que seria relevante estudar a sua resiliência perante faltas maliciosas. Estes códigos foram conceptualizados para corrigirem faltas acidentais, e fazem-no incrivelmente bem: os RaptorQ, por exemplo, têm uma probabilidade de falha (i.e., não conseguirem recuperar os símbolos originais após a operação de descodificação) na ordem dos 10−5 para um overhead de apenas 1 símbolo (i.e., K. = K + 1). Nesta dissertação nós relatamos a nossa investigação sobre a robustez do código RaptorQ perante faltas maliciosas injectadas por um atacante com controlo da rede (i.e., que pode eliminar pacotes, por exemplo através de um router infectado). Para além disso descrevemos, tanto quanto sabemos, a primeira concretização do RaptorQ, além da empresa1 que os desenvolveu originalmente. Tencionamos transformar a nossa implementação num projecto de código aberto. Começamos por contextualizar os cenários onde a utilização de fountain codes é relevante, e por vezes quase que necessária. A seguir abordamos a evolução dos fountain codes, culminando numa descrição mais detalhada do código RaptorQ. Prosseguimos para a nossa implementação de uma biblioteca completamente compatível com o standard do IETF RFC 6330 (onde o RaptorQ está especificado). Testámos a sua resiliência, primeiro contra faltas acidentais, para verificar que os valores da probabilidade de falha obtidos na prática, estavam congruentes com os valores disponíveis na literatura. De seguida, estabelecemos um ataque de prova de conceito que permite que, escolhendo os pacotes que passam, mas perdendo relativamente muitos pacotes, consigamos forçar 100% de probabilidade da descodificação falhar. Entretanto, visto ser necessário perder um grande número de pacotes, o ataque pode ser facilmente detectado, pois para a maioria dos valores de K testados seria quase um ataque de Denial-of-Service (DoS). Com base no raciocínio do nosso ataque inicial, nós aperfeiçoamos o ataque, reduzindo o número de pacotes perdidos para vários valores de K para apenas entre 1% e 2% dos pacotes a transmitir. Estes valores tornam o ataque muito viável, pois dificultam muito a sua detecção. Também discutimos como este ataque poderia ser efectuado quando a comunicação é feita através de um canal seguro, onde as mensagens são cifradas. Isto é possível visto o ataque ser directamente ao desenho do standard, e independente do conteúdo das mensagens. Por fim, discutimos as implicações prácticas deste ataque, e propomos algumas possíveis soluções, que dificultariam o ataque, tornando-o inexiquível na práctica. Estas soluções podem ser facilmente adaptadas às implementações existentes e ao próprio standard. As contribuições principais do nosso trabalho, podem ser resumidas em: 1. Uma implementação do standard do IETF RFC 6330, que especifica o código RaptorQ, e uma avaliação dos valores de probabilidade de falha do código RaptorQ, comparando os nossos resultados com os disponíveis na literatura; 2. Uma prova de conceito de que o código RaptorQ pode ser quebrado se as faltas forem arbitrariamente maliciosas, e um algoritmo que permite refinar esse ataque, reduzindo ao mínimo o número de pacotes que têm de ser eliminados; 3. Algumas ideias e tácticas para ajudar a execução do ataque quando canais cifrados são utilizados; 4. Um conjunto de possíveis soluções que podem ser adaptadas ao standard e as implementações para tornar o ataque inexequível. Do nosso trabalho, nomeadamente da nossa prova de conceito de que o código RaptorQ pode ser atacado, resultou uma publicação: J. Lopes and N. Neves, “Robustness of the RaptorQ FEC Code Under Malicious Attacks”, in INForum, Évora, September 2013. Entretanto, ainda há material para ser publicado, nomeadamente o nosso ataque aperfeiçoado e as soluções propostas, que pretendemos submeter para publicação a curto prazo.
Forward Error Correction (FEC) is a technique used to recover from erasures that might occur during the transmission of packets. The central idea is for the sender to encode its data in a redundant way using an error-correcting code (ECC). Fountain codes is a class of ECC that allows a potentially limitless sequence of encoded packets to be created from the original data, allowing the recovery of arbitrary losses (with high probability) with small overheads. The most recent fountain code to be standardized by the Internet Engineering Task Force (IETF) is called RaptorQ. It offers enviable decoding complexity and has an overhead failure curve that puts it closest to the ideal fountain code. Given that RaptorQ was conceived with accidental faults in mind, we decided to investigate its robustness in a malicious environment. The motivation is that RaptorQ will be used not only for media delivery but also in critical systems, such as in military and defense scenarios, and as such it might become the target of an attack. The thesis presents our implementation of RaptorQ, which we intend to make public in the near future (to our knowledge, the first for this code). It also evaluates the decoding failure probabilities of RaptorQ and compares them to the ones available in the literature. An attack to the RaptorQ standard was also investigated: first, as a proof of concept, resulting in an inelegant and easily detectable attack; then, it was refined, making the attack much more effective and harder to detect. Finally, we also discuss some possible solutions that could easily be adopted into the standard and its implementations, which would render our attack much harder to execute (or even unfeasible).