作者：Innokenty Sennovsky（rumata888）

如何使学生对枯燥的学科感兴趣？给学习一种游戏形式。很久以前，有人想出了这样的安全游戏-夺旗（CTF）。因此，懒惰的学生对学习如何反向程序，在何处插入引号更好以及为什么专有加密就像在运行中起步而行之类的兴趣更加感兴趣。

学生已经长大，现在有孩子和抵押贷款的经验丰富的专业人员参加了这些“游戏”。他们看到了很多东西，因此为CTF安排任务以使“老人”不发牢骚不是一件容易的事。

而且，如果您过度使用硬核，那么拥有非核心学科领域或第一个认真的CTF的团队将被炸毁。

在本文中，我将告诉您我们的团队如何在“嗯，有些新东西”和“这是某种锡”之间找到平衡，并为今年的CTFZone决赛开发了加密任务。

最终计分板CTFZone 2020

最终计分板CTFZone 2020

内容

可选介绍：2分钟内讲解CTF

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

, , .

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

. . . , — . :

, . .

, . , , .

— :

邻接矩阵

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

.

- , . ;
, , .

, , (Prover), (Verifier).

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

矩阵乘法和转置

, . — .

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

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

$P'$ (, ) .

, . $M'$ $R$ .

$P'$ . .

, $M'$ .

最终矩阵

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

, , !

自行编写的密码：容易受设计或一项CTF任务的历史的影响

内容

可选介绍：2分钟内讲解CTF

,

.

.

:

:

More articles: