Running lattic_attack.py "private_value must be an integer type"

[Lee-TC]

When I using python3 gen_data.py -f data.json -m "1" -c SECP256K1 -b 8 -t LSB -n 50 to generate 50 signatures to test this script, I successfully get data.json, but when I using python3 lattice_attack.py -f data.json, it came up with following output:

 ----- Lattice ECDSA Attack -----
Loading data from file data.json
Running with 8 bits of k (LSB)
Starting recovery attack (curve SECP256K1)
Constructing matrix
Solving matrix ...
LLL reduction
/usr/lib/python3/dist-packages/apport/report.py:13: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses
  import fnmatch, glob, traceback, errno, sys, atexit, locale, imp, stat
Traceback (most recent call last):
  File "lattice_attack.py", line 259, in <module>
    lattice_attack_cli(arg.f, arg.l)
  File "lattice_attack.py", line 239, in lattice_attack_cli
    result = recover_private_key(
  File "lattice_attack.py", line 195, in recover_private_key
    res = test_result(lattice, pub_key, curve)
  File "lattice_attack.py", line 93, in test_result
    if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve):
  File "/mnt/c/Users/LENOVO/Desktop/lattice-attack-master/lattice-attack-master/ecdsa_lib.py", line 129, in privkey_to_pubkey
    ec.derive_private_key(pv_key_int, ec_backend, backends.default_backend())
  File "/home/leetc/.local/lib/python3.8/site-packages/cryptography/hazmat/primitives/asymmetric/ec.py", line 332, in derive_private_key
    raise TypeError("private_value must be an integer type.")
TypeError: private_value must be an integer type.

But when I generate 5 signatures(small m), it just work fine but got:

----- Lattice ECDSA Attack -----
Loading data from file data.json
Running with 8 bits of k (LSB)
Starting recovery attack (curve SECP256K1)
Not enough signatures
Private key not found. Sorry For Your Loss

I wonder to know how to fix it. Thanks. BTW. Here are my system info:

• OS: Ubuntu 20.04 (wsl)
• Python: Python 3.8.10

[bitlogik]

We'll investigate. But at first it looks like an issue with you fpyLLL library installation. Some people faced similar issue because of an invalid fpyLLL installation. When you run with 5 signatures, LatticeAttack is not trying to compute the matrix, as it first looks if there is a minimal number of provided signatures, enough to be able to recover in theory the private key from the data parameters input. So with a low number of signatures, it simply prints out that the number of signature is not enough to get the private key, and it does nothing else.

From what we can see, fpyLLL is supposed to give out an integer out of the IntegerMatrix object. And your fpyLLL library doesn't gives an integer. Hence the issue. So I would say you got an incompatible fpyLLL library version. What is your fpyLLL version installed ? How did you install it ?

Check there this issue is the same, but there the user had Ubuntu, not WSL. But the symptoms are exactly the same.

[Lee-TC]

Well, thanks for your reply. I installed fpyLLL using apt and the version is 0.5.1+ds1-2build1. Then, I have read the issue that you mention, I will try to upgrade my OS and fpyLLL. At last, Thank your early reply and your excellent project.

[Lee-TC]

Hi, After changing script you mention in https://github.com/bitlogik/lattice-attack/issues/1#issuecomment-855447562 , I successfully solve my question. Sincerely thank your help!

[bitlogik]

Can you detail the change? Was it to add int( ) ?

I reopen the issue, because we need to clarify why the fpylll library on some systems doesn't provide an integer, as it should by instantiating with IntegerMatrix.

[bitlogik]

We tested on the following platforms, all dependencies installed with apt, and everything goes right.

Ubuntu 20.04 Python 3.8.2 python3-fpylll (0.5.1+ds1-2build1)

Ubuntu 20.04.1 Python 3.8.5 python3-fpylll (0.5.1+ds1-2build1)

Ubuntu 20.04.3 Python 3.8.10 python3-fpylll (0.5.1+ds1-2build1)

The last one seems exactly as your configuration, still yet not WSL.

At this point, this is a mystery why some systems read out something different from an integer when using IntegerMatrix of fpylll.

By the way, we made some changes in the code which are improving the compatibility with older version of the cryptography library, like the one on Ubuntu 18.04 and 20.04. So lattice-attack can now work "out of the box" on Ubuntu from 18.04 (still no Python3 fpylll on 18.04).

[rockygsm]

Hi I noticed this issue too.But it was working fine till yesterday. found problem in test_result type of row[-2] is "sage.misc.inherit_comparison.InheritComparisonMetaclass" "sage.rings.integer.Integer" this issue only come after i installed sagemath seems fpylll internally use sagemath if its available and make issue. int(row[-2]) fix issue but process is slow before taking 11 sec now taking 59sec

[bitlogik]

Thank you for reporting your investigation, to help on this issue. This can explain the mystery why some systems get this situation, and some others (as in our tests) don't. I also think about some related causes. One can be you input the input number as Sage number. the input script is the same when it works or not? Also I think the slow down is provided by the work using Sage objects. As the conversion to int itself, is only performed once per matrix computation loop (to check the result), so that shouldn't change so much the overall time. Probably the underlying system for integer is changed from something fast like GMP, to the Sage library, which is way slower for the matrix computations. Then when it checks the end result, it can't convert the types and brings the error. So the slow down would not be because of the int() conversion, but just because the Sage system is used for the computation in place of the fplll GMP.

In practice, that means :

• either patch for a workaround to convert to integer int(row[-2]) % mod_n
• or remove/uninstall sagemath. I'm recommending the latter method if possible. Because one can use this script as it is, and Sage seems to slow down considerably the computation.

[bitlogik]

An other way is to run LatticeAttack in a virtual env (venv), so fpylll doesn't detect Sage at runtime and doesn't perform unnecessary Sage conversions.

[cloudnathy]

This tool works on wallet.dat file?

[bitlogik]

Not at all. In order to find the private key, the software needs:

• A set of EC signatures
• For each signature, a part of internal information. More specifically it needs starting or trailing bits of the ECDSA one-time hidden random.

[smartunia]

Did u solve a problem? I have same thing.

[bitlogik]

This issues kicks when your system has also sagemath installed.

Here are some ways to fix this issue :

• Remove/uninstall sagemath, if not required on your system (not used by any other app).
• Run LatticeAttack in a virtual env (venv), so fpylll doesn't detect Sage at runtime. This isolates the sagemath installation from the LatticeAttack.
• Patch LatticeAttack to work with Sage, change in line 89 in lattice_attack.py : candidate = int(row[-2]) % mod_n. Note that it is apprx 5x slower when using sage instead of "direct" fpylll.

See more details about this issue, in issue #1 .