[Crypto] Cracking Diffie–Hellman key exchange using CADO-NFS + Logjam SSL/TLS attack

This is yet another explanation of Diffie–Hellman key exchange.

Tiny Python example

I'll start right at Python code, without introducing mathematical equations.

First, pick a prime. I like 1009.

I'll use Wolfram Mathematica to find primitive root (I explained earlier) of 1009:

In[]:= PrimitiveRootList[1009]
Out[]= {11,17,22,26,31,33,34,38,46,51,52,53,55,65,66,76,78,79,83,85,86,88,89,91,92,94,95,97,99,102,106,107,114,115,118,124,130,133,138,146,153,154,156,158,159,161,163,165,166,172,176,178,181,188,190,193,194,195,198,208,214,215,220,228,233,234,235,237,238,239,244,248,249,257,258,262,263,264,265,267,272,273,277,279,281,282,285,291,293,297,298,301,304,305,307,308,310,311,318,319,321,325,326,329,340,342,358,364,366,367,368,372,377,385,389,390,395,399,401,408,413,415,416,419,422,424,430,434,439,445,446,458,462,466,468,470,474,475,477,483,489,493,495,498,511,514,516,520,526,532,534,535,539,541,543,547,551,563,564,570,575,579,585,587,590,593,594,596,601,608,610,614,619,620,624,632,637,641,642,643,645,651,667,669,680,683,684,688,690,691,698,699,701,702,704,705,708,711,712,716,718,724,727,728,730,732,736,737,742,744,745,746,747,751,752,760,761,765,770,771,772,774,775,776,781,789,794,795,801,811,814,815,816,819,821,828,831,833,837,843,844,846,848,850,851,853,855,856,863,871,876,879,885,891,894,895,902,903,907,910,912,914,915,917,918,920,921,923,924,926,930,931,933,943,944,954,956,957,958,963,971,975,976,978,983,987,992,998}

I like the smallest one -- 11.

So now $p=1009$ and $g=11$.

These two parameters is called 'Diffie Hellman Group'.

Run the following code (DH_prepare.py) twice:

#!/usr/bin/env python3
import random

p=1009
g=11

secret=random.randrange(1, p-1)
print ("secret=", secret)
public=pow(g, secret, p)
print ("public=", public)

The first result for Alice, the second for Bob:

 % python3 DH_prepare.py
secret= 315
public= 204

 % python3 DH_prepare.py
secret= 60
public= 668

Alice and Bob exchange 'public' keys and run another program (DH_receive.py):

#!/usr/bin/env python3
import sys

p=1009
g=11

my_secret=int(sys.argv[1])
received=int(sys.argv[2])

shared_secret=pow(received, my_secret, p)

print ("shared_secret=", shared_secret)
 % python3 DH_receive.py 315 668
shared_secret= 540

 % python3 DH_receive.py 60 204
shared_secret= 540

Now Alice and Bob have the shared secret: 540. Eve (eavesdropper) only knows two 'public' values and can't reconstruct shared secret.

Let's say this: you can reconstruct the 'shared secret' only using Alice's 'public' value and Bob's 'secret' value (or vice versa). But it's impossible to reconstruct it using two 'public' values. Both Alice and Bob have enough information for that.

In fact, you can view the function $g^{secret} \equiv public \mod p$ as a hash function. It's easy to compute, but hard to compute the inverse function (which is discrete logarithm).

By the way, these two functions are bijective with each other, if $secret \lt p$ and $g$ is a primitive root of $p$. So for each $public$ value, there is a single $secret$ corresponding to it. The problem is to find it.

Why it works anyway?

Because:

$public\_alice = g^{secret\_alice} \mod p$

$public\_bob = g^{secret\_bob} \mod p$

Bob will compute:

$public\_alice^{secret\_bob} \mod p$

... can be rewritten:

$(g^{secret\_alice} \mod p) ^{secret\_bob} \mod p$

... again:

$(g^{secret\_alice}) ^{secret\_bob} \mod p$

... again:

$g^{secret\_alice \cdot secret\_bob} \mod p$

So, the shared_secret is basically: $g^{secret\_alice \cdot secret\_bob}$, but it's 'limited' or 'cut' by $p$. This expression can be computed by both Alice and Bob.

Without modular arithmetics, sharing just $g^{secret\_alice}$ would be senseless -- can be broken much easier.


Wolfram Mathematica can find inverse for small values: finding discrete logarithms for some modulo. Let's revese back Alice's 'public' value:

In[]:= MultiplicativeOrder[11,1009,204]
Out[]= 315

Bob's 'public' value:

In[]:= MultiplicativeOrder[11, 1009, 668]
Out[]= 60

Using SageMath:

sage: p=1009
sage: g=11
sage: x=668
sage: discrete_log(Mod(x,p), Mod(g,p), p-1)
60

Mathematica and SageMath performance

Both can 'reverse' small values, but not the big one, used in cryptography.

With Mathematica 12 I can only able to find exponents for $p \approx 2^{32}$

People say that SageMath can do this better. Let's see.

My CPU is 6-core AMD Ryzen 5 3600, but SageMath's discrete_log() function uses only a single thread.

I've found that SageMath can reliably find discrete logarithms for $p \approx 2^{64}$ -- almost instantly.

But for larger $p$, like $p \approx 2^{80}$, sometimes it can do it, sometimes it can eat all your RAM and crash. In my case, 52GB RAM wasn't enough.

But sometimes, given enough luck, it can find a logarithm for $p \approx 2^{128}$.

Before experimenting, it's advised to set a RAM limit (Ubuntu Linux), 52GB in my case:

ulimit -Sv 52000000

(The 'ulimit' command is to be executed before SageMath.)

Otherwise your computer may freeze due to swapping/memory paging.

Why using primitive root for $g$ and prime number for $p$?

You can use arbitrary number for $g$. But this will reduce a number of all possible 'secret' values. See again my previous post. This imply that attacker would have smaller space for brute-force.

See also

Even more -- $p$ may not be a prime number:

There is no obvious reason to restrict the size of the finite field to a prime number. So, from now
on the size of the field can be any prime power q=p^e (see Theorem B. 16 or Theorem B.20).

In [Lune87], Chapter XIII, efficient algorithms to find primitive elements in finite fields are
described. See also Problem B.6 and Problem B. 10.

( Henk C.A. van Tilborg -- FUNDAMENTALS OF CRYPTOLOGY (2002) )

This is a real case. While I've been writing this blog post, I prepared various $p$ numbers for SageMath to gauge its discrete_log() function's performance. SageMath correctly 'reversed' and found the exponent, and once it showed different exponent, but still correct. But mine exponent was also correct. (I checked both.) How this can be? Didn't I state already that there is a bijective mapping between two functions. Ouch, I forgot to reset $g$, which was set to 2, aligning with OpenSSL parameters, I previously worked with. But my random prime numbers I generated with Wolfram Mathematica required different $g$ as primitive root to be working good in this scheme. In other words, my mistake could shorten keyspace for attacker, however, everything would work correctly.

'Serious' Python example

Let's now use 2048-bit $p$. I'll take a recommended constant from RFC 7919, that is based on Euler constant.

Despite the fact, that these constants are all well-known, no problems at all. Even having $p$ and $g$, discrete logarithm problem is still hard.

DH_prepare_2.py:

#!/usr/bin/env python3
import random

p=0xFFFFFFFFFFFFFFFFADF85458A2BB4A9AAFDC5620273D3CF1D8B9C583CE2D3695A9E13641146433FBCC939DCE249B3EF97D2FE363630C75D8F681B202AEC4617AD3DF1ED5D5FD65612433F51F5F066ED0856365553DED1AF3B557135E7F57C935984F0C70E0E68B77E2A689DAF3EFE8721DF158A136ADE73530ACCA4F483A797ABC0AB182B324FB61D108A94BB2C8E3FBB96ADAB760D7F4681D4F42A3DE394DF4AE56EDE76372BB190B07A7C8EE0A6D709E02FCE1CDF7E2ECC03404CD28342F619172FE9CE98583FF8E4F1232EEF28183C3FE3B1B4C6FAD733BB5FCBC2EC22005C58EF1837D1683B2C6F34A26C1B2EFFA886B423861285C97FFFFFFFFFFFFFFFF
g=2

secret=random.randrange(1, p-1)
print ("secret=", secret)
public=pow(g, secret, p)
print ("public=", public)

DH_receive_2.py:

#!/usr/bin/env python3
import sys

p=0xFFFFFFFFFFFFFFFFADF85458A2BB4A9AAFDC5620273D3CF1D8B9C583CE2D3695A9E13641146433FBCC939DCE249B3EF97D2FE363630C75D8F681B202AEC4617AD3DF1ED5D5FD65612433F51F5F066ED0856365553DED1AF3B557135E7F57C935984F0C70E0E68B77E2A689DAF3EFE8721DF158A136ADE73530ACCA4F483A797ABC0AB182B324FB61D108A94BB2C8E3FBB96ADAB760D7F4681D4F42A3DE394DF4AE56EDE76372BB190B07A7C8EE0A6D709E02FCE1CDF7E2ECC03404CD28342F619172FE9CE98583FF8E4F1232EEF28183C3FE3B1B4C6FAD733BB5FCBC2EC22005C58EF1837D1683B2C6F34A26C1B2EFFA886B423861285C97FFFFFFFFFFFFFFFF
g=2

my_secret=int(sys.argv[1])
received=int(sys.argv[2])

shared_secret=pow(received, my_secret, p)

print ("shared_secret=", shared_secret)

Run DH_prepare_2.py twice:

 % python3 DH_prepare_2.py

secret= 13398249543775387671653288988935976350849077618344786160010229385740479997961409219497692489438705135146781463507619443743516182409077070833836981454105128863615667537528211364960356967997691337320923884414825012423575766085878368524086137326908007843544929192170545819108317884909616739404223364281785418937490344751620023254960336104186873790540873868716628844507413346952719789331150148111302925779469262243973801639011161561417866816488583496218626170668516999541932909643237774322165010010677431109650429451091232399942951477478568241517002396366950991356568250889209331817040399392142563909291941247954418747254

public= 22283721717219209737396435546886881160465582836860750128349243177226635935345066595208044363861638182685876962736088865327596794745596901065779695009118978857910650991653418211147709561328066523003893739980594470881575261350702829074527680188272616866544230081871238203277100826622551815636660109509230422538824027534902465223268071724010616338640146336528514370110721396332932408936718128515818680933735242858955024880835966623623476500287900214425042350874460534897460884477009989397518403747839271928301487058825079977226081607136891585142309184845019803638074909244498717200654407671986268642396118164749665911580

 % python3 DH_prepare_2.py

secret= 8057800931498322290778482564400977998338900779977414044809785856806619726705111501037775481819833531193405303151579280775893615733753611526130767827386642376909237633986806520109750467220161309029242483221735139892186548575311731412073672910444226075279785633868877710196100001107932120498947144010937702586322272385525152293450381725695204725624505979591436928771097798686811411415275891508487100678691637399873361444880233168261103713885687067807312453050563997436148913473397638779026662590874571879072831631874241524736941797897962583238880706695994237413163107244022310379171154708173552302094482911953439174971

public= 10880775340675814592719931421669682295699031931090466476023055033561172917209945042126408557036513534551774685870053664637863204812478321548563751258604900618312786706521392405867822701699319692179709956025624557145955897493362603432208690437636481567312986225698302464785482572143787239300612938720204195695995451801934716259669354462996360503895153023013781865123187025969009737877043972996661565763244153502442574791476139742672805421996951510639024588280464682909546356361753378191219652827946374691604837831710973477657137709375355106777710975869639094671426271544546331995729884803638515742013385971223419205077

Generate 'shared secret' for both parties:

 % python3 DH_receive_2.py 13398249543775387671653288988935976350849077618344786160010229385740479997961409219497692489438705135146781463507619443743516182409077070833836981454105128863615667537528211364960356967997691337320923884414825012423575766085878368524086137326908007843544929192170545819108317884909616739404223364281785418937490344751620023254960336104186873790540873868716628844507413346952719789331150148111302925779469262243973801639011161561417866816488583496218626170668516999541932909643237774322165010010677431109650429451091232399942951477478568241517002396366950991356568250889209331817040399392142563909291941247954418747254 10880775340675814592719931421669682295699031931090466476023055033561172917209945042126408557036513534551774685870053664637863204812478321548563751258604900618312786706521392405867822701699319692179709956025624557145955897493362603432208690437636481567312986225698302464785482572143787239300612938720204195695995451801934716259669354462996360503895153023013781865123187025969009737877043972996661565763244153502442574791476139742672805421996951510639024588280464682909546356361753378191219652827946374691604837831710973477657137709375355106777710975869639094671426271544546331995729884803638515742013385971223419205077

shared_secret= 7601389475506658369589877614349435024528828523616570077451544241473768648277556709385895655963655366588664470214221763334249504211754873250341542121357567422194445291381892003315645976625399570009323513559210749050616927506475362182406664651606783083024179240975613038094153626248964051913753705832550150126073283123938303937011111938795437847434786053813333007893902867685446613361757645664621237521097149542489068567954517306675165564691480001270201344122370403435829793572198063007384266620320163135355399753238287905687132090846682978668580275059453281478835952093190515644109612342118714961229218400332129947075

 % python3 DH_receive_2.py 8057800931498322290778482564400977998338900779977414044809785856806619726705111501037775481819833531193405303151579280775893615733753611526130767827386642376909237633986806520109750467220161309029242483221735139892186548575311731412073672910444226075279785633868877710196100001107932120498947144010937702586322272385525152293450381725695204725624505979591436928771097798686811411415275891508487100678691637399873361444880233168261103713885687067807312453050563997436148913473397638779026662590874571879072831631874241524736941797897962583238880706695994237413163107244022310379171154708173552302094482911953439174971 22283721717219209737396435546886881160465582836860750128349243177226635935345066595208044363861638182685876962736088865327596794745596901065779695009118978857910650991653418211147709561328066523003893739980594470881575261350702829074527680188272616866544230081871238203277100826622551815636660109509230422538824027534902465223268071724010616338640146336528514370110721396332932408936718128515818680933735242858955024880835966623623476500287900214425042350874460534897460884477009989397518403747839271928301487058825079977226081607136891585142309184845019803638074909244498717200654407671986268642396118164749665911580

shared_secret= 7601389475506658369589877614349435024528828523616570077451544241473768648277556709385895655963655366588664470214221763334249504211754873250341542121357567422194445291381892003315645976625399570009323513559210749050616927506475362182406664651606783083024179240975613038094153626248964051913753705832550150126073283123938303937011111938795437847434786053813333007893902867685446613361757645664621237521097149542489068567954517306675165564691480001270201344122370403435829793572198063007384266620320163135355399753238287905687132090846682978668580275059453281478835952093190515644109612342118714961229218400332129947075

Now that shared secret can be used as a key for symmetrical cryptography like AES, etc. This is 'serious-grade' cryptography.

As of 2022, it's unbreakable. Even given the fact that $g$ and $p$ are known. 'Secret' values cannot be recovered even if you have both 'public' values and $g$ and $p$.

The exponentiation operation modulo $p$ (pow() in Python and PowerMod[] in Wolfram Mathematica) is so fast you can create 'shared secrets' for each session, or even more frequently.

This implies that all past 'shared secrets' are not recoverable (if not saved somewhere), meaning, all the previous traffic wouldn't be possible to decrypt. See also: Forward secrecy

Why using these well-known/popular parameters?

   These additions to the "Supported Groups Registry" are described in
   detail in Appendix A.  They are all safe primes derived from the base
   of the natural logarithm ("e"), with the high and low 64 bits set to
   1 for efficient Montgomery or Barrett reduction.

   The use of the base of the natural logarithm here is as a "nothing-
   up-my-sleeve" number.  The goal is to guarantee that the bits in the
   middle of the modulus are effectively random, while avoiding any
   suspicion that the primes have secretly been selected to be weak
   according to some secret criteria.  [RFC3526] used pi for this value.
   See Section 8.5 for reasons that this document does not reuse pi.

( RFC 7919 )

Yes, indeed. $p$ based on $e$: RFC 7919; $p$ based on $\pi$: RFC 3526

Using such a 'famous' mathematical constants has some benefits. Do you remember how IBM sent DES S-Boxes to NSA and they returned in slightly modified form? But as with $e$ or $\pi$, no one can tamper these constants.

These constants are recommended by OpenSSL developers.

MD2 also used $\pi$: "This step uses a 256-byte "random" permutation constructed from the digits of pi."

As well as MD5: see RFC1321 3.4 and this answer.

'Logjam' attack authors found that the most popular $p$ constant for DH-512 in 2015 is: 9fdb8b8a004544f0045f1737d0ba2e0b274cdf1a9f588218fb435316a16e374171fd19d8d8f37c39bf863fd60e3e300680a3030c6e4c3757d08f70e6aa871033

(Hardcoded in Apache webserver.)

Second is: d4bcd52406f69b35994b88de5db89682c8157f62d8f33633ee5772f11f05ab22d6b5145b9f241e5acc31ff090a4bc71148976f76795094e71e7903529f5a824b

(Supplied with OpenSSL.)

( From their paper )

Finding parameters for 'serious' Python example

But you may want to find your own DH parameters.

I can manage this with OpenSSL:

% openssl dhparam -out dhparams.pem 4096

(But generation is slow, even on a fast computer. (Because finding a big safe prime is slow.) This is why you have to precompute these parameters, or use well-known ones. You can't generate them for each TLS session, for example.)

I ran this openssl command on 6-core AMD Ryzen 5 3600. It took ~300 seconds or ~5 minutes.

Of course, as a sysadmin, preparing DH parameters for whatever service you have on server, you can wait ~5 minutes. But this is unrealistic to prepare these for each TLS session.

% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MIICCAKCAgEA/UNNEpl9ltVSw2udvOSVH6Za/LcluZ3snQzOrLZYRdNOV48HrsvO
ukapgGGTO+/iQm3crJw6P0+AKZhSrq3D4skwDBWYPHcwmzCbMSC/Pd1rpMODrq1S
Lhnoc4kt3T091Af0EB1UriP0Tsx4+M3dD3uu/0+C2p8n7ZFck79pYxyqfRiqXylm
aSxz6gQOxp5n+VB52+IhdystDGKBD5gJ0oiWIIA0QfNLmhrYzwSe1TlSQC9J4FTE
fbU1rFDlj4gyA/LhFu0ckmJM6iuv3EpeOBAK9p8yqymq3M0zCuxQHR72G6CD+u/l
dIV42/DLXgBnSgAJ3cdlT1TkAvoZ2r3IBR5Wtr2JdsiPA+MosV+D9Z8+THxDDxm3
ZrUCiQWGgqZsW4GF+CcEJb2MUty9syZ3ChZS97KEexBsgDzsAVICrDdsWzs+QYxW
VCXEepZGmfnAVZt3JlOF81S5r+P90xEO0R/T3ueHYJApi7+E8aw/ji+ikrhsNWps
2TE2059HZbMLQLSXQC9Bzp1x65i/Sb0bI6hJ/CFnPIY0gypdxhGZdrO2GtOsYgp1
rEZIh/5hYYU3Ujz9/NHWq64Y6Bpbhcy5o4DN2cVfq71nj+ROzW/+d2U7AJg8xWng
ar3iMt+DgNkJ/zQfU3ZrmT57L/PvDyDY9D4BhZkvMYeqjpZeIFSvBssCAQI=
-----END DH PARAMETERS-----

% openssl asn1parse < dhparams.pem
    0:d=0  hl=4 l= 520 cons: SEQUENCE
    4:d=1  hl=4 l= 513 prim: INTEGER           :FD434D12997D96D552C36B9DBCE4951FA65AFCB725B99DEC9D0CCEACB65845D34E578F07AECBCEBA46A98061933BEFE2426DDCAC9C3A3F4F80299852AEADC3E2C9300C15983C77309B309B3120BF3DDD6BA4C383AEAD522E19E873892DDD3D3DD407F4101D54AE23F44ECC78F8CDDD0F7BAEFF4F82DA9F27ED915C93BF69631CAA7D18AA5F2966692C73EA040EC69E67F95079DBE221772B2D0C62810F9809D2889620803441F34B9A1AD8CF049ED53952402F49E054C47DB535AC50E58F883203F2E116ED1C92624CEA2BAFDC4A5E38100AF69F32AB29AADCCD330AEC501D1EF61BA083FAEFE5748578DBF0CB5E00674A0009DDC7654F54E402FA19DABDC8051E56B6BD8976C88F03E328B15F83F59F3E4C7C430F19B766B50289058682A66C5B8185F8270425BD8C52DCBDB326770A1652F7B2847B106C803CEC015202AC376C5B3B3E418C565425C47A964699F9C0559B77265385F354B9AFE3FDD3110ED11FD3DEE7876090298BBF84F1AC3F8E2FA292B86C356A6CD93136D39F4765B30B40B497402F41CE9D71EB98BF49BD1B23A849FC21673C8634832A5DC6119976B3B61AD3AC620A75AC464887FE61618537523CFDFCD1D6ABAE18E81A5B85CCB9A380CDD9C55FABBD678FE44ECD6FFE77653B00983CC569E06ABDE232DF8380D909FF341F53766B993E7B2FF3EF0F20D8F43E0185992F3187AA8E965E2054AF06CB
  521:d=1  hl=2 l=   1 prim: INTEGER           :02

You can use these constants -- $p$ and $g$, right away. Right in the Python code I offered earlier.

Why $g$ is always 2?

By curiosity, I tried to generate DH parameters for key sizes 256..4096 bits, and found that $g$ is always 2. Why 2?

Such a generator is called a "primitive root" (which is trivial to find when p is "safe").

...

   It is recommended to use 2 as generator, because it improves
   efficiency in multiplication performance.  It is usable even when it
   is not a primitive root, as it still covers half of the space of
   possible residues.

...

   It is important to employ only safe primes as moduli, as they allow
   us to find a generator g so that the order of the generated subgroup
   does not factor into small primes, that is, with p = 2q + 1, the
   order has to be either q or p - 1.  If the order is p - 1, then the
   exponents generate all possible public values, evenly distributed
   throughout the range of the modulus p, without cycling through a
   smaller subset.  Van Oorshot and Wiener note that using short private
   exponents with a random prime modulus p makes the computation of the
   discrete logarithm easy [VAN-OORSCHOT].  However, they also state
   that this problem does not apply to safe primes.

( RFC 4419 )

Safe prime is a prime in form $p=2q+1$ where both $p$ and $q$ are primes. These are used in all DH implementatoins, but it's important to note that this is not a strict requirement. It's just makes several algorithms to work better/faster/simpler.

Two possible attacks

MITM is possible for DH in general. Of course, you can pretend you're Bob for Alice. And you're Alice for Bob, at the same moment.

There will be two shared secrets, but Mallory (in the middle) would know both. He can read and modify traffic. But this is a general problem for DH.

Another problem: DH_prepare*.py uses random.randrange(1, p-1). I don't know how Python's library do this.

But in general, getting 2048 or 4096 bits of entropy is a task far from trivial. See RFC 4086. Care is to be taken when using (C)PRNG.

If your random() function use 32-bit seed, for example, it would be a piece of cake for an attacker to enumerate them all. That would imply that both 'secret' and 'public' values only have 32 bits of entropy, no matter how big these numbers are.

A classic bug: using a 32-bit seed for PRNG, and then calling rand() function many times in serie to get enough bits for your long 'secret' key. Of course, an attacker only needs to bruteforce that 32-bit seed value.

Cracking DH-256 with CADO-NFS

Let's now use heavy machinery.

Generate DH-256:

% openssl dhparam -out dhparams.pem 256

% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MCYCIQDoFpe1cB/4o5fP9I1ZZOQr32QGqhO7o6OiS+rrUZc0ewIBAg==
-----END DH PARAMETERS-----

% openssl asn1parse < dhparams.pem
    0:d=0  hl=2 l=  38 cons: SEQUENCE
    2:d=1  hl=2 l=  33 prim: INTEGER           :E81697B5701FF8A397CFF48D5964E42BDF6406AA13BBA3A3A24BEAEB5197347B
   37:d=1  hl=2 l=   1 prim: INTEGER           :02

Using Wolfram Mathematica, I will also find the $ell$ parameter for CADO-NFS. See README.dlp. Remember safe primes? $ell$ is $q$. Finding it is trivial: just factor $p$ or divide $p-1$ by 2.

In[133]:= p=16^^E81697B5701FF8A397CFF48D5964E42BDF6406AA13BBA3A3A24BEAEB5197347B;

In[134]:= g=2;

In[135]:= (*Or use this: FactorInteger[p-1]*)

In[136]:= ell=(p-1)/2;

In[137]:= secret=Random[Integer,{1,ell}]
Out[137]= 7934140645160489087289656956441415697281962880349867745619770353314420891184

In[139]:= public=PowerMod[g,secret,p]
Out[139]= 88040204463577827248022472790210266970490684840632186604213471839237284800973

In[140]:= CommandLine="./cado-nfs.py -dlp -ell "<>ToString[ell]<>" target=" <>ToString[public]<>" "<>ToString[p]
Out[140]= ./cado-nfs.py -dlp -ell 52488249280999883780991186966113904727034251326410736142720734204350276803133 target=88040204463577827248022472790210266970490684840632186604213471839237284800973 104976498561999767561982373932227809454068502652821472285441468408700553606267

CADO-NFS installation instruction you can find here.

Running it on 6-core AMD Ryzen 5 3600 (~4 minutes):

Info:root: CADO_DEBUG is on, data kept in /tmp/cado.7i4pmpu8
Info:root: Checking that log(2) and log(3) are consistent...
Info:root:   p = 104976498561999767561982373932227809454068502652821472285441468408700553606267
Info:root:   ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133
Info:root:   log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178
Info:root:   log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101
Info:root: Also check log(target) vs log(2) ...
Info:root: target = 88040204463577827248022472790210266970490684840632186604213471839237284800973
Info:root: log(target) = 28153509009254853143733272656017027349752145111918347033278047853598428730789
28153509009254853143733272656017027349752145111918347033278047853598428730789
Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.7i4pmpu8/p80.parameters_snapshot.0 target=<target>

Ouch! CADO-NFS doesn't print the 'secret' value.

It solves diophantine equation: $x^y=target \mod p$ But without telling you $x$.

But it's easy to find $x$ if you can run CADO-NFS several times and know some theory behind logarithms.

Run it for target=2 ($g$ value):

% ./cado-nfs.py /tmp/cado.7i4pmpu8/p80.parameters_snapshot.0 target=2

...

Info:root: Checking that log(2) and log(3) are consistent...
Info:root:   p = 104976498561999767561982373932227809454068502652821472285441468408700553606267
Info:root:   ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133
Info:root:   log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178
Info:root:   log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101
Info:root: Also check log(target) vs log(2) ...
Info:root: target = 2
Info:root: log(target) = 20850424008160966946484149043838897061775211265562183011766205305702305660178
20850424008160966946484149043838897061775211265562183011766205305702305660178

Now we see: this value was printed by CADO-NFS at first place: "log2 = ...", so no need to run CADO-NFS second time.

You may know that $log_b(x) = \frac{log(b)}{log(x)}$ -- the last two logarithms can be of arbitrary base. But things are different for diophantine equations in modular arithmetics. This rule becomes slightly different. (The first output of CADO-NFS I'll name 'logtarget', the second 'logg': $log(g)$)

$logg^{-1} \mod ell$ -- this is modular inverse, to be used if you want to replace division by multiplication.

$secret = logtarget \cdot (logg^{-1} \mod ell) \mod ell$

( Some of the theory is explained in my other collection of mathematical notes. )

Reconstruct the 'secret' using Wolfram Mathematica:

In[148]:= logtarget=28153509009254853143733272656017027349752145111918347033278047853598428730789;

In[149]:= logg=20850424008160966946484149043838897061775211265562183011766205305702305660178;

In[150]:= Mod[logtarget*PowerMod[logg,-1,ell],ell]
Out[150]= 7934140645160489087289656956441415697281962880349867745619770353314420891184

Indeed, it is the same as been generated using Random[Integer,{1,ell}].

At this point, astute reader may ask, why using $ell$ instead of $p$? Because $p$ is a safe prime (as generated by OpenSSL) and effectively, it's all limited by modulo $ell$, not $p$.

But the difference is not significant, just one bit:

In[191]:= Log[2, p] // N
Out[191]= 255.859

In[193]:= Log[2, ell] // N
Out[193]= 254.859

Raising the bar: cracking DH-320 with CADO-NFS

% openssl dhparam -out dhparams.pem 320

% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MC4CKQCijY12yObAyUj0ngneSu0/Uh/gXyrdqLZbQvCDsGeBOXI/WAIElKQ7AgEC
-----END DH PARAMETERS-----

% openssl asn1parse < dhparams.pem
    0:d=0  hl=2 l=  46 cons: SEQUENCE
    2:d=1  hl=2 l=  41 prim: INTEGER           :A28D8D76C8E6C0C948F49E09DE4AED3F521FE05F2ADDA8B65B42F083B0678139723F58020494A43B
   45:d=1  hl=2 l=   1 prim: INTEGER           :02
In[173]:= p=16^^A28D8D76C8E6C0C948F49E09DE4AED3F521FE05F2ADDA8B65B42F083B0678139723F58020494A43B;

In[174]:= g=2;

In[175]:= ell=(p-1)/2;

In[176]:= secret=Random[Integer,{1,ell}]
Out[176]= 99837042807986311247572608007098848566328141427417511605593944555864084325327113900468311574143

In[177]:= public=PowerMod[g,secret,p]
Out[177]= 819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535

In[178]:= CommandLine="./cado-nfs.py -dlp -ell "<>ToString[ell]<>" target=" <>ToString[public]<>" "<>ToString[p]
Out[178]= ./cado-nfs.py -dlp -ell 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949 target=819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899

28 minutes on the same CPU:

Info:root: CADO_DEBUG is on, data kept in /tmp/cado.49m3wqzt
Info:root: Checking that log(2) and log(3) are consistent...
Info:root:   p = 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899
Info:root:   ell = 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949
Info:root:   log2 = 656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481
Info:root:   log3 = 21090163601429749780531272128570957412543080143027196514836751563768934683700030454141298669455
Info:root: Also check log(target) vs log(2) ...
Info:root: target = 819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535
Info:root: log(target) = 670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272
670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272
Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=<target>

BTW, did you notice the last line? "If you want to compute a new target, run ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=<target>"

Plug these values:

In[201]:= logtarget=670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272;

In[202]:= logg=656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481;

In[203]:= Mod[logtarget*PowerMod[logg,-1,ell],ell]
Out[203]= 99837042807986311247572608007098848566328141427417511605593944555864084325327113900468311574143

This is the correct value, same as 'secret' we used.

Interestingly, can we try another 'secret' value now?

In[204]:= secret2 = Random[Integer, {1, ell}]
Out[204]= 415811153047574077839411211302321097841230130891095315432045532418232041491290051605042781367275

In[205]:= public2 = PowerMod[g, secret2, p]
Out[205]= 664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721
% ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721

Only 20 seconds!

Info:root: Checking that log(2) and log(3) are consistent...
Info:root:   p = 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899
Info:root:   ell = 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949
Info:root:   log2 = 656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481
Info:root:   log3 = 21090163601429749780531272128570957412543080143027196514836751563768934683700030454141298669455
Info:root: Also check log(target) vs log(2) ...
Info:root: target = 664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721
Info:root: log(target) = 356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748
356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748

Check:

In[206]:= logtarget2=356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748;

In[207]:= Mod[logtarget2*PowerMod[logg,-1,ell],ell]
Out[207]= 415811153047574077839411211302321097841230130891095315432045532418232041491290051605042781367275

CADO-NFS works that fast now because it cached some data for your $ell$ and $p$ and now can reuse this information.

Wow, not a small piece of data:

 % du -sh /tmp/cado.49m3wqzt
1.7G    /tmp/cado.49m3wqzt

Of course, it would be bigger for bigger values.

DH-512

I also tried 512-bit keys.

CADO-NFS predicts that it will process the data 2-4 months, on the same Ryzen CPU. I haven't run it. But of course, it's all doable, on off-the-shelf hardware, just be patient enough.

CADO-NFS: updated version (Feb-2022)

In February 2022, CADO-NFS has been updated to print discrete logarithm given $g=2$.

Info:root: CADO_DEBUG is on, data kept in /tmp/cado.kdiz2kdp
Info:root:   p = 104976498561999767561982373932227809454068502652821472285441468408700553606267
Info:root:   ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133
Info:root: Checking that log(2) and log(3) are consistent...
Info:root:   unscaled_log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178 mod ell
Info:root:   unscaled_log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101 mod ell
Info:root: Checking that log(2) and log(3) are consistent... passed!
Info:root: Also check log(target) vs log(2) ...
Info:root:   target = 88040204463577827248022472790210266970490684840632186604213471839237284800973
Info:root:   unscaled_log(target) = 28153509009254853143733272656017027349752145111918347033278047853598428730789 mod ell
Info:root: Also check log(target) vs log(2) ... passed!
Info:root: Using g=2 as a generator
Info:root:   log2 = 1 mod ell
Info:root:   log3 = 21740896517265330765147904861772161197398290270049688221140686652820410005729 mod ell
Info:root: target = 88040204463577827248022472790210266970490684840632186604213471839237284800973
Info:root: log(target) = 7934140645160489087289656956441415697281962880349867745619770353314420891184 mod ell
7934140645160489087289656956441415697281962880349867745619770353314420891184
Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.kdiz2kdp/p80.parameters_snapshot.0 target=<target>

So now you don't need to recover it by additional steps. The final log(target) value is the exponent you want, for base=2.

But I left instructions for older CADO-NFS anyway. They can help a bit in understanding discrete logarithms and modular arithmetics.

Also, when you'll google for CADO-NFS blog/forum posts, you'll find 'old-style' printouts (generated before Feb-2022). So I think it's better to use both 'styles' here in this blog post.

'Logjam' attack

This is the essence of 'Logjam' attack: 1, 2.

An attacker can use a huge power to cache all the data beforehand, for specific, well-known $p$ and then use it when they need to reverse back a 'shared secret', relatively fast. He can use the same CADO-NFS tool I've shown.

(Remember these two most used $p$ for DH-512 in 2015?)

It's speculated NSA may have enough power to break DH-512, maybe even DH-1024 and wiretap SSL/TLS traffic.

Protection for sysadmins: generate DH parameters with $p$ of at least 2048 bits. Recommendations from Logjam authors.

Alas, well-known $p$ values (such as based on $\pi$, $e$) are not to be used. Not because they are 'bad' or 'insecure', but because an attacker can get prepared for these beforehand.

Why CADO-NFS can factor composite numbers and compute discrete logarithms?

They are close problems

Thanks

Emmanuel Thomé

SageMath forum

Some reading that helped me

This blog post also helped me.

This answer also helped.

And the CADO-NFS mailing list: 1, 2, 3.

Further reading in my blog

How to crack RSA-512 on off-the-shelf hardware in 4 days using CADO-NFS.


UPD: as seen at reddit.


List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.