full-disclosure - Re: [FD] Should openssl accept weak DSA/DH keys with g = +/- 1 ?

Open Source and information security mailing list archives

Message-ID: <alpine.LRH.2.02.1404171815040.5393@argo.troja.mff.cuni.cz>
Date: Thu, 17 Apr 2014 18:50:06 +0200 (CEST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: Georgi Guninski <guninski@...inski.com>
Cc: fulldisclosure@...lists.org
Subject: Re: [FD] Should openssl accept weak DSA/DH keys with g = +/- 1 ?

On Wed, 16 Apr 2014, Georgi Guninski wrote:

> AFAICT weak DH keys can't be recognized
> since they can be well formed.

You can check whether the modulus is a safe prime (p = 2q + 1
where q is a prime number as well) and whether the generator is not a 
degenerate one (g != +/- 1; this is sufficient to prove that the order
of g is either q or 2q).

Does anyone use non-safe primes for DH? Afaik any well-known moduli 
are safe. And openssl dhparam generates safe primes only.

The check would burn quite a lot of CPU cycles but it would be feasible 
and the client could cache results because bening servers are expected to 
switch groups rather infrequently.

> The hardness of the discrete log doesn't depend on the size of $p$ but 
> on the size of $q$ which is the largest prime factor of the 
> multiplicative order of $g$.

No. It depends on both of those sizes in the sense that for some moduli
the algorithm whose complexity depends on q (Pollard's rho?) is better, 
for other moduli other algorithms (e.g. NFS) depending on p (L_p(a,c) to 
be precise) are more efficient.

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /

_______________________________________________
Sent through the Full Disclosure mailing list
http://nmap.org/mailman/listinfo/fulldisclosure
Web Archives & RSS: http://seclists.org/fulldisclosure/

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives