Closed Bug 298517 Opened 15 years ago Closed 15 years ago

Implement minimum time intervals for login attempts failures for FIPS 140-2


(NSS :: Libraries, defect, P1)



(Not tracked)



(Reporter: glenbeasley, Assigned: wtc)



(2 files, 3 obsolete files)

Implement minimum time intervals for login attempts failures for FIPS 140-2 
see VE.03.26.01 and AS03.26 

For multiple attemps to use the authentication mechanism during a one minute
period the probability shall be less than one in 100,000 that a random attempt
will succeed or a false acceptance will occur.
OS: Solaris → All
Priority: -- → P1
Hardware: Sun → All
Summary: Implement minimum time intervals for login attempts failures for FIPS 140-2 → Implement minimum time intervals for login attempts failures for FIPS 140-2
Target Milestone: --- → 3.11
This patch fixes this bug and the closely related bug

In plain English, we need to meet the following two
1. The probability of guessing a password is less than
one in 1,000,000.
2. With multiple attempts during one minute, the probability
of guessing a password is less than one in 100,000.

We can meet requirement 1 by requiring a password to have
at least 6 characters.	Then even if only digits are used,
the probability of guessing such a password is less than
10^6 = 1,000,000.

Assuming requirement 1 is met, we can meet requirement 2
by allowing at most 10 attempts per minute.  That can be
accomplished by serializing the login attempts and
requiring at least 6 seconds between login failures.

I hope everyone can at least review the above proposed
solutions.  I think only Bob needs to review the patch,
but additional code reviews by others are welcome.

Some comments on the patch.

1. It contains some code cleanup fixes, which may or may
not be related to this bug.

2. The sftk_newPinCheck function ensures that the new
password is at least 6 characters long.  Note its algorithm.
It counts characters (Unicode code points) as opposed to
bytes if the password is a valid UTF8 string.  However,
if the password is not a valid UTF8 string, it just counts
bytes.	I considered several alternatives but didn't find
any of them clearly better than this algorithm.

3. I added a new lock "pwCheckLock" to the SFTKSlot structure
for serializing the password checks in NSC_SetPIN and NSC_Login.

The existing "slotLock" could actually be used for this purpose,
but I found that "slotLock" does not protect all accesses to
the data it is supposed to protect, and I don't have time to
fix these (minor) thread-safety bugs.  So I decided to add a
new lock so I can clearly see the new code is correct.

4. The minimum 6 seconds between login failures are accomplished
with a 6 second PR_Sleep call after a password check failure.
This freezes Firefox UI for six seconds.  I implemented an
alternative (locking the password/PIN for six seconds) but
Firefox doesn't handle that error code and fails with a very
confusing error dialog.  So I decided to use the PR_Sleep method.
Attachment #189102 - Flags: superreview?(nelson)
Attachment #189102 - Flags: review?(rrelyea)
Comment on attachment 189102 [details] [diff] [review]
Proposed patch for this bug and bug 298516

I should explain how I determined which C_xxx functions need
to be modified.

I first find the functions that take PIN as an argument:
C_InitToken: SO PIN
C_InitPIN: normal user's PIN
C_SetPIN: old PIN, new PIN
C_Login: PIN

Since NSS doesn't use an SO PIN, I eliminate C_InitToken.

I find the functions that may return CKR_PIN_INCORRECT:
C_SetPIN, C_Login.  These need to have the 6 second PR_Sleep
call after a password check failure.

I find the functions that may return CKR_PIN_LEN_RANGE
(and CKR_PIN_INVALID): C_InitPIN, C_SetPIN.  These need to
check the number of characters in the new assword/PIN.
I wonder if we can't boost this by requiring 7 digits chars if the password is
all digits, 6 otherwise. I would like to have to sleep on the order of 1 second,
and no more than 3 seconds. 6 seconds would be a pretty significate user
perception hit (password dialog going a way for 6 seconds is long enough for the
user to be concerned. If it is 1 second or less, the user will not even realize
anything has happenned).

If you implement a limit that works for a single process but not for a group
of cooperating processes, does that meet the requirement?
Might you have to provide some system-wide limit?

The proposed solution will meet the stated requirements for a single process.
But multiple processes could be used in parallel to increaase the frequency
of guesses, and this sleeping scheme will not effectively limit the combined
rate of guesses for the entire set of processes to within the acceptable 
limits, even if each and every process in the set experienced the 6-second 

These new limits porbably need to be enforced only when setting a new password
not when entering a password to login.  You probably need to "grandfather" 
passwords (keys used to encrypt the keyDB) that were set while the token was
not in "FIPS mode".  

Do PKCS11's APIs for setting passwords define an error code by which the
module can reject new passwords that are unacceptable, due to being too short?

I agree that a 6 second wait between tries will seem like something is broken
and will frustrate users.  There is another approach, which is to let the user
guess as fast as he wants until he has tried and failed some number of times 
in succession, then impose a longer timeout.  For example, you might allow 
10 guesses, with a 60 second delay after the 10'th successive failure.  

Having said that, I will tell you that Ii8 believe that long-pause-after-N-
successive-failures style of behavior is ultimately MORE frustrating to the 
user than a series of shorter waits.  I have a device that works that way, 
and the first time I ran into that long delay, I was ready to destroy it.  

The new password/PIN length limits are only enforced
when setting a new password/PIN, in the C_InitPIN
and C_SetPIN methods.

C_InitPIN and C_SetPIN return CKR_PIN_LEN_RANGE if
the new password/PIN is too short or too long.  This
is the error code my sftk_newPinCheck function returns.

I will look into reducing the login wait and dealing
with multiple processes.
Of course we are completely skirting the idea that someone could try to crack
the password with their own code against the key database directly;(.
Attached patch Proposed patch, v1.1 (obsolete) — Splinter Review
I didn't change the 6 character minimum password length
or the 6 second minimum wait time between password check

What's new in this patch is that I count the time between
the last password check failure and the new login attempt.
I subtract this elapsed time from the 6 second wait time,
so the actual PR_Sleep time is much less than 6 seconds
in most cases.	(Human users need several seconds to
read the "incorrect password" error message and re-enter
the password.)	If you still find this approach unacceptable,
I will do something to reduce the minimum wait time to
3 seconds or 1 second; it may simply require a good argument
that the probability of guessing a 6 character password
is much less than one in 1,000,000.

I decided not to address the multi-process password guessing
attack because a proper solution requires extraordinary means.
I will ask the testing lab if we need to handle this scenario.
Please ignore this issue when reviewing this patch.
Attachment #189102 - Attachment is obsolete: true
Attachment #189719 - Flags: superreview?(nelson)
Attachment #189719 - Flags: review?(rrelyea)
Attachment #189102 - Flags: superreview?(nelson)
Attachment #189102 - Flags: review?(rrelyea)
Comment on attachment 189719 [details] [diff] [review]
Proposed patch, v1.1

1.   6 seconds is still to long, even if it is counted from retry to retry. I
can type my password fairly fast. 6 seconds is based on an all digit 6
character password.
If we either restrict all digit passwords to 7, then we can easily show that we
only need to weight .6 seconds or less. 1 second is a perfectly acceptable
time. It's perceivable by the user, but only barely. With a separate FIPS
function to verify adequate pin length, special casing 7 for digits would be
relatively easy.

2. It might be nice to have the UTF8 character counter pulled out as separate
function. We may want to use it in the non-fips pin length check. (an idea, not
a' required to fix')

3. Don't we need to use the LL_ macros when dealing with PRTime, or do we know
we have native PRInt64 support on all our platforms?

4. Since we return after our first failure, it may be possible for a single
attacker to run the following:

for (nexttry=0; nexttry < MAX_PW_TRIES; nexttry++) {

    C_CreateSession( ... );
    crv = C_Login(... passwordArray[nexttry] ...);
    if (crv = CKR_OK) {

No real application of ours will do this, and a real attacker could always
bypass our code themselves, but it does demonstrate an attack against the
cryptographic module, which is what we are evaluating.

Also, we do have real applications that can launch and initialize NSS in less
than 6 seconds, so with a 6 second delay this is still a problem with these

5. (minor) This patch includes another (incorrect fix) from another bug. That
bug now has the correct patch.
Attachment #189719 - Flags: review?(rrelyea) → review-
I first enounctered these requirements (10**-6 probability per guess, and 
10**-5 probability per second) back in 1990, as part of the DoD's "green book"
requirements.  IIRC, at that time, it was widely accepted that the single
guess probability requirement could not be met, even with a 7 character 
minimum, without disallowing dictionary words as passwords.  Otherwise
users would always choose minimum length dictionary words, of which there 
are far fewer than 10**6 (IIRC).

I seem to recall implementing a requirement of 7 characters minimum with no 
more than 5 from the same class (e.g. no more than 5 digits, or 5 letters, 
or 5 non-alphanumeric characters).  
Comment on attachment 189719 [details] [diff] [review]
Proposed patch, v1.1

Removing SR request, since it got r-
Attachment #189719 - Flags: superreview?(nelson)
Nelson: I agree with your comment 9 about password probability.

If the password is truly a PIN, consisting of only digits, it
is easy to argue that the usual assumption of independently
chosen characters holds.

However, if the password is allowed to contain arbitrary
characters, most people will choose one that's either a
word or a "mangled" version of a word.  In that case the
characters are not really independently chosen, so it is
not easy to determine the probability using only password

I will ask the testing lab if NIST has published any password
rules that meet the FIPS 140-2 requirement.
Attached patch Proposed patch, v1.2 (obsolete) — Splinter Review
This patch is essentially the same as the original
patch, with two differences.

1. The minimum password/PIN length is 7 (UTF8) characters,
regardless of the type of characters. Assuming the characters
are independent and the probability of guessing a character
is <= 1/10, the probability of guessing a password/PIN
in one attempt is <= 1/10^7.
2. The delay after an incorrect password/PIN is 1 second.
So the probability of guessing a password/PIN in a one
minute period is <= 60 / 10^7 < 1/10^5.

Our testing lab says it's okay to only rate-limit the
number of login attempts in each process and not impose
a system-wide limit.
Attachment #195199 - Flags: superreview?(nelson)
Attachment #195199 - Flags: review?(rrelyea)
Attachment #189719 - Attachment is obsolete: true
Comment on attachment 195199 [details] [diff] [review]
Proposed patch, v1.2

> Assuming the characters are independent and the probability of 
> guessing a character is <= 1/10, the probability of guessing a 
> password/PIN in one attempt is <= 1/10^7.

Has the testing lab OKed the assumption of independent characters?
If the characters are machine generated, then the assumption of
independence could be correct.	But for human-chosen passwords,
it is almost certainly incorrect, because people will use 
dictionary words.  So I wonder if this assumption is truly 
acceptable to the government (to the people who have the final 
say in a FIPS evaluation).  

Now the rest of this review is purely about the implementation,
not the assumption.

>Index: fipstokn.c

>+	if (ntrail) {
>+	    if ((byte & 0xc0) == 0x80) {
>+		if (--ntrail == 0) {
>+		    nchar++;
>+		}
>+	        continue;
>+	    }
>+	    /* illegal */
>+	    nchar = -1;
>+	    break;
>+	}

I think this would be easier to follow if it were coded as

>+	if (ntrail) {
>+	    if ((byte & 0xc0) != 0x80) {
>+	        /* illegal */
>+	        nchar = -1;
>+	        break;
>+	    }
>+	    if (--ntrail == 0) {
>+		nchar++;
>+	    }
>+	    continue;
>+	}

>+ * The password/PIN is supposed to be a UTF8 string.  So we count the
>+ * number of characters in the string.  However, if the password/PIN is
>+ * not a legal UTF8 string, we just consider each byte a character.  An
>+ * alternative is to reject an illegal UTF8 string as the password/PIN,
>+ * returning CKR_PIN_INVALID.

I think that alternative is better.  It will prevent us from accepting
invalid UTF8 strings as new passwords.	Counting each byte as a char 
tends to consider passwords as acceptable (long enough) that otherwise
might not be.  I think we want to err on the side of strictness to the
standard and the policy.  I'm inclined to give r- for this one issue,
but I might be persuaded otherwise.

>+ * Although NSC_SetPIN and NSC_InitPIN already do the maximum and minimum
>+ * password/PIN length checks, they check the length in bytes as opposed
>+ * to characters.  To meet the minimum password/PIN breaking probability
>+ * requirements in FIPS 140-2, we need to check the length in characters.

Should NSC_SetPIN and NSC_InitPIN be changed to count UTF8 characters 
in addition to, or instead of, adding this check to the FC_ versions of 
those functions?
Attachment #195199 - Flags: superreview?(nelson) → superreview-
Attachment #195199 - Flags: review?(rrelyea)
I implemented the two changes Nelson suggested (rewriting
nested if statements to make the code easier to read, and
rejecting invalid UTF8 string as the password/PIN).  Now
the function returns CKR_PIN_INVALID if the password/PIN
contains invalid UTF8 characters.

I also implemented a new requirement of password consisting
of characters from three or more character classes.  I
didn't implement the scheme Nelson outlined in comment 9
(no more than 5 characters from the same class) because
that scheme limits the maximum password length to 5 x
the number of character classes.  The scheme I implemented
is described in the comment before the function.

Regarding the assumption of mutually independent characters,
this is the model I used to calculate the probability of
guessing a password.  No matter what model I choose for
the password, I have to make some simplifying assumptions,
and some of those assumptions will not match the reality.
But we can only calculate the probability in a mathematical
model.	The mutually independent character model is the
simplest model for probability calculation.
Attachment #195199 - Attachment is obsolete: true
Attachment #196270 - Flags: superreview?(nelson)
Attachment #196270 - Flags: review?(rrelyea)
Wan-Teh, your new patch implements the policy you said it would.  

I should clarify one point in comment 9, the rule wasn't "maximum 5 characters
from any class" but rather was "maximum N-2 characters from any class" where 
N is the total number of characters in the password.  So that policy doesn't
create a 15 character limit.

I think both policies (mine from comment 9 as clarified, and your latest one)
result in similar password guessing probabilities (for a given guessing rate), 
and I fear neither is good enough. :(
I've sent email with more explanation of that fear.
Comment on attachment 196270 [details] [diff] [review]
Proposed patch, v1.3

Everything looks fine except one thing:

The count of characters in the non-ascii case.

The comment says that we count 'Unicode' characters, but the code counts
'encoded bytes', that is 2 byte Unicode characters are counted as 2 bytes, 3
byte Unicode characters or counted as 3 bytes, etc. Either the comment should
change or the code should change. I'm not sure which. It seems to me that a
Kanji character is definately worth more than 1 byte, but it's not clear that a
Thai or Hindi character are (they encode in 3 bytes total, counted as 2 bytes
in this code).

Anyway the comment should definately match the implementation.

Also a nit (not worthy of a r-): adding the word 'single' in front of 'digit'
in the comment 
'or a digit at the end of the password/PIN is not counted.' would be a little
more clear.
Attachment #196270 - Flags: review?(rrelyea) → review-
Comment on attachment 196270 [details] [diff] [review]
Proposed patch, v1.3

Bob, this is the only place I increment the nnonascii

>+	    if (--ntrail == 0) {
>+		nchar++;
>+		nnonascii++;
>+	    }

So nchar and nnonascii are only incremented here when we
reach the end of a multi-byte sequence (when ntrail is
decremented to 0).  So I am counting Unicode characters,
not bytes.
Comment on attachment 196270 [details] [diff] [review]
Proposed patch, v1.3

Apart from issues with comments, I believe this patch correctly implements the
policy Wan-Teh said it did.  I think there is little significant difference
between this policy and the one I proposed.  But in retrospect, I doubt that
either one meets the desired password proability criteria.
Attachment #196270 - Flags: superreview?(nelson)
Comment on attachment 196270 [details] [diff] [review]
Proposed patch, v1.3

arg, my mis read, you are correct. r+ then.

RE nelson's concerns. This is one of those areas where we are asking ourselves,
do we really want to try to get the perfect password environment, or are just
trying to construct a 'defensible' model. I think that this point we need to
use our lab to see if our model is sufficient to pass the FIPS requirement.
Attachment #196270 - Flags: review- → review+
Comment on attachment 196270 [details] [diff] [review]
Proposed patch, v1.3

I totally agree about relying on the lab for guidance.	
That's why I asked about that in comment 13.

We can check in this patch.  If we later determine that a different scheme is
needed, we can replace this one.
Attachment #196270 - Flags: review+
There's good information on password length and password guessing 
probability in appendices C and F of the document entitled:

I rewrote the comment about not counting an uppercase
letter at the beginning of the password or a digit at
the end.  I hope the new comment is clear.
Checking in fipstokn.c;
/cvsroot/mozilla/security/nss/lib/softoken/fipstokn.c,v  <--  fipstokn.c
new revision: 1.11; previous revision: 1.10
Checking in pkcs11.c;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11.c,v  <--  pkcs11.c
new revision: 1.111; previous revision: 1.110
Checking in pkcs11i.h;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11i.h,v  <--  pkcs11i.h
new revision: 1.40; previous revision: 1.39
Closed: 15 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.