Autor: Innokenty Sennovsky (rumata888)

Como fazer um aluno se interessar por um assunto chato? Dê ao aprendizado uma forma de brincar. Há muito tempo atrás, alguém surgiu com um jogo de segurança - Capture the Flag ou CTF. Portanto, os alunos preguiçosos estavam mais interessados em aprender como reverter programas, onde é melhor inserir aspas e por que a criptografia proprietária é como pular em um ancinho com uma inicialização rápida.

Os alunos cresceram, e agora profissionais experientes com crianças e hipotecas participam desses "jogos". Eles viram muito, então fazer uma tarefa para a CTF para que os "velhos" não chorem não é uma tarefa fácil.

E se você exagerar com o hardcore, as equipes que têm essa área de assunto não essencial ou o primeiro CTF sério vão ser destruídas.

Neste artigo, contarei como nossa equipe encontrou um equilíbrio entre “hmm, algo novo” e “isso é algum tipo de lata”, desenvolvendo a tarefa de cripta para as finais do CTFZone este ano.

Placar final CTFZone 2020

Placar final CTFZone 2020

Conteúdo

Introdução opcional: explicando CTF em 2 minutos
Como entendemos que precisávamos de uma cripta
Como escolhemos a pilha
4.1. .

4.2. .
5.1. :

5.2. :

5.3.

: CTF 2

, 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 adjacência

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

.

- , . ;
, , .

, , (Prover), (Verifier).

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

Multiplicação e transposição de matrizes

, . — .

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$ :

Produto das funções 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$ .
.

Exemplo

$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.

, , !

Criptukh autoescrito: vulnerável por design ou a história de uma tarefa de CTF

Conteúdo

: CTF 2

,

.

.

:

:

More articles: