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 SignaturesAs 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 GeneratorsThis 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.