• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Doctoral Thesis
DOI
10.11606/T.3.2016.tde-26082016-150620
Document
Author
Full name
Ewerton Rodrigues Andrade
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2016
Supervisor
Committee
Simplicio Junior, Marcos Antonio (President)
Aranha, Diego de Freitas
Goya, Denise Hideko
Misoczki, Rafael
Ruggiero, Wilson Vicente
Title in English
Lyra2: password hashing scheme with improved security against time-memory trade-offs.
Keywords in English
Algorithms
Computer security
Cryptology
Methodology and techniques of computing
Password hashing scheme
Abstract in English
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 pseudorandom 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 improvements 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.
Title in Portuguese
LYRA2: um esquema de hash de senhas com maior segurança contra trade-offs entre processamento e memória.
Keywords in Portuguese
Algoritmos
Criptologia
Esquema de hash de senhas
Metodologia e técnicas de computação
Segurança de computadores
Abstract in Portuguese
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 criptográ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 testando 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 configurá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 processamento, 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 pesquisa 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. Especificamente, 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 seguranç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 processamento 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 diferentes plataformas. Cabe notar que o Lyra2, conforme aqui descrito, recebeu uma menção de reconhecimento especial ao final da competição PHC previamente mencionada.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2016-08-29
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • ALMEIDA, L. C., et al. Lyra: Password-Based Key Derivation with Tunable Memory and Processing Costs. Journal of Cryptographic Engineering, 2014.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2019. All rights reserved.