ICMC: Status of the Transition to New Algorithms and Stonger Keys

Allen Roginsky, Mathematician, NIST

FIPS 140-2 doesn't talk much about the algorithms themselves, they are covered in the Annexes.  There were minor changes back in 2002/2003, however the algorithms have changed. New algorithms have come in, old ones have been deprecated.

Under the ISO rules, every country can choose their own algorithms. In the US, we've already chosen our algorithms for FIPS 140-2. We'll likely continue to use the same ones in FIPS 140-4 (or whatever we call them).

The current major algorithm documents are SP 800-131A and FIPS 186-4.  The stronger key requirements went into effect last year and there is a major hit coming in at the end of 2015.

Why are we doing this transition?  Security strenght of 80 bits is insufficient (the 56-bit strong DES was broken long ago; attacks on the SHA-1 collision resistance property; advances in integer factorization; etc).  Some of the currently approved algorithms aren't strong regardless of the key length (the non SP-800-90A RNGs).  Transition plans were fist announced in SP 800-57, Part 1 in 2005.  We've delayed this from going into effect from 2010 to 2015, but cannot delay it further or we'll be hurting the consumers.

Approved are the best algorithms. Deprecated algorithms are not recommended, but can be used. This is different than restricted, which you should not use.  Legacy use have no guarantee, but really should not be used, except to verify previously generated signatures, for example.  Some algorithms are just simply not allowed.

For example, SKIPJACK decryption was allowed at the end of 2010 for legacy use only, but SKIPJACK encryption is disallowed.  Only 8 certificates were ever issued, so there were not any complaints bout this change.

At the end of 2010, two-key 3DES encyrption is restricted (100 bits of strength for two-key 3DES with no more than 3^20 (plantext, cyphertext) pairs), two-key 3DES decryption is legacy-use only.
At the end of 2015, two-key 3DES encryption is disallowed.  AES and three-key 3DES are acceptable.  We allowed this for so long, because it was in wide use and the attacks were not straight forward.

Digital Signatures

As of the end of 2010, signature generation algorithms with less than 112 bits of encryption strenght became deprecated. As of the end of 2013, there was a transition from FIPS 186-2 to FIPS 186-4 and signature generation algorithms with less than 112 bits of cryptographic strength became disallowed.

Signature verification with less than 112 bits of strength is legacy-use, beginning in 2011.

Deterministic Random Number Generators

This is the BIG problem! As of the end of 2010, te non-SP-800-90A compliant RNGs became deprecated. As of the endof 2015, the non-SP-800-90A compliant RNGs will become disallowed. As of the end of 2015, the non-SP-800-90A complaint RNGs became disallowed - RETROACTIVELY!  This will be a big expense, as previously purchased software can no longer be used.

Note from Randy Easter: What this means is that every validation that was done over the last 15 years and every validation that is not using this RNG, that item will be moved to the nonapproved line.  If the keying algorithm is using this RNG, ALL of those functions become non approved.

Key Agreement and Key Transport

As of the end of 2013, Key Agreement and Key Transport algorithms stay acceptable if: key strength is at least 112 bits AND the algorithms are compliant with the appropriate NIST standards: SP 800-56A, SP 800-56B and SP 800-38F. As of the end of 2013, the non-compliant Key Agreement and Key Transport (Key Encapsulation) algorithms have become deprecated if key strength is at least 112 bits.  Key wrapping must be complaint with one of the provisions of SP 800-38F. Everything else is disallowed.

Others

Hash and MAC functions will be impacted, as well as some key derivation algorithms. See SP 800-131A for details

FIPS 186-2 to 186-4 Transition

Beginning in 2014, new implementations shall be tested for their compliance with FIPS 186-4. This applies to domain parameter generation, key pair generation and digital signature generation.  Signature verification per FIPS 186-2 is Legacy-use. Beginning this year (2014), RSA digital signature keys must be generated as shown in FIPS 186-4.

Future Transition Plans

You bet - already looking forward to the future.  We want to transition away from non-Approved implementations of key agreement (DLC-based) and key transport (RSA-based) schemes.  Unfortunately, there are too many modules in existence that are non compliant with SP 800-56A and 56B. We need a well thought out strategy for transition.