O título acima não dá ideia do quão interessante é esta descoberta. O texto a seguir é a minha interpretação da descrição detalhada que pode ser vista em https://www.openwall.com/lists/oss-security/2024/01/30/7.
A rigor esta falha é um risco de segurança, presente há mais de 30 anos na biblioteca C do GNU (glibc), podendo afetar inúmeras aplicações que utilizem a função qsort.
O Que Faz a Função qsort()
A função qsort é uma rotina de ordenação relativamente genérica, que recebe quatro parâmetros:
- Um ponteiro para o início dos dados
- A quantidade de elementos
- O tamanho de cada elemento
- Um ponteiro para a rotina de comparação de elementos
A julgar pelo nome, espera-se que esta rotina utilize o algorítimo quicksort para ordenar os dados diretamente na área onde estão ("in-place"). Aqui temos a primeira surpresa: normalmente qsort() usa um merge sort. O quicksort só é usado se o tamanho dos dados for acima de um certo valor ou se der erro na alocação da área de memória usada para a ordenação pelo merge sort. Provavelmente isso deve ao fato do quicksort ter um excelente tempo médio, mas um péssimo pior caso (veja os meus artigos sobre odernação).
O bug ocorre quando qsort() usa o quicksort, mas não no algorítimo quicksort propriamente dito. O quicksort é um algorítimo recursivo, onde os dados a serem ordenados vão sendo dividos em parte cada vez menor. Quando o tamanho de um pedaço fica abaixo de um limite (tipicamente 4), é usado um insetion sort para terminar a ordenação.
Neste insertion sort é inicialmente colocado o menor dos elementos na primeira posição e isto é usado para limitar a ordenação dos demais. É aqui que mora o perigo.
A Rotina de Comparação dos Elementos
A rotina de comparação recebe ponteiros para os dois elementos a comparar e deve retornar um valor negativo se o primeiro elemento for menor que o segundo, zero se forem iguais ou positivo se o primeiro for maior que o segundo.
A documentação avisa que esta rotina precisa ser transitiva: se a é maior que b e b é maior que c, então a tem que ser maior que c.
Existem várias formas de implementar a comparação. Quando se trata de inteiros, a tendência natural (e errada) é usar a subtração. Por que errada? Porque em casos limites pode ocorrer um overflow na subtração. Normalmente números inteiros são armazenados na notação complemento de 2. Para n bits, o valor máximo é 2^(n-1)-1 e o valor mínimo -2^(n-1). Por exemplo, se usarmos 8 bits, o valor máximo é 127 e o mínimo -128. Se subtrairmos -128 de 0, o resultado seria +128 mas será interpretado como -1. Ou seja, a comparação por diferença faz com que 0 seja considerado menor que -128.
Juntando Tudo para Causar o Erro
Vamos supor que você saiba que um programa usa a rotina qsort() da glibc com uma rotina de comparação que usa a subtração (ou outra implementação que não seja transitiva) para ordenar um conjunto de dados que você fornece.
Para causar o bug você precisa:
- Fornecer um conjunto grande de dados e/ou limitar a memória disponível para o programa para obrigar o usao do quicksort
- Preparar um conjunto de dados onde o valor incorreto seja colocado na primeira posição na etapa de insertion sort
O resultado (se você conseguir atingir todas estas condições) será a escrita fora da área original de dados. Transformar isso em uma forma controlada de ataque é ainda mais complexo.
Conclusão
Apesar da imensa quantidade de sistemas e programas potencialmente afetados, o risco de isto ser explorado é muito baixo. Resta uma história interessante sobre algorítimos, comparações e as limitações da notação complemento de 2.
Nenhum comentário:
Postar um comentário