Right after the Lantern Festival, we (Never Stop Exploiting abbr. NeSE) participated in bi0sCTF. I spent a whole day on the crypto challenges, most of which are well-designed and impressive. This writeup includes all 6 crypto challenges in this CTF.

## lalala, 80 solves

### Source Code

1 | from random import randint |

### Solution

Just a few equations. We are given 100 equations and there are 10 unknown variables denoted as . In every equation, we have three parameter lists : , and which meet:

The unknown monomials are all in the form of and there are total 100 possible monomials which can be perfectly linearized with 100 equations. That’s it! Linearization and gaussian elimination.

### Exp

Sage 9.2

1 | from out import p, output |

## rr

### Source Code

1 | from Crypto.Util.number import * |

### Solution

This is an awesome challenge. I love the way to solve discrete logarithm with modulus that seems strongly safe. This challenge gives two ciphertext of `flag`

:

If all coefficients are known, we can easily construct two polynomials and in . Computing the polynomial of and yields the solution of flag.

### Discrete Logarithm Over

Things are far from that simple. Denote as for simplicity. The output list is obfuscated by power in and is a strong prime :

Let’s focus on the first case , which I encountered in some previous competitions.

We require a bit of finesse to transform the above equation, achieved by raising both sides of the equation to the power of q simultaneously :

By Fermat’s little theorem, the equation can be rewritten as follows:

Expand the right side :

That is:

where is known and can be fully recovered.

Talk is cheap, let’s show the code:

1 | from data import ks, rr, n, c1, c2 |

Now we focus on solving the discrete logarithm over in the general form. Given and a safe prime , solve for such that :

Let , and , we can first compute by downgrading the equation to mod or doing -digit expansion similarly

After is recovered, the equation becomes :

We have circled back to the case of , this time we can solve for . We can repeat until which means the computable discrete logarithm is up to for modulo . That’s why we restrict to be less than .

**Remarks**

When , . Therefore, we actually downgrade the equation to mod and solve for in the same way as the trivial case . The sage codes show the details:

1 | def binomial_dlog_sub(y,g,p,q,r=2): |

`binomial_dlog`

function works for composite modulo if we pass in parameter ! You can see this function working in challenge Katyusha’s Campervan with composite modulo.

I find some other solutions from the discussion in discord:

- Discrete logarithm modulo powers of a small prime.
- Using -adic Ring in sage to compute discrete logarithm ：
`Zpr(y).log() / Zpr(g).log()`

.

### Polynomial

Now we have polynomials in

If you don’t care about efficiency, use the following simple Euclidean division :

1 | def gcd(g1, g2): |

I recommend using the method for polynomial. You can find an implementation in jvdsn’s crypto-attacks. Then we derive the common root of which is the flag.

### Exp

1 | from Crypto.Util.number import long_to_bytes |

## daisy_bell, 18 solves

### Source Code

1 | from Crypto.Util.number import * |

### Solution

Classic coppersmith for RSA partial key leakage. We have high bits of denoted as and 955 low bits of denoted . The high bits of denoted as can also be derived from and .

where .

We use the following equations:

Then we have polynomials:

In this writeup, we use polynomial as the coppersmith polynomial. I recommend the coppersmith repository from Kiona. It can automate parameter tuning and works fine for this challenge.

### Exp

Sage

1 | from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic |

## Katyusha’s Campervan

### Source Code

1 | from Crypto.Util.number import * |

### Solution

Another RSA partial key leak challenge. Let , we have:

where ( is the same size with ).

Let , we can solve for using multivariate-coppersmith from coppersmith repository mentioned in daisy bell.

After the factorization of , we need to compute the discrete logarithm over which is mentioned in challenge rr. Check the detailed analysis there.

Some papers are related to the scenarios of `Katyusha's Campervan`

and `daisy_bell`

. Put it here for later need:

- Some Applications of Lattice Based Root Finding Techniques
- New Results for Partial Key Exposure on RSA with Exponent Blinding

### Exp

Sage

1 | from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic |

## challengename

### Source Code

1 | from ecdsa.ecdsa import Public_key, Private_key |

### Solution

This modulo is from the standard curve secp256r1. By validating the points from remote server, we can make sure that the curve for ECDSA is exactly secp256r1. Note that the digesting results from `md5`

hash is only 128 bit while the ECDSA is defined in 256-bit curve, the short nonce attack can be applied in this case! Two signatures are enough to recover private key by the lattice theory.

By the way, the intended solution is the nonce reuse attack by exploiting the flaw of `bigsur`

implementation. Here are two writeups using the nonce-reuse attack :

- https://berliangabriel.github.io/post/bi0s-ctf-2024/
- https://gist.github.com/Hisokap3/f446034f6d6ca9bcfeee05c1dad0aaa4

### Exp

Not optimized attack, probabilistic exp.

1 | from hashlib import md5 |

## predictable, 9 solves

This challenge did not provide the source code. By the description :

Can you help me test out this PRNG I implemented? I’m inserting a backdoor, but I’m sure you can’t find it. Oh btw, I did some optimizing, so version 2 is faster. You can still try out version 1 though. They’re the same anyway.

And the information from `nc`

port :

1 | $$ nc 13.201.224.182 32291 |

It must be Dual-EC prng with a backdoor. If you’re not familiar with Dual EC, try to search it in google and read relative blog. You can also read my blog if you are familiar with Chinese. I will not explain Dual EC and its backdoor in this blog.

I did not solve this challenge during this CTF since I did not realize the timing information in period of `computing parameters`

.

### Timing Attack

The timing information can be obtained from the refresh frequency of `\r`

. The time intervals between two adjacent `\r`

occurrences are as follows :

1 | [Log] 1 Time info: 0.4543850680001924 |

For curve `secp192r1`

, there are exactly 192 `\r`

occurrences. We guess the `Computing parameters`

means the fast scalar multiplication process (similar to fast power ) for elliptic curve point associated with backdoor `d`

. Then the longer time interval stands for bit `1`

and the shorter one stands for bit `0`

.

I finally recovered the bits of `d`

in version 1 since in version 2, the network latency in China affects the timing information a lot.

### Exp

Sage exp only works for version 1 and curve secp192r1.

1 | from pwn import remote, context |