Esta pregunta es un seguimiento de un comentario de Tobias Kienzler a una respuesta a" ¿Cuál es el propósito de la configuración de "Edad mínima de la contraseña"? ".
Considere la política de contraseñas de que las nuevas contraseñas no pueden ser idénticas a la contraseña actual ni a ninguna de las cinco contraseñas del usuario que preceden a la contraseña actual. Tampoco pueden ser similares a la contraseña actual o cualquiera de estas contraseñas anteriores, donde "similar" se define como la distancia de Levenshtein 2 o menos. (Por el bien de esta pregunta, no asuma ningún requisito de complejidad que no sea seis o más caracteres, una letra y un dígito). Esto protege contra, digamos, "bush41", "clinton42", "bush-43" (que debe detenerse ), "obama44" (que debería estar permitido), y "clinton 45" o "bush 45" (cualquiera de los cuales debe detenerse).
El flujo de cambio de contraseña normal requiere la contraseña actual para que alguien no pueda ejecutar un cambio de contraseña con una cookie de sesión Firesheeped. El flujo de cambio de contraseña alternativo envía un token de restablecimiento a través de otro canal, como correo electrónico, voz o texto. En el flujo ordinario, puedo probar si la nueva contraseña es similar a la actual usando la función de distancia Levenshtein de una biblioteca. Pero no tengo la contraseña anterior; Todo lo que tengo son hash PBKDF2 salados. Tampoco puedo probar la similitud con la contraseña actual si el usuario ingresó un token de restablecimiento de contraseña en lugar de la contraseña actual.
En el comentario mencionado anteriormente, Tobias Kienzler recomendó "calcular todas las mutaciones de la nueva contraseña dentro de la distancia de edición inaceptable, calcular sus hashes y compararlos con hashes de contraseñas antiguas (con las respectivas sales)". En una respuesta a la "Seguridad de la contraseña" , una responda a" ¿Facebook almacena contraseñas de texto sin formato? ", y una respuesta a "¿Cómo puede un sistema imponer un número mínimo de caracteres modificados en las contraseñas, sin almacenar o procesar contraseñas antiguas en texto simple?" , Apsillers, Michał Šrajer y Ori sugirieron algo similar.
Pero no veo cómo es manejable en el hardware actual calcular el conjunto de todas las cadenas con la distancia Levenshtein 2 de una frase de contraseña de más de 20 caracteres y agruparlas todas, especialmente con un hash intencionalmente lento como PBKDF2 y gran conjunto de caracteres como Unicode. Parece que se requieren alrededor de hash h(nc)s , donde h es la longitud del historial (aquí 5), n es el número de caracteres en una contraseña (y, por lo tanto, el número de posiciones en las que puede ocurrir un reemplazo o una inserción), c es el número de caracteres en el conjunto de caracteres (95 para ASCII imprimible o mucho más grande para Unicode imprimible), y s es la distancia de edición máxima para llamar a dos contraseñas "similares".
Entonces, ¿cuál es esta forma computacionalmente factible de probar una contraseña para determinar la similitud con contraseñas anteriores sin almacenar contraseñas anteriores con cifrado reversible? ¿Requeriría aplicar cualquiera o todas las siguientes simplificaciones a la definición de similitud y, de ser así, comprometerían la seguridad del sistema de contraseñas en la práctica?
- Requerir que todos los caracteres en las contraseñas sean ASCII imprimibles (espacio para ~).
- Reduzca la distancia de Levenshtein de una "contraseña similar" a 1.
- Compare solo la contraseña actual por similitud y las contraseñas anteriores solo por identidad.
- Sacrificar la disponibilidad para proteger la confidencialidad de la contraseña Cuando un usuario solicita un cambio de contraseña, bloquee al usuario por el resto del día mientras el sistema enumera todas las contraseñas similares posibles, y no permita que otros usuarios cambien sus contraseñas si hay demasiadas búsquedas de similitud de usuarios.