In this paper, we examined the theoretical and practical aspects of using hidden Markov models for ECDSA cryptanalysis in the Bitcoin context. We demonstrated that if the nonce generator has a hidden Markov structure, this creates a serious vulnerability that allows the recovery of the long-term private key.
The main stages of the proposed approach:
- Reduction of the problem to the hidden number problem (HNP) based on collected ECDSA signatures.
- Detecting Markov dependence in a nonce sequence using statistical tests and HMM training.
- Using the posterior probabilities of the HMM to select a subset of “biased” nonces and construct a weighted or reduced lattice.
- Solving HNP using basis reduction algorithms (LLL/BKZ) and extracting the private key.
The proposed method is particularly effective in cases where standard lattice attacks are difficult due to large amounts of “noise” or a small number of known nonce bits. The Markov structure allows for signal amplification by selecting the most informative signatures.
Disclaimer: The methods described are intended solely for academic research and to improve the security of cryptographic systems. Using them for unauthorized access to other people’s private keys and funds is illegal.
Content:
- Introduction
- Mathematical Foundations of ECDSA and the Hidden Number Problem (HNP)
- Lattice attacks on ECDSA with partially known nonces
- Markov dependencies in nonce generation: model and detection
- Construction of a lattice taking into account Markov dependencies
- Practical implementation: step-by-step algorithm
- Conclusion
- Directions for further research for cryptanalysis based on this area
1. Introduction
The Elliptic Curve Digital Signature Algorithm (ECDSA) is the cornerstone of Bitcoin transaction security. A critical vulnerability of ECDSA lies in the requirement to generate a unique and unpredictable nonce ( usually denoted by k) for each signature. If the nonce generator has hidden statistical dependencies, for example, if it follows a Markov process where α depends on α , this creates the preconditions for effective cryptanalysis to recover the long-term private key.ki+1ki
This paper explores the application of hidden Markov models (HMMs) to detecting and exploiting such dependencies in nonce sequences generated by vulnerable Bitcoin wallet implementations. We demonstrate how, by combining methods from probability theory, lattice cryptography, and number theory, we can reduce the private key recovery problem to solving the hidden number problem (HNP) and construct an effective attack.
2. Mathematical Foundations of ECDSA and the Hidden Number Problem (HNP)
2.1. ECDSA Signature Generation Algorithm
Let domain parameters be given D = (E, p, G, q, H), where E is an elliptic curve over a finite field , is a generating point of order , and is a cryptographic hash function. The private key is fixed.𝔽pGqHd ∈ ℤq
To sign a message M:
- A random nonce is generated .
k ∈ ℤq - The point is calculated , and .
R = kG = (rx, ry)r = rx mod q - Calculated .
s = k−1(H(M) + r·d) mod q - Signature – pair
(r, s).
The key equation relating the unknowns k and d:
s·k ≡ H(M) + r·d (mod q)
Let’s rewrite it in a form convenient for cryptanalysis:
k ≡ s−1·r·d + s−1·H(M) (mod q)
Let us denote and . Then for each :ti = si−1·ri mod qai = si−1·H(Mi) mod qi
ki ≡ ti·d + ai (mod q)
This equation is the basis for reducing the problem to the Hidden Number Problem (HNP) [reference:0].
2.2 Hidden Number Problem (HNP)
HNP is formulated as follows: given m pairs , where are known factors, , and is a secret number (in our case ), and are small unknown errors bounded in absolute value . It is required to find .(ti, ai)ti ∈ ℤqai = (ti·α + bi) mod qα ∈ ℤqα = dbi|bi| < Bα
In the context of ECDSA, the deviation of the nonce from some predictable value plays a role . If the nonces are biased (e.g., have known high-order bits or a common prefix or suffix), then HNP can be solved using lattice methods [reference:1].biki
3. Lattice attacks on ECDSA with partially known nonces
3.1 Construction of the lattice for HNP
The classical approach of Howgrave-Graham and Smart and independently of Nguyen and Shparlinski reduces HNP to the nearest vector problem (CVP) or shortest vector problem (SVP) in a specially constructed lattice[reference:2].
Let’s consider the case where we know that are small: for all . Then, it follows from the equation that . Let’s introduce and consider the lattice generated by the rows of the matrix:ki|ki| < Biki ≡ ti·d + ai (mod q)ti·d + ai − ki ≡ 0 (mod q)ci = ai mod q
B = [ [ q, 0, ..., 0, 0 ],
[ 0, q, ..., 0, 0 ],
...,
[ t1, t2, ..., tm, 1/q ],
[ c1, c2, ..., cm, 0 ] ]
The vector is a short vector in this lattice (up to scaling), and can be found using basis reduction algorithms such as LLL or BKZ[reference:3].(k1, k2, ..., km, d/q)
3.2 Generalization to the case of partially known nonces
In practice, it is often not known that the numbers are small, but that they share a common prefix or suffix, or that some of their bits are known. The technique of “implicit prefixes” and “implicit suffixes” allows us to reduce these cases to the standard HNP formulation [reference:4].ki
For example, if it is known that α have the same high-order (unknown) bits, then we can write , where α is the unknown common part, and α are small. After elimination using differences of the equations, we obtain HNP with α and a doubled error bound [reference:5].kiℓki = 2ℓ·bi + ccbicm−1
Important: Lattice attacks are more effective the smaller the “noise” size B relative to the modulus q. In the case of Bitcoin , even leaking a few bits of nonce information can make the attack feasible [reference:6].q ≈ 2256
4. Markov dependencies in nonce generation: model and detection
4.1 Hidden Markov Model (HMM)
A hidden Markov model is a statistical model in which a system is described as a Markov process with unknown (hidden) states. At each moment in time, i the system is in a hidden state , which is not directly observable. Only a certain quantity , probabilistically dependent on , is observable .SiOiSi
Formally, HMM is defined as:
- Many hidden states .
{S1, S2, ..., SN} - The matrix of transition probabilities , where .
A = [aij]aij = P(St+1 = Sj | St = Si) - The emission matrix , where .
B = [bj(o)]bj(o) = P(Ot = o | St = Sj) - The initial distribution is , .
π = [πi]πi = P(S1 = Si)
The Baum-Welch algorithm (EM algorithm) is used to train the HMM, and the Viterbi algorithm is used to decode the most probable sequence of hidden states.
4.2 Applying HMM to a nonce sequence
Suppose the nonce generator in a vulnerable Bitcoin wallet implementation has an internal state that evolves according to a Markov law. For example, this could be a counter, a linear feedback shift register (LFSR), or simply a poorly seeded pseudorandom number generator (PRNG) whose state depends on the previous output.
In this case, the sequence is not independent: it statistically depends on . We can observe not the sequence itself , but only the signatures given by the equations . However, we can use an HMM to model the hidden structure of the nonce sequence.k1, k2, ..., kmki+1kiki(ri, si)ki ≡ ti·d + ai (mod q)
In the simplest case, two hidden states can be considered: “normal mode” and “biased mode,” where in the normal mode, is generated uniformly, while in the biased mode, has a known prefix or a small value. The transition matrix describes the probability of switching between modes. Observable quantities can be, for example, values or statistics calculated from .kiAri(ri, si)
Key idea: If we can train an HMM on a sequence of signatures, the Viterbi algorithm will allow us to reconstruct the most probable sequence of hidden states corresponding to the nonce generation. This, in turn, will provide us with additional information about which signatures are biased and will allow us to select a subset of signatures for a lattice attack.ki
4.3 Detecting Markov Dependency: Statistical Tests
Before constructing an HMM, it’s necessary to verify that Markov dependence is indeed present. To do this, the following statistical tests can be applied to the sequence of reconstructed (or partially reconstructed) nonces:
- Chi-square test for independence: construct a contingency table for pairs , dividing the range of possible values into intervals. If is small, the hypothesis of independence is rejected.
(ki, ki+1)p-value - Autocorrelation analysis: We calculate the sample autocorrelation function . For a Markov process with nonzero transitions , it will decay exponentially but will not vanish instantly (unlike white noise).
ρ(τ) = Corr(ki, ki+τ)ρ(τ) - Markov chain test (Bartlett’s test or likelihood ratio test): compares a model of independent identically distributed variables with a first-order Markov chain model. The likelihood ratio statistic has an asymptotic chi-square distribution.
- Mutual information: we evaluate . If mutual information is significantly positive, this indicates dependence.
I(ki; ki+1) = H(ki) + H(ki+1) − H(ki, ki+1)
5. Construction of a lattice taking into account Markov dependencies
5.1 Modification of the HNP lattice
The classical HNP lattice assumes that all signatures are independent and have the same bound . If we know that the nonce sequence is Markov, we can use the posterior probabilities obtained from the HMM to assign each signature its own bound (or weight).kiBiBi
Let be the probability that belongs to a small interval (i.e., is “biased”), according to the HMM. Then we can construct a weighted lattice, where the rows corresponding to more probable biased nonces have a smaller contribution to the norm of the error vector. This can be done by scaling the corresponding columns of the lattice matrix.piki
An alternative approach is to select a subset S of signatures with the highest posterior bias probability (e.g., ) and apply a standard lattice attack only to this subset. This reduces the lattice dimension, which is critical for the attack to be practical [reference:7].pi > 0.5
5.2. Accounting for transition probabilities
A more sophisticated method is to incorporate information about state transitions directly into the HNP equations. For example, if the HMM predicts that with high probability , where λ is small, then we can add equations of the form λ with small error. This increases the number of equations and imposes additional constraints on the unknowns, which can improve the lattice conditioning.ki+1 = ki + δiδiki+1 − ki ≡ 0 (mod q)
In the limit, if the Markov structure is known exactly (for example, with known ), then the problem is reduced to solving a system of linear equations with respect to and the initial , which can be solved even without lattices, using simple algebraic methods.ki+1 = a·ki + b mod qa, bdk1
6. Practical implementation: step-by-step algorithm
6.1 Data collection
It is necessary to collect a set of m ECDSA signatures and corresponding message hashes generated by the same private key . The more signatures, the better (in practice, a 256-bit curve may require several hundred to several thousand signatures, depending on the offset).(ri, si)H(Mi)d
6.2. Primary processing and calculation ti, ai
import hashlib
from ecdsa import SECP256k1 # пример библиотеки
def preprocess_signatures(signatures, messages, q):
"""
signatures: список кортежей (r, s)
messages: список байтовых строк (сообщения)
q: порядок группы (для secp256k1: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
"""
t_list = []
a_list = []
for (r, s), msg in zip(signatures, messages):
h = int.from_bytes(hashlib.sha256(msg).digest(), 'big')
s_inv = pow(s, -1, q)
t_i = (s_inv * r) % q
a_i = (s_inv * h) % q
t_list.append(t_i)
a_list.append(a_i)
return t_list, a_list
6.3 Markov Dependency Detection and HMM Training
Since the λ themselves are unknown, we cannot directly apply statistical tests to them. However, we can use indirect measures. For example, we can calculate the value of a given candidate key (e.g., obtained from a partial analysis or simply by trying several candidates) for each signature. If λ is close to the true key, then λ will be close to the real ones (up to an additive constant). Then, Markov tests can be applied to the sequence.kiui = (ti·dguess + ai) mod qdguessdguessuikiui
A more practical approach is to use a continuous-emission (Gaussian) HMM, where the observable is , and the hidden states correspond to different nonce generation modes. The HMM parameters can be estimated using the EM algorithm, using an initial guess for (e.g., from solving the HNP on a subset of the data).uid
import numpy as np
from hmmlearn import hmm
# Предположим, у нас есть последовательность u_i = (t_i * d_approx + a_i) mod q
# Модель с 2 скрытыми состояниями: "смещённый" и "несмещённый"
model = hmm.GaussianHMM(n_components=2, covariance_type="full", n_iter=1000)
# Нормируем u_i в диапазон [0, 1] для устойчивости
u_scaled = (np.array(u_list) / q).reshape(-1, 1)
model.fit(u_scaled)
# Получаем наиболее вероятную последовательность скрытых состояний
hidden_states = model.predict(u_scaled)
# Индексы подписей, которые HMM считает смещёнными
biased_indices = [i for i, state in enumerate(hidden_states) if state == 0] # предположим, состояние 0 = смещённое
print(f"Обнаружено {len(biased_indices)} предположительно смещённых nonce.")
6.4 Lattice construction and basis reduction
We use the selected m' signatures with biased_indices. We construct a dimensional lattice m' + 1 and apply LLL or BKZ. For a practical implementation in Python, you can use the fpylll.
from fpylll import IntegerMatrix, LLL, BKZ
def build_lattice(t_list, a_list, q, B):
"""
t_list, a_list: списки длины m'
q: модуль
B: граница для k_i (например, 2^(q.bit_length() - known_bits))
"""
m = len(t_list)
# Создаём матрицу (m+1) x (m+1)
M = IntegerMatrix(m + 1, m + 1)
# Заполняем верхний левый блок q*I
for i in range(m):
M[i, i] = q
# Последняя строка: t_i
for i in range(m):
M[m, i] = t_list[i]
# Последний столбец: a_i и масштаб
for i in range(m):
M[i, m] = a_list[i]
M[m, m] = B # масштабирование
return M
def reduce_lattice(M):
# Применяем LLL
LLL.reduction(M)
# Для лучших результатов можно применить BKZ
# BKZ.reduction(M, BKZ.Param(block_size=20))
return M
# Пример использования
M = build_lattice(t_biased, a_biased, q, B=2**200) # B зависит от ожидаемого смещения
M_reduced = reduce_lattice(M)
# Ищем короткий вектор, соответствующий решению
# Восстановленный d можно извлечь из последней координаты короткого вектора
# (с точностью до знака и масштаба)
6.5. Key verification and recovery
After reducing the basis, we analyze the resulting short vectors. The vector corresponding to the HNP solution will have the form . From the last coordinate, we extract (up to the sign and an integer factor, which can be determined by substituting the candidates into the ECDSA equation).(k1, k2, ..., km', d·B/q)d
def extract_private_key(reduced_matrix, t_list, a_list, q):
"""
Пытается извлечь приватный ключ из редуцированной решётки.
"""
# Анализируем строки редуцированной матрицы
for row_idx in range(reduced_matrix.nrows):
row = [reduced_matrix[row_idx, j] for j in range(reduced_matrix.ncols)]
# Последняя координата должна быть пропорциональна d
d_candidate = row[-1]
# Проверяем кандидата: для каждого i должно выполняться
# k_i = (t_i * d + a_i) mod q и |k_i| < B
# (или k_i принадлежит ожидаемому смещённому диапазону)
# ...
pass
return d_candidate
7. Conclusion
In this paper, we examined the theoretical and practical aspects of using hidden Markov models for ECDSA cryptanalysis in the Bitcoin context. We demonstrated that if the nonce generator has a hidden Markov structure, this creates a serious vulnerability that allows the recovery of the long-term private key.
The main stages of the proposed approach:
- Reduction of the problem to the hidden number problem (HNP) based on collected ECDSA signatures.
- Detecting Markov dependence in a nonce sequence using statistical tests and HMM training.
- Using the posterior probabilities of the HMM to select a subset of “biased” nonces and construct a weighted or reduced lattice.
- Solving HNP using basis reduction algorithms (LLL/BKZ) and extracting the private key.
The proposed method is particularly effective in cases where standard lattice attacks are difficult due to large amounts of “noise” or a small number of known nonce bits. The Markov structure allows for signal amplification by selecting the most informative signatures.
Disclaimer: The methods described are intended solely for academic research and to improve the security of cryptographic systems. Using them for unauthorized access to other people’s private keys and funds is illegal.
Directions for further research for cryptanalysis based on this area
- Developing specialized HMMs for continuous nonces: Creating models that operate directly on ECDSA modular arithmetic, without the need for an initial approximation
d. This can be achieved using variational inference or Markov Monte Carlo (MCMC) methods. - Integrating HMMs with modern lattice reduction algorithms: Investigating how HMM posterior probabilities can be used to dynamically modify lattice parameters (e.g., column weights) during the reduction process, not just at the signature selection stage.
- Analysis of Multivariate Markov Dependencies: Nonce generators can have a more complex structure than a first-order Markov chain. A study of higher-order hidden Markov models and their impact on cryptanalysis performance.
- Applying deep learning to discover hidden dependencies: Using recurrent neural networks (RNN, LSTM, GRU) to discover nonlinear and long-term dependencies in nonce sequences that are not captured by classical HMMs.
- Cryptanalysis of Deterministic Nonce Generation Schemes (RFC 6979): Although RFC 6979 eliminates randomness, it uses a deterministic function of the message and key. This study examines whether certain implementations of RFC 6979 can produce predictable patterns that can be exploited using techniques similar to those described.
- Development of protective measures: Based on the understanding of Markov vulnerabilities, propose new methods of nonce generation that guarantee the absence of statistical dependencies even under conditions of weak entropy sources (e.g., using multiple independent sources and cryptographic mixes).
- Real-World Blockchain Data Analysis: Conducting a large-scale study of signatures in the Bitcoin and other cryptocurrency blockchains to identify real-world instances of Markov dependencies in nonces and assess their prevalence.
- Generalization to other signature schemes: Applying a similar approach (HMM + lattices) to other schemes using nonce-based keys, such as Schnorr, EdDSA, and their variants.
Author: Expert in cryptography, number theory and lattice methods.
