Foro de elhacker.net

Hola

La duda que tengo esta en este paper, punto 4.1 Software:

https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/gcm-spec.pdf (https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/gcm-spec.pdf)

Segun lo que puedo entender la variable P es una representacion de un elemento primitivo en gf(2), el modulo f es la variable R.

La x es un byte, tiene unas 256 conbinaciones, las tablas M son de 256 elementos.

Mas o menos todo esto lo llevo bien, si vamos a la pag 9, en (3) se puede observar la variable P que es el polinomio α.

En la pag 14 tenemos el algoritmo numero 3, con este podriamos computar las tablas M, los 65,535 bytes/key si no me equivoco. Doy por sentado de que con el algortimo 3, ya podria crear todas las tablas, cifrando la cadena de de 128 bits de 0s con el codigo.

Pero no acabo de entender del todo la variable P del algritmo 3.

Perdon si no se me entiende bien, estoy algo liado.

Saludos.

La representacion del finite field GF(p^n) se puede realizar mediante el quotient ring de F_p(x)/f(x) donde f(x) es un polinomio irreducible sobre (over) GF(2) de grado n. Pero resulta, que la definición se puede realizar mediante un elemento primitivo, que es a su vez un cero de un polinomio irreducible.

Y te preguntarás, ¿cómo que un cero de un polinomio irreducible? ¿si un polinomio es irreducible no tiene ceros verdad? Bueno f(x) está over GF(2) y no tiene ceros ahí, cierto, pero y sobre una extensión, es decir, la x que entra a f(x) en vez de estar over GF(2) esté over GF(2^2) si su grado es 2. Puede que tenga un cero llamado alpha, y alpha sería un polinomio over GF(2) en vez de ser un elemento in GF(2). El over y el in lían mucho, over es que los coeficientes del polinomio estan definidos sobre GF e in GF significa que el polinomio esta en GF y sus  coeficientes en la base.

Por lo tanto podemos realizar tablas de multiplicación, exponenciales, aditivas, negativas, bases polinomiales en espacios vectoriales, vamos, muchisimas cosas.

Matemáticamente, digamos que tenemos una extensíon E sobre el campo F, puede ser GF(2^2) sobre GF(2) imaginate. Si yo te doy un poly irred sobre GF(2) que obviamente no tiene ceros en GF(2), encuentro un polinomio alpha en la extensión E tal que f(alpha)=0 entonces decimos que alpha es algebraica sobre el campo F.

Ahora mismo, creo que lo que te diría sobre el algoritmo te liaría aún más. Te recomiendo que cojas lo más parecido al RFC, compares, y postees de nuevo por aquí a ver si lo puedo simplificar para que se entienda desde el punto de vista de la computación. Resumiendo, leyendo las descripciones, por ejemplo V.P, V.P^2 etc quizá haga referencia a que P es un poly en alpha sobre GF(2) y que va tomando los coeficientes alpha^i y multiplicandolos por V (lo que es un shifteo como se ve arriba en el paper).

Si tengo (a^5+a^4+a^2).(a^3+a^2) sería (a^5+a^4+a^2).a^3 + (a^5+a^4+a^2).a^2. La a es alpha. Creo que entiendo eso, por lo que te digo que si me pasas algo más estandar mejor. Esto sería aprovechar la propiedad distributiva tomando alpha como la "x" (con el valor primitivo). Recuerda que estamos en F[ a ]/f(a) en vez de F[ x ]/f(x) debido a las relaciones anteriormente dichas.

Fíjate en este ejemplo utilizando Zech's Logarithms:

https://en.wikipedia.org/wiki/Zech%27s_logarithm#Examples

Métodos generales para aritmética en finite fields:

https://en.wikipedia.org/wiki/Finite_field_arithmetic

En este PDF situate en la página 19 y verás como también referencian el uso de las tablas logaritmicas para computar multiplicaciones, entre otras.

https://web.stanford.edu/class/ee392d/Chap7.pdf

EDIT=Una pena que el foro no tenga mathjax, sería mas fácil de escribir y leer notación.

Saludos.

Hola

El de metodos generales, me recuerdo que ya lo lei en su dia, por el tema de AES. Voy a leer con calma los dos restantes.

Creo que ya cada vez lo tengo mas claro, tambien me preocupa mucho el peso de 64K que tienen las tablas, y cada vez que quiera cambiar el codigo volver a calcular y el espacio en memoria, pero eso ya es otra historia.

He visto que se pueden hacer tablas de 4-bit, y ocuparia unos 8,192 bytes, y solo consumiria un pelin mas de recursos, pero el espacio baja mucho.

Pero ya tengo bastante lio de momento, gracias por el apoyo.

Saludos.

Realmente lo que estás haciendo es díficil, ya que entender un proyecto entero, por fases y algoritmos lleva semanas, pues tienes que entender bien cada parte. No te fustres, sigue el camino. Las dudas estarían bien acumularlas y cuando no puedas avanzar más, estudiar y responder tus propias preguntas. Te puedo decir que hace un año me inicié en una rama de la crypto de la cual no tenía ni idea, y a día de hoy, me veo con un nivel fuertísimo y leyendo lo que los expertos suben sin problema. Si lo tienes por hobby y te gusta, en poco tiempo veras grandes resultados.

En mi rutina utilizo Sage y Wolfram Mathematica. Traen métodos para reducir modulo f(x) y un sinfín más. Si no en C++ utilizo NTL que es una librería que es un All in 1. Trae lo básico de number theory y aritmética en GL(n,p), GL(n,p^e), GF(p), GF(p^n), creo que es incluso mejor utilizar éstas que rollear tus propios métodos aritméticos para la crypto.

Cuando no tengo ordenador, o el ejercicio que me planteo a mi mismo es pequeñito para encontrar contradiciones o simplemente curiosidades para investigar, utilizo las siguientes técnicas para realizar multiplicaciones en finite fields:

Si la función módulo es x^n-1 over F_q entonces dicho finite field es isomorfo al grupo de matrices circulantes over F_q denotado por C_n y multiplicando la matriz del poly p(x) por la 1º columna de la matriz del poly q(x) nos dan p(x).q(x). En este caso C_n  es un group algebra, y su representación como ves nos deja computar en una estructura u otra, al final es lo mismo.

Si la función módulo no es x^n-1 entonces podemos linearizar un polinomio, esto es, coger su representación lineal. Esto es un tema que he descubierto digamos, si quieres hacer muchos productos de p(x), digamos una tupla de  r productos { p(x).q_1(x), ..., p(x).q_r(x) } en vez de invocar el algoritmo convencional r veces, capturamos la transformación lineal de p(x) el cual tendría coeficientes enteros, claro. Entonces nos queda una matriz que representa el producto de p(x) por cualquier polinomio q(x). Sólo tenemos que introducir q(x) como vector (no como polinomio), y multiplicar M_p(x).v_q(x). Es un trucazo, pues calcularía la inversa de p(x) también si haces M^(-1)_p(x). No lo he visto en literatura, pero es algo que cualquiera que conozca los teoremas de representacion lineal de grupos puede llegar a saber.

Otro método típico es el descrito arriba con la propiedad distributiva, cojo p(x)=(a^5+a^4+a^2+1) y q(x)=(a^3+a+1) y p(x).q(x)= p(x)*a^3 + p(x)*a + p(x)*1. ¿Por qué? Bueno, digamos que q(x) es un polinomio, donde a su vez, cada coeficiente se puede tomar como polinomio. Claro está, que nos faltaría reducir dicho producto mod f(x).

Seguramente esto lo encontreís aburrido y/o tedioso de primeras, pero bueno, siempre podeís pedir un ejemplo por aquí.

Saludos.

Tengo que hacer lo que me acabas de decir, una recopilacion de todos los problemas que veo, y de hay sacar una conclusion, ya que no he avanzado mucho desde mi anterior mensaje, he buscado mas informacion tampoco es que haya mucha...

https://crypto.stackexchange.com/questions/57785/gcm-cipher-m0-tables-semantic-questions-on-how-to-implement-gcm?rq=1 (https://crypto.stackexchange.com/questions/57785/gcm-cipher-m0-tables-semantic-questions-on-how-to-implement-gcm?rq=1)

https://crypto.stackexchange.com/questions/67642/gcm-optimisation-using-m-0-and-r-tables-calculation-of-r?rq=1 (https://crypto.stackexchange.com/questions/67642/gcm-optimisation-using-m-0-and-r-tables-calculation-of-r?rq=1)

Ya veo que no soy el unico con problemas xD.

Si, todo lo que ago es por hobby pero con un proposito, tengo mas cosas por hacer, cosas que ni siquiera he planteado, y ahora mismo lo que siento es una perdida de tiempo, ya que no puedo estar profundizando tanto en las cosas, cuando te topas con este tipo de problemas te das cuenta de que no sabes nada...


Si, depende de como se mire estoy inventando la rueda de nuevo, seria mucho mas facil usar la libreria de openssl o cualquier otra, y hacer llamadas, pero no me gusta programar de esa forma me gusta crear mis propias funciones (no me gusta que mis programas solo haya call call call call xD), todos sabemos pasar parametros a funciones y llamarlas (no quiero ofender a nadie) a parte para el proposito que tengo es mejor asi.

Ahora mismo tengo esta rutina para hacer las multiplicaciones:

section .data
 
_R: .quad 0x0000000000000000,0xe100000000000000
 
section .text
globl _mulbl
 
_mulbl:
 
 
pushq %rax
movdqa $-127, %rax         ; rax  == i
pxor %xmm0, %xmm0          ; xmm0 == Z
 
 
_C.0:
 
andq $1, 127(%rax,%r10)    ; %r10 == x
jz _C.1
pxor (%r11), %xmm0         ; %r11 == V
 
_C.1:
 
movdqa (%r11), %xmm1
andq $1, 127(%r11)
jz _C.2
 
psrldq $1, %xmm1
pxor _R, %xmm1
movdqa %xmm1, (%r11)
jmp _C.3
 
_C.2:
 
psrldq $1, %xmm1
movdqa %xmm1, (%r11)
 
_C.3:
 
incq %rax
js _C.0
 
popq %rax
retq
 

Bueno haciendo mis calculos a base de los del paper, sale mas o menos a unos 80-90 OPS por byte, sin tablas. En la pag 12 del documento sale la tabla, 119 OPS en la implementacion del paper.

Si miramos la tabla, con el metodo Shoup’s, mejora notablemente el rendimiento, comparando mi funcion con el Shoup’s de 4-bit, hay mas o menos un 30% de rendimiento superior a la mia.
Pero dudo que mi funcion cause overhead no?

Lo dicho dicho, voy a leer un pelin mas.

Saludos.

Hola

Parace que voy entendiendo mas el paper, voy a explicarlo:

Cuando tengo que multiplicar por la variable P no es mas que un shift a los indices (creo que eso ya me lo has explicado @kub0x). Arriba de la pag 10 tengo el ejemplo de la multiplicacion por X · P y supongo que le de abajo es para multiplicar dos elementos.


Practicamente es lo mismo que el algoritmo 1, que explique en mi anterior duda de la sintaxis, si no me equivoco:


Por lo que entiendo:


Segun los ejemplos de la pag 9 en las formulas (3) (5), serian lo mismo no?

Bien ya en la pag 11 en el ejemplo de la desconposicion de X (7), xi hace referencia a 1 byte de X, pero mi duda esta en P^8i, en el primer for 8·i daria cero y al final cuando i es 15 daria 120. Esa parte no la entiendo mucho la verdad.

Creo que la respuesta esta en estos parrafos:


Pasando al algorimo 3 y a su explicacion arriba, vale creo que entiendo la funcion, en la explicacion cuando dice esto:



Partiendo de que el valor de i es 64, Ese ciclo multiplicaria por P ocho veces si no me equivoco.

Bien y en la parte de la multiplicacion por P:


Y las 247 adiciones seria:


Estoy en lo cierto?

Creo que con eso ya bastaria para crear la tabla M0, pero no entiendo lo de las elevacion a P a 8, 128 o i.

Saludos y gracias.

Voy a dejar mis avances, creo que ya casi lo tengo, el algoritmo numero 3 el de la creacion de la tabla M0 es de la siguiente manera:


Eso crearia la tabla M0 de 4096 bytes a partir de H, pero tengo la siguente duda, ya que me quedaria por crear la tabla de R que son 1024 bytes. Supongo que se refiere a esto:


Otra cosa que aun no he entendido es en el algoritmo 2 a la hora de usar las tablas M0, en la directiva byte(X,i), no la he encontrado documentada en el paper, pero supongo que tomara el byte de X segun el valor de i, pero no entiendo lo siguiente, en el caso de ser el valor de X "0xff" se haria un XOR a Z con esa tabla, pero como estan las tablas enumeradas? No se si me explico.

Saludos.

Hola,

hace un tiempo que no comento en este post. Estudiando el campo de los finite fields, hace un tiempo di con una representación del producto de dos polinomios o elementos de GF(p^e) mediante operaciones en un algebra de matrices. Es decir, GF(p^e) es isomorfo a un algebra matricial, donde cada matriz representa un polinomio p(x) en GF(p^e) o F_q como lo quieras llamar.

Por lo tanto, dado un polinomio irreducible f(x) modulo p, podemos representar el producto p(x)q(x) = r(x) mediante una operacion Ax = b donde A es una matriz cuadrada que siempre tendrá determinante 1, por lo tanto no singular. x es un vector columna, es decir de n y b igual.

La matriz A en columnas quedaría: A = [p(x), p(x)*x,p(x)*x^2,...,p(x)*x^(n-1)]. Entonces al computar A.(y1,...,yn) obtendremos el producto el producto r(x) de ambos polinomios, como vector es decir en F_q^{n} que es un espacio vectorial (imaginate (1,0,1) en vector es 1+x^2.

Un ejemplito, toma el poly irreducible f(x) = y^4+y^3+1. La matriz A queda:

A =

(https://i.imgur.com/ZhepVca.png)

y por lo tanto r(x)=pq(x) se escribe como un sistema de n ecuaciones no lineales en 2n variables:

x1 y1 + x4 y2 + (x3 + x4) y3 + (x2 + x3 + x4) y4,
x2 y1 + x1 y2 + x4 y3 + (x3 + x4) y4,
x3 y1 + x2 y2 + x1 y3 + x4 y4,
x4 y1 + (x3 + x4) y2 + (x2 + x3 + x4) y3 + (x1 + x2 + x3 + x4) y4

Ahora selecciona un p(x) y q(x) en este finite field. Múltiplica y comprueba que el sistema obtiene r(x).

Con este sistema puedes computar incluso las inversas, poli caracteristico, traza, trabajar en extensiones etc

Lo mismo pasa con los linearised polynomials, al final son matrices que definen la misma transformación lineal.

Saludos.

Hola

Agradezco el apoyo, ya tengo algo terminado, cuando tenga todo listo lo subire, yo tambien hace tiempo que no digo nada por el echo que ahora mismo estoy haciendo otra cosa, como arreglarme la moto xD, no es broma.

A el codigo que subi esta mal, en casi todo, no se que me fumaria aquel dia, ya pondre el bueno.

Saludos.

Estaría bien que pusieras por aquí el code de multiplicar dos elementos en GF(p^n). Así podemos comparar costes y si resulta mejor te facilito el código de multiplicación, el cual es matricial. Por lo demás, que siga todo bien.

Saludos.

Hola

Cuanto tiempo ha pasado ya, disculpas por abandonar el tema pero he tenido que ocuparme de otras cosas.

Aqui dejo el codigo, lo he testeado a mano siguiendo el algoritmo del PDF del NIST el 1. Testeado con 1 byte.

Se que se puede mejorar, pero no he encontrado un TEST VECTOR para este algoritmo, como los que hay en el PDF de AES al final de todo.

He pensado en contruir todo el PAPER del NIST y luego retomar esto de las las tablas, no se o ire tirando.

.section .text
.globl _start
.align 16
 
_start:
 
pxor %xmm0, %xmm0                        # xmm0 | Z
movdqu %xmm1, (%rsp)                     # rsp  | x
movdqu %xmm1, -16(%rsp)                  # rsp  | V
 
_l02:
 
movq $-16, %rax                           # contador byte
 
_l01:
 
xorq %r8, %r8                          # contador bit 
movq $-8, %r9
 
_l0:
 
btq %r8, 16(%rsp, %rax)                 # compruebo el bit  de el primer byte
jnc _l1                                  # si el bit es 0,  paso a LSB
 
movdqu -16(%rsp), %xmm3
pxor %xmm3, %xmm0                        # si el bit es 1, Z xor V, paso a LSB
 
_l1:
 
btq $63, -8(%rsp)                        # compruebo el ultimo bit 127 LSB 1 (V)
jc _l2
 
movq -8(%rsp), %rbx
shlq $63, %rbx
shrq $1, -8(%rsp)
shrq $1, -16(%rsp)                       # LSB(V)=0
orq %rbx, -16(%rsp)
 
jmp _l3
 
_l2:
 
movq -8(%rsp), %rbx
shlq $63, %rbx
shrq $1, -8(%rsp)                        #LSB(V)=1
shrq $1, -16(%rsp)
orq %rbx, -16(%rsp)
xorq $0x00000000000000e1, -16(%rsp)
 
_l3:
 
incq %r8
incq %r9
js _l0
 
incq %rax
js _l01

El codigo en realidad no es muy bueno, comparandolo con las tablas GCM, y ni hablar del paso de parametros. Y todas las operaciones las realizo en memoria.

Me gustaria encontrar un test vector de este algoritmo, si alguien sabe algo por favor que me lo diga, o que me confirme que el codigo opera bien.

Saludos.

Hola, cuanto tiempo ha pasado, deje de lado el problema por otros asuntos pero ya lo tengo resuelto, y de vez en cuando leo el foro y me acorde de este problema que publique. Y no me gusta dejar las cosas colgadas.

Bien, el ultimo codigo que comparti esta mal, interprete erroneamente el algoritmo y la multiplicacion de galois de GCM.

Lo que sucede es que GCM toma los bytes en little-endian y los bits en big-endian, hay estaba el problema a parte de algunas tonterias mas.

Por ejemplo el polinomio f = 1 + α + α2 + α7 = 0x87(10000111) pero en realidad es  0xe1 (11100001) ya que como dije anteriormente los bit son representados en big-endian.

Pues podemos aplicar todo eso al algoritmo de multiplicacion, que sucede que el bit menos significativo 0 es realidad es 127, si por ejemplo 0x80, se representa como 0x01. Aqui el codigo donde se puede ver todo lo que digo:

.section .data
 
R: .quad 0xb32b6656a05b40b6,0x952b2a56a5604ac0
S: .quad 0xffcaff95f830f061,0xdfa6bf4ded81db03
 
.section .text
.globl _start
.align 16
 
_start:
 
pxor %xmm0, %xmm0                        # xmm0 | Z
movdqu R, %xmm1
movdqu S, %xmm2
movdqu %xmm1, (%rsp)                     # rsp  | Y
movdqu %xmm2, -16(%rsp)                  # rsp-16  | V
 
_l02:
 
movq $15, %rax                           # byte position
 
_l01:
 
movq $7, %r8
 
_l0:
 
btq %r8, (%rsp, %rax)                 # check the bit posotion 0 - 7
jnc _l1                                 # bit equal to 0,  jump to _l1
 
movdqu -16(%rsp), %xmm3
pxor %xmm3, %xmm0                        # bit equal to 1, Z xor V
 
_l1:
 
btq $0, -16(%rsp)                        # check V[127] equal to 1 V = rightshift(V) xor R
jc _l2                                   # equal to 0, V = rightshift(V)
 
 
movq -8(%rsp), %rbx
shlq $63,%rbx
shrq $1, -8(%rsp)
shrq $1, -16(%rsp)                       #Rightshift V in memory
orq %rbx, -16(%rsp)
 
jmp _l3
 
_l2:
 
movq -8(%rsp), %rbx
shlq $63, %rbx
shrq $1, -8(%rsp)
shrq $1, -16(%rsp)                       #Rightshift V in memory and xored by R
orq %rbx, -16(%rsp)
xorb $0xe1, -1(%rsp)
 
_l3:
 
decq %r8                                   #next bit position
jns _l0                                     #r9 equal to 0, jump to next byte
 
decq %rax                                  #byte addition, rax equal to 0, block finished
jns _l01
 
 
//RET Z IN XMM0

R Y S son los valores a multiplicar sacados de un Test vector. Bueno lo dejo aqui. Seguramente que tenga las tablas para algun dia... voy haciendo cuando puedo.

Saludos.

P.D:Cualquier pregunta ya saben.