Autor: Innokenty Sennovsky (rumata888)

¿Cómo conseguir que un alumno se interese por un tema aburrido? Dale al aprendizaje una forma de juego. Hace bastante tiempo, a alguien se le ocurrió un juego de seguridad de este tipo: Capture the Flag, o CTF. Así que los estudiantes perezosos estaban más interesados en aprender cómo revertir programas, dónde es mejor insertar comillas y por qué el cifrado propietario es como saltar sobre un rastrillo con un comienzo en marcha.

Los estudiantes han crecido, y ahora profesionales experimentados con hijos e hipotecas participan en estos "juegos". Han visto mucho, por lo que hacer una tarea para el CTF para que los "viejos" no se quejen no es tarea fácil.

Y si se excede con el hardcore, los equipos que tienen esta área temática no básica o el primer CTF serio serán destruidos.

En este artículo, les contaré cómo nuestro equipo encontró un equilibrio entre “hmm, algo nuevo” y “esto es una especie de lata”, desarrollando la tarea de cripta para las finales de CTFZone de este año.

Marcador final CTFZone 2020

Marcador final CTFZone 2020

Contenido

Introducción opcional: explicando CTF en 2 minutos

, CTF, — . , CTF- .

: jeopardy attack-defense.

jeopardy . «Jeopardy!», « ». , . , «» . , .

attack-defense (AD) . , — . : attack-defense -10 -20 jeopardy.

AD vulnboxes — , . vulnboxes . — , (checker). , .

, — , . , 5 . . vulnbox , .

, :

vulnbox;
, ;
, .

- CTF, , :

web,
pwn,
misc,
PPC,
forensic,
reverse,
crypto ( , ).

, , jeopardy. , AD . «» , - , CTFZone.

,

CTFZone, , AD.

, AD, , . , . , .

, . . , nonce ECDSA, , .

, . - AD- , . , : . , , .

, ( ), . , .

, , CTF . — .

, , . , ? :)

, , Python. , .

, DEF CON , Python + C ( , ). C, Python , .

, , , .

, , CTF, — Zero Knowledge Proofs of Knowledge (ZKPoK), . , , - , . ZKPoK : - , . .

.

. . . — , .

, , . , , .

— . , . , .

. , , , , , . , 4 : A, B, C, D. A B, C D.

:

Matriz

, , .

, , : , ABCD → BADC. (): B→A→D→C→B.

. . . , — . :

Matriz

, . .

, . , , .

— :

Matriz de adyacencia

, (x, y) (y, x), B D.

.

- , . ;
, , .

, , (Prover), (Verifier).

0. . , : A→B→C→D→A. , , (. . ) . ( ) .

Multiplicación y transposición de matrices

, . — .

1. . , (commitment). , , : , — , . , , .

. ;
. , . : .

2. . , (challenge) $b \in \{0,1\}$ . , ( $b=0$ ) ( $b=1$ ) .

, , — .

3. . , , , , . , , , .

, , . , , .

. , $b$ . $b$ , : $b=0$ , , $b=1$ , . $b$ , . , - ( , ).

, , , 50- , , . , . . , . 25%, — 12,5% . . , .

P.S. Zero Knowledge, - Zero Knowledge Proofs: An illustrated primer. .

. « » = «», « » = «», « » = « ».

:

, , . , , , . :

;
;
16- RANDOMR, ;
RSA- .

RANDOMR , .

, : , DoS- . PKCS#1 v1.5. , , 3 (Bleichenbacher's e=3 signature attack). , 3 (, SAFE_VERSION macro ):

 uint8_t* badPKCSUnpadHash(uint8_t* pDecryptedSignature, uint32_t dsSize){
    uint32_t i;
    if (dsSize<MIN_PKCS_SIG_SIZE) return NULL;
    if ((pDecryptedSignature[0]!=0)||(pDecryptedSignature[1]!=1))return NULL;
    i=2;
    while ((i<dsSize) && (pDecryptedSignature[i]==0xff)) i=i+1;
    if (i==2 || i>=dsSize) return NULL;
    if (pDecryptedSignature[i]!=0) return NULL;
    i=i+1;
    if ((i>=dsSize)||((dsSize-i)<SHA256_SIZE)) return NULL;
    #ifdef SAFE_VERSION
    //Check that there are no bytes left, apart from hash itself
    //(We presume that the caller did not truncate the signature afte exponentiation
    // and the dsSize is the equal to modulus size in bytes
    if ((dsSize-i)!=SHA256_SIZE) return NULL;
    #endif
    return pDecryptedSignature+i;
}

30 :

;
, ;
, .

, .

. , , . , , .

:

, , .

— Python + C. C, 95% . Python . . (, void_p ctypes. 64- 32 ).

Python :

verifier=Verifier(4,4,7)

. , , , : .

, 256. :

-, , 2 ( , ). , 5 , .
-, , .

. , , - . $\frac{1}{16}$ . .

, , 64, $\frac{1}{2^{64}}$ . — .

, — .

. , 3 , :

, "" CRC32;
, SHA-256;
, AES-128 CBC.

$1-7$ , . : CRC32, SHA-256, AES. , CRC32 AES, CRC32.

, :

( ).
.
, 1. proof_count.
( proof_count).
, .
, , .
3.

. (, ). . (simulation mode), . . . , , , . , . , ,

. .

CRC32 SHA-256 , . , (uint16_t), , 8 . , , -. :

H a s h (P a c k (p e r m u t a t i o n)) | H a s h (P a c k (p e r m u t e d_g r a p h)) | H a s h (P a c k (p e r m u t e d_c y c l e))

$Hash(Pack(permutation)) | Hash(Pack(permuted\_graph)) | Hash(Pack(permuted\_cycle))$

. $b$ , , . , , . , , .

AES, : $K_1$ $K_2$ . , , $K_1$ $K_2$ . :

E n c (P a c k (p e r m u t a t i o n), K_{1}) | E n c (P a c k (p e r m u t e d_c y c l e), K_{2}) | P a c k (p e r m u t e d_g r a p h)

$Enc(Pack(permutation),K_1) | Enc(Pack(permuted\_cycle),K_2) | Pack(permuted\_graph)$

$b$ $K_b$ . .

, , AES, ( , , ). , SHA-256, ( ), - , .

CRC32, , , . CRC32 $2^{32}$ . Meet-in-the-Middle (« »), $2^{17}$ .

: , . . MitM , .. .

Meet-in-the-Middle , CRC32. ,

y = C R C 32 (x_{0})

$y=CRC32(x_0)$

$x_1$ ,

C R C 32 (x_{1}) = y

$CRC32(x_1)=y$

$x_1$ , 6 ( ). CRC32 :

$Init$ .
$t_{i+1}=Round(t_i,b_i)$ , ( $t_i$ — , $b_i$ — ).
$Finish$ .

, 6 :

C R C 32_{6} (x) = F i n i s h (R o u n d (R o u n d (R o u n d (R o u n d (R o u n d (R o u n d (I n i t (), b_{1}), b_{2}), b_{3}), b_{4}), b_{5}), b_{6}))

$CRC32_6(x)=Finish(Round(Round(Round(Round(Round(Round(Init()\\,b_1),b_2),b_3),b_4),b_5),b_6))$

$t$ :

Producto de funciones de t

$CRC32_6$ :

C R C 32_{6} = C R C 32_{F H} * C R C 32_{S H}

$CRC32_6=CRC32_{FH}∗CRC32_{SH}$

C R C 32_{F H} = I n i t * R o u n d_{b_{1}} * R o u n d_{b_{2}} * R o u n d_{b_{3}}

$CRC32_{FH}=Init∗Round_{b_1}∗Round_{b_2}∗Round_{b_3}$

C R C 32_{S H} = R o u n d_{b_{4}} * R o u n d_{b_{5}} * R o u n d_{b_{6}} * F i n i s h

$CRC32_{SH}=Round_{b_4}∗Round_{b_5}∗Round_{b_6}∗Finish$

CRC32 . , $Round_{b_i}$ $Finish$ , $CRC32_{SH}$ :

C R C 32_{S H_I N V} = C R C 32_{S H}^{- 1}

$CRC32_{SH\_INV}=CRC32^{−1}_{SH}$

$CRC32_6$ :

$2^{17}$ $CRC32_{FH}$ $b_1b_2b_3$ -, $b_1b_2b_3$ .
$CRC32_{SH\_INV}(y)$ $b_4b_5b_6$ . , -. , . $\frac{1}{2^{16}}-\frac{1}{2^{15}}$ .
: $t=CRC32_{FH}(b_1,b_2,b_3)=CRC32_{SH\_INV}(y,b_6,b_5,b_4)$ , , $y=CRC32(b_1b_2b_3b_4b_5b_6)$ , .

: « , , , — , , ». — , . , :

S I Z E (2 b y t e s) | P A C K E D_D A T A

$SIZE (2\space bytes)\space |\space PACKED\_DATA$

, HASHES — , , $size^2$ $packed\_data$ , . , 6 :

S I Z E (2 b y t e s) | P A C K E D_D A T A | e_{1} | e_{2} | e_{3} | e_{4} | e_{5} | e_{6}

, $CRC32_{FH}$

S I Z E (2 b y t e s) | P A C K E D_D A T A | e_{1} | e_{2} | e_{3}

$SIZE (2\space bytes) \space |\space PACKED\_DATA \space|\space e_1\space|\space e_2\space|\space e_3$

$CRC32_{SH\_INV}$

e_{4} | e_{5} | e_{6}

$e_4\space|\space e_5\space|\space e_6$

4 . . , , — (PRNG ).

C rand, - . Legendre PRF, .

, , $GF(p)$ , - $p$ . , . , $\frac{(p-1)}{2}$ ( 0) .

- , $0$ , , , $\frac{1}{2}$ . , ( — $r≠0$ ) . . $r$ $r^\frac{p−1}{2}=1\space mod \space p$ , . $r$ 50%, , .

$a\in GF(p)$ . Python :

def LegendrePRNG(a,p):
    if a==0:
        a+=1
    while True:
        next_bit=pow(a,(p-1)//2,p)
        if next_bit==1:
            yield 1
        else:
            yield 0
        a=(a+1)%p
        if a==0:
            a+=1

32- $p$ , Meet-in-the-Middle. , $2^{16}+31$ , . , $2^{16}$ 32- , 32 . , — big-endian little-endian, — .

, . Legendre PRNG. $a=1$ 32 . , (, ).

, $a=1+2^{16}$ . $a$ $2^{16}$ , . , , . $a$ , — . , , .

, , . , . , .

, :

Bleichenbacher’s e=3.
.
.
CRC32.
.

, .

, , , . - Linux Usermode Kernel CryptoAPI .

, : . SIMD, . , , : . .

, $M$ $P$ . $M_p$ , : $M_p=P^T⋅M⋅P$ . — . $1$ , $0$ . . $P′$ $M′$ , $R=P′⋅M′$ .

, . , , $1$ , :

$P′$ .
$1$ , , $j$ .
$j$ - $M′$ $R$ .
.

Ejemplo

$P'$ (, ) .

Matriz

, . $M'$ $R$ .

Matriz

$P'$ . .

Matriz

, $M'$ .

Matriz

Matriz final

, $1$ , , $j$ - . , memcpy , SIMD, memcpy . .

- . Zero Knowledge , Python, PEM. , , , .

, .

24 , , . CryptoAPI: AF_ALG, .

, - . .

, , .

, , . , pwn :)

, :

-, C , . ASAN (Address Sanitizer), .
-, , , . , . Libfuzzer , .

: . /dev/urandom randrand, ( Legendre PRF, ) srand(0). , . - AES- .

, . , .

, , . , , — : , , .

Legendre PRNG . , . , .

Proof of Knowledge, . , , . , :

. , . - , SLA ( ).
, , . . . - , SLA.
. . , , , . , , . SLA.

(Bushwhackers) SLA 65%, . , scoreboard, .

, , . .

, , . , , . , .

, https://github.com/bi-zone/CTFZone-2020-Finals-LittleKnowledge. , . , ( ) . . , , . , - CTF.

, , !

Cryptukh autoescrito: vulnerable por diseño o el historial de una tarea de CTF

Contenido

Introducción opcional: explicando CTF en 2 minutos

,

.

.

:

:

More articles: