Subject: Re: [Cfrg] Weak Diffie-Hellman Primes

From: "Michael D'Errico" <[email-masked]>
Date: Thu, 15 Oct 2020 12:15:43 -0400

Hi,

I've figured out just a bit more.  I'm actually trying
not to work on this problem, but my brain keeps
thinking about it anyway.  The special format of
the prime numbers in RFC's 2409, 3526, and
7919 allow you to create an interesting device to
calculate the private value from a Diffie-Hellman
public value using on the order of N bits (size of
prime P).

The lowest 64 bits of the Diffie-Hellman public
value Y = (2^X mod P) contain a record of when
the mod operation performed a subtraction of a
shifted version of P (see my original message
quoted below).  You can reconstruct a larger value
the modulo operation was working on by adding
back:

    uint64 y = Y;    // low 64 bits of public value

    Y += y * P;    // mod P touched this number

This updated version of Y contains the number
that the mod P operation was working on 64 steps
prior to finishing.  But since the generator was 2
(and 2^X is a solitary 1 followed by a huge string
of zeros), this new larger value of Y will have 64
zeros at the end which can be removed:

    Y >>= 64;    // remove 64 zero bits

This process can now repeat using the lowest 64
bits of Y again:

repeat {

    uint64 y = Y;

    Y += y * P;

    Y >>= 64;

} until (???);

This process unwinds the modulo P operation all
the way back to 2^X in steps of size 64.  The only
thing missing is the terminating condition, which
I'm pretty sure would be: Y contains a single bit
with value 1 (somewhere in the top 64 bits).  If
so, then the value of y would be zero a few times
in a row and then contain a single one bit.

If you can reliably determine when the algorithm
has finished, you could build a device which
computes X from Y using roughly N bits.  It would
be really slow, but it would be guaranteed to find
the answer (32 times faster than brute force
reversing the mod P operation one bit at a time
on average?).

Perhaps there is a way to make this algorithm
(much) faster?

Even if there isn't, it is very interesting to me that
these primes exhibit such a strange feature.

Mike

> From: Michael D'Errico <[email-masked]>
> Sent: *Oct 10, 2020 6:01 PM
> To: [email-masked]
> Subject: [Cfrg] Weak Diffie-Hellman Primes
> 
> Hi,
> 
> I'm not a member of this list, but was encouraged to
> start a discussion here about a discovery I made
> w.r.t. the published Diffie-Hellman prime numbers in
> RFC's 2409, 3526, and 7919.  These primes all have
> a very interesting property where you get 64 or more
> bits (the least significant bits of 2^X mod P for some
> secret X and prime P) detailing how the modulo
> operation was done.  These 64 bits probably reduce
> the security of Diffie-Hellman key exchanges though
> I have not tried to figure out how.
> 
> The number 2^X is going to be a single bit with value
> 1 followed by a lot of zeros.  All of the primes in the
> above mentioned RFC's have 64 bits of 1 in the most
> and least significant positions.  The 2's complement
> of these primes will have a one in the least significant
> bit and at least 63 zeros to the left.
> 
> When you think about how a modulo operation is done
> manually, you compare a shifted version of P against
> the current value of the operand (which is initially 2^X)
> and if it's larger than the (shifted) P, you subtract P at
> that position and shift P to the right, or if the operand
> is smaller than (the shifted) P, you just shift P to the
> right without subtracting.
> 
> Instead of subtracting, you can add the 2's complement
> I mentioned above.  Because of the fact that there are
> 63 zeros followed by a 1 in the lowest position, you will
> see a record of when the modulo operation performed
> a subtraction (there's a one) and when it didn't (there's
> a zero).
> 
> You can use the value of the result you were given by
> your peer (which is 2^X mod P) and then add back the
> various 2^j * P's detailed wherever the lowest 64 bits
> had a value of 1 to find the state of the mod  P operation
> when it wasn't yet finished.  This intermediate result is
> likely going to make it easier to determine X than just a
> brute force search.
> 
> I don't plan to join this list, though I am flattered to have
> been asked to do so.  I'm not a cryptographer.
> 
> Mike

---

From: Anna Johnston <[email-masked]>
Date: Thu, 15 Oct 2020 13:00:09 -0700

Hi Michael,
  The attack you mentioned is logical. If I am not mistaken, the attack is recovering, bit by bit, the quotient (v) in the equation: 2^X = vP + r, where r = 2^X mod P. The fly in the attack is size. 
(1) The smallest P in this list is over 700 bits: P > 2^{700}.
(2) X is on the order of P, as 2 has order q where P=2q+1.
(3) so, 2^X, in its unreduced form, is greater than 2^{2^{700}}
(4) That means that v (the quotient) is greater than 2^{2^{700}}/2^{700}=2^{2^{700}-700} which is still about 2^{2^{700}}, or 2^{700} bits long. 

This size means that only a minuscule fraction of the quotient bits could be computed/stored (not enough seconds in time or atoms in the known universe).

Hope this helps,

Anna

> On Oct 15, 2020, at 09:15, Michael D'Errico <[email-masked]> wrote:
> 
> Hi,
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Michael D'Errico" <[email-masked]>
Date: Thu, 15 Oct 2020 22:22:42 -0400

Hello,

Thank you for your message!

The algorithm I showed should run about 32 times faster
than brute force, even though it's doing a brute force
search.

According to Wikipedia, a 2048-bit Diffie-Hellman prime
is equivalent to 112 bits for a symmetric key, so perhaps
the special structure of both 2048-bit published primes
makes them equivalent to only 107 bits.

Mike

On Thu, Oct 15, 2020, at 16:00, Anna Johnston wrote:
> Hi Michael,
>   The attack you mentioned is logical. If I am not mistaken, the attack 
> is recovering, bit by bit, the quotient (v) in the equation: 2^X = vP + 
> r, where r = 2^X mod P. The fly in the attack is size. 
> (4) That means that v (the quotient) is greater than 
> 2^{2^{700}}/2^{700}=2^{2^{700}-700} which is still about 2^{2^{700}}, 
> or 2^{700} bits long. 
> 
> This size means that only a minuscule fraction of the quotient bits 
> could be computed/stored (not enough seconds in time or atoms in the 
> known universe).
> 
> Hope this helps,
> 
> Anna
>

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 16 Oct 2020 14:07:32 +0100

Hello Mike,

The limiting factor for DH security (and also RSA security) is a very complex
attack algorithm called the Number Field Sieve.  So attacks on 2048-bit DH
safe prime would take time:

* ~ 2^2048 using straightforward brute force
* ~ 2^1024 using collision-based brute force such as Pollard’s Rho
* ~ 2^112 using NFS.

For DSA and sometimes for DH, people use primes p with a generator g
of smaller prime order q, eg q ~ 2^256 here.  This speeds up the operation
at the cost of lower brute-force resistance.  This would reduce the brute
force costs to

* ~ 2^256 using straightforward brute force
* ~ 2^128 using collision-based brute force
* but still ~ 2^112 using NFS

This is generally seen as acceptable, because the cost estimates for rho
attacks are much more certain than for NFS, and are still at an acceptable
level.  Since the security is determined mainly by the best attack, this
doesn’t lower the security.  (Unless NFS at that scale is harder than
projected, but in that case the security is still fine.)

Likewise, your attack slightly speeds up straightforward brute force, but
not (as far as you’ve shown) collision-based brute force or NFS.  So it
doesn’t affect the overall security of DH / DSA.

However, primes of a special form *can* reduce security against the NFS.
But these aren’t primes that specifically begin or end with a lot of 1s, but
rather primes that can be expressed as a low or medium-degree polynomial
with small coefficients.  For example, p = 2^2048 - 1557 would be a poor
choice, because it can be written as a small polynomial, eg

p = x^32 - 1557 with x = 2^64.

I’m not an expert on NFS, so I’m not sure exactly how much security this
knocks off.  Asymptotically you lose about 20% of the bits, (eg 2^112 ->
2^89, which is still out of reach of academics but maybe not large / govt
organizations, especially because most of the work can be amortized
across many discrete logs) but concretely this might be quite different.

Cheers,
— Another Mike

> On Oct 16, 2020, at 3:22 AM, Michael D'Errico <[email-masked]> wrote:
> 
> Hello,
>

---

From: "Michael D'Errico" <[email-masked]>
Date: Fri, 16 Oct 2020 15:53:36 -0400

Hello,

I think that the current definition of a "safe prime"
for use in Diffie-Hellman may be inadequate and
could require more than just:

    [1] P is prime
    [2] (P-1)/2 is also prime

Maybe you also want:

    [3] (P+1) is square-free

This postulate follows from the discussion quoted
below.  I've found that all of the Diffie-Helman primes
published in RFC's 2409, 3526, and 7919 allow you
to brute-force compute a secret 32 times faster than
you would expect just looking at the number of bits.

The prime numbers all have the property that (P+1)
is divisible by 2^64.  This follows from the fact that
the lower sixty-four bits are all ones.  I don't know
if any additional problem arises by having the top
64 bits also equal to 1.

These primes are (assumedly) safe according to the
current definition ([1] and [2] above), but perhaps
effectively 64 or more bits shorter than advertised.

This could mean that the number field sieve would
also be faster (the 2048-bit primes could act like
1984-bit primes), but I have not tried to determine
this myself.

It may be really difficult to find primes satisfying [1],
[2], and [3], so there'd maybe be a trade-off where
you'd allow a few square factors....

This is not my field of expertise, so I apologize if
anyone feels I'm wasting their time.

Mike

---

From: "Michael D'Errico" <[email-masked]>
Date: Sat, 17 Oct 2020 14:34:01 -0400

Hi,

I went to the trouble of computing the factors [*]
of (P+1)/2^64 for all of the "MODP" primes in RFCs
2409 and 3526, and the "FFDHE" primes in RFC 7919,
so I thought it would be good to share the results.

The final factor(s) are not shown but are assumed
to be prime or very large since the factoring
program never finished:

  modp-0768: 3 * 5 * 58502243 * {183-digits}

  modp-1024: 2 * 3^3 * 7 * 61 * 755333 *
	     903210511397 * {267}

  modp-1536: 2^3 * 3^2 * 5 * 7 * 59 * 773 *
             10111 * 713941 * 116114161 * {418}

  modp-2048: 3 * 5 * {597}
 ffdhe-2048: 2^3 * 3^3 * 5 * 101 * 46559 *
             95651 * {583}

  modp-3072: 3 * 13 * 2129 * 5572027361377 * {888}
 ffdhe-3072: 2^3 * 3 * 173 * {902}

  modp-4096: 2 * 3 * 3067 * {1210}
 ffdhe-4096: 3^3 * 5^2 * 5683 * 853854997 * {1199}

  modp-6144: 3 * 19 * 137 * 211 * {1825}
 ffdhe-6144: 2 × 3 × 41 × 9533 × 2417897 * {1818}

  modp-8192: 2^5 * 3^3 * 5 * 7^2 * 17 * 277 * {2438}
 ffdhe-8192: 3 * 937 * 140611 * {2439}

Are there any conclusions to be drawn from this?

Maybe that modp-2048 is "better" than ffdhe-2048,
but ffdhe-8192 is better than modp-8192?

Is modp-1536 a really bad choice for a prime?

Mike

[*] I used: https://www.alpertron.com.ar/ECM.HTM
    (hopefully I didn't make any mistakes....)

>>> [...]
>>>>>   Y>>= 64;    // remove 64 zero bits
>>>>> 
>>>>>   Y>>= 64;
>>>>>> Sent: Oct 10, 2020 6:01 PM
>>>>>> To: [email-masked]
>>>>>> I don't plan to join this list, though I am flattered to
>>>>>> have been asked to do so.  I'm not a cryptographer.
>>>>>> 
>>>>>> Mike

---

From: "Michael D'Errico" <[email-masked]>
Date: Sun, 18 Oct 2020 10:04:39 -0400

Good morning,

Perhaps there is an "ideal" Diffie-Hellman prime
with the following characteristics:

    [1] P is prime
    [2] (P-1)/2 is prime
    [3] (P+1)/4 is prime

Is it possible to generate such a number (in a
reasonable amount of time)?  (You'd be able to
skip any numbers where P mod 8 isn't 3.)

In addition, I notice that all of the published
Diffie-Hellman primes in [MODP] and [FFDHE] have
their 64 most significant bits set to 1.

Is this to make it unlikely for the secret X to
be randomly chosen greater than P (when
calculating 2^X mod P)?

Does Diffie-Hellman fail if you choose a secret
X larger than P?  Do clients and servers check?

Mike

[MODP]:  RFC 2409 and RFC 3526
[FFDHE]: RFC 7919

---

From: "Michael D'Errico" <[email-masked]>
Date: Tue, 20 Oct 2020 12:50:17 -0400

Hi again,

My theory is that vanilla modular-exponentiation
Diffie-Hellman is not as bad as currently thought
and maybe the Number Field Sieve achieves its
impressive results when the prime is "bad", where
bad means that P+1 has lots of (small) factors.

It was pointed out to me that the largest prime
satisfying [1], [2], and [3] in my previous
message is 11, but that [3] could be replaced by:

    [3'] (P+1)/12 is prime

Does anybody have access to a Number Field Sieve
program who can do the following experiment?

  - Choose a prime P such that (P-1)/2 and
    (P+1)/12 are also prime

  - [Added bonus for long string of 1's in
    the top bits? (*)]

  - Determine equivalent security bits for
    the prime P

Maybe a 64-bit prime would have 30 or so bits
of security?

Mike

(*) All of the published primes have sixty-four
1's in the top bits -- is this done for the
reason that Diffie-Hellman fails if the secret
X is greater than P?

[I also corrected the factorizations below; there
were two missing large factors.]

On Sun, Oct 18, 2020, at 10:04, Michael D'Errico wrote:
> On Sat, Oct 17, 2020, at 14:34, Michael D'Errico wrote:
>> Hi,
>> 
>>   modp-0768: 3 * 5 * 58502243 *
>>              500905890761075075179[a] * {183-digits}
>> 
>>   modp-6144: 3 * 19 * 137 * 211 *
>>              233140623089477581[b] * {1807}
>> [a] This factor was accidentally omitted when I
>>     composed my original message
>>
>> [b] I didn't wait long enough to find this factor
>>     but someone else did (via private email)
>> 
>> 
>>> Hello,
>>> 
>>>> The limiting factor for DH security (and also RSA security) is a
>>>> very complex attack algorithm called the Number Field Sieve.  So
>>>> attacks on 2048-bit DH safe prime would take time:
>>>> 
>>>> For DSA and sometimes for DH, people use primes p with a generator
>>>> g of smaller prime order q, eg q ~ 2^256 here.  This speeds up the
>>>> operation at the cost of lower brute-force resistance.  This would
>>>> reduce the brute force costs to
>>>> 
>>>> This is generally seen as acceptable, because the cost estimates for
>>>> rho attacks are much more certain than for NFS, and are still at an
>>>> acceptable level.  Since the security is determined mainly by the
>>>> best attack, this doesn’t lower the security.  (Unless NFS at that
>>>> scale is harder than projected, but in that case the security is
>>>> still fine.)
>>>> 
>>>> Likewise, your attack slightly speeds up straightforward brute force,
>>>> but not (as far as you’ve shown) collision-based brute force or NFS.
>>>> So it doesn’t affect the overall security of DH / DSA.
>>>> 
>>>> However, primes of a special form *can* reduce security against the
>>>> NFS.  But these aren’t primes that specifically begin or end with a
>>>> lot of 1s, but rather primes that can be expressed as a low or medium-
>>>> degree polynomial with small coefficients.  For example,
>>>> p = 2^2048 - 1557 would be a poor choice, because it can be written
>>>> as a small polynomial, eg
>>>> 
>>>> I’m not an expert on NFS, so I’m not sure exactly how much security
>>>> this knocks off.  Asymptotically you lose about 20% of the bits,
>>>> (eg 2^112 -> 2^89, which is still out of reach of academics but maybe
>>>> not large / govt organizations, especially because most of the work
>>>> can be amortized across many discrete logs) but concretely this might
>>>> be quite different.
>>>> 
>>>> Cheers,
>>>> — Another Mike
>>>> 
>>>>> On Fri, Oct 16, 2020, at 03:22, Michael D'Errico wrote:
>>>>> 
>>>>> Hello,
>>>>> 
>>>>> [...]
>>>>> 
>>>>>>> On Thu, Oct 15, 2020, at 09:15, Michael D'Errico wrote:
>>>>>>> 
>>>>>>> Hi,
>>>>>>> 
>>>>>>> On Sat, Oct 10, 2020, at 18:01, Michael D'Errico wrote:

---

From: Christopher Patton <[email-masked]>
Date: Tue, 20 Oct 2020 10:49:02 -0700

> Diffie-Hellman is not as bad as currently thought [...]
>

Note that there's a number of issues with classical DH that are solved by
ECDH. For example, It's much easier to make secret key operations constant
time for ECDH:
https://tools.ietf.org/html/rfc7748#section-1

There are also some crazy attacks that impact classical DH when parameters
are used for a long time:
https://weakdh.org/

> program who can do the following experiment?

It seems like there's lots of great open source implementations to play
with, if you'd like to try it yourself:
https://en.wikipedia.org/wiki/General_number_field_sieve#Implementations

Best,
Chris P.

---

From: "Michael D'Errico" <[email-masked]>
Date: Wed, 21 Oct 2020 11:30:36 -0400

Hello,

If the length of your Diffie-Hellman secret
exponent is on the order of the number of bits
of security you are trying to achieve, then
it's too short.  [Below I propose a way to
make a better choice for the prime P used in
the Diffie-Hellman exchange, which may make it
easier to determine the strength of D-H.]

The prime P will end with at least 2 ones in
the least significant bits (if it's a safe
prime) and all of the published parameters in
[MODP] and [FFDHE] have primes with at least
64 trailing bits of 1.

If you count the number of trailing one bits
and call this M, then brute force finding the
secret takes 1/M the time you would expect.
A custom device can be built to unwind the
modular exponentiation M steps at a time.

For details, please refer to the conversation
below, starting with the first message all the
way at the bottom.

This translates to a loss of log2(M) bits of
security of the secret.

As an example, if you have a requirement that
your secret exponent X can not be determined
in 2^64 operations and assume you can just
generate a random 64-bit number to use as the
Diffie-Hellman exponent, and if you are using
any of the published MODP or FFDHE parameters,
then your secret is actually only giving you
about 58 bits of security.  (This revised
estimate may be optimistic.)

All of the trailing 1 bits show up as factors
of 2 in the number (P+1), which is why I got
interested in factoring these numbers (see
below for a list of the factors of all of the
MODP and FFDHE primes plus one).

I don't know how factors other than 2 affect
the security, so it seems best to avoid them.

Here's a proposed way to avoid any factors of
(P+1) which aren't 2:

  - Choose a prime W of sufficient length
    ending with bits 01 (W mod 4 is 1)

  - Append a whole lot of 1 bits to the
    end of (W-1) and call this P

  - Ensure P and (P-1)/2 are both prime

Would P be roughly twice as long as W at the
minimum?

Does P perform better than expected w.r.t. all
of the known Diffie-Hellman attacks on primes
on the order of the length of W? (P is only
effectively as long as W, right?)

Do we actually know that P isn't effectively
even shorter than W?

Mike

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 21 Oct 2020 21:14:05 +0100

Hello again Mike,

In general, secrets for discrete log systems have to be at least
twice the security level, due to collision-based attacks such as
Pollard rho, baby-step-giant-step, etc.

This is also why P-1 must be divisible by a prime that’s at least
2*lambda bits, where lambda is the desired security level.
Otherwise the Pohlig-Hellman attack breaks the system.

Cheers,
— Mike

> On Oct 21, 2020, at 4:30 PM, Michael D'Errico <[email-masked]> wrote:
> 
> Hello,
>

---

From: Dan Brown <[email-masked]>
Date: Wed, 21 Oct 2020 22:14:54 +0000

> From: Cfrg <[email-masked]> On Behalf Of Michael D'Errico
>
> If the length of your Diffie-Hellman secret exponent is on the order of the
> number of bits of security you are trying to achieve, then it's too short.

Yes, but that's already well-known.  Doubling the number of bits avoids 
various square-root time attacks such as Shank's baby-step-giant-step and 
Pollard rho/lambda attacks (e.g. kangaroo). E.g. 256 bit keys for 128-bit 
security.

> If you count the number of trailing one bits and call this M, then brute 
> force
> finding the secret takes 1/M the time you would expect.

Is your "attack" generic enough to work against composite N?  If so, then 
consider the next speculative argument.

Any given P should divide a composite number N with M trailing one bits, e.g. 
N = P(-1/P mod 2^M), right?  Finding a discrete log mod N allows finding them 
mod P, by reducing the logs mod P-1.

Of course, N is larger, so logs mod N should naturally take little longer than 
in mod P, but is it by a factor log2(M)?

Well, if the key sizes are fixed at K bits, then exhaustive search or Pollard 
rho-type attacks (respectively) should take the same number of mod P or mod N 
operations, 2^K or 2^(K/2) (respectively).  The runtime factor in modular 
arithmetic (between N vs P) is something like 1+log2(M)/log2(N), which seems 
smaller than log2(M).  So, if generic, then your attack should affect all P 
almost equally, right?

> This translates to a loss of log2(M) bits of security of the secret.
As already explained so well by Mike H., brute force attacks do not define the 
security of Diffie--Hellman, because there are better attacks.  Even your 
hypothetical sped-up exhaustive search would still be slower than Pollard rho 
variants or number field sieve (unless the keys have <=2log2(M) bits).

You do not claim to speed up Pollard rho or NFS, right?

If so, the best attacks are unchanged (AFAICT), and thus security is 
unchanged, right?

> As an example, if you have a requirement that your secret exponent X can not
> be determined in 2^64 operations and assume you can just generate a random
> 64-bit number to use as the Diffie-Hellman exponent, and if you are using 
> any
> of the published MODP or FFDHE parameters, then your secret is actually only
> giving you about 58 bits of security.  (This revised estimate may be 
> optimistic.)

It gives 32 bits of security, due to Shank's baby-step giant-step algorithm, 
which takes about 2^32 operations mod P, noticeably less than 2^58 ops.

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 21 Oct 2020 18:20:33 -0700

Is the Pollar-Rho algorithm able to take advantage of the exponent size
that is about the size of the security parameter?

Let's consider ECDLP for P-256 or Curve25519. Does private x for public
Q=xG need to be ~256 bits? I would appreciate pointers on how does
Pollard-Rho can take advantage of x~2^128 for P-256 of Curve25519.

( I know that e.g. NIST documents recommend a private key to be as you Mike
wrote, e.g. 256 bits for P-256)

Thank you.

On Wed, Oct 21, 2020 at 1:14 PM Mike Hamburg <[email-masked]> wrote:

> ...

---

From: Ian Goldberg <[email-masked]>
Date: Wed, 21 Oct 2020 22:15:43 -0400

> Pollard-Rho can take advantage of x~2^128 for P-256 of Curve25519.

If you choose x ~ 2^128 and Q=xG, Pollard's kangaroo (aka Pollard's
lambda) algorithm can break that in ~2^64 time.

https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm

> wrote, e.g. 256 bits for P-256)

As well it should.  Is there a standard that suggests choosing a 128-bit x?

-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo

---

From: Dan Brown <[email-masked]>
Date: Thu, 22 Oct 2020 02:24:39 +0000

​in the case of ECC, See
https://eprint.iacr.org/2015/605
For recent work in this area.

Sent with BlackBerry Work (www.blackberry.com)
________________________________
From: Andrey Jivsov <[email-masked]>
Sent: Oct 21, 2020 9:21 PM
To: Mike Hamburg <[email-masked]>
Cc: Michael D'Errico <[email-masked]>; IRTF CFRG <[email-masked]>
Subject: Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

Is the Pollar-Rho algorithm able to take advantage of the exponent size that is about the size of the security parameter?

Let's consider ECDLP for P-256 or Curve25519. Does private x for public Q=xG need to be ~256 bits? I would appreciate pointers on how does Pollard-Rho can take advantage of x~2^128 for P-256 of Curve25519.

( I know that e.g. NIST documents recommend a private key to be as you Mike wrote, e.g. 256 bits for P-256)

Thank you.

On Wed, Oct 21, 2020 at 1:14 PM Mike Hamburg <[email-masked]<mailto:[email-masked]>> wrote:
Hello again Mike,

Cheers,
— Mike
...

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 22 Oct 2020 15:12:39 -0700

Hm, this was my original question. When the generator is in a large
subgroup/group, I don't see how the algorithm on Wikipedia page benefits
from the limited range of the secret exponent.

I can further enhance my question by saying that instead of using x in
[1,sqrt(group_order)] the secrets are derived with a KDF(128-bit key, x),
where KDF's output is 256 bits (mod group order), so that they are
unpredictable values. However, I don't even see why this is needed.

It seems that the page is written for a small 128-bit subgroup (for a
256-bit curve).

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 22 Oct 2020 19:15:33 -0700

Thanks to an anonymous reply, I see this
https://eprint.iacr.org/2010/615.pdf, sec. 2, which is a good description
of the enhanced algorithm that takes advantage of a short exponent (The
Gaudry-Schost Algorithm). It's similar to Pollard-Rho algorithm, but its
not the the same, and the link below is not an accurate description of this
algorithm. In particular, this later algorithm is structured to contain the
"walk" within the small set corresponding to small exponents, which doesn't
happen with the Pollar-Rho algorithm.

Looks like a private key expanded from 128 bits into 256 is needed as a
mitigation e.g. if you must use a 128-bit secret with e.g. P-256.

Thank you.

---

From: Ian Goldberg <[email-masked]>
Date: Thu, 22 Oct 2020 22:29:48 -0400

> happen with the Pollar-Rho algorithm.

Pollard rho indeed doesn't take advantage of short exponents; we were
talking about Pollard lambda (aka kangaroo), which is a different
algorithm that does.

> mitigation e.g. if you must use a 128-bit secret with e.g. P-256.

And you have to be at least a little bit careful when you do the
expansion.  Trivial things like padding with a constant, etc., don't
help.
-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo

---

From: "Michael D'Errico" <[email-masked]>
Date: Mon, 26 Oct 2020 22:16:38 -0400

Hi Again,

I may have discovered a new type of math object
while trying to find a prime according to my
previous message (which may not be possible).

For lack of a better term, I call them "prefix
primes" which have this weird property:

  If P is prime, P is also a prefix prime
  if you can remove any number of trailing
  bits and add 1 to yield another prefix
  prime multiplied by a power of 2.

I didn't expect to find many examples of this
but there are lots of them!  Here's one set
where the prefix prime generator is 157:

  PP{157}: 157 313 2503 20023 160183
           1281463 164027263 335927834623
           42998762831743

The binary expansion of these numbers
illustrates the idea behind a prefix prime:

  10011101
  100111001
  100111000111
  100111000110111
  100111000110110111
  100111000110110110111
  1001110001101101101101111111
  100111000110110110110111111011111111111
  1001110001101101101101111110111111111101111111

The generator should be a prime ending with
bits 01 [the prime is congruent to 1 (mod 4)].
To find the "next" prime in the set, flip the
final one bit to zero and append as many bits
with value one until you find another prime.
Repeat the process to find the next one, etc.

I was hoping to find a prefix prime Q with
generator W, where P=2*Q+1 is also prime.  I
don't know if this is possible, but I didn't
find one in a few hours of trying.

Maybe these prefix primes are just a curiosity
and not actually useful for anything, but I
thought some of you might find them interesting.

Mike

On Wed, Oct 21, 2020, at 11:30, Michael D'Errico wrote:
>>>>> I think that the current definition of a "safe
>>>>> prime" for use in Diffie-Hellman may be
>>>>> inadequate and could require more than just:
>>>>> 
>>>>>     [1] P is prime
>>>>> This postulate follows from the discussion
>>>>> quoted below.  I've found that all of the
>>>>> Diffie-Helman primes published in RFC's 2409,
>>>>> 3526, and 7919 allow you to brute-force compute
>>>>> a secret 32 times faster than you would expect
>>>>> just looking at the number of bits.
>>>>> 
>>>>> The prime numbers all have the property that
>>>>> (P+1) is divisible by 2^64.  This follows from
>>>>> the fact that the lower sixty-four bits are all
>>>>> ones.  I don't know if any additional problem
>>>>> arises by having the top 64 bits also equal to
>>>>> 1.
>>>>> 
>>>>> These primes are (assumedly) safe according to
>>>>> the current definition ([1] and [2] above), but
>>>>> perhaps effectively 64 or more bits shorter
>>>>> than advertised.
>>>>> 
>>>>> This could mean that the number field sieve
>>>>> would also be faster (the 2048-bit primes could
>>>>> act like 1984-bit primes), but I have not tried
>>>>> to determine this myself.
>>>>> 
>>>>> It may be really difficult to find primes
>>>>> satisfying [1], [2], and [3], so there'd maybe
>>>>> be a trade-off where you'd allow a few square
>>>>> factors....
>>>>> 
>>>>> This is not my field of expertise, so I
>>>>> apologize if anyone feels I'm wasting their
>>>>> time.
>>>>> 
>>>>> Mike
>>>>> 
>>>>>> The limiting factor for DH security (and also RSA security)
>>>>>> is a very complex attack algorithm called the Number Field
>>>>>> Sieve.  So attacks on 2048-bit DH safe prime would take
>>>>>> time:
>>>>>> 
>>>>>> For DSA and sometimes for DH, people use primes p with a
>>>>>> generator g of smaller prime order q, eg q ~ 2^256 here.
>>>>>> This speeds up the operation at the cost of lower brute-
>>>>>> force resistance.  This would reduce the brute force
>>>>>> costs to
>>>>>> 
>>>>>> This is generally seen as acceptable, because the cost
>>>>>> estimates for rho attacks are much more certain than for
>>>>>> NFS, and are still at an acceptable level.  Since the
>>>>>> security is determined mainly by the best attack, this
>>>>>> doesn’t lower the security.  (Unless NFS at that scale is
>>>>>> harder than projected, but in that case the security is
>>>>>> still fine.)
>>>>>> 
>>>>>> Likewise, your attack slightly speeds up straightforward
>>>>>> brute force, but not (as far as you’ve shown) collision-
>>>>>> based brute force or NFS.  So it doesn’t affect the overall
>>>>>> security of DH / DSA.
>>>>>> 
>>>>>> However, primes of a special form *can* reduce security
>>>>>> against the NFS.  But these aren’t primes that specifically
>>>>>> begin or end with a lot of 1s, but rather primes that can
>>>>>> be expressed as a low or medium-degree polynomial with
>>>>>> small coefficients.  For example, p = 2^2048 - 1557 would
>>>>>> be a poor choice, because it can be written as a small
>>>>>> polynomial, eg
>>>>>> 
>>>>>> I’m not an expert on NFS, so I’m not sure exactly how much
>>>>>> security this knocks off.  Asymptotically you lose about
>>>>>> 20% of the bits, (eg 2^112 -> 2^89, which is still out of
>>>>>> reach of academics but maybe not large / govt organizations,
>>>>>> especially because most of the work can be amortized across
>>>>>> many discrete logs) but concretely this might be quite
>>>>>> different.
>>>>>> 
>>>>>> Cheers,
>>>>>> — Another Mike
>>>>>> 
>>>>>>> The algorithm I showed should run about 32
>>>>>>> times faster than brute force, even though
>>>>>>> it's doing a brute force search.
>>>>>>> 
>>>>>>> According to Wikipedia, a 2048-bit Diffie-
>>>>>>> Hellman prime is equivalent to 112 bits for
>>>>>>> a symmetric key, so perhaps the special
>>>>>>> structure of both 2048-bit published primes
>>>>>>>>> I've figured out just a bit more.  I'm
>>>>>>>>> actually trying not to work on this
>>>>>>>>> problem, but my brain keeps thinking about
>>>>>>>>> it anyway.  The special format of the
>>>>>>>>> prime numbers in RFC's 2409, 3526, and
>>>>>>>>> 7919 allow you to create an interesting
>>>>>>>>> device to calculate the private value from
>>>>>>>>> a Diffie-Hellman public value using on the
>>>>>>>>> order of N bits (size of prime P).
>>>>>>>>> 
>>>>>>>>> The lowest 64 bits of the Diffie-Hellman
>>>>>>>>> public value Y = (2^X mod P) contain a
>>>>>>>>> record of when the mod operation performed
>>>>>>>>> a subtraction of a shifted version of P
>>>>>>>>> (see my original message quoted below). 
>>>>>>>>> You can reconstruct a larger value the
>>>>>>>>> modulo operation was working on by adding
>>>>>>>>> back:
>>>>>>>>> 
>>>>>>>>> This updated version of Y contains the
>>>>>>>>> number that the mod P operation was
>>>>>>>>> working on 64 steps prior to finishing. 
>>>>>>>>> But since the generator was 2 (and 2^X is
>>>>>>>>> a solitary 1 followed by a huge string of
>>>>>>>>> zeros), this new larger value of Y will
>>>>>>>>> have 64 zeros at the end which can be
>>>>>>>>> removed:
>>>>>>>>> 
>>>>>>>>> This process can now repeat using the
>>>>>>>>> lowest 64 bits of Y again:
>>>>>>>>> 
>>>>>>>>> repeat {
>>>>>>>>> 
>>>>>>>>>   uint64 y = Y;
>>>>>>>>> 
>>>>>>>>>   Y += y * P;
>>>>>>>>> 
>>>>>>>>>   Y >>= 64;
>>>>>>>>> 
>>>>>>>>> } until (???);
>>>>>>>>> 
>>>>>>>>> This process unwinds the modulo P
>>>>>>>>> operation all the way back to 2^X in steps
>>>>>>>>> of size 64.  The only thing missing is the
>>>>>>>>> terminating condition, which I'm pretty
>>>>>>>>> sure would be: Y contains a single bit
>>>>>>>>> with value 1 (somewhere in the top 64
>>>>>>>>> bits).  If so, then the value of y would
>>>>>>>>> be zero a few times in a row and then
>>>>>>>>> contain a single one bit.
>>>>>>>>> 
>>>>>>>>> If you can reliably determine when the
>>>>>>>>> algorithm has finished, you could build a
>>>>>>>>> device which computes X from Y using
>>>>>>>>> roughly N bits.  It would be really slow,
>>>>>>>>> but it would be guaranteed to find the
>>>>>>>>> answer (32 times faster than brute force
>>>>>>>>> reversing the mod P operation one bit at a
>>>>>>>>> time on average?).
>>>>>>>>> 
>>>>>>>>> Perhaps there is a way to make this
>>>>>>>>> algorithm (much) faster?
>>>>>>>>> 
>>>>>>>>> Even if there isn't, it is very
>>>>>>>>> interesting to me that these primes
>>>>>>>>> exhibit such a strange feature.
>>>>>>>>> 
>>>>>>>>> Mike
>>>>>>>>> 
>>>>>>>>>> I'm not a member of this list, but was
>>>>>>>>>> encouraged to start a discussion here
>>>>>>>>>> about a discovery I made w.r.t. the
>>>>>>>>>> published Diffie-Hellman prime numbers
>>>>>>>>>> in RFC's 2409, 3526, and 7919.  These
>>>>>>>>>> primes all have a very interesting
>>>>>>>>>> property where you get 64 or more bits
>>>>>>>>>> (the least significant bits of 2^X mod P
>>>>>>>>>> for some secret X and prime P) detailing
>>>>>>>>>> how the modulo operation was done.  These
>>>>>>>>>> 64 bits probably reduce the security of
>>>>>>>>>> Diffie-Hellman key exchanges though I
>>>>>>>>>> have not tried to figure out how.
>>>>>>>>>> 
>>>>>>>>>> The number 2^X is going to be a single
>>>>>>>>>> bit with value 1 followed by a lot of
>>>>>>>>>> zeros.  All of the primes in the above
>>>>>>>>>> mentioned RFC's have 64 bits of 1 in the
>>>>>>>>>> most and least significant positions. 
>>>>>>>>>> The 2's complement of these primes will
>>>>>>>>>> have a one in the least significant bit
>>>>>>>>>> and at least 63 zeros to the left.
>>>>>>>>>> 
>>>>>>>>>> When you think about how a modulo
>>>>>>>>>> operation is done manually, you compare a
>>>>>>>>>> shifted version of P against the current
>>>>>>>>>> value of the operand (which is initially
>>>>>>>>>> 2^X) and if it's larger than the
>>>>>>>>>> (shifted) P, you subtract P at that
>>>>>>>>>> position and shift P to the right, or if
>>>>>>>>>> the operand is smaller than (the shifted)
>>>>>>>>>> P, you just shift P to the right without
>>>>>>>>>> subtracting.
>>>>>>>>>> 
>>>>>>>>>> Instead of subtracting, you can add the
>>>>>>>>>> 2's complement I mentioned above. 
>>>>>>>>>> Because of the fact that there are 63
>>>>>>>>>> zeros followed by a 1 in the lowest
>>>>>>>>>> position, you will see a record of when
>>>>>>>>>> the modulo operation performed a
>>>>>>>>>> subtraction (there's a one) and when it
>>>>>>>>>> didn't (there's a zero).
>>>>>>>>>> 
>>>>>>>>>> You can use the value of the result you
>>>>>>>>>> were given by your peer (which is 2^X mod
>>>>>>>>>> P) and then add back the various 2^j *
>>>>>>>>>> P's detailed wherever the lowest 64 bits
>>>>>>>>>> had a value of 1 to find the state of the
>>>>>>>>>> mod P operation when it wasn't yet
>>>>>>>>>> finished.  This intermediate result is
>>>>>>>>>> likely going to make it easier to
>>>>>>>>>> determine X than just a brute force
>>>>>>>>>> search.
>>>>>>>>>> 
>>>>>>>>>> I don't plan to join this list, though I
>>>>>>>>>> am flattered to have been asked to do so.
>>>>>>>>>> I'm not a cryptographer.
>>>>>>>>>> 
>>>>>>>>>> Mike