# Oven

| parameter | description |
|---|---|
| $F$ | `FLAG` with less than $384$ bits|
| $i \in I$ | $I$ is indexing the quries to `challenge.py` |
| $v_i$ | `v`, pseudo-random with only up to $512$ bits |
| $c_i$ | `c`, can be computed by the attacker |
| $r_i$ | $v_i - c_i F$ mod $p_i - 1$|
| $k$ | $512$ |
| $N$ | ???, choose wisely |
| $C(p_0, p_1, \dots, p_n, N)$ | depends on the norm chosen for the lattice $\mathcal{L}$ |

One can query as many as one wants the parameters:

$$
(p_i, 2^F, 2^{v_i}, v_i - c_i F)\in
\mathbb{B}_{1024} \times
\mathbb{Z}_{p_i}^* \times
\mathbb{Z}_{p_i}^* \times
\mathbb{Z}_{p_i - 1}
$$

Even though $v_i$ is psuedo-random since it does not have more than $512$ bits, $v_i - c_i F$ and $-c_iF$ have the same most significant bits $\texttt{mod} \space (p_i - 1)$ (bits from $513$ to $1024$ which is actually quite a lot, half the bits are biased/leaked). Therefore the most significant bits of $-c_iF$ are known and $v_i$ becomes irrelavent. This is sort of a variant of **Hidden Number Problem** but with non-prime modulus. Usually these problems are solved using lattice attacks by finidng nearest or smallest vectors.

Note that $p_i - 1$ is not exaclty the order of the element $2 \in \mathbb{Z}_{p_i}^*$ but it would be divisible by it. Slightly different from the **Hidden Number Problem** assumptions.

$$
\vert r_i - (-c_iF) \vert \leq 2^{512} = \cfrac{2^{1024}}{2^{512}} \leq \cfrac{p_i - 1}{2^{512}} < \cfrac{p_i}{2^{512}} = \cfrac{p_i}{2^k}
$$

$$
A = \begin{bmatrix}
p_0 - 1 & 0 & 0 & \dots & 0 & 0 \\
0 & p_1 - 1 & 0 & \dots & 0 & 0 \\
0 & 0 & p_2 - 1 & \dots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \dots & p_n - 1 & 0 \\
-c_0 & -c_1 & -c_2 & \dots & -c_n & \cfrac{1}{N}
\end{bmatrix}
$$

Let $\mathcal{L}$ be the lattice generated by the rows of $A$.

$$
v = F\cdot (-c_0, -c_1, \dots, -c_n, \cfrac{1}{N}) \in \mathcal{L}
$$

$$
u = (r_0, r_1, \dots, r_n, 0)
$$

$$
\texttt{dist}(A, u) \leq \left\lVert (v_0, v_1, \dots, v_n, 0) \right\rVert \leq C(p_0, p_1, \dots, p_n, N)
$$

In general with respect to a specific norm lattice points that are super close to $u$ are supposed to be of the form:

$$
v' = (\dots, \cfrac{\beta}{N}) \in \mathcal{L}
$$

where $\beta = F \space \texttt{mod} \space N$. Finding one of these points would suffice to find $F$.

## Reference

1. [On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem](https://eprint.iacr.org/2020/1540.pdf)
2. [Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies](https://eprint.iacr.org/2019/023.pdf)
3. [Lattice Attacks on Digital Signature Schemes](https://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf)
4. [The Insecurity of the Digital Signature Algorithm with Partially Known Nonces](https://link.springer.com/content/pdf/10.1007/s00145-002-0021-3.pdf)
5. [The hidden number problem with non-prime modulus](https://tgaref.github.io/assets/publications/hnp-current.pdf)
6. [On Lattices, Learning with Errors, Random Linear Codes, and Cryptography](https://cims.nyu.edu/~regev/papers/qcrypto.pdf)
7. [Lattice Problem](https://en.wikipedia.org/wiki/Lattice_problem)
8. [Lenstra–Lenstra–Lovász lattice basis reduction algorithm](https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm)
9. [Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes](https://link.springer.com/chapter/10.1007/3-540-68697-5_11)
10. [The curse of ECDSA nonces](https://eprint.iacr.org/2020/728.pdf)