Why libressl-2.2.3 and openssl-1.0.1p accept very weak elliptic curves?

[Georgi Guninski]

Summary:  libressl-2.2.3 and openssl-1.0.1p appear to accept elliptic
curves which might be broken by Pollard's rho DL in O(2^56) or O(2^82)
group operations

Pollard's rho DL algorithm [1] solves discrete logarithm in O(\sqrt{n})
where n is the group order. Equivalently the complexity is
O(2^{(log_2{n})/2}).

Both libressl-2.2.3 and openssl-1.0.1p have curves with
log_2{n}=112 and NIST curve with log_2{n}=163.

Assuming Pollard's rho succeeds, the complexity is O(2^56) and O(2^82)
group operations.

The first is close to real time on ``nice hardware''.

To reproduce:

$ ~/inst/openssl-1.0.1p/apps/openssl ecparam -list_curves
 secp112r1 : SECG/WTLS curve over a 112 bit prime field
  sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field

$ ~/inst/libressl-2.2.3/apps/openssl ecparam -list_curves|grep -i ' 1'
   secp112r1 : SECG/WTLS curve over a 112 bit prime field
   sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field

For reference,
http://comments.gmane.org/gmane.comp.security.cypherpunks/6101
Bitcoin networks surpasses 2^80 hashes per week

I believe in an Edward model of EC, the group operation on the EC
isn't much slower than Bitcoin SHA hash, so someone with such
resources might break ...2r1 in nearly real time and ...3k1 in few
weeks.

This resembles the ``DSA oddity'' of _forcing_ q as low as 160
bits, giving the same level (to ...3k1) of security compared to
DSA as shown at [2], search for "160"


[1]:
https://en.wikipedia.org/w/index.php?title=Pollard%27s_rho_algorithm_for_logarithms&oldid=667021803
[2]:
https://j.ludost.net/blog/archives/2015/09/05/rfc-2631_fips_186-3_and_openssls_implementation_of_dsa_appear_broken_and_possibly_backdoored/index.html