Markov’s inequality, one of the simplest results in probability theory, plays a fundamental role in the cryptanalysis of ECDSA . It provides a rigorous mathematical framework for:
- detection of statistical anomalies in the distribution of nonces across public signatures;
- estimates of the probability of false positives in statistical testing;
- determining the minimum number of signatures required for a reliable attack;
- analysis of the stability of lattice methods to random fluctuations.
The practical significance of these theoretical results has been confirmed by mass recovery of Bitcoin private keys in real-world conditions, making the problem of high-quality nonce generation one of the critical vulnerabilities in modern cryptocurrency systems.
Understanding the relationship between abstract probabilistic inequalities and specific cryptographic attacks allows us not only to effectively identify existing vulnerabilities, but also
Content
- 1. Introduction
- 2. Markov’s inequality: mathematical essence
- 3. ECDSA and the Critical Role of Nonce
- 4. Application of Markov’s inequality to nonce analysis
- 5. Statistical attacks: Bleichenbacher’s method
- 6. Lattice attacks and the hidden number problem (HNP)
- 7. Practice: Bitcoin Key Recovery
- 8. Limitations and countermeasures
- 9. Conclusion
- Directions for further research for cryptanalysis based on this area
1. Introduction
ECDSA (Elliptic Curve Digital Signature Algorithm) is the cornerstone of transaction security in the Bitcoin network and many other cryptocurrencies. However, contrary to popular belief, the strength of ECDSA depends not only on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) but also on the quality of the generation of the ephemeral secret number — the so-called nonce . Any deviation from a uniform kdistribution creates a statistical vulnerability that can be exploited to recover the long-term private key.k[1, n-1]
Markov’s inequality, a fundamental result in probability theory, allows one to estimate the probability of large deviations in a random variable, knowing only its expected value. It is precisely this minimal requirement for prior data that makes Markov’s inequality an exceptionally valuable tool in cryptanalysis: by observing only public outputs of ECDSA signatures, an attacker can obtain statistical estimates that, through Markov’s inequality, are transformed into strict probability bounds sufficient to detect nonce drift and subsequently recover the key.
2. Markov’s inequality: mathematical essence
Markov’s inequality (in probability theory) states that if X is a non-negative random variable with finite mathematical expectation E[X], then for any a > 0:
P(X ≥ a) ≤ E[X] / a
Equivalent form of writing via parameter ε > 0:
P(X ≥ ε · E[X]) ≤ 1/ε
Markov’s inequality is the most elementary tail inequality : it requires only the existence of the first moment and imposes no restrictions on the distribution [reference:0]. Many stronger inequalities (Chebyshev’s, Chernoff’s, Hoeffding’s) are obtained by applying Markov’s inequality to suitably transformed random variables [reference:1].
In a cryptographic context, Markov’s inequality allows one to solve the inverse problem: using the observed sample mean of a random variable to estimate the probability that the true value (or the associated secret) lies within a certain range. This ability makes it a key tool for statistical distinguishing attacks —attacks aimed at distinguishing between distributions.
The key idea behind its application in cryptanalysis is that if an observed statistic (for example, the sample mean of some function of signatures) significantly exceeds the expected value under the hypothesis of a uniform nonce, Markov’s inequality provides a strict upper bound on the probability of such an excess, assuming randomness . A small value of this bound allows one to reject the uniformity hypothesis and proceed to an attack.
3. ECDSA and the Critical Role of Nonce
The ECDSA algorithm over an elliptic curve with order n and base point G works as follows. To sign a message with a hash z and a private key d:
- An ephemeral secret
k ∈ [1, n-1](nonce) is generated. - The point is calculated
R = kG, andr = x(R) mod n. - Calculated
s = k⁻¹(z + rd) mod n. - Signature – pair
(r, s).
From the signature equation follows the fundamental relationship:
k ≡ s⁻¹ · z + s⁻¹ · r · d (mod n)
or, in a more convenient form for attacks:
d ≡ r⁻¹ · (s · k − z) (mod n)
Thus, knowledge of even one nonce k completely reveals the private key d [reference:2]. Moreover, even partial leakage of information k (for example, a shift in the high-order bits) can be recovered d with a sufficient number of signatures. ECDSA is extremely sensitive to the quality of the nonce: even a shift of less than one bit can lead to complete key recovery [reference:3].
In Bitcoin, hardware random number generators (RNGs) or deterministic schemes (RFC 6979) are often used to generate nonces. However, software bugs, weak RNGs, and side-channel leaks have repeatedly resulted in biased nonces appearing in real transactions, making mass private key recovery possible[reference:4].
4. Application of Markov’s inequality to nonce analysis
Let us consider how Markov inequality is applied to detect nonce bias and estimate the required number of signatures for an attack.
4.1. Biased Nonce Model
Let nonce k be generated not uniformly, but rather according to some distribution skewed toward small values. A typical example: truncation —generating k a random number from [1, 2^m] instead of [1, n-1], where m < log₂ n. Then k has the expected value E[k] ≈ 2^m / 2 = 2^{m-1}, which is significantly less than n/2 .
Let us define an indicator random variable:
X = 1, если k < n/2 (то есть старший бит k равен 0);
X = 0 в противном случае.
For uniform k on , [1, n-1] we have P(X=1) ≈ 1/2 and E[X] ≈ 1/2. If k is biased toward small values, then P(X=1) > 1/2, and the sample mean X̄ for N signatures will systematically exceed 1/2.
4.2 Markov’s inequality for estimating the probability of a false rejection
We apply Markov’s inequality to a random variable Y = (X - 1/2)²that is non-negative and has a mathematical expectation E[Y] = Var(X) ≤ 1/4 (since it X is Bernoulli). Then, for any a > 0:
P( (X̄ - 1/2)² ≥ a ) ≤ E[(X - 1/2)²] / (N · a) ≤ 1 / (4 N a)
This provides a tight upper bound on the probability that the observed deviation of the sample mean from 1/2 will exceed √a , given that the nonce was uniform . If this deviation is large for real data and the calculated bound is small (e.g., 10⁻⁶), the uniformity hypothesis is rejected with high statistical significance.
4.3 Estimating the number of signatures for an attack
Let δ = |P(X=1) - 1/2| be the magnitude of the bias. With N signatures, the sample mean X̄ is concentrated around the true mean P(X=1) with a standard deviation of σ = √(P(1-P)/N) ≤ 1/(2√N). To reliably detect the bias δ (e.g., with a margin of 3σ), it is necessary:
δ > 3 / (2√N) ⟹ N > 9 / (4 δ²)
This is a necessary condition , which follows from Markov’s inequality and its corollaries. For example, detecting a bias δ = 0.01 (a 1% deviation from uniformity) requires N > 22 500 signatures. In practice, attacks on Bitcoin keys often collect tens of thousands of signatures, which is consistent with this estimate [reference:5].
5. Statistical attacks: Bleichenbacher’s method
Historically, the first method to exploit biased nonces was a purely statistical attack by Daniel Bleichenbacher (2000), based on Fourier analysis and not requiring lattice computations[reference:6].
5.1. The idea of the method
The signature equation k ≡ s⁻¹(z + rd) mod n implies that for a true key, d the values k form a “correct” sequence. If the nonce is biased (for example, the most significant bits are more often 0), then for the correct candidate , d the calculated values k will exhibit this bias, while for incorrect candidates, they will appear uniform.
Bleichenbacher proposed using the discrete Fourier transform to detect periodicity in a distribution k. For each candidate, d' the following statistic is calculated:
B(d') = | (1/N) Σ_{i=1}^N exp(2πi · (s_i⁻¹(z_i + r_i d') mod n) / n) |
If true, d the value B(d) significantly exceeds the values for random candidates. Markov’s inequality allows us to estimate the probability that such an excess arose by chance, and thus establish a threshold for candidate selection.
5.2 Connection with Markov’s inequality
The statistic B(d') is the sample mean of complex exponential functions. Its mathematical expectation k is zero for a uniform distribution. Apply Markov’s inequality to |B(d')|²:
P( |B(d')|² ≥ a ) ≤ E[ |B(d')|² ] / a = (1/N) / a
Thus, the probability of a false peak decreases as 1/(N a). This provides a strict criterion: if for some d' value |B(d')|² of exceeds N · a, the randomness hypothesis is rejected with an error probability of no more than 1/a. In practice, Bleichenbacher’s method allowed recovery of 384-bit ECDSA keys with a 5-bit nonce leak from 4000 signatures [reference:7].
5.3. Advantages and disadvantages
| Aspect | Characteristic |
|---|---|
| Required data volume | Large (thousands–tens of thousands of signatures) |
| Error tolerance | High (works with leak errors) |
| Computational complexity | O(N · n) for exhaustive search; optimized via FFT |
| Minimum displacement | Less than 1 bit (theoretically any δ > 0) |
6. Lattice attacks and the hidden number problem (HNP)
A more powerful and efficient approach is to reduce the ECDSA key recovery problem with a known nonce bias to the Hidden Number Problem (HNP) and solve it using lattice basis reduction (LLL, BKZ) methods [reference:8].
6.1. HNP staging for ECDSA
Let’s assume that for each signature i the nonce k_i lies in a certain interval [0, 2^ℓ) (that is, ℓ the most significant bits are zero). Then:
k_i = s_i⁻¹(z_i + r_i d) mod n, причём 0 ≤ k_i < 2^ℓ
This can be rewritten as:
| s_i⁻¹ r_i d − s_i⁻¹ z_i + n · t_i | < 2^ℓ
for some integers t_i. This is a system of linear inequalities with respect to the unknown d and auxiliary variables t_i. Such systems are naturally formulated as problems of finding a short vector in a lattice.
6.2 Lattice construction and the LLL algorithm
A lattice of dimension N+1 (where N is the number of signatures) is constructed with basis vectors:
B = [ n 0 ... 0 0
0 n ... 0 0
...
0 0 ... n 0
α₁ α₂ ... α_N B/n ]
where α_i = s_i⁻¹ r_i mod n, and B is a scaling parameter (usually B ≈ 2^ℓ). Using the LLL (Lenstra–Lenstra–Lovász) algorithm or its more powerful variant, BKZ, finds short vectors in this lattice. One of them, with high probability, contains the desired private key d[reference:9].
The role of Markov’s inequality here is to estimate the probability of success: the length of the desired vector is proportional to 2^ℓ, and the length of the random vectors is n. Markov’s inequality allows us to rigorously demonstrate that for sufficiently large N and small , ℓ the probability that the random grid contains a vector shorter than the desired one is exponentially small.
6.3 Comparison with statistical attacks
| Criterion | Statistical Attack (Bleichenbacher) | Lattice attack (LLL/BKZ) |
|---|---|---|
| Number of signatures | Very large (10⁴–10⁵) | Moderate (10²–10³) |
| Minimum displacement | Any (even < 1 bit) | Typically ≥ 2–3 bits |
| Computational complexity | FFT, O(N log N) | LLL/BKZ, polynomial in N |
| Error tolerance | High | Average |
7. Practice: Bitcoin Key Recovery
The most famous example of the practical application of the described methods is the work “Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies” (2019), in which the authors analyzed millions of signatures in the Bitcoin and Ethereum blockchains and recovered hundreds of private keys [reference:10].
7.1. Mechanisms for the emergence of biased nonces in Bitcoin
- Nonce reuse: If two signatures have the same
k, the key is calculated directly:d = (s₁z₂ − s₂z₁) / (r₁s₂ − r₂s₁) mod n. This is a classic example of the complete failure of ECDSA. - Weak RNGs: Some wallets used predictable generators (e.g. time-based or counter-based), which resulted in systematic bias
k. - Implementation errors: for example, generation
kwith truncation to 128 bits instead of 256, which givesℓ ≈ 128known zero high bits.
A 2019 paper showed that even a 128-bit nonce truncation (i.e. ℓ = 128) with ~30 signatures allows the key to be recovered in seconds using LLL[reference:11].
7.2. Step-by-step attack scenario
- Data collection: All transactions signed by the same public key are extracted from the blockchain. For each signature, the
(r, s, z). - Bias detection: Using statistical tests (based on Markov inequalities), the hypothesis of uniformity is tested
k. If bias is detected, proceed to the next step. - HNP formulation: a system of inequalities is constructed
0 ≤ k_i < 2^ℓ. - LLL/BKZ solution: construct a lattice and apply basis reduction. The resulting short vector yields a candidate for
d. - Verification: Checks that
d · Git matches the public key.
Real-world result: In 2019, researchers recovered over 300 Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS keys using exclusively public blockchain data[reference:12].
8. Limitations and countermeasures
8.1 Limitations of the methods
- Statistical attacks require very large amounts of data (tens of thousands of signatures), which is not always available.
- Lattice attacks are effective for
ℓ ≥ 2–3bits of known bias; forℓ < 1LLL/BKZ bits they may fail, requiring hybrid methods[reference:13]. - If the nonce is generated by a cryptographically strong RNG and does not leak, attacks are impossible.
8.2. Countermeasures
- RFC 6979: Deterministic nonce generation based on HMAC-SHA256 from a private key and a message hash. This eliminates the dependence on RNG and makes it
kpseudo-random with guaranteed quality [reference:14]. - Hardware RNGs with post-processing: using certified generators (FIPS 140-2) with entropy estimation.
- Range checking: Rejects
kout-of-range[1, n-1]or abnormally structured bits. - Blockchain monitoring: Regularly scanning transactions for recurring
ror statistical anomalies.
9. Conclusion
Markov’s inequality, one of the simplest results in probability theory, plays a fundamental role in the cryptanalysis of ECDSA . It provides a rigorous mathematical framework for:
- detection of statistical anomalies in the distribution of nonces across public signatures;
- estimates of the probability of false positives in statistical testing;
- determining the minimum number of signatures required for a reliable attack;
- analysis of the stability of lattice methods to random fluctuations.
The practical significance of these theoretical results has been confirmed by mass recovery of Bitcoin private keys in real-world conditions, making the problem of high-quality nonce generation one of the critical vulnerabilities in modern cryptocurrency systems.
Understanding the relationship between abstract probabilistic inequalities and specific cryptographic attacks allows us not only to effectively identify existing vulnerabilities, but also to design more secure signature schemes that are resistant to statistical and lattice cryptanalysis.
Directions for further research for cryptanalysis based on this area
- Developing adaptive statistical tests using Markov inequalities for nonstationary nonce distributions. Existing methods assume a fixed bias. However, in real systems, the distribution
kmay change over time (for example, due to RNG degradation). Applying Markov inequalities to sliding observation windows will allow for the detection of evolving leaks. - Combining Markov inequality with machine learning methods to identify hidden patterns in nonces. Neural network models can detect nonlinear relationships that are undetectable by classical statistics. Markov inequality can serve as a theoretical basis for assessing the validity of the inferences of such models.
- Analysis of Markov Inequality for Quantum Nonce Distributions. With the development of quantum computing and quantum random number generators, new distribution models are emerging. Studying the behavior of Markov inequalities in a quantum context may reveal new classes of attacks against post-quantum signature schemes.
- Applying Markov’s inequality to the analysis of side-channel leaks in hardware wallets. Power consumption and electromagnetic radiation can provide statistical information about the nonce. Markov’s inequality allows for a rigorous assessment of the probability that the observed fluctuations are due to the secret and not noise.
- Developing hybrid statistical-lattice attacks for the case of less than 1 bit of bias. Although Bleichenbacher demonstrated the feasibility of the attack for arbitrarily small biases, practical effectiveness
δ < 2⁻¹⁰remains low. Combining ideas from Markov inequality with modern lattice reduction algorithms (e.g., G6K) can improve this situation. - A study of Markov inequality in the context of attacks against deterministic nonce schemes (RFC 6979). Although RFC 6979 is considered secure, it may be vulnerable to attacks based on linked messages. Markov inequality can help estimate the success rate of such attacks.
- Building formal verification frameworks for assessing the security of ECDSA implementations based on probabilistic inequalities. Automated security proofs using Markov inequalities as a basic tool will enable the creation of certified implementations resistant to statistical cryptanalysis.
This document is based on an analysis of scientific publications on ECDSA cryptanalysis and probability theory.
All methods mentioned are intended solely for educational and research purposes in the field of information security.
