Subject: [Cfrg] [CFRG] Zero-Padding Protocol level mitigation strategies against SPA attacks on Merkle-Damgard-style hashes (John Mattson's proposal and CPace)

From: Björn Haase <[email-masked]>
Date: Sun, 26 Apr 2020 12:30:43 +0200

Dear John,

I'd like to come back to our discussion of the context of the
"Zero-Padding" topic as a mitigation against side-channel attacks on
Merkle-Damgard-style hash constructions. In the CFRG iterim meeting, you
gave the pointer to Niel Samwel's work with his attack on SHA512. I
actually was already aware of this. My discussions with Niels made me
suggest a very similar zero-padding as in your suggestion for enhanced
deterministic signatures, where RNG outputs are to be combined with
deterministic components.
I have contacted Leijla and her group and also asked similar questions
to other people (BSI, ...) with side channel expertise. Note that for
CPace, we also have the need to protect some secret value that enters
into the hash invokation, similarly to your application.

I come to the conclusion that adding a zero-padding to hash
constructions such as in your suggestion and in the CPace-01 draft is
indeed a good idea. I do support your suggested construction for
improving deterministic signatures.

FYI, you will find enclosed Lejla's response to my related question
regarding the corresponding zero-padding in the CPace draft, which
closely resembles your applications for the signatures:

 >>Question: Do you believe a construction with such a zero-padding to
be harder to attack
 >>or is there no significant difference in your opinion.
 >
 >Yes, I believe that this is in general harder to attack, although it
is difficult to say how much
 >harder without defined numbers for parameters, password constraints etc.

Below you will find some more details. I think, that analyzing this
topic in more detail would be worthwile. I will try to motivate Lejla
and her group to setup a small research project on this.

I would appreciate if you could keep me synchronized with your findings
and results regarding protocol-level mitigations on side-channel attacks
on hashes.

Yours,

Björn
-------- Weitergeleitete Nachricht --------
Betreff: 	PAKE selection process: FWD: Protocol level mitigation
strategies against SPA attacks on SHA-512 for CPace
Datum: 	Sat, 21 Mar 2020 10:51:08 +0100
Von: 	Björn Haase <[email-masked]>
An: 	Stanislav V. Smyshlyaev <[email-masked]>

Dear Stanislav,

I would first like to thank you for your moderation of the PAKE
selection process.

My impression is that all participants in the discussions and review did
collaborate in a very serious and cooperative atmosphere. I see this
also as a result of your clearly structured and openly communicated
process procedures.

For the next steps, I would be willing to contribute for getting things
further regarding CPace and OPAQUE.

The most important aspect in my opinion is the specification of the
hash_to_curve substep, because in case of CPace this one really needs to
be designed in a side-channel protected way.

I would like to keeep you synchronized with my activities that I already
have started with respect to this point.

One aspect is the zero-padding that I have suggested in the
draft-haase-cpace-01  I-D. My zero-padding suggestion has been based on
mainly heuristical reasoning regarding SCA and DPA resilience so far. I
have meanwhile contacted people with more SCA and DPA expertise than I
could be providing. Among the people that I have contacted, I have
meanwhile obtained a first feedback from Lejla Batina, that such
zero-padding of the password should be considered to provide some level
of mitigation against SCA and DPA attacks (see below).

Possibly I will not be able to attend the online CFRG meetings at IETF
107. For this reason, I would like to inform you that If there will be
an official design team for CPace at CFRG, I will be willing to
contribute and please add me to the participant list.

Yours,

Björn.

-------- Weitergeleitete Nachricht --------
Betreff: 	Re: Your feedback would be appreciated // Protocol level
mitigation strategies against SPA attacks on SHA-512 for CPace Internet
Draft
Datum: 	Sun, 8 Mar 2020 13:29:00 +0100
Von: 	Lejla Batina <[email-masked]>
An: 	Björn Haase <[email-masked]>
Kopie (CC): 	Lejla Batina <[email-masked]>, Niels Samwel
<[email-masked]>, Riad S. Wahby <[email-masked]>

Dear Bjorn,
> The question shows up in the following context. Currently CPace is one
> of the remaining candidates in the CFRG Pake selection process. CPace
> runs a conventional Diffie-Hellman key exchange using a secret
> generator G = Map_to_point( hash(password ||
> sessionSpecificRandomDataKnownToAnAdversary ||
> possiblyAdversaryControlledInputs) ).
>
> The question relates to possible side-channels in the hashing
> operation. The adversary would like to learn the password from
> analysing the hash operation. The password is moreover of low entropy.
>
> For CPace on Curve25519, the CPace Internet draft 01 suggests to use
> SHA512 as hash and Elligator2 for the mapping.
>
> Obviously, there is the risk that the password will leak to power or
> EM analysis in the hashing operation. The question is, whether one
> could somewhat mitigate this risk on the protocol level.
>
> If the protocol inserts known random or adversarially controlled
> inputs in the first block of a SHA512 or SHA256 operation, there will
> be some points where logic operations combine the unknown with known
> inputs. One could possibly setup a leakage model and mount an attack
> based on correlation analysis.
>
> For this reason, the CPace internet draft suggests to add a zero-padding
>
> hash(password || zeroPaddingFIllingTheFirstHashBlock ||
> sessionSpecificRandomDataKnownToAnAdversary ||
> possiblyAdversaryControlledInputs)
>
> such that the password is first hashed into the complete intermediate
> state of the hash. The idea is that the adversary would first having
> the advantage of getting a higher-resolution trace for the first hash
> block (which is always identical). However, she possibly would have a
> harder work for extracting information from this: A divide and conquer
> approach attacking individual bytes of the password one after the
> other might be harder to mount.
>
> I understood from the discussions with Niels that one of the important
> points in your successful attack on SHA512 in deterministic Ed25519
> was that the attacked addition instruction had one secret and one
> varying random input known to the attacker as input operands.
>
> Question: Do you believe a construction with such a zero-padding to be
> harder to attack or is there no significant difference in your opinion.
>
Yes, I believe that this is in general harder to attack, although it is
difficult to say how much harder without defined numbers for parameters,
password constraints etc.

[....]

Best regards,

Lejla
>
>>> On 23 Jan 2020, at 23:53, Björn Haase <[email-masked]
>>> <mailto:[email-masked]>> wrote:
>>>
>>> Dear Niels, Dear Leijla,
>>>
>>> I hope you are well. I am just working on an Internet Draft for the
>>> CPace and AuCPace PAKE protocols. In this context, I'd appreciate
>>> your feedback/insight regarding possible mitigation approaches that
>>> might make a possible side-channel attack path against SHA512 more
>>> difficult by tweaks in the high-level protocol structure. I presume
>>> that you might be having slightly more insight than I do ;-).
>>>
>>> The draft is online at
>>> https://tools.ietf.org/html/draft-haase-cpace-00 . My question is
>>> specifically related to the following paragraphs in the specification.
>>>
>>> Basically the story is that the secret password (PRS) input to the
>>> hash is of low entropy (thus particularly vulnerable). Moreover the
>>> secret input would be directly passed to the hash function. There is
>>> also a session specific nonce (sid) which is under (partial) control
>>> of the adversary. I suggested to first hash the secret and pad it
>>> with zeros, so that for different nonce values the first hash block
>>> for a given secret is always identical. This would give a single
>>> trace with high accuracy but is presumed to make a lot of belief
>>> propagation necessary (and make a byte by byte correlation analysis
>>> more difficult). The variable nonce value (sid) is only added
>>> afterwards, when the short low-entropy secret is already absorbed in
>>> the (large) state of the hash construction:
>>>
>>>     "With ZPAD we denote a zero-padding string that is appended to PRS
>>>     such that DSI||PRS has a length of at least H_block.  CPace aims at
>>>     mixing in entropy of PRS into the full internal state of the hash
>>>     function before any adversary-known variable information (ADVI)
>>>     enters the hashing algorithm.  ADVI such as party identities or
>>>     session IDs might be partially controlled by an adversary.
>>>     Correlations of ADVI with the bare PRS string are considered to be
>>>     easier exploitable by side-channel methods in comparison to a pre-
>>>     hashed representation of PRS."
>>>
>>>     ...
>>>
>>>     "The map_to_group_mod_neg function is implemented as follows.  First
>>>     the byte length of the ZPAD zero-padding string is determined such
>>>     that len(ZPAD) = max(0, H_block_SHA512 - len(DSI1 || PRS)), with
>>>     H_block_SHA512 = 128 bytes.  Then a byte string u is calculated by
>>>     use of u = SHA512(DSI1||PRS||ZPAD||sid||CI).  The resulting string is
>>>     interpreted as 512-bit integer in little-endian format according to
>>>     the definition of decodeLittleEndian() from [RFC7748  <https://tools.ietf.org/html/rfc7748>].  The resulting
>>>     integer is then reduced to the base field as input to the Elligator2
>>>     map specified in [HASH2CURVE  <https://tools.ietf.org/html/draft-haase-cpace-00#ref-HASH2CURVE>] to yield the secret generator G =
>>>     Elligator2(u)."
>>>
>>>     ...
>>>
>>>     "The definitions above regarding the mapping deviate
>>>     from the definition in the encode_to_curve function from [HASH2CURVE  <https://tools.ietf.org/html/draft-haase-cpace-00#ref-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
>>>     attacks of an adversary that analyzes correlations between publicly
>>>     known information with the low-entropy PRS strings was considered
>>>     relevant in important settings."
>>>
>>>     ...
>>>
>>>     "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."
>>>
>>>     "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."
>>>
>>>
>>