# L3HCTF2021

Contents

## EzECDSA

This challenge use SECP256k1 curve to generate the generator ec system

we get 100 sets of signatures and the task.py tells us the low-8bits of K leak：$kp = K;mod;256$

In there，known nonce is low-8bits

The idea is to convert the determination of a private key from biased k nonces in several ECDSA signatures into instances of the hidden number problem (HNP), and then solve the HNP as a reduction to the closest vector problem(CVP).

At least ,we kwon we can turn sequence S into a Linear structure

and the answer also tells us,how to turn the equation in a HNP

you can write k as

$k = a + 2^\ell b$

then perfect,without any problem

Define  and you have

$xt = u + b$

construct sequence  Then,construct a matrix out of basis vectors:  so,we should to find a beautiful B ,Then make

$S_T=B/p$

$S_U=B$

and if you are palying with a good luck

most likely, you’ll see the next-to-last entry of next-to-last row containing a dA or -dA

unfortunately，the lattice in paper seems not very efficient

and @BitLogiK gives a efficient way to make the boundary valid

His way of constructing denotation:

$T_i=2\cdot2^{\ell}\cdot \frac{R_i}{2^{\ell}\cdot S_i} ;mod;n$

$U_i=(2\cdot 2^{\ell}\cdot \frac{KP_i-H_i}{2^{\ell}\cdot S_i} ;mod;n)+n$

$Q'=2\cdot 2^{\ell}\cdot n$

$C_t=1$

$C_u=q$

new lattice looks like this:  then,the privacy will lay in next-to-last col

Obviously,I

  1 2 3 4 5 6 7 8 9 10 11 12  def test_result(mat, target_pubkey, curve): mod_n = ecdsa_lib.curve_n(curve) for row in mat: candidate = row[-2] % mod_n if candidate > 0: cand1 = candidate cand2 = mod_n - candidate if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve): return cand1 if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand2, curve): return cand2 return 0 

### solve

recv data into a jsonfile and set lattice_attack.py options and get flag by hand

or copy others code to have a happy day 😀

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68  #! python3 import icecream import string from icecream import * from pwnlib.util.iters import mbruteforce from pwn import * from hashlib import sha256 from tqdm import tqdm from rich.progress import track from rich.traceback import install install() # ----------------------------------- table = string.ascii_letters+string.digits from Crypto.Util.number import * io = remote('0.0.0.0',23331) def gopow(): s=io.recvuntil("XXXX+".encode("utf-8")) s=io.recvuntil(")".encode("utf-8")) suffix=s[:-1] s=io.recvuntil("==".encode("utf-8")) s=io.recvuntil("\n".encode("utf-8")) cipher=s[1:-1].decode() ic(cipher) ic(suffix) # ic("AAAA".encode() + suffix) # ic(sha256("AAAA".encode() + suffix).hexdigest()) proof = mbruteforce(lambda x: sha256(x.encode() + suffix).hexdigest() == cipher, table, length=4, method='fixed') ic(proof) io.sendlineafter("Give me XXXX:", proof) gopow() pubkey=eval(io.recvline()) data={} from tqdm import tqdm from os import system data["curve"]="SECP256K1" data["public_key"]=[pubkey,pubkey] #data["message"]="0".encode("utf-8") data["known_type"]="LSB" data["known_bits"]=8 data["signatures"]=[] for i in tqdm(range(100)): io.recvuntil("ge:".encode("utf-8")) io.sendline("0".encode("utf-8")) io.recvuntil("r =".encode("utf-8")) ( ()) r=int(io.recvline()) io.recvuntil("s =".encode("utf-8")) s=int(io.recvline()) io.recvuntil("kp =".encode("utf-8")) kp=int(io.recvline()) io.recvuntil("hash =".encode("utf-8")) hsh=int(io.recvline()) (data["signatures"]).append({"r":r,"s":s,"kp":kp,"hash":hsh}) f=open("data.json","w") import json f.write(json.dumps(data)) f.close() system("python3 lattice_attack.py -f data.json") d=eval(input("plz input the ans\n")) io.sendline(str(d).encode("utf-8")) io.interactive() ### The curse of ECDSA nonces

In the question-44644 on stackexchange we know how to solve HNP of bias nonce ecdsa

And Minerva: The curse of ECDSA nonces shows us the attack in detail Obviously，the primitives is not what we should focus on remove U to raise speed？

• So mul $2^\ell$to T and U to

• add a N to U

So，we make make an effort to make the boundary valid? :D