Auteur: Innokenty Sennovsky (rumata888)

Comment intéresser un étudiant à un sujet ennuyeux? Donnez à l'apprentissage une forme de jeu. Il y a assez longtemps, quelqu'un a inventé un tel jeu de sécurité - Capture the Flag, ou CTF. Les étudiants paresseux étaient donc plus intéressés à apprendre à inverser les programmes, où il est préférable d'insérer des guillemets et pourquoi le cryptage propriétaire est comme sauter sur un râteau avec un démarrage en cours.

Les étudiants ont grandi, et maintenant des professionnels expérimentés avec des enfants et des hypothèques participent à ces «jeux». Ils ont vu beaucoup de choses, alors confier une tâche à la FCE pour que les «vieux» ne se plaignent pas n'est pas une tâche facile.

Et si vous en faites trop avec le hardcore, les équipes qui ont ce domaine secondaire ou le premier CTF sérieux seront foudroyées.

Dans cet article, je vais vous dire comment notre équipe a trouvé un équilibre entre «hmm, quelque chose de nouveau» et «c'est une sorte d'étain», en développant la tâche de cryptage pour les finales CTFZone cette année.

Tableau de bord final CTFZone 2020

Tableau de bord final CTFZone 2020

Contenu

Introduction facultative: expliquer le CTF en 2 minutes
Comment avons-nous compris que nous avions besoin d'une crypte
Comment nous avons choisi la pile
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.

:

Matrice

, , .

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

. . . , — . :

Matrice

, . .

, . , , .

— :

Matrice d'adjacence

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

.

- , . ;
, , .

, , (Prover), (Verifier).

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

Multiplication et transposition 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$ :

Produit des fonctions 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$ .
.

Exemple

$P'$ (, ) .

Matrice

, . $M'$ $R$ .

Matrice

$P'$ . .

Matrice

, $M'$ .

Matrice

Matrice finale

, $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 auto-écrit: vulnérable par conception, ou historique d'une tâche CTF

Contenu

: CTF 2

,

.

.

:

:

More articles: