[PYTHON-CRYPTO] FIPS stuff (was: Re: PyCrypto rant thread)

[Dwayne C. Litzenberger]

On Tue, Oct 21, 2008 at 06:54:20AM -0700, Paul Hoffman wrote:
>On Mon, Oct 20, 2008 at 1:08 PM, Dwayne C. Litzenberger <dlitz at dlitz.net> wrote:
>> On Mon, Oct 20, 2008 at 08:59:44AM -0700, Paul Hoffman wrote:
>> Yes, and as far as I know, any certification effort would have to target
>> FIPS 186-2, not the FIPS 186-3 draft.  That makes it difficult to implement
>> a policy of avoiding weak algorithms, since the appropriate replacements
>> might not be in the standard yet.
>
>Not true. You could implement both, as many others who have gotten
>certified have. You do not have to make any algorithm you consider
>weak part of your shipping product.

My whole point is that I don't want to add multiple implementations where a 
single implementation would suffice but for the certification requirements.

>> Sure, and that's great.  However, PyCrypto already has a PRNG, so using 
>> the
>> DSS prime-generation algorithm would require implementing *yet another
>> PRNG*.  The only tangible benefit of supporting the DSS prime-generation
>> algorithm is that it allows compact representation of the private key (since
>> you would only need to store the PRNG seed).
>
>The other tangible benefit of swapping your current PRNG with one that
>is FIPS-approved is that you will know that the PRNG you end up with
>is correct.

There is no such guarantee of correctness.  There are implementation bugs 
and algorithmic weaknesses to consider.  If I replaced PyCrypto's current 
PRNG with (NIST-approved) Dual_EC_DRBG, would that be a good thing?

>You would be amazed at the number of hand-rolled PRNGs that people are 
>sure are correct that have flaws.

I would be amazed if most of them _weren't_ flawed.

PyCrypto's flaws have primarily been implementation bugs and error-prone 
API design.  My approach is to take _one_ good design and produce a good 
implementation, rather than taking several designs and trying to implement 
them all.

In the case of a PRNG, I have chosen Fortuna over the DSA PRNG.  Fortuna is 
Niels Ferguson & Bruce Schneier's algorithm, which is profusely documented 
in _Practical Cryptography_.  As far as I know (and I might be mistaken 
here) the design rationale for the DSA PRNG has never been published.

Users are encouraged to use Random.new() as their source of random bytes.  
Random.new() feeds entropy from the OS PRNG and from two different timers 
to Fortuna.  The resulting data flow looks something like this:

     OS PRNG*     --\
     time.time()  ---+----> Fortuna -> isPrime
     time.clock() --/

     (* OS-provided RNG: /dev/urandom, CryptGenRandom, or os.urandom())

Adding the DSA PRNG will make the graph look like this:

     OS PRNG*     --\
     time.time()  ---+----> Fortuna -> DSA PRNG -> isPrime
     time.clock() --/

     (* OS-provided RNG: /dev/urandom, CryptGenRandom, or os.urandom())

If Fortuna is predictable or if isPrime doesn't work, then adding the DSA 
PRNG is unlikely to make things better, but a flawed implementation of the 
DSA PRNG could make things worse.

In this example, my time would be better spent making sure Fortuna and 
isPrime work properly (and attempting to work around weaknesses in various 
OS PRNGs---argh).

If you would like to argue the merits of Fortuna vs the DSA PRNG, that's 
perfectly fine.  "You shouldn't just make up your own algorithm" is also a 
good argument (albeit not applicable in this case).  However, "you can't 
get certified without the DSA PRNG" is not a convincing argument in my 
mind.  That's really all I'm saying.

>>> Quite right. You should have just one that is usable everywhere. That
>>> is the whole point of FIPS 186-3 and NIST SP 800-90.
>>
>> That's a very US-centric point of view.  I would be surprised if the
>> European, Russian, Japanese, and Chinese standards didn't specify different
>> algorithms.
>
>I have never heard of that, and I work with manufacturers who
>implement at least the first three. Do you have any evidence of
>differences in PRNG requirements?

The PRNG was just an example.  I understand that there are a wide variety 
of padding schemes and block cipher modes of operation.  If I were 
implementing PyCrypto from scratch today, I might have omitted certain 
standardized modes of operation, like OFB and CFB mode, since they provide 
no benefit over modes like CBC and CTR.  Similarly, if SHA-1 weren't 
already implemented, I wouldn't implement it today just to pass 
certification.

As I mentioned before, one thing I am explicitly avoiding at the moment is 
X.509 and ASN.1.  I have no idea if these are required for certification, 
but I suspect at least ASN.1 is.

>> If I'm going to care about certification, why would I limit
>> myself to the US standards?  I don't even live in the US.
>
>No one said you you limit yourself to US standards. If you want to add
>support for NESSIE, GOST, and Camillia, feel free to. (Sorry, I don't
>know the name of the Chinese standard you referred to.)  I don't even
>believe that *you* should try to get PyCrypto certified. I am
>proposing that you use the best known crypto practices, and don't do
>anything that would prevent someone else who wants to gat a
>PyCrytpo-based system from spending the time and effort to get their
>system certified, anywhere in the world.

That's exactly what I am proposing.  Good. :-)

>> As for being able to license patents separately from Certicom, I have no
>> motivation to help anyone who makes the software patent problem worse,
>> standards notwithstanding.  It's often a steep uphill battle to get
>> widespread adoption of any patent-encumbered crypto algorithm.  I want to
>> keep it that way.
>
>Note that other crypto libraries include ECC, and it seems kind of
>unlikely that they have licenses for them.

I'm referring specifically to NSA Suite B.  I have heard a few people say 
that it's "okay to use because the NSA licensed the patents", but further 
investigation suggests that the patents are only licensed for narrow, U.S.  
federal government uses.  On the other hand, I've heard that there are 
numerous ECC techniques that _aren't_ covered by patents.  Unfortunately, 
there's no clarity, especially with regard to patents outside the U.S.

>>> That is a difficult statement to prove either way without looking at
>>> the build chains for every product that is released.
>>
>> Fair enough.  What I mean is that for the packages I've seen that have an
>> optional "FIPS mode" or "FIPS build", it seems like only a small 
>> fraction of
>> users actually choose the certified/certifiable code over the "normal" code.
>
>You seem to think there are two different code bases in all those
>products. I have seen the opposite in all cases I have looked at.
>Where there is a difference is that the "FIPS mode", by nature, puts a
>boundary around the code it uses, but tht doesn't prevent the non-FIPS
>mode from using the same code.

Fair enough.  I have no objections to this approach.

>> It suggests that certification status and number of security holes are
>> uncorrelated at best and inversely related at worst.
>
>Fully agree with the first part, not at all with the second unless you
>have any evidence.

Fair enough.

>> I treat FIPS and NIST special publications just like any other peer-reviewed
>> source: useful, but tentative, and susceptible to errors, omissions,
>> obsolescence and politics.
>
>That's a healthy attitude.

:-)

>> I'm certainly not going to make a special effort
>> to avoid the standards,
>
>Err, you said above that you weren't going to use the PRNG from FIPS
>186-3, but instead use your own.

Luckily, I didn't design my own PRNG; I used Fortuna.  See above.

>> but I have no intention of ever compromising the
>> security of PyCrypto (or adding patent-encumbered code) just because some
>> standard or certification process says I should.
>
>Sounds fine.
>

Good.

I should make it clear that I'm not particularly hostile to certification.  
With all the crap out there, I can understand why people would want a 
"certified" product.  On the other hand, the certification standards often 
seem to be obsolete, and I have no intention of implementing obsolete 
algorithms (or allowing weak parameter choices) just to pass certification.

My main complaint about the current FIPS standards is that they mostly 
target a 2**80 security level, which is fairly weak by modern standards.

-- 
Dwayne C. Litzenberger <dlitz at dlitz.net>
  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
  Annual key (2008) - 4B2A FD82 FC7D 9E38 38D9  179F 1C11 B877 E780 4B45
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://mail.python.org/pipermail/python-crypto/attachments/20081021/fa2f710c/attachment.pgp>