Gimli, hazlo aún más corto?

25

Soy uno de los autores de Gimli. Ya tenemos una versión de 2 tweets (280 caracteres) en C, pero me gustaría ver qué tan pequeña puede ser.

Gimli ( papel , sitio web ) es un diseño de permutación criptográfica de alta velocidad con alto nivel de seguridad que se presentará en la Conferencia sobre hardware criptográfico y sistemas integrados (CHES) 2017 (25-28 de septiembre).

La tarea

Como de costumbre: para realizar la implementación utilizable de Gimli en el idioma que elija.

Debe poder tomar como entrada 384 bits (o 48 bytes, o 12 sin signo int ...) y devolver (puede modificarse en su lugar si usa punteros) el resultado de Gimli aplicado en estos 384 bits.

Se permite la conversión de entrada de decimal, hexadecimal, octal o binario.

Posibles casos de esquina

Se supone que la codificación de enteros es little-endian (por ejemplo, lo que probablemente ya tenga).

Es posible cambiar el nombre Gimlien Gpero todavía debe ser una llamada a la función.

¿Quién gana?

Este es el código de golf, por lo que gana la respuesta más corta en bytes. Se aplican reglas estándar, por supuesto.

Una implementación de referencia se proporciona a continuación.

Nota

Se ha planteado cierta preocupación:

"Hola pandilla, por favor implementa mi programa gratis en otros idiomas para que no tenga que hacerlo" (gracias a @jstnthms)

Mi respuesta es la siguiente:

Puedo hacerlo fácilmente en Java, C #, JS, Ocaml ... Es más por diversión. Actualmente, nosotros (el equipo de Gimli) lo hemos implementado (y optimizado) en AVR, Cortex-M0, Cortex-M3 / M4, Neon, SSE, SSE-Unrolled, AVX, AVX2, VHDL y Python3. :)

Sobre Gimli

El estado

Gimli aplica una secuencia de rondas a un estado de 384 bits. El estado se representa como un paralelepípedo con dimensiones 3 × 4 × 32 o, de manera equivalente, como una matriz 3 × 4 de palabras de 32 bits.

estado

Cada ronda es una secuencia de tres operaciones:

  • una capa no lineal, específicamente una caja SP de 96 bits aplicada a cada columna;
  • en cada segunda ronda, una capa de mezcla lineal;
  • en cada cuarta ronda, una adición constante.

La capa no lineal.

El cuadro SP consta de tres suboperaciones: rotaciones de la primera y segunda palabras; una función T no lineal de 3 entradas; y un intercambio de la primera y tercera palabras.

SP

La capa lineal.

La capa lineal consta de dos operaciones de intercambio, a saber, Small-Swap y Big-Swap. Small-Swap ocurre cada 4 rondas a partir de la 1ª ronda. Big-Swap ocurre cada 4 rondas a partir de la 3ª ronda.

Lineal

Las constantes redondas.

Hay 24 rondas en Gimli, numeradas 24,23, ..., 1. Cuando el número redondo r es 24,20,16,12,8,4 XOR la ​​constante redonda (0x9e377900 XOR r) a la primera palabra de estado.

ingrese la descripción de la imagen aquí

fuente de referencia en C

#include <stdint.h>

uint32_t rotate(uint32_t x, int bits)
{
  if (bits == 0) return x;
  return (x << bits) | (x >> (32 - bits));
}

extern void gimli(uint32_t *state)
{
  int round;
  int column;
  uint32_t x;
  uint32_t y;
  uint32_t z;

  for (round = 24; round > 0; --round)
  {
    for (column = 0; column < 4; ++column)
    {
      x = rotate(state[    column], 24);
      y = rotate(state[4 + column],  9);
      z =        state[8 + column];

      state[8 + column] = x ^ (z << 1) ^ ((y&z) << 2);
      state[4 + column] = y ^ x        ^ ((x|z) << 1);
      state[column]     = z ^ y        ^ ((x&y) << 3);
    }

    if ((round & 3) == 0) { // small swap: pattern s...s...s... etc.
      x = state[0];
      state[0] = state[1];
      state[1] = x;
      x = state[2];
      state[2] = state[3];
      state[3] = x;
    }
    if ((round & 3) == 2) { // big swap: pattern ..S...S...S. etc.
      x = state[0];
      state[0] = state[2];
      state[2] = x;
      x = state[1];
      state[1] = state[3];
      state[3] = x;
    }

    if ((round & 3) == 0) { // add constant: pattern c...c...c... etc.
      state[0] ^= (0x9e377900 | round);
    }
  }
}

Versión tweetable en C

Puede que esta no sea la implementación utilizable más pequeña, pero queríamos tener una versión estándar de C (por lo tanto, sin UB y "utilizable" en una biblioteca).

#include<stdint.h>
#define P(V,W)x=V,V=W,W=x
void gimli(uint32_t*S){for(long r=24,c,x,y,z;r;--r%2?P(*S,S[1+y/2]),P(S[3],S[2-y/2]):0,*S^=y?0:0x9e377901+r)for(c=4;c--;y=r%4)x=S[c]<<24|S[c]>>8,y=S[c+4]<<9|S[c+4]>>23,z=S[c+8],S[c]=z^y^8*(x&y),S[c+4]=y^x^2*(x|z),S[c+8]=x^2*z^4*(y&z);}

Vector de prueba

La siguiente entrada generada por 

for (i = 0;i < 12;++i) x[i] = i * i * i + i * 0x9e3779b9;

y valores "impresos" por

for (i = 0;i < 12;++i) {
  printf("%08x ",x[i])
  if (i % 4 == 3) printf("\n");
}

así:

00000000 9e3779ba 3c6ef37a daa66d46 
78dde724 1715611a b54cdb2e 53845566 
f1bbcfc8 8ff34a5a 2e2ac522 cc624026

debería volver:

ba11c85a 91bad119 380ce880 d24c2c68 
3eceffea 277a921c 4f73a0bd da5a9cd8 
84b673f0 34e52ff7 9e2bef49 f41bb8d6
code-golf cryptography Biv
fuente
3
Un tweet tiene 140 caracteres, no un 280
Stan Strum
1
Lo sé, por eso cabe en 2;) twitter.com/TweetGimli .
Biv
10
"Hola pandilla, por favor implementen mi programa gratis en otros idiomas para que no tenga que hacerlo"
jstnthms
jajaja Nah ya lo tengo en Python, y puedo hacerlo fácilmente en Java, C #, JS. Es más por diversión. :)
Biv
55
El código de referencia en el sitio web tiene un error crucial, en -roundlugar de --roundsignifica que nunca termina. La conversión --a un guión probablemente no se sugiere en el código :)
orlp

Respuestas:

3

CJam (114 caracteres)

{24{[4/z{[8ZT].{8\#*G8#:Mmd+}__)2*\+.^W%\[_~;&8*\~@1$|2*@@&4*].^Mf%}%z([7TGT]R=4e!=\f=(2654435608R-_4%!*^\@]e_}fR}

Este es un bloque anónimo (función): si desea nombrarlo, Ganexe :G. En CJam, los nombres asignados solo pueden ser letras mayúsculas individuales. Hay espacio para agregar un comentario e# Gimli in CJamy dejar caracteres en un solo tweet.

Prueba en línea

Disección

{                                e# Define a block
  24{                            e# For R=0 to 23...
    [                            e#   Collect values in an array
      4/z                        e#     Transpose to columns
      {                          e#     Map over each column
        [8ZT].{8\#*G8#:Mmd+}     e#       Rotations, giving [x y z]
        __)2*\+.^W%\             e#       => [y^z x^y x^z*2] [x y z]
        [_~;&8*\~@1$|2*@@&4*].^  e#       => [x' y' z']
        Mf%                      e#       Map out any bits which overflowed
      }%
      z                          e#    Transpose to rows
      ([7TGT]R=4e!=\f=           e#    Permute first row
      (2654435608R-_4%!*^        e#    Apply round constant to first element
      \@                         e#    Put the parts in the right order
    ]e_                          e#  Finish collecting in array and flatten
  }fR
}
Peter Taylor
fuente
Por un momento me sorprendió el hecho de que la salida no estaba en hexadecimal (en la prueba en línea). :)
Biv
15

C (gcc), 237 bytes

#define P(a,l)x=a;a=S[c=l>>r%4*2&3];S[c]=x;
r,c,x,y,z;G(unsigned*S){
for(r=24;r;*S^=r--%4?0:0x9e377901+r){
for(c=4;c--;*S++=z^y^8*(x&y))
x=*S<<24|*S>>8,y=S[4]<<9|S[4]>>23,z=S[8],S[8]=x^2*z^4*(y&z),S[4]=y^x^2*(x|z);
S-=4;P(*S,33)P(S[3],222)}}

Probablemente gané bytes con mi método de intercambio, pero es demasiado lindo para no usarlo.

orlp
fuente
perdido o ganado?
HyperNeutrino
@HyperNeutrino Ganó, haciéndome un perdedor :)
orlp
Ah ok: P tiene sentido: P: P
HyperNeutrino
Esto definitivamente es una mejora, pero es algo engañoso usar en unsignedlugar de uint32_t(y el código de OP era algo engañoso usar long) porque la idea detrás del cifrado es que es altamente portátil. (De hecho, fundamentalmente esto ahorra solo 8 bytes).
Peter Taylor
1
@PeterTaylor Aunque mi código es similar, en realidad no estoy compitiendo contra el código de OP. Estoy trabajando bajo las reglas de PPCG, donde debe funcionar con al menos una implementación en una plataforma, y ​​lo hace con gccuna CPU Intel de 32 o 64 bits (y probablemente muchos más).
orlp
4

C, 268 caracteres (268 bytes) usando uint32_t

Nota: dado que el código original usa <stdint.h>y escribe Scomo uint32_t *, creo que el uso de longes un truco para entrar en 280 caracteres a costa de la portabilidad, que es la razón para usar uint32_ten primer lugar. Si, para ser justos en la comparación, requerimos el uso consistente uint32_ty la firma explícita void gimli(uint32_t *), el código original es realmente 284 caracteres, y el código de orlp es 276 caracteres.

#include<stdint.h>
#define R(V)x=S[V],S[V]=S[V^y],S[V^y]=x,
void gimli(uint32_t*S){for(uint32_t r=24,x,y,z,*T;r--;y=72>>r%4*2&3,R(0)R(3)*S^=y&1?0x9e377901+r:0)for(T=S+4;T-->S;*T=z^y^8*(x&y),T[4]=y^x^2*(x|z),T[8]=x^2*z^4*(y&z))x=*T<<24|*T>>8,y=T[4]<<9|T[4]>>23,z=T[8];}

Esto se puede dividir en dos tweets con marcadores de continuación como

#include<stdint.h>
#define R(V)x=S[V],S[V]=S[V^y],S[V^y]=x,
void gimli(uint32_t*S){for(uint32_t r=24,x,y,z,*T;r--;y=72>>r%4*2&3,R(0)R(3)// 1

y

*S^=y&1?0x9e377901+r:0)for(T=S+4;T-->S;*T=z^y^8*(x&y),T[4]=y^x^2*(x|z),T[8]=x^2*z^4*(y&z))x=*T<<24|*T>>8,y=T[4]<<9|T[4]>>23,z=T[8];}// 2/2
Peter Taylor
fuente
El uso de longen mi versión es seguro (con respecto a la portabilidad) porque el tamaño mínimo de un largo es de 32 bits según el estándar (en oposición a int). Las rotaciones de xy yse realizan antes del lanzamiento en longla asignación, lo que las hace seguras (ya que el desplazamiento a la derecha del valor firmado depende de CC). El elenco al volver a uint32_t* S) elimina los bits superiores y nos pone en el estado correcto :).
Biv
2

Java (OpenJDK 8) , 351 343 339 320 318 247 + 56 bytes

Solo un puerto cercano a 1: 1 de referencia para comenzar a jugar golf

void f(int[]x,int y,int z){int q=x[y];x[y]=x[z];x[z]=q;}

s->{for(int r=24,c,x,y,z;r>0;--r){for(c=0;c<4;x=s[c]<<24|s[c]>>>8,y=s[4+c]<<9|s[4+c]>>>23,z=s[8+c],s[8+c]=x^z<<1^(y&z)<<2,s[4+c]=y^x^(x|z)<<1,s[c++]=z^y^(x&y)<<3);if((r&3)==2){f(s,0,2);f(s,1,3);}if((r&3)<1){f(s,0,1);f(s,2,3);s[0]^=0x9e377900|r;}}}

Pruébalo en línea!

Roberto Graham
fuente
1
¿Por qué usar Integeren absoluto? o_O Dado que no usa ningún Integermétodo, no hay razón para no usar ints aquí ...
Olivier Grégoire
@ OlivierGrégoire Creo que solo queda un remanente de mí intentando Integer.divideUnsigned, pero me di cuenta de que puedo tener >>>
Roberto Graham
s[0]^=(0x9e377900|r);(al final): ¿no puedes dejar los paréntesis adicionales?
Clashsoft
Lo mismo con s[4+c]>>>(23).
Clashsoft
1
Usted puede hacer muchos menos cambios y obtener 300: void P(int[]S,int a,int b){int x=S[a];S[a]=S[b];S[b]=x;}void gimli(int[]S){for(int r=24,c,x,y,z;r>0;S[0]^=y<1?0x9e377901+r:0){for(c=4;c-->0;){x=S[c]<<24|S[c]>>>8;y=S[c+4]<<9|S[c+4]>>>23;z=S[c+8];S[c]=z^y^8*(x&y);S[c+4]=y^x^2*(x|z);S[c+8]=x^2*z^4*(y&z);}y=r%4;if(--r%2>0){P(S,0,1+y/2);P(S,3,2-y/2);}}}. Básicamente he realizado los cambios mínimos necesarios para que se compile. Las reglas de precedencia de Java no son muy diferentes a las de C.
Peter Taylor
2

JavaScript (ES6), 231 bytes

s=>{for(r=25;--r;[a,b,c,d,...e]=s,s=r&1?s:r&2?[c,d,a,b,...e]:[b,a,d,c,...e],s[0]^=r&3?0:0x9e377900|r)for(c=4;c--;x=s[c]<<24|s[c]>>>8,y=s[j=c+4]<<9|s[j]>>>23,z=s[c+8],s[c+8]=x^z*2^(y&z)*4,s[j]=y^x^(x|z)*2,s[c]=z^y^(x&y)*8);return s}

Manifestación

Mostrar fragmento de código

Arnauld
fuente
0

Ensamblador x86 de 32 bits (112 bytes)

(__cdecl convención de llamadas)

            pusha
            mov     ecx, 9E377918h
    loc_6:  mov     esi, [esp+24h]
            push    esi
            push    4
            pop     ebx
    loc_E:  lodsd
            ror     eax, 8
            mov     ebp, [esi+0Ch]
            rol     ebp, 9
            mov     edx, [esi+1Ch]
            push    eax
            push    ebp
            lea     edi, [edx+edx]
            and     ebp, edx
            shl     ebp, 2
            xor     edi, ebp
            xor     eax, edi
            mov     [esi+1Ch], eax
            pop     ebp
            pop     eax
            push    eax
            push    ebp
            xor     ebp, eax
            or      eax, edx
            shl     eax, 1
            xor     ebp, eax
            mov     [esi+0Ch], ebp
            pop     ebp
            pop     eax
            xor     edx, ebp
            and     eax, ebp
            shl     eax, 3
            xor     edx, eax
            push    edx
            dec     ebx
            jnz     short loc_E
            pop     esi
            pop     ebp
            pop     ebx
            pop     eax
            pop     edi
            mov     dl, cl
            and     dl, 3
            jnz     short loc_5B
            xchg    eax, ebx
            xchg    esi, ebp
            xor     eax, ecx
    loc_5B: cmp     dl, 2
            jnz     short loc_63
            xchg    eax, ebp
            xchg    esi, ebx
    loc_63: stosd
            xchg    eax, ebx
            stosd
            xchg    eax, ebp
            stosd
            xchg    eax, esi
            stosd
            dec     cl
            jnz     short loc_6
            popa
            retn

Versión tweetable (codificación Base85 en formato z85):

v7vb1h> C} HbQuA91y51A: oWYw48G)? I = H /] rGf9Na> sA.DWu06 {6f # TEC ^ CM: # IeA-cstx7:>! VfVf # u * YB & mP (tuCl * + 7eENBP) $ :) Lh! k } t $ ^ wM51j% LDf $ HMAg2bB ^ MQP
Peter Ferrie
fuente