Verfasser: Innokenty Sennovsky (rumata888)

Wie kann man einen Studenten für ein langweiliges Fach interessieren? Geben Sie dem Lernen eine Form des Spielens. Vor langer Zeit hat sich jemand ein solches Sicherheitsspiel ausgedacht - Capture the Flag oder CTF. Daher waren faule Schüler mehr daran interessiert zu lernen, wie man Programme umkehrt, wo es besser ist, Anführungszeichen einzufügen und warum proprietäre Verschlüsselung wie ein Sprung auf einen Rechen mit einem laufenden Start ist.

Die Schüler sind erwachsen geworden, und jetzt nehmen erfahrene Fachleute mit Kindern und Hypotheken an diesen "Spielen" teil. Sie haben viel gesehen, daher ist es keine leichte Aufgabe, eine Aufgabe für die CTF zu erledigen, damit die „alten Leute“ nicht jammern.

Und wenn Sie es mit Hardcore übertreiben, werden die Teams, die diesen nicht zum Kern gehörenden Themenbereich oder die erste ernsthafte CTF haben, gesprengt.

In diesem Artikel werde ich Ihnen erzählen, wie unser Team ein Gleichgewicht zwischen "hmm, etwas Neues" und "das ist eine Art Dose" gefunden hat, während es die Krypta-Aufgabe für das CTFZone-Finale in diesem Jahr entwickelte.

Endanzeige CTFZone 2020

Endanzeige CTFZone 2020

Inhalt

Optionale Einführung: CTF in 2 Minuten erklären
Wie haben wir verstanden, dass wir eine Krypta brauchen?
Wie wir den Stapel gewählt haben
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.

:

Matrix

, , .

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

. . . , — . :

Matrix

, . .

, . , , .

— :

Adjazenzmatrix

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

.

- , . ;
, , .

, , (Prover), (Verifier).

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

Matrixmultiplikation und Transposition

, . — .

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

Produkt der Funktionen von 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$ .
.

Beispiel

$P'$ (, ) .

Matrix

, . $M'$ $R$ .

Matrix

$P'$ . .

Matrix

, $M'$ .

Matrix

Endgültige Matrix

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

, , !

Selbstgeschriebenes Cryptukh: Verwundbar aufgrund des Designs oder der Historie einer CTF-Aufgabe

Inhalt

: CTF 2

,

.

.

:

:

More articles: