Summary Private key can be extracted from ECDSA signature upon signing a malformed input (e.g. a string or a number), which could e.g. come from JSON network input
Note that elliptic by design accepts hex strings as one of the possible input types
Details In this code:
elliptic/lib/elliptic/ec/index.js
Lines 100 to 107 in 3e46a48
1 2 3 4 5 6 7 8
msg = this._truncateToN(newBN(msg, 16));
// Zero-extend key to provide enough entropy var bytes = this.n.byteLength(); var bkey = key.getPrivate().toArray('be', bytes);
// Zero-extend nonce to have the same byte size as N var nonce = msg.toArray('be', bytes);
msg is a BN instance after conversion, but nonce is an array, and different BN instances could generate equivalent arrays after conversion.
Meaning that a same nonce could be generated for different messages used in signing process, leading to k reuse, leading to private key extraction from a pair of signatures
Such a message can be constructed for any already known message/signature pair, meaning that the attack needs only a single malicious message being signed for a full key extraction
While signing unverified attacker-controlled messages would be problematic itself (and exploitation of this needs such a scenario), signing a single message still should not leak the private key
Also, message validation could have the same bug (out of scope for this report, but could be possible in some situations), which makes this attack more likely when used in a chain
PoC k reuse example
1 2 3 4 5 6 7 8 9 10 11 12
import elliptic from'elliptic'
const { ec: EC } = elliptic
const privateKey = crypto.getRandomValues(newUint8Array(32)) const curve = 'ed25519'// or any other curve, e.g. secp256k1 const ec = newEC(curve) constprettyprint = ({ r, s }) => `r: ${r}, s: ${s}` const sig0 = prettyprint(ec.sign(Buffer.alloc(32, 1), privateKey)) // array of ones const sig1 = prettyprint(ec.sign('01'.repeat(32), privateKey)) // same message in hex form const sig2 = prettyprint(ec.sign('-' + '01'.repeat(32), privateKey)) // same `r`, different `s` console.log({ sig0, sig1, sig2 })
Full attack This doesn’t include code for generation/recovery on a purpose (bit it’s rather trivial)
# cnt=0 # for u in a: # print(r[cnt%39],np.average(u)) # cnt+=1 # if cnt%39 ==0: # print("\n")
# print(len(a)) # pos=7 # with open("e.csv", "w") as f: # for i in range((pos)*39,(pos+1)*39): # f.write(r[i%39]+","+",".join([str((a[i][j])-9) for j in range(100)])) # f.write("\n") # for i in range(39): # print("\t".join([str((a[i][j])) for j in range(100)])) # print("\n")
# def calculate_variance(arr): # mean = sum(arr) / len(arr) # variance = sum((x - mean) ** 2 for x in arr) / len(arr) # return variance
deffind_farthest_index(arr): mean = sum(arr) / len(arr) max_distance = -1 farthest_index = 0 for index, value inenumerate(arr): current_distance = abs(value - mean) if current_distance > max_distance: max_distance = current_distance farthest_index = index return farthest_index,max_distance
for pos inrange(39): max_dis_max=-1 max_dis_index=0 for o inrange(100): arr = [a[i][o] for i inrange((pos)*39,(pos+1)*39)] fi,md=find_farthest_index(arr) if md>max_dis_max: max_dis_max=md max_dis_index=fi
""" max_dis_index 0 max_dis_index o max_dis_index p max_dis_index s max_dis_index { max_dis_index p max_dis_index o max_dis_index w max_dis_index e max_dis_index r max_dis_index _ max_dis_index 1 max_dis_index s max_dis_index _ max_dis_index a max_dis_index 1 max_dis_index 1 max_dis_index _ max_dis_index y max_dis_index 0 max_dis_index u max_dis_index _ max_dis_index n max_dis_index 5 max_dis_index 5 max_dis_index d max_dis_index }
"""
"0ops{power_1s_a11_y0u_n55d}"
ezCrypt
This text looks suspiciously like Base64… but something’s not quite right. It seems a bit… compressed?
The flag is 0jkl{1=ake_fl@G_oF_CRyPTO_Cha11!}! I'm kidding. April Fool! There is no flag in this one~ But I can provide you some hint for the other block! Maybe it is a compact representation of IPv6 addresses, at least according to some funny RFCs I read earlier. After that, you might want to learn about RSA, and the extreme difficulty to factor huge numbers, especially when they are the product of two large primes, unless someone had published the result of the factorization. Good luck!
I'm so sorry, I forgot to save the private key to decode the flag. But some supercomputer have already cracked it and uploaded to an online db. Can you find the flag?
n = 0x771b68deea7e2ecd0fa15099ae9085e1a6b163c415bde56c61ec811201d52e456e4a876db6da7af2695e206d9e3b23de02a16f675ad087c4bef3acc6c4e16ab3 e = 65537 c = 0x5641d8b05fda28c9af355a488bb6d97d9fe21ea645bc25814db317f04faa84a6fd93fa383396523f050b968e197f89febad840614840eebd675a3f917324f9d0
Deepseek Time!
Now I have those params, Is it possible to decrypt? How? Use python write a program. For anything you are not assured, just write an assert expression, and then suppose they are right.
n = 0x771b68deea7e2ecd0fa15099ae9085e1a6b163c415bde56c61ec811201d52e456e4a876db6da7af2695e206d9e3b23de02a16f675ad087c4bef3acc6c4e16ab3 e = 65537 c = 0x5641d8b05fda28c9af355a488bb6d97d9fe21ea645bc25814db317f04faa84a6fd93fa383396523f050b968e197f89febad840614840eebd675a3f917324f9d0
To decrypt the given RSA ciphertext using the provided private key parameters, we can use the RSA decryption formula $ m = c^d \mod n $. Here’s how to implement this in Python with necessary assertions to ensure parameter correctness:
# Given public key parameters n_hex = 0x771b68deea7e2ecd0fa15099ae9085e1a6b163c415bde56c61ec811201d52e456e4a876db6da7af2695e206d9e3b23de02a16f675ad087c4bef3acc6c4e16ab3 e = 65537 c_hex = 0x5641d8b05fda28c9af355a488bb6d97d9fe21ea645bc25814db317f04faa84a6fd93fa383396523f050b968e197f89febad840614840eebd675a3f917324f9d0
# Provided private key details private_n = 6238143373406144532542613891565796667768433897236661098978663257017587998717436489052602237149416255508431410438139089238652737575356801140372944004934323 d = 4655215801198930537758237600055059243336600647148227480167683658253493084109218161324654347035325460543024738914452051705196359117246632272734492461923913 p = 66720953144911165998838491049270049821121906475512246576323412599571011308613 q = 93496017058652140120451192281187268387402942550918512435321834788719825835671
# Assert that the provided n matches the private key's n assert private_n == n_hex, "Public and private n values do not match"
# Assert that p and q multiply to n calculated_n = p * q assert calculated_n == private_n, f"p*q ({calculated_n}) does not equal n ({private_n})"
# Assert that d is the modular inverse of e modulo φ(n) assert (e * d) % phi == 1, "d is not the modular inverse of e modulo φ(n)"
# Assert that ciphertext is less than n assert c_hex < private_n, "Ciphertext must be less than n"
# Decrypt the ciphertext m = pow(c_hex, d, private_n)
# Convert the decrypted message to bytes byte_length = (m.bit_length() + 7) // 8 plaintext_bytes = m.to_bytes(byte_length, 'big')
# Attempt to decode the bytes as a UTF-8 string try: plaintext = plaintext_bytes.decode('utf-8') print("Decrypted plaintext:", plaintext) except UnicodeDecodeError: print("Decrypted bytes (could not decode as UTF-8):", plaintext_bytes.hex())
Explanation:
Parameter Conversion: The provided hexadecimal values for n and c are directly used as integers.
Assertions: • Ensure the public n matches the private key’s n. • Verify that $ p \times q = n $. • Confirm that $ d $ is the correct modular inverse of $ e $ modulo $ φ(n) $. • Check that the ciphertext is valid (i.e., $ c < n $).
Decryption: Uses Python’s built-in pow function for efficient modular exponentiation.
Conversion to Bytes: Converts the decrypted integer to bytes and attempts to decode it as a UTF-8 string, handling potential decoding errors gracefully.
This program ensures all parameters are correct before performing decryption, providing a robust solution to retrieve the original plaintext message.