Título: Duda secreto compartido Shamir
Publicado por: matake en 14 Noviembre 2016, 15:19 pm
Hola,
Estoy trabajando en un proyecto donde quiero tener un segundo factor de autenticación.
En un principio pensé en una pasarela SMS pero como casi seguro al principio no voy a ganar nada .... esto va a superar mis posibilidades financieras.
Así que la idea es emplear solo una vez para inscripcion un SMS y luego una tarjeta de coordenadas (estilo A1 = xxxx , A2 = yyyy etc )
Despues de mucha lectura ... encontre el "sistema de compartición de secretos de Shamir" que parece bastante robusto.
La idea que me surgió es la siguiente:
1. Emplear algún padding para no revelar la longitud de la clave ( el secreto )
Incluso, dicho padding, poder personalizarse para cada usuario con algo fácil a memorizar ( un color una foto etc )
Problema: Dicho secreto compartido sera difícil de memorizar o de escribir por el usuario (supongamos que con el padding lo aumentamos hasta 1024 bits o mas
Lo que he pensado es: generar aleatoriamente dicha tarjeta de coordenadas que van a ser las coordenadas x e y de la gráfica del algoritmo de Shamir.
Entonces al usuario se le pide su contraseña mas dos coordenadas de su tarjeta (eventualmente mas una cosa para el padding) ... se pasa esto a una función js en el lado cliente y se envía al servidor una parte del secreto compartido ( el servidor teniendo la otra parte )
Mi pregunta es:
¿Supone esto (lo de las coordenadas en la tarjeta) alguna vulnerabilidad al sistema de Shamir? ( descartando que si le roban la contraseña y la tarjeta etc)
Saludos y Gracias
Estoy trabajando en un proyecto donde quiero tener un segundo factor de autenticación.
En un principio pensé en una pasarela SMS pero como casi seguro al principio no voy a ganar nada .... esto va a superar mis posibilidades financieras.
Así que la idea es emplear solo una vez para inscripcion un SMS y luego una tarjeta de coordenadas (estilo A1 = xxxx , A2 = yyyy etc )
Despues de mucha lectura ... encontre el "sistema de compartición de secretos de Shamir" que parece bastante robusto.
La idea que me surgió es la siguiente:
1. Emplear algún padding para no revelar la longitud de la clave ( el secreto )
Incluso, dicho padding, poder personalizarse para cada usuario con algo fácil a memorizar ( un color una foto etc )
Problema: Dicho secreto compartido sera difícil de memorizar o de escribir por el usuario (supongamos que con el padding lo aumentamos hasta 1024 bits o mas
Lo que he pensado es: generar aleatoriamente dicha tarjeta de coordenadas que van a ser las coordenadas x e y de la gráfica del algoritmo de Shamir.
Entonces al usuario se le pide su contraseña mas dos coordenadas de su tarjeta (eventualmente mas una cosa para el padding) ... se pasa esto a una función js en el lado cliente y se envía al servidor una parte del secreto compartido ( el servidor teniendo la otra parte )
Mi pregunta es:
¿Supone esto (lo de las coordenadas en la tarjeta) alguna vulnerabilidad al sistema de Shamir? ( descartando que si le roban la contraseña y la tarjeta etc)
Saludos y Gracias
Título: Re: Duda secreto compartido Shamir
Publicado por: kub0x en 16 Noviembre 2016, 19:19 pm
Buenas matake un placer volverte a ver por aquí, un tema bonito el de la autenticación:
Pongamos que conocemos el user/password de cualquier usuario que utilice tu servicio:
- Tarjeta de coordenadas: ampliamente utilizada como sistema de doble autenticación en Bancos y otras entidades. Al introducir users/password te piden una o varias coordenadas de la misma. Los riesgos son la generación de la matriz o el robo de la tarjeta. Si la generación no tiene ninguna tendencia o vulnerabilidad entonces todo iría bien. Para ello utiliza un espacio numérico para cada coordenada digno y pide tres coordenadas distintas al azar. Si tenemos 20 coordenadas cada una con números entre 10^4 y 10^5 - 1 (entre 10.000 y 99.999), el espacio número por coordenadas es de 89.999. Teniendo en cuenta que las coordenadas que se le piden al usuario son distinas (no se repiten) nos queda una Combinación sin repetición de 20 tomando 3 (C(20,3) ):!})
que son 1140 posibilidades con las que puedes jugar. El atacante por cada coordenada tiene una probabilidad de acierto de 
, son 3 coordenadas por lo tanto 
. La probabilidad de acierto por intento es nula, en cada intento cambias la coordenada a pedir y ya. El espacio numérico puede ser inferior.
- Shamir's secret sharing: utilizado para dividir un secreto en n partes donde k participantes pueden reconstruirlo. En este caso n=k puesto que sólo quieres que el usuario y el servidor lo reconstruyan, nadie más interviene en el esquema que desarrollas. Cosas a tener en cuenta. Los coeficientes del polinomio de descartan al generar por primera vez el secreto y deben de ser aleatorios y menores que el módulo primo p. El secreto es conocido por el servidor, así que hashealo y cada vez que lo reconstruyas comparas hashes. El servidor genera {f,a,b,p,s} siendo s el secreto, hashea el secreto lo mete a la DB y evalúa f (la función) en 1 y 2, se queda el valor (1,f(1),p), envía al usuario (2,f(2),p) y el resto lo descarta. todo esto al registrarse el usuario por primera vez. Entonces cuando el usuario inicie sesión enviará su secreto y el servidor con el otro secreto generará un sistema lineal de ecuaciones donde hallará la solución exacta al secreto original. Que sucede aquí, pues que si al usuario le roban su secreto GAME OVER.
- PKI: Cada vez que un usuario se registra se le asigna un certificado de cliente emitido por la entidad certificadora (CA) del servidor. El servidor guarda la clave pública del usuario en la DB. Cada vez que el usuario inicie sesión enviará el certificado de usuario (realmente se dice cliente) y con el mismo unos parámetros dependiendo del algoritmo asimétrico. El server validará el certificado: comprobará que fue firmado por su entidad certificadora y que conoce la clave pública. Después comprobará la firma digital sobre los parámetros enviados y si la validación es correcta habra autenticado al cliente. PROBLEMAS: si le roban la clave privada al usuario -> GAME OVER. Por lo tanto lo óptimo es que el user cifre la private con una clave simétrica.
Espero haberte servido de ayuda, cualquier cosa me dices.
Saludos!
Pongamos que conocemos el user/password de cualquier usuario que utilice tu servicio:
- Tarjeta de coordenadas: ampliamente utilizada como sistema de doble autenticación en Bancos y otras entidades. Al introducir users/password te piden una o varias coordenadas de la misma. Los riesgos son la generación de la matriz o el robo de la tarjeta. Si la generación no tiene ninguna tendencia o vulnerabilidad entonces todo iría bien. Para ello utiliza un espacio numérico para cada coordenada digno y pide tres coordenadas distintas al azar. Si tenemos 20 coordenadas cada una con números entre 10^4 y 10^5 - 1 (entre 10.000 y 99.999), el espacio número por coordenadas es de 89.999. Teniendo en cuenta que las coordenadas que se le piden al usuario son distinas (no se repiten) nos queda una Combinación sin repetición de 20 tomando 3 (C(20,3) ):
- Shamir's secret sharing: utilizado para dividir un secreto en n partes donde k participantes pueden reconstruirlo. En este caso n=k puesto que sólo quieres que el usuario y el servidor lo reconstruyan, nadie más interviene en el esquema que desarrollas. Cosas a tener en cuenta. Los coeficientes del polinomio de descartan al generar por primera vez el secreto y deben de ser aleatorios y menores que el módulo primo p. El secreto es conocido por el servidor, así que hashealo y cada vez que lo reconstruyas comparas hashes. El servidor genera {f,a,b,p,s} siendo s el secreto, hashea el secreto lo mete a la DB y evalúa f (la función) en 1 y 2, se queda el valor (1,f(1),p), envía al usuario (2,f(2),p) y el resto lo descarta. todo esto al registrarse el usuario por primera vez. Entonces cuando el usuario inicie sesión enviará su secreto y el servidor con el otro secreto generará un sistema lineal de ecuaciones donde hallará la solución exacta al secreto original. Que sucede aquí, pues que si al usuario le roban su secreto GAME OVER.
- PKI: Cada vez que un usuario se registra se le asigna un certificado de cliente emitido por la entidad certificadora (CA) del servidor. El servidor guarda la clave pública del usuario en la DB. Cada vez que el usuario inicie sesión enviará el certificado de usuario (realmente se dice cliente) y con el mismo unos parámetros dependiendo del algoritmo asimétrico. El server validará el certificado: comprobará que fue firmado por su entidad certificadora y que conoce la clave pública. Después comprobará la firma digital sobre los parámetros enviados y si la validación es correcta habra autenticado al cliente. PROBLEMAS: si le roban la clave privada al usuario -> GAME OVER. Por lo tanto lo óptimo es que el user cifre la private con una clave simétrica.
Espero haberte servido de ayuda, cualquier cosa me dices.
Saludos!
Título: Re: Duda secreto compartido Shamir
Publicado por: matake en 18 Noviembre 2016, 03:49 am
El placer es mio kub0x.
Gracias por responder. Como siempre claro y conciso en tus respuestas. Me quito el sombrero! ;-)
Pues me di cuenta ahora mismo que mi enfoque era desde el principio equivocado:
Yo pensé en enviar al cliente por SMS (para no tener que ser muy largo) los {a,b,p} en mi caso la p era un nr primo y no la parte suya del secreto ... y que el cliente mismo se genere su parte de secreto ... pero ... me olvide de la "s" que es el secreto original que sin el .... ¿que va a generar ??!! ;D :silbar:
- Lo que hemos hablado en los otros posts pasados sobre AES ya esta aclarado probado y funcional pienso que entre AES y Shamir se me va a ocurrir alguna cosa.
- Sobre la tarjetas de coordenadas he apuntado lo que me dijiste de la longitud de las coordenadas. No se si añado caracteres también y luego empleo los valores ASCII octales , decimales y hexadecimales de los mismos ¿habra alguna mejora?
- Sobre la PKI (he leído cositas de RSA ) pero lo que no me acuerdo ahora es que dicho certificado me parece que el usuario tiene que instalarlo ... ¿o lo acepta el navegador automáticamente?
Si tiene que instalarlo ( cosa que creo que así va a ser ) ... de momento lo descarto ... la cantidad de gente con la que voy a trabajar que no sabe siquiera cambiar el fondo de pantalla ... faltaría esto de que les digo instalar un certificado :laugh:
- Sigo dándole vueltas y estos días ( si no te molesta ) mandare un algoritmo en cual estoy, para darme tu opinión de como esta y poder rectificarlo, mejorarlo.
Un saludo !
Gracias por responder. Como siempre claro y conciso en tus respuestas. Me quito el sombrero! ;-)
Pues me di cuenta ahora mismo que mi enfoque era desde el principio equivocado:
Yo pensé en enviar al cliente por SMS (para no tener que ser muy largo) los {a,b,p} en mi caso la p era un nr primo y no la parte suya del secreto ... y que el cliente mismo se genere su parte de secreto ... pero ... me olvide de la "s" que es el secreto original que sin el .... ¿que va a generar ??!! ;D :silbar:
- Lo que hemos hablado en los otros posts pasados sobre AES ya esta aclarado probado y funcional pienso que entre AES y Shamir se me va a ocurrir alguna cosa.
- Sobre la tarjetas de coordenadas he apuntado lo que me dijiste de la longitud de las coordenadas. No se si añado caracteres también y luego empleo los valores ASCII octales , decimales y hexadecimales de los mismos ¿habra alguna mejora?
- Sobre la PKI (he leído cositas de RSA ) pero lo que no me acuerdo ahora es que dicho certificado me parece que el usuario tiene que instalarlo ... ¿o lo acepta el navegador automáticamente?
Si tiene que instalarlo ( cosa que creo que así va a ser ) ... de momento lo descarto ... la cantidad de gente con la que voy a trabajar que no sabe siquiera cambiar el fondo de pantalla ... faltaría esto de que les digo instalar un certificado :laugh:
- Sigo dándole vueltas y estos días ( si no te molesta ) mandare un algoritmo en cual estoy, para darme tu opinión de como esta y poder rectificarlo, mejorarlo.
Un saludo !