著者：イノケンティセノフスキー（rumata888）

退屈なテーマに学生を興味を持ってもらう方法は？遊びの形を学ぶことを与えなさい。かなり昔に、誰かがそのようなセキュリティゲームを思いついた-Capture the Flag、またはCTF。そのため、怠惰な学生は、プログラムを逆にする方法、引用符を挿入する方がよい場所、および独自の暗号化が実行中のスタートでレーキにジャンプするようなものである理由を学ぶことにもっと興味を持っていました。

学生は成長し、今では子供や住宅ローンを持つ経験豊富な専門家がこれらの「ゲーム」に参加しています。彼らは多くのことを見てきましたので、「老人」が泣き言を言わないようにCTFのために仕事をすることは簡単な仕事ではありません。

そして、ハードコアでそれをやりすぎると、この非コアサブジェクトエリアまたは最初の深刻なCTFを持っているチームが爆破されます。

この記事では、今年のCTFZoneファイナルの暗号化タスクを開発する際に、私たちのチームが「うーん、何か新しいもの」と「これはある種の缶」のバランスをどのように見つけたかを説明します。

最終スコアボードCTFZone2020

コンテンツ

1. オプションの紹介：2分でCTFを説明する
2. 暗号が必要であることをどのように理解しましたか
3. スタックの選び方
4. 
   
   4.1. .
   
   4.2. .
5. 
   
   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.

:

, , .

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

---

. . . , — . :

, . .

, . , , .

— :

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

.

:

• - , . ;
• , , .

, , (Prover), (Verifier).

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

, . — .

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

:

1. . ;
2. . , . : .

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)

:

1. .
2. .
3. .

.

. , , , : .

, 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. ( ).
2. .
3. , 1. proof_count.
4. ( proof_count).
5. , .
6. , , .
7. 3.

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

. .

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

$$

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

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

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

$$

$$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=CRC32(x_0)$$

$$$x_1$ ,

$$

$$CRC32(x_1)=y$$

$$$x_1$, 6 ( ). CRC32 :

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

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



$$$CRC32_6$ :

$$

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

$$

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

$$

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

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

$$

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

$$$CRC32_6$ :

1. $$$2^{17}$ $$$CRC32_{FH}$ $$$b_1b_2b_3$ -, $$$b_1b_2b_3$ .
2. $$$CRC32_{SH\_INV}(y)$ $$$b_4b_5b_6$. , -. , . $$$\frac{1}{2^{16}}-\frac{1}{2^{15}}$.
3. : $$$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)$, .

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

$$

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

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

$$

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

, $$$CRC32_{FH}$

$$

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

, , . , . , .

, :

1. Bleichenbacher’s e=3.
2. .
3. .
4. CRC32.
5. .

, .

, , , . - Linux Usermode Kernel CryptoAPI .

, : . SIMD, . , , : . .

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

, . , , $$$1$ , :

1. $$$P′$.
2. $$$1$, , $$$j$.
3. $$$j$- $$$M′$ $$$R$.
4. .

:

$$$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を操作するには、Proverに多くのリクエストを送信する必要があります。複数の連続した呼び出し要求があった場合に、C＆Cサーバーが接続を切断することは望ましくありませんでした。チームがこのような単純で退屈な緩和方法の実装を放棄するために、検証サーバーの機能を多様化しました。

各ラウンドの開始時に、検証サーバーは対応するラウンドのフラグとマトリックスをチームサーバーに配置し、すぐにProof of Knowledgeプロトコルのインスタンスを実行して、フラグを元に戻します。その後、検証サーバーが30秒ごとに呼び出され、フラグが無傷であり、サーバーの動作に異常がないことを確認しました。これを行うために、検証サーバーが呼び出しごとに3つの戦略のいずれかを選択するようにしました。

1. . , . - , SLA ( ).
2. , , . . . - , SLA.
3. . . , , , . , , . SLA.

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

, , . .

, , . , , . , .

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

, , !