Click here to load reader

LYRA2: PASSWORDHASHINGSCHEME · PDF file trade-offs entre processamento e memória (Lyra2: Password Hashing Scheme with improved security against time-memory trade-offs) / E. R. Andrade

  • View
    0

  • Download
    0

Embed Size (px)

Text of LYRA2: PASSWORDHASHINGSCHEME · PDF file trade-offs entre processamento e memória...

  • EWERTON RODRIGUES ANDRADE

    LYRA2: PASSWORD HASHING SCHEME WITH IMPROVED SECURITY AGAINST

    TIME-MEMORY TRADE-OFFS

    LYRA2: UM ESQUEMA DE HASH DE SENHAS COM MAIOR SEGURANÇA

    CONTRA TRADE-OFFS ENTRE PROCESSAMENTO E MEMÓRIA

    Tese apresentada à Escola Politécnica da

    Universidade de São Paulo para obtenção

    do Título de Doutor em Ciências.

    São Paulo 2016

  • EWERTON RODRIGUES ANDRADE

    LYRA2: PASSWORD HASHING SCHEME WITH IMPROVED SECURITY AGAINST

    TIME-MEMORY TRADE-OFFS

    LYRA2: UM ESQUEMA DE HASH DE SENHAS COM MAIOR SEGURANÇA

    CONTRA TRADE-OFFS ENTRE PROCESSAMENTO E MEMÓRIA

    Tese apresentada à Escola Politécnica da

    Universidade de São Paulo para obtenção

    do Título de Doutor em Ciências.

    Área de Concentração:

    Engenharia de Computação

    Orientador:

    Prof. Dr. Marcos A. Simplicio Junior

    São Paulo 2016

  • Este exemplar foi revisado e corrigido em relação à versão original, sob responsabilidade única do autor e com a anuência de seu orientador.

    São Paulo, ______ de ____________________ de __________

    Assinatura do autor: ________________________

    Assinatura do orientador: ________________________

    Catalogação-na-publicação

    Andrade, Ewerton Rodrigues Lyra2: Um Esquema de Hash de Senhas com maior segurança contra trade-offs entre processamento e memória (Lyra2: Password Hashing Scheme with improved security against time-memory trade-offs) / E. R. Andrade -- versão corr. -- São Paulo, 2016. 139 p.

    Tese (Doutorado) - Escola Politécnica da Universidade de São Paulo. Departamento de Engenharia de Computação e Sistemas Digitais.

    1.Metodologia e técnicas de computação 2.Segurança de computadores 3.Criptologia 4.Algoritmos 5.Esquemas de Hash de Senhas I.Universidade de São Paulo. Escola Politécnica. Departamento de Engenharia de Computação e Sistemas Digitais II.t.

  • “In practice, the effectiveness of a countermeasure often depends on how it is used; the best safe in the world is worthless if no one remembers to close the door.” Computer at Risk, 1991.

  • AGRADECIMENTOS

    Primeiramente, agradeço a duas pessoas extremamente importantes na minha vida: meu pai, Carlos Lopes Andrade, e minha mãe, Terezinha Aparecida Rodri- gues Andrade (mãe Nega). A vocês o meu muito obrigado por me ajudarem a enfrentar todos os desafios e transpor meus limites, sempre me apoiando, mesmo que muitas vezes tenham se (e me) perguntado quando é que eu iria “começar a trabalhar”.

    A minha irmã, Karla Rodrigues Andrade, pelo sempre presente apoio, com- preensão e demonstração de carinho.

    Também agradeço imensamente ao meu orientador, professor e amigo, Marcos Antonio Simplicio Junior, sempre disponível para longas conversas sobre qualquer que fosse o assunto. Obrigado pela amizade, pelo exemplo, e sobretudo por confiar em mim e me auxiliar durante o desenvolvimento desta tese com seu conhecimento e experiência.

    Aos membros da banca de qualificação e da comissão julgadora, pelos ques- tionamentos, correções, sugestões e comentários.

    Aos amigos e membros do Laboratório de Arquitetura de Redes de Computa- dores (LARC), e também à Prof.ª Tereza Carvalho e ao Prof. Wilson Ruggiero, amigos e coordenadores de diversos projetos dos quais participei. Muito obrigado pelo companheirismo, conhecimento compartilhado, e pelas inspiradas e bem hu- moradas discussões.

    A todos demais professores, alunos e funcionários da Escola Politécnica da Universidade de São Paulo que colaboraram com minha formação, viabilizando a produção desta obra.

    À FDTE (Fundação Para o Desenvolvimento Tecnológico da Engenharia) e à CAPES (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) pelo auxílio financeiro.

    A todos os amigos fiéis que, apesar de muitas vezes separados por quilômetros de distância, continuam sempre disponíveis para uma conversa pelo simples prazer da companhia uns dos outros. E a todos os demais que conviveram comigo durante o desenvolvimento deste trabalho.

    Meus sinceros agradecimentos a todos vocês.

  • RESUMO

    Para proteger-se de ataques de força bruta, sistemas modernos de autentica- ção baseados em senhas geralmente empregam algum Esquema de Hash de Senhas (Password Hashing Scheme – PHS). Basicamente, um PHS é um algoritmo crip- tográfico que gera uma sequência de bits pseudo-aleatórios a partir de uma senha provida pelo usuário, permitindo a este último configurar o custo computacional envolvido no processo e, assim, potencialmente elevar os custos de atacantes tes- tando múltiplas senhas em paralelo. Esquemas tradicionais utilizados para esse propósito são o PBKDF2 e bcrypt, por exemplo, que incluem um parâmetro con- figurável que controla o número de iterações realizadas pelo algoritmo, permitindo ajustar-se o seu tempo total de processamento. Já os algoritmos scrypt e Lyra, mais recentes, permitem que usuários não apenas controlem o tempo de processa- mento, mas também a quantidade de memória necessária para testar uma senha. Apesar desses avanços, ainda há um interesse considerável da comunidade de pes- quisa no desenvolvimento e avaliação de novas (e melhores) alternativas. De fato, tal interesse levou recentemente à criação de uma competição com esta finalidade específica, a Password Hashing Competition (PHC). Neste contexto, o objetivo do presente trabalho é propor uma alternativa superior aos PHS existentes. Es- pecificamente, tem-se como alvo melhorar o algoritmo Lyra, um PHS baseado em esponjas criptográficas cujo projeto contou com a participação dos autores do presente trabalho. O algoritmo resultante, denominado Lyra2, preserva a segu- rança, eficiência e flexibilidade do Lyra, incluindo a habilidade de configurar do uso de memória e tempo de processamento do algoritmo, e também a capacidade de prover um uso de memória superior ao do scrypt com um tempo de proces- samento similar. Entretanto, ele traz importantes melhorias quando comparado ao seu predecessor: (1) permite um maior nível de segurança contra estratégias de ataque envolvendo trade-offs entre tempo de processamento e memória; (2) inclui a possibilidade de elevar os custos envolvidos na construção de plataformas de hardware dedicado para ataques contra o algoritmo; (3) e provê um equilíbrio entre resistância contra ataques de canal colateral (“side-channel ”) e ataques que se baseiam no uso de dispositivos de memória mais baratos (e, portanto, mais lentos) do que os utilizados em computadores controlados por usuários legítimos. Além da descrição detalhada do projeto do algoritmo, o presente trabalho inclui também uma análise detalhada de sua segurança e de seu desempenho em di- ferentes plataformas. Cabe notar que o Lyra2, conforme aqui descrito, recebeu uma menção de reconhecimento especial ao final da competição PHC previamente mencionada.

    Palavras-chave: derivação de chaves, senhas, autenticação de usuários, se- gurança, esponjas criptográficas.

  • ABSTRACT

    To protect against brute force attacks, modern password-based authentication systems usually employ mechanisms known as Password Hashing Schemes (PHS). Basically, a PHS is a cryptographic algorithm that generates a sequence of pseu- dorandom bits from a user-defined password, allowing the user to configure the computational costs involved in the process aiming to raise the costs of attackers testing multiple passwords trying to guess the correct one. Traditional schemes such as PBKDF2 and bcrypt, for example, include a configurable parameter that controls the number of iterations performed, allowing the user to adjust the time required by the password hashing process. The more recent scrypt and Lyra algorithms, on the other hand, allow users to control both processing time and memory usage. Despite these advances, there is still considerable interest by the research community in the development of new (and better) alternatives. Indeed, this led to the creation of a competition with this specific purpose, the Password Hashing Competition (PHC). In this context, the goal of this research effort is to propose a superior PHS alternative. Specifically, the objective is to improve the Lyra algorithm, a PHS built upon cryptographic sponges whose project counted with the authors’ participation. The resulting solution, called Lyra2, preserves the security, efficiency and flexibility of Lyra, including: the ability to configure the desired amount of memory and processing time to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings important impro- vements when compared to its predecessor: (1) it allows a higher security level against attack venues involving time-memory trade-offs; (2) it includes tweaks for increasing the costs involved in the construction of dedicated hardware to attack the algorithm; (3) it balances resistance against side-channel threats and attacks relying on cheaper (and, hence, slower) storage devices. Besides describing the algorithm’s design rationale in detail, this work also includes a detailed analysis of its security and performance in different platforms. It is worth mentioning that Lyra2, as hereby described, received a special recognition in the aforementioned PHC competition.

    Keywords: Password-based key derivation, passwords, authentication, se- curity, cryptographic sponges.

  • RIASSUNTO

    Per prote