On 6/12/2013 11:35 PM, Matt Caswell wrote:
On 12 June 2013 21:15, Jakob Bohm <jb-open...@wisemo.com> wrote:
As for the DH_check_pub_key() function, checking if pubkey is in the
range "two to large prime minus 2, inclusive" is an insufficient check
against accepting degenerate keys. For instance NIST SP 800-56A
requires the following check for most FIPS certified implementations
(they also allow some less practical checks that typically work only
for static DH keys or your own keys):
As far as I am aware there is no claim for NIST SP 800-56A compliance
in the new versions
So how did you go about getting this stuff FIPS validated in the first
place?
I kind of expected the FIPS validated module to include all those OpenSSL
implemented algorithms which can be subjected to the CMVP,
not some random subset.
From "User Guide for the OpenSSL FIPS Object Module v2.0":
"Only the algorithms listed in tables 4a and 4b of the Security Policy
are allowed in FIPS mode.
Note that Diffie-Hellman and RSA are allowed in FIPS mode for key
agreement and key
establishment even though they are “Non-Approved” for that purpose
...snip...
The version of DH used by TLS is a variant on PKCS#3 and not the X9.42
specification, and hence
is not compliant with SP800-56A. For example, the requirement:
Each private key shall be unpredictable and shall be generated in the range [1,
q-1] using an Approved random bit generator.
For TLS clients that requirement cannot be satisfied as stated because
the parameter "q" is not sent
from server to client, only the parameter "p". Clients generate a
private key in the range [1, p-1]
instead"
I was not aware of that specific TLS protocol shortcoming, which makes
it difficult to do a lot of things right.
Are the p values used generally from some list of well known group
parameters or are they completely arbitrary.
In the former case, one could have a lookup table mapping the well
known p values to their well known q values.
In the latter case, the best one could do would be to check if the
p value received is a "safe prime" (i.e. if (p-1)/2 is a prime),
in which case q=(p-1)/2. If p is not a strong prime not on some
list of well known defaults, then the q value will probably be
too hard to find (basically, one needs to factor (p-1) and pick
the largest prime factor, which is generally a hard problem unless
the factor j=(p-1)/q happens to have only small prime factors).
For some uses, just eliminating as many small prime factors from
(p-1) as one can get away with might help, as what one would get
is q1=k*q where k is an unknown odd number and q is the unknown
prime factor we really want.
So something like (I am winging it here, a real mathematician
should check my logic):
// Side channel attacks almost impossible
// This code only processes the received public key and public
// group parameters, the time, power etc. expended (and all
// intermediary results) reveal nothing not already known
// by any potential attacker.
// The only danger is that if this code is run in one thread
// while another thread or process performs a calculation
// which leaks secret data or keys into the CPU load and/or
// cache load, then the time it takes to complete or
// fail this test may serve as a remote probe of those
// side channels of the other thread/process, however this
// is equality true of any other remotely observable
// processing of non-secret data.
Input: group parameters p, q and g, remote public key A
// If q is unknown, pass in 0, it will be replaced by the
// real value or a multiple thereof
Output: Error or OK
// Comments will refer to the remote private key as a
// Open question to the mathematicians: Is it ok to use a
// subgroup of large composite order, without allowing the
// discrete logarithm to be easily found via the factors
// of the subgroup order?
// If so, many tests below are overly restrictive, otherwise they
// detect at least some cases of too small subgroups
if (!primality_test(p))
fatalerror: Bad group parameters // p is not even a prime
if (q != 0) {
if (bitsin(q) < securitylevel)
fatalerror: Bad group parameters
// subgroup is too small
if (q >= p)
fatalerror: Bad group parameters // q out of range
tmp = p - 1
(tmp, r) = (tmp / q, tmp % q); // Bigint moddiv
if (r != 0)
fatalerror: Bad group parameters // q is not any subgroup size
// BEGIN ASSUMPTION: Size of generated subgroup must be prime, as
// otherwise its factorization might help an attacker compute the
// discrete logarithm. Therefore a subgroup of composite size
// must be rejected
if (!primality_test(q))
fatalerror: Bad group parameters
// q is not a prime, which is required in all
// DH variants that explicitly state the value of q
// END ASSUMPTION
} else {
// q not sent and not otherwise known
// This also handles scenarios where it is remotely specified that
// p is a so called "safe prime", i.e. that p = 2*q + 1
q = p-1
// BEGIN ASSUMPTION: Size of generated subgroup must be prime, as
// otherwise its factorization might help an attacker compute the
// discrete logarithm. Therefore a subgroup of composite size
// must be rejected
While (!lsb(q))
q >>= 1;
for s in smallprimes {
do {
tmp = q;
(q, rsmall) = (q / s, q % s); // Bigint moddiv by word
} while (rsmall == 0);
q = tmp; // Undo failed division
}
// if q is a prime, it is what we want, otherwise it is
// a multiple q1 = k * q, where k has no small prime factors
// END ASSUMPTION
if (primality_test(q)) {
if (bitsin(q) < securitylevel)
fatalerror: Bad group parameters
// There is no large enough prime order subgroup
} else {
// BEGIN ASSUMPTION: Size of generated subgroup must be prime, as
// otherwise its factorization might help an attacker compute
// the discrete logarithm. Therefore a subgroup of composite
// size must be rejected
// q holds an unknown multiple of the real subgroup
// size, with the multiplier having no factors on our
// list of small primes
if (bitsin(q) < securitylevel + bitsin(smallprimetes[last]))
fatalerror: Bad group parameters
// There is no large enough prime order subgroup
Warning: Subgroup size not fully known
// The variable q holds a multiple of the real q, and we
// don't know for sure if the real q has too few bits.
// END ASSUMPTION
}
}
if (g <= 1)
Fatal: Bad group parameters // generator does not generate any
// non-trivial subgroup
if (g >= p)
Fatal: Bad group parameters // out of range, protocol violation
tmp = g ** q % p; // mod_exp
if (tmp != 1)
Fatal: Bad group parameters
// g is not a generator of any large prime order subgroup
// Note: If q is a composite with both smallish and large
// factors, then this does not detect if g generates
// one of the smaller groups
tmp = A ** q % p; // mod_exp
if (tmp != 1)
FATAL: Bad public key
// A is not in the subgroup generated by g
// If q != real_q, this test may not catch all such cases
if (A <= 1)
FATAL: Bad public key // Out of range or a is 0
if (A >= p)
FATAL: Bad public key // Out of range
tmp = A * q mod p;
if (tmp <= 1)
FATAL: Bad public key // a == real_q - 1
tmp = A;
while (tmp >= g) {
(tmp, r) = (tmp / g, tmp % g);
if (r) {
tmp = 0;
break;
}
}
if (tmp == 1)
FATAL: Bad public key;
// a is so small, non-modular discrete log found it, in fact
// a == number of iterations done
// This is definitely not secure even if formally permitted.
// This also catches a == 1, which is formally not permitted
// for the same reason
// Note: If q != real_q, tests above are not as complete as they
// should be
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// To genereate own keypair (b, B) where B==g ** b % p
Input: group parameters p, q and g
// q may be a preliminary value from the code above
Output: public key B, private key b
// Note: This will only iterate if q != real_q and we randomly
// stumple upon a closer approximation of real_q
b = q;
for (;;) {
// Note: This first step is a NOP on the first (and usually
// only iteration)
// q and b are both multiple's of g's order and b <= q
// b is thus a better approximation of g's order
// and gcd(q, b) an even better one.
q = gcd(q, b); // Note: because we won't use b, this leaks nothing
s = bitsin(q);
if (s < securitylevel)
FATAL: Evil group parameters; // order of g too small to be
// secure, but large enough
// to go undetected except by
// chance
s = s / (bitsin(g) - 1); // Because g > 1, no div by 0
tmp = q - 2 * s;
// BEGIN SENSITIVE DATA PROCESSING, must avoid side channels
b = random(tmp);
b += s + 1;
// b is now in range s + q to q - s inclusive
B = g ** b % p
// END SENSITIVE DATA PROCESSING
// Hereafter, references to the private key occur only if/when
// discarded and no longer secret
// Rest of this function only needed if q is not a prime
// because q was auto-guessed and the guessing had to
// sett,e on a composite value for q
if (B <= 1) {
// q != real_q and b is a multiple of g's order
// b is thus a better approximation of g's order
// and gcd(q, b) an even better one.
continue;
}
tmp = B;
i = 0;
while (tmp >= g) {
(tmp, r) = (tmp / g, tmp % g);
++i;
if (r) {
tmp = 0;
break;
}
}
if (tmp == 1) {
// q != real_q and b - i is a multiple of g's order
// b - i is thus a better approximation of g's order
// and gcd(q, b - i) an even better one.
b = b - i;
continue;
}
tmp = B;
i = 0;
while (++i < s) {
tmp = tmp * g % p;
if (tmp <= 1)
break;
}
if (tmp <= 1) {
// q != real_q and b + i is a multiple of g's order
// b + i is thus a better approximation of g's order
// and gcd(q, b + i) an even better one.
b = b + i;
continue;
}
// Key seems good
break;
}
Enjoy
Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. http://www.wisemo.com
Transformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
