Breaking PaX ASLR state of the art and future directions tiago,

Breaking PaX ASLR state of the art and future directions tiago, mayhem* {tiago,mayhem}@devhell.org Devhell Labs * the guy in the picture http://www.devhell.org

sobre o co-autor mayhem, o sapo em questão, não pôde chegar em tempo para a apresentação, mas gostaria de dizer às garotas brasileiras: “je veux une petite pipe, s’il vous plait” e acrescenta: “il est parce que je suis français”

sobre o PaX Quite simply: the greatest advance in system security in over a decade that you’ve never heard of Less simply: It provides non-executable memory pages and full address space layout randomization (ASLR) for a wide variety of architectures * PaX: The Guaranteed End of Arbitrary Code Execution

sobre minha relação com o PaX Diversão: construir* ou destruir. Tanto faz. * On the Undecidability of page-level Execution Control on MIPS Based Computers – http://devhell.org/ tiago/projects/undecidable NX on MIPS/

sobre o PaX: paradigmas Sobre a execução arbitrária de dados Definimos como “dado” todo e qualquer tipo de informação escrita ou lida na memória principal, de acesso aleatório, do computador, sem propósito de interferir nas operações primarias executadas pelo computador em questão Definimos como “código” todo e qualquer tipo de informação escrita ou lida na memória principal, de acesso aleatório, do computador, com propósito de interferir nas operações primarias executadas pelo computador em questão

sobre o PaX: paradigmas Sobre a execução arbitrária de dados Definimos como “mapa” um intervalo de memória virtual com características específicas, provido por um serviço supervisor à um “thread” de execução Definimos, finalmente, como “endereço” o valor responsável por identificar uma referência única (contextual ou não) à memória – em nível hierárquico e abstrato qualquer

sobre o PaX: paradigmas NOEXEC - Não-execução de dados . PAGEEXEC . SEGMEXEC . MPROTECT ASLR - Aleatorização da disposição dos mapas de memória . RANDMMAP . RANDEXEC . RANDUSTACK . RANDKSTACK . PIE

sobre o PaX - NOEXEC SEGMEXEC Uma das soluções cabíveis para a implementação de NOEXEC em computadores baseados em i386. Proteção em nível de páginação, para processos não-executivos, faz uso da lógica de segmentação provida por estes computadores e de “virtual memory area mirroring” (desenvolvida pelo PaX Team)

sobre o PaX - NOEXEC VMMIRROR Duplicação da referência de páginas físicas em distintos VMA’s através da divisão do espaço de endereçamento linear em dois – código e dado -, alterando os “segment descriptors” originais

sobre o PaX - NOEXEC * http://www.pjvenda.org/linux/doc/pax-performance/

sobre o PaX - NOEXEC VMMIRROR “Instruction-fetch” em uma página presente na área de dados que não esteja espelhada em uma respectiva VMA no segmento de código, irá gerar uma exceção (page fault) que será tratada pela rotina de tratamento do PaX

sobre o PaX - NOEXEC PAGEEXEC Solução original, multi-arquitetura, para a implementação de NOEXEC. Proteção em nível de páginação, definida pela distinção feita pelo processador sobre o estado das páginas acessadas

sobre o PaX - NOEXEC PAGEEXEC . Em arquiteturas com suporte nativo, faz-se uso do bit “NX” presente nas referências – “Page Table Entry” (PTE) – das páginas tratadas pelo “MMU” em questão . Hacks com a “Translation Lookaside Buffer”, tabela de cache do sistema de tradução de endereços (físico virtual) foram feitos pelo PaX Team para resolver o problema em computadores baseados em i386

sobre o PaX - NOEXEC PAGEEXEC – i386 . Ao sofrer uma exceção do tipo “page fault”, por página não presente na TLB, a rotina de tratamento cria uma PTE marcada (requerendo atenção ou não-presente) e a carrega na DTLB. . Um fetch em alguma página presente na DTLB acarretará em um “page fault”, fazendo com que a rotina de tratamento cheque pelo tipo de requisição. Caso haja um instruction-fetch em uma dessas páginas, o processo é então terminado e informação sobre o contexto é salva nos devidos sistemas de auditoria

sobre o PaX - NOEXEC MPROTECT Restrição das chamadas-de-sistema mmap e mprotect nos seguintes quesitos: . Criação de mapas anônimos com permissão de execução . Criação de mapas executáveis e escrevíveis . Transformar mapas executáveis somente-leitura em executáveis – com exceção de relocações feitas em run-time para objetos PIE. . Transformar um mapa não-executável em executável

sobre o PaX - ASLR ASLR aleatoriza, com distintos níveis entrópicos, a base dos mapas (por instância): . Imagem de código – “.text” . “heap” gerenciada por brk . “heap” gerenciada por mmap . Imagens de DSO’s . “stack” utilizada por processo não-executivo . “stack” utilizada por processo executivo

sobre o PaX - ASLR RANDMMAP Hook na interface de do mmap’’ ({do mmap pgoff, arch get unmapped area, get unmapped area}), onde determina a base do mapa sendo criado (TASK UNMAPPED BASE - bits 12-27) de acordo com delta mmap’’. Tais alteracoes impactam o resultado do sistema dinamico de requisicao de mapas em suas interfaces - brk’’ e mmap’’

sobre o PaX - ASLR RANDEXEC Hook na interface de load elf binary’’ em conjunto com VMMIRROR, que, ao carregar objetos do tipo ET EXEC, determinam como sera criado o espelho dos segmentos relevantes, sendo entao a disposicao desta VMA aleatoria

sobre o PaX - ASLR RANDUSTACK Hook inicial na interface de do execve’’, e posterior em setup arg pages’’ que fara uso de delta stack para determinar a disposicao aleatoria dos bits 12-27 de STACK TOP * “thread stacks” sao alocadas pelo uso de mmap’’, o que implica no uso de RANDMMAP para sua criacao. * com a mudanca do sistema de threading no Linux 2.6, algumas mudancas em RAND{USTACK,MMAP} foram feitas para a adequacao

sobre o PaX - ASLR RANDKSTACK Aleatorizacao da kernel stack mapeada logo apos o termino da user stack - STACK TOP, utilizada como interface para os resultados retornados por servicos do kernel. Implementado por uma modificacao em ret from sys call’’ que chama a rotina responsavel pela criacao da base do mapa - pax randomize kstack’’

sobre o PaX - ASLR PIE Position Indenpendent Executable e’ o nome dado aos objetos executaveis sintetizados em forma de PIC. O PIE vem como solucao mais adequada (menos hackysh) que o seu precursos (RANDEXEC). O resultado e’ que ao ser carregado em memoria, a base das VMAs de codigo (.text), dado (.data) e dado-naoinicializado (.bss), sao definidas por RANDMMAP

sobre o PaX - resultados esperados NOEXEC - Não-execução de dados Quebra do paradigma injeção seguido de execução de código. Mais; frustra a tentativa de executar dados, independente do vetor de injeção ASLR - Aleatorização da disposição dos mapas de memória Quebra do paradigma de mudança de fluxo de código dependente de previsão de endereços absolutos dentro da disposição dos mapas memória

sobre o PaX - ataques On the Effectiveness of Address-Space Randomization Bypassing PaX ASLR Protection

On the Effectiveness of Address-Space Randomization Apoia-se na derivacao de delta mmap’’ por uma busca exaustiva na ordem de 2 16, com um worst-case de 65.536, e um avg-case de 32.768 tentivas Problemas: . Sobre a busca exaustiva acerca de delta mmap’’ . Sobre a derivacao da distancia entre delta mmap’’’ e rotina em questao na libc (ou library de escolha)

On the Effectiveness of Address-Space Randomization Sobre a busca exaustiva de delta mmap’’ . problema de explosao combinatoria determinada por contexto: possibilidade de se fazer buscas na ordem de 2 16 por caracteristicas especificas do apache httpd . timing - de acordo com delay especificado pela criacao do processo: caso GRKERNSEC BRUTE

On the Effectiveness of Address-Space Randomization 8511 config GRKERNSEC BRUTE 8512 bool "Deter exploit bruteforcing" 8513 help 8514 If you say Y here, attempts to bruteforce exploits against forking 8515 daemons such as apache or sshd will be deterred. When a child of a 8516 forking daemon is killed by PaX or crashes due to an illegal 8517 instruction, the parent process will be delayed 30 seconds upon every 8518 subsequent fork until the administrator is able to assess the 8519 situation and restart the daemon. It is recommended that you also 8520 enable signal logging in the auditing section so that logs are 8521 generated when a process performs an illegal instruction.

On the Effectiveness of Address-Space Randomization Sobre a derivacao da distancia entre delta mmap’’ e rotina em questao na libc (ou library de escolha) . Necessidade de acesso aos objetos sintetizados: library e programa vulneravel

Bypassing PaX ASLR Protection Se baseia em uma referencia ‘a GLIBC ( libc start main’’), presente em forma de ponto de retorno salvo no frame 2 graus acima do frame vulneravel, para deduzir a referencia a funcao dentro da instancia da biblioteca em questao

Bypassing PaX ASLR Protection [ libc start main n] [frame de N-1] [variaveis locais] [argumentos] [main p] [frame de N-1] [variaveis locais] [argumentos] [func q] [frame de N-1] [variaveis locais]

Bypassing PaX ASLR Protection Para tal, utiliza-se primitivas de E/S, em conjunto com format-string bugs para vazar a referencia a libc start main’’

Bypassing PaX ASLR Protection Faz-se uso de alguma variante de printf, que deve estar posicionada na mesma pagina que o ponto de retorno da rotina explorada (.) 8048595: 804859a: (.) 80485f4: 80485f9: push call 0x80486bc 80483fc printf call add 8048520 verify 0x10,%esp

Bypassing PaX ASLR Protection A carga tem dois pontos relevantes

Bypassing PaX ASLR Protection Deslocamento relativo referente a chamada do printf’’ em questao, ‘0x9a’ que sobrescrevera’ os primeiros 8 bits do page-offset do ponto de retorno da funcao vulneravel

Bypassing PaX ASLR Protection format-strings responsaveis por vazar o stack frame de interesse "%001 08u" "%002 08u” "%003 08u” "%iii 08u”

Bypassing PaX ASLR Protection Ao retornar, a funcao vulneravel vaza o frame em questao: 00000000 08049820 0000002F 00000001 472ED57C 4728BE10 B9BDB84C 4727464F 080486B0 B9BDB8B4 472C6138 473A2A58 47281A90 B9BDB868 B9BDB888 472B42EB 00000001 B9BDB8B4 B9BDB8BC 0804868C

Bypassing PaX ASLR Protection Problemas: . visto que faz uso de funcoes complexas, como printf’’, tem grandes chances de ter problemas por destruir o frame pointer atual . engenharia demasiado especifica, requerendo contextos e situacoes extremamente restritas

Breaking PaX ASLR state of the art and future directions Surgimento da ideia um sapo (mayhem) um coconut (eu) precisando de uma ideia pro h2hc melhorias em Bypassing PaX ASLR Protection

Breaking PaX ASLR state of the art and future directions Proposta Modificar a engenharia (de Bypassing PaX ASLR Protection) de tal forma que resultasse na viabilidade pratica, em casos reais, da tecnica apresentada

Breaking PaX ASLR state of the art and future directions Premissas Capacidade de deduzir deslocamentos relativos entre blocos de codigo, no programa e na biblioteca . conhecimento previo do resultado da sintetizacao do codigo-objeto referente ao programa vulneravel . conhecimento previo do resultado da sintetizacao do codigo-objeto referente a biblioteca ligada ao programa, contendo a funcao de escolha para se fazer branch-and-link

Breaking PaX ASLR state of the art and future directions Premissas Mais simples e viavel do que parece . grande parte dos administradores utilizam pre-built binaries . ignorando o caso acima (sempre tentando resolver o worst-case), mesmo que o codigo fonte seja reconstruido, com conhecimento do ambiente utilizado (p.exe. definido por uma “distribuicao”) e’ simples reproduzir a imagem dos binarios em questao. Quantos porcento das pessoas constroi sua propria LIBC, binutils, GCC?

Breaking PaX ASLR state of the art and future directions Resultado Blind Information Leakage - “blind info leak” for short

A solucao Apresentacao da solucao i386

A solucao Sobre a notacao . Notacao algebrica em conjunto com notacao de teoria de computacao (logica e booleana) . o token ‘@’ denota que um elemento definido em uma proposicao e’ uma referencia a memoria dentro do espaco de enderacamento do processo em questao

A solucao Proposicoes Atomicas . target referencia ao programa com um conjunto de rotinas vulneraveis aos ataques aqui descritos . virtual area espaco de enderecamento virtual provido pelo program loader, atraves de rotinas no kernel, para um programa correr sobre e desde

A solucao Proposicoes Atomicas . @SP - 32-bit aligned stack pointer atual . target frame referencia ao stack frame controlado pelo ataque . @previous fp - 32-bit aligned frame pointer de grau N-1, tal que o frame pointer de grau N e’ o atual

A solucao Proposicoes Atomicas . @procedure - 32-bit aligned 32-bit offset (RVA) referente a funcao da biblioteca de escolha para se fazer branch-and-link. a derivacao final do ataque que implica na quebra do PaX ASLR . noise referencia a instancia atual (em memoria) da library de escolha

A solucao Proposicoes Atomicas . delta - 32-bit aligned distancia entre @noise e @procedure . page dir - 10 bits page directory index para uma pagina de memoria arbitraria . page entry - 10 bits page entry index para uma pagina de memoria arbitraria

A solucao Proposicoes Atomicas . page offset - 12 bits valor que, combinado a page dir e page entry, cria um endereco efetivo de 32 bits . @branch point - 32-bit aligned posicao em target frame que contem a referencia de memoria para o ponto de retorno no fluxo de codigo da funcao calee. conhecido como return address

A solucao Proposicoes Atomicas . @transform - 32-bit aligned transformacao definida como conjunto de instrucoes do computador, na forma de delta noise procedure . nibble 1 - 4-bit aligned o nibble mais baixo do page entry de @branch point antes da tentativa de ataque

A solucao Proposicoes Atomicas . nibble 2 - 4-bit aligned o nibble mais baixo do page entry de @transform . linear copy - {8,16,32}-bit aligned possibilidades de transformacoes, para o vetor de injecao, sobre o intervalo de target frame

A solucao Proposicoes Atomicas . combinatorial plane conjunto de (possiveis) elementos fora da intersecao nibble 1 nibble 2, definido pela aleatorizacao do ASLR .k a ordem de grandeza de combinatorial plane - 4 2

A solucao Proposicoes Atomicas . exhaustive search determinemos nibble 2 como p exhaustive search esta na forma de :p k P tal que p, k P p 0x0FFF P P k 12 k combinatorial plane

A solucao Proposicoes Atomicas . P,Q P e’ a distancia entre o enesimo @transform e delta Q e’ a distancia entre delta e @procedure .S largura de target frame, tal que P S

A solucao Prova determinemos como S o conjunto de todas as possiveis combinacoes de instrucoes do computador (ISA) presentes na pagina que contem branch point. chamemos C a imagem definida por um sub-conjunto de virtual area, num dado momento, presente num processo corrente de target, tal que o vetor de ataque permita acesso a C definimos como ideal a transformacao sobre um cuja imagem e’ o ataque bem sucedido definimos, entao: T S T : C S A transformacao ideal T, tal que T deriva o ataque bem sucedido A

Blind Info Leak Blind Info Leak consiste em encontrar o T ideal dado um C, S qualquer

Blind Info Leak As Tecnicas Program Analysis sobre C, S definido em duas etapas

Blind Info Leak {Data,code}-flow analysis sobre C para deduzir a disposicao (ou suas possibilades, caso dinamico) de C e os residuos da biblioteca presentes no contexto - noise

Blind Info Leak O Profiler Por decisoes de otimizacao utilizaremos Static e Dynamic Analysis combinados

Blind Info Leak O Profiler A notacao utilizada e’ mista entre linguagem C e simbolos algebricos e de logica. Iteracoes e controle de fluxo sao definidos por indentacao - onde o conjunto de tokens ’ ’ ‘ ’ ‘ ’ , nesta ordem, definem a profundidade do controle de fluxo

Blind Info Leak O Profiler LIBRARY modulo DSO sintetizado com a funcao de escolha para se fazer branch-and-link. PROGRAM objeto {ET EXEC, ET DYN} sintetizado ligado com LIBRARY, carregado em um ambiente full PaX’ed, com a(s) rotina(s) vulneravel em questao

Blind Info Leak O Profiler static code-flow analysis TEXT START inicio da secao .text’’ de PROGRAM TEXT SIZE tamanho da secao .text’’ de PROGRAM TEXT END final da da secao .text’’ de PROGRAM

Blind Info Leak O Profiler for each * branch : PROGRAM LIBRARY - break branch PROGRAM

Blind Info Leak ugly hack atual: GDB script

Blind Info Leak O Profiler dynamic {code,data}-flow analysis for each * a priori break point - RA endereco de retorno da funcao pai - iff RA TEXT START RA TEXT END !saved RA . break RA . save RA

Blind Info Leak Deduzido a possivel disposicao de C e derivado o conjunto de noise e delta em C, temos entao o universo para encontrar o T ideal contido em S

Blind Info Leak Sobre a derivacao de T . manual, revertendo o codigo gerado por um toolchain qualquer . fazendo busca exaustiva no interalo C, S , de forma similar a proposta por [{soeder,permeh,ukai} 04] (hrrmm, falta tempo pra fazer slides sobre isso, explique!) . analise semantica sobre C, S

Blind Info Leak Apendice A O caso de computadores baseados em “RISC”: Instruction Encoding e Addressing Mode

Blind Info Leak Apendice A .set noreorder .cpload 25 .set reorder subu sp, sp,48 .cprestore 16 sw 31,40( sp) sw fp,36( sp) sw 28,32( sp) move fp, sp la 4, LC0 la 25,printf jal 31, 25 la 25,fnc jal 31, 25 sw 2,24( fp) lw 3,24( fp) move 2, 3 j L3

Blind Info Leak Apendice A Pre-LIBC branching (gdb) r Starting program: /home/tiago/t Breakpoint 1, 0x004007c4 in main () Before lazy binding 0x4007c4 main 52 : jalr t9 t9: 0x4009d0 GOT entry for printf 0x4009d0 printf : lw t9,-32752(gp) 0x4009d4 printf 4 : move t7,ra 0x4009d8 printf 8 : jalr t9 0x4009dc printf 12 : li t8,9 0x4009e0 printf 16 : nop Hello 1

Blind Info Leak Apendice A Breakpoint 2, 0x004007e8 in main () After lazy binding 0x4007e8 main 88 : jalr t9 t9: 0x2abb2980 libc reference for printf 0x2abb2980 printf : lui gp,0x17 0x2abb2984 printf 4 : addiu gp,gp,-2464 0x2abb2988 printf 8 : addu gp,gp,t9 0x2abb298c printf 12 : addiu sp,sp,-32 0x2abb2990 printf 16 : sw gp,16(sp) Hello 2 Program exited normally. (gdb)

Blind Info Leak Apendice A Post-LIBC branching tiago@surreal( ) gdb -q -x ./script.gdb ./t Using host libthread db library "/lib/libthread db.so.1". Breakpoint 1 at 0x4007fc Breakpoint 2 at 0x400820 Breakpoint 3 at 0x400838 Breakpoint 4 at 0x400854 Hello 1 Breakpoint 1, 0x004007fc in main () 1: /x t9 0x2abc74a0 call to printf #1 0x4007f4 main 52 : 0x4007f8 main 56 : 0x4007fc main 60 : ---- PC jalr t9 nop lw gp,16(s8)

Blind Info Leak Apendice A Hello 2 Breakpoint 2, 0x00400820 in main () 1: /x t9 0x2abc74a0 call to printf #2 0x400818 main 88 : 0x40081c main 92 : 0x400820 main 96 : ---- PC jalr t9 nop lw gp,16(s8) Breakpoint 3, 0x00400838 in main () 1: /x t9 0x2abe464c call to malloc 0x400830 main 112 : 0x400834 main 116 : 0x400838 main 120 : ---- PC jalr t9 nop lw gp,16(s8)

Blind Info Leak Apendice A Breakpoint 4, 0x00400854 in main () 1: /x t9 0x2abe4cb0 call to free 0x40084c main 140 : 0x400850 main 144 : 0x400854 main 148 : ---- PC Program exited normally. (gdb) jalr t9 nop lw gp,16(s8)

Acknowledgements O título original, “Breaking PaX ASLR in the Wild”, foi modificado pela não-determinação estatística da aplicabilidade das teorias aqui apresentadas e formalizadas em larga escala. O trabalho apresentado neste documento foi teorizado e desenvolvido num curto período de tempo e representa, o que acreditamos ser, o início de novas direções na avaliação e determinação formal na exploração de vulnerabilidades desta classe. Trabalhos futuros devem ser apresentados com generalizações e tratamento de casos especiais.

Acknowledgements Gostaria de agradecer à diversas pessoas, responsáveis por contribuir de alguma forma para a realização deste projeto. Devhell crew: vous des types rock! Hilbert Alan Kleene; Immutiny Team: Nicolas “coxinha” Waisman, Dave Aitel, “the-great” Bas Alberts, Sinan “noir” Eren, Frank “hieu”; The PaX Team - boszme, fasza, fomufti, huzos, haver, .; JP, Diego Bauche, belou, ga, dvorak, .; Tempest dudes \o/ !!! Especialmente dedicado ao meu irmão “fancy-dancy-etc” tea 3