RFC Errata
RFC 5931, "Extensible Authentication Protocol (EAP) Authentication Using Only a Password", August 2010
Note: This RFC has been updated by RFC 8146
Source of RFC: IETF - NON WORKING GROUPArea Assignment: sec
Errata ID: 5681
Status: Reported
Type: Technical
Publication Format(s) : TEXT
Reported By: Dan Harkins
Date Reported: 2019-03-31
Section 2.8.3 says:
2.8.3 Fixing the Password Element
Fixing the Password Element involves an iterative hunting-and-pecking
technique using the prime from the negotiated group's domain
parameter set and an ECC- or FFC-specific operation depending on the
negotiated group.
2.8.3.1. ECC Operation for PWE
The group-specific operation for ECC groups uses pwd-value, pwd-seed,
and the equation for the curve to produce the Password Element.
First, pwd-value is used directly as the x-coordinate, x, with the
equation for the elliptic curve, with parameters a and b from the
domain parameter set of the curve, to solve for a y-coordinate, y.
If there is no solution to the quadratic equation, this operation
fails and the hunting-and-pecking process continues. If a solution
is found, then an ambiguity exists as there are technically two
solutions to the equation and pwd-seed is used to unambiguously
select one of them. If the low-order bit of pwd-seed is equal to the
low-order bit of y, then a candidate PWE is defined as the point
(x, y); if the low-order bit of pwd-seed differs from the low-order
bit of y, then a candidate PWE is defined as the point (x, p - y),
where p is the prime over which the curve is defined. The candidate
PWE becomes PWE, and the hunting and pecking terminates successfully.
Algorithmically, the process looks like this:
found = 0
counter = 1
do {
pwd-seed = H(token | peer-ID | server-ID | password | counter)
pwd-value = KDF(pwd-seed, "EAP-pwd Hunting And Pecking", len(p))
if (pwd-value < p)
then
x = pwd-value
if ( (y = sqrt(x^3 + ax + b)) != FAIL)
then
if (LSB(y) == LSB(pwd-seed))
then
PWE = (x, y)
else
PWE = (x, p-y)
fi
found = 1
fi
fi
counter = counter + 1
} while (found == 0)
Figure 3: Fixing PWE for ECC Groups
2.8.3.2. FFC Operation for pwe
The group-specific operation for FFC groups takes pwd-value, and the
prime, p, and order, r, from the group's domain parameter set (see
Section 2.2.1 when the order is not part of the defined domain
parameter set) to directly produce a candidate Password Element, pwe,
by exponentiating the pwd-value to the value ((p-1)/r) modulo the
prime. If the result is greater than one (1), the candidate pwe
becomes pwe, and the hunting and pecking terminates successfully.
Algorithmically, the process looks like this:
found = 0
counter = 1
do {
pwd-seed = H(token | peer-ID | server-ID | password | counter)
pwd-value = KDF(pwd-seed, "EAP-pwd Hunting And Pecking", len(p))
if (pwd-value < p)
then
pwe = pwd-value ^ ((p-1)/r) mod p
if (pwe > 1)
then
found = 1
fi
fi
counter = counter + 1
} while (found == 0)
Figure 4: Fixing PWE for FFC Groups
It should say:
2.8.3 Fixing the Password Element
Fixing the Password Element involves an iterative hunting-and-pecking
technique using the prime from the negotiated group's domain
parameter set and an ECC- or FFC-specific operation depending on the
negotiated group.
To thwart side-channel attacks that attempt to determine the number
of iterations of the hunting-and-pecking loop used to find the PE for
a given password, a security parameter, k, is used that ensures that
at least k iterations are always performed. The probability that one
requires more than n iterations of the hunting-and-pecking loop to
find an ECC PE is roughly (q/2p)^n and to find an FFC PE is roughly
(q/p)^n, both of which rapidly approach zero (0) as n increases. The
security parameter, k, SHOULD be set sufficiently large such that the
probability that finding the PE would take more than k iterations is
sufficiently small. It is RECOMMENDED that an implementation set the
security parameter, k, to a value of at least forty (40) which will
put the probability that more than forty iterations are needed in the
order of one in one trillion (1:1,000,000,000,000)
2.8.3.1. ECC Operation for PWE
The group-specific operation for ECC groups uses pwd-value, pwd-seed,
and the equation for the curve to produce the Password Element.
First, pwd-value is used directly as an x-coordinate, v, with the
equation for the elliptic curve, with parameters a and b from the
domain parameter set of the curve, to check whether v^3 + a*v + b
is a quadratic residue modulo p.
If it is a quadratic non residue, this operation fails and the
hunting-and-pecking process continues. If it is a quadratic residue,
then the x-coordinate is saved and the current seed is stored. When
the hunting-and-pecking loop terminates, the x-coordinate is used
with the equation of the curve to solve for a y-coordinate. An
ambiguity exists since two values for the y-coordinate would be
valid, and the low-order bit of the stored base is used to
unambiguously determine the correct y-coordinate. The resulting
(x,y) pair becomes PWE.
Algorithmically, the process looks like this:
found = 0
counter = 1
do {
pwd-seed = H(token | peer-ID | server-ID | password | counter)
pwd-value = KDF(pwd-seed, "EAP-pwd Hunting And Pecking", len(p))
if (pwd-value < p)
then
v = pwd-value
if ((v^3 + av + b)) is a quadratic residue)
then
if ( found == 0 )
then
x = v
save = pwd-seed
found = 1
fi
fi
fi
counter = counter + 1
} while ((found == 0) || (counter < k))
y = sqrt(x^3 + ax + b)
if ( lsb(y) == lsb(save))
then
PWE = (x, y)
else
PWE = (x, p-y)
fi
Figure 3: Fixing PWE for ECC Groups
Checking whether a value is a quadratic residue modulo a prime can
leak information about that value in a side-channel attack.
Therefore, it is RECOMMENDED that the technique used to determine if
the value is a quadratic residue modulo p blind the value with a
random number so that the blinded value can take on all numbers
between 1 and p-1 with equal probability while not changing its
quadratic residuosity. Determining the quadratic residue in a
fashion that resists leakage of information is handled by flipping a
coin and multiplying the blinded value by either a random quadratic
residue or a random quadratic nonresidue and checking whether the
multiplied value is a quadratic residue (qr) or a quadratic
nonresidue (qnr) modulo p, respectively. The random residue and
nonresidue can be calculated prior to hunting and pecking by
calculating the Legendre symbol on random values until they are
found:
do {
qr = random() mod p
} while ( lgr(qr, p) != 1)
do {
qnr = random() mod p
} while ( lgr(qnr, p) != -1)
Algorithmically, the masking technique to find out whether or not a
value is a quadratic residue looks like this:
is_quadratic_residue (val, p) {
r = (random() mod (p - 1)) + 1
num = (val * r * r) mod p
if ( lsb(r) == 1 )
num = (num * qr) mod p
if ( lgr(num, p) == 1)
then
return TRUE
fi
else
num = (num * qnr) mod p
if ( lgr(num, p) == -1)
then
return TRUE
fi
fi
return FALSE
}
2.8.3.2. FFC Operation for pwe
The group-specific operation for FFC groups takes pwd-value, and the
prime, p, and order, r, from the group's domain parameter set (see
Section 2.2.1 when the order is not part of the defined domain
parameter set) to directly produce a candidate Password Element, pwe,
by exponentiating the pwd-value to the value ((p-1)/r) modulo the
prime. If the result is greater than one (1), the candidate pwe
becomes pwe, and the hunting and pecking continues.
Algorithmically, the process looks like this:
found = 0
counter = 1
do {
pwd-seed = H(token | peer-ID | server-ID | password | counter)
pwd-value = KDF(pwd-seed, "EAP-pwd Hunting And Pecking", len(p))
if (pwd-value < p)
then
temp = pwd-value ^ ((p-1)/r) mod p
if (temp > 1)
then
found = 1
pwe = temp
fi
fi
counter = counter + 1
} while ((found == 0) || (counter < k))
Figure 4: Fixing PWE for FFC Groups
Notes:
The key exchange in EAP-pwd is dragonfly which was described in RFC 7664. During the standardization of RFC 7664, comments were received to prevent a side-channel attack against the hunting-and-pecking loop and the technique used in RFC 7664 should be done in RFC 5931 to prevent side-channel attack.