TODO_review

Here is my review of the CPace draft 10. As a summary: looks like a decent protocol, there are a few presentation issues which are not hard to fix (e.g. there’s no actual specification of how character strings are turned into octet strings); my main reproach would be the use of the “network_encode()” function, which nominally is handled on the transport layer, but is here integrated into the key derivation, which breaches abstraction layers. This is likely to induce interoperability woes and much misery down the line, and I strongly recommend that the spec instead mandates use of the lv_cat() function (which the draft specifies, and uses for test vectors), systematically, regardless of whatever is used at the transport layer to convey the message elements to the other party (and is not even necessarily using octets).

Thomas

Detailed comments below:

# 1.1: "Section 4 gives an overview over" -> "... an overview of"
#
> Fixed

# 5.1: "the default output size in bytes corresponding to the symmetric
# security level of the hash function": this sentence is a bit confusing
# because hash function security has several meanings that would call for
# distinct output sizes. E.g. SHA-256 and SHAKE-128 are normally said to
# offer "128-bit security" but here H.b_in_bytes is asserted to be 32 for
# these functions. At this point in the document I suppose that what is
# meant is "the minimal output size needed for collision resistance at the
# expected security level" (i.e. you need at least 32 bytes to get 128-bit
# security against collisions).
#
> Fixed.

# 5.1: "input block size": maybe add a remark that this "block size" is
# the same concept as the one used in HMAC (with a reference to RFC 2104).
#
> Fixed

#5.2: "returning a representation of a scalar (referred to as 'scalar'
#from now on)": this feels weirdly circular. The word "scalar" was not
#defined before in the document, and the definition of a scalar should
#not be "it is a scalar". I suppose that the sentence should read as:
#"... returning a representation of an integer (referred to as 'scalar'
#from now on)"
#
> Fixed.

#5.2: the document uses multiplicative notation for the group operation,
#but the function scalar_mult is called scalar_mult and not pow or exp.
#
> Switched consistently to additive notation.


#5.3: LEB128 and lv_cat are specified in an appendix. Shouldn't that be
#moved to the main document? It feels weird to have these parts in an
#appendix.
> Fixed. Yes we added a textual description in addition to the reference code
> in the appendix.

# 5.3: sample_random_bytes(n) is defined as "a function that returns n
# octets uniformly distributed between 0 and 255", which can be understood
# in several ways. It can be "n octets, each selected with a uniform
# distribution between 0 and 255, and the octets are sampled independently
# of each other" (this is what is meant in the document). But it can also
# be read as "n copies of a single value which is sampled uniformly
# between 0 and 255". Or even "n octets out of the 256 that are between 0
# and 255", i.e. implicitly n distinct octets. I suggest making the
# wording a bit more precise, under the assumption that the document
# reader may be an implementer who is not ncessarily a professional
# cryptographer. This matters in particular for random selection of
# values, because bad sampling code will still "work", and thus may evade
# detection through functional testing (there are known precedents, e.g.
# when Sony was generating ECDSA signatures with a fixed secret scalar k).
#
> Fixed.

# 6.1: The diagram shows "[CI]" as being "public", but section 3.1 said
# that CI "may also include confidential information", which means that it
# is not, in fact, public. Maybe what is meant here is that it is a common
# value known to both parties.
#
> Fixed.

# 6.2: "was properly generated conform with" -> "was properly generated,
# in conformity with" ("conform" is a verb, it cannot be used that way).
#
> Fixed.

# 6.2: "Otherwise B returns ISK = H.hash(...). B returns ISK and terminates."
# -> the first "returns ISK" should be "computes ISK"
# -> idem for "Otherwise A returns ISK" in the next paragraph
#
> Fixed.

#6.2: the specification uses lv_cat on the concatenation of two character
#strings (G.DSI and "_ISK") but lv_cat expects octet strings, so that
#leaves the question of how character strings are converted to octet
#strings. There are several conventions in wide usage; even for strings
#with only ASCII characters, they could be encoded in UTF-8 (one byte per
#character), or some UTF-16 variant (two bytes per character, and in that
#case there is the question of endianness); there could (or could not) be
#a leading BOM; and there may or may not be a terminating NUL character,
#which could be included in the resulting sequence of octets. How
#characters become octets should really be specified somewhere in the
#document (e.g. in section 5.3).
#(See also point below on section 9.4 and strings with a 'b' prefix.)
> We added a clearifying specification and distinguished between character strings
> and byte strings by using the python-style notation with prepended b"some string"

#6.2: if A and B don't agree with each other about whether the protocol
#is in initiator/responder mode or in symmetric mode, then they will
#still get the same key about half of the time. It would feel "cleaner"
#if the actually used convention was explicitly part of the input to
#H.hash() for the key derivation, so that A and B do not end up with the
#same key out of luck if they do not have the same notion of how the
#protocol should go.
#
> Fixed by a change of the definition of the o_cat function.
> Accidental success can now be ruled out as o_cat prepends b"oc".


#6.2: The derived key depends on the used encoding, represented by
#network_encode() and nominally open to whatever the outer layer chooses.
#This is a somewhat leaky abstraction; the outer layer might use a
#representation that is not amenable to easy canonicalization; e.g.
#somebody will certainly try to put that in JSON, or even XML. Should the
#parties somehow order and hash XML data? Some network encodings could
#even be non-binary (e.g. QR codes mostly convey _characters_ in a
#specific subset of ASCII). That looks like a recipe for disaster, or at
#least implementation annoyance. An illustration of the problem is the
#test vectors from appendix B, which (necessarily) must assume a specific
#network_encode() (namely, lv_cat()) in order to provide the ISK value
#that should be obtained.
>
> Yes we agree.
# Also, concatenation of network_encode() values could be ambiguous. As
# 5.3 specifies it, network_encode() shall be such that an _individual_
# output of network_encode() can be unambiguously split into its two
# parameters, but that does not necessarily implies that concatenating
# both values is unambiguous. For instance, one could make
# network_encode(Y,AD) as the concatenation of, in that order: the length
# of Y (with LEB128), then Y, then AD. Given network_encode(Y,AD), you can
# recover Y and AD (by decoding the length of Y, which starts the string,
# so you know where the split occurs between Y and AD). But then, if you
# receive network_encode(Ya,ADa)||network_encode(Yb,ADb), you cannot
# always unambiguously recover Ya, ADa, Yb and ADb. This can imply
# unwanted collisions in ISK and that might make security proofs derail a
# bit.
#
#
# To avoid such issues, I would strongly recommend that the specification
# mandates that key derivation (computations of ISK) always uses
# lv_cat(Y,AD) regardless of how the messages were actually encoded over
# the wire (with network_encode()). This implies that in symmetric mode,
# the lexicographic order would be evaluated over lv_cat(), not
# necessarily what was sent.
# (In fact I think network_encode() should be removed from the document
# altogether; there should be lv_cat(), for key computation purposes, and
# otherwise some text that says "MSGa is the pair of values (Ya, ADa),
# sent to the peer with an unambiguous encoding format appropriate for the
# used transport medium".)
>
> Yes probably, you are right. The idea was to be able to re-use the
> current procedures used for the TLS encodings such that session key derivation
> for TLS does not require the additional lv_cat operation.
> However the hypothetical advantage here probably will not justify the
> possible inter-operability issue when allowing arbitrary network_encode functions.


# 7.1: maybe add a sentence to assert that the zero padding should not be
# considered as a requirement that the length of PRS be limited so that
# DSI||PRS||padding always fits on exactly one block? There are already
# too many systems out there that enforce _maximum_ password lengths at 8
# or 10 characters, for mostly mythical reasons. It might be good to
# preach the good word and state that PRS length should not be
# artificially limited, notwithstanding the zero padding. In particular,
# password managers tend to generate large high-entropy random passwords,
# and limitations on password length are a usual annoyance for them.
#
> Fixed. Note was added.

# 7.2.1: "on either, the curve or the quadratic twist" -> the comma looks
# misplaced. With the Oxford comma, it should be "on either the curve, or
# the quadratic twist". Or the comma could be simply removed.
#
> Fixed. Comma removed.


# 8: "with respect invalid encodings" -> "with respect to invalid encodings"
#
# 
# 8: "recieved" -> "received"
#
> Fixed

# 9.2: "the length of of all" -> "the length of all"
#
> Fixed

# 9.4: "calculate mac_key as as" -> "calculate mac_key as"
#
> Fixed

#9.4: Starting at the point, we begin to see notations like b"CPaceMac",
# i.e. the Python-like syntax for character strings which really are octet
# strings. This should be harmonized with the previous use of character
# strings (G.DSI, "_ISK",...) since these strings also implicitly assumed
# some sort of characters-to-octets conversion.
#
> Yes Consistently used the b"" syntax in the text body where octet strings
> are meant.

# 9.5: "We do so in order to reduce both, complexity of the implementation
# and reducing the attack surface" -> "We do so in order to reduce both the
# complexity of the implementation and the attack surface" (you don't
# reduce the reduction)
#
> Fixed.

#9.5: Rejection sampling can be a bit tricky to implement in practice; I
#encountered many implementations that did it in a non-constant-time way,
#thus leaking information on the scalars. Also, it means that the amount
#of randomness and generation time are only probalistically bounded; this
#can be a problem for embedded systems operating under strong latency
#constraints. In RFC 9380, the hash_to_field() process uses instead some
#oversampling (say, 16 extra bytes, beyond the field length) and a
#modular reduction. RFC 9380 is already referenced and used (for the
#computation of the generator); it cannot be used exactly "as is" because
#hash_to_field() targets the base field for the curve, not the scalar
#field, but the method is still applicable here and may be preferable to
#rejection sampling, at least in some usage contexts. Since the output of
#the oversampling+reduction method is not entirely uniform in the
#mathematical sense (it has a bias which is negligible, but it is still
#conceptually there), it is formally forbidden by this specification
#document (section 7.4.3 says "MUST BE uniformly random"; it does not say
#"MUST BE computationally indistinguishable from uniform random
#selection"). It might be worth adding a note in section 9.5 that the
#oversampling+reduction method is actually OK?
#
> Yes. Done. Thank you.

# 9.5: "begning" -> "benign"
#
> Fixed.


# 9.6: "The cofactor c' of the twist MUST BE EQUAL to or an integer
# multiple of the cofactor c of the curve." -> it's the opposite! The
# cofactor c must be a multiple of c'. The reason is that the x-only
# multiplication routine ensures that the scalar is a multiple of c
# (through the so-called "clamping") and we want in fact the scalar to be
# a multiple of both c and c'.
#
#
# Speaking of which, this point is missing from section 9.6: the scalar
# must be a multiple of c and c'. The general method is: generate the
# random (uniform) scalar, then multiply it by lcm(c,c') to get the actual
# scalar. X25519 and X448 can get away with "clamping" because the
# subgroup order is close enough to a power of two, the cofactors are
# themselves powers of 2 (c = 8 and c' = 4 for X25519), and X-only
# computations don't distinguish between points P and -P, so that the
# clamped scalars are still unbiased enough. Section 9.6 should state it
# clearly that being a multiple of lcm(c,c') is important and must be
# ensured in some way.
#
> Yes! Thank you. Of course it's just as you wrote and fixed now.


#9.6: The text lists as a requirement that the base field order p and the
#group order q must be "close to a power of two". This is not strictly
#necessary; having q close to a power of two only makes scalar sampling
#more convenient (you can avoid rejection sampling, and also
#oversampling, thus not requiring any reduction modulo q). If q is close
#to a power of two, then p will be close too (by Hasse's theorem,
#assuming the cofactor is itself a power of two). But if neither was
#close to a power of two, then everything would still be fine, provided
#that the scalars are sampled properly? This requirement is not really
#about using a Montgomery curve, but about using a simple scalar sampling
#method.
#
> Yes agreed. We have added a clearifying note here.


# 9.6: The section talks about Montgomery curves, but it really applies to
# any elliptic curve, since X-only algorithms work on all curve. It is
# just that Montgomery curves offer _efficient_ (hence tempting) X-only
# algorithms, and, on the other hand, necessarily have a cofactor (which
# is a multiple of 4), thereby requiring some specific extra care related
# to that cofactor.
#
> Yes. Changed the name of the subsection and added a corresponding sentence.

#9.8: About side-channel attacks: while the paragraph points out that
#calculate_generator is the primary target for such attacks, the scalar
#sampling and subsequent operations should be protected from
#side-channels as well. It is noteworthy that for short Weierstraß
#curves, the used reference is IEEE1363, which says nothing about
#side-channels and in particular describes curve operations with
#non-constant-time algorithms.
#
> Yes. Changed the wording. Thank you!

# A.5: pseudocode for Elligator2 uses the field order as parameter 'q'
# which is a bit confusing because it was called 'p' previously in the
# document, while 'q' designated the curve (sub)group order.
#
# Fixed that. Thank you. Naming in the main body was actually inconsistent
# Now p is the curve subgroup order and q is the field order.

# B.1.7 (and others): Some nitpicking: "ANSI-C" (or "ANSI C") was the C
# language as standardized by ANSI in 1989, but in 1990 the language was
# handed over to ISO, so that "ANSI-C" cannot formally include anything
# that was made part of the C language after 1990. In particular,
# 'uint8_t' was integrated in the language in the 1999 version (in a pure
# "ANSI C" dialect, you would have to use 'unsigned char' instead, and
# there would be the usual question about hardware platforms with bytes
# which are not octets). Thus, these section title should not be saying
# "ANSI-C". I suggest a more neutral wording, e.g. "Corresponding
# initializers in the C language". The complete formal name of the
# language is "ISO/IEC 9899:2017", which is precise but not very
# informative.
# (There is supposed to be a new variant soon, dubbed "C23", but it will
# probably show up only in 2024.)
#
> Fixed. Now we refer to C programming language initializers.
> We also added JSON version of the test vectors.

(I do not have time to check the test vectors right now.)



******************************************************************************************
******************************************************************************************
******************************************************************************************

Hello All,

I spent a couple of days re-reading the CPace draft 10 (
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-cpace-10) the 2021
security analysis paper by Abdella, Haase,
and Hesse (https://eprint.iacr.org/2021/114.pdf) and the process critique
paper by Hao (https://eprint.iacr.org/2021/839.pdf)
In particular, I looked at how CPace could be securely integrated into a
protocol like TLS 1.3.

----
#In 2019, we reviewed the original CPace proposal with colleagues at Inria>
#Prosecco and our review raised three points on the original proposal:
#
#1) CPace uses a unique connection identifier (CI) in the first message from
#  the initiator to the responder to prevent relay attacks.
#  It was not clear to us how this unique CI could be computed without
#  adding a round-trip to the protocol.
#
# 2) CPace relies on a unique session identifier (sid) for multi-session
#    security. This sid is also used in the first protocol message.
#    Again, it was not clear to us how the two parties could agree on an sid
#    without adding a round-trip to the protocol.
#
# 3) It was unclear whether key confirmation was needed or not.

# It is worth noting that 1) and 2) are also pointed out as potential CPace
# defects in Hao’s critique.

----
# After reviewing the latest CPace draft, I can confirm that these questions
# are now answered in the text:

# Connection Identifier (CI)
# - Section 3.1 now says that the CI is *optional*.
# - In response to our review, the authors said that the CI could use network
#   addresses (IP addresses and ports) which do not require a round-trip
# - The authors also say that CI is not needed if the application protocol
# provides key confirmation, which e.g. TLS 1.3 does
> We have further clarified the intended use of CI regarding party identity strings
> in the light of the crypto2024 paper and recommend party identities to be included
> in CI (with preference) or alternatively in ADa and ADb.

# Session Identifier (sid)
# - Section 3.1 now says that the sid is *optional*.
# - This section recommends that the two parties should jointly establish an
#   sid before the connection (which does imply an extra round-trip, at least
#   for TLS 1.3)
# - It also says that the initiator can unilaterally generate a fresh sid and
# send it to the responder (which would not require an extra round-trip).
> The aspect of the session identifer has been analyzed in the recent crypto2024 paper
> and it has been confirmed that CPace can be proven secure also without pre-agreed sid.
> This is now also stated in the text.

#Key Confirmation
# - Section 9.4 explicitly describes how to obtain Explicit Key Confirmation
#   if needed
# - Protocols like TLS 1.3 already provide key confirmation.

----
Given the above clarifications, the following security questions still
remain:

# - The multi-session security of CPace relies on a “jointly” generated
#   unique sid.
#   Does this proof still hold if the initiator unilaterally generates the
#   sid?
#   Couldn’t the responder be vulnerable to replay attacks in this setting?
#   How would one adapt the proof to account for unilateral “sid”s?
> The aspect of the session identifer has been analyzed in the recent crypto2024 paper
> and it has been confirmed that CPace can be proven secure also without pre-agreed sid.
> This is now also stated in the text.


# - What is the recommended way of integrating CPace into (say) TLS 1.3?
#   Does the ISK take the role of (EC)DHE shared secret in the key schedule?
#   Does the ISK become an additional input that is combined with an (EC)DHE
#   shared secret?
#   The definition and format of transcript in CPace is not exactly the same
#   as the TLS handshake transcript.
#   Are these two to be merged? If so, the test vectors of CPace would no
#   longer work.
> We added an explicit section with recommendations on how to integrate CPace
> in TLS 1.3.
> Originally we meant to leave the flexibility for implementers to use their
> own network encoding format for CPace such that the transcripts of TLS and
> CPace may match. However after considering the feedback of Thomas Pornin we
> agreed that it is better to enforce a specific form of the transcript even
> if that adds some level of redundancy for protocols such as TLS 1.3. 
> The advantage is that this way we will have inter-operability even if a higher-
> level protocol uses different types of encodings on the network layer.

# It if of course not expected that the CPace draft should answer these
# questions with concrete designs and formal proofs,
# but it would be useful to the reader and implementor to learn the answers
# to these questions and know the pitfalls of
# embedding CPace incorrectly into an application protocol.
#

# Best regards,
# Karthik

------------------------------------------

From: Bjoern Tackmann <bjoern.tackmann@ieee.org>
Date: Sun, 7 Jan 2024 at 01:39
Subject: Re: Request for review: CPace
To: Stanislav V. Smyshlyaev <smyshsv@gmail.com>
Cc: <cfrg-chairs@ietf.org>


Dear Stanislav,
it took me a bit longer than expected, but here comes my review. Overall the
document seems to be in pretty good shape, I’ve collected various comments 
I had while reading. The comments are almost exclusively editorial.

=======
Technical
#Section 7.1, if I understand correctly, len_zpad is defined to ensure that the prefix 
#of lv_cat(DSI, PRS, zero_bytes(len_zpad), CI, sid) fills the first hash function block.
#To me, there seem to be two issues with this:
#- First, it seems that DSI and PRS could even exceed H.s_in_bytes. 
#In that case the alignment at a block boundary would fail.
#
> Yes and we don't see how this could be producing a side-channel vulnerability as long 
> as such excessively long PRS strings would still have low entropy.
> As a response to Thomas Pornin we also have made explicit that use of long PRS strings
> is explicitly encouraged.

#-  Second, the "-1" seems to assume that the len_zpad is encoded as a single
#  byte in LEB128, which would mean it is < 128. This is likely true for all 
# realistic implementations, but the dependence on this unstated restriction is a but unfortunate.
> No there is no such assumption that alignment takes any meaningful role.
> In fact the side-channel considerations carried out by the teams whe have contacted only indicate
> that the essential helpful aspect might be that at least the first hash block should be completely filled
> (irrespective of the alingment idea). As such we think that we should not add the complexity
> of making the zero padding length dependent on the LEB128 encoding length.

Editorial
Page 6:
#- "The final section provides explicit reference implementations" 
#- Provides reference implementations? Is _provide_ the word you want to use here? 
# Is _reference implementations_?
# Maybe I have a different understanding of what a reference implementation is.
> We did rephrase that and state that we provide code for the functions. Regarding the reference
> implementation there is also a new section giving the link to the true reference implementation in sage.

#- Also, the formulation seems to indicate that only one more section follows, but 
# indeed there are many more sections in the document.
> Fixed.

#Page 7:
#- "CPace requires a shared secret octet string [...] is available for 
#  both parties A and B." – Somehow the grammar is broken in this sentence.
> We agree. We rephrased this as:
> "CPace requires that both parties A and B start the protocol with
> a shared secret octet string, namely the password-related string (PRS)."

  
#- "A and B will produce the same ISK value only if both sides did initiate" - 
#  I expected an "if and only if"
> Yes we added the "if and".

#- "CI, ADa, ADb and sid that will be specified in the upcoming sections" - 
#   why even list the names if the reader can anyway not understand them? 
#   Or at least link to the section number explicitly.
> We added the section number. 
 
# - "The values ADa (and ADb, respectively)" - why not just "The values ADa and ADb"?
> We rephrased this paragraph.

#Page 8:
#- "by use of a sid string" - reads weird, maybe "a string sid" 
#  or "a session identifier" or maybe just "sid" referring to the previous use of the term?
> We rephrased this section.

#Page 12:
#- "The length shall be prepended by using an LEB128 encoding of the 
#  length." - This seems confusing to me. Maybe "The length is encoded using LEB128"?
> Yes we did fix that.
  
# - "denotes function outputing" - "denotes a function outputting"?
> Fixed.

#Page 14:
# - "Testvectors of examples" - "Test vectors"
> Fixed.

#- s_in_bytes should probably be H.s_in_bytes in Section 7.1, although
#  H is also not referenced there.
> Fixed.
  
#Page 19:
#- "identy map" - "identity map"
> Fixed.

Page 21:
- "or the secret shared value "z" (otherwise)." - in the definition of this function, 
  z is not defined and whether it is secret or shared seems irrelevant.
> We rephrased this for making clear that the object "z" is something introduced and defined in [IEEE1363].
 
#Page 22:
#- "with respect [to] invalid"
> Fixed.

# - "recieved" - "received"
>Fixed.

# Page 24:
# - is in H.hash(b"CPaceMac" the b"..." intentional, if so, what does it mean?
> We now explicitly introduce this notation. (This aspect also has been 
> brought up by Thomas.)

#- "was demonstrated to be begning in [AHH21]" - I am not actually sure what that 
#  is supposed to say
> We rephrased this as
> [AHH21] demonstrated that non-uniform sampling did not negatively impact security
> in case of Curve25519 and Curve448.
  
  
#Page 25:
#- EQUAL - why capitalized?
> Fixed.

#Page 26:
#- why is Simultaneous capitalized for sSDH but not computational for sCDH?
> In [AHH21] the small "s" is used as acronym for "strong" and the large S in sSDH stands 
> for "simultaneous". We could also have used SCDH as a name for the assumption instead of 
> SDH but we kept SDH because the acronym SDH was used in previous papers.

#Subjective:
#- In the beginning of Section 6, there seems to be confusion between sending an 
#  empty string ADa vs. not sending ADa. For me, sending a length of 0 means sending an 
#  empty string. This does not seem important, but I think the text may become easier to 
#  read if this gets clarified and one consistent interpretation is used. 
#  (For instance, instead of always stating ADa and ADb as optional, one could just state 
#  that implementations that don't want to use these should just default them to the 
#  empty string. This is what seems to happen in the protocol anyway.)
> Agreed. Fixed.

#- At places, the punctuation seems quite unidiomatic to me, especially the frequent use 
#  of commas after the word "both".
> We did our best to rework that.