Author: Innokenty Sennovsky (rumata888)

How to get a student interested in a boring subject? Give learning a form of play. Quite a long time ago someone came up with such a security game - Capture the Flag, or CTF. So lazy students were more interested in learning how to reverse programs, where it is better to insert quotes, and why proprietary encryption is like jumping on a rake with a running start.

Students have grown up, and now experienced professionals with children and mortgages participate in these "games". They have seen a lot, so making a task for the CTF so that the “old people” don't whine is not an easy task.

And if you overdo it with hardcore, the teams who have this non-core subject area or the first serious CTF will be blasted.

In this article, I will tell you how our team found a balance between “hmm, something new” and “this is some kind of tin,” developing the crypt task for the CTFZone finals this year.

Final scoreboard CTFZone 2020

Content

1. Optional introduction: explaining CTF in 2 minutes
2. How did we understand that we needed a crypt
3. How we chose the stack
4. How we found the idea for the task
   
   4.1. A. What is the Hamiltonian property of graphs
   
   4.2. B. How to identify yourself using the Hamiltonian cycle
5. How we built the task
   
   5.1. Protocol: top view
   
   5.2. Protocol: internals
   
   5.3. The latest vulnerability
6. How we developed the task
7. How we tested the task
8. How we dealt with cheating
9. Conclusion

Optional introduction: explaining CTF in 2 minutes

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

Proof of Knowledge, . , , . , :

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

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

, , . .

, , . , , . , .

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

, , !