¿Puede el cifrado dos veces con dos claves en diferentes secuencias llevar al mismo resultado?

4

Estoy buscando un algoritmo de cifrado para uno de mis documentos actuales. El requisito básico es que, supongamos que tengo dos claves k1 y k2, y la E (k1, t) significa cifrar t con la clave k1.

¿Hay algún algoritmo de cifrado que satisfaga que E (k2, E (k1, t)) = E (k1, E (k2, t))?

Sé que el cifrado César cumple el requisito. Pero parece demasiado débil. ¿Hay algún algoritmo más seguro que pueda usarse para mi requerimiento? Gracias!

    
pregunta kevin123 01.03.2013 - 04:16
fuente

3 respuestas

4

Puede usar cualquier cifrado simétrico que funcione generando un flujo de bytes dependiente de la clave que luego se XORed con los datos para cifrar. Este es el caso de la mayoría de los cifrados de flujo ; esto también se aplica a un cifrado de bloque en modo CTR (que prácticamente convierte un cifrado de bloque en una secuencia cifrado).

Dichos cifrados son un poco delicados de usar, porque nunca reutilizará una secuencia determinada dependiente de la clave (que sería el infame "pad dos veces"). Esto significa que una clave dada se usará para cifrar solo un mensaje un , o que usted usa un cifrado de flujo con un vector de inicialización que necesitará su propia gestión. Crucialmente , en su caso, esto significa que no se debe permitir que los atacantes potenciales observen E (k1, t) , E (k2, t) y E (k1, E (k2, t)) , porque esto les permitiría recuperar t (es decir, al XORAR las tres secuencias juntas).

Si su escenario específico hace que la solución de cifrado de flujo no sea aplicable, entonces tendría que usar soluciones más esotéricas que no son estándar, por lo que no se pueden recomendar en la práctica (pero están bien para investigación). Por ejemplo, dados parámetros del grupo Diffie-Hellman (un módulo p y un generador g que es tal que g q = 1 mod p para un primo q que divide p-1 ), un elemento de subgrupo (un gx para algún entero x ) se puede "cifrar" con la clave a elevándola a la potencia a ( E (a, h) = h a mod p ). "Descifrado" implica subir a potencia 1 / a mod q (el módulo inverso q se calcula con algoritmo euclidiano extendido ). Con este algoritmo de "encriptación", obtiene la conmutatividad que busca ( E (a, E (b, h)) = E (b, E (a, h)) ) Y puede publicar E (a, h) , E (b, h) y E (a, E (b, h)) sin revelar h .

... pero eso es solo una variante de Diffie-Hellman. La buena pregunta es entonces: ¿por qué quieres tu cifrado conmutativo? ¿Qué estás tratando de hacer, que Diffie-Hellman no puede hacer?

    
respondido por el Thomas Pornin 01.03.2013 - 13:35
fuente
1

RSA (sin relleno) cumple este requisito, si usa dos pares de teclas diferentes pero el mismo módulo: ( Actualización: no, no lo hace, como señaló Thomas Pornin en los comentarios)

(t^k1)^k2 = t^(k1*k2) = (t^k2)^k1

Si necesita un cifrado simétrico, también funcionará un simple One-Time-Pad (aunque en este caso, las longitudes de las claves deben ser al menos tan grandes como el mensaje, y nunca deben reutilizarse):

(t xor k1) xor k2 = (t xor k2) xor k1

También puede haber otros. Sugiero que busques los algoritmos de encriptación homomórfica para obtener más información, aunque no estoy seguro de que sean realmente conmutativos de la forma que deseas. a (y probablemente no tan fuertes como los que no tienen esta restricción).

Actualización: Algunas notas basadas en sus comentarios:

  • Como las claves nunca tendrán que ser intercambiadas (es decir, la parte que encripta es la única que conoce la clave), entonces la longitud de la clave OTP no es realmente una preocupación;
  • Si el canal que las partes usan para comunicarse entre sí es seguro, entonces no hay necesidad de proteger los datos contra un atacante externo;
  • Si realiza una operación criptográfica pero nunca revela el resultado , entonces no importa si reutilizó o no su clave. Esta es mi comprensión del protocolo (exención de responsabilidad: no soy criptógrafo, tengo un conocimiento muy limitado del tema y puedo estar totalmente equivocado; mi consejo sería, si es posible, seguir un protocolo establecido, como Problema de los millonarios de Yao ):

    Alice                    Bob
    a1, k1, a1 xor k1        a2, k2, a2 xor k2
    a2 xor k2          <==>  a1 xor k1
    a2 xor k2 xor k1         a1 xor k1 xor k2
    

    Si a1 == a2 , entonces los resultados de Alice y Bob serán iguales. El problema ahora es: ¿cómo compararlos? Alice reutilizó k1 , por lo que no puede enviar a2 xor k2 xor k1 a Bob o él podría recuperar k1 (xorándolo con a2 xor k2 ).

    Pero asumiendo que k1 es lo suficientemente grande, ella puede enviar un hash del resultado, de modo que Bob pueda compararlo con su hash de su resultado. Mientras Bob no pueda revertir el hash, no aprende nada sobre k1 . Si k1 fue generado por un CSPRNG, incluso un hash rápido como SHA-512 debería ser lo suficientemente seguro.

    (Nota: Bob también tendría que enviar a Alice su hash para que ella la compare; mientras que este protocolo garantiza que ninguno de los dos obtenga información sobre a1 o a2 más que si son iguales, nada impide que hacer trampa : ambos pueden enviar un hash no relacionado para convencer al otro de que los valores son diferentes, o el primer receptor puede reenviar el mismo hash para convencer al primer remitente de que los valores son iguales)

respondido por el mgibsonbr 01.03.2013 - 04:43
fuente
0

Me sorprende que nadie haya mencionado Cero pruebas de conocimientos todavía. Suena como la definición de lo que estás buscando.

Además, ¿es el requisito que el sistema sea reversible? Si simplemente está demostrando que conoce un cierto valor, tomar HMAC de la combinación de atributo / valor puede demostrar que conocer el valor sin decir cuál es el valor (suponiendo que el otro lado tenga los mismos valores para poder verificar el HMAC).

    
respondido por el Sean Madden 01.03.2013 - 22:34
fuente

Lea otras preguntas en las etiquetas