Contents

L3HCTF2021

阿巴阿巴,周末白天忙了一整天学校的事,晚上挂机跑了一晚还是没跑出来捏

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$

and question-44644 on stackexchange says its a problem of Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

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:

which from this article

https://gitee.com/ljahum/images/raw/master/img/20211115110741.png

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[0],pubkey[1]]
#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()

https://gitee.com/ljahum/images/raw/master/img/20211118165619.png

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

https://gitee.com/ljahum/images/raw/master/img/20211118163035.png

Obviously,the primitives is not what we should focus on


https://gitee.com/ljahum/images/raw/master/img/20211118163842.png

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