[CRIPTOGRAFÍA] Stream Cipher - HC-128/HC-256

Cifrado de flujo

Esta semana investigamos sobre cifras de flujo. A diferencia de el cifrado por bloques que utiliza bloques de información de tamaño constante, el cifrado de flujo utiliza un generador de flujo de clave para operar con cada bit o cada caracter del texto plano.

Generalmente el generador es un algoritmo que recibe una entrada aleatoria (una clave) y a partir de esta genera una salida datos continua pseudoaleatoria.

Para generar esta salida, se aplica un algoritmo hash a la contraseña de longitud variable y se obtiene una contraseña de longitud fija.

Se puede utilizar una contraseña tan larga como la cantidad de datos que se cifran, lo cual es una de las fortalezas de los sistemas de cifrado.

HC-256

Escogí un algoritmo llamado HC-256. HC-256 es un cifrado de flujo diseñado para proporcionar cifrado masivo de software a gran velocidad mientras que permite una gran confianza en su seguridad. Su variante HC-128 fue presentado como un candidato eSTREAM y fue uno de los 4 finalistas en el perfil de software.

HC-128 y HC-256 son algoritmos adecuados para microprocesadores superescalares modernos y futuros. Sus pasos se pueden calcular en paralelo tanto de entrada como salida.

La velocidad de codificación de HC-128 llega a 3,05 ciclos / byte en un procesador Intel Pentium

M mientras que HC-256 llega a los 4.2 ciclos / byte en un procesador Intel Pentium 4.

Algoritmo

El proceso de cifrado para HC-256 consiste en lo siguiente:

• Inicialmente se necesita una clave (K) de 256 bits y un vector de inicialización (IV) de 256 bits.
• Internamente, consiste en dos tablas secretas (P y Q), cada una contiene 1024 palabras de 32 bits.
• EL flujo de clave (s) es generado del mismo algoritmo. La salida de 32 bits del paso i es denotada como si. Así que s = s0 || s1 || s2...

Hay 6 funciones en el algoritmo. Para g1(x) y h1(x) la tabla Q es usada como S-box y para g2(x) y h2(x) la tabla P es al S-box.

donde x = x3 || x2 || x1 || x0, x es una palabra de 32 bits, x0, x1, x2 y x3 son 4 bytes, x3 y x0 son los bytes mas y menos significativos respectivamente.

El código en python de estas formulas es como sigue:

	def F1(x):
	fun1 = ((x>>7) ^ (x<<(32-7)))
	fun2 = ((x>>18) ^ (x<<(32-18)))
	fun3 = (x>>3)
	return (fun1 ^ fun2 ^ fun3)
	def F2(x):
	fun1 = ((x>>17) ^ (x<<(32-17)))
	fun2 = ((x>>19) ^ (x<<(32-19)))
	fun3 = (x>>10)
	return (fun1 ^ fun2 ^ fun3)
	def G1(x,y):
	fun1 = ((x>>10) ^ (x<<(32-10)))
	fun2 = ((y>>23) ^ (y<<(32-23)))
	fun3 = Q[(x^y) % (1024)]
	return ((fun1 ^ fun2) + fun3 % (2**32))
	def G2(x,y):
	fun1 = ((x>>10) ^ (x<<(32-10)))
	fun2 = ((y>>23) ^ (y<<(32-23)))
	fun3 = P[(x^y) % (1024)]
	return ((fun1 ^ fun2) + fun3 %(2**32))
	def H1(x):
	x0,x1,x2,x3 = bin_int(x)
	fun1 = Q[x0]
	fun2 = Q[256 + x1 % (2**32)]
	fun3 = Q[512 + x2 % (2**32)]
	fun4 = Q[768 + x3 % (2**32)]
	return (fun1 + (fun2 % (2**32) + (fun3 % (2**32) + (fun4 % (2**32)))))
	def H2(x):
	x0,x1,x2,x3 = bin_int(x)
	fun1 = P[x0]
	fun2 = P[256 + x1 % (2**32)]
	fun3 = P[512 + x2 % (2**32)]
	fun4 = P[768 + x3 % (2**32)]
	return (fun1 + (fun2 % (2**32) + (fun3 % (2**32) + (fun4 % (2**32)))))

view raw cripto1.py hosted with ❤ by GitHub

Con respecto al proceso de inicialización, serán 4096 pasos antes de generar alguna salida, se expande K y IV dentro de un vector W, esto para actualizar las S-box P y Q.

El código en python para esta parte:

	def expand_Wi(K, IV):
	K = order(K)
	IV = order(IV)
	Ki = []
	Wi = []
	IVi = []
	i=0
	for j in range(8):
	Ki.append((K[i]+K[i+1]+K[i+2]+K[i+3]))
	i+=4
	i=0
	for j in range(8):
	IVi.append((IV[i]+IV[i+1]+IV[i+2]+IV[i+3]))
	i+=4
	i=0
	Wi = Ki+IVi
	i = 16
	for j in range(2543):
	Wi.append(F2(Wi[i-2]) +(Wi[i-7] % (2**32) + F1(Wi[i-15]) % (2**32) + (Wi[i-16] % (2**32) + i % (2**32))))
	i += 1
	i = 0
	for j in range(1023):
	P[i] = Wi[i+512]
	Q[i] = Wi[i+1536]
	i+=1

view raw cripto2.py hosted with ❤ by GitHub

En la ultima parte generaremos el flujo de clave s y se generará por cada paso una salida de 32 bits. También se actualiza cada tabla P o Q dependiendo de los datos que se operan. El código de esta parte es:

	def keygen():
	i = 0
	s = []
	for i in range(4096):
	j = i % (1024)
	if i % (2048) < 1024:
	P[j] = P[j] + (P[j-10 % (1024)] % (2**32) + G1(P[j-3 % (1024)], P[j-1023 % (1024)]) % (2**32))
	s.append(H1(P[j-12 % (1024)])^P[j])
	else:
	Q[j] = Q[j] + (Q[j-10 % (1024)] % (2**32) + G2(Q[j-3 % (1024)], Q[j-1023 % (1024)\
	]) % (2**32))
	s.append(H2(Q[j-12 % (1024)])^Q[j])
	i+=1
	print s

view raw cripto.py hosted with ❤ by GitHub

Y de esta manera con la salida s generamos el flujo de clave que al final solo se aplicara XOR a el mensaje. La cantidad de pasos en el código es fija, pero lo recomendable es que sea indeterminada o bien de largo del mensaje.

El código completo es:

	from random import randint
	P = [randint(0, 2**32)for i in range(1024)]
	Q = [randint(0, 2**32)for i in range(1024)]
	K = "c175c540ce4cfed4ec38294074f63f51"
	IV = "8738320efb379725d158ffc59a95b2cd"
	def order(c):
	x = []
	for i in c:
	x.append(i)
	x.sort()
	y = []
	for i in x:
	y.append(ord(i))
	return y
	def F1(x):
	fun1 = ((x>>7) ^ (x<<(32-7)))
	fun2 = ((x>>18) ^ (x<<(32-18)))
	fun3 = (x>>3)
	return (fun1 ^ fun2 ^ fun3)
	def F2(x):
	fun1 = ((x>>17) ^ (x<<(32-17)))
	fun2 = ((x>>19) ^ (x<<(32-19)))
	fun3 = (x>>10)
	return (fun1 ^ fun2 ^ fun3)
	def G1(x,y):
	fun1 = ((x>>10) ^ (x<<(32-10)))
	fun2 = ((y>>23) ^ (y<<(32-23)))
	fun3 = Q[(x^y) % (1024)]
	return ((fun1 ^ fun2) + fun3 % (2**32))
	def G2(x,y):
	fun1 = ((x>>10) ^ (x<<(32-10)))
	fun2 = ((y>>23) ^ (y<<(32-23)))
	fun3 = P[(x^y) % (1024)]
	return ((fun1 ^ fun2) + fun3 %(2**32))
	def H1(x):
	x0,x1,x2,x3 = bin_int(x)
	fun1 = Q[x0]
	fun2 = Q[256 + x1 % (2**32)]
	fun3 = Q[512 + x2 % (2**32)]
	fun4 = Q[768 + x3 % (2**32)]
	return (fun1 + (fun2 % (2**32) + (fun3 % (2**32) + (fun4 % (2**32)))))
	def H2(x):
	x0,x1,x2,x3 = bin_int(x)
	fun1 = P[x0]
	fun2 = P[256 + x1 % (2**32)]
	fun3 = P[512 + x2 % (2**32)]
	fun4 = P[768 + x3 % (2**32)]
	return (fun1 + (fun2 % (2**32) + (fun3 % (2**32) + (fun4 % (2**32)))))
	def expand_Wi(K, IV):
	K = order(K)
	IV = order(IV)
	Ki = []
	Wi = []
	IVi = []
	i=0
	for j in range(8):
	Ki.append((K[i]+K[i+1]+K[i+2]+K[i+3]))
	i+=4
	i=0
	for j in range(8):
	IVi.append((IV[i]+IV[i+1]+IV[i+2]+IV[i+3]))
	i+=4
	i=0
	Wi = Ki+IVi
	i = 16
	for j in range(2543):
	Wi.append(F2(Wi[i-2]) +(Wi[i-7] % (2**32) + F1(Wi[i-15]) % (2**32) + (Wi[i-16] % (2**32) + i % (2**32))))
	i += 1
	i = 0
	for j in range(1023):
	P[i] = Wi[i+512]
	Q[i] = Wi[i+1536]
	i+=1
	def keygen():
	i = 0
	s = []
	for i in range(4096):
	j = i % (1024)
	if i % (2048) < 1024:
	P[j] = P[j] + (P[j-10 % (1024)] % (2**32) + G1(P[j-3 % (1024)], P[j-1023 % (1024)]) % (2**32))
	s.append(H1(P[j-12 % (1024)])^P[j])
	else:
	Q[j] = Q[j] + (Q[j-10 % (1024)] % (2**32) + G2(Q[j-3 % (1024)], Q[j-1023 % (1024)\
	]) % (2**32))
	s.append(H2(Q[j-12 % (1024)])^Q[j])
	i+=1
	print s
	def bin_int(x):
	x = bin(x)[2:].zfill(32)
	xi = []
	xi.append(x[0:8])
	xi.append(x[9:16])
	xi.append(x[17:24])
	xi.append(x[25:32])
	xi[0] = int(xi[0], 2)
	xi[1] = int(xi[1], 2)
	xi[2] = int(xi[2], 2)
	xi[3] = int(xi[3], 2)
	xi.sort()
	return (xi[0], xi[1], xi[2], xi[3])
	expand_Wi(K, IV)
	keygen()

view raw cripto_full.py hosted with ❤ by GitHub

La captura de pantalla mostrando el resultado de s:

Seguridad

El cifrado es seguro y casi impenetrable, se han probado con ataques algebraicos sin resultados positivos para el atacante. La salida de el cifrado es proveniente de una función no lineal por lo que recuperar la contraseña es casi imposible.

Sin embargo al conocer parte del texto plano surge el problema, ya que en base a otros ataques de diccionario en combinacion con álgebra se puede recuperar parte de la clave y el vector de inicialización.

Lo que hace seguro el sistema es el uso de claves aleatorias de largo igual que el mensaje y de cifrados múltiples, pero eso es aplicando en todos los algoritmos en general. Lo que le da la seguridad extra es el uso de las tablas S-box P y Q que reciben cambios casi en cada paso, lo que la vuelve difícil de decifrar sin la clave.

Fuentes:

Wikipedia
Link 1
Link 2
PDF oficial
PDF de HC-128