Elliptic Curve Cryptography and Government Backdoors

[Pythagoras33]

Assuming that the attacker generated the constants used in Dual EC pseudorandom number generator it has been known for several years that an attacker generating these constants and seeing a long enough stretch of Dual EC output bits can predict all future outputs. This could be a problem since in the very early days of Bitcoin it was common to pay to public keys (P2PK) directly?

References

https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf

https://services.math.duke.edu/~bray/Courses/89s-MOU/2016/Papers/BAS_Paper3_EllipticCurveCryptography.pdf

https://www.youtube.com/watch?v=-UcCMjQab4w

[MisterCooper]

Assuming that the attacker generated the constants used in Dual EC pseudorandom number generator it has been known for several years that an attacker generating these constants and seeing a long enough stretch of Dual EC output bits can predict all future outputs. This could be a problem since in the very early days of Bitcoin it was common to pay to public keys (P2PK) directly?

References

https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf

https://services.math.duke.edu/~bray/Courses/89s-MOU/2016/Papers/BAS_Paper3_EllipticCurveCryptography.pdf

https://www.youtube.com/watch?v=-UcCMjQab4w

@Pythagoras33 for what purpose did you publish it?

[Pythagoras33]

Assuming that the attacker generated the constants used in Dual EC pseudorandom number generator it has been known for several years that an attacker generating these constants and seeing a long enough stretch of Dual EC output bits can predict all future outputs. This could be a problem since in the very early days of Bitcoin it was common to pay to public keys (P2PK) directly?

References

https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf

https://services.math.duke.edu/~bray/Courses/89s-MOU/2016/Papers/BAS_Paper3_EllipticCurveCryptography.pdf

https://www.youtube.com/watch?v=-UcCMjQab4w

@Pythagoras33 for what purpose did you publish it?

This is to highlight the fact that compared to 10 years ago the ECC algorithm presents worrying vulnerabilities.

https://github.com/tintinweb/ecdsa-private-key-recovery

https://github.com/tintinweb/ecdsa-private-key-recovery/blob/master/tools/README.md

[BrewMaster]

This is to highlight the fact that compared to 10 years ago the ECC algorithm presents worrying vulnerabilities.

nonsense.
this is not a vulnerability in elliptic curve cryptography. it is a weakness in some of the bad implementations of it created by bad developers. it is not even about ECC, it is about RNG.
it also has nothing to do with what your title suggests.

the standard for ECC clearly states that k must be chosen randomly. when an implantation like blockchain.info decides to use a weak one or use a crazy option such as random.org that's not the algorithm's flaw!

[Pythagoras33]

This is to highlight the fact that compared to 10 years ago the ECC algorithm presents worrying vulnerabilities.

nonsense.
this is not a vulnerability in elliptic curve cryptography. it is a weakness in some of the bad implementations of it created by bad developers. it is not even about ECC, it is about RNG.
it also has nothing to do with what your title suggests.

the standard for ECC clearly states that k must be chosen randomly. when an implantation like blockchain.info decides to use a weak one or use a crazy option such as random.org that's not the algorithm's flaw!

In Satoshi Nakamoto's day there were no vulnerabilities like the MOV Attack

https://asecuritysite.com/encryption/mir_mov

[j2002ba2]

In Satoshi Nakamoto's day there were no vulnerabilities like the MOV Attack

https://asecuritysite.com/encryption/mir_mov

The MOV Attack is from 1993:
A. J. Menezes, T. Okamoto and S. A. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," in IEEE Transactions on Information Theory, vol. 39, no. 5, pp. 1639-1646, Sept. 1993, doi: 10.1109/18.259647.

[NotATether]

This is to highlight the fact that compared to 10 years ago the ECC algorithm presents worrying vulnerabilities.

nonsense.
this is not a vulnerability in elliptic curve cryptography. it is a weakness in some of the bad implementations of it created by bad developers. it is not even about ECC, it is about RNG.
it also has nothing to do with what your title suggests.

the standard for ECC clearly states that k must be chosen randomly. when an implantation like blockchain.info decides to use a weak one or use a crazy option such as random.org that's not the algorithm's flaw!

Dual_EC_DBRG, the random number generator OP is talking about, isn't even used by default by anyone except for some obscure RSA corp library (and that's only because NSA bribed them to do it). Not that it means anything because everybody else is either using a hash-based, HMAC-based or the block cipher based RNG, none of which have the flaw.

In Satoshi Nakamoto's day there were no vulnerabilities like the MOV Attack

https://asecuritysite.com/encryption/mir_mov

This only works if you have a second point from a generator point different from G that has the same group order as secp256k1. Since bitcoin doesn't bother with using different generator points this attack can't be done.

[Pythagoras33]

This is to highlight the fact that compared to 10 years ago the ECC algorithm presents worrying vulnerabilities.

nonsense.
this is not a vulnerability in elliptic curve cryptography. it is a weakness in some of the bad implementations of it created by bad developers. it is not even about ECC, it is about RNG.
it also has nothing to do with what your title suggests.

the standard for ECC clearly states that k must be chosen randomly. when an implantation like blockchain.info decides to use a weak one or use a crazy option such as random.org that's not the algorithm's flaw!

Dual_EC_DBRG, the random number generator OP is talking about, isn't even used by default by anyone except for some obscure RSA corp library (and that's only because NSA bribed them to do it). Not that it means anything because everybody else is either using a hash-based, HMAC-based or the block cipher based RNG, none of which have the flaw.

In Satoshi Nakamoto's day there were no vulnerabilities like the MOV Attack

https://asecuritysite.com/encryption/mir_mov

This only works if you have a second point from a generator point different from G that has the same group order as secp256k1. Since bitcoin doesn't bother with using different generator points this attack can't be done.

If you create such a backdoor then it is likely that the encryption algorithm you have chosen is a backdoor as well. I am not a mathematician but the solution to the problem of the elliptic curve can be solved even by a student in the first year of high school.

https://www.aimath.org/news/congruentnumbers/ecconnection.html#:~:text=Congruent%20numbers%20naturally%20lead%20to,%2Bb2%3D%20c2.&text=It%20is%20possible%20to%20describe%20all%20Pythagorean%20triples%20by%20a%20formula.

[NotATether]

If you create such a backdoor then it is likely that the encryption algorithm you have chosen is a backdoor as well. I am not a mathematician but the solution to the problem of the elliptic curve can be solved even by a student in the first year of high school.

~snip

The solution that is in your link applies to curves formed from congruent numbers only. Like if you have a,b,c = 3,4,5 the sides of a right triangle, or 2,4,sqrt(12) [<-- a set of sides with a fractional c shouldn't be used because x and y have to be integers], then that can be used to construct a point on this special curve.

Similarly you can get all the x and y coordinates on your curve constructed from measuring the hypotenuses of a bunch of triangles with different side lengths.

But - and this is the big part - this is not the secp256k1 curve. The equations are totally different. This curve uses y² = x³ - n²x, while secp256k1 is y² = x³ + 7. The term with n (which is supposed to represent area AFAIK) isn't even there, so for your curve that would make an invalid triangle with an area 0. There is no a and b /= 0 that satisfies a*b/2 = n = 0, so that implies right triangle sides cannot be made for Bitcoin's curve. So this solution totally collapses on its head for secp256k1.


To answer your first remark of an encryption algorithm being chosen is "likely ...  a backdoor as well", Dual_EC_DRBG uses two curve points to generate a random number:


Image source:  https://blog.0xbadc0de.be/archives/155 (equations are images with transparent background; use your browser's Reader Mode to read them).

The backdoor was that somebody made one of the points a multiple of the other, Q = dP, and P is already a known generator point. So where one of the points was supposed to be unknown, none of them are unknown now and the random number can be guessed easily if you know the initial seed.

This bug cannot be used on RNGs (hash/HMAC/block cipher) that don't use ECC!