```
def littleEndianStringToInteger(k):
bytes = [ord(b) for b in k]
return sum((bytes[i] << (8 * i)) for i in range(len(bytes)))
def map_to_group_mod_neg_CPace25519(sid, PRS, CI):
m = hashlib.sha512()
p = 2^255 - 19
H_block_SHA512 = 128
DSI1 = b"CPace25519-1"
ZPAD_len = max(0,H_block_SHA512 - len(CI) - len(PRS))
ZPAD = ZPAD_len * "\0"
m.update(DSI1)
m.update(PRS)
m.update(ZPAD)
m.update(sid)
m.update(CI)
u = littleEndianStringToInteger(m.digest())
return map_to_curve_elligator2_curve25519(u % p)
def generate_ISK_CPace25519(sid,K,Ya,Yb):
m = hashlib.sha512(b"CPace25519-2")
m.update(sid)
m.update(K)
m.update(Ya)
m.update(Yb)
return m.digest()
``````
The definitions above aim at making the protocol suitable for
outsourcing CPace to secure elements (SE) where nested hash function
constructions such as defined in [RFC5869] have to be considered to
be particularly costly. As a result, the task of generating session
keys by a strong KDF function is left out of the scope of the CPace
protocol. This fact is expressed by the naming of the intermediate
shared Key ISK. The definitions above regarding the mapping deviate
from the definition in the encode_to_curve function from [HASH2CURVE]
by significantly reducing the amount of hash invocations. Moreover,
the CPace protocol specification, unlike the hash-to-curve draft
specification also considers the risk of side-channel leakage during
the hashing of PRS by introducing the ZPAD padding. Mitigating
Abdalla, et al. Expires January 29, 2021 [Page 10]
Internet-Draft CPace, a balanced composable PAKE July 2020
attacks of an adversary that analyzes correlations between publicly
known information with the low-entropy PRS strings was considered
relevant in important settings. We also avoid the overhead of
redundant cofactor clearing, by making the Diffie-Hellman protocol
responsible for this task (and not the mapping algorithm). Due to
its use in Ed25519 [RFC8032], SHA512 is considered to be the natural
hash choice for Curve25519. The 512 bit output of SHA512 moreover
allows for removing any statistical bias stemming from the non-
canonical base field representations, such that the overhead of the
HKDF_extract/HKDF_expand sequences from [HASH2CURVE] are considered
not necessary (in line with the assessments regarding Curve25519 in
[HASH2CURVE]).
4.2. CPACE-P256-SSWU_SHA256-SHA256
This cipher suite targets applications that do not as agressively
focus on efficiency, bandwidth and code size as the Curve25519
implementation. Instead it aims at reusing existing encoding and
curve standards wherever possible.
It uses the group of points on the NIST P-256 curve which is defined
in short Weierstrass form for constructing J [RFC5480]. The base
field F is the prime field built upon the Solinas prime p =
2^256-2^224+2^192+2^96-1. Encoding of full group elements requires
both, x and y coordinates. In order to facilitate point validation
and in order to be in line with recent TLS 1.3 requirements,
implementations MUST encode both, x and y coordinates. It is
RECOMMENDED to use the uncompressed format from [SEC1] using the 0x04
octet prefix. The strip_sign_information() function returns the
substring from the SEC1 representation encoding the x-coordinate of
the curve point.
NIST P-256 is of prime order and does not require cofactor clearing.
The scalar_cofactor_clearing function is the identity function with
scalar_cofactor_clearing(s) == s
The domain separation strings are defined as DSI1 = "CPace-P256-1",
DSI2 = "CPace-P256-2".
For the scalar_mult_cc function operating on the internally generated
points, a conventional scalar multiplication on P-256 is used, i.e.
without the need of further verification checks. The scalar_mult_ccv
function that operates on remotely generated points includes the
mandatory verification as follows. First from the encoded point the
x and y coordinates are decoded. These points are used for verifying
the curve equation. If the point is not on the curve,
scalar_mult_ccv returns the neutral element I. If the point is on
Abdalla, et al. Expires January 29, 2021 [Page 11]
Internet-Draft CPace, a balanced composable PAKE July 2020
the curve, scalar_mult_ccv calls scalar_mult_cc and returns the
result of the scalar multiplication.
For P-256, the map_to_group_mod_neg function is implemented as
follows. The zero-padding string length is calculated as len(ZPAD) =
max(0, H_block_SHA256 - len(DSI1 || PRS)) with H_block_SHA256 = 64.
For the mapping to the curve, a 32 byte string U1 = SHA256(DSI1 ||
PRS || ZPAD || sid || CI) is calculated. From U1 a second 32 byte
value is calculated as U2 = SHA256(U1). The concatenation of U1 and
U2 is interpreted as a 512 bit integer u by use of the u =
OS2IP(U1 || U2) function from [HASH2CURVE]. This value is reduced to
a 32 byte representation of a field element fu = u % p. The
coordinates (x,y) in F of the secret generator G are calculated as
(x,y) = map_to_curve_simple_swu_3mod4(fu) function from [HASH2CURVE].
As hash function H SHA256 is chosen, returning a session key ISK of
32 bytes length with ISK=SHA256(DSI2 || sid || Ks || Yas || Ybs).
The following sage code could be used as reference implementation for
the mapping and key derivation functions.
Abdalla, et al. Expires January 29, 2021 [Page 12]
Internet-Draft CPace, a balanced composable PAKE July 2020
``````
def map_to_group_mod_neg_CPace_P256(sid, PRS, CI):
m = hashlib.sha256()
H_block_SHA256 = 64
DSI1 = b"CPace-P256-1"
ZPAD_len = max(0,H_block_SHA256 - len(CI) - len(PRS))
ZPAD = ZPAD_len * "\0"
m.update(DSI1)
m.update(PRS)
m.update(ZPAD)
m.update(sid)
m.update(CI)
U1 = m.digest()
U2 = hashlib.sha256(U1).digest()
u = OS2I(U1 + U2)
return map_to_curve_simple_swu_3mod4(u)
def generate_ISK_CPace_P256(sid,K,Ya,Yb):
m = hashlib.sha256(b"CPace-P256-2")
m.update(sid)
m.update(strip_sign_information(K))
m.update(strip_sign_information(Ya))
m.update(strip_sign_information(Yb))
return m.digest()
``````
Similarly to the Curve25519 implementation, the definitions above aim
at making the protocol suitable for outsourcing to secure elements
where hash function invocations have to be considered to be
particularly costly. As a result, the task of generating session
keys by a strong KDF function is left out of the scope of the CPace
protocol. The naming of ISK as intermediate shared key reflects this
fact. Also the method for calculating the generator has been
optimized for reducing the number of hash calculations in comparison
to the suggestions [HASH2CURVE].
5. Security Considerations
A security proof of CPace is found in [cpace_paper].
Elements received from a peer MUST be checked by a proper
implementation of the scalar_mult_ccv method. Failure to properly
validate group elements can lead to attacks. The Curve25519-based
cipher suite employs the twist security feature of the curve for
Abdalla, et al. Expires January 29, 2021 [Page 13]
Internet-Draft CPace, a balanced composable PAKE July 2020
point validation. As such, it is mandatory to check that all low-
order points on both the curve and the twist are mapped on the
neutral element by the X25519 function. Corresponding test vectors
are provided in the appendix.
The choices of random numbers MUST be uniform. Randomly generated
values (e.g., ya and yb) MUST NOT be reused.
CPace is NOT RECOMMENDED to be used in conjunction with applications
supporting different username/password pairs. In this case it is
RECOMMENDED to use CPace as building block of the augmented AuCPace
protocol.
If CPace is used as a building block of higher-level protocols, it is
RECOMMENDED that sid is generated by the higher-level protocol and
passed to CPace. It is RECOMMENDED sid, is generated by sampling
ephemeral random strings.
Since CPace is designed to be used as a building block in higher-
level protocols and for compatibility with constrained hardware, it
does not by itself include a strong KDF construction. CPace uses a
simple hash operation for generating its intermediate key ISK. It is
RECOMMENDED that the ISK is post-processed by a KDF according the
needs of the higher-level protocol. In case that the CPace protocol
is delegated to a secure element hardware, it is RECOMMENDED that the
main processing unit applies a KDF to the externally generated ISK.
In case that side-channel attacks are to be considered practical for
a given application, it is RECOMMENDED to focus side-channel
protections such as masking and redundant execution (faults) on the
process of calculating the secret generator G. The most critical
aspect to consider is the processing of the first block of the hash
that includes the PRS string. The CPace protocol construction
considers the fact that side-channel protections of hash functions
might be particularly resource hungry. For this reason, CPace aims
at minimizing the number of hash functions invocations in the
specified mapping method.
CPace is proven secure under the hardness of the computational
Simultaneous Diffie-Hellmann (SDH) assumption in the group J (as
defined in [VTBPEKE]). Still, even for the event that large-scale
quantum computers (LSQC) will become available, CPace forces an
active adversary to solve one CDH per password guess. Using the
wording suggested by Steve Thomas on the CFRG mailing list, CPace is
"quantum-annoying".
Abdalla, et al. Expires January 29, 2021 [Page 14]
Internet-Draft CPace, a balanced composable PAKE July 2020
6. IANA Considerations
No IANA action is required.
7. Acknowledgments
Thanks to the members of the CFRG for comments and advice. Any
comment and advice is appreciated.
Comments are specifically invited regarding the following aspect.
The CPace mapping function design is based on the following
assessments. 1.) Masked, hardware-side-channel-protected hash
function implementations should be considered highly desirable for
the calculation of the generators G if an implementation might be
exposed to physical attacks. 2.) The complexity of such protected
hash implementations (possibly with lots of boolean-arithmetic
masking conversions) was assessed critical for constrained hardware.
Hash operation complexity was also assessed to be critical for secure
element chipsets that often were assessed to run hash operations in
software without hardware accellerator support.
This assessment is not in line with the assumptions for the hash-to-
curve-05 draft. As a consequence, this draft aimed at more
aggressively reducing the number of nested hash function invocations
in comparison to the suggestions of the hash-to-curve-05 draft.
8. References
8.1. Normative References
[HASH2CURVE]
Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and
C. Wood, "draft-irtf-cfrg-hash-to-curve-05", 2019.
IRTF draft standard
[IEEE1363]
IEEE, ""Standard Specifications for Public Key
Cryptography", IEEE 1363", 2000.
IEEE 1363
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
```.
Abdalla, et al. Expires January 29, 2021 [Page 15]
Internet-Draft CPace, a balanced composable PAKE July 2020
[RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk,
"Elliptic Curve Cryptography Subject Public Key
Information", RFC 5480, DOI 10.17487/RFC5480, March 2009,
.
[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
Key Derivation Function (HKDF)", RFC 5869,
DOI 10.17487/RFC5869, May 2010,
.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011,
.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, .
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
[SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1:
Elliptic Curve Cryptography", version 2.0", May 2009.
8.2. Informative References
[cpace_paper]
Haase, B. and B. Labrique, "AuCPace. PAKE protocol
tailored for the use in the internet of things.", Feb
2018.
eprint.iacr.org/2018/286
[VTBPEKE] Pointcheval, D. and G. Wang, "VTBPEKE: Verifier-based Two-
Basis Password ExponentialKey Exchange", 2017.
Proceedings of the 2017 {ACM} on Asia Conference on
Computer and Communications Security, AsiaCCS 2017
Abdalla, et al. Expires January 29, 2021 [Page 16]
Internet-Draft CPace, a balanced composable PAKE July 2020
Appendix A. CPace25519 Test Vectors
The test vectors for CPace25519 consist of three blocks.
First test vectors for X25519 are provided which is used as combined
scalar multiplication, cofactor clearing and verification function.
Specifically, test vectors for the small order points are provided
for checking that all small order points are mapped to the neutral
element
Then test vectors for the Elligator2 primitive are provided.
Then test vectors for the encoding of the secret generator are
provided combining the hash operation and the encoding of the
generator.
Finally test vectors for a honest party protocol execution are
provided, including derivation of the session key ISK.
A.1. X25519 test vectors
Abdalla, et al. Expires January 29, 2021 [Page 17]
Internet-Draft CPace, a balanced composable PAKE July 2020
########################### /X25519 ###############################
Test vectors for X25519 include three values:
- The scalar encoding prior to co-factor clearing and clamping, s
- The little-endian byte string encoding of the input point, u
- The expected little-endian byte string encoding of the result, r
Test vector for X25519 with a coordinate on J:
s: a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4
u: e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c
r: c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552
Test vector for X25519 with a coordinate on the twist J':
s: 4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d
u: e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a413
r: 95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957
Test vectors for X25519 with coordinates on J and J' that MUST all
yield the neutral element (0) independent of s:
s: a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4
u: 0000000000000000000000000000000000000000000000000000000000000000
u: 0100000000000000000000000000000000000000000000000000000000000000
u: e0eb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b800
u: 5f9c95bca3508c24b1d0b1559c83ef5b04445cc4581c8e86d8224eddd09f1157
u: ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
u: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
u: eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
u: cdeb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b880
u: 4c9c95bca3508c24b1d0b1559c83ef5b04445cc4581c8e86d8224eddd09f11d7
u: d9ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
u: daffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
u: dbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
r: 0000000000000000000000000000000000000000000000000000000000000000
########################### X25519/ ###############################
A.2. Elligator2 test vectors
Two test vectors are provided
Abdalla, et al. Expires January 29, 2021 [Page 18]
Internet-Draft CPace, a balanced composable PAKE July 2020
#################### /Elligator 2 ##################################
Vector set 1 as little endian byte strings:
in: bc149a46d293b0aeea34581349d72f8a5a96cd531102d67379cd9bfadd4ec800
out:66b68f7575cd282403fc2bd323ff04601203c1ec5516ce247f7c0adbef05d367
Vector set 1 as base 10 numbers:
in: 35391373371110637358764021258915994089392966
2186061014226937583985831318716
out: 46961069109971370193035504450677895166687682
601074157241352710439876254742118
####################################################################
Vector set 2 as little endian byte strings:
in: 89cf55d4b5d3f84b1634957ac503a32b84ba11471a96b227bca70a0c3bf26375
out:1db163c86ceca7621903c9412d6dc71b4ed263b687eed092b194b5e540bba308
Vector set 2 as base 10 numbers:
in: 530971929581761349677698694411105058011053992421528586742712709
85522606362505
out: 390779123641965710057372702362153599533842156764537839663973068
2305857171741
#################### Elligator 2/ ##################################
A.3. Test vectors for the secret generator G
Abdalla, et al. Expires January 29, 2021 [Page 19]
Internet-Draft CPace, a balanced composable PAKE July 2020
###################### /Secret generator G #########################
Inputs:
DSI1 = 'CPace25519-1'
PRS = 'password'
sid = SHA512('sid'), bytes 0 to 15
A = 'Ainitiator'
B = 'Bresponder'
AD = 'AD'
####################################################################
Outputs and intermediate results:
DSI1 = 435061636532353531392d31 string ('CPace25519-1') of len(12)
PRS = 70617373776f7264 ('password') string of len(8)
ZPAD = 98 zero bytes (before mixing in variable data)
sid = 7e4b4791d6a8ef019b936c79fb7f2c57 string of len(16)
CI = 41696e69746961746f7242726573706f6e6465724144
('AinitiatorBresponderAD') string of len(22)
u = SHA512(DSI1||PRS||ZPAD||sid||CI) as 512 bit little-endian int:
(0xced4bf3254970eaec9f304ed422d8fde59e8c4abb0a27c675b4820a0c2c8fd92
<< 256)
+ 0x6dd2899f728ed1620e01e3d7fb9f5cd86e06ee4b5d552bde1524e0cb1e9344e0
u as reduced base field element coordinate:
0x2166eb1800faff5408149f0fce62b7d9c6941fc79573a335a1d9b8a80868ed26
u encoded as little endian byte string:
26ed6808a8b8d9a135a37395c71f94c6d9b762ce0f9f140854fffa0018eb6621
Elligator2 output G as base field element coordinate:
0x307760941be97d7c68b037cb9d22d69838b60e194c50ded8b85873f9e1395126
Elligator2 output G encoded as little endian byte string:
265139e1f97358b8d8de504c190eb63898d6229dcb37b0687c7de91b94607730
###################### Secret generator G/ #########################
A.4. Test vectors for CPace DH
Abdalla, et al. Expires January 29, 2021 [Page 20]
Internet-Draft CPace, a balanced composable PAKE July 2020
##################### /CPace Diffie-Hellman ########################
Inputs:
Elligator2 output G as base field element coordinate:
0x307760941be97d7c68b037cb9d22d69838b60e194c50ded8b85873f9e1395126
Elligator2 output G encoded as little endian byte string:
265139e1f97358b8d8de504c190eb63898d6229dcb37b0687c7de91b94607730
Secret scalar ya=SHA512('ya'), bytes 0...31, as integer:
0xbfec93334144994275a3eba9eb0adf3fe40d54e400d105d59724bee398b722d1
ya encoded as little endian byte string:
d122b798e3be2497d505d100e4540de43fdf0aeba9eba375429944413393ecbf
Secret scalar yb=SHA512('yb'), bytes 0...31, as integer:
0xb16a6ff3fcaf874cb59058493cb1f28b3e20084ad6d46fcd3c053284d60cecc0
yb encoded as little endian byte string:
c0ec0cd68432053ccd6fd4d64a08203e8bf2b13c495890b54c87affcf36f6ab1
####################################################################
Outputs:
Public point Ya as integer:
0x79f9f2c1245fd8c4ab38bc75082f2daf6f47ca53fd5f0de7af72fee9c7ddd993
Ya encoded as little endian byte string:
93d9ddc7e9fe72afe70d5ffd53ca476faf2d2f0875bc38abc4d85f24c1f2f979
Public point Yb as integer:
0x18ac9063b4419695db48028d2eda7b2b2e649d22f56a5987eba9f05941de1c74
Yb encoded as little endian byte string:
741cde4159f0a9eb87596af5229d642e2b7bda2e8d0248db959641b46390ac18
DH point K as integer:
0x276896a227a09f389a04b9656099aa05ef8ec2b394cf32cc50cca9ae56334215
K encoded as little endian byte string:
15423356aea9cc50cc32cf94b3c28eef05aa996065b9049a389fa027a2966827
##################### CPace Diffie-Hellman/ ########################
A.5. Test vectors for intermediate session key generation
Abdalla, et al. Expires January 29, 2021 [Page 21]
Internet-Draft CPace, a balanced composable PAKE July 2020
#################### /Session Key derivation #######################
Inputs:
DSI2 = 435061636532353531392d32 string ('CPace25519-2') of len(12)
sid = 7e4b4791d6a8ef019b936c79fb7f2c57 string of len(16)
strings of length 32:
K = 15423356aea9cc50cc32cf94b3c28eef05aa996065b9049a389fa027a2966827
Ya= 93d9ddc7e9fe72afe70d5ffd53ca476faf2d2f0875bc38abc4d85f24c1f2f979
Yb= 741cde4159f0a9eb87596af5229d642e2b7bda2e8d0248db959641b46390ac18
####################################################################
string of length 64:
ISK = SHA512(DSI2 || sid || K || Ya || Yb)
= de0be1eeb7e6453d8c961353cd333694866f5432f24b0d4ed393cb6473e835df
265ce72613effa3368a907031d897c733d300dfdb364ff66d270b404cdfbcb0a
#################### Session Key derivation/ #######################
Authors' Addresses
Michel Abdalla
DI, Ecole Normale Superieure, Paris
Email: michel.abdalla@ens.fr
Bjoern Haase
Endress + Hauser Liquid Analysis
Email: bjoern.m.haase@web.de
Julia Hesse
IBM, Zuerich Research Laboratory
Email: JHS@zurich.ibm.com
Abdalla, et al. Expires January 29, 2021 [Page 22]