¿Puede un circuito de hardware combinatorio sin entradas resolver un problema criptográfico?

0

Soy noob en electrónica pero, en resumen, estoy interesado en estados estables de circuito con no hay entradas que representan una fórmula booleana.

Sea \ $ f \ $ una función hash, digamos md5. Restringir el tamaño de entrada para ser igual a la salida (128 bits para md5).

Cryptographer dijo que es un problema abierto si hay solución a \ $ f (x) = x \ $ (tratada como una secuencia de bits).

Implementar \ $ f \ $ como circuito combinatorio puro (SIN RELOJ), con 128 \ $ i_k \ $ entradas y 128 salidas \ $ o_k \ $.

Para todos \ $ j \ $, conecte \ $ i_j \ $ con \ $ o_j \ $ para que el circuito no tiene entradas (básicamente bucle el circuito \ $ f \ $).

Enciende.

Medir (posiblemente con un osciloscopio) \ $ i_j = o_j \ $.

Si tienes suerte de alcanzar el estado estable (lógicamente consistente), has resuelto \ $ f (x) = x \ $.

En un establo inestable (sin solución), tal vez uno medirá muy alta frecuencia.

Probablemente esto está bien estudiado, aunque un El ingeniero no pudo encontrar una referencia para el caso general.

  
  1. ¿Hay referencias para esto?

  2.   
  3. Si falla, ¿por qué fallará?

  4.   
  5. Si existe una solución, se sabe por cuánto tiempo.   será encontrado?

  6.   
  7. Si esto tiene sentido, por favor, alguien lo pruebe en algo.   simple, aunque no del todo trivial?

  8.   

Resultados experimentales parciales:

No fue fácil, pero yo convencí a un ingeniero para que lo probara en metal desnudo.

Tome \ $ n \ $ inversores (negación lógica) y enróllelos en un ciclo (básicamente esto corresponde al ciclo gráfico \ $ C_n \ $).

No hay entradas ni salidas.

Para incluso \ $ n \ $ el circuito tiene exactamente 2 estables estados.

Para impares \ $ n \ $, no hay un estado estable desde La fórmula booleana no es satisfactoria.

El ingeniero trabajó con las puertas NAND en un stand.

Experimentalmente, para \ $ n = 4 \ $, el ingeniero alcanzó estado estable Dependiendo de qué puertas NAND eligió, el estado estable difería.

Para \ $ n = 3 \ $ no hubo estado estable. El voltaje estaba en el medio entre 0-1 lógico, Posiblemente con alta frecuencia que su osciloscopio. no se pudo medir.

No confiaría en una simulación de software para esto, podría estar equivocado.

Los experimentos fueron demasiado triviales, por lo que es Posible corriente eléctrica para resolver problemas fáciles. y no resolver problemas difíciles.

Alguien sugirió que esto es "fuerza bruta adiabática", aunque Todavía no puedo encontrar los términos de búsqueda correctos.

    
pregunta Chicho Gosho

2 respuestas

1

El campo general de la lógica digital sin reloj es lógica asíncrona . Se han realizado investigaciones en esta área, pero en realidad no se han comercializado.

Su ejemplo criptográfico puede fallar por dos razones:

  • puede encontrar un ciclo, posiblemente uno largo, que produce una secuencia de valores pero no converge en la solución deseada. Este es un aspecto matemático del problema en lugar de un detalle de implementación.

  • Si usa lógica normal y no tiene algún sistema para mantener la propagación de la señal sincronizada, no calculará lo correcto, ya que algunas partes de la respuesta estarán listas antes que otras, que el turno perturbará la entrada. Consulte el "elemento C de Muller" para obtener una solución a esto.

Su ingeniero debería haberle dicho que estaba reinventando el "oscilador en anillo". Estos a menudo se usan junto con los bucles de bloqueo de fase para producir relojes digitales de alta frecuencia que son un múltiplo de un reloj de entrada sin usar un cristal de alta frecuencia.

    
respondido por el pjc50
0

Está asumiendo erróneamente que tal máquina siempre pasaría por todas las entradas posibles; este no es el caso Puede ingresar un bucle que no abarque todo el espacio de entrada.

Por ejemplo, tratemos de resolver este problema criptográfico:

  

Sea H (n) una función hash, definida así: H (n) = n + 2. Esta función toma cuatro bits y devuelve cuatro bits. Cualquier bit de acarreo (por ejemplo, 15 + 2 = 17 = 10001 ) se ignora (en nuestro caso, H (17) = 1 = 0001 )
  Encuentra x tal que H (x) = 3.

Construyes un circuito que representa el comportamiento de H (n): toma cuatro entradas y cuatro salidas. Su salida actual es 0000 . Ahora, conecte las entradas I1, I2, I3, I4 a las salidas O1, O2, O3, O4. ¿Qué pasa?

  

Instant 0: la salida es 0000 [0].
  Instant 1: la salida es 0010 [2].
  Instant 2: la salida es 0100 [4].
  Instant 3: la salida es 0110 [6].
  Instant 4: la salida es 1000 [8].
  Instant 5: la salida es 1010 [10].
  Instant 6: la salida es 1100 [12].
  Instant 7: la salida es 1110 [14].

     

Instant 8: la salida es 0000 [0].
  Instant 9: la salida es 0010 [2].
  ...

¿A dónde va esto? El circuito recorrerá solo unos pocos estados y es posible que nunca llegue a la solución.

Ahora, pensé en un ejemplo trivial para ilustrar este concepto, pero esto también funciona para funciones de hashing reales como MD5 o SHA1.

Sea I = { 0x00...01 , 0x00...02 , ... 0xff...ff } sea la lista de enteros sin signo de 256 bits, y deje que S(x): I -> I sea la función de hashing SHA256.

Aplique S(x) a cada elemento en I. Es muy probable que encuentre colisiones: es decir, dos valores que tienen el mismo valor (digamos H(0x00...01) = H(0xEE...EE) ). Si existe una colisión, entonces el conjunto I es más grande que su imagen con respecto a S : es decir, hay elementos en I que no tienen una contraimagen, lo que significa que no se pueden obtener mediante un hashing de 256 bits. valor.

TLDR: podría ser matemáticamente imposible resolver un problema usando tu método.

    
respondido por el Giulio Muscarello

Lea otras preguntas en las etiquetas